题目一

Project Euler RSA Encryption Problem 182

链接：https://projecteuler.net/problem=182

RSA 有可能存在加密但没有加密的情况。

起初遍历所有可能的消息并逐个加密来计算 unconsealed messages count。后来发现有以下公式：

$$ N = (1 + \gcd(e-1, p-1)) \times (1 + \gcd(e-1, q-1)) $$

from gmpy2 import gcd

p = 1009
q = 3643
phi = (p - 1) * (q - 1)

min_unconcealed = p * q
candidates = []

for e in range(3, phi, 2):
    if gcd(e, phi) != 1:
        continue
    count = (1 + gcd(e - 1, p - 1)) * (1 + gcd(e - 1, q - 1))
    if count < min_unconcealed:
        min_unconcealed = count
        candidates = [e]
    elif count == min_unconcealed:
        candidates.append(e)

print(f"min_unconcealed: {min_unconcealed}")
print("e:", end=" ")

for e in candidates[:50]:
    print(f'{e} ', end='')
print()

题目二

Implement RSA

链接：https://www.cryptopals.com/sets/5/challenges/39

只是实现一个简单的 RSA，要求手写 exgcd 和 modinv，那就手写吧。

from gmpy2 import next_prime, powmod
from secrets import randbits
from Crypto.Util.number import bytes_to_long


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def ex_gcd(a, b):
    if b == 0:
        return 1, 0
    else:
        x1, y1 = ex_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return x, y


def inverse(a, m):
    x, _ = ex_gcd(a, m)
    return (x % m + m) % m


e = 3
while True:
    p = next_prime(randbits(64))
    q = next_prime(randbits(64))
    n = p * q
    phi = (p - 1) * (q - 1)
    if gcd(e, phi) == 1:
        break

m = bytes_to_long(b'pwnerik.cn')
assert 0 <= m < n
c = powmod(m, e, n)

d = inverse(e, phi)
msg = powmod(c, d, n)
assert m == msg

这个实现有很多问题，例如 e、p、q 太小。

题目一

地址：https://mysterytwister.org/challenges/level-2/aes-key--encoded-in-the-machine-readable-zone-of-a-european-epassport

俄罗斯的电子护照编号编码了一个 AES 密钥，我们需要解码出这个密钥然后解密 AES CBC 模式密文。题目说 IV 初始化为 0，那么我们只需要得到密钥。

目标密文（base64）：

9MgYwmuPrjiecPMx61O6zIuy3MtIXQQ0E59T3xB6u0Gyf1gYs2i3K9Jxaa0zj4gTMazJuApwd6+jdyeI5iGHvhQyDHGVlAuYTgJrbFDrfB22Fpil2NfNnWFBTXyf7SDI

题目已经过期了，现在的 ICAO 文件描述的护照编号格式连长度都不一样。这怎么做？只能抄题解了……

题目二

地址：https://cryptopals.com/sets/2

Implement PKCS#7 padding

不需要特别考虑 content 恰好和块等长的情况，相当于再附加一个只有 padding 的块。

def pkcs_7(content: bytes) -> bytes:
    padlen = 16 - (len(content) % 16)
    return content + bytes([padlen] * padlen)


pkcs_7("YELLOW SUBMARINE", 20)

# "YELLOW SUBMARINE\x04\x04\x04\x04"

Implement CBC mode

from base64 import b64decode
from Crypto.Cipher import AES


def aes_ecb_dec(block: bytes, key: bytes) -> bytes:
    assert len(block) % 16 == 0
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.decrypt(block)


def bytesxor(a: bytes, b: bytes) -> bytes:
    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)])])


def depkcs_7(content: bytes) -> bytes:
    return content[:len(content) - content[-1]]


def aes_cbc_dec(cipher: bytes, key: bytes, iv: bytes) -> bytes:
    assert len(cipher) % 16 == 0
    result = bytes()
    prev_block = iv
    for i in range(0, len(cipher), 16):
        block = cipher[i:i+16]
        decrypted = aes_ecb_dec(block, key)
        result += bytesxor(decrypted, prev_block)
        prev_block = block
    return depkcs_7(result)


