Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
(訳者注: 文字コードの説明は適当です) 各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準として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での値の和を求めよ.
アプローチ
問題の意味を理解する為に答えから入ると、暗号鍵はgod。
g、o、dの文字コードはそれぞれ$103$、$111$、$100$となる。
(man ascii参照)
cipher.txtの先頭$3$文字は$79,59,12$でありこれらとgodとのXORを取ると下記のようになる。
79 XOR 103 = 40
59 XOR 111 = 84
12 XOR 100 = 104
これらをman asciiで確認すると、「(」、「T」、「h」となり復号できていることが分かる。
解答
time cat cipher.txt |
awk -F, '{for(i=92;i<=122;i++){for(j=92;j<=122;j++){for(k=92;k<=122;k++){for(m=1;m<=NF;m++){if(m%3==1){printf xor($m,i)" "}else if(m%3==2){printf xor($m,j)" "}else{printf xor($m,k)" "}};print ""}}}}' |
grep -v " [0-9] " |
egrep -v " (92|96|124|127) " |
tr ' ' '\n' |
awk '{s+=$1}END{print s}'
107359
real 0m29.638s
user 0m43.669s
sys 0m0.498s
最初は問題の意味がよく分からなかった。。
XORはここでは、($2$進数に直して)XORを取って($10$進数に戻す)という意味だった。
これを理解するのに大分時間がかかった。
また、最初はXORをecho $(( A ^ B ))でやる方法で考えていたが、
調べてみたら単純にawkでできるようだった。
鍵を探す操作で小文字$3$文字と分かっているので、何も考えず総当たりで三重ループした。
その為やや時間がかかっているがよしとする。
答え合わせ
こちらのサイト様と一致していればOKとした。
Project Euler 59 Decrypt the cipher using XOR encryption _ MathBlog
参考にさせて頂いたサイト様
シェルスクリプトでのビット演算(AND、OR、XOR) _ ハックノート
Project Euler 59 _ XOR暗号解読 - PEをMathematicaで
xor = XOR演算する。整数をビット毎に排他的論理和（Gawk専用） - AWK - to_dk notebook