200年を経て解読――パターソンからジェファソンへの暗号

1803年,第3代アメリカ大統領のトマス・ジェファソンはフランス駐在公使のロバート・R・リヴィングストンに新しい暗号を送付した.ジェファソンはそれまでにも多くの通信相手とさまざまな暗号を使ってやり取りしており,ジェファソン自身が暗号を作成したことも一度ならずあったが(拙稿Thomas Jefferson's Codes and Ciphers I (1783-1789)参照),そうした従来の暗号は基本的には単語や音節を数字で置き換えるというコード暗号だった.今回の暗号はそうしたコード暗号とは根本的に異なっており,ジェファソンは「使いやすい」「解読不能」と高く評価している.それは,アメリカ哲学協会でジェファソンの同僚だった数学者ロバート・パターソンが考案したものだった.

パターソンはこの暗号を,全人類の叡智を集めても時間の終焉に至るまでも解読できないと述べているが,それから200年あまりたった2009年,ローレン・M・スミスラインがコンピューターを使って解読に成功した.

パターソン暗号

暗号文作成手順

パターソンは1802年12月の手紙で大統領ジェファソンに新しく考案した暗号を伝えた.これは文字を別の文字に変換する換字(かえじ)ではなく,平文(ひらぶん)の文字を並べ替えて暗号文を作成するという転置式暗号だった.

平文を暗号にするには,まず文章を普通の英語のように横書きにするのではなく,1文字ずつ縦に書いていく(パターソンはこれを「中国風に」と言っている).下図のパターソン自身の例では,左上から縦に"Buonaparte has at last given peace to Europe! ..."(ボナパルトがついにヨーロッパに平和をもたらした!)という平文が書かれていることがわかる.

この縦に書いたものを横に見た行が暗号文になるというのがパターソン暗号の基本だが,パターソンはさらに「行の入れ替え」と「冗字の挿入」によって解読を難しくする工夫をしている.

まず行の入れ替えために各行に1, 2, 3, …と番号を振っていく.パターソンが示した例では番号は8までで,8行が1つの「セクション」をなしている.番号を振ったら,メッセージの受信者との間で合意されている行転置鍵5-7-3-4-8-1-6-2に従った順序で行を転記していく.さらにその際,各行の先頭にいくつかの無意味な文字(冗字)を挿入する.転記される各行の行頭の冗字の数は別の鍵8-1-3-9-3-4-2-0によって指定される.行末にも適宜冗字を入れて各行の長さを揃えると,次のような暗号文ができあがる(下図では冗字の部分を暗くしてある).

この例では3つのセクションがあるが,各セクションごとに行転置鍵5-7-3-4-8-1-6-2の順に行が転記されていることがわかる.また,転記された各行の先頭に冗字数鍵8-1-3-9-3-4-2-0で指定される数の無意味な文字が追加されている.さらに,行末に挿入される冗字の数は各行の長さがだいたい揃うように選ばれている.

解読手順

解読側は行転置鍵と冗字数鍵を使ってこれを解読することになる.

まず,冗字数鍵8-1-3-9-3-4-2-0に従って行頭の冗字をその数だけ削除する.次に各行に行転置鍵5-7-3-4-8-1-6-2を振っていき,数字の順に行を並べ替えると(パターソンは行を切り取って別の用紙に貼り付けるのが簡単と言っている),最初の図に示したように縦に平文が現われる.

パターソンの暗号文

パターソンはジェファソンへの手紙にこの暗号を使った暗号文を添付し,解読不能とする自信に満ちた見解を披瀝している.

そのような書き方の見本で締めくくることにします.それは,全人類の叡智を集めても時間の終焉に至るまで解読できまいと言っても過言ではないでしょう.ですが,高々数字18個からなる鍵の助けがあれば,至極簡単に15分もかからずに読むことができます.

パターソンの暗号文を下に示す.なお,パターソンの誤記は一部訂正してあるが,「a」の抜け,「w」の抜け,別の箇所に余計な「w」が挿入されている誤りは原文通りとしてある.(パターソンの手稿は本稿末尾に鍵とともに掲げる.)

200年後の解読

パターソンが鍵なくしては解読不能と考えた暗号は,200年後に数学者ローレン・M・スミスラインによってコンピューターを使って解読された.(詳細についてはLawren M. Smithlilne, 'A Cipher to Thomas Jfferson: A collection of decryption techniques and the analysis of various texts combine in the breaking of a 200-year old code', American Sicentist, 97 (2009), 142-149参照.)

着目するのは二連字の出現確率である(たとえばquは「有望」,lsは「非有望」,「dx」は「不存在」としてスコアを割り当てる).さらに,行転置鍵を一度につきとめるのではなく,相続く2つの行を見つけ出すことに集中する.より具体的には,1セクション内の行数(K)について特定の値を想定し,相続く2つの行(R,S)を想定し,それら2つの行の行頭に挿入されている冗字の数(C,D)の最も有望な値を見出す.その過程でスコアが算出されるので,それに基づいてさまざまなK,R,Sの組み合わせのうちスコアが最良のものが決定できる.

二連字を使うことは転置式暗号の解読のための常套手段である.(たとえばDavid Kahn, The Codebreakers, p.302 ff; Fletcher Pratt, Secret and Urgent, p.97 ff.参照.)冗字や手稿からの転写ミスがあると通常の英文には表われない二連字も生起することになるが,スミスラインは,二連字がどのくらい有望かの定量的なスコアを導入することによって冗字や転写ミスにも対応できる堅牢なアルゴリズムを構築することに成功した.また,どこかに空白を挿入すべき可能性をも考慮に入れており,これによりたとえば手稿のwをuiとする転写ミスによる桁のずれにも柔軟に対応できるという.さらに,二連字を手がかりに隣接する行を一行ずつみつけていくという逐次的な方法を採用することにより,計算コストを現実的なレベルまで引き下げることに成功した.

パターソンの残した暗号の鍵は1-3-5-6-2-7-4(行転置鍵)および3-4-7-5-2-8-9(冗字数鍵)と突き止められた.解読された復元されたメッセージは,"In Congress, July fourth, one thousand seven hundred and seventy six. A declaration by the Representatives of the United States of America in Congress assembled. When in the course of human events,...."というもので,アメリカ独立宣言の前文であった.



©2009 S.Tomokiyo
First posted on 19 April 2009. Last modified on 19 April 2009.
Articles on Historical Cryptography
inserted by FC2 system