プロジェクトオイラー Problem 59 「XOR暗号解読」 †

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での値の和を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2059




解法
eが一番多いのでeへ多く変換できる数字。
これを
1,4,7、、、
2,5,8、、、
3,6,9、、
文字目でそれぞれ個別に求めて計算。
何か楽しみ方を見いだせない問題なのでコードも適当。


is_ok1(X,1):-atom_codes('the',X),!.
is_ok1(_,0):-!.
is_ok2(X,2):-atom_codes('this',X),!.
is_ok2(_,0):-!.

search([X1,X2,X3],[A1,A2,A3],Sum,3,Sum1,[]):-!,
      Sum1 is Sum+(A1 xor X1)+(A2 xor X2)+(A3 xor X3).

search([X1,X2,X3],[A1,A2,A3,A4|Rest],Sum,IsOK,Result,[A11|ReText]):-
      A11 is A1 xor X1,
      A22 is A2 xor X2,
      A33 is A3 xor X3,
      A44 is A4 xor X1,
      is_ok1([A11,A22,A33],Add1),
      is_ok2([A11,A22,A33,A44],Add2),
      IsOK1 is IsOK \/ Add1 \/ Add2,
      !,
      Sum1 is Sum+A11,
      search([X2,X3,X1],[A2,A3,A4|Rest],Sum1,IsOK1,Result,ReText)
      .
search([X1,X2,X3],[A1|Rest],Sum,IsOK,Result,[A11|ReText]):-
      !,
      A11 is A1 xor X1,
      Sum1 is Sum+(A1 xor X1),
      search([X2,X3,X1],Rest,Sum1,IsOK,Result,ReText).



change(N,N1):-!,
      char_code('e',E),
      N1 is N xor E.


count([],[Count,X],[[Count,X1]]):-!,
      change(X,X1).
count([X|Xs],[Count,X],Result):-
      !,
      Count1 is Count+1,
      count(Xs,[Count1,X],Result).
count([X1|Xs],[Count,X],[[Count,X2]|Result]):-
      change(X,X2),
      !,
      count(Xs,[1,X1],Result).

count_w(Text,[X1,X2,X3,X4,X5,X6]):-
      msort(Text,[Top|Text1]),
      count(Text1,[1,Top],Count),
      msort(Count,Count1),
      reverse(Count1,[X1,X2,X3,X4,X5,X6|_]).


split3([],[],[],[]):-!.
split3([X|Text],[X|Text0],Text1,Text2):-
      !,
      split3(Text,Text1,Text2,Text0).

main59:-
      open('pe59.txt',read,IS),
      read_term(IS,Text,[]),
      close(IS),
      split3(Text,Text0,Text1,Text2),
      count_w(Text0,XORs0),
      count_w(Text1,XORs1),
      count_w(Text2,XORs2),
      member([_,A0],XORs0),
      member([_,A1],XORs1),
      member([_,A2],XORs2),
      search([A0,A1,A2],Text,0,0,Ans,ReText),
      atom_codes(AnsText,ReText),
      write(AnsText),nl,
      write(Ans).