Problem 59 - XOR暗号解読

はじめての暗号解読に挑んでみる。

(訳者注: 文字コードの説明は適当です) 各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準としてASCII (American Standard Code for Information Interchange) がある. ASCIIでは, 大文字A = 65, アスタリスク (*) = 42, 小文字k = 107というふうに割り当てられている.
モダンな暗号化の方法として, テキストファイルの各バイトをASCIIに変換し, 秘密鍵から計算された値とXORを取るという手法がある. XOR関数の良い点は, 暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号できる点である. 65 XOR 42 = 107であり, 107 XOR 42 = 65である.
破られない暗号化のためには, 鍵は平文と同じ長さのランダムなバイト列でなければならない. ユーザーは暗号文と暗号化鍵を別々の場所に保存する必要がある. また, もし一方が失われると, 暗号文を復号することは不可能になる.
悲しいかな, この手法はほとんどのユーザーにとって非現実的である. そこで, 鍵の変わりにパスワードを用いる手法が用いられる. パスワードが平文より短ければ (よくあることだが), パスワードは鍵として繰り返し用いられる. この手法では, 安全性を保つために十分長いパスワードを用いる必要があるが, 記憶するためにはある程度短くないといけない.
この問題での課題は簡単になっている. 暗号化鍵は3文字の小文字である. cipher1.txtは暗号化されたASCIIのコードを含んでいる. また, 平文はよく用いられる英単語を含んでいる. この暗号文を復号し, 平文のASCIIでの値の和を求めよ

要するにXOR暗号を解読せよって事。

結構ハマりポイント多数。

abcというパスワードがあったら、1文字目をaでxor。2文字目をbでxor。3文字目をcでxor。
- という感じ。3回xorしてたよ・・・あんま意味なし。
記号、数字を含むけど、あんまり記号を含みすぎるとどんなパスワードでもマッチしちゃって、解読できない。

結構大変でした。

方針は,

とりあえず3つに分けちまう
xorしてアタック
文字としての整合性をチェック
繋げる

デス。

暗号作成ツールを作りながら進めたほうがいいかも。

文字の解析部分はもうちょっとなんとかなると思うけど、疲れたので・・・。

(define (problem59 data)
  (letrec ((a (char->integer #\a))
           (z (char->integer #\z))
           (A (char->integer #\A))
           (Z (char->integer #\Z))
           (real-string? (lambda (s)
                           (cond ((null? s) #t)
                                 ((not (or (and (>= (car s) a)
                                                (<= (car s) z))
                                           (and (>= (car s) A)
                                                (<= (car s) Z))
                                           (and (>= (car s) (char->integer #\0))
                                                (<= (car s) (char->integer #\9)))
                                           (= (car s) (char->integer #\space))
                                           (= (car s) (char->integer #\())
                                           (= (car s) (char->integer #\)))
                                           (= (car s) (char->integer #\;))
                                           (= (car s) (char->integer #\'))
                                           (= (car s) (char->integer #\.))
                                           (= (car s) (char->integer #\,))
                                           (= (car s) (char->integer #\!))))
                                  #f)
                                 (else
                                   (real-string? (cdr s))))))
           (attack (lambda (key data)
                     (let ((code (map (lambda (n)
                                           (bitwise-xor n key))
                                         data)))
                       (and (real-string? code) code))))
           (try (lambda (key data)
                  (let ((res (attack key data)))
                    (cond (res res)
                          ((> key z) #f)
                          (else
                            (try (+ key 1) data))))))
           (rotate-list (lambda (n l)
                          (if (zero? n)
                              l
                              (rotate-list (- n 1)
                                           (append
                                             (cdr l)
                                             (list (car l)))))))
           (make-attack-list (lambda (data)
                                 (fold-right
                                   (lambda (s acc)
                                     (rotate-list 1 (cons (cons s (car acc)) (cdr acc))))
                                   '(() () ())
                                   data))))
    (apply + (apply append (map (lambda (x)
                                  (try a x))
                                (make-attack-list data))))))

(problem59 *code*) ; 107359

; (The Gospel of John, chapter 1)
; 1 In the beginning the Word already existed.He was with God, and he was God.
; 2 He was in the beginning with God.
; 3 He created everything there is. Nothing exists that he didn't make.
; 4 Life itself was in him, and this life gives light to everyone.
; 5 The light shines through the darkness, and the darkness can never extinguish it.
; 6 God sent John the Baptist
; 7 to tell everyone about the light so that everyone might believe because of his testimony.
; 8 John himself was not the light; he was only a witness to the light.
; 9 The one who is the true light, who gives light to everyone, was going to come into the world.
; 10 But although the world was made through him, the world didn't recognize him when he came.
; 11 Even in his own land and among his own people, he was not accepted.
; 12 But to all who believed him and accepted him, he gave the right to become children of God.
; 13 They are reborn! This is not a physical birth resulting from human passion or plan, this rebirth comes from God.
; 14 So the Word became human and lived here on earth among us. He was full of unfailing
; love and faithfulness. And we have seen his glory, the glory of the only Son of the Father

聖書か。

3文字というヒントがなかったらかなり辛かった。