从零开始的密码学学习之旅(一)

题目链接 https://cryptopals.com

以及大佬的wp https://cedricvanrompay.gitlab.io/cryptopals/

菜鸡日常挖坑,随缘填坑

运行环境:linux + python3.7

challenge 1

题目描述:convert hex to base64

这个比较简单,就是两个库的使用,直接上代码了

1
2
3
4
5
6
7
8
import binascii
import base64

i = ''
o = ''
result = base64.b64encode(binascii.unhexlify(i))
if result==o:
print('ok')

challenge 2

题目描述:Write a function that takes two equal-length buffers and produces their XOR combination.

异或两个长度相等的字符串,这个是接下来几个的基础,主要是对byte的操作

代码如下

1
2
3
4
5
6
7
8
9
import binascii
def bxor(a, b):
return bytes([ x^y for (x,y) in zip(a, b)])

a = binascii.unhexlify('1c0111001f010100061a024b53535009181c')
b = binascii.unhexlify('686974207468652062756c6c277320657965')
c = binascii.unhexlify('746865206b696420646f6e277420706c6179')
if bxor(a,b)==c:
print('ok')

challenge 3

题目描述:has been XOR’d against a single character. Find the key, decrypt the message.

单字符异或,可以直接爆破得到明文

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
import binascii
c = '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736'

def bxor(a, b):
return bytes([ x^y for (x,y) in zip(a, b)])

# 判断是否是可打印字符,此处只判断了大小写字母和空格单引号
def check_printable(cipher):
ascii_text_chars = list(range(65, 90)) + list(range(97, 122)) + [32] +[39]
# 判断判断当前字符是否在list里,返回的是True或False的list,求和之后可以当作是正确的概率
letters = sum([ x in ascii_text_chars for x in cipher])
p = letters/len(cipher)
# 忽略一些误差,所以让p>0.9
if p > 0.9:
return True
return False

def attack_single_byte_xor(cipher):
# 直接循环爆破
for i in range(127):
# 将数字转成bytes并对齐长度
tmp_key = i.to_bytes(1,byteorder='big')*len(cipher)
plaintext = bxor(tmp_key,binascii.unhexlify(cipher))
if check_printable(plaintext):
print(plaintext)

attack_single_byte_xor(c)

challenge 4

题目描述:One of the 60-character strings in this file has been encrypted by single-character XOR.

和上一题一样,只不过多了个逐行读文件的操作,代码如下

1
2
3
4
5
6
7
n = 0
for line in open("s1-4.txt"):
n += 1
c = line.strip()
if attack_single_byte_xor(c):
print(n)
break

challenge 5

题目描述:Implement repeating-key XOR

给出明文和key,将key和明文对齐,异或得到密文

1
2
3
4
5
6
7
8
9
10
11
12
import binascii

def bxor(a, b):
return bytes([ x^y for (x,y) in zip(a, b)])

