2012/02/17

John Nashの暗号器

John Nashが1955年にNSAに送った、暗号アルゴリズムを提案する書簡というのを見た(pdf)。 最初の書簡では、「暗号アルゴリズムにとって重要な性質は、暗号文から鍵を推測するための計算量が、鍵長に対して指数的に増加することである (そして単純な置換暗号はこの性質を満たさない)」という一般的な議論がなされ、 次の書簡でその性質を満たす具体的な暗号器の例が示されている。

(関係ないけど、この書簡は「手書きの文字の綺麗さ/汚さで内容を判断してはいけない」という好例かもしれない。)

NSAの返信は「うちのセキュリティ標準に達してない」というそっけないものだが、 当時のレベルとしてはどんなものだったんだろう。 Nashの示したアルゴリズム自体は現代のコンピュータなら簡単だけど、 当時の技術でどのくらいのものだったのかというのも気になる。 既に真空管式やリレー式のプログラム内蔵式のコンピュータはあったはずだけど。

なんてことを考えてるうちに、何となく試したくなって Nashの暗号器を実装してみた。Gaucheの次のバージョンに入るgeneratorの 例にもなりそうだ。

コードはこちら。実行にはGaucheの開発版HEAD(2fa6baf以降)が必要。

• make-enciphererとmake-deciphererがそれぞれ暗号化器と復号化器を作る。
• 暗号の鍵は、P0, P1, R0, R1で指定されるPermuter-Reverser (P/R)ユニットの構成法。 make-permuterが与えられたパラメータからP/Rユニットを作る。例を参照。
• P/Rユニットは、1ビット入力を受け取り1ビットの出力を返す手続きとして実装される。
• 暗号化器は平文のビット列のジェネレータを受け取り、暗号化されたビット列のジェネレータを返す。
• 復号化器は暗号化されたビット列のジェネレータを受け取り、平文のビット列のジェネレータを返す。

実装の本質はここまで。後は文字列をビット列のジェネレータに変換したり、 その逆をやったりするユーティリティ。

ジェネレータを介しているので、パイプをつなげるみたいにして 暗号化器と復号化器をつなげることができる。

($ bools->string $ D $ E $ string->bools "hi, there!")

とやれば文字列をEで暗号化、Dで復号化してすぐ文字列に直してる。

($ write-bools $ D $ E $ port->bools (current-input-port))

とすると、標準入力から読み取ってEで暗号化し、Dで復号化して標準出力に書き出す。

Tags: Programming, Gauche