1. 1. 一、古典密码-维吉尼亚密码
    1. 1.1. 1.简介
    2. 1.2. 2.算法流程
    3. 1.3. 3.算法实现
      1. 1.3.1. 3.1明文预处理
      2. 1.3.2. 3.2密钥字符串转为数字列表
      3. 1.3.3. 3.3加密过程
      4. 1.3.4. 3.4解密过程
    4. 1.4. 4.算法验证
    5. 1.5. 5.算法破解
      1. 1.5.1. 5.1确定密钥长度
      2. 1.5.2. 5.2确定密钥
      3. 1.5.3. 5.3恢复明文并验证
    6. 1.6. 6.算法分析
    7. 1.7. 7.选择工具原因
    8. 1.8. 8.实现难点
  2. 2. 二、序列密码-线性反馈移位寄存器
    1. 2.1. 1.简介
    2. 2.2. 2.算法实现
      1. 2.2.1. 2.1选定初始序列和特征多项式
      2. 2.2.2. 2.2线性反馈移位寄存器
    3. 2.3. 3.算法验证
    4. 2.4. 4.实现难点
  3. 3. 三、对称密码-DES算法
    1. 3.1. 1.简介
    2. 3.2. 2.算法流程
      1. 3.2.1. 2.1初始置换和逆初始置换
      2. 3.2.2. 2.2轮函数
      3. 3.2.3. 2.3密钥编排
    3. 3.3. 3.算法实现
      1. 3.3.1. 3.1初始置换和逆初始置换
      2. 3.3.2. 3.2 E盒扩展
      3. 3.3.3. 3.3 密钥加
      4. 3.3.4. 3.4 S盒代换
      5. 3.3.5. 3.5 P盒置换
      6. 3.3.6. 3.6子密钥生成
      7. 3.3.7. 3.7单次加密过程
      8. 3.3.8. 3.8单次解密过程
    4. 3.4. 4.算法验证
    5. 3.5. 5.算法分析
      1. 3.5.1. 5.1互补性
      2. 3.5.2. 5.2弱密钥
      3. 3.5.3. 5.3迭代轮数
      4. 3.5.4. 5.4密钥长度
    6. 3.6. 6.选择工具原因
    7. 3.7. 7.实现难点
  4. 4. 四、非对称密码-RSA算法
    1. 4.1. 1.简介
    2. 4.2. 2.算法流程
      1. 4.2.1. 2.1密钥生成
    3. 4.3. 3.算法实现
      1. 4.3.1. 3.1生成大奇数
      2. 4.3.2. 3.2快速幂
      3. 4.3.3. 3.3素性检验
      4. 4.3.4. 3.4产生大素数
      5. 4.3.5. 3.5求模逆
    4. 4.4. 4.算法验证
    5. 4.5. 5.算法分析
      1. 4.5.1. 5.1因子分解法
      2. 4.5.2. 5.2共模攻击
      3. 4.5.3. 5.3低加密指数攻击
      4. 4.5.4. 5.4循环攻击
    6. 4.6. 6.选择工具原因
    7. 4.7. 7.实现难点
  5. 5. 五、Hash函数-MD5算法
    1. 5.1. 1.简介
    2. 5.2. 2.算法流程
      1. 5.2.1. 2.1附加填充位
      2. 5.2.2. 2.2初始化链接变量
      3. 5.2.3. 2.3分组处理
      4. 5.2.4. 2.4步函数
    3. 5.3. 3.算法实现
      1. 5.3.1. 3.1附加填充位
      2. 5.3.2. 3.2分组处理及步函数
      3. 5.3.3. 3.3输出结果
    4. 5.4. 4.算法验证
    5. 5.5. 5.算法分析
    6. 5.6. 6.选择工具原因
    7. 5.7. 7.实现难点
  6. 6. 六、综合实验
    1. 6.1. 1.简介
    2. 6.2. 2.算法流程
    3. 6.3. 3.算法实现
      1. 6.3.1. 3.1身份认证
      2. 6.3.2. 3.2加密文件和对称密钥
      3. 6.3.3. 3.3解密对称密钥和文件
    4. 6.4. 4.算法验证
      1. 6.4.1. 4.1身份认证
      2. 6.4.2. 4.2加密文件和对称密钥
      3. 6.4.3. 4.3解密对称密钥和文件
    5. 6.5. 5.算法分析
    6. 6.6. 6.选择工具原因
    7. 6.7. 7.实现难点

密码学课程设计报告

Crypto
,

一、古典密码-维吉尼亚密码

1.简介

​ 维吉尼亚密码是由法国密码学家Blaise De Vigenère于1858年提出的一种代换密码，它是多表代换密码的典型代表。

​ 在凯撒密码中，字母表中的每一字母都会作一定的偏移，例如偏移量为3时，A就转换为了D、B转换为了E等等。而维吉尼亚密码，可以看成是由一些偏移量不同的恺撒密码所组成的。

2.算法流程

​ 维吉尼亚加密需要先选定一个密钥，再将明文和密钥的每个字符都按字母表顺序，转换为数字。然后，把明文按密钥字的长度分组，使用密钥字母对应数字加上明文字母对应数字之后，进行模26的运算，求余，即为加密结果。

​ 为了快速生成密码，可以使用表格法。这一表格包括26行字母表，每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的，在过程中会不断地变换。

​ 加密过程：明文字母p对应的列和密钥字母对应的行的交叉点，就是加密后的密文字母c。

​ 解密过程：在密钥字母k对应的行，找到相应的密文字母c，则c所在列对应的明文字母即为p。

维吉尼亚表

3.算法实现

3.1明文预处理

​ 因为维吉尼亚密码只能对英文字母进行处理，所以先用正则表达式去匹配文本中的非字母，然后再去除这些字符，即得到了纯英文字符明文。

1
2
3
4
5
6
def PreTreat():  
    with open("/Users/crownz/Crypto/1.Vigenere/plain.txt","r") as f:  
        plaintext = f.read()  
    pattern = re.compile('[\n]|\d|\W')  #匹配非字母  
    f_plain = re.sub(pattern,'',plaintext).lower()  
    return f_plain

3.2密钥字符串转为数字列表

​ 因为要使用密钥字符对应数字与明文字符对应数字相加来模26，这里将密钥字符先转换为数字列表，方便下面运用。

1
2
3
4
5
6
7
def key_to_num(key):  
    key_list=list(key)  
    num_key_list=[]  
    for key in key_list:  
        num_key=ord(key)-97  
        num_key_list.append(num_key)  
    return num_key_list

3.3加密过程

​ 在加密中，先将明文预处理，并将密钥转换为数字列表。之后，遍历明文，依次对每个明文数字减去a的assic码，再加上密钥字的数字后，模26取余，将余数转换为相应密文字符。将所有密文字符相连接，返回密文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def encrypt(key):  
    plaintext = PreTreat()  
    num_key_list = key_to_num(key)  
    ciphertext=''  
    k=0  
    for p in plaintext:  
        if k == len(num_key_list):  
            k = 0  
        num_p = ord(p)-97  
        cipher = (num_p+num_key_list[k]) % 26  
        cipher = chr(cipher+97-32)  
        ciphertext = ciphertext + cipher  
        k += 1  
    return ciphertext

3.4解密过程

