cryptopals

Posted on Edited on In Word count in article: 11k Reading time ≈ 10 mins.

开始学习cryptopals啦, 一题一题的做完它吧(也不知道能做多久…

目录

cryptopals 1.1 - Convert hex to base64

challenge

The string:

1
49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d

Should produce:

1
SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t

So go ahead and make that happen. You’ll need to use this code for the rest of the exercises.

大概就是手动写一个hex2base64的脚本吧

Base64

写之前先去了解一下hex转base64的原理(wiki真不错
Base64是一种基于64个可打印字符来表示二进制数据的表示方法。由于 ，所以每6个比特为一个单元，对应某个可打印字符。3个字节相当于24个比特，对应于4个Base64单元，即3个字节可由4个可打印字符来表示。
图片.png

转换的时候，将3字节的数据，先后放入一个24位的缓冲区中，先来的字节占高位。数据不足3字节的话，于缓冲器中剩下的比特用0补足。每次取出6比特，按照其值选择

1
2
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

中的字符作为编码后的输出，直到全部输入数据转换完成。

若原数据长度不是3的倍数时且剩下1个输入数据，则在编码结果后加2个=；若剩下2个输入数据，则在编码结果后加1个=。

脚本

知道原理就好写脚本了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def padding(Hex):
    if len(Hex) % 6:
        return Hex + '0' * (6 - len(Hex) % 6)
    return Hex


def encodeb64(Hex):
    Hex = padding(Hex)
    output = ''
    for i in range(0, len(Hex), 6):
        buff = bin(int(Hex[i:i + 6], 16))[2:]
        buff = '0' * (24 - len(buff)) + buff
        for j in range(0, len(buff), 6):
            value = int(buff[j:j + 6], 2)
            if value == 0:
                output += '='
            elif value < 26:
                output += chr(value + 65)
            elif value < 52:
                output += chr(value + 71)
            elif value < 62:
                output += str(value - 52)
            elif value == 62:
                output += '+'
            else:
                output += '/'
    return output


def main():
    Hex = '49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d'
    print(encodeb64(Hex))


if __name__ == '__main__':
    main()


cryptopals 1.2 - Fixed XOR

题目

Write a function that takes two equal-length buffers and produces their XOR combination.

If your function works properly, then when you feed it the string:

1
1c0111001f010100061a024b53535009181c

… after hex decoding, and when XOR’d against:
1
686974207468652062756c6c277320657965

… should produce:
1
746865206b696420646f6e277420706c6179

相同长度的十六进制的xor, 一位一位的xor就行了吧

脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fixex_xor(Hex1, Hex2):
    res = ''
    for i, j in zip(Hex1, Hex2):
        res += hex(int(i, 16) ^ int(j, 16))[2:]
    return res


def main():
    Hex1 = '1c0111001f010100061a024b53535009181c'
    Hex2 = '686974207468652062756c6c277320657965'
    print(fixex_xor(Hex1, Hex2))

if __name__ == '__main__':
    main()

还是比较简单的,后面就不一定了Orz

cryptopals 1.3 - Single-byte XOR cipher

从这里开始难度突然就上升了

题目

The hex encoded string:

1
1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736

… has been XOR’d against a single character. Find the key, decrypt the message.

You can do this by hand. But don’t: write code to do it for you.

How? Devise some method for “scoring” a piece of English plaintext. Character frequency is a good metric. Evaluate each output and choose the one with the best score.

说是一段文字被单个字符(8bit)异或加密了, 要找出这个字符然后输出明文, 密钥空间为, 也不算多, 但是如何让程序找出唯一一个正确的字符?

提示上有提到可以利用解密后的字符串的”得分”. 查了一下, 在一个dalao的博客上找到的这个得分应该叫字符频率(dalao说wiki上有字符频率表, 但我没找到, 就连这个”得分”的相关内容都没找到), 但是还好他的博客里附带了一个字符频率的数组.

1
2
3
4
5
CHARACTER_FREQ = { #字符频率表, 出现一次某字母的得分
    'a': 0.0651738, 'b': 0.0124248, 'c': 0.0217339, 'd': 0.0349835, 'e': 0.1041442, 'f': 0.0197881, 'g': 0.0158610,
    'h': 0.0492888, 'i': 0.0558094, 'j': 0.0009033, 'k': 0.0050529, 'l': 0.0331490, 'm': 0.0202124, 'n': 0.0564513,
    'o': 0.0596302, 'p': 0.0137645, 'q': 0.0008606, 'r': 0.0497563, 's': 0.0515760, 't': 0.0729357, 'u': 0.0225134,
    'v': 0.0082903, 'w': 0.0171272, 'x': 0.0013692, 'y': 0.0145984, 'z': 0.0007836, ' ': 0.1918182}

通过这个字符频率表, 可以定量的分析每次解密结果的得分, 得分最高就代表最接近正常英文语句(或者说文章).

脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
CHARACTER_FREQ = {  # 字符频率表, 出现一次某字母的得分
    'a': 0.0651738, 'b': 0.0124248, 'c': 0.0217339, 'd': 0.0349835, 'e': 0.1041442, 'f': 0.0197881, 'g': 0.0158610,
    'h': 0.0492888, 'i': 0.0558094, 'j': 0.0009033, 'k': 0.0050529, 'l': 0.0331490, 'm': 0.0202124, 'n': 0.0564513,
    'o': 0.0596302, 'p': 0.0137645, 'q': 0.0008606, 'r': 0.0497563, 's': 0.0515760, 't': 0.0729357, 'u': 0.0225134,
    'v': 0.0082903, 'w': 0.0171272, 'x': 0.0013692, 'y': 0.0145984, 'z': 0.0007836, ' ': 0.1918182}

from Set1.Fixed_XOR import fixed_xor


def hex2text(Hex):
    h = Hex
    if len(h) % 2 == 1:
        t = '0' + h
    return ''.join([chr(int(b, 16)) for b in [h[i:i + 2] for i in range(0, len(h), 2)]])


def keygen(LEN):
    for i in range(256): yield ((2 - len(hex(i)[2:])) * '0' + hex(i)[2:]) * (LEN // 2)


def getscore(text):
    score = 0
    for i in text:
        i = i.lower()
        if i in CHARACTER_FREQ:
            score += CHARACTER_FREQ[i]
    return score


def attack(cipher):
    generator = keygen(len(cipher))
    res = []
    for i in generator:
        plain = hex2text(fixed_xor(cipher, i))
        score = getscore(plain)
        res.append([plain, score, i])
    return res


def main():
    cipher = '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736'
    max = [0, -1]
    for i in attack(cipher):
        if max[1] < i[1]:
            max = i
    print(max)


if __name__ == '__main__':
    main()

关于最后面的排序, 看了相关文章发现其实可以用sorted()函数

直接举例子, 简单易懂

  1. 对键排序
    1
    2
    3
    dict1={'a':2,'e':3,'f':8,'d':4}
    list1= sorted(dict1.items(),key=lambda x:x[0])
    print(list1)
    2.对值排序
    1
    2
    3
    dict1={'a':2,'e':3,'f':8,'d':4}
    list1= sorted(dict1.items(),key=lambda x:x[1])
    print(list1)
    借用大佬的代码, 其实attack函数可以写成
    1
    2
    3
    4
    5
    6
    7
    8
    def attack(cipher): 
        generator = keygen(len(cipher))
        res = []
        for i in generator:
            plain = hex2text(fixed_xor(cipher, i))
            score = getscore(plain)
            res.append({'key': key, 'plaintext': plaintext, 'score': score})
        return sorted(res, key = lambda c:c['score'])

cryptopals 1.4 - Detect single-character XOR

题目

One of the 60-character strings in this file has been encrypted by single-character XOR.

Find it.

(Your code from #3 should help.)

意思是说, 在那个文件里面的60个字符串里面, 有一个是被xor加密过后的(一开始读题还以为是60个都是被加密的), 让我们找到他并且解密出来.

其实跟1.3没什么区别, 只是从1组里面选得分最高的密钥变成先根据密钥选出1组里面最高分的, 再选出60个字符串里面最高分的那组.

脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Single_byte_XOR_cipher import *


def main():
    cipher = ''
    res = []
    with open('4.txt', 'r') as f:
        while True:
            cipher = f.readline()[:-1]
            if cipher == '':
                break
            res.append(attack(cipher)[-1])
    print(sorted(res, key=lambda x: x['score'])[-1])


if __name__ == '__main__':
    main()

cryptopals 1.5 - Implement repeating-key XOR

题目

Here is the opening stanza of an important work of the English language:

1
2
Burning 'em, if you ain't quick and nimble
I go crazy when I hear a cymbal

Encrypt it, under the key “ICE”, using repeating-key XOR.

In repeating-key XOR, you’ll sequentially apply each byte of the key; the first byte of plaintext will be XOR’d against I, the next C, the next E, then I again for the 4th byte, and so on.

It should come out to:

1
2
0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272
a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f

Encrypt a bunch of stuff using your repeating-key XOR function. Encrypt your mail. Encrypt your password file. Your .sig file. Get a feel for it. I promise, we aren’t wasting your time with this.

题目升级了!!!

脚本

写完脚本才发现他是要我加密, 而不是解密, 所以只好再写一个加密的了

解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Fixed_XOR import fixed_xor
from Single_byte_XOR_cipher import hex2text


def keypadding(ciplen, key):
    return ''.join([key[i % len(key)] for i in range(ciplen)])


def text2hex(text):
    return ''.join(hex(ord(i))[2:] for i in text)


def main():
    cipher = '0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272\na282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f'
    key = 'ICE'
    cipher = ''.join(cipher.split('\n'))
    padkey = text2hex(keypadding(len(cipher), key))
    res = hex2text(fixed_xor(cipher, padkey))
    print(res)


if __name__ == '__main__':
    main()

加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Fixed_XOR import fixed_xor


def keypadding(ciplen, key):
    return ''.join([key[i % len(key)] for i in range(ciplen)])


def text2hex(text):
    return ''.join(hex(ord(i))[2:] for i in text)


def main():
    plain = "Burning 'em, if you ain't quick and nimble I go crazy when I hear a cymbal"
    key = 'ICE'
    padkey = keypadding(len(plain), key)
    hexplain = text2hex(plain)
    hexpadkey = text2hex(padkey)
    print(fixed_xor(hexplain, hexpadkey))


if __name__ == '__main__':
    main()

cryptopals 1.6 - Break repeating-key XOR

题目

There’s a file here. It’s been base64’d after being encrypted with repeating-key XOR.

Decrypt it.

Here’s how:

  1. Let KEYSIZE be the guessed length of the key; try values from 2 to (say) 40.
  2. Write a function to compute the edit distance/Hamming distance between two strings. The Hamming distance is just the number of differing bits. The distance between:
    this is a test and wokka wokka!!! is 37. Make sure your code agrees before you proceed.
  3. For each KEYSIZE, take the first KEYSIZE worth of bytes, and the second KEYSIZE worth of bytes, and find the edit distance between them. Normalize this result by dividing by KEYSIZE.
  4. The KEYSIZE with the smallest normalized edit distance is probably the key. You could proceed perhaps with the smallest 2-3 KEYSIZE values. Or take 4 KEYSIZE blocks instead of 2 and average the distances.
  5. Now that you probably know the KEYSIZE: break the ciphertext into blocks of KEYSIZE length.
  6. Now transpose the blocks: make a block that is the first byte of every block, and a block that is the second byte of every block, and so on.
  7. Solve each block as if it was single-character XOR. You already have code to do this.
  8. For each block, the single-byte XOR key that produces the best looking histogram is the repeating-key XOR key byte for that block. Put them together and you have the key.

This code is going to turn out to be surprisingly useful later on. Breaking repeating-key XOR (“Vigenere”) statistically is obviously an academic exercise, a “Crypto 101” thing. But more people “know how” to break it than can actually break it, and a similar technique breaks something much more important.

cryptopals 1.7 - AES in ECB mode

题目

The Base64-encoded content in this file has been encrypted via AES-128 in ECB mode under the key

"YELLOW SUBMARINE".

(case-sensitive, without the quotes; exactly 16 characters; I like “YELLOW SUBMARINE” because it’s exactly 16 bytes long, and now you do too).

Decrypt it. You know the key, after all.

Easiest way: use OpenSSL::Cipher and give it AES-128-ECB as the cipher.

You can obviously decrypt this using the OpenSSL command-line tool, but we’re having you get ECB working in code for a reason. You’ll need it a lot later on, and not just for attacking ECB.

未完待续…

cryptopals 1.8 - Detect AES in ECB mode

题目

In this file are a bunch of hex-encoded ciphertexts.

One of them has been encrypted with ECB.

Detect it.

Remember that the problem with ECB is that it is stateless and deterministic; the same 16 byte plaintext block will always produce the same 16 byte ciphertext.

未完待续…