9.8 Turing の暗号 (バージョン 2.0)
1940 年、フランスが Hitler の手に落ちたことで、西ヨーロッパでナチスと戦える国はイギリスだけとなった。イギリスの抵抗はアメリカが北大西洋を通る船団を通して絶え間なく供給する資源に依存していた。ドイツはイギリスに対する資源供給を断ち最終的には降伏させるために、アメリカの船団を標的として U ボートと呼ばれる潜水艦を北大西洋に展開した。この戦争の命運は、情報戦で相手を上回れるかどうかにかかっていた: 連合国はドイツが船団を見つける前に U ボートを見つけられるか、それとも逆か？
ドイツは負けた。
ドイツが敗戦した決定的な理由は 1974 年に初めて公になった: ドイツ海軍が使用したエニグマ (Enigma) と呼ばれる暗号がポーランド暗号局1によって解読されており、その知識が 1939 年にナチスがポーランドに侵攻する数週間前にイギリスに伝えられていたのである。このため戦争の大部分を通じて、連合国はドイツの通信を盗聴することで U ボートを回避するルートを船団に指示できた。ただ、イギリス政府はどうやってエニグマを解読したかを 1996 年まで説明しなかった。その詳細が (アメリカによって) ついに公開されると、1939 年に Alan Turing がイギリスの Bletchley Park に存在した秘密暗号解読機関に参加し、高速かつ大規模なエニグマ解読手法の開発を主導していた事実が明らかになった。Turing によるエニグマ解読は、連合国の勝利に対する計り知れない貢献だった。
どんな政府も暗号については必ず口が堅い。しかし、イギリスを救ったエニグマ解読で Turing が果たした役割についてイギリス政府が半世紀にわたって沈黙を保った理由には、おそらく戦争終結後に起きた不幸な出来事が関係している ── この話は別の機会とする。ここでは数論の話に戻り、第 9.5 節で触れた Turing の暗号のもう一つの解釈を考えよう。おそらく「メッセージと鍵の積を送信する」というアイデアに問題はなく、通常の算術を使ったのが間違いだったのかもしれない。Turing が考えていたのは剰余算術を使う次の暗号だった可能性がある:
-
前準備: 送信者と受信者は大きな整数 \(n\) に合意する。\(n\) は公開されても構わない (この \(n\) が以降の計算における法となる)。バージョン 1.0 と同様に、両者は秘密鍵として素数 \(k < n\) にも合意しておく。
-
暗号化: バージョン 1.0 と同様に、メッセージ \(m\) は \([0..n)\) に属する素数である必要がある。送信者はメッセージ \(m\) から \(mk\) を計算することで暗号化したメッセージ \(\widehat{\vphantom{\scriptsize l} m}\) を計算する。ただし、今回は \(n\) を法とした合同計算で計算する:
\[ \widehat{\vphantom{\scriptsize l} m} ::= m \cdot k \quad (\mathbb{Z}_{n}) \] -
復号: ( \(\cdots\) ？)
復号ステップが問題になる。以前と同じように暗号化されたメッセージ \(\widehat{\vphantom{\scriptsize l} m}\) を秘密鍵 \(k\) で割る方法は使えない。\(\widehat{\vphantom{\scriptsize l} m}\) は \(mk\) を \(n\) で割った剰余なので、\(\widehat{\vphantom{\scriptsize l} m}\) を \(k\) で割った結果はそもそも整数でない可能性さえある！
この問題を解決するには、剰余算術で \(k\) による除算が可能な状況について理解する必要がある。