​ 先将所有字符转为小写，并将密钥转为数字列表。之后，遍历密文，依次对每个密文数字减去a的assic码，在加上密钥字的数字后，判断正负，负数加上26，将结果转换为相应明文字符。将所有明文字符连接，返回明文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def decrypt(key):  
    with open("/Users/crownz/Crypto/1.Vigenere/cipher.txt") as f:  
        ciphertext = f.read().lower()  
    num_key = key_to_num(key)  
    plaintext=''  
    k = 0  
    for c in ciphertext:  
        if k == len(num_key):  
            k = 0  
        result = ord(c)-97 - num_key[k]  
        if result < 0:  
            result = 26 + result  
        plain = result  
        plain = chr(plain+97)  
        plaintext = plaintext + plain  
        k += 1  
    return plaintext

4.算法验证

​ 先找到一篇英文文章，用来加密。

​ 读入文件，选定密钥为“ilovecumt”，再使用加密算法，加密文章，输出密文。

​ 然后，再用自己的解密算法解密。在控制台中，可以看到跟明文意思相符的一连串字符。

​ 为了验证自己的算法，再去找一个维吉尼亚解密的在线网站解密。

​ 可以看到，下面的解密是有明文意思的连续字符串，只不过都是大写的。

5.算法破解

​ 维吉尼亚密码是一个多表代换密码，它打破了原语言的字符出现规律，比单表代换密码分析要复杂很多，但仍然有分析破解它的方法。

​ 维吉尼亚密码破解的分析方法主要分为三步：

​ ①重合指数法确定密钥长度

​ ②拟重合指数法确定密钥

​ ③根据确定的密钥来恢复明文

5.1确定密钥长度

​ 设一门语言由n个字母组成，每个字母出现的概率为 Pi ，则重合指数是指两个元素随机相同的概率之和，记作CI=∑Pi2 (1<= i <= n)。

​ 经分析，英文中，一段文字是随机的话，CI≈0.038；如果这段文字是有意义的，那么CI≈0.065。实际上计算CI时，应该用这个公式：

（L：密文长度；fi：在密文中的出现次数；n：这门语言的字母个数）

​ 然后算出不同密钥长度下，遍历该密钥长度区间，来计算每个密钥长度下的CI’的值。之后，去找出最接近0.065的值，其对应的密钥长度即为最可能的密钥长度。

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
def get_keylen():   #猜解密钥长度  
    flist=[]  
    ave_flist=[]  
    len_list=[]  
    result=[]  
    res=[]  
    initial_text=open("/Users/crownz/Crypto/1.Vigenere/cipher.txt","r")
    simplified_text=initial_text.read()#防止len出错
    letter_cnt=len(simplified_text)#英文字母总个数  
    simp_text=map(all_lower,simplified_text)#都换成小写字母  
    text_list=list(simp_text)#将简化的文本列表化  
    for key_len in range(2,50):   #在密钥可能的长度范围里面找  
        len_list.append(key_len)      
        for i in range(key_len):  
            templist=text_list[i::key_len]  #按密钥长度分组  
            sqcnt_list=[]  
            temp_len=len(templist)#分组字母个数  
            once_list=simplifiy_list(templist)#对当前分组去重复  
            for letter in range(len(once_list)):  
                cnt=templist.count(once_list[letter])#在templist出现的次数  
                sqcnt=cnt*(cnt-1)  
                sqcnt_list.append(sqcnt)#存放的都是sqcnt  
            flist.append(add_the_list(sqcnt_list)/(temp_len*(temp_len-1)))  
        ave_fre=add_the_list(flist)/len(flist)  
        ave_flist.append(ave_fre)  
    res=list(zip(len_list,(list(map(sub_stdfre,ave_flist)))))  
    result=sorted(res, key=lambda x:x[1]) 
    print("最有可能的前十个密钥长度及其对应频率和0.065差值为：")  
    for i in range(10):  
        print(result[i])

​ 当程序运行到这一步，可以看到跟0.065最相近的前10个密钥长度。

5.2确定密钥

​ 在确定密钥长度之后，就可以根据拟重合指数法，来确定密钥。根据密钥长度来确定密文分组，然后，分别遍历每个密文字符的可能取值，以此来恢复该组明文，并计算相应的重合指数。将每组最高重合指数下对应的数字转换为字符连接，即得到相应的密钥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def Crack_key(text,length):   
    key = []   
    array =makelist(text,length)  
    for i in range(length):  
        flist = f_list([row[i] for row in array])  
        multi = []   
        for j in range(26):  
            Sum = 0.0  
            for k in range(26):  
                Sum += freq[k]*flist[k]  
            multi.append(Sum)  
            flist = flist[1:]+flist[:1]  
        n = 100  
        ch = ''  
        for j in range(len(multi)):  
             if abs(multi[j] - 0.065)<n:   
                 n = abs(multi[j] -0.065)  
                 ch = chr(j+97)  
        key.append(ch)  
    return key

​ 运用上一步得到的密钥长度9，下面看到猜测的密钥为“ilovecumt”。

5.3恢复明文并验证

​ 由上一步得到密钥为“ilovecumt”，将密钥列表连接为字符串后，调用之前写好的解密函数，就可以得到明文。因为，我们知道猜测密钥就是正确的，解密得到的明文也就是正确的。

6.算法分析

​ 维吉尼亚密钥是典型的多表代换密码，通过多表代换，将明文的统计特性通过多个表的平均作用隐藏起来，相较于单表代换密码，增大了破解的难度。

​ 对所有多表密码的破译都是以字母频率为基础的，这里对维吉尼亚的分析仍不例外，只是直接的频率分析并不适用。通过卡西斯基试验或者就可以得到密钥长度，得到密钥长度，密钥就可以看作是多个凯撒密码结合到一起，每一个都可单独破解，就像上面的破解步骤。

​ 从维吉尼亚密码被创造出来的16世纪来说，那时人们并没有相应的分析方法，也就认为它是无法破解的，乃至往后1-2个世纪都有人认为它是足够安全的。直到19世纪，卡西斯基完全破解维吉尼亚密码并发表相关方法。

​ 就现在来说，因为相关分析方法的公布，维吉尼亚密码是不安全的，个人通过计算机就可破解，没有安全性可言。

7.选择工具原因

​ 以前一直想学习python，因为深知python的方便有效（对于编程人员来说），但一直又没有实践。曾看过一段时间的python书籍，练过相关小实例，但终究只浮于表面，做完就忘，很不深入，没有进展。所以，在密码学课程设计刚开始时，就决定要用python做完所有实验 ，不会就查，就问，去在实践中锻炼python的使用。

​ 现在看来，那句话挺不错的，“人生苦短，我用Python”。python的确很方便易用，通过这里锻练的能力会更多地应用在其他方面。

8.实现难点

​ 实验的难点在于维吉尼亚破解方法的理解，并将相应数学公式转换为相应的代码，出错也只能一步步调了。同时，也可以去看别人代码，看他们在程序的某一步是用什么函数和方法来处理的，能解决一些很困扰人的问题，比如类型不匹配，这个函数不能那样操作等。通过这个过程，能学习到很多。

二、序列密码-线性反馈移位寄存器

1.简介

