情報セキュリティ第08回

(1)

情報セキュリティ第08回

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

2/51

 はじめに

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

 公開鍵暗号と認証

 演習：ハッシュ値

はじめに

3/51

今回の内容

 基礎技術：

 秘密鍵暗号方式

 暗号化

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

 公開鍵暗号方式

 暗号化と認証

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

 乱数

 実際の実装：



RSA

暗号の仕組み _4/51

一方向関数とメッセージダイジェスト

5/51

こういう場合はどうする？

Hello World

Hellow World

Bob

送信

Hellow World

ファイルをダウンロードしてきたけど、正しくダウンロードで

きたかなぁなんとかして

検証したい

6/51

一方向関数とは



ある関数

f が、



任意の

x が与えられたとき、f(x)の値を求めること

は簡単、



任意の

y

が与えられたとき、

y=f(x)

となる

x

を求めることは難しい

とき、この関数は一方向関数であるという。

元の値計算結果

簡単

難解

1

(2)

7/51

メッセージダイジェストとは



ファイルの中身に対応して生成した固定長のbit列



フィンガープリント、ファイルの指紋、ハッシュ値とも



異なる中身の場合、同じメッセージダイジェストになる可能性は低い（ゼロではない）。



一方向関数である。



暗号と違い、復号はできない。

eee0ca57643e4b59 815847fdd152cd5c

This is a pen.

平文

フィンガープリント

639c7143c6937907 ef3bfbed7501d898

This is a book.

8/51

メッセージダイジェストの利用 (1)



文章のテキストファイルから生成できるビット列平文 ^{フィンガー}_プリント



異なる平文が、同じ指紋を生成する確率は低い。

平文

A

平文

B

違う指紋に



平文と指紋を受け取り、比較することで、平文が正しいか否かを判定できる。

9/51

メッセージダイジェストの利用(2)

Hello World

Bob

１）送信

メッセージダイジェスト

B Hellow

World

Hellow

World メッセージ

ダイジェスト A メッセージ

ダイジェスト

A

３）比較したら

違う値に！

失敗している！

2）メッセージ

ダイジェストを計算

10/51

メッセージダイジェストの利用(3)



多くのサイトで、ファイルの検証用にMD5値が置かれています。

http://www.tnlab.inf.uec.ac.jp/daihinmin/announce/180525.html

11/51

メッセージダイジェストの利用 (4)

 httpsでも使用されています。

 Firefox

では、httpsでの通信を行っているサイトで、

1.

上の青い部分を押す。

2.

詳細を表示を押す。

3.

証明書を表示を押すことで確認できます。

12/51

メッセージダイジェストの利用 (5)

 UNIXのパスワード認証は、実際にはパスワードは

保存されていません。



保存されているのは、パスワードのハッシュ値を保存しています。



パスワードを入力すると、

1.

入力されたパスワードのハッシュ値を計算。

2.

保存してあるハッシュ値と一致するか検証。

3.

一致していたら認証を通過。

となります。



ようするに、ハッシュ値が同じになるパスワードなら、

パスワードが異なっていても、認証を通ります。

2

(3)

13/51

広く使われているメッセージダイジェスト



メッセージダイジェストの代表的なものとして、MD5や

SHA等があります。



メッセージダイジェストは、いろいろなところで使用されています。

 OpenOffice.org

のような、ファイルのダウンロードの検証のため。

 WindowsやUNIXにおけるパスワード認証。

 https

等の暗号化プロトコル。



メールの暗号化プロトコルである

PGP

。



メールの認証プロトコルである

apop

。

14/51

メッセージダイジェストの利用 (6)



ニュースにも（それらしきものが）登場します。

15/51

強衝突耐性と弱衝突耐性



弱衝突耐性：

 x

が与えられたとき、

f(x) = f(y)

なる

y (

^ただし

y

≠

x)

を発見することは難しい。



強衝突耐性：

 f(x) = f(y)

なる

x

と

y (

ただし

x

≠

y)

を発見することは難しい。

 MD5は強衝突耐性は無いことが知られている。

16/51

認証

17/51

復習：公開鍵暗号の鍵 (1)



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

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



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



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

公秘

平文暗号文暗号文平文

18/51

公開鍵暗号の鍵 (2)



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



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



前回のRSA暗号も、この性質を備えている。

秘公

平文暗号文暗号文平文

3

(4)

19/51

直感的なイメージ (1)

Hello World

Hello World Hello

World 送信

Bob

Alice

Hello World

送信

このファイル、本当に

Alice

から送られてきたのかなぁ...

20/51

公開鍵暗号方式と認証



