Cryptopals解题报告(一)

发表于 | 分类于 | | 热度: ℃
字数统计: 3,047 | 阅读时长 ≈ 13

0x00 前言

Cryptopals这个网站有许多较为有趣的密码学问题,此系列用于记录一些密码学问题的解决分析过程.

题目链接地址: Cryptopals-Set1

0x01 储备函数

Set1部分功能的实现需要依赖一些储备函数,进行字符串、字节数组与十六进制数之间的转换.相关代码如下: 

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
# 十六进制字符串转化为字节数组
def hex_to_bytelist(hexString):
	return [ord(c) for c in hexString.decode('hex')]

# 字节数组转化为十六进制字符串
def bytelist_to_hex(bytelist):
	return ''.join(hex(x)[2:] if x > 15 else '0' + hex(x)[2:] for x in bytelist)

# 字符串转化为十六进制字符串
def str_to_hex(string):
	return string.encode('hex')

# 十六进制字符串转化为字符串
def hex_to_str(hexString):
	return hexString.decode('hex')

# 字节数组转化为字符串
def bytelist_to_str(bytelist):
	return hex_to_str(bytelist_to_hex(bytelist))

# 字符串转化为字节数组
def str_to_bytelist(string):
	return hex_to_bytelist(str_to_hex(string))

# 字节数组异或
def xor(b1, b2):
	result = []
	for i in range(len(b1)):
		result.append(b1[i]^b2[i])
	return result

# 将字符串string以n字节长度的大小进行切分,切分后的每块合为一个列表
def chunks(string, n):
	for i in range(0, len(string), n):
		yield string[i:i+n]

0x02 Challenge1 Convert hex to base64

题目要求

实现一个函数,将十六进制字符串转化为base64编码的字符串.

Python编解码

计算机中的文本数据以Unicode万国码的形式存储.在写入与输出过程中会经历将字符串解码为Unicode后存储在本地以及将本地Unicode字符串进行指定类型的编码这两个过程.

编码的过程是将Unicode字符按照编码规则(如utf-8)编成字节序列.但是在使用print语句打印编码后文本是乱码或对应中文,而不是字节序列.这是因为print语句默认进行了隐式编码,为的是让人类看见友好的字符数据.对于背后的十六进制数,需要调用魔术方法__repr__(). 解码过程是将字节序列按照编码规则(如utf-8)解释成Unicode形式.

Python2/3中的str与bytes

Python3中,文本字符串类型(Unicode编码数据)被命名为str,字节字符串类型被命名为bytes.一般来说实例化一个字符串会得到一个str对象.所以Python3默认为Unicode,如果需要得到bytes类型数据,需要在文本之前加上前缀b或者进行encode. 

1
2
3
4
5
6
7
8
>>> a = '测试'
>>> type(a)
<class 'str'>
>>> a.encode('GBK')
b'\xb2\xe2\xca\xd4'
>>> a = b'hello'
>>> a.__repr__()
"b'hello'"

显然,str对象拥有encode方法,而bytes对象拥有decode方法.

Python2中情况就大相径庭.Python3中的str对象在Python2中为unicode,而bytes对象在Python2中叫做str.如果想要得到一个文本字符串,则需要在字符串之前加上前缀u或者进行decode.值得注意的是,str对象的encode方法与unicode对象的decode方法是为报错而生的,所以尽量不要使用该类方法.

题目分析

首先将十六进制字符串使用decode方法解码为unicode编码,然后再将字符串编码为base64.代码如下: 

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*-

import base64

plain = '49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d'

print plain.decode('hex')
print base64.b64encode(plain.decode('hex'))

0x03 Challenge2 Fixed XOR

题目要求

实现一个函数,输入为两个等长的字符串,输出为这两个字符串的异或结果.

题目分析

储备函数中已经实现了两个字节数组异或的函数.若要实现两个等长字符串的异或,先使用储备函数中的str_to_bytelist()方法将字符串转化为字节数组,然后调用xor方法进行异或操作,最后再调用bytelist_to_str()方法将字节数组转化为十六进制字符串.代码如下:

1
2
3
4
5
6
7
8
9
10
11
# -*- coding:utf -*-
from Set0 import *
def xor(b1, b2):
	result = []
	for i in range(len(b1)):
		result.append(b1[i]^b2[i])
	return result
