はじめに
yuzuemonさんが何かのテストらしきものに取り組んでおられ、つぎのようにおっしゃっている。
初暗号挑戦で力技過ぎた感があるのですが、結局法則はあったのでしょうか
もし解いた人で法則を見つけた人がいたら教えて下さい
取り上げられている課題を私も実際に解いてみたところ、一定の規則性を見つけることができた。結論を先に書こう。その規則性というか処理手順はcommon lispでは以下のように表すことができる。
(lambda (index rhs) (mod (funcall (if (evenp rhs) #'- #'+) index rhs) 26))
以下、この処理を探し出すまでに行ったことを振り返ってみよう。
テストケースの用意
まず、「暗号文 : 解読結果」をもとに暗号文と復号結果のペアを登録しておく。
(defparameter *test1* '("a0c2e4g6" "aaaa")) (defparameter *test2* '("a0z1c2x3" "aaaa")) (defparameter *test3* '("p65e68t2o51d27n48u38n13" "corneria")) (defparameter *test4* '("x6136494262r7484725313x185670378k2531105274x7114948063" "venom"))
暗号文を適宜切り出す処理を作成する
(ql:quickload :cl-ppcre) (defun get-base-char (seq) (subseq seq 0 1)) (defun get-number-of-times-moving (seq) (parse-integer (subseq seq 1))) (defun conv-string-of-cipher-to-list (str) (ppcre:all-matches-as-strings "\\w\\d+" str)) (defun get-pair-of-string-and-nums (str) (mapcar #'(lambda (x) (cons (get-base-char x) (get-number-of-times-moving x))) (conv-string-of-cipher-to-list str))) ;; (get-pair-of-string-and-nums (car *test1*)) ;; -> (("a" . 0) ("c" . 2) ("e" . 4) ("g" . 6))
文字をindexに変換する処理をつくる
ここではaを0、bを1、cを2のように変換する。数値からアルファベットを生成できるようにもしておく。以下では数値の部分をindexと呼ぶ。
(defun conv-char-code-to-index (i) "convert char-code to index. ex.) #\a -> 0" (- i (char-code #\a))) (defun conv-index-to-char-code (i) "convert index to char-code. ex.) 0 -> #\a" (+ i (char-code #\a))) (defun conv-string-to-index (str) "convert char-code of a string to index. ex.) \"a\" -> 0" (labels ((conv-string-to-num (str) (char-code (coerce str 'character)))) (conv-char-code-to-index (conv-string-to-num str)))) (defun get-pair-of-index-and-nums (str) (mapcar #'(lambda (x) (cons (conv-string-to-index (get-base-char x)) (get-number-of-times-moving x))) (conv-string-of-cipher-to-list str)))
indexを動かす処理（第1バージョン）を作成する
"a0c2e4g6 : aaaa"を念頭において、つぎのような処理を作成してみた。
;; move-index 1st version (uncompleted) (defun move-index (index rhs) (- index rhs))
復号する処理を作成する
数値とアルファベットからなる文字列を受け取り、アルファベットのみの文字列を返す処理を作成する。
(defun decipher (str) (labels ((concat (lst) (apply #'concatenate 'string (mapcar #'princ-to-string lst))) (get-indexes (str) (mapcar #'(lambda (x) (move-index (car x) (cdr x))) (get-pair-of-index-and-nums str))) (mapcar-and-concat (fn lst) (concat (mapcar fn lst))) (conv-index-to-char (x) (code-char (+ (char-code #\a) x)))) (values (mapcar-and-concat #'(lambda (x) (conv-index-to-char x)) (get-indexes str)) (get-indexes str) (get-pair-of-index-and-nums str) (get-pair-of-string-and-nums str) str)))
test1 の暗号文を復号してみる
(decipher (car *test1*)) ;; "aaaa" ;; (0 0 0 0) ;; ((0 . 0) (2 . 2) (4 . 4) (6 . 6)) ;; (("a" . 0) ("c" . 2) ("e" . 4) ("g" . 6)) ;; "a0c2e4g6"
うまくいったようだ。
テストを一度に行う処理を作成する
複数のテストを一度に行うようにする。
(defun test-decipher (lst) (multiple-value-bind (a b c d e) (decipher (car lst)) (values (string= (cadr lst) a) a b c d e))) (defun tests (fn lst) (labels ((rec (next result) (if (null next) result (let* ((x (car next)) (result (funcall fn x))) (format t "~A ; => ~A~%" x result) (format t "~15,,,'=A~%" "=") (rec (when result (cdr next)) result))))) (rec lst t)))
テストを試してみる->*test2*で失敗
(tests #'test-decipher (list *test1* *test2* *test3* *test4*)) ;; (a0c2e4g6 aaaa) ; => T ;; ==================== ;; (a0z1c2x3 aaaa) ; => NIL ;; ==================== ;; NIL
test2の部分の処理が適切ではないようだ。
テストした結果をより詳細に表示できるようにする
テストした結果が正しくないときに、その内容を表示するよう処理を書き換えた。
(defun test-decipher (lst) (labels ((conv-string-to-list (str) (mapcar #'string (concatenate 'list str))) (conv-string-to-index-directly (str) (mapcar #'conv-string-to-index (conv-string-to-list str))) (get-list-only-indexes (lst) (cadr lst)) (get-list-indexes-and-number-of-times (lst) (caddr lst)) (get-list-string-and-number-of-times (lst) (cadddr lst))) (let* ((result (multiple-value-list (decipher (car lst)))) (string-deciphered (car result)) (string-expected (cadr lst))) (if (string= string-expected string-deciphered) t (progn (mapc #'(lambda (string-test string-post string-and-times-of-moving index-and-times-of-moving index-test index-post) (if (string= string-test string-post) (format t "[~A] ----~%" string-post) (let* ((index-pre (car index-and-times-of-moving)) (diff-index-post (- index-post index-pre)) (diff-index-test (- index-test index-pre))) (format t "~80<[~A] (~2D)~;*~2D [~A]~;<-~;~2D~;<-~;[~A] ~9,,,A~;diff: ~3,,,@D (~3,,,@D); ~3,,,@D (~3,,,@D)~>~%" string-post index-post index-test string-test (+ index-pre (cdr index-and-times-of-moving)) (car string-and-times-of-moving) index-and-times-of-moving diff-index-post (funcall (if (< 0 diff-index-post) #'- #'+) diff-index-post 26) diff-index-test (funcall (if (< 0 diff-index-test) #'- #'+) diff-index-test 26)) ))) (conv-string-to-list (car result)) (conv-string-to-list string-expected) (get-list-string-and-number-of-times result) (get-list-indexes-and-number-of-times result) (get-list-only-indexes result) (conv-string-to-index-directly string-expected)) (values nil (list (car lst) string-deciphered string-expected)))))))
これを用いると、つぎのような出力結果を得ることができる。
(tests #'test-decipher (list *test1* *test2* *test3* *test4*)) ;; (a0c2e4g6 aaaa) ; => T ;; =============== ;; [a] ---- ;; [a] ( 0) *24 [y] <- 26 <- [z] (25 . 1) diff: -25 ( +1); -1 (+25) ;; [a] ---- ;; [a] ( 0) *20 [u] <- 26 <- [x] (23 . 3) diff: -23 ( +3); -3 (+23) ;; (a0z1c2x3 aaaa) ; => NIL ;; =============== NIL
この出力結果からわかるのは、zからの移動とxからの移動において、移動する方向が逆になっていることである。
indexを動かす処理（第2バージョン）を作成する->*test3*で失敗
zからの移動とxからの移動時に、移動する方向を逆にするよう処理を改変した。アルファベットのindexとアルファベットの隣の数値を足しあわせ、それが26を超えるときには、移動する方向を逆にしてみる。
;; new version 2nd version (uncompleted) (defun move-index (index rhs) (let ((result (+ index rhs))) (if (>= result 26) (mod result 26) (- index rhs))))
これを用いてテストしてみよう。
(tests #'test-decipher (list *test1* *test2* *test3* *test4*)) ;; (a0c2e4g6 aaaa) ; => T ;; =============== ;; (a0z1c2x3 aaaa) ; => T ;; =============== ;; [c] ---- ;; [o] (14) *20 [u] <- 72 <- [e] (4 . 68) diff: +10 (-16); +16 (-10) ;; [r] ---- ;; [n] ---- ;; [e] ---- ;; [r] (17) * 9 [j] <- 61 <- [n] (13 . 48) diff: +4 (-22); -4 (+22) ;; [i] ( 8) * 6 [g] <- 58 <- [u] (20 . 38) diff: -12 (+14); -14 (+12) ;; [a] ---- ;; (p65e68t2o51d27n48u38n13 corneria) ; => NIL ;; =============== NIL
今度は*test3*の処理がうまくいかなかったようだ。そのうまく行かなかった処理を見る限りでは、とくに法則らしきものは見当たらないように思われる。
indexを動かす処理（第3バージョン）を作成する->同じく*test3*で失敗
上記のmove-indexの処理に手を加えよう。今回は、アルファベットのindexとアルファベットのとなりの数値を足しあわせてその結果の商を取得し、それをもとにindexの移動方向を変えてみる。
;; move-index 3rd version (uncompleted) (defun move-index (index rhs) (let* ((result (truncate (+ index rhs) 26))) (mod (funcall (if (evenp result) #'- #'+) index rhs) 26)))
これを用いてテストをしても、やはり*test3*の判定で失敗してしまう。
(tests #'test-decipher (list *test1* *test2* *test3* *test4*)) ;; (a0c2e4g6 aaaa) ; => T ;; =============== ;; (a0z1c2x3 aaaa) ; => T ;; =============== ;; [c] ---- ;; [o] ---- ;; [r] ---- ;; [n] (13) *15 [p] <- 65 <- [o] (14 . 51) diff: -1 (+25); +1 (-25) ;; [e] ---- ;; [r] ---- ;; [i] ---- ;; [a] ---- ;; (p65e68t2o51d27n48u38n13 corneria) ; => NIL ;; =============== NIL
この結果から分かることは何だろうか。index を 1 減らしたいところで、1 増やしてしまったということだ。言い換えると、index を動かす方向の判定がおかしいようである。
テストの結果をさらに細かく出力する
問題を整理するために、テストの結果を詳しく出力する処理を作成してみよう。
;; truncate version (defun test-decipher-and-truncate (lst) (format t "~80< ~20,,,A~;~17,,,A~;->~;direction (truncate)~;move (mod)~>~%" "end" "from") (mapc #'(lambda (x y) (let* ((lhs (car x)) (rhs (cdr x)) (index (conv-string-to-index lhs)) (truncate-result (truncate (+ index rhs) 26))) (format t "~80<[~A] (~2,,,D)~;([~A] ~2,,,D, ~2,,,D)~;->~;~A (~A)~;~2,,,D (~2,,,D)~>~%" y (conv-string-to-index y) lhs (conv-string-to-index lhs) rhs (if (evenp truncate-result) "L" "R") truncate-result rhs (mod rhs 26)))) (get-pair-of-string-and-nums (car lst)) (mapcar #'string (concatenate 'list (cadr lst)))))
これを利用すると、つぎのような結果を取得できる。
(test-decipher-and-truncate *test3*) ;; end from -> direction (truncate) move (mod) ;; [c] ( 2) ([p] 15, 65) -> R (3) 65 (13) ;; [o] (14) ([e] 4, 68) -> L (2) 68 (16) ;; [r] (17) ([t] 19, 2) -> L (0) 2 ( 2) ;; [n] (13) ([o] 14, 51) -> L (2) 51 (25) ;; [e] ( 4) ([d] 3, 27) -> R (1) 27 ( 1) ;; [r] (17) ([n] 13, 48) -> L (2) 48 (22) ;; [i] ( 8) ([u] 20, 38) -> L (2) 38 (12) ;; [a] ( 0) ([n] 13, 13) -> R (1) 13 (13) (("p" . 65) ("e" . 68) ("t" . 2) ("o" . 51) ("d" . 27) ("n" . 48) ("u" . 38) ("n" . 13))
この結果のうち、R と L の部分を並び替えてみよう。そして、[n] の部分は R になるはずなので、R に書き換えておく。
;; end from -> direction (truncate) move (mod) ;; [c] ( 2) ([p] 15, 65) -> R (3) 65 (13) ;; [n] (13) ([o] 14, 51) -> R (2) (*L) 51 (25) ;; [e] ( 4) ([d] 3, 27) -> R (1) 27 ( 1) ;; [a] ( 0) ([n] 13, 13) -> R (1) 13 (13) ;; [o] (14) ([e] 4, 68) -> L (2) 68 (16) ;; [r] (17) ([n] 13, 48) -> L (2) 48 (22) ;; [r] (17) ([t] 19, 2) -> L (0) 2 ( 2) ;; [i] ( 8) ([u] 20, 38) -> L (2) 38 (12)
これらを眺めて気づくのは、direction が R のグループでは、fromの二番目の数値が奇数になっており、 L のグループでは偶数になっているということだ。
これをもとに、fromの二番目の数値によってdirectionを決するようなテスト処理を作ってみよう。
;; not truncate version (defun test-decipher-and-not-truncate (lst) (format t "~80< ~20,,,A~;~13,,,A~;->~;direction (evenp)~;move (mod)~>~%" "end" "from") (mapc #'(lambda (x y) (let* ((lhs (car x)) (rhs (cdr x)) (index (conv-string-to-index lhs))) (format t "~80<[~A] (~2,,,D)~;([~A] ~2,,,D, ~2,,,D)~;->~;~A (~3,,,A)~;~2,,,D (~2,,,D)~>~%" y (conv-string-to-index y) lhs (conv-string-to-index lhs) rhs (if (evenp rhs) "L" "R") (evenp rhs) rhs (mod rhs 26)))) (get-pair-of-string-and-nums (car lst)) (mapcar #'string (concatenate 'list (cadr lst)))))
実行結果はつぎのとおりである。
(test-decipher-and-not-truncate *test3*) ;; end from -> direction (evenp) move (mod) ;; [c] ( 2) ([p] 15, 65) -> R (NIL) 65 (13) ;; [o] (14) ([e] 4, 68) -> L (T ) 68 (16) ;; [r] (17) ([t] 19, 2) -> L (T ) 2 ( 2) ;; [n] (13) ([o] 14, 51) -> R (NIL) 51 (25) ;; [e] ( 4) ([d] 3, 27) -> R (NIL) 27 ( 1) ;; [r] (17) ([n] 13, 48) -> L (T ) 48 (22) ;; [i] ( 8) ([u] 20, 38) -> L (T ) 38 (12) ;; [a] ( 0) ([n] 13, 13) -> R (NIL) 13 (13) (("p" . 65) ("e" . 68) ("t" . 2) ("o" . 51) ("d" . 27) ("n" . 48) ("u" . 38) ("n" . 13))
とくに問題はなさそうだ。
indexを動かす処理（第4バージョン）を作成する->すべて成功
以上の検討を受けて、つぎのような処理を作成するに至った。
;; move-index 4th version (completed) (defun move-index (index rhs) (mod (funcall (if (evenp rhs) #'- #'+) index rhs) 26))
これを用いて早速テストしてみよう。
(tests #'test-decipher (list *test1* *test2* *test3* *test4*)) ;; (a0c2e4g6 aaaa) ; => T ;; ==================== ;; (a0z1c2x3 aaaa) ; => T ;; ==================== ;; (p65e68t2o51d27n48u38n13 corneria) ; => T ;; ==================== ;; (x6136494262r7484725313x185670378k2531105274x7114948063 venom) ; => T ;; ==================== ;; T
うまく処理できているようだ。
最後の問題に取り組む
残された最後の問題を解いてみよう。
(defparameter *test5* "m7752902780q5670754954w2654637406q5286271066m8125522416a1926172574x504148223l9676431138g5289793839l5799859691n5135660909g5241613386k4148674163p2895427859i4115643171d6373795065") (format nil "~A" (decipher *test5*)) ;; "awesomeblackhole"
うまく解くことが出来た。
おわりに
このエントリーでは、試行錯誤しながら件の問題を解いていく過程を示した。一定の規則性を発見するまで苦労したが、それを見つければ難なく解答できるだろう。