「Aliceの公開鍵」で復号できる暗号文なら、その暗号文は「Aliceの秘密鍵」で作成したに違いない。



「

Alice

の秘密鍵」で暗号化できるのは、秘密鍵を持っ

ている

Alice

だけ。

「Aliceの公開鍵」で復号できるものは、

Aliceのファイルに違いない！

21/51 hogehoge

Alice

Bob

②

送信

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

③

暗号文を「

Alice

の公開鍵」で復号

hogehoge

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

①

平文を

「Aliceの秘密鍵」で暗号化

直感的なイメージ(2)

Aliceの公開鍵で復号できた！

暗号文を作れるのは

Alice

だけだから、このファイルはAlice

のだ！

22/51 hogehoge

Mallory

Bob

②

送信

Asdfasdfasdf adfasdf

③

暗号文を「

Alice

の公開鍵」で復号

sdlakfjl Hoaslkjlsalf;j;

Asdfasdfasdf adfasdf

①

平文を

「Malloryの秘密鍵」で暗号化

直感的なイメージ(3)

Aliceの公開鍵で復号に失敗！

このファイルは、

Alice

のものではない！？

Aliceを語って

送信だ！

23/51

復習： RSA 暗号の鍵



秘密鍵



素数

p



素数

q

 (p  1)(q  1)

と素かつ

(p  1)(q  1)

より小さい、

適当な正の整数

e



公開鍵

 n=p  q

 ed mod (p  1)(q  1)= 1

となるような

d

24/51

復習： RSA 暗号の暗号化と復号



平文



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

C

を作成する場合。

 C=M

^d

mod n

ここで d

と

n

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



暗号文

C

を復号する場合。

 M=C

^e

mod n

ここで e

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



公開鍵

n

が因数分解できて

p

と

q

がわかると、

p,q,d

から秘密鍵

e

もばれてしまう！

4

(5)

25/51

復習： RSA 暗号の理屈

C

^e

mod n

は本当に元の平文

M

に戻るのか？

n C

^e

mod

 M

^{オイラーの定理より}

p

と

q

が素数ならば

n M

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

mod

 ^{edの決め方から}

n M

^ed

mod



数式を展開

n n

M

^d

mod )

^e

mod

 (

C

の作り方より

26/51

認証の暗号化と復号



平文



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

C

を作成する場合。

 C=M

^e

mod n



ここで

e

は秘密鍵、

n



暗号文Cを復号する場合。

 M=C

^d

mod n

ここで d

と

n

27/51

今回の場合

C

^d

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

n C

^d

mod

 M M

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

mod n



^{ここから先は元と一緒}

n M

^ed

mod



数式を展開

n n

M

^e

mod )

^d

