1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Project Euler 59「XOR暗号解読」

Posted at

暗号解読よりも先に問の読解力が試される。
暗号化鍵の3文字は一文字ずつ繰り返し使用するってことなんですね。
意味が分からず小一時間右往左往しました。

下記リンクによると最も使用頻度の高い英単語は「the」らしいです。
https://gakumado.mynavi.jp/gmd/articles/17855

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

from itertools import product

def hoge(path):
    cipher = [ int(x) for x in open(path).read().split(',') ]
    m = len(cipher) // 3 + 1
    for p in product(( chr(97+i) for i in range(26) ), repeat=3):
        decrypted = [ a ^ b for a, b in zip( cipher, [ ord(x) for x in p ] * m ) ]
        text = ''.join( chr(x) for x in decrypted ) 
        if text.find(' The ') != -1 or text.find(' the ') != -1:
            #print(p, text)
            return sum(decrypted)

print(hoge('p059_cipher.txt'))

うーむ、解答も若干難解になってしまったか。

1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?