plaintext = b'''Burning 'em, if you ain't quick and nimble\nI go crazy when I hear a cymbal'''
key = b"ICE"
keystream = key*(len(plaintext)//len(key)+1) # 按照明文长度对齐密钥
ciphertext = bxor(plaintext,keystream)
o = '0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f'
if ciphertext == binascii.unhexlify(o):
print('ok')

challenge 6

题目描述:There’s a file here. It’s been base64’d after being encrypted with repeating-key XOR. Decrypt it.

根据题目描述,要求很简单,给了密文和加密方式异或,求明文,但是不知道密钥长度,直接爆破显然不可以

这里引入了一个概念Hamming distance,表示两个等长字符串在对应位置上不同字符的数目,通过计算最小Hamming distance,就可以确定密钥长度,然后根据密钥长度将密文分组,每一组可以直接用上边写完的单字节异或爆破的函数,最后再将结果组合到一起即可

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import base64
import binascii

# 上边写过的异或,直接拿来用
def bxor(a, b):
return bytes([ x^y for (x,y) in zip(a, b)])

# 判断是否是可打印字符,这里根据英语的规则,选择了大小写字母和,'?!- 换行等
def check_printable(ciphertext):
ascii_text_chars = list(range(65, 90)) + list(range(97, 122)) + [32] + [33] + [39] +list(range(44, 57)) + [63] + [10]
letters = sum([ x in ascii_text_chars for x in ciphertext])
p = letters/len(ciphertext)
# 这里选择调高p,因为可能会出现多个结果,理论上应该选择最大的,这里偷懒直接选0.95了
if p > 0.95:
return True
return False

# 先将两个字符串异或之后计算Hamming distance
def get_distance(a,b):
return sum(bin(byte).count('1') for byte in bxor(a,b))

# 之前写好的爆破单字节异或的函数,但是要改一下返回值
def attack_single_byte_xor(cipher):
p = None
for i in range(127):
tmp_key = i.to_bytes(1,byteorder='big')*len(cipher)
plaintext = bxor(tmp_key,cipher)
if check_printable(plaintext):
p = {'key':i.to_bytes(1,byteorder='big'),'message':plaintext}
return p

# 计算每个密钥长度的得分
def score_vigenere_key_size(candidate_key_size, ciphertext):
slice_size = 2*candidate_key_size # 根据题目,分片长度选择候选密钥长度的二倍
nb_measurements = len(ciphertext) // slice_size - 1 # 将密文分片
score = 0

# 计算每个密钥长度的得分,越小说明越有可能是密钥长度
# 循环累计每一个分片的距离,最后再标准化
for i in range(nb_measurements):
s = slice_size
k = candidate_key_size
slice_1 = slice(i*s, i*s + k)
slice_2 = slice(i*s + k, i*s + 2*k)
score += get_distance(ciphertext[slice_1], ciphertext[slice_2])

# 标准化score
score /= candidate_key_size
score /= nb_measurements
return score

# 寻找最可能的密钥长度
def find_key_length(ciphertext,min_length=2,max_length=30):
key = lambda x: score_vigenere_key_size(x,ciphertext)
return min(range(min_length,max_length),key=key) # 以key的方式求最小值

def attack_repeating_key_xor(ciphertext):
key_size = find_key_length(ciphertext)
key = bytes()
message_part = list()
# 循环爆破单个
for i in range(key_size):
part = attack_single_byte_xor(bytes(ciphertext[i::key_size])) # 步长为keysize
key += part["key"]
message_part.append(part["message"])
message = bytes()
# 按照位置循环,将明文正确排列
for i in range(max(map(len, message_part))):
message += bytes([part[i] for part in message_part if len(part)>=i+1])
return {”key_size":key_size,"key":key,"message":message}


f = open('s1-6.txt','r')
cipher = f.read()
tmp = base64.b64decode(cipher)
print(attack_repeating_key_xor(tmp))

challenge 7

题目描述:The Base64-encoded content in this file has been encrypted via AES-128 in ECB mode under the key. Decrypt it.

给了密文的加密方式和key,可以直接使用python的解密库来进行操作,直接按照官方文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.backends import default_backend
import base64
backend = default_backend()

def decrypt_aes_128_ecb(ciphertxt, key):
cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=backend)
decryptor = cipher.decryptor()
decrypted_data = decryptor.update(ciphertxt) + decryptor.finalize()
message = decrypted_data
return message

f = open("s1-7.txt","r")
data = f.read()
print(decrypt_aes_128_ecb(ciphertxt = base64.b64decode(data),key=b"YELLOW SUBMARINE").decode())

challenge 8

题目描述:In this file are a bunch of hex-encoded ciphertexts. One of them has been encrypted with ECB. Detect it.

给了一堆密文,其中一个是用ECB模式加密的,找到密文,这道题主要想考的是ECB模式的特点是会保留明文的重复,可以根据这一特点来找到明文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import binascii

with open('s1-8.txt') as f:
ctxts = [binascii.unhexlify(line.strip()) for line in f]

def has_repeated_blocks(ctxt, blocksize=16):
if len(ctxt) % blocksize != 0:
raise Exception('ciphertext length is not a multiple of block size')
else:
num_blocks = len(ctxt) // blocksize

# 将密文分块
blocks = [ctxt[i*blocksize:(i+1)*blocksize] for i in range(num_blocks)]
# 判断是否有重复
if len(set(blocks)) != num_blocks:
return True
else:
return False

hits = [ctxt for ctxt in ctxts if has_repeated_blocks(ctxt)]
print(hits)
0%