​ 反馈移位寄存器由移位寄存器和反馈函数组成。移位寄存器是由位组成的序列，每次移位寄存器中所有位右移一位，新的最左端的位根据寄存器中的某些位计算来得到，反馈函数用来计算新的最左端位。

​ 而线性移位寄存器就是采用线性函数来作为反馈函数的反馈移位寄存器。

2.算法实现

​ 在这里只是实现一个简单线性移位寄存器，没有什么明确的流程，只是编写一个可以移位并加有反馈的寄存器。所以并没有什么具体的算法流程，直接编写就可以。

2.1选定初始序列和特征多项式

​ 因为要对一个序列进行移位那就先选定一个初始序列和一个16次的特征多项式，以再之后验证周期。

1
2
init_ = '1000000000000000'    #初始序列  
tap =  '1000000000010101'     #特征多项式二进制

2.2线性反馈移位寄存器

​ 开始设置好寄存器初始序列全局变量，抽头序列，再初始化一个跟寄存器长度一样的新列表。sum用来计数初始序列中1的数量，之后将sum对2取余作为反馈函数，算出左边新一位的值。最后，返回新的寄存器序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def lfsr(init,tap):  
    global init_  #全局变量，以改变寄存器序列
    array_init_bin = list(init)  
    tap = list(tap)   #抽头序列
  
    array_new = '0'*len(array_init_bin)  
    array_new = list(array_new) #再初始化一个相同长度序列  
  
    sum = 0  
    for i in range(len(array_new)):  
        if tap[i] == '1':  
            sum += int(array_init_bin[i])   
    for i in range(len(array_new)):  
        if i == 0 :  
            array_new[i] = str(sum % 2)#反馈函数  
        else :  #其他位不做处理
            array_new[i] = array_init_bin[i-1]  
    init_ = "".join(array_new)

3.算法验证

​ 写好线性反馈移位寄存器之后，就在主函数调用。用一个逻辑判断，去看哪一次移位反馈后，寄存器状态和初始一样，就打断循环，输出当前循环次数，即为周期。

1
2
3
4
5
6
7
for i in range(10000000000):  
    if init == init_ and i != 0 :  
        print("第{0}次:".format(i),init_)  
        print("序列周期为:",i)  
        break  
    print("第{0}次:".format(i),init_)  
    lfsr(init_,tap)

​ 在循环中，调用函数，等待一会儿，就可以看到输出了周期。

​ 在这里，生成序列的周期是65535，拿计算器算了下，正好是2的16次方减1，而我的多项式阶数就是16。也就是说，我所选择的特征多项式正好是一个本原多项式。验证了课上所学，特征多项式是本原多项式的LFSR对应周期为2的多项式阶数次幂减1。

4.实现难点

​ 这个反馈移位寄存器的书写并没有什么困难，按照那个移位寄存器的图，再加上反馈函数就可以很快写出。难在去找一个15阶以上的本原多项式去验证生成序列的周期。

​ 刚开始，我用了书上的32阶本原多项式，但序列周期实在太大，而且还不会用python的多线程来加快处理速度，40多亿条的序列，python单个处理实在太慢，跑不出来。然后，问其他同学要了一个16阶的多项式，测试一下，没想到正好是一个本原多项式，那也就正好验证周期为65535，结论正确。

三、对称密码-DES算法

1.简介

​ 数据加密标准(DES,Data Encryption Standard)是一个对称密码体制，1976年被美国联邦政府的国家标准局确定为联邦资料处理标准，随后在国际上广泛流传开来。

​ DES的加密和解密使用同一密钥，有效密钥的长度为56位。对数据进行加解密的单位为64位，明文和密文的长度相同。而且它使用Feistel结构，具有加解密相似特性。

2.算法流程

​ DES的整个操作可以分为三部分：

​ ①初始置换和逆初始置换

​ ②轮函数

​ ③密钥编排

​ 整个DES的基本结构如下：

2.1初始置换和逆初始置换

​ 初始置换是在第一轮迭代之前进行的，目的是将原明文块的位进行换位。逆初始置换是初始置换的逆置换。数据块经过初始置换和逆初始置换后，可以恢复到原有的位置。初始置换和逆初始置换的置换表都是固定且公开的，这步操作主要目的是为了在硬件实现时，更容易的将明文和密文以字节的大小存放入DES芯片中。

2.2轮函数

​ DES的轮函数有四部分组成：扩展置换(E盒)、密钥加、非线性代换(S盒)和线性置换(P盒)。

​ 扩展置换，它将32位输入扩展为48位输出。扩展方法为：将48位输出按8行6列的次序排列，排列时，将输入位序号按32、1、2、…、31、32、1的次序依次排列，且上一行的最后两位依次在下一行的起始位置得到重用。

​ 密钥加层的运算就是把E盒扩展输出的48位数据与48位字密钥进行逐位异或运算，输出48位数据。

​ 非线性代换，利用S盒将E盒扩展生成的48位数据又重新压缩为32位数据。S盒实质是一个查表运算，8个S盒分别对应8个非线性的代换表，每个S盒的输入均为6位，输出为4位。再查表前，要将输入的48位数据分为8组，每组6位，然后分别进入8个S盒，进行运算。

​ S盒具体的查表方法：设S盒的6位输入为b1、b2、b3、b4、b5、b6。将b1、b6位组合为2位的二进制数，其相应的十进制数对应表的行号；b2、b3、b4和b5构成4位的二进制数，其相应的十进制数对应表的列号。

​ 线性置换用来进行简单的位置置换，它按照给定的列表进行位置调换，不进行扩展和压缩。

2.3密钥编排

​ DES的初始64位密钥通过置换选择PC-1，来得到有效的56位密钥。这56位密钥分为2个28位数据C0和D0。每轮生成字密钥的迭代中，Ci-1盒Di-1分别循环左移1位或2位，移位后的值作为下一轮的输入，同时，也作为置换选择PC-2的输入，通过置换选择PC-2产生一个48位的输入，即产生一个子密钥。
)

3.算法实现

3.1初始置换和逆初始置换

​ 在实现初始置换和逆初始置换的时候，只需要把已知的置换表预先存到一个一维数组中，初始的64位明文分组以这个数组的中数字减1的值作为新的序号，来附加到返回结果后面。

1
2
3
4
5
6
7
8
9
10
11
12
# 初始IP置换  
def IP(init_str) :    
    res = ""  
    for i in IP_Sub:  
        res += init_str[i-1]  
    return res  
# IP逆置换  
def IP_re(final_str) :  
    res = ""  
    for i in IP_re_Sub:  
        res += final_str[i-1]  
    return res

3.2 E盒扩展

​ E盒扩展的实现方法跟上面初始置换的实现方法一样。

1
2
3
4
5
def Expan(bin_str) :  
    res = ""  
    for i in E :  
        res += bin_str[i-1]  
    return res

3.3 密钥加

​ 实现密钥加的时候，将E盒扩展的位和密钥的位，换为数字格式，就可以用数学符号异或，之后，根据异或结果，在返回结果后添加上字符类型的0或1。

1
2
3
4
5
6
7
8
9
def Xor(str,key) :  
    res = ""  
    for i in range(0,len(str)) :  
        xor_res = int(str[i],10) ^ int(key[i],10)  
        if xor_res == 1 :  
            res += '1'  
        elif xor_res == 0 :  
            res += '0'  
    return res

