広場にいる離れた二人が大声を出しながら秘密のメッセージを交換するにはどうしたらいい？(1)

ただし、

• 二人は十分大きな桁の加減乗除、剰余計算、n^mの計算をできる電卓を持つ
• 広場には他にも沢山の人がいる
  • 迷惑は考えないものとする
• 厳密なことをいうと相手が本当に本人かどうか確かめる必要があったりもしますが、今回は無視します

ネタ記事です。。。

前置き

SSL/TLSの勉強をしていて個人的に一番面白いな～～と思ったところなので、ここで書かせていただきます。
この問題、一見すると不可能ですが、高校数学の力を借りれば実は可能です！！
なお、元ネタはDiffie-Hellman鍵交換と言われるもので、この記事はそのアナロジーにすぎません。先人たちがわかりやすい記事を沢山残してくださっているので、アルゴリズムを手っ取り早く知りたい方はそちらを見ると良い気がします。
https://qiita.com/okajima/items/036d7e751234f88fbe9a

二人のやりとり

やり取りしようとしている二人の名前をA、Bとしましょう。
数学が得意なAはBに次の手順にしたがうようにいいました(別にここも大声でやり取りして構いません)。

A「まず9桁くらいの秘密の数字を思い浮かべて、紙に書いておいて。僕も自分の秘密の数字を紙にかいておくね」
Aは720,100,545、Bは479,829,432を紙に書きました。
A「2^(君の秘密の数字)を1,000,000,007で割ったあまりを僕に教えて」
Bは電卓に2^479,829,432 mod¹ 1,000,000,007を打ち込み、312,251,220をすぐに得ました。
B「312,251,220」
A「ありがとう。2^(僕の秘密の数字)を1,000,000,007で割ったあまりは58,064,454になった。ちょっとまってね…」
すると、Aはなにか操作をしたあとに、いいました。
A「それじゃ、僕がさっき言った数字の58,064,454^(君の秘密の数字)を1,000,000,007で割ったあまりを教えて。多分451,088,379になるでしょ？」
Bは58,064,454^479,829,432 mod 1,000,000,007を計算してびっくりしました。たしかに451,088,379になったのです。
B「なった」
A「オッケー。そしたら次も同じように、2^(自分の秘密の数字)を1,000,000,007で割ったあまりをお互いに伝えて、その数字^(自分の秘密の数字)を1,000,000,007で割ったあまりをお互いの共通の"鍵"にしよう！」

解説

以上の話を図解するとこんな感じになります：

そして、公の場の視点に立つと、このやり取りはこういうことになります：

そして、秘密の数字を知らない人たちがこの赤い???を効率的に求める方法は2023年現在のところ、ありません。非効率的な求め方というのは要するに、総当たりです²。公の場にいるCが???をもとめるには、9桁の数をすべて試してどちらかの秘密の数字???を当てるしかないのです：

• 2^100,000,000 mod 1,000,000,007 = 494,499,948 (はずれ)
• 2^100,000,001 mod 1,000,000,007 = 988,999,896 (はずれ)
• 2^100,000,002 mod 1,000,000,007 = 977,999,785 (はずれ)
• ...
• 2^479,829,432 mod 1,000,000,007 = 312,251,220 (当たり！)

ちなみにこの程度の桁数ならば普通のコンピュータを使っても数秒で見つかってしまうと思いますが、もっと桁数を大きくしていくとスーパーコンピュータを何年使ってもわからなくなります。

もしかしたら「いや、58,064,454^479,829,432 mod 1,000,000,007のような計算も途方もなく時間かかるんじゃないの？」と思う方もいらっしゃるかもしれません。しかし、それは効率の良いやり方が大昔から見つかっています³。繰り返し二乗法、というやつです。ここでは雰囲気だけ伝えますが、詳しく知りたい人は調べればわかりやすい記事がいくらでも出てくると思います。
例えば、17^8を計算するにはどうするのが速いでしょうか？馬鹿正直に17x17x17x17x17x17x17x17を左から計算すると時間がかかりそうなので、次のように計算しましょう：

\begin{align}
& 17\times17\times17\times17\times17\times17\times17\times17 \\
& = (17\times17\times17\times17) \times (左と同じもの) \\
& = ((17\times17) \times (左と同じもの)) \times (左と同じもの) \\
& = (289\times289) \times (左と同じもの) \\
& = 83521 \times 83521 \\
& = 6975757441
\end{align}

これで実質的に17x17, 289x289, 83521x83521の三回しか掛け算せずにすみましたね！大まかなイメージはこんな感じです。とりあえず、効率のいいやり方があるんだなあと思ってくだされば大丈夫だと思います。

二人のやり取りの続き

A「じゃあ同じように、9桁くらいの秘密の数字を思い浮かべて、紙に書いておいて」
Aはxxxxxxxxx、Bはyyyyyyyyyを紙に書きました。
A「2^(君の秘密の数字)を 1,000,000,007で割ったあまりを僕に教えて。僕は707,086,186」
B「570,925,259」
A「ありがとう。計算したけど、共通の"鍵"の下1桁は9かな？⁴」
B「そうだね」
A「よし、それじゃあこれを使ってお互いのメッセージを暗号化していこうか」

メッセージの暗号化編へ続く…(かも)

1. この記事ではa mod bはaをbで割ったあまり、を意味しています。 ↩

2. もしかしたらもう少しいいやり方があるかもしれないです、私が調べた限りだと見つかりませんでした。ただ、どんなにいい方法でもO(log N)のような効率のいいやり方はやり方はないはず… ↩

3. というか、これがなければWolfram Alphaは一瞬で計算が出来ないです。 ↩

4. 脆弱性のもとになるのでこういうことをするのはやめましょう。 ↩