key = b"YELLOW SUBMARINE"
with open('10.txt', 'r') as f:
    encrypted_b64 = f.read()
cipher = b64decode(encrypted_b64)
print(aes_cbc_dec(cipher, key, b'\x00' * 16))

An ECB/CBC detection oracle

通过检查是否有重复块来判断是否是 ECB 模式，用户输入需要有较长的重复 pattern 才能成功。

def aes_ecb_enc(data: bytes, key: bytes) -> bytes:
    assert len(data) % 16 == 0
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.encrypt(data)


def pkcs_7(content: bytes) -> bytes:
    padlen = 16 - (len(content) % 16)
    return content + bytes([padlen] * padlen)


def aes_cbc_enc(plain: bytes, key: bytes, iv: bytes) -> bytes:
    plain = pkcs_7(plain)
    result = bytes()
    prev_block = iv
    for i in range(0, len(plain), 16):
        block = plain[i: i + 16]
        encrypted = aes_ecb_enc(bytesxor(block, prev_block), key)
        result += encrypted
        prev_block = encrypted
    return result


def randint(a: int, b: int) -> int:
    return randbelow(b - a + 1) + a


def encryption_oracle(plaintext: bytes) -> bytes:
    key = token_bytes(16)
    plaintext = token_bytes(randint(5, 10)) + \
        plaintext + token_bytes(randint(5, 10))

    if randbelow(2) == 0:
        print("Oracle used: ECB")
        ciphertext = aes_ecb_enc(pkcs_7(plaintext), key)
    else:
        print("Oracle used: CBC")
        iv = token_bytes(16)
        ciphertext = aes_cbc_enc(plaintext, key, iv)
    return ciphertext


def detect_mode(ciphertext: bytes) -> str:
    blocks = [ciphertext[i:i+16] for i in range(0, len(ciphertext), 16)]
    if len(set(blocks)) != len(blocks):
        return "ECB"
    return "CBC"


ciphertext = encryption_oracle(input().encode())
mode = detect_mode(ciphertext)
print(f"Detected mode: {mode}")

Byte-at-a-time ECB decryption (Simple)

经典的 ECB Padding Oracle，由于 ECB 对相同 key 相同块的加密无论位置永远相同，我们可以逐字节爆破明文。

由于 key 不变，优化为只初始化 AES cipher 一次。爆破时无需拼接整个 cracked，只需拼接 (padding + cracked)[-15:] 以节省加密时间。

from secrets import token_bytes


unknown = b64decode(
    'Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkgaGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK')
key = token_bytes(16)
cipher = AES.new(key, AES.MODE_ECB)


def encryption_oracle(plaintext: bytes) -> bytes:
    plaintext = pkcs_7(plaintext + unknown)
    ciphertext = cipher.encrypt(plaintext)
    return ciphertext


# block_size is 16
# Mode is ECB

cracked = b''
for i in range(len(unknown)):
    padding = b'A' * ((16 - 1) - (i % 16))
    encrypted = encryption_oracle(padding)
    start = i // 16 * 16
    target_block = encrypted[start:start + 16]
    for j in range(256):
        if encryption_oracle((padding + cracked)[-15:] + bytes([j]))[:16] == target_block:
            cracked += bytes([j])
            break

print(cracked)
assert cracked == unknown

# b"Rollin' in my 5.0\nWith my rag-top down so my hair can blow\nThe girlies on standby waving just to say hi\nDid you stop? No, I just drove by\n"

ECB cut-and-paste

同上，我们调整用户输入的邮箱地址，构造一个包含 PKCS#7 padded admin 和 user 这两个块的 k-v 字符串输入。截取加密后 PKCS#7 padded admin 块，替换加密后的最后一个块（PKCS#7 padded user），获得 admin profile 密文。

（如果要验证邮箱地址格式的话这招估计就不管用了。）

def kv_to_dict(input: str) -> dict[str, str]:
    result = dict()
    for entry in input.split('&'):
        k, v = entry.split('=')
        result[k] = v.replace('%26', '&').replace('%3D', '=')
    return result


