情報セキュリティ第05回

(1)

情報セキュリティ第05回

大久保誠也静岡県立大学経営情報学部

2/42

 はじめに

 秘密鍵暗号の復習

 公開鍵暗号の考え方



RSA暗号

 演習：RSA暗号

はじめに

3/42

前回の復習

4/42

論理積

x y x  y 0 0 0 0 1 0 1 0 0 1 1 1

ビット毎の論理積の例：

2つの0,1の値がどちらも1なら1に、

さもなければ0になる。

記号は



で書かれることが多い。

C言語等ではビット毎の論理積を＆で書く

00100101 00101101

&10110101

5/42

論理和

x y x  y 0 0 0 0 1 1 1 0 1 1 1 1

ビット毎の論理和の例：

2つの0,1の値のどちらかが1なら1に、

さもなければ1になる。

記号は



C

言語等ではビット毎の論理積を

|

で書く

10111101 00101101

| 10110101

6/42

排他的論理和

x y x  y 0 0 0 0 1 1 1 0 1 1 1 0

ビット毎の排他的論理和の例：

2つの0,1の値が同じなら0に、

異なっていたら1になる。

記号は



10011000

^もとの

データと

00101101

一緒

 10110101 10011000

00101101

 10110101

(2)

7/42

使用例 3 ：

#include<stdio.h>

int main(){

int i;

int test;

test=6; // 110 for(i=0;i<=3;i++){

printf("---i=%d ¥n",i);

printf("%d ¥n",test & i );

printf("%d ¥n",test | i );

printf("%d ¥n",test ^ i );

} }

#include<stdio.h>

int main(){

int i;

int test;

test=6; // 110 for(i=0;i<=3;i++){

} }

6の2進数表記は0110 i=0からスタート 0

の

2

進数表記は

0000

0110 & 0000 = 0000 10進数表記で0

0110 | 0000 = 0110 10進数表記で6 0110 ^ 0000 = 0110

10

進数表記で

6

_8/42

使用例 3 ：

#include<stdio.h>

int main(){

int i;

int test;

test=6; // 110 for(i=0;i<=3;i++){

} }

#include<stdio.h>

int main(){

int i;

int test;

test=6; // 110 for(i=0;i<=3;i++){

} }

6の2進数表記は0110 i=1のとき

1

の

2

進数表記は

0001

0110 & 0001 = 0000 10進数表記で0

0110 | 0001 = 0111 10進数表記で7 0110 ^ 0001 = 0111 10

進数表記で

7

9/42

使用例 3：

#include<stdio.h>

int main(){

int i;

int test;

test=6; // 110 for(i=0;i<=3;i++){

} }

#include<stdio.h>

int main(){

int i;

int test;

test=6; // 110 for(i=0;i<=3;i++){

} }

6

の

2

進数表記は

0110 i=2のとき

2の2進数表記は0010

0110 & 0010 = 0010 10進数表記で2

0110 | 0010 = 0110 10進数表記で6 0110 ^ 0010 = 0100

10進数表記で4

_10/42

使用例 3：

#include<stdio.h>

int main(){

int i;

int test;

test=6; // 110 for(i=0;i<=3;i++){

} }

#include<stdio.h>

int main(){

int i;

int test;

test=6; // 110 for(i=0;i<=3;i++){

} }

6

の

2

進数表記は

0110 i=3のとき

3の2進数表記は0011

0110 & 0011 = 0010 10進数表記で2

0110 | 0011 = 0111 10進数表記で7 0110 ^ 0011 = 0101 10進数表記で5

11/42 11/63

暗号と鍵



平文から暗号文を生成するとき、鍵を使用する。



復号するときも鍵を使用する。

適切な鍵を利用しないと、平文に戻せない。

平文暗号文

鍵を利用して暗号化

正しい鍵で複合

変な暗号文文

正しい鍵以外では複合できない

12/42

2 種類の暗号方式



秘密鍵方式



暗号化も複合も、同じ鍵を使用する。



秘密鍵を使用する。鍵は秘匿しておく必要がある。



一般的に、処理が軽い。



公開鍵方式



暗号化と復号で、異なる鍵を使用する。



公開鍵と秘密鍵があり、秘密鍵は秘匿し、公開鍵は公開しておく。



一般的に、処理が重い。

共

公秘

(3)

13/42

秘密鍵暗号



暗号化も復号も、同じ鍵を使用する。

共

秘密鍵



秘密鍵は第三者に渡してはいけない。



処理が軽いため、大きい平文を暗号化できる。

共共

平文暗号文暗号文平文

14/42

秘密鍵のイメージ



暗号化も復号も、同じ鍵を使用する。

鍵を持っている人は開けることができて、

鍵を持っていない人は開けることができない鍵を持っている人は開けることができて、

鍵を持っていない人は開けることができない

15/42 ID

PASSWD

Alice

Bob

② 送信

あｓｄふぁｓｄＪｌｋｊぇｗｋｆ

③ 「秘密鍵」で復号

ID PASSWD

① 「秘密鍵」で暗号化

盗聴しても、

復号できない……。

共

秘密鍵暗号による通信

16/42 ID

PASSWD

Alice

Bob

① 「秘密鍵」で暗号化

盗聴するぞ！

共

秘密鍵、持って無い！

送ってもらうわけにもいかないしなぁ

