Diffie-Hellman
Diffie-Hellman
ここでやっと本題です。
いま、AliceとBobの2人がDiffie-Hellmanを使って鍵交換をしようとします。次のステップになります。
(1) 大きな素数 pp, 小さな適当な整数 xx を用意しておく。これは公開して構わない。
(2a) Aliceが秘密の aa を, 2 以上 pp 未満の整数からランダムに選ぶ。
(3a) Aliceは E=xa mod pE=xa mod p を計算する（これがカンタンなことはさっき確認しました)。その結果の EE をBobに送る。
(2b) Bobが秘密の bb を, 22以上 pp 未満の整数からランダムに選ぶ。
(3b) Bobは F=xb mod pF=xb mod p を計算する（これがカンタンなことはさっき確認しました)。その結果の FF をAliceに送る。
(4a) Aliceは、Bobから受け取った FF と、自分の手元にある aa を使って、 Ga=Fa mod pGa=Fa mod p を計算する。
(4b) Bobは、Aliceから受け取った EE と、自分の手元にある bb を使って、 Gb=Eb mod pGb=Eb mod p を計算する。
さてこの結果、E と Fを求めたときの手順を見れば、Ga=Gb=(xab) mod pGa=Gb=(xab) mod p であることがわかります。これをAliceとBobの共通鍵にすればいいのです。
図にするとこうなります。
仮にこの通信を傍受している悪者がいたとしても、見えるのは x,p,E,Fx,p,E,F のみです。そこから aa や bb を逆算するのが困難であるのはさきほど確認したとおりです。
SSHの場合
申し遅れましたが、私はPoderosaというSSHクライアントを開発しており、SSHプロトコルには実はけっこう詳しいのです。昔に未踏ソフトウェア事業に採択もされましたが、その後放置期間を経て2016年に復活しました。
SSHでは、この計算において x = 2 で固定された値を使っています。pについては、16進数で
FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFFFFFFFFFF
(diffie-hellman-group1-sha1)
という値が長らく使われてきましたが、最近はこの程度では計算機パワーで力ずくで解けてしまう危険が高まったのでさらに大きな
FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF
(diffie-hellman-group14-sha1)
というものも使われています。世の中のほとんどすべてのSSH接続では、ログイン時にこのどちらかの p を使っているのです。この巨大素数は世界共通の資産といえます。
まとめ
Diffie-Hellman鍵交換は、傍受されている通信路を使っても安全に通信相手に鍵を届けることができる
その根拠は、 xy=z mod pxy=z mod p (p は大きな素数) において、(x, y, p)から zを求めるのは簡単だが(x, z, p)からyを求めるのは困難という計算理論上の定理である
穴
Diffie-Hellman鍵交換が担当するのはあくまでも通信の傍受に対する耐性です。セキュリティにおいては別の問題もいろいろあるので、決して万能ではありません。例えば、Aliceが通信 している相手はBobではなく「Bobのふりをした悪者」だった場合は極めて危険です。
また、計算理論の定理も将来は崩される危険があります。量子コンピュータのような、これまでとは次元の異なる計算手段が実用化された場合、一発で前提がひっくり返る可能性があります。その確率はとても低いですが、０ではありません！