def dict_to_kv(input: dict[str, str]) -> str:
    entries: list[str] = list()
    for entry in input.items():
        entries.append(
            f'{entry[0]}={entry[1].replace('&', '%26').replace('=', '%3D')}')
    return '&'.join(entries)


current_uid = 0


def profile_for(email: str) -> str:
    global current_uid
    result = dict_to_kv(
        {'email': email, 'uid': str(current_uid), 'role': 'user'})
    current_uid += 1
    return result


print(kv_to_dict('foo=bar&baz=qux&zap=zazzle'))
print(profile_for('foo@bar.com'))

key = token_bytes(16)
cipher = AES.new(key, AES.MODE_ECB)


def send_profile(email: str) -> bytes:
    return cipher.encrypt(pkcs_7(profile_for(email).encode()))


def recv_profile(encrypted: bytes) -> dict[str, str]:
    return kv_to_dict(depkcs_7(cipher.decrypt(encrypted)).decode())


admin_block = pkcs_7(b'admin')
encrypted = send_profile('A' * (16 - len(b'email=')) +
                         admin_block.decode() + 'AAAA')
fake_encrypted = encrypted[:-16] + encrypted[16:32]
print(recv_profile(fake_encrypted))

# {'foo': 'bar', 'baz': 'qux', 'zap': 'zazzle'}
# email=foo@bar.com&uid=0&role=user
# {'email': 'AAAAAAAAAAadmin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0bAAAA', 'uid': '1', 'role': 'admin'}

Byte-at-a-time ECB decryption (Harder)

已知随机添加 5 ～ 10 随机字节。我们可以假设额外的随机 padding 长度就是 10，为了检测这种情况已经发生，我们可以在用户输入的 padding 插入一段 b'B' * block_size，检测只有 B 的加密块是否存在，为了检测这种块我们需要先得到它（利用上文提到的 ECB 缺陷），先输入 b'B' * (block_size * 3) 然后检测重复块，重复的就是只有 B 的块。为了使只有 B 的加密块有可能存在（block_size 字节对齐），我们还需要在“B 块”前添加 b'A' * (block_size - 10)。

def hard_encryption_oracle(plaintext: bytes) -> bytes:
    plaintext = pkcs_7(token_bytes(randint(5, 10)) + plaintext + unknown)
    ciphertext = cipher.encrypt(plaintext)
    return ciphertext


def detect_repeat(ecb_enc: bytes) -> int:
    assert len(ecb_enc) >= 32
    for i in range(0, len(ecb_enc) - 16, 16):
        if ecb_enc[i:i+16] == ecb_enc[i+16:i+32]:
            return i


cracked = b''
test = hard_encryption_oracle(b'B' * (16 * 3))
offset = detect_repeat(test)
pure_B_block_enc = test[offset:offset + 16]
for i in range(len(unknown)):
    extra_padding = b'A' * (16 - 10) + b'B' * 16
    padding = b'A' * ((16 - 1) - (i % 16))
    encrypted = bytes()
    while pure_B_block_enc not in encrypted:
        encrypted = hard_encryption_oracle(extra_padding + padding)
    start = i // 16 * 16 + 32
    target_block = encrypted[start:start + 16]
    for j in range(256):
        guess_enc = bytes()
        while pure_B_block_enc not in guess_enc:
            guess_enc = hard_encryption_oracle(
                extra_padding + (padding + cracked)[-15:] + bytes([j]))

        if guess_enc[32:48] == target_block:
            cracked += bytes([j])
            break

print(cracked)
assert cracked == unknown

PKCS#7 padding validation

def depkcs_7(input: bytes) -> bytes:
    padlen = input[-1]
    if 0 < padlen <= 16 or input.endswith(bytes([padlen]) * padlen):
        raise ValueError("Bad padding")
    return input[:-padlen]

CBC bitflipping attacks

You're relying on the fact that in CBC mode, a 1-bit error in a ciphertext block:

• Completely scrambles the block the error occurs in
• Produces the identical 1-bit error(/edit) in the next ciphertext block.

