No180 暗号化で使われる鍵交換の秘密

前回は暗号化で使う鍵を第三者に知られずに交換することがとても
難しいことをお話しました。

今回はそれを解決した鍵交換という方式を詳しく解説をしたいと
思います。

今回、かなり数学が出てきますが、そんなに難しくはないはずです。
というか、筆者は決して数学に明るい人ではなので、難しいことは
書けませんので、ご安心ください。

1. 逆算の難しさ

鍵交換のアイデアは逆算の難しさを利用しています。
逆算が難しいってどういうことでしょうか？

例えば次の計算はカンタンですよね。

311×199＝

これは筆算でも計算できます。ちなみに答えは 61899 ですね。

ですがこれが逆になるとどうでしょう？

61899＝Ａ×Ｂ

このＡとＢを求めてください。

これ、めっちゃ難しいですよね。最初の問題は小学生でも簡単
ですが、その逆算をしようとなるとひどく難しいです。
やるとすれば、全組み合わせを調べるしかありません。Ａが２
なら？３なら？４なら？,.... といった具合です。

このように逆算にものすごく手間がかかる計算式のことを
「一方向性関数」と呼ぶのです。

この一方向性関数をうまく利用するのが鍵交換の考え方の根底
にあります。

このような一方向性関数はいくつも発見されていて、現代暗号
ではよく使われています。
例えば次のようなものがあります。
・素因数分解問題(上の例）
・離散対数問題（以下で解説する方式）
・楕円関数問題
などなど。

2. 離散対数問題

なんだか、えらく難しそうな名前が出てきましたが、大したことは
ありません。

要は累乗（２乗とか３乗とかのやつ）の逆算が難しいという性質を
使う方式ということです。

そのため、今回は累乗という表記方法を使います。

数学の書籍なら、ａ×ａのことを文字の右上に小さく２を書いて
ａの２乗を示します。
ですがメールではそのような表記ができませんので、ここでは次の
ように「＾」記号を用いてそれをあらわすことにします。

累乗：　Ａ×Ａ×Ａ＝Ａ^3

少々わかりづらいですが、ご容赦ください。

3. 累乗を利用した鍵交換の方法

さて、ここではアリスとボブの二人が登場します。

余談ですが、暗号通信の話をする時には、Ａさん、Ｂさんと
言わずに、アリス(Alice)、ボブ(Bob)、チャーリー(Charlie）
などを使うのが定番です。頭文字がA,B,Cなんですね。

さてアリスとボブの鍵交換の手順は次の通りです。

計算方法については後で詳しく解説しますので、ここでは
全体の手順を把握いただければＯＫです。

１）アリスとボブの間では、計算の基準値を決めます。
　　どんな値でもいいですが、通常は100ケタとか500ケタとか
　　のバカでかい値にします。
　　これをｇとしましょう。

２) アリスはランダムな値ａを自分の鍵に決めます。
　　ａの値は正の整数なら何でもＯＫですが、一般的には大きな
　　値（数十ケタ程度）にします。
　　そして、以下の計算をします。
　　Ａ＝ｇ^ａ
　　この値(Ａ)をボブに送ります。

３）ボブも同様にランダムな値ｂを自分の鍵に決め、同じ方法で値
　　（Ｂ）をアリスに送ります。
　　Ｂ＝ｇ^ｂ

４）アリスはＢを入手すれば以下を計算します。
　　Ｋ＝Ｂ^a
　　また、ボブはＡを入手して以下を計算します。
　　Ｋ＝Ａ^b

これで目出たくアリスとボブは同じＫという値が共有できました。

なんだか騙されたようなホントのような、モヤモヤ感が漂いま
せんか？
Ｂ^a と Ａ^b ってホントに同じ値なの？とか、ＢとＡを掛ければ、
結局Ｋはバレちゃうんじゃないの？とか。

まず最初の疑問、Ｋ＝Ａ^ｂ＝Ｂ^ａ、つまりアリスとボブが同じ
鍵を入手できることを確認してみましょう。

4. 累乗の計算の正しさ（数式による説明）

まずは、数式でも大丈夫な人向けの説明です。
数式はカンベンという方は、スキップしてください。

　Ａ^ｂ＝（ｇ^ａ）^ｂ
　Ｂ^ａ＝（ｇ^ｂ）^ａ
交換則により、
　（ｇ^ａ）^ｂ＝（ｇ^ｂ）^ａ
よって、アリスとボブが入手した値は等しいと言えます。

5. 累乗の計算の正しさ（数式を使わない説明）

数式の説明では何だかよくわからないという方向けに、具体的な
値を使って同じことを計算してみましょう。

まず、それぞれの値を次の通りとします。
　共有する値ｇ＝3
　アリスの秘密の値ａ＝4
　ボブの秘密の値ｂ＝2

さて、この時、
　アリスがボブに送る値(Ａ)：　3^4＝3×3×3×3＝81
　ボブがアリスに送る値(Ｂ)：　3^2＝3×3＝9
となります。

そして、それぞれが受け取った値に自分の秘密の値を掛けます。
　アリスの計算(Ｂ^ａ)：　9^4＝9×9×9×9＝6561
　ボブの計算(Ａ^ｂ)：　 81^2＝81×81＝6561

確かに両方の値は一致するのですが、偶然のようにも見えます
ので、もう少し細かく書いてみましょう。
　アリスの計算：　9^4＝(3×3)×(3×3)×(3×3)(3×3)＝3^8
　ボブの計算：　 81^2＝(3×3×3×3)×(3×3×3×3)＝3^8

どちらも、アリスの秘密の値とボブの秘密の値を掛け合わせた回数
（4×2＝8回）だけｇを累乗していることがわかります。

6. 第三者が鍵を得られないか？

さて、両者が等しい鍵（Ｋ）を得たのはいいとしても、通信内容を
盗聴していた第三者であるチャーリーにも鍵が知られてしまうこと
はないのでしょうか？

チャーリーが知ることができるのは以下の値です。
　共有する値ｇ＝3
　アリスが送った値(Ａ)＝81
　ボブが送った値(Ｂ)＝9

では、ＡとＢを使ってＫを計算できないでしょうか？
　Ａ×Ｂ＝81×9＝729
　Ａ^Ｂ＝81^9＝150094635296999121
とどちらもＫと同じ値を得ることができません。

ですが、勘の良い方ならお気づきだと思いますが、Ｂとｇがわか
ればｂを逆算できるはずです。（Ａとｇでも同様）
つまり、Ｂ＝ｇ^ｂでしたから、Ｂとｇがわかっていれば、ｂは
逆算できるはずです。数学で言う対数(log)というやつです。

これは正しいのですが、対数の計算ってかなり面倒なんですね。
これも最初に書いた掛け算の逆算が難しいのと同様に逆算が
難しい（面倒臭い）のです。
今どきはそうでもないでしょうが、昔は対数の計算をラクにする
ため、対数表というのをよく利用したくらいですから。

7. それでも計算は可能だよね？

これでめでたし、めでたし、と言いたいところですが、この
方法には２つほど問題があるのです。

一つは最近のコンピュータを前提にすると、単純な対数の計算
はそれほど大変ではない点で、実は離散対数問題として成立を
させるにはもう一捻りが必要なのです。

もう一つの問題は、得られる鍵が大きな値になりすぎるという
点です。

上記のようにｇが３、ａが４、ｂが２というほぼ最小値の組み
合わせでも鍵の値は４ケタでした。
これが実際的な値、例えばｇ、ａ、ｂをそれぞれ100ケタだと
すると、鍵の大きさは最低でも100万ケタになります。
これは１つの数字がこのメルマガ200回分くらいの文字数になる
いうことです。

これほど大きな値は暗号鍵としても非現実的です。

この解決には剰余（割り算のあまりのこと）を使います。
ですが、既におなかいっぱいの方もおられると思いますので、
今回はここまでとします。

次回は剰余を用いた解決方法について解説します。
次回もお楽しみに。

このNoteは私が主宰するメルマガ「がんばりすぎないセキュリティ」からの転載です。
誰もが気になるセキュリティに関連するトピックを毎週月曜日の早朝に配信しています。
無料ですので、是非ご登録ください。
https://www.mag2.com/m/0001678731.html