No181 鍵交換の鍵は剰余演算にあり

暗号化をするには通常は鍵が必要になります。
鍵があれば暗号文を読めるわけですから、その鍵を第三者に盗聴
されずに安全に交換する方法が必要です。そのために鍵交換という
方式が発明されました。

前回はその鍵交換をどのように行うかを解説しました。
今回はその続きとして、鍵の入手をより困難にするための方式に
ついて解説します。

今回も数学が多少登場しますが、前回同様にさほど難しいものは
出てきません。
というか、筆者は決して数学に明るい人ではないので、難しい
ことは書けませんので、ご安心ください。

1. 前回のおさらい

鍵を安全に渡すためには、その鍵を簡単に得られないような工夫
が必要です。

現代暗号は数学で組み立てられていて、鍵交換では離散対数問題
や楕円関数問題といった方式がよく用いられます。

前回は離散対数問題と呼ばれる累乗（２乗とか３乗とかのやつ）の
逆算が難しい性質を利用して盗聴されても大丈夫な鍵の交換方法を
解説しました。

前回の後半にも書きましたが、離散対数問題の完成には累乗以外に
もう一つの数学の考え方が必要となります。

それが剰余（じょうよ）というものです。

2. 剰余というもの

剰余なんていうのも難しい言い方ですが、要は割算のあまりです。

そう、小学校の割り算で習う「あまり」のことです。
こんなやつです。
16÷3 ＝ 5 ...1

中学校以降の数学ではこの余りというのは出てきませんが、その
余りに着目した計算を剰余演算といいます。

ここでは、商（上の例なら5）は使わず、余り（上の例なら1）
だけを使います。

その計算をするための演算子（＋とか×のような記号）はありま
せんので、mod（モッドとかモジュロと読みます）という単語で
代用することにします。

こんな書き方になります。
　10 mod 3 = 1 (10÷3 ＝3...1 だから）
　13 mod 11 = 2 (13÷11＝1...2 だから）
　10 mod 5 = 0 (10÷5 ＝2...0 だから）

今更、余りなんて使って何ができるというの？とお考えでしょうか？
実は、この剰余というのは見た目と裏腹にいろいろと妙な性質が
あり、意外にも暗号化理論ではよく使われる計算方法なのです。

3. 剰余演算の性質

剰余演算のそういった性質の一つに同一性というものがあります。

これは、ある計算をする時、最後に余りを求めた場合でも都度都度
余りを求めた場合でも、同じ結果になるというものです。

と、これだけでは意味がわからないので、具体的な値でいきます。

例１：
　5×7 を3で割った余りを求めてみます。
　
　これを素直に式にすると (5×7)mod 3 です。
　計算をすれば、
　　35 mod 3 = 2 (35÷3＝11...2 だから）
　となりますよね。

　次に、それぞれの値を３で割った余りを使って同じ計算をします。
　つまり、
　((5 mod 3)×(7 mod 3))mod 3
　ということです。
　
　これを計算してみます。
　((5 mod 3)×(7 mod 3))mod 3
　＝(2×1)mod 3
　＝2

　確かに同じ結果になりました。
　え？偶然じゃないか？ですって？

ではもう少し複雑なパターンでやってみましょう。

例２：
　今回は項目数を増やして、2×3×5×7 を 11 で割った余りを
　求めてみます。

　最初は全てを掛けた結果を11で割った余りを求めるパターン
　つまり、(2×3×5×7) mod 11 となります。

　これを計算すると
　(2×3×5×7) mod 11
　＝210 mod 11
　＝1
　ですね。

　次に最初の２つを掛けた後に11の余りを求め、後半の２つを
　掛けた後にも11の余りを求め、最後にその結果を掛けた後にも
　11の余りを求めてみます。
　ちょっと長いですが、こんな式になります。
　(((2×3)mod 11)×((5×7)mod 11))mod 11 です。
　これを計算してみます。

　(((2×3)mod 11)×((5×7)mod 11))mod 11
　＝((6 mod 11)×(35 mod 11))mod 11
　＝(6×2)mod 11
　＝12 mod 11
　＝1
　どちらも１になることがわかります。

　さらに掛け算の都度、11の余りを求めても同じ結果になります。
　(((((2×3)mod 11)×5)mod 11)×7)mod 11
　＝((((6 mod 11)×5)mod 11)×7)mod 11
　＝(((6×5)mod 11)×7)mod 11
　＝((30 mod 11)×7)mod 11
　＝(8 ×7)mod 11
　＝56 mod 11
　＝1

つまり計算過程のどこで余りを求めても最終的な答えは一致すると
いうわけです。

4. アリスとボブ再び

さて、ここで前回のアリスとボブの鍵交換の手順に上記の剰余演算
の手順を加えた例を述べます。
（詳しくは「No180 暗号化で使われる鍵交換の秘密」をどうぞ）

まず、それぞれの値を次の通りとします。
（最後の１項目が今回追加されています）
　共有する値ｇ＝3
　アリスの秘密の値ａ＝4
　ボブの秘密の値ｂ＝2
　剰余のための割る数＝19

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

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

両方の計算の過程は全く違っているにも関わらず、アリスとボブは
同じ鍵を共有できることがわかります。

5. 累乗だけだとカンタンに鍵がバレる

剰余の妙な性質はわかったし、それを使っても鍵が一致することも
わかった。でもそこまでして剰余なんてのを使う必要があるの？
面倒なだけじゃないの？

その疑問はもっともです。

実は累乗だけだとアリスとボブ以外の第三者にも割と簡単に鍵が
知られてしまいます。
というのは、累乗というのは前回も書いた通り、掛ける回数に
比例してどんどんケタ数が増え続けます。

例えば、2ケタの値を2乗すれば、必ず3桁か4桁になります。3乗
すれば、4桁か5桁、4乗すれば、5桁か6桁です。それ以外の桁数
には絶対になりません。
ということは、アリスが送った値(Ａ)のケタ数を数えるだけで、
元の数を何乗したかほぼほぼわかってしまうのです。

それがわかってしまうと、第三者も鍵が手に入ってしまいます。
それでは全くもって秘密が成立しません。

ですが、アリスが「余り」を送るようにすれば、この欠点は隠す
ことができます。何回計算を行ったかがわからなくできるのです。

前回説明した累乗を用いた方法に、今回説明した剰余演算を施す
ことで、非常に逆算に強いバレにくい鍵交換方式が完成するわけ
です。

6. 暗号の本質は時間稼ぎ

以上が、離散対数問題を用いた鍵交換の方法となります。

では、離散対数問題を用いた鍵交換なら絶対にバレないので
しょうか？

そんなことはありません。数式なのですから、解くことはでき
ます。ただ時間がかかるだけです。

これが5分や10分で解けてしまうなら、暗号としての価値は低い
と言えます。ですが、解くのに何憶年もかかるようならもはや
解けないといっても過言ではありません。

数学を駆使した鍵交換方式が時間稼ぎだなんて何とも場違いな
印象ですが、それが現代暗号というものの本質のようです。

次回もお楽しみに。

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