KEY = token_bytes(16)
IV = token_bytes(16)


def aes_cbc_enc(plain: bytes, key: bytes, iv: bytes) -> bytes:
    plain = pkcs_7(plain)
    result = bytes()
    prev_block = iv
    for i in range(0, len(plain), 16):
        block = plain[i:i + 16]
        encrypted = aes_ecb_enc(bytesxor(block, prev_block), key)
        result += encrypted
        prev_block = encrypted
    return result


def quote(data: bytes) -> bytes:
    return data.replace(b';', b'%3B').replace(b'=', b'%3D')


def encrypt_userdata(userdata: bytes) -> bytes:
    prefix = b'comment1=cooking%20MCs;userdata='
    suffix = b';comment2=%20like%20a%20pound%20of%20bacon'

    plaintext = prefix + quote(userdata) + suffix
    return aes_cbc_enc(plaintext, KEY, IV)


def check_admin(ciphertext: bytes) -> bool:
    try:
        plaintext = aes_cbc_dec(ciphertext, KEY, IV)
        return b';admin=true;' in plaintext
    except:
        return False


# len(b'comment1=cooking%20MCs;userdata=') -> 32
# len(b';comment2=%20like%20a%20pound%20of%20bacon') -> 42
ciphertext = encrypt_userdata(b'A' * (16 + (48 - 42)))
mask = bytesxor(b'AAAAAA;comme', b';admin=true;')
payload = bytesxor(ciphertext[32:32 + len(mask)], mask)
fake_ciphertext = ciphertext[:32] + payload + ciphertext[32 + len(mask):]
print(check_admin(fake_ciphertext))

# True

题目一

地址：https://www.coursera.org/learn/crypto/assignment-submission/KZ9js/week-1-programming-assignment-optional/attempt

​ 题目使用同一个流密码密钥加密得到 10 个密文，加密方式是逐字节异或，目标是通过这 10 个密文得到密钥以解出第 11 个密文。

​ 已知消息 M、密钥 K，异或加密的过程是

$$ C=M\oplus K $$

得到密文 C。异或是自反的运算，所以解密与加密过程相同

$$ M=C\oplus K $$

​ 对于同一个密钥 K 加密的两个密文 C_1、C_2，如果将两者异或可以得到

$$ B=C_1\oplus C_2=M_1\oplus K\oplus M_2\oplus K=M_1\oplus M_2 $$

字节流B是两消息逐字节异或结果。

​ 我们首先导入这些密文和加密方法

msg_1 = bytes.fromhex('315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e')
msg_2 = bytes.fromhex('234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f')
msg_3 = bytes.fromhex('32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb')
msg_4 = bytes.fromhex('32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa')
msg_5 = bytes.fromhex('3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070')
msg_6 = bytes.fromhex('32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4')
msg_7 = bytes.fromhex('32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce')
msg_8 = bytes.fromhex('315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3')
msg_9 = bytes.fromhex('271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027')
msg_10 = bytes.fromhex('466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83')

msg_target = bytes.fromhex('32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904')

msgs = [msg_1, msg_2, msg_3, msg_4, msg_5, msg_6, msg_7, msg_8, msg_9, msg_10]

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)])])

根据前文理论，我们先尝试异或 msg_1 和 msg_2，结果是

b'\x12\x10L\x06\x13NW\t\x14\x0f\x10O\x02R\x1b\n\x04B\x02\x0cM\x07\x0b\x18OH\x15T\x1f\x08\x00HN\x1e\x02A\x06\x1d\x06MT\x0b\n\x02\x02\x10\x19E\x10\x16MO:\x00SC\x00NC\x0e\x1e\x1d\nRF\x12\x17\x1b\x01\x17\x00\x1b\x0eEC\x1c\x0c\x1d\x16\nR\r\x11tN\x19\x06\x1a\x11M\x0eU\x17O\x08NT7\x14\x05\x0b\x17CST\x1bH\x07\x0e\x00\x0eM'

