『暗号のおはなし』：第4章まとめ
Amazon.co.jp：暗号のおはなし―情報セキュリティの基盤 (おはなし科学・技術シリーズ)
- 第1章 暗号とは
- 第2章 DESからAESへ
- 第3章 鍵配送方式と公開鍵暗号
- 第4章 デジタル署名と認証方式
- 第5章 ネットワーク暗号に向けて
- 第6章 暗号のひろがり
- 第7章 ヒューマンクリプト
本記事では第4章の要約を載せる。なお、記事中の図はすべて本書より引用した。
デジタル署名
共通鍵暗号方式を用いて通信すれば、送り手や通信内容の認証(メッセージ認証)も同時に行われている。ただ、送り手と受け手で同じ鍵を持っているため、当事者同士の争いを解決することはできない。
そこで公開鍵暗号方式を逆にすることが行われる。つまり、送り手の秘密鍵で認証文を作り、受け手が公開鍵で復号を行うのである。
このやり方はどんな公開鍵暗号方式でも可能というわけではないが、RSA暗号では可能である。
ハッシュ関数 …… 範囲の限定されていない情報を、一定の範囲の値に対応づける関数。ハッシュ関数の値をハッシュ値と呼ぶ。
今、文書Mを捺印付きで送る場合、送り手側はMのハッシュ値Dを自身の秘密鍵で暗号化する。その結果であるV_Aを文書Mに対する認証子と呼ぶ。送り手は文書Mにこの認証子V_Aを添え、認証文(M, V_A)を送る。受け手側はV_Aを送り手の公開鍵で復号し、Mのハッシュ値と比較することによって文書の正しさを確かめられる。つまり、認証子が署名・捺印の役割を果たすのである。この認証方式をデジタル署名(電子署名)と呼ぶ。
RSA署名 …… RSA暗号を用いたデジタル署名。
誕生日のパラドックス
衝突困難ハッシュ関数 …… 電子署名に用いられるハッシュ関数はなるべく衝突がないように(別々の入力に対して同じ出力が得られないように)しなければならない。そのようなハッシュ関数を衝突困難ハッシュ関数という。
誕生日のパラドックス …… 無作為なn人のうち、少なくとも同じ誕生日のペアが一組存在する確率は直観的なものより高いというもの。ハッシュ関数を考える際はこのことを考慮するべきである。ハッシュ値がnビットのハッシュ関数に対し、勝手に選んだ入力に対するハッシュ値がある特定の値をとる確率は1/(2^n)であるが、同じハッシュ値を与える二つの異なる入力を見つけるのは2^(n/2)回試せば1/2の確率で見つけることができてしまう。
ハッシュ関数の標準
- SHA-1 …… Secure Hash Algorithm-1。1994年に連邦政府標準に制定されたnが160のハッシュ関数。
- SHA-256, 384, 512 …… 2002年にAESに対応して制定されたハッシュ関数。nはそれぞれ256, 384, 512。
さまざまなデジタル署名方式
- DSA(Digital Signature Algorithm) …… エルガマル署名を基にした方式で、米国の連邦政府標準。
- エルガマル署名 …… 離散対数問題の難しさを利用した方式であるが、エルガマル暗号とは全く違う方式。