密码学实验一

密码学实验一做完了，写篇博客总结一下。

题目描述

1.让我们看看流密码多次使用时出了什么问题。以下是十一个十六进制编码的密文，这些密文是使用流密文加密所有十一个具有相同流密文密钥的明文的结果。目标是解密最后的密文。提示：对密文进行异或运算，并考虑将空格与[a-zA-Z]中的字符进行异或运算时会发生什么。
2.编写一个程序破解一个类似于维吉尼亚密码加密的字符串，与维吉尼亚不同的是该加密方案使用的是字节异或而不是模26。
3.加密挑战赛
3.1将十六进制转换为base64
3.2两个十六进制表示的字符串的异或
3.3解密经过一个字符异或加密后的数据，采用累计得分的方式
3.4 3.3的加强版，在n行的文件中找出经过一个字符异或加密的一行，并给出明文
3.5 使用“ICE”三个字母采用重复的密钥异或的方式加密两个字符串
3.6解密通过重复密钥异或加密后并且经过base64处理的数据
4.通过社会工程学，猜测用户口令，破解SHA1处理后的字符串

过程

1.流密码多次使用

[A-Z]用[0x41-0x5a]表示。相应地，[a-z]用[0x61-0x7a]表示。而空格，则用0x20表示，也就是表格中的SP。空格这个表示带来了一个很巧妙的转换：如果一个大写字母与空格与或，那么结果为一个对应的小写字母；如果一个小写字母与空格与或，那么结果为一个对应的大写字母！举两个例子： a ^ SP = 01100001 ^ 00100000 = 01000001 = A A ^ SP = a ^ SP ^ SP = a 同时，解密过程中也用到了xor的另一个性质：对于一个数，连续与或两次任意相同的数，其结果与原数相同。用公式表示就是，对于任意的x和y： x ^ y ^ y = x 根据提示，每一个ciphertext都是用相同的streamcipher加密的。因此，假设plaintext分别为m1、m2，那么c1 = m1 ^ k， c2 = m2 ^ k，于是c1 ^ c2= m1 ^ k ^ m2 ^ k = m1 ^ m2。这样我们就把k消去，只剩下了m1和m2。 那么，我们的解法就很显然了：随便找任意给定的m_i，m_j相与或，如果发现了有意义的英文字母，那么对应位上很可能一个是空格，另一个是英文字母

代码运行结果如下图：

2.维吉尼亚密码破解

首先我们要确定密钥的长度，从0-255循环遍历，查看哪个长度对应的可见字符数量最多。 从图中可以看出，当keysize=7的时候有解的可能性最大 :

于是我们可以猜测密钥长度就是7，接下来我们猜测具体的密钥，从0-255循环与密文异或，如果是大小写字母或者空格逗号之类的，那么就计数+1，找到可以解密所有的字符的口令后返回：

最后发现密钥就是：[[186], [31], [145], [178], [83], [205], [62]] 然后用密钥解密原文就得到了明文：

3.加密挑战赛

3.1将16进制字符串转化为base64

代码很简单，调用相关函数即可：

import binascii
import base64

def hexToBase64(s):
    decoded = binascii.unhexlify(s)
    return base64.b64encode(decoded).decode('ascii')

x = '49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d'
expectedY = 'SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t'
y = hexToBase64(x)
print(y)
print(expectedY)

结果如下：

SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t
SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t

3.2十六进制表示的字符串的异或

先将十六进制字符串转换成字符串，然后调用strxor函数即可：

import binascii

from Crypto.Util.strxor import strxor

encodedS = '1c0111001f010100061a024b53535009181c'
encodedT = '686974207468652062756c6c277320657965'
encodedExpectedU = '746865206b696420646f6e277420706c6179'

s = binascii.unhexlify(encodedS)
t = binascii.unhexlify(encodedT)
expectedU = binascii.unhexlify(encodedExpectedU)

u = strxor(s, t)
print(u)
print(expectedU)

运行结果：

b”the kid don’t play”
b”the kid don’t play”

3.3解密经过一个字符异或加密后的数据，采用累计得分的方式

首先查找一下英文词频，以便于后面的赋值：

