「暗号技術入門 秘密の国のアリス」 (3) 第5章 公開鍵暗号

暗号技術入門 第3版

第5章 公開鍵暗号

公開鍵暗号方式とは、暗号化と復号化でそれぞれ異なる鍵を使う方式。復号化のための鍵は誰にも見せないため、鍵を配送する途中で盗聴されることによる危険をなくすことができる。(鍵配送問題)

鍵配送問題

対象暗号を用いて暗号通信を行いたい場合、鍵を送らないと相手はメッセージを読めないが鍵を送ってしまうと途中でだれかに盗聴され、暗号通信を解読されてしまうおそれがある。これが鍵配送問題。これを解決する方法としては、

• 鍵の事前共有
• 鍵配布センター
• Diffie-Hellman鍵交換 (11章で解説)
• 公開鍵暗号

といった解決策がある。

鍵の事前共有は文字通り事前に安全な手段で鍵を渡しておくこと。これは安全性が高いが、使える場面は限られてしまう。鍵をメディアに入れて直接渡すのはコストが高いし、N人がお互い暗号通信できるようにするには(N*(N-1))/2個の鍵が必要。 鍵配布センターはN人分の秘密鍵が登録されている。AとBが通信を行いたい場合、そのときのみ使うワンタイムのセッション鍵をA,Bそれぞれの鍵で暗号化し、A,Bそれぞれに送る。そうするとA,Bはそれを自分の鍵で復号化し、セッション鍵を得ることができる。(通信はこのセッション鍵で暗号化される)しかし鍵配布センターがダウンすると一切の暗号通信ができなくなってしまう脆弱性がある。

公開鍵暗号

公開鍵暗号は、次のような性質を利用する。

• 送信者が必要なのは「暗号化の鍵」だけ
• 受信者が必要なのは「復号化の鍵」だけ
• 暗号化の鍵は盗まれても平気
• 復号化の鍵だけは盗まれると困る

受信者が手元に復号化の鍵(プライベート鍵)を保管したまま、自分にメッセージを送りたい人相手に暗号化の鍵(公開鍵)を教えるだけでよい。

しかし、公開鍵暗号方式は対称暗号に比べるとはるかに処理速度が遅く、また手に入れた公開鍵が正しいものなのか認証する必要がある。

時計演算

modの計算を復習しよう！

RSA

暗号文 = 平文^E mod N

RSAにおける公開鍵は、このEとNという2つの数の組。

平文 = 暗号文^D mod N

RSAにおけるプライベート鍵はこのDとNの組。(Nはさきほどと同じ)

鍵のつくりかた

1. ある程度大きな素数p, qを用意する。
2. N = p * q
3. L = lcm(p-1, q-1) (Lは一時変数)
4. E: 1< E < L, gcd(E, L) = 1
5. D: 1 < D < L, E*D mod L = 1

RSAへの攻撃

N = p * qという関係がある以上、素因数分解を高速に行う方法が見つかればRSAは解読できる。(いまのところはみつかっていない)

man-in-the-middle攻撃: 間に入り込んで、解読こそできなくても自分のメッセージに書き換えることができる。これを防ぐには、鍵の認証が必要。