我们不使用十六进制格式输出，是因为需要观察其中有一些大写或小写英文字母。根据题目，明文是 ASCII 英语句子，其中大部分符号都是大小写英文字母和空格。我们需要知道一个特殊的规律

$$ ASCII(大/小写字母)\oplus ASCII(空格)=ASCII(小/大写字母) $$

即英文字母的 ASCII 值与空格的 ASCII 值异或得到的 ASCII 值相当于切换原字母的大小写。

​ 根据以上规律，我们十个中的一个密文 C，与其余九个密文逐字节异或，得到九个字节流 B_i，观察其中相同索引 j（位置）的字节 b_k，如果这九个字节几乎都是英文字母，那么我们选取的密文 C 的索引 j 处的字节 C[j] 的明文就大概是空格。此时我们有

$$ C[j]\oplus ASCII(空格)=K[j] $$

从而有可能还原出一个字节的密钥。如果密文足够多足够长，重复上述过程可以还原完整的密钥。

key = [0] * len(msg_7) # `msg_7` is the longest ciphertext.

def isalpha(b):
    return (ord('a') <= b <= ord('z')) or (ord('A') <= b <= ord('Z'))

for i, msg_i in enumerate(msgs):
    may_not_space = [0] * len(msg_i) # Count cases when b_k is not alphabetic.
    for j, msg_j in enumerate(msgs):
        if i != j:
            xored = bytesxor(msg_i, msg_j)
            for k, xb in enumerate(xored):
                if (not isalpha(xb)) and xb != 0:
                    may_not_space[k] += 1
    
    for j, may_not in enumerate(may_not_space):
        if may_not <= 2: # If almost all b_k are alphabetic
            key_byte = msg_i[j] ^ ord(' ')
            if key[j] == 0:
                key[j] = key_byte
                continue
            
            if key[j] != key_byte: # Detect contradiction. Do more checks.
                reliable = True
                for m in msgs:
                    if j >= len(m):
                        continue
                    byte = m[j] ^ key_byte
                    if not isalpha(byte) and byte != ord(' '):
                        reliable = False
                        break
                if reliable:
                    key[j] = key_byte

