2012/02/17
John Nashの暗号器
John Nashが1955年にNSAに送った、暗号アルゴリズムを提案する書簡というのを見た(pdf)。 最初の書簡では、「暗号アルゴリズムにとって重要な性質は、暗号文から鍵を推測するための計算量が、鍵長に対して指数的に増加することである (そして単純な置換暗号はこの性質を満たさない)」という一般的な議論がなされ、 次の書簡でその性質を満たす具体的な暗号器の例が示されている。
(関係ないけど、この書簡は「手書きの文字の綺麗さ/汚さで内容を判断してはいけない」という好例かもしれない。)
NSAの返信は「うちのセキュリティ標準に達してない」というそっけないものだが、 当時のレベルとしてはどんなものだったんだろう。 Nashの示したアルゴリズム自体は現代のコンピュータなら簡単だけど、 当時の技術でどのくらいのものだったのかというのも気になる。 既に真空管式やリレー式のプログラム内蔵式のコンピュータはあったはずだけど。
なんてことを考えてるうちに、何となく試したくなって Nashの暗号器を実装してみた。Gaucheの次のバージョンに入るgeneratorの 例にもなりそうだ。
コードはこちら。実行にはGaucheの開発版HEAD(2fa6baf以降)が必要。
;; | |
;; Implementation of John Nash's enciphering-deciphering machine described in | |
;; https://www.nsa.gov/Portals/70/documents/news-features/declassified-documents/nash-letters/nash_letters1.pdf | |
;; | |
(use gauche.sequence) | |
(use gauche.generator) | |
(use srfi-1) | |
(use srfi-43) | |
(use srfi-60) | |
;; The 'key' of this machine is a configuration of Permuter-Reverser (P/R) | |
;; We have N positions in the P/R. You should provide two sets of | |
;; permutations P and reversal-bitmask R. | |
;; P is a permutation of (0 1 ... N-1). R is a list of N booleans | |
(define (make-permuter P0 P1 R0 R1) | |
(define regs (make-vector (length P0) #f)) | |
(^[in-bit] | |
(set! (~ regs 0) in-bit) | |
(permute! regs (uncycle-perm (if in-bit P1 P0))) | |
(vector-map! (^[i b] (xor (~ (if in-bit R1 R0) i) b)) regs) | |
(~ regs 0))) | |
(define (make-encipherer P0 P1 R0 R1) | |
(define P (make-permuter P0 P1 R0 R1)) | |
(define D #f) | |
(^[plaintext-input] | |
(^[] (glet1 in (plaintext-input) | |
(rlet1 r (xor in (P D)) | |
(set! D r)))))) | |
(define (make-decipherer P0 P1 R0 R1) | |
(define P (make-permuter P0 P1 R0 R1)) | |
(define D #f) | |
(^[ciphered-input] | |
(^[] (glet1 in (ciphered-input) | |
(rlet1 r (xor in (P D)) | |
(set! D in)))))) | |
(define (xor a b) (if (and a b) #f (or a b))) | |
;; Convert cycle notation of permutation (see TAOCP 1.3.3) into the | |
;; second-line of the two-line permutation. | |
(define (uncycle-perm p) | |
(map cdr (sort-by (map cons p (append (cdr p) p)) car))) | |
;; End of implementation | |
;; | |
;; The rest is convenient generator utilities | |
;; | |
(define (bytes->bools byte-gen) | |
(define c '()) | |
(^[] | |
(if (null? c) | |
(glet1 d (byte-gen) | |
(set! c (integer->list d 8)) | |
(pop! c)) | |
(pop! c)))) | |
(define (bools->bytes bool-gen) | |
(^[] (let1 bits (generator->list bool-gen 8) | |
(case (length bits) | |
[(0) (eof-object)] | |
[(8) (list->integer bits)] | |
[else (error "premature end of input stream")])))) | |
(define port->bools ($ bytes->bools $ port->byte-generator $)) | |
(define (string->bools s) (call-with-input-string s port->bools)) | |
(define write-bools | |
($ for-each (^b (write-byte b) (flush)) $ generator->lseq $ bools->bytes $)) | |
(define (bools->string bools) | |
(with-output-to-string (cut write-bools bools))) | |
;; Examples | |
#| | |
(define key '((1 3 6 2 4 0 5) | |
(2 1 5 0 3 6 4) | |
(#f #t #f #f #t #f #f) | |
(#t #t #t #f #f #t #t))) | |
(define E (apply make-encipherer key)) | |
(define D (apply make-decipherer key)) | |
($ bools->string $ D $ E $ string->bools "hi, there!") | |
($ write-bools $ D $ E $ port->bools (current-input-port)) | |
|# |
- 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
Post a comment