mod

 (

C

の作り方より

28/51

なりすましの防止と電子署名

29/51

認証と秘密鍵

 なりすましを防止するには、どうすればよいか？

→ ようするに、相手が本当に本人か確認したい！

認証・署名

 実世界では、印鑑やサイン、パスワードで本人確認。

 本人確認は、「本人しか持っていない情報を持っているか」で確認する。

秘密鍵は「本人しか持っていない情報」

30/51

なりすまし防止のアイディア (1)

公

Bob

AliceからBobにファイルを送るので、

BobはAliceからのファイルかを

検証したい

Aliceの

Alice

秘

平文

5

(6)

31/51

なりすまし防止のアイディア (2)

送信

公 Aliceの Aliceの

Bob

Alice

① Aliceの公開鍵を

事前に渡しておく秘

平文

公 Aliceの

32/51

なりすまし防止のアイディア (3)

秘

平文

Bob

Alice

② ハッシュ値を計算

① 公開鍵を事前に渡しておく

33/51

なりすまし防止のアイディア(4)

秘

平文

Bob

Alice

フィンガープリント公暗

③ 秘密鍵で暗号化

① 公開鍵を

事前に渡しておく ^34/51

なりすまし防止のアイディア(5)

秘

平文

Aliceの Aliceの

Bob

Alice

送信

平文

公公暗

④ 送信

35/51

なりすまし防止のアイディア (6)

秘

平文

Aliceの Aliceの

Bob

Alice

送信

平文

公公暗

④ 送信

フィンガー

プリント ⑤ 復号する Aliceからの

メールか検証しよう……

36/51

なりすまし防止のアイディア (7)

秘

平文

Aliceの Aliceの

Bob

Alice

送信

平文

公公暗

④ 送信

フィンガー

プリント ⑤ 復号するフィンガー

プリント

⑥ ハッシュ値を計算 Aliceからの

メールか検証しよう……

6

(7)

37/51

なりすまし防止のアイディア (8)

秘

平文

Aliceの Aliceの

Bob

Alice

送信

平文

公公暗

④ 送信

フィンガー

プリント ⑤ 復号するフィンガー

プリント

⑥ ハッシュ値を計算

⑦ 比較して同じなら

Aliceからの

メールだ！

Aliceからのメールか検証しよう……

38/51 フィンガー

プリントフィンガープリント

なりすまされた場合 (1)

平文

暗

公 Eveの

Bob

なりすまし

Eve

_パス

＋フレーズ

EveがAliceの名前を騙って、

Bob

にファイルを送る。

BobはAliceのファイルか検証したい

プリント

フィンガープリントフィンガー

なりすまされた場合(2)

平文

暗

送信

平文

異なる何か

暗公

Aliceの Eveの

Bob

Aliceの公開鍵で

元に戻せない！。

Aliceからの

メールじゃない！

なりすまし

Eve

プリント

なりすまされた場合(3)

平文

暗

送信

平文

異なる何か

暗公

Aliceの Eveの

Bob

Alice

の公開鍵で元に戻せない！。

Aliceからの

メールじゃない！

なりすまし

Eve

Eveは Alice

の秘密鍵を

知らないので、

Aliceの公開鍵で

復号できる暗号化済み指紋を

作れない。

改竄された場合 (1)

平文

暗

送信

公 Aliceの

Bob

送信中に、

データが変わってしまった！

パス

＋フレーズ秘 Aliceの

Alice

_42/51

異なるフィンガー

プリント

改竄された場合 (2)

平文

暗

送信

異なる平文

暗公

Aliceの

Bob

Aliceの公開鍵で

正常に通信できてない！

パス

＋フレーズ秘 Aliceの

Alice

7

(8)

43/51 異なる

改竄された場合 (3)

平文

暗

送信

平文

暗公

Aliceの

Bob

Aliceの公開鍵で

正常に通信できていない！

秘 Aliceの

Alice

指紋の値が異なるので、

正常に通信できていないことがわかる。

44/51

なりすまし防止の手順



以下のような流れで行われる。

1. Aliceは平文のフィンガープリントを作成する。

2. AliceはAliceの秘密鍵とパスフレーズでフィンガープ

リントを暗号化

3. Aliceは、平文と3で生成したものを、Bobにメール 4. Bobは、Aliceの公開鍵でAliceから送られた『暗号化

されたフィンガープリント』を復号する。

5. Bobは、『Aliceから送られてきた平文

^』から作ったフィンガープリントと、4のフィンガープリントを比較する。

45/51

何が守れているのか

 盗聴について：

 対処されていない。

 なりすましについて：

 対処されている。

 ただし、改竄と区別は付かない。

 改竄について：

 対処されている。

 ただし、なりすましと区別は付かない。

さらに暗号技術等と組み合わせる必要がある

46/51

次のステップ

 暗号技術で盗聴に、認証技術でなりすましや改竄を防止することができる。

 説明のあちこちにある「公開鍵を事前に渡しておく」

の具体的な方法が、今のところノータッチ。



偽物の公開鍵を掴まされたりしないか？



直に会えば確実だけど、相手が地球の裏側に居たりするなら、どうするの？

暗号技術と認証技術を組み合わせれば、

これらすべてに対処できる（はず）！

47/51

演習：一方向関数とハッシュ値

48/51

fuko でのフィンガープリント (1)

1. fukoにログインする。

2. Solaris では digest コマンドでMD5の値を求めること

ができる。

として、ファイルのMD5の値を出力してみましょう。

3.

とすることで、ファイルのsha1の値を出力してみましょう。

%/> digest –a md5 ファイル名

%/> digest –a sha1 ファイル名

8

(9)

49/51

課題でやること

1.

テキストファイルを作成する。中身は以下の通り。

2. md5とsha1のハッシュ値を計算する。

3.

テキストファイルを作成する。中身は以下の通り。

4. md5とsha1のハッシュ値を計算する。

5.

中身が異なっていることを確認する。

catcat

cutcut

50/51

課題でやること (1)

1.

さまざまな単語等のMD5値を求め、近い値が出るか挑戦しましょう。（注：出ません）

2.

入力した単語と、そのMD5値をレポートにまとめてください。

 各結果をテキストファイルもしくはWordファイルにまとめ、経情グループウェアから提出しなさい。

51/51

課題でやること(2)

 以下をレポートにまとめて提出。

Amazon等で、曰く「セキュアなログイン」等を利用し

ているとき、

“

自分が、なぜ安全だと思って通信しているのか

”

を書く。



調べ物の課題ではなく、

“今までの自分がどう

思っていたか

”

を書く。

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

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

情報セキュリティ 第08回