现代密码学 实验一

题目一

题目地址：http://www.cryptopals.com/sets/1

1.Convert hex to base64

题目地址：https://www.cryptopals.com/sets/1/challenges/1

1
2
3
from base64 import b64encode

print(b64encode(bytes.fromhex('49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d')).decode())

2.Fixed XOR

题目地址：https://www.cryptopals.com/sets/1/challenges/2

1
2
3
4
5
6
7
def bytesxor(a, b):
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])
    
print(bytesxor(bytes.fromhex('1c0111001f010100061a024b53535009181c'), bytes.fromhex('686974207468652062756c6c277320657965')).hex())

3.Single-byte XOR cipher

题目地址：https://www.cryptopals.com/sets/1/challenges/3

题目提到了一句：

Achievement Unlocked
You now have our permission to make “ETAOIN SHRDLU” jokes on Twitter.

查询可以得知“etaoinshrdlu”就是最常用的12个字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def score(s):
    ans = 0
    for c in s.lower():
        if c in b" etaoinshrdlu":
            ans += 2
        elif 32 <= c <= 126:
            ans += 1
        else:
            ans -= 5
    return ans


s = bytes.fromhex("1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736")
best = None

for i in range(256):
    x = bytes([c ^ i for c in s])
    cur = score(x)
    if best is None or cur > best[0]:
        best = (cur, i, x)

print(best[1])
print(best[2].decode())

4.Detect single-character XOR

题目地址：https://www.cryptopals.com/sets/1/challenges/4

题目需要下载一个txt文件，利用AI+requests改成全自动化脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def score(s):
    ans = 0
    for c in s.lower():
        if c in b" etaoinshrdlu":
            ans += 2
        elif 32 <= c <= 126:
            ans += 1
        else:
            ans -= 5
    return ans


s = bytes.fromhex("1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736")
best = None

for i in range(256):
    x = bytes([c ^ i for c in s])
    cur = score(x)
    if best is None or cur > best[0]:
        best = (cur, i, x)

print(best[1])
print(best[2].decode())

5.Implement repeating-key XOR

题目地址：https://www.cryptopals.com/sets/1/challenges/5

1
2
3
4
5
6
7
8
9
def xor(a, key):
    return bytes([a[i] ^ key[i % len(key)] for i in range(len(a))])

s = (
    "Burning 'em, if you ain't quick and nimble\n"
    "I go crazy when I hear a cymbal"
).encode()

print(xor(s, b"ICE").hex())

6.Break repeating-key XOR

题目地址：https://www.cryptopals.com/sets/1/challenges/6

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
51
52
53
54
55
56
import base64
import requests


def score(s):
    ans = 0
    for c in s.lower():
        if c in b" etaoinshrdlu":
            ans += 2
        elif 32 <= c <= 126:
            ans += 1
        else:
            ans -= 5
    return ans


def hamming(a, b):
    return sum((x ^ y).bit_count() for x, y in zip(a, b))


def one_byte_xor(s):
    best = None
    for i in range(256):
        x = bytes([c ^ i for c in s])
        cur = score(x)
        if best is None or cur > best[0]:
            best = (cur, i, x)
    return best


data = base64.b64decode(requests.get("https://cryptopals.com/static/challenge-data/6.txt").text)
cand = []

for keysize in range(2, 41):
    blocks = [data[i : i + keysize] for i in range(0, keysize * 8, keysize)]
    if len(blocks[-1]) < keysize:
        continue
    dist = 0
    for i in range(len(blocks) - 1):
        dist += hamming(blocks[i], blocks[i + 1]) / keysize
    cand.append((dist / (len(blocks) - 1), keysize))

best = None

for _, keysize in sorted(cand)[:5]:
    key = b""
    for i in range(keysize):
        block = bytes([data[j] for j in range(i, len(data), keysize)])
        key += bytes([one_byte_xor(block)[1]])
    plain = bytes([data[i] ^ key[i % len(key)] for i in range(len(data))])
    cur = score(plain)
    if best is None or cur > best[0]:
        best = (cur, key, plain)

print(best[1].decode())
print("\n".join(best[2].decode(errors="ignore").splitlines()[:4]))

题目二

题目地址：https://www.mysterytwisterc3.org/en/challenges/level-2/cracking-sha1-hashed-passwords

1.MTC3: Cracking SHA1-Hashed Passwords

1
2
3
4
5
6
7
8
9
10
11
import hashlib
import itertools

target = "67ae1a64661ac8b4494666f58c4822408dd0a3e4"
chars = ["(", "Q", "=", "w", "i", "n", "*", "5"]

for x in itertools.permutations(chars):
    s = "".join(x)
    if hashlib.sha1(s.encode()).hexdigest() == target:
        print(s)
        break