鍵配送問題の解決：アルゴリズムと思想の強度

サイモン・シンの「暗号解読」の第Ⅵ章「アリスとボブは鍵を公開する」まで読んだ。これ以前の章も興味深いのだが、何といっても現代のネットセキュリティに不可欠の「公開鍵」の話題は楽しい。

私自身、公開鍵システムの黎明期にセキュリティシステムに深く関わった。日々「電子証明書」「デジタル署名検証」などの設計や実装をやったものだ。とはいえ、本書にあるような「暗号技術の基礎」は、ある程度は理解はしていたが、じっくりと検証したことはなかった。RSA Security 社 や VeriSign 社 は既に有名で、ある意味そんな会社に対抗するシステム構築をしていたので、「暗号技術の基礎があった上での話」ではあったから。

そんな基礎的なことを本書で読みながら、この分野の楽しさを再発見している感じだ。「暗号解読」ていう言葉の響きからしても「ハッカー的」でワクワクする。私は善良？な一般市民なので、「スパイ的」とは思わないが... (^^)v

ここでは、「デジタル時代の暗号」の極基礎的なポイントを二つ取り上げる。「公開鍵」についてはいくらでも平易な解説がネット上にある（数学的に平易な解説があるかは知らない）。

暗号解読―ロゼッタストーンから量子暗号まで

サイモン シン

新潮社
Amazon.co.jpで詳細を見る

デジタル暗号の基礎

まず、「暗号と復号に作用する鍵」につて、本書の P.103 の例を使って概説する。専門用語の注釈として、「平文」とは暗号前のデータ、暗号を解いて平文に戻すことを「復号」、としています。

以下は "HELLO" という文字を、鍵 "DAVID" で暗号したもの。

　1001000 1000101 1001100 1001100 1001111：平文=HELLO
　1000100 1000001 1010110 1001001 1000100：鍵=DAVID
　0001100 0000100 0011010 0000101 0001011：暗号文

デジタルデータは、このように「二進数」で処理され、文字は ASCII コードを割り当てたもので、単語 H は 1001000 という具合。平文（暗号前のデータ）"HELLO" が 鍵 "DAVID" で暗号のされ方は、対応するビットの XOR で、1 + 1 = 0 , 1 + 0 = 1, 0 + 1 = 1 。

以下は復号の様子で、暗号文と鍵を XOR して平文になる。

　0001100 0000100 0011010 0000101 0001011：暗号文
　1000100 1000001 1010110 1001001 1000100：鍵=DAVID
　1001000 1000101 1001100 1001100 1001111：平文=HELLO

では「鍵を知らない」条件で

　0001100 0000100 0011010 0000101 0001011：暗号文
　1001000 1000101 1001100 1001100 1001111：平文=HELLO

暗号文から平文を生成するのは容易ではない 。

とはいえ、この程度の鍵の長さでは、暗号解読は「容易」だろう。解読のアルゴリズムも計算機の性能も向上しているので、現代ではなおさら容易だ。そんな解読の手法は、本書の他の章が詳しい。


鍵配送問題

多くの人が想像する「悪者ハッカー」がやっているのは、右の漫画の左 "A Crypto Nerd's Imagination" の方かもしれないが、現実の多くは右側の「暴力的」な方だと私も思う（笑）

暗号の歴史は、人類の知的活動と同時に始まったと言える。「秘密に伝えあいたいこと」は、欲望の一つとして当然。「詐欺の計画」「浮気ごと」「誹謗中傷」などなど...。あれ？悪いことばかりしか浮かばないや（笑）この辺の「黒い側面」が「暗号の魅力」であるのも事実。そして「情報戦争」には、暗号が欠かせないのは言わずもがな。

そんな暗号の歴史上、常にあった「暗号上の弱点」が「鍵配送問題」。

いかに強力な暗号装置であろうと「鍵の受け渡し」は常に「弱点」だった。つまり、鍵を定期的に交換しないと、暗号文のパターンから鍵を発見させる確率は時間と比例して高まる「弱点」もあれば、鍵そのものを盗まれてしまう「弱点」も常にあった。

余談：現代においても、「パスワードは定期的に変更しましょう」としつこく言われる理由は容易に想像できますよね。そろそろ容易で画期的なパスワード管理の技術が登場して欲しいところだが...。指紋認証破りが「指切断事件」なんて怖いよ（泣）