3.4 S盒代换

​ 因为字符是二进制字符型的，在python中选择字符串中相应的字符后，可以直接用加号连接，之后再把相应行列号转为数字，在一位数组中查找即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def Sub(xor_str) :  
    res = ""  
    count = 0     #用来计数S盒，共8个  
    for i in range(0,len(xor_str),6) :  #每6个分一组，循环8次  
        now_str = xor_str[i:i+6]    #将第i个分组，切片处理  
        row = int(now_str[0] + now_str[5],2) #二进制转化为十进制  
        col = int(now_str[1:5],2)  
  
        # S盒的第count个表,row*16是因为用一维列表存入矩阵值  
        num = bin(S[count][row*16 + col])[2:] 
        for i in range(0,4-len(num)) :  #利用bin输出有可能不是4位str
            num = '0' + num       #类型的值，下面的循环加上字符0  
        res += num  
        count += 1  
    return res

3.5 P盒置换

​ 仍然是把一维数组中数字减一，来作为编号，调整移位。

1
2
3
4
5
def PSub(sub_str) :  
    res = ""  
    for i in P :  
        res += sub_str[i-1]  
    return res

3.6子密钥生成

​ 生成密钥的时候，PC-1和PC-2就是查表，循环移位的位数在移位数组Shift中，循环左移利用python字符串的序号和拼接特性就可以实现。

1
2
3
4
5
6
7
8
9
10
11
def gen_key(key) :  
    key_list = []  
    key_change1 = PC1(key)  #PC-1置换
    key_C0 = key_change1[0:28]  
    key_D0 = key_change1[28:]  
    for i in Shift :  #循环移位 生成子密钥
        key_c = left_shift(key_C0,i)  
        key_d = left_shift(key_D0,i)  
        key_output = PC2(key_c + key_d)  #PC-2置换
        key_list.append(key_output)  
    return key_list

3.7单次加密过程

​ 这里对64位明文分组进行加密处理，整个流程和上面的算法流程中一样，很规律，需要注意的是，在最后一轮输出的时候，左右两边并不交换位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def encrypt_one(bin_plain,bin_key): #64位二进制加密  
    mes_ip_bin = IP(bin_plain)    #初始IP置换  
    key_list = gen_key(bin_key)  
    mes_left = mes_ip_bin[0:32]  
    mes_right = mes_ip_bin[32:]  
    for i in range(0,15):  
        mes_tmp = mes_right     #暂存右边32位  
        f_res = fac(mes_tmp,key_list[i])    #轮函数处理  
        mes_right = Xor(mes_left,f_res)     #右边f后，与左边密钥加  
        mes_left = mes_tmp  #初始右边32位放左边  
  
    f_res = fac(mes_right,key_list[15])  #轮函数f
    mes_fin_left = Xor(mes_left,f_res)  #最后一轮不交换位置
    mes_fin_right = mes_right  
    bin_cipher = IP_re(mes_fin_left+mes_fin_right)  
    return bin_cipher       #返回二进制

3.8单次解密过程

​ DES的加解密具有一致性，实际中，加密器可用作解密器，所以在实现解密的时候，跟加密的流程一致，只是在调用密钥的时候，将密钥列表倒序使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def decrypt_one(bin_cipher,bin_key):  
    cipher_ip_bin = IP(bin_cipher)  
    key_list = gen_key(bin_key)  
    lst = range(1,16)   #循环15次  
    cipher_left = cipher_ip_bin[0:32]  
    cipher_right = cipher_ip_bin[32:]  

    for i in lst[::-1]:   #表示逆转列表调用  
        mes_tmp = cipher_right  
        f_result = fac(cipher_right,key_list[i])  
        cipher_right = Xor(cipher_left,f_result)  
        cipher_left = mes_tmp  
      
    f_result = fac(cipher_right,key_list[0])  
    mes_fin_left = Xor(cipher_left,f_result)  
    mes_fin_right = cipher_right  
    bin_plain = IP_re(mes_fin_left + mes_fin_right)  
    return bin_plain    #返回二进制

​ 以上是DES各个主要步骤的函数实现，在实际应用的时候，还需要各种辅助函数来处理数据。就像我们日常使用的数据，不全是二进制，那就要编写函数将其转换为二进制；字符转为二进制不足64位，又要将其补为64位，还要写使用单次加密过程，来进行众多数据的加密函数。

4.算法验证

​ 将自己的DES算法加了一些交互之后，运行程序。

​ 选择加密，输入要加密的字符串为:i love china,密钥:cumt。加密后，将密文输出到了文件中，方便后面解密。

​ 再选择解密，输入密钥:cumt，即可获得之前的明文:i love cumt。

​ 加解密成功实现，且恢复了自己输入的明文，即验证了自己算法的正确性。

5.算法分析

​ 自从DES诞生，针对DES的讨论和攻击就没有停止，安全性主要包括四个方面:互补性、弱密钥、迭代轮数和密钥长度。

5.1互补性

​ DES有补码的特性，明文和密钥都取补时，密文也取补。

​ 在选择明文攻击下，可以对明文的补用同一密钥加密，这样由DES互补性就可以得到密钥的补对明文的加密结果。当穷举搜索密钥时，若输出密文为正常明文加密结果，则加密密钥就是现在所用的密钥；若输出密文是明文用密钥补的加密结果，则加密密钥就是现在所用密钥的补。
​ 利用DES的互补性，可以使穷举搜索的工作量由256将为255，减少了一半，能极大地加快破解速度。

5.2弱密钥

​ DES有四个弱密钥，使用它们作为子密钥，将使得DES加密两次后，数据仍为原来的数据，或者说是，加密和解密有同样的效果。

​ 还有12个半弱密钥，使用一个半弱密钥K1加密，相当于使用其对应的半弱密钥K2解密，会减少攻击工作量。

​ 因为弱密钥和半弱密钥的数量非常少，在实际使用时，可以检测事先检测一下密钥是否为弱密钥或半弱密钥，再使用，去避免不必要的风险。

5.3迭代轮数

​ DES的迭代轮数为16轮，为什么是16轮呢？因为使用差分分析方法时，对于8轮迭代的DES，在个人计算机上只需要几分钟就可以破解。而当DES进行16轮迭代的时候，差分分析攻击就没有穷举攻击有效了。所以DES的迭代轮数不应当减少，过多又会降低效率，这才定为16轮迭代。

5.4密钥长度

​ 在DES刚诞生的时候，56位的有效密钥就被认为是不安全的，因为它是从112位削减过来的。但即便这样，以当时的计算机处理能力想要穷举搜索256的密钥量，是非常困难的。1977年，Diffie和Hellman设想了一种机器可以在1μs之内完成一次加密，使平均搜索时间降到10个小时，但机器的造价在当时是2000万美元，很不切实际。

​ 但随着计算机性能的不断提高，用穷举攻击来破解DES成为现实。1998年，一台25万美元的计算机在56小时内破解了DES，这个时间内，破译的密钥仍具有时效性，意味着DES已经不再安全。只得转向三重DES，来增大密钥长度，缓解密钥长度不足带来的安全问题。

6.选择工具原因

​ 在这个算法实现中，python的字符串特性非常方便，像将明文分组分为两半、实现循环移位、二进制位置换都体现了这一点，所以选择python没有错。