if __name__ == '__main__':
	s1 = hex_to_bytelist('1c0111001f010100061a024b53535009181c')
	s2 = hex_to_bytelist('686974207468652062756c6c277320657965')
	print bytelist_to_hex(xor(s1,s2))

0x04 Challenge3 Single-byte XOR cipher

题目要求

给定一个十六进制字符串,该字符串是明文与一个单字符key进行异或加密之后得到的结果.现要求在已知cipher_hex_string的情况下还原plaintext.

题目分析

该题目使用的核心思想为爆破.已知密文是明文与同一单字符进行异或生成,那么我们可以循环遍历所有可能的单字符,与密文进行异或从而得到所有可能的明文.根据不同英文字母出现的统计频率,可以计算所有明文对应的频率分数.频率分数越高则该明文为语义通顺的英文文本可能性越高.取最高频率分数对应的结果为明文,代码如下: 

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
# -*- coding:utf-8 -*-
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}

def get_score(string):  # 计算字符串的频率得分
	score = 0
	for ch in string:
		ch = ch.lower()
		if ch in CHARACTER_FREQ:
			score += CHARACTER_FREQ[ch]
	return score


def singlebyte_xor(key, string): # 进行单字符异或解密
	result = ''
	for i in string:
		ch = chr(key^ord(i))
		result += ch
	return result

def ergodic_found(string): # 对最后的明文结果进行分析
	candidate = []
	for key in range(256):
		plaintext = singlebyte_xor(key, string)
		score = get_score(plaintext)
		result = {'key': key, 'plaintext': plaintext, 'score': score}
		candidate.append(result)
	# 获取最高的得分对应的明文作为最后的结果
	return sorted(candidate, key = lambda c:c['score'])[-1]

if __name__ == '__main__':
	ciphertext = '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736'
	print ergodic_found(ciphertext.decode('hex'))

运行结果如下图:

1.png-33.8kB

0x05 Challenge4 Detect Single-character XOR

题目要求

给出challenge4.txt文件,文件中的一个字符串是由单字符异或方法加密的十六进制编码串,找到并解密这个字符串.

题目分析

结合Challenge3中的函数,对所给文件的每个字符串调用ergodic_found()方法进行遍历和评估,对于文件中每个字符串返回的所有得分最高对象,选取其中分数最高的作为最终结果,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
from challenge3 import *
if __name__ == '__main__':
	f = open('challenge4.txt', 'r')
	hexStringSet = f.readlines()
	candidate = []
	for line in hexStringSet:
		line = line.strip()
		string = line.decode('hex')
		candidate.append(ergodic_found(string))

	print sorted(candidate, key = lambda c:c['score'])[-1]['plaintext']

运行结果如下图:

2.png-28.7kB

0x06 Challenge5 Implement repeating-key XOR

题目要求

实现一个函数,给定待加密的字符串和密钥,该函数通过使用重复密钥异或的方法加密一段英文文本,返回加密后的结果.

题目分析

将待加密的字符串按照keysize的大小进行分块,将每块分别与密钥key进行逐字符异或加密,最后将每块的加密结果合并到一起.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
from Set0 import *
def repeatingkey_xor(key, string):
	res = ''
	for i in xrange(0, len(string), len(key)):
		res += bytelist_to_hex(xor(str_to_bytelist(string[i:i+len(key)]), str_to_bytelist(key)))
	return res
	
if __name__ == '__main__':
	res = ''
	plaintext = 'Burning \'em, if you ain\'t quick and nimble I go crazy when I hear a cymbal'
	key = 'ICE'
	print repeatingkey_xor(key, plaintext)

0x07 Challenge6 Break repeating-key XOR

题目要求

该挑战中提供challenge6.txt文件,文件使用重复密钥异或方法加密后,再经过bas64编码后得到的文本,我们需要找到密钥,对其进行解密.

题目分析

对密文的攻击采用了流密码加密密钥重用对应的攻击方法.大体破解方法如下:首先从2到40猜测密钥长度,对于每个KEYSIZE,求得解密块两两之间的汉明距离,对KEYSIZE取平均值.选取2-3个最小汉明距离对应的KEYSIZE作为最终的密钥长度.获得密钥长度后,按照密钥长度对密文进行分块,即将使用同一单字符密钥加密后的密文分到一组.使用破解单字符异或的方法来逐字符破解密钥.对不同KEYSIZE解密后的明文进行评估,选取得分最高的一组作为最终的明文.代码如下: 

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
from Set0 import *
from Challenge3 import *
from Challenge4 import *
import base64
import itertools
def hamming_distance(s1, s2):
        dis = 0
        for i in range(min(len(s1), len(s2))):
            b = bin(ord(s1[i]) ^ ord(s2[i]))
            dis += b.count('1')
        return dis