秘密鍵暗号と鍵配送問題

17/42

鍵配送問題解決のアイデア

ID PASSWD

Alice

Bob

盗聴するぞ！

開ける鍵と閉める鍵をわけちゃえばいいんじゃない？

18/42

公開鍵暗号

(4)

19/42

公開鍵と秘密鍵 (1)



秘密鍵と公開鍵は、一対のもの

公秘

公開鍵秘密鍵

ペア



秘密鍵は、自分しか知らない。



公開鍵は、世間に公開する。



処理が重いため、小さい平文を暗号化するのに使用される。例えば、秘密鍵暗号の秘密鍵を暗号化する。

20/42

秘密鍵と公開鍵 (2)



暗号化と復号では、異なる鍵を使用する。

公開鍵で暗号化し、秘密鍵で復号する。



秘密鍵は第三者に渡してはいけない。



処理が重いため、基本的に小さい平文を暗号化する。

公秘

21/42

秘密鍵と公開鍵(3)



提案されている実現方法は、秘密鍵で暗号化し、公開鍵で復号できる公開鍵暗号方式が多い。



この性質は、次回以降に行う「認証」を実現する際に利用されている。

秘公

22/42

公開鍵暗号のイメージ



鍵付きの貯金箱：



誰でも中にお金を入れることができる

（箱が公開鍵に相当）。



中身を取り出せるのは鍵を持っている人だけ。

（鍵が秘密鍵に相当）

ID PASSWD

Alice

Bob

③ 送信

④ 「秘密鍵」で復号

ID PASSWD

② 「公開鍵」で暗号化

秘公

① 送信

公

公開鍵暗号方式

盗聴しても、

復号できな

公い……。

代表的な暗号



公開鍵暗号方式

 RSA暗号



楕円曲線暗号



秘密鍵暗号方式

 DES

 AES

 RC4

いろいろあります

(5)

25/42 ID

PASSWD

Alice

Bob

③ 送信

② 偽「公開鍵」で暗号化

① 送信

公

鍵配送問題

復号できる

秘ぞ差し替えて

公やろう

公

本物である保証は？

26/42

RSA 暗号

27/42

RSA暗号とは



代表的な公開鍵暗号方式の一つ。

 1977年に、Rivest、Shamir、Adelmanの3人が発見。

当時、まだアイデアしかなかった公開鍵暗号方式に、

具体的な実現方法を示した。



最初の公開鍵暗号方式だが、現在でも幅広く使用されている。



因数分解の難しさに安全性の根拠を置く。



因数分解が解けると、暗号も解ける。



因数分解が、将来も難しい保証はない。

あくまでも、今の人類が効率的な解き方を知らな

いだけ。 _28/42

RSA暗号の鍵



秘密鍵



素数

p



素数

q

 (p  1)(q  ^{1)と素かつ(p}  1)(q  ^{1)より小さい、}

適当な正の整数

e



公開鍵

 n=p  q

 ed mod (p  1)(q  1)= 1 となるような d

29/42

RSA 暗号の暗号化と復号



平文



を暗号化して暗号文Cを作成する場合。

 C=M

^d

mod n



ここで

d

と

n

は公開鍵であることに注意。



平文



^{を暗号化して暗号文}

C

を作成する場合。

 M=C

^e

mod n



ここで

e

は秘密鍵、nは公開鍵であることに注意。



公開鍵

n

が因数分解できて

p

と

q

がわかると、

p,q,d

から秘密鍵

e

もばれてしまう！

30/42

RSA 暗号の理屈

C

^e

mod n は本当に元の平文Mに戻るのか？

 M

n C

^e

mod

n n

M

^d

mod )

^e

mod

 (

n M

^ed

mod



n M

⁽^p^¹⁾⁽^q^¹⁾^¹

mod



オイラーの定理より pとqが素数ならば

ed

の決め方から

数式を展開 Cの作り方より

(6)

31/42

演習： RSA 暗号

32/42

演習： RSA 暗号鍵の準備 (1)

素数を入力

素数を入力 (p1)(q1)より小さく、(p1)(q1) と素な、正の数を入力

33/42

演習：RSA暗号鍵の準備(2)

=B3*B4

と入力

LCM(B3-1,B4-1)

と入力

34/42

演習：RSA暗号鍵の準備(3)

ed/B8のあまりの値が1になるような d

を探して入力

演習： RSA 暗号暗号化 (1)

暗号化したい値を入力

nより小さい値

演習： RSA 暗号暗号化 (2)

=B11

=mod(F3*$B$11,$B7) F4のセルを

コピーしてペースト計算したM^eを入力。

今回は=F7

(7)

37/42

演習： RSA 暗号復号

暗号化と同様にしてC^dを計算

計算したC^dを入力。

今回は=I13 _38/42

注意点



mod は、あまりを計算する演算です。

例：10÷3= 3 あまり 1 なので、

10 mod 3 = 1 となる。

今回の演習では、MS-Excelの制限で、あまり大きい値を暗号化・復号することができません。

小さい値で行いましょう。

39/42

やること

40/42

課題の提出

 今日のMS-Excelのファイルを経情グループウェアから提出する。

 ファイル名は学籍番号の末尾にfをつけたものとする。

 グループ名は『H28_情報セキュリティ』です。

情報セキュリティ 第05回