この歴史的にも解決不可能と思われていた「鍵配送問題」は、1970年代についに解決した。個人的には、公開鍵と合わせて、これはノーベル賞ものだと思うのだが。


Alice, Bob が会わずして鍵を共有する方法

そんな「鍵配送問題」の解決の様子を、 本書の表26 (P.136) を基づき記す。

目的：Bob と Alice だけが知る「秘密の鍵」を、二人が出会うことなく作成する。
条件：一方向関数 Y^x(mod P)、今回は Y = 7, P = 11 と取り決める。
脅威：Eve が Bob と Alice のやり取りを盗聴中（電話盗聴、手紙の覗き、など）。

Alice
#1: 秘密の数字 A = 3
#2: A を一方向関数に代入した結果 α =  7³(mod 11) = 343(mod 11) ≡ 2
#3: α の値を Bob に通知。
#4: A と、Bob から受け取った β から鍵を生成
　　β^A(mod 11) = 4³(mod 11) = 64(mod 11) ≡ 9

Bob
#1: 秘密の数字 B = 6
#2: A を一方向関数に代入した結果 β =  7⁶(mod 11) = 117649(mod 11) ≡ 4
#3: β の値を Alice に通知。

#4: B と、Alice から受け取った α から鍵を生成
　　α^B(mod 11) = 2⁶(mod 11) = 64(mod 11) ≡ 9

Alice と Bob が得た鍵は同じ 9 となっている。問題は、盗聴中の Eve がこの鍵を生成できるか、ということ。

Eve の苦しみ：一方向関数

二人のやり取り盗聴した Eve が知り得る情報は

　一方向関数 Y^x(mod P) , Y = 7, P = 11, α = 2, β = 4 

Alice と Bob が鍵生成した処理は

　Alice: β^A(mod 11) = 4^A(mod 11) 

　Bob:   α^B(mod 11) = 2^B(mod 11) 

A, B が分かれば Eve は鍵生成できる。Eve の盗聴した情報から

　α =  7^A(mod 11)  ≡ 2

　β =  7^B(mod 11)  ≡ 4

ここまでは分かるのだが、Eve の苦しみの原因は、7^A(mod 11)  が 2 になる A を「容易には見つけられない」こと、4 になる B も同様。それは、一方向関数の特徴でもある。

とはいえ、今回の「7 を A 累乗した値を 11 で割った余りが 2」という A を求めるのは、面倒だが困難ではない。ところが

　128^x (mod 123983) =  64728

つまり「128 を x 累乗した値を 123983 で割った余りが 64728」という x  を求めるのは、断然難しくなる。ここでは x = 8 で生成した。

> 128^8%%123983

[1] 64728

因みに 8 に近い値 7 や 9 は以下のようになり、7 と 9 の結果から 8 を類推することはできない。このランダム性が一方向関数の特徴。

> 128^7%%123983

[1] 98336

> 128^9%%123983

[1] 102400

つまり、Alice と Bob が取り決める Y と P の値を大きな数にするほど、A, B の発見は難しくなり、よって二人が生成した鍵の発見も同時に困難となる。

本書に従って「鍵配送問題」の解決方法を示したが、本来なら数学的な証明をしたいところだが割愛。私が、容易に解説できるほど理解していないのと、実際の鍵の生成はもっと複雑になっていると思うから。


公開する社会へ：思想の強度

戦時中で有名なドイツの暗号機「エニグマ」は、機械の複雑さが暗号強度の要の一つではあった。現代では「エニグマ」に相当する秘密の機械を作る手間は不要になっている。つまり、「暗号アルゴリズム」は公開されているのだ。逆に 公開してこそ、弱点を広く改善する利点の方が大きいのだ。ネット時代の現代では尚更だ。

そんなアルゴリズムの基礎にあるのが数学です。公開鍵は「素数」の原理に基づいているように、やはり数学の力なのだ。現代は「数学戦争」なのですよ。

秘密は秘密にした瞬間に秘密ではなくなる

とは、ずっと昔に聞いたセリフだ。哲学的だが、まさにその通りだと思う、「秘密は弱さ」なのだ。コソコソと秘密にする輩って、結局は「もろい連中」。論破されない思想やメッセージは、秘密にする必要はないのだから。

「アルゴリズムの強度」と「思想の強度」て一致するよな..。