print(f'Recovered key: {key}')
print(f'Target message: {bytesxor(bytes(key), msg_target)}'')
# for msg in msgs:
#     print(bytesxor(msg, bytes(key)))

题目二

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

1. Convert hex to base64

from base64 import b64encode

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

2. Fixed XOR

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

突发奇想，这里我用《动物森友会》给信件评分的算法来判断哪个结果最正确。（还真没毛病

def get_score(message: str) -> int:
    """*Animal Crossing* message scoring algorithm."""
    t = set("abl abo abr abs acc ach acr act add adm adv aer aff afr aft aga age ago ahe air ali all alm alo alr als alt alw am  ame amo and ang ani ano ans any apa app apr are arg arm arr art asi ask asl ate atm att aud aug aut ave avo awa cak cal cam can cap car cas cat cau cen cer cha che chi cho chi chu cir cit cla cle cli clo coa cof coi col com con coo cop cor cos cou cov cow cre cri cro cry cup cur cus cut bab bac bad bag bal ban bas bat be  bea bec bed bee bef beg beh bel bes bet bey bic big bik bil bir bit bla ble blo blu boa bod bon boo bor bot bou box boy bra bre bri bro bui bur bus but buy by  eac ear eas eat edu eff egg eig eit ele els emp end ene eng enj eno ent equ err esp eur eve exa exc exe exp eye dad dai dam dan dar dat dau day dea dec dee def deg del dem den dep des det dev dic did die dif dig din dir dis div do  doc doe dog dol don doo dou dow doz dra dre dri dro dru dry due dur dus dut gai gam gar gas gat gav gen ger get gir giv gla go  god goi gon goo got gov gra gre gro gua gue gui gun fac fai fal fam far fas fat fea feb fed fee fel few fie fif fig fil fin fir fis fiv fix fla fle fli flo fly fol foo for fou fra fre fri fro fru ful fun fut i   ice ide if  ima imm imp in  inc ind inf ins int inv iro is  isl it  its hab had hai hal han hap har has hat hav he  hea hei hel her hi  hid hig hil him hir his hit hol hom hon hop hor hos hot hou how hum hun hur hus kee kep key kic kil kin kit kne kni kno kab kad kai kak kan kar kas kat kau kaw kay kaz kea ked kef keg ken kes ket kev kib kie kif kig kik kim kin kis kit kiv koc kon koo kos kot kou kov kow kun kyi kac kad kag kai kaj kak kan kap kar kat kay ke  kea ked kee kem ken kes ket kid kig kil kin kis kod kom kon koo kor kos kot kou kov kuc kum kus ky  kys kam kar kat kea kec kee kei kev kew kex kic kig kin ko  kob koi kon koo kor kos kot kov kow kum kbj k'c kct kf  kff kft kh  kil kka kld kn  knc kne knl kpe kpi kpp kr  kra krd kth kur kut kve kwn jan jap job joi jud jul jum jun jus qua que qui pac pag pai pap par pas pat pay pea pen peo per pho pic pie pin pip pla ple poc poi pol poo pop pos pot pou pow pra pre pri pro pub pul pup pur pus put sad saf sai sal sam san sat sav saw say sce sch sci sco sea sec see sel sen sep ser set sev sex sha she shi sho shu sic sid sig sil sim sin sis sit six siz ski sky sle sli slo sma sme smi smo sno so  soa soc sof soi sol som son soo sor sou spa spe spi spo spr squ sta ste sti sto str stu sty sub suc sud suf sug sum sun sup sur swa swe swi swu sys rac rad rai ran rap rat rea rec red ref reg rel rem rep req res ret ric rid rig rin ris riv roa roc rod rol roo ros rou row rul run rus una unc und uni unl unt up  upo us  use usu tab tak tal tas tau tax tea tee tel tem ten ter tes tha the thi tho thr thu tic tie til tim tir tit to  tod tog tol tom ton too top tor tot tou tow tra tre tri tro tru try tue tur tv  twe twi two tyi typ val var veg ver vie vil vis voi vol vot vai vak val van var vas vat vav vay ve  vea ved vee vei vel ven ver ves vet vha vhe vhi vho vhy vid vif vil vin vir vis vit viv vok vom von voo vor vou vri vro vma yar yea yel yen yes yet you zer".split())
    s = 0
    if message and message[-1] in '.?!':
        s += 20
    for i, c in enumerate(message):
        if c in '.?!':
            for j in range(i+1, min(i+4, len(message))):
                if message[j].isupper():
                    s += 10
                    break
                elif message[j].isalpha():
                    s -= 10
                    break
    s += sum(3 for w in message.split() if len(cw :=
             ''.join(c for c in w if c.isalpha()).lower()) >= 3 and cw[:3] in t)
    for c in message:
        if not c.isspace():
            s += 20 if c.isupper() else -10
            break
    for i in range(len(message)-2):
        if message[i].isalpha() and message[i] == message[i+1] == message[i+2]:
            s -= 50
            break
    sp, nsp = message.count(' '), len(message) - message.count(' ')
    s += -20 if nsp == 0 or (sp * 100 // nsp if nsp else 0) < 20 else 20
    if len(message) > 75:
        c = 0
        for ch in message:
            c = 0 if ch in '.?!' else c + 1
            if c == 75:
                s -= 150
                break
    s -= sum(20 for i in range(0, len(message), 32)
             if ' ' not in message[i:i+32] and len(message[i:i+32]) == 32)
    return s


cipher = bytes.fromhex(
    '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736')
results = list()
for c in range(256):
    try:
        res = bytesxor((chr(c) * len(cipher)).encode(), cipher).decode()
        results.append((res, get_score(res)))
    except UnicodeDecodeError:
        pass

best = sorted(results, key=lambda x: x[1])[-1][0]
print(best)

# Cooking MC's like a pound of bacon

4. Detect single-character XOR

with open('4.txt', 'r') as file:
    ciphers = file.readlines()

for original_cipher in ciphers:
    results = list()
    cipher = bytes.fromhex(original_cipher)
    for c in range(256):
        try:
            res = bytesxor((chr(c) * len(cipher)).encode(), cipher).decode()
            results.append((res, get_score(res)))
        except UnicodeDecodeError:
            pass
    if len(results) == 0:
        continue

    best = sorted(results, key=lambda x: x[1])[-1]
    if best[1] > 40:
        print(f'{original_cipher.strip()} -> {best[0]}')

# 7b5a4215415d544115415d5015455447414c155c46155f4058455c5b523f -> Now that the party is jumping

5. Implement repeating-key XOR

def repeating_key_xor_to_hex(msg: bytes, key: bytes) -> str:
    result_chars = []
    keylen = len(key)
    for i, b in enumerate(msg):
        result_chars.append(b ^ key[i % keylen])
    return bytes(result_chars).hex()

print(repeating_key_xor_to_hex(b"Burning 'em, if you ain't quick and nimble", b'ICE'))
print(repeating_key_xor_to_hex(b'I go crazy when I hear a cymbal', b'ICE'))

6. Break repeating-key XOR

一开始没有还原正确，检查了一下发现是 # 扰乱了解密评分。考虑到英文句子里极少有 #，所以遇到就扣 5 分。

from base64 import b64decode


def get_score(message: str):
    score = 0
    for c in message:
        if c.islower():
            score += 3
        if c.isupper():
            score += 1
        if c == ' ':
            score += 1
        if c == '#':
            score -= 5
    return score


def get_key(cipher: bytes) -> int:
    results = list()
    for c in range(256):
        try:
            res = bytesxor((chr(c) * len(cipher)).encode(), cipher).decode()
            results.append((c, get_score(res)))
        except UnicodeDecodeError:
            pass
    return sorted(results, key=lambda x: x[1])[-1][0]


def repeating_key_xor(msg: bytes, key: bytes) -> bytes:
    result_chars = []
    keylen = len(key)
    for i, b in enumerate(msg):
        result_chars.append(b ^ key[i % keylen])
    return bytes(result_chars)


def normalized_average_hd(data: bytes, unit_len: int) -> float:
    chunks = [data[i:i + unit_len] for i in range(0, len(data), unit_len)]
    num_chunks = len(chunks)
    total_hd = 0
    count = 0
    for i in range(num_chunks):
        for j in range(i + 1, num_chunks):
            if len(chunks[i]) == unit_len and len(chunks[j]) == unit_len:
                total_hd += sum((byte1 ^ byte2).bit_count()
                                for byte1, byte2 in zip(chunks[i], chunks[j]))
                count += 1
    return total_hd / (count * unit_len)


with open('6.txt', 'r') as file:
    cipher = b64decode(file.read())

results = list()
for l in range(2, 41):
    norm_hd = normalized_average_hd(cipher, l)
    results.append((l, norm_hd))
keylens = sorted(results, key=lambda x: x[1])

for k in range(1):
    keylen = keylens[k][0]
    print(f"Guessed key length: {keylen}")

    key_bytes = []
    for i in range(keylen):
        block = bytes([cipher[j * keylen + i]
                      for j in range(len(cipher) // keylen)])
        key_bytes.append(get_key(block))

    key = bytes(key_bytes)
    # print(repeating_key_xor(cipher, key).decode())
    print(f'Key: {key}')

# Guessed key length: 29
# Key: b'Terminator X: Bring the noise'

7. AES in ECB mode

import base64
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms

key = b"YELLOW SUBMARINE"
with open('7.txt', 'r') as f:
    encrypted_b64 = f.read()
encrypted_data = base64.b64decode(encrypted_b64)
cipher = Cipher(algorithms.AES(key)) # Default to ECB mode
decryptor = cipher.decryptor()
decrypted_data = decryptor.update(encrypted_data) + decryptor.finalize()

print(decrypted_data.decode())

8. Detect AES in ECB mode

print(max(open('8.txt').read().splitlines(), key=lambda x: len(c:=[x[i:i+32] for i in range(0, len(x), 32)]) - len(set(c))))