7.实现难点

​ 对自己来说，因为想实现的是字符的加解密，所以第一个困难就是将字符化为二进制，这里是更深刻的体会了一个字符占8位，不足还要补齐，不然后面解码要出错。

​ 然后就是在解密的时候，处理的是二进制，不能讲加密结果简单的转为字符串，再将字符串复制过去，调用字符串转二进制函数，因为，密文每8位的二进制是很混乱的，并没有对应的编码，如果复制字符串，会不知道哪里是密文的终止处。所以，要么是密文就直接二进制不要动，复制解密的时候，不会错；要么是输出到文件中，等解密的时候，在从文件中读出。这里，我选择输出到文件中，这样密文转为字符串，也没有影响，因为文件算是闭合的，读取时，只会读取数据的部分，不会出现之前叙述的问题。

​ 最后，就是S盒、E盒等等，不要弄错，当时的盒都是百度找的，结果运行不了。最后各种调试，才发现是PC-2盒错了，资料的查询一定要官方，可信度高一点 。

四、非对称密码-RSA算法

1.简介

​ 在Diffie和Hellman提出公钥密码体制的设想后，Merkle和Hellman首先共同提出MH背包公钥加密体制，随后Rivest、Shamir、Adleman联合提出RSA公钥加密体制。RSA虽晚于MH背包公钥加密体制，但它是第一个安全、实用的公钥加密算法，已成为国际标准。

​ RSA的基础是数论的欧拉定理，它的安全性依赖于大整数因子分解的困难性。且因为加解密次序可换，RSA公钥佳美体制既可用于加密，也可用于设计数字签名体制。

2.算法流程

​ RSA加密算法的操作可以分为三部分:密钥生成算法、加密算法和解密算法。

2.1密钥生成

​ (1)选择两个大素数 p, q ( p ≠ q ，建议步骤(4)以后销毁)

​ (2)计算n = p×q，φ(n) = (p-1)×(q-1)

​ (3)选择整数e，使(φ(n), e) = 1，其中1<e<φ(n)

​ (4)计算d，使d = e-1 mod φ(n)

​ 得到公钥{e, n}和私钥{d}。

​ 2.2加密

​ 明文M < n，密文C = Me(mod n)

​ 2.3解密

​ 密文C，明文M = Cd(mod n)

3.算法实现

3.1生成大奇数

​ 因为素数没有规律，不能有规律地产生很多素数，只能是先产生一个数，然后再判断它是不是素数。这里是，先产生一个足够大的奇数(因为除了2其他素数都是奇数)，然后再通过素性检验来判断这个数是否是素数，不是的话，就要重新产生。

1
2
3
4
5
6
7
8
9
def gen_bin(num): #num为希望产生伪素数的位数  
    list = []  
    list.append('1')    #最高位为1  
    for i in range(num-2):  
        c = random.choice(['0','1'])  
        list.append(c)  
    list.append('1')    #最低位为1  
    res = int("".join(list),2)  
    return res

3.2快速幂

​ 下面的素性检验需要用到快速计算模幂，这里就把它封装起来，方便后面调用。

1
2
3
4
5
6
7
8
def X_n_mod_P(x,n,p):  # 计算x的n次方模p,快速计算模幂
    res = 1  
    n_bin = bin(n)[2:]  # 幂次的二进制
    for i in range(0,len(n_bin)):  
        res = res**2 % p 
        if n_bin[i] == '1':  
            res = res * x % p  
    return res

3.3素性检验

​ 素性检验分了两步，首先是条件宽松的费马小定理，通过这个检验之后，才是更为严格的Miller-Rabin检验。这两者的代码实现，都是参照具体的定理和公式，将其转化为代码。

​ 费马小定理:若a是一个整数，p是一个指数，那么p|ap-a。

​ Miller-Rabin算法:要检验n是否为素数，首先将n-1分解为2sd，每次测试前，随机选取一个介于[1, n - 1]的整数a，然后若对于所有的r ∈[0, s - 1]，若ad mod n ≠ -1，则n为合数，否则n有0.75的概率为素数。增加测试次数，其为素数的概率也就越高。

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
def fermat_test(a,n):  # 如果n是一个素数，a是小于n的任意正整数， 
    if n == 1:       # 那么a的n次方与a模n同余  
        return False  
    if n == 2:  
        return True  
    res = X_n_mod_P(a,n-1,n)  #   以2为底  
    return res == 1  
  
def MillerRabin(n):  # 二次探测,进一步判断n是否为素数  
    a = random.randint(2,n-2)#随机选择 2-n-2  
    if fermat_test(a,n) == 1:#p经过判断，可能为素数  
        d = n-1 #初始的d  
        sum = 0 #d中因子2的次数  
        while (d%2) == 0:  
            sum += 1  
            d = d>>1  
        x=X_n_mod_P(a,d,n)  
        for i in range(sum):  
            new_x = X_n_mod_P(x,2,n)  
            if new_x == 1 and x != 1 and x != n-1:  
                return False  
            x = new_x  
        if x != 1:  
            return False  
        else:  
            return True

3.4产生大素数

​ 在这里是产生512位的大素数，在产生初始的大奇数之后，通过多次调用Miller-Rabin素性检测，来判断这附近的奇数是不是素数，如果是，就返回该数；如果不是，就重新产生，知道产生一个数通过测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gen_512():  
    while 1:  
        d = gen_bin(512)  
        for i in range(50):# 伪素数附近50个奇数都没有真素数 重新产生一个伪素数  
            flag = testMillerRabin(d+2*i,5)# 增加测试轮数，来提升精确度  
            if flag:  
                b = d + 2*i#这个数通过检验  
                break  
            else:  
                continue  
        if flag:  
            return b  
        else:  
            continue

3.5求模逆

​ 在RSA生成密钥的时候，需要使用模逆运算。这里利用辗转相除法的变形来求模逆，将相应定理转化为代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def invert(e,phi):  # 模逆存在的前提是两者互素  
    a_list = []  
    m = phi  
    n = e  
    tmp = m % n  
  
    while(tmp != 0):  
        a = (m - tmp)/n  
        a_list.append(a)  
        m = n  
        n = tmp  
        tmp = m % n  
    a_list.reverse()  
    b_list = []  
    b_list.append(1)    #倒数第二个式子,互素得到为1  
    b_list.append(a_list[0])  
    for i in range(len(a_list)-1):  
        b = b_list[-1] * a_list[i+1] + b_list[-2]  
        b_list.append(b)  
    if len(a_list) % 2 == 0:#list数目为偶数  
        return int(b_list[-1])  
    else:                   #list数目为奇数  
        return int(phi-b_list[-1])

​ 这里好像出了点问题，后面把报告都交了，才发现我这个求模逆的算法出错了，当时演示验证的时候，我好像调用的是gmpy2的库，才没出错。emmm，要是有人看到这里，还请 不要参考这个代码。

4.算法验证

​ 如果一段明文能经过RSA加密，在解密后，能恢复出明文，就验证了RSA算法的正确性。编写如下算法主流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
print("Loading...")  
while 1:  
    p = gen_512()  
    q = gen_512()  
    n = p*q  
    if (len(bin(n)[2:])) == 1024:  
        break  