def guess_keysize(string):
    keys = []
    for keysize in range(2, 40):
        blocks = []
        count = 0
        dis = 0
        for i in range(0, len(string), keysize):
            count += 1
            blocks.append(string[i:i+keysize])
            if count == 4:
                break
        #选取四个块，两两组合求汉明距离
        pairs = itertools.combinations(blocks, 2)
        for (x, y) in pairs:
            dis += hamming_distance(x, y)
        ndis = dis / keysize
        key = {'keysize': keysize, 'distance': ndis}
        keys.append(key)
    return sorted(keys, key=lambda c:c['distance'])[0:3]

def guess_key(keysize, string):
    key = ''
    for i in range(keysize):
        now_str = ''
        #获取每个块相同位置的字符
        for index, ch in enumerate(string):
            if index % keysize == i:
                now_str += ch
        key += chr(ergodic_found(now_str)['key'])
    return key

def break_repeatingkey_xor(string):
    keysizes = guess_keysize(string)
    candidate = []
    plains = []
    for keysize in keysizes:
        key = guess_key(keysize['keysize'], string)
        #二元组：重复密钥异或解密明文，对应密钥key
        plains.append((hex_to_str(repeatingkey_xor(string, key)), key))
    return sorted(plains, key=lambda c:get_score(c[0]))[-1]

if __name__ == '__main__':
    f = open('challenge6.txt', 'r')
    s = f.read()
    string=base64.b64decode(s)
    res=break_repeatingkey_xor(string)
    print res[0]
    print 'key: \n'+res[1]

解密结果如下图:

3.png-250.7kB

0x08 Challenge7 AES in ECB mode

题目要求

该挑战提供了一个文件challenge7.txt,文件的内容是经过AES-128 ECB模式加密后的base64编码的文本,已知密钥key,进行解密.

题目分析

直接使用from Crypto.Cipher import AES调用AES模块,构造AES-ECB生成器,调用其encrypt和decrypt方法进行加解密.解密后明文末尾包含填充部分,可以遵循PKCS7填充标准进行填充内容剔除.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Cipher import AES
import base64
def aes_ecb_encrypt(key, plaintext):
	crypto = AES.new(key,AES.MODE_ECB)
	ciphertext = crypto.encrypt(plaintext)
	return ciphertext
def aes_ecb_decrypt(key, ciphertext):
	crypto = AES.new(key,AES.MODE_ECB)
	plaintext = crypto.decrypt(ciphertext)
	return plaintext
if __name__ == '__main__':
	f = open("challenge7.txt", "r")
	ciphertext = f.read()
	ciphertext = base64.b64decode(ciphertext)
	key = "YELLOW SUBMARINE"
	plaintext = aes_ecb_decrypt(key, ciphertext)
	print plaintext

0x09 Challenge8 Detect AES in ECB mode

题目要求

该挑战提供一个文件,文件内容是十六进制编码的若干加密字符串,其中一个字符串是通过AES-ECB模式加密的,key未知.我们需要通过密文找到这个AES ECB加密的字符串.

题目分析

由于ECB模式加密是静态和确定的,相同的16字节明文块总是生成相同16字节密文块.所以我们可以通过查找加密字符串中是否有相同的密文块,来判断是否为ECB模式.如果存在,则为ECB模式.此方法只可以用于判断所给密文字节数较多的情况,即在基数较大情况下出现相同的16字节明文块的统计概率较高.对于所给密文字节数较少的情况,不存在对应统计规律,无法使用该方法判断.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding:utf-8 -*-

# 将字符串string以n字节长度的大小进行切分,切分后的每块合为一个列表
def chunks(string, n):
	for i in xrange(0, len(string), n):
		yield string[i:i+n]

def detect_ecb(ciphertext):
	blocks = [b for b in chunks(ciphertext, 16)]
	detects = []
	for b in blocks:
		if blocks.count(b) > 1:
			detects.append(b)
	if detects:
		return 'ECB MODE detected!'
	else:
		return ''
		
if __name__ == "__main__":
	f = open("challenge8.txt", "r")
	i = 1
	for line in f:
		print i, ':', detect_ecb(line)
		i += 1
请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多