freqs = {
    '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 scoring(s):
    score = 0
    for i in s:
        c = chr(i).lower()
        if c in freqs:
            score += freqs[c]
    return score

剩下的就是从0-255试密钥了，将得分值最高的密钥返回，认定为最有可能的密钥

def breakSingleByteXOR(s):
    def key(p):
        #print(p)
        return scoring(p[1])
    return max([(i, strxor_c(s, i)) for i in range(0, 256)], key=key)

if __name__ == '__main__':
    encodedS = '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736'
    s = binascii.unhexlify(encodedS)
    print(breakSingleByteXOR(s))

最后的解密结果就是：

(88, b”Cooking MC’s like a pound of bacon”)

密钥就是88，明文是 Cooking MC’s like a pound of bacon

3.4 3.3的加强版，在文件中找出经过一个字符异或加密的一行，并给出明文

这题和上面那题一样，只不过从一行变成n行而已，我们只需将上面那题循环n次即可，找出n行中得分最高的一行和对应的密钥即可：

import binascii
import challenge3

def decodeLines(filename):
    f = open(filename, 'r')
    for line in f:
        if line[-1] == '\n':
            line = line[:-1]
        s = binascii.unhexlify(line)
        yield s

def findSingleByteXOR(lines):
    brokenLines = [challenge3.breakSingleByteXOR(l)[1] for l in lines]
    def scoring(i):
        return challenge3.scoring(brokenLines[i])
    maxI = max(range(len(brokenLines)), key=scoring)
    return (maxI+1, brokenLines[maxI])

if __name__ == '__main__':
    print(findSingleByteXOR(decodeLines('challenge4.txt')))

结果如下：

(171, b’Now that the party is jumping\n’)

第171行是经过单字符加密的口令，解密结果就是Now that the party is jumping

3.5使用“ICE”三个字母采用重复的密钥异或的方式加密两个字符串

无非是密钥个数从一变为三了，取余3字节异或即可：

import binascii

def encodeRepeatingKeyXor(s, key):
    return bytes([s[i] ^ key[i % len(key)] for i in range(len(s))])

x = b'''Burning 'em, if you ain't quick and nimble
I go crazy when I hear a cymbal'''
key = b'ICE'

if __name__ == '__main__':
    y = encodeRepeatingKeyXor(x, key)
    encodedY = binascii.hexlify(y).decode('ascii')
    print(encodedY)

结果如下：

0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f

3.6解密通过重复密钥异或加密后并且经过base64处理的数据

步骤题目中已经给出，按照题目给的步骤一步一步来做即可
首先确定 KEYSIZE 也就是密钥长度，题目中说的是密钥长度在2-40之间，这里提一个汉明距离的概念，就是不同比特的数量。

def getHammingDistance(x, y):
    return sum([bin(x[i] ^ y[i]).count('1') for i in range(len(x))])

#检测汉明距离计算函数是否正确
x = b'this is a test'
y = b'wokka wokka!!!'
expectedD = 37
d = getHammingDistance(x, y)
if d != expectedD:
    raise Exception(encodedD + ' != ' + encodedExpectedD)

先根据汉明距离，计算出汉明距离最小的keysize值

def normalizedEditDistance(x, k):
    blocks = [x[i:i+k] for i in range(0, len(x), k)][0:4]
    pairs = list(itertools.combinations(blocks, 2))
    scores = [getHammingDistance(p[0], p[1])/float(k) for p in pairs][0:6]
    return sum(scores) / len(scores)

k = min(range(2, 41), key=lambda k: normalizedEditDistance(x, k))

最终k值就是keysize
然后，取得keysize后，按照keysize对密文进行分块，然后对密文的每一个比特采用第三题的方法，猜出得分值最高的就是密钥，共需要keysize次循环即可找出相应的全部口令，函数如下：

def breakRepeatingKeyXor(x, k):
    blocks = [x[i:i+k] for i in range(0, len(x), k)]
    transposedBlocks = list(itertools.zip_longest(*blocks, fillvalue=0))
    key = [challenge3.breakSingleByteXOR(bytes(x))[0] for x in transposedBlocks]
    return bytes(key)

key = breakRepeatingKeyXor(x, k)
y = challenge5.encodeRepeatingKeyXor(x, key)
print(key)
#write the result to file to look
result = y.decode()
open('Dechallenge6.txt', 'w').write(result)

最后运行的结果为：
key = erminator X: Bring the noise
明文写入了文件，部分如下图：

4.通过社会工程学，猜测用户口令，破解SHA1处理后的字符串

题目给了我们一个键盘使用痕迹和数据库存储的sha1值，我们需要猜测出明文：

我们根据键盘使用确定使用的字符，然后循环计算sha1值与题目给的sha1值比对即可：

#coding:utf-8
import re
from Crypto.Hash import SHA
import hashlib
import itertools
hash1="67ae1a64661ac8b4494666f58c4822408dd0a3e4"
str1="QqWw%58(=0Ii*+nN"
str2=[['Q', 'q'],[ 'W', 'w'],[ '%', '5'], ['8', '('],[ '=', '0'], ['I', 'i'], ['*', '+'], ['n', 'N']]
def sha_encrypt(str):
    sha = hashlib.sha1(str)
    encrypts = sha.hexdigest()
    return encrypts
st3="0"*8
str4=""
str3=list(st3)
for a in range(0,2):
    str3[0]=str2[0][a]
    for b in range(0,2):
        str3[1]=str2[1][b]
        for c in range(0,2):
            str3[2]=str2[2][c]
            for d in range(0,2):
                str3[3] = str2[3][d]
                for e in range(0,2):
                    str3[4] = str2[4][e]
                    for f in range(0,2):
                        str3[5] = str2[5][f]
                        for g in range(0,2):
                            str3[6] = str2[6][g]
                            for h in range(0,2):
                                str3[7] = str2[7][h]
                                newS="".join(str3)
                                for i in itertools.permutations(newS, 8):
                                    str4 = sha_encrypt("".join(i))
                                    if str4==hash1:
                                        print "".join(i)
                                        exit(0)

结果为：

(Q=win*5

总结

通过本次实验，我学会了通过赋分的方式遍历出最有可能的密钥值，学会了如何破解类维吉尼亚密码，学会了通过结合社会工程学的方法破解出用户口令的方法。

本次实验刚开始还很没有头绪，只知道遍历密钥不知道还有赋分这种模式，也不知道这种模式如何使用，然后去GitHub上参考了一波大佬们写的代码，顿时茅塞顿开，GitHub真是个好地方。其余python有关的库的使用问题百度基本就可解决所有问题。

参考文献

https://github.com/akalin/cryptopals-python3
https://blog.csdn.net/liuweiran900217/article/details/19933549
https://www.cnblogs.com/elpsycongroo/p/7669786.html