phi = (p-1)*(q-1)  
e=65537  
d=invert(e,phi)  
print("d:",d)  
print("e:",e)  
print("n:",n)  
print("---------")  
m=libnum.s2n("i love cumt!")#明文数字  
c=X_n_mod_P(m,e,n)    #密文  
m=X_n_mod_P(c,d,n)    #明文数字  
print("明文:",libnum.n2s(m))

​ 运行上面算法，可以看到，明文仍然为:i love cumt!，即验证算法正确。

5.算法分析

​ 针对RSA的攻击有很多种，主要是参数选择、使用不当造成的，下面就对这些进行讨论。

5.1因子分解法

​ SA密码体制的安全性主要依赖于大整数因数分解的难题，试图分解模数 n的素因子是攻击RSA最直接的方法。如果能够分解n，那么φ(n) = (p-1)×(q-1)就可以分解出来。分解方法有试除法、p-1因子分解法、p+1因子分解法、二次筛因子分解法、椭圆曲线因子分解法、数域筛因子分解法等。但由于因子分解的时间复杂性并没有降为多项式时间，因此，因子分解还是一个计算上的难题，只是在实际使用中，需要考虑使用较大的位数，以确保无法在短时间内被破解。

5.2共模攻击

​ 在实现RSA的时候，有时为了方便，在共享同一消息的时候，会让多个用户使用相同的模数n，但公、私钥对不同。而这种做法是不安全的。

​ 设两个用户的公开密钥为e1和e2，且e1和e2互素，明文消息m，密文分别为c1≡me1(mod n)，c2≡me2(mod n)。攻击者截获c1和c2之后，用拓展欧几里得算法求出满足re1+se2=1的两个整数r和s，由此可得c1rc2s≡mre1mse2≡mre1+se2≡m(mod n)，即获取明文。

5.3低加密指数攻击

​ 有时为了增强加密的高效性，会使用较小的加密密钥e，但将消息发送给多个实体时，这样就会存在很大问题。

​ 当e=3的时候，如果明文也较小，会使得明文的三次方仍然小于n，当将多个消息通过不同模数产生密文时，可以通过中国剩余定理来求出m3对多个模数乘积的取余结果，又m3小于模数乘积，对m3直接开立方，就可以得到结果。

5.4循环攻击

​ 当攻击者截获密文之后，可以对密文进行循环加密，将每次加密结果和密文进行对比，如果有哪一次的加密结果和密文相同，说明上一次的加密结果即为明文。这种攻击只有在循环加密密文，再次得到原始密文的次数比较小的时候，才是可行的。为了抵抗这种攻击，应当通过p和q的选择，使得p-1和q-1都有较大的素因子。

​ 为了防范这些攻击，首先应当使得密钥长度足够大，NIST建议，若保密期限超过2015年，则建议至少使用2048比特长密钥。同时，p和q的选取应当满足以下几点要求：

​ ①p和q的长度相差不能太大

​ ②p和q的差值不应该太小

​ ③p-1和q-1的公因数应尽可能小

​ ④p-1和q-1都应该有大的素数因子

6.选择工具原因

​ 在这里，python的优势在于它语言的简洁性和描述性，通过近似英语的描述，就可以实现出多个数学公式和定理的代码形式。

7.实现难点

​ 首先是找到可行的素性检测方法，需要搜索一番资料，然后就是对这些方法的代码实现，比较难一点。

五、Hash函数-MD5算法

1.简介

​ Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入(又叫做预映射)通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是说，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是是将任意长度的输入变换为固定长度的输出的不可逆的单向密码体 制。

​ MD5(Message-Digest Algorithm,信息摘要算法)，是由美国著名密码学家Rivest设计的一种密码散列函数，可以将长度小于264比特的消息，按512比特的分组单位进行处理，输出一个128比特的消息摘要。

2.算法流程

​ MD5算法的流程可以分为:附加填充位、初始化链接变量、分组处理和步函数。

2.1附加填充位

​ 首先需要对明文信息进行填充，使其位长度模512和448同余。因此，信息的位长度被扩展至512×N + 448。然后在这个结果后面附加一个以64位二进制表示的填充前信息长度。经过这两步的处理，现在的信息字节长度为512 × N + 448 + 64 = (N + 1) × 512，即长度恰好是512的整数倍。

2.2初始化链接变量

​ 使用4个32位的寄存器A，B，C，D存放4个固定的32位整型参数，
A:0x1234567,B:0x89ABCDEF,C:0xFEDCBA98,D:0x76543210。

2.3分组处理

​ 将填充好的信息进行分组，每组512位 ,共有N组。主循环有四轮，每轮循环包括16个步骤。每步的输入是4个32比特的链接变量和一个32比特的消息子分组，输出为32位值。经过4轮共64步之后，得到的4个寄存器值分别与输入链接变量进行模加，即得到此次分组处理的输出链接变量。

2.4步函数

​ MD5每轮包含16步，每轮的步函数相同，即使用同一个非线性函数，而不同轮的步函数使用的非线性函数是不同的，即四轮使用4个不同的非线性函数。设X、Y、Z是3个32比特的输入变量，输出是一个32比特变量，则这4个非线性函数F、G、H和I定义为：

​ F(X,Y,Z)=(X&Y)|((~X)&Z)

​ G(X,Y,Z)=(X&Z)|(Y&(~Z))

​ H(X,Y,Z)=X^Y^Z

​ I(X,Y,Z)=Y^(X|(~Z))

3.算法实现

3.1附加填充位

​ 下面这段话是在当初学习的时候所写，近期在复习密码学时想到了这个问题，看了其他人的博客，认为原先这个必须附加0x80的描述是不准确的。之前验证的时候，没有出错只是碰到了大多数附加填充位大于8bit的状况，如果验证例子够多，肯定会有出错的例子。

​ 对输入的消息先附加0x80，这一步不可少，之后再去判断模512是否跟448同余。需要注意的是，即便是消息长度刚好是模512和448同余，也要有附加填充位这个操作，这时就是填充512位，最高位为1，其余都为0，使填充后消息再模512和448同余，可以说是，附加0x80的优先级要高于判断同余。

​ 在找了很多博客之后，发现这一点都是很模糊，最后想到去找官方文档看看，这总不至于理解不清吧。这就在这里看到了描述，截取填充的内容如下。看到最后描述说，填充总是必需的，最少1bit，最多512bit。所以，这个必须先附加0x80是有问题。如果人家就差1bit就能满足条件了，附加0x80(8bit)不就出错了吗。总的来说，之前写的附加填充位代码还是有问题的，应该先检查长度，决定要附加消息的位数，再去附加填充，就可以了。代码也懒得改了，如果有谁看到这里想应用，记得把下面那个代码逻辑改下，应该挺好弄，就几行。先判断差多少，然后去附加填充位数，使得之后的位数模512和448同余。

3.1 Step 1. Append Padding Bits

