「プロジェクトオイラー問５９」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問５９」(2014/02/20 (木) 03:39:11) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2059
*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での値の和を求めよ.
解法
１,4,7、、、
2,5,8,,,
3,6,9,,,
文字目の暗号化された文字の出現頻度を個別に数えてそれが多い順にソート。
上位７番目までのどれかがEになる可能性は高いのでその中で探索。
theとthisを使用した。
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).
check(N):-!,
char_code('a',A),
char_code('z',Z),
A=<N,
N=<Z.
lists(7,_,[]):-!.
lists(Deep,[[_,N]|Count],[N1|Result]):-
char_code('e',E),
N1 is N xor E,
check(N1),
!,
Deep1 is Deep+1,
lists(Deep1,Count,Result).
lists(Deep,[_|Count],Result):-
!,
lists(Deep,Count,Result).
count([X,_,_|Rest],Count,Result):-
select([Len,X],Count,Count1),
!,
Len1 is Len+1,
count(Rest,[[Len1,X]|Count1],Result).
count([X,_,_|Rest],Count,Result):-
!,
count(Rest,[[1,X]|Count],Result).
count(_,Count,Result):-!,
sort(Count,Count1),
reverse(Count1,Count2),
write(Count2),
lists(0,Count2,Result).
main59:-
open('pe59.txt',read,IS),
read_term(IS,Text,[]),
close(IS),
[_|Text1]=Text,
[_|Text2]=Text1,
count(Text,[],List),
count(Text1,[],List2),
count(Text2,[],List3),
nl,nl,
write(List),nl,
write(List2),nl,
write(List3),
nl,
member(X1,List),
member(X2,List2),
member(X3,List3),
search([X1,X2,X3],Text,0,0,Ans,ReText),
atom_codes(AnsText,ReText),
write(Ans),nl,
write(AnsText).
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2059
*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での値の和を求めよ.
解法
１,4,7、、、
2,5,8,,,
3,6,9,,,
文字目の暗号化された文字の出現頻度を個別に数えてそれが多い順にソート。
上位７番目までのどれかがEになる可能性は高いのでその7*7*7全部で探索。
復号がうまくいったかはtheとthisが復号分にあるかで判断した。
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).
check(N):-!,
char_code('a',A),
char_code('z',Z),
A=<N,
N=<Z.
lists(7,_,[]):-!.
lists(Deep,[[_,N]|Count],[N1|Result]):-
char_code('e',E),
N1 is N xor E,
check(N1),
!,
Deep1 is Deep+1,
lists(Deep1,Count,Result).
lists(Deep,[_|Count],Result):-
!,
lists(Deep,Count,Result).
count([X,_,_|Rest],Count,Result):-
select([Len,X],Count,Count1),
!,
Len1 is Len+1,
count(Rest,[[Len1,X]|Count1],Result).
count([X,_,_|Rest],Count,Result):-
!,
count(Rest,[[1,X]|Count],Result).
count(_,Count,Result):-!,
sort(Count,Count1),
reverse(Count1,Count2),
write(Count2),
lists(0,Count2,Result).
main59:-
open('pe59.txt',read,IS),
read_term(IS,Text,[]),
close(IS),
[_|Text1]=Text,
[_|Text2]=Text1,
count(Text,[],List),
count(Text1,[],List2),
count(Text2,[],List3),
nl,nl,
write(List),nl,
write(List2),nl,
write(List3),
nl,
member(X1,List),
member(X2,List2),
member(X3,List3),
search([X1,X2,X3],Text,0,0,Ans,ReText),
atom_codes(AnsText,ReText),
write(Ans),nl,
write(AnsText).
