情報セキュリティ第07回

(1)

情報セキュリティ第07回

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

2/45

 はじめに

 秘密鍵暗号の復習

 公開鍵暗号の考え方



RSA暗号

 演習：RSA暗号

はじめに

3/45

前回の復習

4/45

論理積

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/45

論理和

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/45

排他的論理和

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

1

(2)

7/45

使用例 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/45

使用例 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/45

使用例 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/45

使用例 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/45

計算機と乱数：疑似乱数とは

 計算機は、基本的に「決まったことしかしない」もの。

 乱数のように「予想できないもの」を取り扱うことはできない。

 計算機で使用する乱数の多くは疑似乱数。

 疑似乱数は、計算機が内部で計算して「乱数っぽいもの」を生成したもの。

 疑似乱数は本当の意味での乱数にはなっていない。

 疑似乱数をどのように生成するか、いろいろな手法が検討・提案されている。

12/45

疑似乱数：多くの場合の例

 多くの疑似乱数は、種（seed）から、乱数列を生成する。

 今までの値を元に、何らかの処理を行い、乱数を生成。

単純な例

種 ^処理値1 ^処理値2 ^処理値3

…

乱数値1 乱数値2 乱数値3

処理処理処理

…

2

(3)

13/45



srand()

：

乱数の種（seed）から乱数系列を設定する関数。



rand() ：

乱数値を生成する関数。

UNIX での乱数値の生成

srand(unsigned int seed) srand(unsigned int seed)

rand() rand()

種処理値1 値2 値3 … 乱数値1 乱数値2 乱数値3 … srand(略) 1回目の

rand() 2回目の

rand() 3回目の

rand()

14/45 14/63

暗号と鍵



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



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

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

平文暗号文

鍵を利用して暗号化

正しい鍵で複合

変な暗号文文

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

15/45

2種類の暗号方式



秘密鍵方式



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



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



一般的に、処理が軽い。



公開鍵方式



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



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



一般的に、処理が重い。

共

公秘

16/45

秘密鍵暗号



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

共

秘密鍵



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



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

共共

平文暗号文暗号文平文

17/45

秘密鍵のイメージ



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

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

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

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

18/45 ID

PASSWD

Alice

Bob

② 送信

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

③ 「秘密鍵」で復号

ID PASSWD

① 「秘密鍵」で暗号化

盗聴しても、

復号できない……。

共

秘密鍵暗号による通信

3

(4)

19/45 ID

PASSWD

Alice

Bob

① 「秘密鍵」で暗号化

盗聴するぞ！

共

秘密鍵、持って無い！

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

秘密鍵暗号と鍵配送問題

20/45

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

ID PASSWD

Alice

Bob

盗聴するぞ！

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

21/45

今回の内容

 基礎技術：

 秘密鍵暗号方式

 暗号化

 ブロック暗号とストリーム暗号

 公開鍵暗号方式

 暗号化と認証

 ハッシュ値と一方向関数

 乱数

 実際の実装：



RSA

暗号の仕組み _22/45

公開鍵暗号

23/45

公開鍵と秘密鍵 (1)



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

公秘

公開鍵秘密鍵

ペア



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



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



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

24/45

秘密鍵と公開鍵 (2)



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

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



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



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

公秘

4

(5)

25/45

秘密鍵と公開鍵 (3)



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



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

秘公

26/45

公開鍵暗号のイメージ



鍵付きの貯金箱：



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

（箱が公開鍵に相当）。



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

（鍵が秘密鍵に相当）

27/45 ID

PASSWD

Alice

Bob

③ 送信

④ 「秘密鍵」で復号

ID PASSWD

② 「公開鍵」で暗号化

秘公

① 送信

公

公開鍵暗号方式

盗聴しても、

復号できな

公い……。

28/45

代表的な暗号



公開鍵暗号方式

 RSA暗号



楕円曲線暗号



秘密鍵暗号方式

 DES

 AES

 RC4

いろいろあります

29/45 ID

PASSWD

Alice

Bob

③ 送信

② 偽「公開鍵」で暗号化

① 送信

公

鍵配送問題

復号できる

秘ぞ差し替えてやろう

公

本物である保証は？

30/45

RSA 暗号

5

(6)

31/45

RSA 暗号とは



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

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

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

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



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



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



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



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

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

いだけ。 _32/45

RSA 暗号の鍵



秘密鍵



素数

p



素数

q

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

適当な正の整数

e



公開鍵

 n=p  q

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

33/45

RSA暗号の暗号化と復号



平文



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

C

を作成する場合。

 C=M

^d

mod n



ここで

d

と

n

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



平文



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

C

を作成する場合。

 M=C

^e

mod n



ここで

e

は秘密鍵、

n

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



公開鍵

n が因数分解できて p と q がわかると、

p,q,d から秘密鍵 e もばれてしまう！

34/45

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の作り方より

35/45

演習： RSA 暗号

36/45

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

素数を入力

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

6

(7)

37/45

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

=B3*B4

と入力

LCM(B3-1,B4-1)

と入力

38/45

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

ed/B8のあまりの値が1になるようなdを探して入力

39/45

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

暗号化したい値を入力

nより小さい値

40/45

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

=B11

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

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

今回は=F7 完成したM^e mod n が暗号文

M^eは値が大きく計算できないので、工夫が必要

41/45

演習： RSA 暗号復号

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

計算したC^dを入力。

今回は=I13 _42/45

注意点



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



例：10÷3= 3 あまり

1 なので、

10 mod 3 = 1 となる。

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

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

7

(8)

43/45

演習： RSA 暗号暗号化 (2) の意味



x

^y

mod n

を計算するとき、

Excel

だと、

x

^yは値が大きすぎて計算できない。



ab* mod n = (a mod n) * (b mod n) mod n を利用。



x

^y

mod n = (((x mod n) * x mod n ) * x mod n )

* x mod n) * x mod n ) …………

=mod(F3*$B$11,$7)

x

をかけて

mod n

するに相当

44/45

やること

45/45

課題の提出

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

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

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

情報セキュリティ 第07回