The message is “padded” (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.

Padding is performed as follows: a single “1” bit is appended to the message, and then “0” bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

​ 在填充消息之后，还要注意大小端序的转换，这些数字在寄存器中是以小端序进行存储的，不然就会出错。为什么这样呢？因为MD5这个算法认为分组里面的数据都是小端序存储的，我们必须要把数据存储成它想要的小端序。更详细的话，参见这篇文章。那为什么MD5认为数据是小端序的呢，因为这是标准规定（RFC1321），Rivest设计之初就是这样考虑的，就像1+1=2这样的东西，记着就好了。

​ 用下面这个图来理解一下，我们已知一个地址0x11223344，想要小端序存储，就要高字节高地址，低字节低地址，得到结果为0x44332211。同样，给出的初始链接变量中，A=0x01234567，小端序存储就为0x67452301，其他变量B、C、D也是如此。等MD5的变换完成之后，再把小端序转换回去即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def append(mes):                         #封装起来用  
    ascii_list = map(hex,map(ord,input_m))      # 转换为asc码  
    ascii_list = list(ascii_list)  
    msg_lenth = len(ascii_list)*8  
    #对每一个输入先添加一个'0x80'，即'10000000'  
    ascii_list.append('0x80')  
    #补充0  
    while (len(ascii_list)*8+64)%512 != 0:  
        ascii_list.append('0x00')  
    #最后64位存放消息长度，长度存放顺序是低位在前。  
    msg_lenth_0x = hex(msg_lenth)[2:]  
    msg_lenth_0x = '0x' + msg_lenth_0x.rjust(16,'0')  
    msg_lenth_0x_big_order = reverse_hex(msg_lenth_0x)[2:]      # 反转  
    msg_lenth_0x_list = []  
    for i in range(0,len(msg_lenth_0x_big_order),2):  
        msg_lenth_0x_list.append('0x'+ msg_lenth_0x_big_order[i:i+2])       
    return ascii_list.extend(msg_lenth_0x_list)

3.2分组处理及步函数

​ 将链接变量初始化后，存到fun_list，所用的各种非线性逻辑函数预先写好，在函数中用参数f调用，参数m是每轮运算所需要的消息分组(也要注意大小端序的转换)，参数shi是每次循环移位的位数，根据算法的要求预先定义到一个元组中，方便使用。算法的整体流程和图5.3的流程一样，只不过要多次循环处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def fun(fun_list,f,m,shi):#参数为初始化链接变量 每轮用到的F G H I 生成的M[]，
    count = 0  		    #以及循环左移的位数。该函数用来完成一轮运算，共16步  
    global Ti_count      #全局变量，T(i)从1到64循环  
    while count<16:  
        # A+轮函数处理+M[i]+T[i]  
        xx = int(fun_list[0],16)+f(int(fun_list[1],16),int(fun_list[2],16),int(fun_list[3],16))+int(m[count],16)+T(Ti_count)  
        xx = xx&0xffffffff  
        # 循环左移  
        ll = L(xx,shi[count])  
        fun_list[0] = hex((int(fun_list[1],16) + ll)&(0xffffffff))  
        # ABCD -> DABC  
        fun_list = shift(fun_list)  
        count += 1  
        Ti_count += 1  
    return fun_list

3.3输出结果

​ 将循环处理64步之后的4个输出和4个初始化链接变量分别相加后，存到一个列表中，在函数中 用f_list调用，将字符串进行大小端序转换，再连接，即输出MD5加密值。

1
2
3
4
5
6
7
def show_result(f_list):  
    result = ''  
    f_list1 = [0]*4  
    for i in f_list:  
        f_list1[f_list.index(i)] = reverse_hex(i)[2:]  
        result = result + f_list1[f_list.index(i)]  
    return result

其他更详细的代码没有单独拿出来列举，具体可以参见github，博客最后附有链接。

4.算法验证

​ 将算法整体实现之后，运行，输入要进行MD5加密的消息，这里为书上的例子:iscbupt，之后输出MD5加密值，跟书上相比对，除了这里字母是小写的之外，其他都跟书上一样。这里输出小写是因为python计算16进制是按小写来的，因为我之前存入初始链接变量是大写，它也按小写来处理，输出也是小写的，但它所代表的意思都没有变，所以这也没错。

5.算法分析

​ MD5具有Hash函数的所有特性。

​ ①压缩性。无论输入的明文多长，计算出来的MD5值长度固定为128位。

​ ②易计算性。由原数据容易计算出MD5值 。

​ ③抗碰撞性。知道明文和MD5值，很难找到相同MD5值相同的明文。

​ ④抗修改性。即便修改一个字节，计算出来的MD5值也会存在极大差异

​ MD5是在MD4基础上发展而来的，虽然比MD4稍慢，但更安全，实现了更快的雪崩效应，在实际应用中更受欢迎。

​ 散列函数的安全性主要体现在其良好的单向性和对碰撞的有效避免。由于散列变换是一种压缩变换，输入和输出长度相差极大啊，很难通过输出来确定 输入。但是，散列函数经常被用于数据改动检测，如果一个合法消息和一个非法消息能够碰撞，攻击就可以用合法消息生成散列值，再以非法消息作为该散列值的对应消息进行欺骗，且是他人无法识别。所以，对于Hash函数的攻击，攻击者的主要目标不是恢复原始明文，而是用相同散列值的非法消息来替代合法消息进行伪造和欺骗。

​ 对于MD5的碰撞研究，王小云教授做出了突破性的贡献，她的研究成果可以概括为：对于给定的M1，可以比较快速地找到M2，使得H(M1)=H(M2)。在2004年发表的论文中，她在IBM P690上用了一个小时左右就找了这样的一个碰撞，放到现在的计算机上面，这个时间会更短。所以，如果是要求高度保密的场所，比如说军工之类，MD5已经不安全了，应更换为更安全的Hash算法；但对于民用来说，一般没有人有能承受那么大计算量的设备，在一些不重要的认证上面仍可使用。

6.选择工具原因

​ 使用python可以直观地描述出整个算法的流程，而且在大小端序的转换这里，利用它字符串的拼接特性，也可以较为容易地实现。

7.实现难点

​ 下面所写的难点仍是之前写报告所写的，之前附加填充的理解错了，这里的实现难点自然也描述错了，实现难点就是理解这个流程，再用代码表述，还有大小端序的问题。

​ 对首先是附加长度，不知道附加0x80是必须的，不管它消息长度是不是模512和448同余，必须是先附加个0x80，之后再判断同余，再填充0。

​ 还有一点是大小端序的转换，刚开始并不知道要进行转换，知道后，刚开始也只是对初始化链接变量进行大小端序转换了，这样还是不能得到正确结果。多次尝试之后，又去看别人所写，才知道知道每个消息分组的内容也要进行大小端序的转换。在将大小端序调整好以后，才是能正确的输出结果。

六、综合实验

1.简介

​ 现在，Alice想通过公共信道给Bob传输一份秘密文件（文件非常大）。又知道，很多人和机构想得到这份文件。需要设计一个通信模型，来保证文件的机密性和完整性。

2.算法流程

​ 我设想算法模型分为三步，分别为身份认证、加密文件和对称密钥、解密对称密钥和文件。

​ 现在很多人想要得到这份文件，那么，可能会有很多人在假冒Bob的身份，来请求得到这个文件，需要对Bob身份进行验证；也有可能是很多人得不到文件，就假冒Alice的身份，想要给Bob发送文件，如果有人发送恶意文件给Bob，Bob发现不是想要的文件，但这个文件给Bob电脑安装了后门，等他接受了正确的文件，就存在泄漏的风险，所以需要对Alice身份进行验证。

​ 双向身份验证通过后，就可以收发数据，要发送的文件非常大，就采用对称加密算法，因为这个算法相较于非对称算法速度快。这里让通过公共信道进行传输，Bob和Alice不可能在公共信道交换密钥，则对称密钥也需要加密。那就使用非对称算法来对密钥加密，处理的密钥长度不算长，速度没有显著降低，而且是采用两种加密方法，在一定程度上可以增大攻击者的破解难度。加密完成后，就可以通过公共信道传输数据。

​ 但Bob接收到加密消息后，先通过非对称算法的私钥计算出对称密钥，然后用对称密钥，就可以解密出明文。

3.算法实现

​ 首先说明，整个算法的代码实现是利用python的socket编程来写的。Alice作为客户端，Bob作为服务端，方便说明。

3.1身份认证

​ 因为Bob是要接受数据 ，这里Bob作为服务端，被动地等待连接。当Alice连上后，就送出自己的身份hash，等待Bob验证。

1
2
3
print("等待bob验证自身身份...")  #送出自己身份hash  
hash_name = bytes(Md5(name),"utf-8")  
client.send(hash_name)

​ 当Bob收到Alice发送的身份信息之后，就会通过Hash函数的比对，来验证是否通过验证，若通过验证，就会返回通过验证，并同时输送自己身份信息给Alice。

1
2
3
4
5
6
7
8
9
print("验证alice身份...")  
a = input()  
hash_name = con.recv(512).decode()  
if hash_name == Md5("alice"):  
    print("验证通过！")  
    con.send(bytes("您通过了验证!","utf-8"))  
else:  
    print(hash_name,Md5("alice"))  
    exit("验证错误！")

​ Alice收到验证通过和Bob的身份信息，就会开始比对Bob的身份Hash，如果通过验证，Alice就可以继续下面的传输。

1
2
3
4
5
6
7
8
9
10
11
print(client.recv(1024).decode())  
#接收bob身份hash并验证  
print("验证bob身份...",end="")  
a=input()  
hash_name = client.recv(1024).decode()  
client.send(b'1')  
if hash_name == Md5("bob"):  
    print("验证通过!")  
else:  
    print(hash_name,Md5("bob"))  
    exit("验证错误!")

3.2加密文件和对称密钥

​ 当验证通过以后，Bob送出自己的公钥及Hash，防止他人篡改。

1
2
3
4
con.send(bytes(str(e),"utf-8"))  #送出公钥及相应hash  
con.recv(1024)  
hash_e = Md5(str(e))  
con.send(bytes(hash_e,"utf-8"))

​ 当Alice收到公钥和Hash之后，先验证Hash正确性，通过之后 ，继续向下进行。

1
2
3
4
5
6
7
8
e = int(client.recv(1024))  
print("获取公钥:", e)  
client.send(b'1')  
hash_e = client.recv(1024).decode()  
if hash_e == Md5(str(e)):  
    print("公钥正确!\n开始传输数据:")  
else:  
    exit("公钥错误!")

​ 公钥无误，可以开始加密数据。先调用对称密钥生成算法，随机生成一个对称密钥，这里用的是DES算法。有了密钥之后，调用DES加密算法进行加密文件。加密文件之后，再将对称密钥用RSA算法加密。加密完成之后，就将加密密钥和密文传输过去。要注意的是，在传输密文之前，还要传输密文的长度，方便Bob进行解密。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bin_key = gen_key()         #生成对称密钥  
int_key = int(bin_key,2)      
print("产生对称密钥:",int_key)  
  
plain = read_out_file()#明文  
bin_cipher = des_encrypt(bin_key, plain)#二进制加密值  
print("加密明文中...")  
  
cipher_key = X_n_mod_P(int_key, e, n)  
plain_key = X_n_mod_P(cipher_key, d,n)  
print("加密对称密钥...")  

print("传输密钥中...")  #传输密钥  
client.sendall(bytes(str(int_key),"utf-8"))  
  
client.recv(512)  #防止前后数据包的粘连
  
length = str(len(bin_cipher))  #传输密文大小  
length = bytes(length,"utf-8")  
client.send(length)  
  
print("传输密文中...")  #传输密文  
client.sendall(bytes(str(bin_cipher),"utf-8"))

3.3解密对称密钥和文件

​ Bob先接收密钥和密文，然后对密钥解密。得到对称之后，对密文进行解密，就可以得到明文。

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
buffer = []  #接收密钥  
data = con.recv(1024)  
data = data.decode()#str  
int_key = int(data)  
print(int_key)  
  
con.send(b'1')  #防止前后数据包的粘连
  
length = con.recv(1024)  #接收密文长度  
length = int(length.decode())  
  
buffer = []  #接收密文  
size = 0  
while size < length:  
    dat = con.recv(1024)      # 每次最多接收1k字节
    size += len(dat.decode())  
    buffer.append(dat)  
data = b''.join(buffer)  
bin_cipher = data.decode()#接受信息  
print(bin_cipher)  
 
int_key = x_k_mod_n(int_key,d,n)  #解密密钥 
cipher = libnum.b2s(bin_cipher)  #还原明文  
bin_key = bin(int_key)[2:]  
print("解密传输内容:")  
print(libnum.b2s(des_decrypt(bin_key, cipher)))

4.算法验证

4.1身份认证

​ 先运行Bob服务端，再运行Alice客户端，看到双方的验证都通过了。

4.2加密文件和对称密钥

​ 当验证通过以后，Alice就获取公钥并验证。通过之后，开始产生对称密钥并加密明文，明文加密完之后，就对对称密钥加密，加密以后。传输加密的密钥和密文。

4.3解密对称密钥和文件

​ Bob收到加密密钥和文件以后，对密钥解密，再对文件解密就得到了完整文件。这里的文件内容和自己本地一样，可以认为算法在传输数据上没有错误。

5.算法分析

​ 这个模型综合运用了之前的DES算法、RSA算法和MD5算法，是一个综合的算法。相较于单独运用每一种算法，这个算法更具安全性，能实现身份认证、完整性验证。

​ 但是就再分析安全性，发现还是有些不足，因为这里采用了DES加密，在整个加密系统中，可以认为它安全性取决于最容易被破解的算法，在这里就是DES算法。因为随着相关研究的发表和计算机能力的提升，DES已经不再是牢不可破的，如果攻击者有这种能力，完全可以直接不管这个算法的其他部分。对密文截取以后，直接穷举攻击，就能得到文件内容。所以，在设计安全算法时，要考虑各个部分的安全性，不能顾此失彼。如果想要对这个算法进行改进，可以将对成加密算法换为AES算法或者IDEA算法，因为这两个算法，就目前来说，都没有明显有效的破解方法。

6.选择工具原因

​ python有额外写好的socket编程模块可以使用，在这里实现交互演示的时候更加方便。

7.实现难点

​ 这个实验模型主题框架就是老师上课所讲，调用的算法也都是前面自己写过的，只不过，有些是自己又回去把它们给封装成函数在这里调用，并没有算法上的困难性。关键是socket编程，这一块是完全不会的，在实际做的时候，在多个数据包的粘连、数据编码和文件传输这方面，有很大问题，不会就去问同学和百度了，代码写得比较冗余，但总归算是能做出来。

GitHub:https://github.com/crownz-sec/Cryptography-course-design