密码学作业记录(二)

接上篇

序列密码

RC4算法

​RC4算法是一种流加密算法,密钥长度可变。它加解密使用相同的密钥,因此也属于对称加密算法。RC4是有线等效加密(WEP)中采用的加密算法,也曾经是TLS可采用的算法之一。

算法原理:

​RSA算法原理非常简单,256字节的状态向量S= {0,1,…,255},用比特字节表示为S= {00000000, 00000001, ….,11111111}。用一个可变长度为1~256字节(8~8048位)的密钥来初始化256字节的状态向量S={S[0], S[1], …, S[255]},任何时候,S都包含0~255的8位无符号数的排列组合。加密和解密时,密码流中的每一个字节k由S产生,通过系统的方式随机从S的256个元素中选取一个。每产生一个字节k,S的元素都要被再次排列。具体步骤如下:

  • 步骤一:S向量原状态:

    1
    ​S=[0,1,2,...,255]
  • 步骤二:创建临时向量T(256位),如果密钥K的长度为256位,则直接将K赋给T,否则一直重复复制K,直到填满256位的向量T

  • 步骤三:接下来我们使用T向量来产生S的初始排列。这个过程从S[0]开始一直处理到S[255],同时对每个S[i],根据T[i指定的方案将S[i]与S的另一个元素进行交换:
  • 步骤四:密码流产生。一旦S向量的初始排列完成后,密钥就不再被使用。接下来就是使用S自身来不断输出伪随机密码流的过程了。
  • 步骤五:加密。将步骤四中获得的随机字节k与明文的下一字节做异或运算,产生的字节即为对应的密文字节。

​解密时,由于加密只是使用密码流对明文做了异或运算,因此解密过程只需要使用相同步骤产生密码流并对密文进行同样的异或运算即可得到加密前的明文。

代码如下:

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
import sys
import base64

s = []
t = []

# 初始化s
for i in range(256):
s.append(i);

# 秘钥
# 通常取16字节
k = [1,45,12,12,3,5,6,7,123,45,78,95,65,23,44,55]

# 为暂时向量t赋值
for i in range(256):
t.append(k[i % len(k)])

j = 0
for i in range(256):
j = (j+s[i]+t[i]) % 256
s[i],s[j] = s[j],s[i]

f = open('a.txt','rb')
text = f.read()

# 产生密钥流
q = []
i = 0
j = 0
for r in range(len(text)):
i = (i+1) % 256
j = (j+s[i]) % 256
s[i],s[j] = s[j],s[i]
t = (s[i] + s[j]) % 256
q.append(s[t])

cipher = ""
for i in range(len(text)):
t = (q[i] ^ text[i]) % 128
cipher += chr(t)

plain = ""
for i in range(len(text)):
t = (q[i] ^ ord(cipher[i])) % 128
plain += chr(t)

if sys.argv[1] == "d":
print("plain: ")
print(plain)
else:
print("cipher: ")
print(base64.b64encode(cipher.encode('utf-8')).decode('utf-8'))
f.close()

实例演示:

​ 代码中加密的是一段英文文本,密文转为base64编码存储

demo

安全性分析

​ 由于RC4算法加密采用的是xor异或运算,所以一旦子密钥序列出现了重复,密文就有可能被破解。 那么,RC4算法生成的子密钥序列是否会出现重复呢?由于存在部分弱密钥,使得子密钥序列在不到100万字节内就发生了完全的重复,如果是部分重复,则可能在不到10万字节内就能发生重复。所以在使用中应该对密钥进行检查。

​ 根据目前的分析结果,没有任何的分析对于密钥长度达到128位的RC4有效,目前主要的攻击方法还是穷举攻击,所以到目前为止,RC4还算一个安全的加密算法。

​ 2015年,比利时研究人员Mathy Vanhoef及Frank Piessens,公布了针对RC4加密算法的新型攻击程式,可在75小时内取得cookie的内容。

实用性分析

​ RC4算法等序列密码加密过程较之分组密码而言相对简单,实现起来相对容易,在加密效率上对分组密码的优势是不言而喻的。此外,对于需要加密/解密数据流的应用,比如在数据通信信道或浏览器/网络链路上,流密码可能是更好的选择 。


​ 流密码在安全性强度上不逊分组密码,而加密速率又远优于后者,那是不是说明流密码可以完全取代分组密码呢?很可惜,答案是否定的。

​ 众所周知,分组密码的设计关键在于加解密算法,是明文和密文在密钥的控制下尽可能复杂,而序列密码的设计关键在于密钥序列产生器,使生成的密钥序列具有不可预测性。而密码序列产生器,也就是伪随机数字节流的产生,依赖种子(密钥)和伪随机函数,而如果种子和伪随机函数不变的情况下,每次产生的伪随机数字节流都是一样的。如果每次都用同样的密钥作为PRF的输入,产生同样的密码流来与两个不同的明文流分别进行异或运算得到两个密文流,那么将这两个密文流进行异或,结果就是两个原始明文的异或值。如果明文是文本字符串或其他已知其性质的字节流,那么密码破解很可能会成功。因此,对于这些已知性质的字节流进行流密码加密,密钥就不能被重复使用了。在这一点上,分组密码的优点就体现出来了。

哈希函数

​ 哈希函数的单向性,压缩性,抗碰撞性等特点使得它能够解决实际应用中很多棘手的安全问题,诸如数字签名,文件指纹等。

MD5算法

​ MD5(Message Digest Algorithm 5),为计算机安全领域广泛使用的一种散列函数,用以提供消息的完整性保护。

​ MD5是一种信息摘要算法,MD5算法对输入任意长度的消息进行运行,通过特定的hash散列方法将文本信息转换成产生一个128位的消息摘要,压缩+加密+hash算法的结合体,是绝对不可逆的。

算法原理:

  • 步骤一:数据填充。对消息进行数据填充,使消息的长度对512取模得448,设消息长度为X,即满 足X mod 512=448。根据此公式得出需要填充的数据长度。填充方法:在消息后面进行填充,填充第一位为1,其余为0。
  • 步骤二:添加消息长度。在第一步结果之后再填充上原消息的长度,可用来进行的存储长度为64位。如果消息长度大于264,则只使用其低64位的值,即(消息长度 对 264取模)。在此步骤进行完毕后,最终消息长度就是512的整数倍。
  • 步骤三:初始化链接变量。MD5使用4个32位的寄存器A、B、C、D,最开始存放4个固定的32位初始链接变量,这些参数用于第一轮迭代。
  • 步骤四:分组处理。将每个分组(512比特)分成16个小组,每个小组32位,这些分组参与每轮16步的函数运算,输出为32位值,经过4轮(共有四个轮函数)共64步之后,得到的4个寄存器的值分别于输入链接变量进行模加,即得到此次分组处理的输入链接变量。第四轮最后一步完成后,再与该分组最初的寄存器的初值相加,然后把A、B、C、D的值作为下一个迭代压缩的链接变量输入,直到最后一个消息分组得到的A、B、C、D寄存器值级联输出作为128比特的消息散列值。

​ 此处需要特别指出的是,在MD5的代码实现中,要特别注意小端序大端序的问题,这个问题如果不注意的话会导致MD5计算出错。而MD5的所有数据计算都是基于小端序的。

小端字节序(Little Endian):低位字节存放在低内存地址,高位字节存放在高内存地址端。 大端字节序(Big Endian):高位字节存放在低内存地址,低位字节存放在高内存地址端。

​ 在步骤二中添加消息长度就要按照小端序的方法填充长度,同时轮函数中各个参数也要按照小端序来计算,这点一定要特别注意。

​ 还有对于需要处理多个分组的情况,要做好A、B、C、D寄存器的及时更新,否则无法得到正确的MD5值。

代码如下:

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
import math

# 字符串转为2进制
def str2bin(s):
text = ""
for i in s:
text += '{:0>8}'.format(bin(ord(i))[2:])
return text

# 附加填充,输入为字母明文,输出为二进制
def additonal_filling(data):
bin_data = str2bin(data)
origi_mess_len = len(bin_data)
if origi_mess_len > math.pow(2,64):
print('Message too long!')
return "0"
else:
bit_origi_mess_len = f'{bin(origi_mess_len)[2:]:0>64}'
mod_remain = origi_mess_len % 512 # 余数
if mod_remain < 449:
padding_len = 448 - mod_remain
else:
padding_len = 448 - mod_remain + 512
if padding_len == 1:
bin_data += '1'
elif padding_len > 1:
bin_data = bin_data + '1' + '0' * (padding_len-1)
left = bit_origi_mess_len[:32]
right = bit_origi_mess_len[32:]
left = left[24:32] + left[16:24] + left[8:16] + left[:8]
right = right[24:32] + right[16:24] + right[8:16] + right[:8]
# 32为为一组
bin_data += (right + left)
return bin_data



# 迭代压缩,输出为分组比特消息数组,每组的长度为512bit
def iter_compress(bdata):
group_mess = [[]*16] # 分组消息数组
print(len(bdata))
for i in range(len(bdata)//512):
temp = bdata[i*512:i*512+512]
for j in range(16):
print(temp[j*32:j*32+32])
group_mess[i].append(temp[j*32:j*32+32])
return group_mess

# 小端序处理 @input hex
def little_endian(x,n):
x = f'{bin(x)[2:]:0>{n}}'
ans = ""
for i in range(n//8,0,-1):
ans += x[(i-1)*8:i*8]
return int(ans,2)


# 由于逻辑非比较特殊,所以另外实现一下,输入为16进制数据
def not_operate(data):
data = f'{bin(data)[2:]:0>32}'
out = ""
for i in data:
if i == "0":
out += "1"
else:
out += "0"
return int(out,2)


# 四个非线性函数,输入均为32bit的三个数据
# @input hex
def F(x, y, z):
return (x&y) | (not_operate(x) & z)

def G(x,y,z):
return (x & z) | (y & not_operate(z))

def H(x,y,z):
return (x ^ y ^ z)

def I(x,y,z):
return y ^ (x | not_operate(z))

def rotate_move(x,n):
x = f'{bin(x)[2:]:0>32}'
return int(x[n:] + x[:n],2)

# t[i],返回10进制
def get_t(i):
return int(math.pow(2,32) * abs(math.sin(i)))

# @input digital
def FF(a,b,c,d,m,s,Ti):
# m = int(m,2)
m = little_endian(int(m,2),32)
t = a + F(b,c,d) + m + Ti
t = t % (2**32)
a = (rotate_move(t,s) + b) % (2**32)
return a

def GG(a,b,c,d,m,s,Ti):
m = little_endian(int(m,2),32)
t = a + G(b,c,d) + m + Ti
t = t % (2**32)
a = (rotate_move(t,s) + b) % (2**32)
return a

def HH(a,b,c,d,m,s,Ti):
m = little_endian(int(m,2),32)
t = a + H(b,c,d) + m + Ti
t = t % (2**32)
a = (rotate_move(t,s) + b) % (2**32)
return a

def II(a,b,c,d,m,s,Ti):
m = little_endian(int(m,2),32)
t = a + I(b,c,d) + m + Ti
t = t % (2**32)
a = (rotate_move(t,s) + b) % (2**32)
return a

def step_function(M):
global A
global B
global C
global D
# 复制前一分组的链接变量
AA = A
BB = B
CC = C
DD = D
for i in range(len(M)):
# 第一轮循环
A = FF(A,B,C,D,M[i][0],7,get_t(1))
D = FF(D,A,B,C,M[i][1],12,get_t(2))
C = FF(C,D,A,B,M[i][2],17,get_t(3))
B = FF(B,C,D,A,M[i][3],22,get_t(4))
A = FF(A,B,C,D,M[i][4],7,get_t(5))
D = FF(D,A,B,C,M[i][5],12,get_t(6))
C = FF(C,D,A,B,M[i][6],17,get_t(7))
B = FF(B,C,D,A,M[i][7],22,get_t(8))
A = FF(A,B,C,D,M[i][8],7,get_t(9))
D = FF(D,A,B,C,M[i][9],12,get_t(10))
C = FF(C,D,A,B,M[i][10],17,get_t(11))
B = FF(B,C,D,A,M[i][11],22,get_t(12))
A = FF(A,B,C,D,M[i][12],7,get_t(13))
D = FF(D,A,B,C,M[i][13],12,get_t(14))
C = FF(C,D,A,B,M[i][14],17,get_t(15))
B = FF(B,C,D,A,M[i][15],22,get_t(16))

# 第二轮循环
A = GG(A,B,C,D,M[i][1],5,get_t(17))
D = GG(D,A,B,C,M[i][6],9,get_t(18))
C = GG(C,D,A,B,M[i][11],14,get_t(19))
B = GG(B,C,D,A,M[i][0],20,get_t(20))
A = GG(A,B,C,D,M[i][5],5,get_t(21))
D = GG(D,A,B,C,M[i][10],9,get_t(22))
C = GG(C,D,A,B,M[i][15],14,get_t(23))
B = GG(B,C,D,A,M[i][4],20,get_t(24))
A = GG(A,B,C,D,M[i][9],5,get_t(25))
D = GG(D,A,B,C,M[i][14],9,get_t(26))
C = GG(C,D,A,B,M[i][3],14,get_t(27))
B = GG(B,C,D,A,M[i][8],20,get_t(28))
A = GG(A,B,C,D,M[i][13],5,get_t(29))
D = GG(D,A,B,C,M[i][2],9,get_t(30))
C = GG(C,D,A,B,M[i][7],14,get_t(31))
B = GG(B,C,D,A,M[i][12],20,get_t(32))

# 第三轮循环
A = HH(A,B,C,D,M[i][5],4,get_t(33))
D = HH(D,A,B,C,M[i][8],11,get_t(34))
C = HH(C,D,A,B,M[i][11],16,get_t(35))
B = HH(B,C,D,A,M[i][14],23,get_t(36))
A = HH(A,B,C,D,M[i][1],4,get_t(37))
D = HH(D,A,B,C,M[i][4],11,get_t(38))
C = HH(C,D,A,B,M[i][7],16,get_t(39))
B = HH(B,C,D,A,M[i][10],23,get_t(40))
A = HH(A,B,C,D,M[i][13],4,get_t(41))
D = HH(D,A,B,C,M[i][0],11,get_t(42))
C = HH(C,D,A,B,M[i][3],16,get_t(43))
B = HH(B,C,D,A,M[i][6],23,get_t(44))
A = HH(A,B,C,D,M[i][9],4,get_t(45))
D = HH(D,A,B,C,M[i][12],11,get_t(46))
C = HH(C,D,A,B,M[i][15],16,get_t(47))
B = HH(B,C,D,A,M[i][2],23,get_t(48))

# 第四轮循环
A = II(A,B,C,D,M[i][0],6,get_t(49))
D = II(D,A,B,C,M[i][7],10,get_t(50))
C = II(C,D,A,B,M[i][14],15,get_t(51))
B = II(B,C,D,A,M[i][5],21,get_t(52))
A = II(A,B,C,D,M[i][12],6,get_t(53))
D = II(D,A,B,C,M[i][3],10,get_t(54))
C = II(C,D,A,B,M[i][10],15,get_t(55))
B = II(B,C,D,A,M[i][1],21,get_t(56))
A = II(A,B,C,D,M[i][8],6,get_t(57))
D = II(D,A,B,C,M[i][15],10,get_t(58))
C = II(C,D,A,B,M[i][6],15,get_t(59))
B = II(B,C,D,A,M[i][13],21,get_t(60))
A = II(A,B,C,D,M[i][4],6,get_t(61))
D = II(D,A,B,C,M[i][11],10,get_t(62))
C = II(C,D,A,B,M[i][2],15,get_t(63))
B = II(B,C,D,A,M[i][9],21,get_t(64))

A = (AA + A) % 2**32
B = (BB + B) % 2**32
C = (CC + C) % 2**32
D = (DD + D) % 2**32
AA = A
BB = B
CC = C
DD = D

def encrypt(word):
global A,B,C,D
# 初始化链接向量
A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
bintext = additonal_filling(word)
bdata = bintext
group_mess = [[]*16] # 分组消息数组
for i in range(16):
group_mess[0].append("")
for i in range(len(bdata)//512):
temp = bdata[i*512:i*512+512]
for j in range(16):
group_mess[0][j] = temp[j*32:j*32+32]
step_function(group_mess)
A = hex(A)[2:]
B = hex(B)[2:]
C = hex(C)[2:]
D = hex(D)[2:]
# 按小端字节序级联输出
out = ""
for item in (A,B,C,D):
for i in range(8//2):
out += item[(3-i)*2:(3-i)*2+2]
return out

if __name__ == '__main__':
word1 = "iscbupt"
word2 = "Beijing University of Posts and TelecommunicationsBeijing University of Posts and Telecommunications"
word3 = "State Key Laboratory of Networking and Switching"
word4 = "Hello! Bob, I'm Alice! We could communicate with each other now, It's so great!"
print(word1)
print(encrypt(word1))
print(word2)
print(encrypt(word2))

实例演示:

demo

安全性分析

​ MD5算法是一种哈希算法,所以对于MD5算法的安全问题主要在于它是否具有足够的抗碰撞性。

​ 在碰撞攻击方面,王小云教授研究很深入,她的成果集中在加速构造碰撞对。原来理论上构造出一个MD5碰撞对需要2^64次尝试,而现在只需要2^39次,其算法大大加速了这一过程。但从应用场景上来看,它本身并不具备太多的应用价值,因为构造出的碰撞很可能毫无意义。它的价值在于,在此算法基础上衍生出来的一系列MD5的算法,能够在部分场景下,构造出一个有意义的伪造信息,并且MD5值保持不变。所以,单单看这个算法本身就说MD5不安全,有些夸大其实。但是,后续的那些算法出现之后,MD5的安全性就真的有些令人担忧了,也就是下文要说的两种算法。

  • 哈希长度扩展攻击,具体细节可以参考大牛道哥的博文 http://blog.chinaunix.net/uid-27070210-id-3255947.html,简单说来就是在已知输入M的长度(注意是长度)和其MD5值的情况下,可以在原文M后面附加任意内容,同时能够推算出新的MD5。在某些将MD5作为签名手段的系统中,攻击者可以在原文M后面随意添加内容同时能够提供正确的MD5值。 在校学习平台上就有类似的题目

    存在这一问题的原因是算法使用了Merkle–Damgård construction进行数据的压缩,不止MD5,很多流行的算法都存在这个问题,比如SHA1。

  • 特定前缀攻击。两个不同的exe程序会在屏幕上打出不同的字符,但是他们的MD5值确是相同的,exe程序下载地址如下 link,专家还给出了MD5碰撞快读生成器。

面对这两个攻击,一个提高MD5安全性的有效手段是 加盐(每一个口令同一个叫做”盐“(salt)的n位随机数相关联 )

实用性分析:

​ 即使MD5现在已经被证明不是百分百安全的,但是被攻破只是有限情况下的个例,对于大多数安全性要求不是很高的应用中,MD5依然拥有广泛的使用空间。MD5具有压缩性,容易计算,抗修改性和强抗碰撞性等特点,在实际应用中,其结果方便存储,在对文件加密上有很大的优势(只需要32位字符串就能对一个巨大的文件进行验证完整性 ),且加密损耗低,对性能要求较低,计算迅速。由于其不可逆的特性,在实际应用中可以用来用户密码,请求参数校验,文件校验等用途。

公钥密码

RSA公钥加密体制

​ RSA公钥加密算法是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。1987年7月首次在美国公布,当时他们三人都在麻省理工学院工作实习。RSA就是他们三人姓氏开头字母拼在一起组成的。RSA是目前最有影响力和最常用的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准,是一种非对称加密算法。RSA是目前最重要的网络加密算法。

算法原理:

RSA算法基于一个十分简单的数论事实:将两个大质数相乘十分容易,但是想要对其乘积进行因式分解却极其困难

​ 第一步

选定两个质数p、q,实际应用中这两个数越大安全性越高。

​ 第二步

计算p、q的乘积,即n = p*q,n的二进制表示时所占的二进制位数就是密钥长度,实际应用中密钥长度一般为1024位,对于更高保密级别的应用则为2048位。

​ 第三步

计算n的 欧拉函数 φ(n) = (p-1)*(q-1),为了保持连贯性,欧拉函数先按下不表

​ 第四步

随机选定一个数e1,要求1 < e1 < φ(n),并且要求e1与n互质(实际应用中这个数字常选择65537),不知道什么是互质请点击这里

​ 第五步

寻找一个e2,要求 e1 * e2 ≡ 1 (mod φ(n)),好像是可以用扩展欧几里得算法 算出来,但是恕本人实在对数学不感冒,这个就略过了,想学的自己百度吧。

​ 第六步

封装(n,e1)公钥(n,e2)私钥

​ 至此,所有准备工作完成。

​ 加密和解密

先介绍一下加解密的公式,假定明文为A,那么,
密文B≡A^e1 mod n,要传输给对方的就是B
对方得到B之后利用私钥进行恢复,公式A≡B^e2 mod n,从而得到明文A。

​ 假定我选择了p = 5,q = 7,那么相应的n = 35,φ(n) = 24,再假定我选择了e1 = 5,那么e2 = 29(别问我怎么算出来的,我是不会告诉你我是编代码试出来的!!),那么我的公钥就是(5,35),私钥就是(29,35)。那么接下来就开始我们的秘密通信(^▽^)。

假定要传输的明文为: 32
注意:传输的内容必须为整数,并且要小于n,如果要传送字符串,可以用ascii码或unicode 编码传输。

​ 加密

A = 32,则B=A^e1 mod n = 2,将密文B发送,这个过程使用公钥进行加密

​ 解密

A = B^e2 mod n = 32 ,成功得到明文32!

简单证明一下上述算法的正确性:

欧拉定理

若n,a为正整数,且n,a互质,则
$a^{φ(n)} ≡ 1 (mod \; n)$

​ φ(n)为 欧拉函数 ,欧拉函数是小于n的正整数中与n互质的数的个数,下面介绍一个性质

如果n可以分解为两个互质的整数p、q的乘积,那么有
φ(n)= (p-1) * (q-1)

​ 接下来要证明的就是为什么下面两个式子可以互换实现

B=A^e1 mod n
A=B^e2 mod n

​ 解密规则为

A=B^e2 mod n

​ 根据加密规则

B = A^e1 mod n
B = A^e1 - kn

​ 代入解密式中

(A^e1 - kn)^e2 ≡ A (mod n)

​ 等于证

$A^{e1*e2} ≡ m (mod \; n)$


欧拉定理 可以得到

e1*e2 ≡ 1 [ mod φ(n)]
e1*e2 ≡ hφ(n)+1

​ 代入前面的式子可以得到

$A^{hφ(n)+1} \; ≡ m (mod\;n)$

​ 上式恒成立,则算法正确性得证。

代码如下:

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
77
78
79
80
81
82
83
84
85
86
import gmpy2 as gp
import math
import sys

# 字符串转为2进制
def str2bin(s):
text = ""
for i in s:
text += '{:0>8}'.format(bin(ord(i))[2:])
return text

def bin2str(s):
text = ""
for i in range(len(s)//8):
if int(s[i*8:i*8+8], 2) == 0:
continue
text += chr(int(s[i*8:i*8+8], 2))
return text

def fastExpMod(b, e, m):
result = 1
while e != 0:
if (e&1) == 1:
# ei = 1, then mul
result = (result * b) % m
e >>= 1
b = (b*b) % m
return result

# 加密函数,输入为plain字符明文,n,e
def rsa_encrypt(plain):
global n
global e
# 将明文转为比特串
bitplian = str2bin(plain)
group_len = int(math.log(n,2)) - 1
arr_group = []
if (len(bitplian) % group_len) != 0:
bitplian += "0"*(group_len-(len(bitplian) % group_len))
for i in range(len(bitplian) // group_len):
arr_group.append(bitplian[i*group_len:i*group_len+group_len])
cipher = ""
for item in arr_group:
ci = fastExpMod(int(item,2),e,n)
cipher += f'{bin(ci)[2:]:0>{group_len+2}}'
return hex(int(cipher,2))[2:]


# 解密函数,输入为cipehr16进制密文,n,d
def rsa_decrypt(cipher):
global n
global d
bitcipher = bin(int(cipher,16))[2:]
temp_len = int(math.log(n,2)) + 1
if (len(bitcipher) % temp_len) != 0:
bitcipher = "0"*(temp_len - (len(bitcipher) % temp_len)) + bitcipher
group_len = int(math.log(n,2)) + 1
arr_group = []
for i in range(len(bitcipher) // group_len):
arr_group.append(bitcipher[i*group_len:i*group_len+group_len])
bitplain = ""
for item in arr_group:
# mi = (int(item,2)**d % n)
mi = fastExpMod(int(item,2),d,n)
bitplain += f'{bin(mi)[2:]:0>{group_len-2}}'
return bin2str(bitplain)

p = 2147483647
q = 1000000007
n = p * q
pi_n = (p-1) * (q-1)
e = 65537
d = int(gp.invert(e,pi_n))

if __name__ == "__main__":
mode = sys.argv[1]
if mode == 'e':
plain = input("Plz input message: ")
cipher = rsa_encrypt(plain)
print("cipher: ", cipher)
elif mode == 'd':
cipher = input("Plz input cipher: ")
plain = rsa_decrypt(cipher)
print("plain: ",plain)
else:
pass

实例演示:

demo

安全性分析

​ 到目前为止,世界上还没有任何可靠的攻击RSA算法的方式 。然而即便RSA算法目前来说是安全可靠的,但是错误的应用场景,错误的环境配置,以及错误的使用方法,都会导致RSA的算法体系出现问题,从而也派生出针对各种特定场景下的RSA攻击方法。 此处指简单列举一些攻击方法

  • 直接分解n。一般这种情况是由于n较小,或者使用已经使用过的p、q造成的,这样会造成RSA直接被破解

  • 低加密指数攻击。当e=3时,如果明文过小,导致明文的三次方仍然小于n,那么通过直接对密文三次开方,即可得到明文。

    当e=3时,如果明文过小,导致明文的三次方仍然小于n,那么通过直接对密文三次开方,即可得到明文。

    即:

如果e=3,且$ m^e<{n} $,那么:

​ $ c= m^e,$ $e=3$

​ $ m=sqrt[3]{c}$

如果明文的三次方比n大,但是不是足够大,那么设k,有:

​ $ c= m^e+kn$

爆破k,如果$ c-kn $能开三次根式,那么可以直接得到明文。

  • 低加密指数广播攻击。如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。

    即,选取了相同的加密指数e(这里取e=3),对相同的明文m进行了加密并进行了消息的传递,那么有:

    ​ $ c_1equiv m^e$ $mod$ $n_1$

    ​ $ c_2equiv m^e$ $mod$ $n_2$

    ​ $ c_3equiv m^e$ $mod$ $n_3$

    对上述等式运用中国剩余定理,在e=3时,可以得到:

    ​ $ c_xequiv m^3$ $mod$ $n_1n_2n_3$

    通过对$ c_x $进行三次开方可以求得明文。

  • 公模攻击。如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密,那么就可以在不分解n的情况下还原出明文m的值。

    即:

    ​ $ c_1equiv m^{e_1}$ $mod$ $n$

    ​ $ c_2equiv m^{e_2}$ $mod$ $n$

    此时不需要分解n,不需要求解私钥,如果两个加密指数互素,就可以通过共模攻击在两个密文和公钥被嗅探到的情况下还原出明文m的值。


​ 由于RSA良好的安全性,RSA可用来电子签名中来确认通信双方身份。


通过对RSA的分析可知,RSA的安全性是基于大数的难分解性的,所以应尽可能选择足够大的p、q,目前大素数的产生依然是一个世界难题,这里展示一个素性判断算法miller-rabin算法,可以利用此算法判断一个数是不是素数从而穷举产生大素数。

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
from random import randint
import math

def xn_mod_p2(x, n, p):
res = 1
# n_bin = bin(n)[2:]
n_bin = bin(int(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

def miller_rabin_witness(a, p):
if p == 1:
return False
if p == 2:
return True
#p-1 = u*2^t 求解 u, t
n = p - 1
t = int(math.floor(math.log(n, 2)))
u = 1
while t > 0:
u = n / 2**t
if n % 2**t == 0 and u % 2 == 1:
break
t = t - 1
b1 = b2 = xn_mod_p2(a, u, p)
for i in range(1, t + 1):
b2 = b1**2 % p
if b2 == 1 and b1 != 1 and b1 != (p - 1):
return False
b1 = b2
if b1 != 1:
return False
return True
def prime_test_miller_rabin(p, k):
while k > 0:
a = randint(1, p - 1)
if not miller_rabin_witness(a, p):
return False
k = k - 1
return True

num = input(u"请输入要进行Miller-Rabin算法检测的数:")
if prime_test_miller_rabin(int(num),10):
print (u"{0}大概率是素数".format(num))
else:
print (u"{0}是合数 ".format(num))

实例演示:

demo

通信过程模拟

​ 有了前面的算法基础,我们现在可以模拟出一个从Alice到Bob的通信过程,步骤如下:

demo

​ 接下来用代码详细模拟了一下该过程

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
import rsa
import md5
import des

print("现在开始模拟Alice到Bob之间的通信过程:")
print()
print('*******Alice的发送准备*********')
print()
message = "Hello! Bob, I'm Alice! We could communicate with each other now, It's so great!"

# 设定message哈希值
message_hash = md5.encrypt(message)
sign = rsa.rsa_encrypt(message_hash)
key = "infosecu"
print("Alice想要发送到明文信息: ",message)
print("Alice的DES秘钥:", key)
print("消息哈希(用于检验消息完整性): ",message_hash)
print("Alice签名: ", sign)

print()
print('公开信道上传输DES加密数据')
print()
print('*******sending...**********')
print()
send_mess = des.encrypt(message,key)
send_sign = des.encrypt(sign,key)
print("message: ",send_mess)
print("sign: ",send_sign)
print("message_hash: ",message_hash)
print()
print('********sending finish*******')
print()
print()
print("********Bob处理收到的信息********")
print()
print("DES解密对应的内容:")
b_sign = des.decrypt(send_sign,key)
b_mess = des.decrypt(send_mess,key)
print("Alice发送的明文message: ",b_mess)
print("消息签名sign: ",b_sign)
print()
b_mess_hash = md5.encrypt(message)
print("此时Bob自己求出明文哈希值: ", b_mess_hash)
print("之后与Alice发送的消息哈希进行校验")
print("...****....")

print(b_mess_hash,"==",message_hash,"消息在传输过程中没有出错! 但是无法确定是否是Alice所发。")
print()

vert = rsa.rsa_decrypt(sign)
print("Bob对签名进行RSA解密: ",vert)
print("对解密后的签名值与自己计算出的MD5值相比较来验证发送方身份..")
print("verting.....")
if vert == b_mess_hash:
print("message is ok. 此时Bob可以确认从Alice处收到了完整的信息。")
else:
print("message is broken.")
print()
print("通信过程完成,Bob收到了Alice的信息!")

实例演示:

demo

-------------本文结束感谢您的阅读-------------
您今天怎么辣么迷人!