9.5 Alan Turing
Alan Turing は情報科学の歴史の中で最も重要な人物である。数十年にわたって、彼の波乱に満ちた人生は政府の秘密主義、社会的タブー、そしてときには彼自身の嘘によって隠されてきた。
24 才のとき、彼は「計算可能数、そして決定問題への応用について (On Computable Numbers, with an Application to the Entscheidungsproblem)」と題した論文を執筆した。この論文の核心部分では数学の言葉でコンピューターをモデル化する鮮やかな方法が示されており、これは計算に関する問題を数学のツールで考察することを可能にしたという点で画期的だった。例えば、Turing は自身のモデルを使ってコンピューターが ── プログラマーがどれだけ賢くても ── 解けない問題の存在 (第 6.3 節) をすぐに証明している。この論文の重要性は 1936 年に執筆された事実によってさらに増す: 電気式コンピューターが実際に作成されるより 10 年も前のことだった。
論文のタイトルにある「決定問題 (Entscheidungsproblem)」は David Hilbert が 1900 年に二十世紀の数学者に向けて提示した 28 個の数学問題の一つを指す。Turing は同じ論文でそれを解決した。「Church-Turing のテーゼ (Church-Turing thesis)」について聞いたことは？ それも同じ論文で示された。このように、Turing は素晴らしいアイデアをいくつも生み出した非常に聡明な人物だった。ただ、本講義では Turing のそれほど素晴らしくないアイデアに焦点を当てる。暗号と数論に関する、あまり賢いとは言えないアイデアである。
1937 年の秋、Adolf Hitler の下でナチスが再軍備を進め、世界を二分する大戦争が間近に迫っているように思えたころ、Alan Turing は ── 我々と同じように ── 数論の有用性について考えていた。彼は目前に迫った軍事衝突では軍事機密の秘匿が極めて重要になると考え、数論を使った通信の暗号化を提案した。このアイデア自体は現在でも通用する: 数論は様々な公開鍵暗号、デジタル署名方式、暗号学的ハッシュ関数、電子決済システムを支えている。また、暗号研究に対する最大の資金提供機関の一つは軍事研究助成機関である。Hardy には申し訳ないが！
暗号を考案してからしばらくして、Turing は公の場から姿を消した。それから半世紀にわたって、この後に彼がどこで何をしていたかを世界が知ることはなかった。Turing の人生を追うのは次の機会として、これから Turing が残した暗号を見ていく。彼の暗号のアイデアは公式に発表されていないために詳細がはっきりと分からない部分があるので、いくつかの可能性を考える。
9.5.1 Turing の暗号 (バージョン 1.0)
まず、数学的演算が可能なようにテキストのメッセージを一つの整数に変換することが問題となる。このステップの目的はメッセージを解読困難にすることではないので、その詳細はあまり重要でない。アプローチの一つを示す: メッセージを構成する文字を二桁の数字で (\(A = 01\), \(B = 02\), \(C = 03\) などと) 置き換え、全ての数字をつなげて大きな一つの数字を作成する。例えば、メッセージ「victory」は次のように変換される:
Turing の暗号はメッセージが素数であることを要求するので、いくつかの桁を末尾に追加して素数を作る。素数定理からは、このとき追加が必要な桁数がそれほど多くないことが分かる。上記の例では、\(13\) を末尾に追加すると素数 \(2209032015182513\) が得られる。
ここからの処理を次に示す。\(m\) は暗号化されていない (秘匿する必要がある) メッセージを表し、\(\widehat{\vphantom{\scriptsize l} m}\) は暗号化された (ナチスが盗み見る可能性のある) メッセージを表す:
-
前準備: 送信者と受信者は通信で利用する大きな素数 \(k\) について合意しておく。この \(k\) を秘密鍵 (secret key) と呼ぶ。
-
暗号化: 送信者は素数のメッセージ \(m\) を次の計算で暗号化する:
\[ \widehat{\vphantom{\scriptsize l} m} = m \cdot k \] -
復号: 受信者は \(\widehat{\vphantom{\scriptsize l} m}\) から次の計算でメッセージを復号する:
\[ \frac{\widehat{\vphantom{\scriptsize l} m}}{k} = m \]
例えば秘密鍵の素数 \(k\) が \(22801763489\) で、相手に伝えたいメッセージ \(m\) が「victory」を表す \(2209032015182513\) のとき、暗号化されたメッセージ \(\widehat{\vphantom{\scriptsize l} m}\) は次の値となる:
この Turing の暗号に関する基本的な疑問を考えよう:
-
送信者と受信者は \(m\) と \(k\) が素数である仮定をどのように確かめるのか？
大きい整数が素数かどうかを判定する一般的な問題は数世紀にわたって研究されており、Turing の時代に知られていた手法でも現実的な時間で判定が可能だった。次のテキストボックスで説明されるように、過去数十年の間に素数判定法はさらに大きく進化している。
-
Turing の暗号は安全なのか？
ナチスが暗号化されたメッセージ \(\widehat{\vphantom{\scriptsize l} m} = m \cdot k\) を入手したとしても、元のメッセージ \(m\) を復元するには \(\widehat{\vphantom{\scriptsize l} m}\) を素因数分解しなければならない。多大な労力が注ぎ込まれてきたにもかかわらず、効率的な素因数分解の手法は現在まで見つかっていない。そのため素因数分解はおそらく本質的に難しい問題である。いつの日かブレークスルーが起こる可能性は否定できないものの、効率的な素因数分解は不可能であるという予想は広く受け入れられている。ある意味で、Turing の暗号は「計算能力に限界がある」という彼の発見した事実を利用していると言える。よって、\(m\) と \(k\) が十分大きい限りナチスが暗号を破ることはきっとない！
これを見ると前途有望に思える。しかし、Turing の暗号には大きな欠点がある。
容易に分かるように、整数 \(n\) が素数なのは \(2\) から \(\lfloor \sqrt{n} \rfloor\) までの全ての整数で割り切れないとき、かつそのときに限る (問題 1.13)。もちろん、このナイーブな手法による素数判定にかかるステップ数は \(\sqrt{n}\) であり、これは \(n\) が二進表記あるいは十進表記で表されるとき入力の長さ \(n\) に関して指数的に増加する。1970 年代以前には、こういった指数的振る舞いを持たない素数判定法は知られていなかった。
1974 年、Volker Strassen が単純かつ高速な確率的素数判定法を発明した。この判定法は素数に対して必ず正しい解答を答えるものの、素数でない整数に対しては間違った解答を答える可能性がある。どんな整数に対しても間違った解答が得られる確率は非常に小さいので、その解答を信じることが最良の選択肢となった。
ただ、間違った解答が得られる可能性が理論的に存在することは知的に収まりが悪い ── コンピューターが検出不能なハードウェアエラーを起こす確率よりずっと低い誤答率だったとしても。ついに 2002 年、素数判定問題の重要性と歴史の長さを記した Gauss の言葉の引用から始まる画期的な論文において、Manindra Agrawal, Neeraj Kayal, Nitin Saxena は多項式時間で実行できる素数判定法の 13 行の説明を示した。
このため、素数判定問題は SAT などの指数的な時間が必要になる問題よりずっと簡単である。一方で、Agrawal らが示したアルゴリズムの実行時間を抑える多項式の次数は \(12\) だった。後の研究によって次数は \(5\) まで小さくなったものの、これでも実用するには大きすぎる。そのため現実の問題に対しては現在でも確率的な判定法が利用されている。次数をさらに小さくできる可能性は残されているものの、既知の確率的手法と同等の速度を達成するのは非常に難易度の高い問題である。
9.5.2 Turing の暗号 (バージョン 1.0) の解読
送信者が同じ秘密鍵を使う Turing 暗号で二つ目のメッセージを送信したとき何が起こるかを考えよう。このときナチスは暗号化されたメッセージを二つ手にする:
このとき、二つの暗号化されたメッセージ \(\widehat{\vphantom{\scriptsize l} m}_{1}\) と \(\widehat{\vphantom{\scriptsize l} m}_{2}\) の最大公約数が秘密鍵 \(k\) となる。そして、これまでに見たように二つの整数の最大公約数は非常に効率良く計算できる。よって二つ目のメッセージが送信されると、ナチスは秘密鍵を復元して全てのメッセージを解読可能になってしまう！
Turing ほど聡明な数学者がこれほど明らかな問題を見落としたとは考えにくい。そのため、彼が思い描いていたのは合同算術 (modular arithmetic) を利用する少し異なる暗号だったことが示唆される。