一、实验目的
深度理解MD4(SHA-1,SM3)算法的工作原理，理解单向散列函数的应用，体会区块链挖矿的难度系数、加深对单向散列函数性质的理解。
二、实验器材
pycharm+python3.11
三、实验内容
1.实验要求：自己配置python环境，编写MD4(SHA-1, SM3)算法实现程序，运行MD4(SHA-1,SM3)程序，演示MD4(SHA-1,SM3)算法的计算过程。
(1)编写程序实现任意消息的填充分组。
1 flag = 1 # 补1标志位，补一次1后置0
2 while len(M) % 512 != 448:
3 if flag:
4 M += '1'
5 flag = 0
6 else:
7 M += '0'
8 M += "{:064b}".format(l) # 末尾64位写入长度，空余补位补0
9 M = hex(int(M, 2))[2:] # 这种转换会用到很多次，2进制转16进制，M现在是一个16进制字符串，如'1342a2c12...'
10 Mn = [] # 存储每个32位的字，因为M中一个字符4位（16进制），所以取M中的8个为一组，按要求将M分割成16个32位的字，故这里8*4=32，32*16=512
11 for i in range(16):
12 Mn.append(M[8*i: 8*i+8])
(2)编写程序实现消息扩展将每个分组中的16个32比特字扩展为80个32比特字。
1 W = ['' for _ in range(80)] # 存储80份扩展子明文 2 for i in range(80): 3 if 16 <= i <= 79: 4 # 16-79要进行异或运算，这里先转换成十进制（W中存的是16进制字符串，str无法运算） 5 temp = int(W[i-3], 16) ^ int(W[i-8], 6 16) ^ int(W[i-14], 16) ^ int(W[i-16], 16) 7 8 W[i] = hex(roll_left(temp, 1))[2:].zfill(8) # 循环左移1位 9 else: 10 W[i] = Mn[i]
(3)分别编写程序实现循环移位、32比特与(或、非)运算、模232加运算，建议将这些程序作为独立的程序，在整个运算中调用这些程序完成单向散列函数的计算。
def roll_left(num, k): """循环左移函数 Parameters ---------- num : int 输入一个数字，2进制、10进制等均可 k : int 左移位数 Returns ------- int 返回一个int结果 """ num_bin = bin(num)[2:].zfill( 32) out = num_bin[k % len(num_bin):]+num_bin[:k % len(num_bin)] # 注意预防溢出 return int(out, 2) # 二进制左移完成后转化成10进制输出 def ft(b, c, d, t): """ft为逻辑函数 Parameters ---------- b : int B值 c : int C值 d : int D值 t : int 轮次 Returns ------- int 运算结果 """ if t >= 0 and t <= 19: return ((b & c) | (~b & d)) elif t >= 20 and t <= 39: return (b ^ c ^ d) elif t >= 40 and t <= 59: return ((b & c) | (b & d) | (d & c)) elif t >= 60 and t <= 79: return (b ^ c ^ d) for t in range(80): tmp = B B = A A = ((((E + ft(tmp, C, D, t)) % (2**32)+roll_left(A, 5)) % (2**32)+int(W[t], 16)) % (2**32)+K[t//20]) % (2**32) # 预防溢出进行取模运算 E = D D = C C = roll_left(tmp, 30)
(4)用第二步的80个32比特字迭代修改初始的单向散列函数值，并输出最后的单向散列函数值。
SHA-1杂凑算法实现：
1 A, B, C, D, E = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0 # 常量
2 K = [0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6] # 常量
3
4 str = input("输入明文：\n").encode('utf-8') # 这里对输入明文进行编码，str为bytes型
5 l = len(str)*8 # 每个字符8位
6 # python中二进制是字符串，不保留高位的0，这里使用zfill补高位0，如十进制6->110->0110，M这里是用了一个很长的字符串如:'11001010100011...'来表示原始数据
7 M = bin(int(str.hex(), 16))[2:].zfill(l)
8
9 # [可选项] 下面的函数仅仅显示输入明文的ascii，末尾为长度，该段显示的是补位后的
10 for i in range(64):
11 if i < len(str):
12 print(str[i], end=' ')
13 elif i < len(str)+1:
14 print('128', end=' ')
15 elif i < 63:
16 print('0', end=' ')
17 else:
18 print(l)
19
20 flag = 1 # 补1标志位，补一次1后置0
21 while len(M) % 512 != 448:
22 if flag:
23 M += '1'
24 flag = 0
25 else:
26 M += '0'
27 M += "{:064b}".format(l) # 末尾64位写入长度，空余补位补0
28 M = hex(int(M, 2))[2:] # 这种转换会用到很多次，2进制转16进制，M现在是一个16进制字符串，如'1342a2c12...'
29 Mn = [] # 存储每个32位的字，因为M中一个字符4位（16进制），所以取M中的8个为一组，按要求将M分割成16个32位的字，故这里8*4=32，32*16=512
30 for i in range(16):
31 Mn.append(M[8*i: 8*i+8])
32
33
34 def roll_left(num, k):
35 """循环左移函数
36
37 Parameters
38 ----------
39 num : int
40 输入一个数字，2进制、10进制等均可
41 k : int
42 左移位数
43
44 Returns
45 -------
46 int
47 返回一个int结果
48 """
49 num_bin = bin(num)[2:].zfill(
50 32)
51 out = num_bin[k % len(num_bin):]+num_bin[:k % len(num_bin)] # 注意预防溢出
52 return int(out, 2) # 二进制左移完成后转化成10进制输出
53
54
55 W = ['' for _ in range(80)] # 存储80份扩展子明文
56 for i in range(80):
57 if 16 <= i <= 79:
58 # 16-79要进行异或运算，这里先转换成十进制（W中存的是16进制字符串，str无法运算）
59 temp = int(W[i-3], 16) ^ int(W[i-8],
60 16) ^ int(W[i-14], 16) ^ int(W[i-16], 16)
61
62 W[i] = hex(roll_left(temp, 1))[2:].zfill(8) # 循环左移1位
63 else:
64 W[i] = Mn[i]
65
66
67 def ft(b, c, d, t):
68 """ft为逻辑函数
69
70 Parameters
71 ----------
72 b : int
73 B值
74 c : int
75 C值
76 d : int
77 D值
78 t : int
79 轮次
80
81 Returns
82 -------
83 int
84 运算结果
85 """
86 if t >= 0 and t <= 19:
87 return ((b & c) | (~b & d))
88 elif t >= 20 and t <= 39:
89 return (b ^ c ^ d)
90 elif t >= 40 and t <= 59:
91 return ((b & c) | (b & d) | (d & c))
92 elif t >= 60 and t <= 79:
93 return (b ^ c ^ d)
94
95
96 Ap, Bp, Cp, Dp, Ep = A, B, C, D, E # 暂存初始值
97 for t in range(80):
98 tmp = B
99 B = A
100 A = ((((E + ft(tmp, C, D, t)) % (2**32)+roll_left(A, 5)) %
101 (2**32)+int(W[t], 16)) % (2**32)+K[t//20]) % (2**32) # 预防溢出进行取模运算
102 E = D
103 D = C
104 C = roll_left(tmp, 30)
105
106 #print(f" round{t+1} : {hex(A)} {hex(B)} {hex(C)} {hex(D)} {hex(E)}\n")
107 A, B, C, D, E = (Ap+A) % (2**32), (Bp+B) % (2**32), (Cp +
108 C) % (2**32), (Dp+D) % (2**32), (Ep+E) % (2**32)
109 # 相加运算，因为python不像c/c++可以使用unsigned char_32直接限制位数，因此要对位数进行限制
110 print("明文对应的杂凑码：\n", hex(A), hex(B), hex(C), hex(D), hex(E))
加密结果：
SM-3杂凑算法实现：
1 def rotation_left(x, num):
2 # 循环左移
3 num %= 32
4 left = (x << num) % (2 ** 32)
5 right = (x >> (32 - num)) % (2 ** 32)
6 result = left ^ right
7 return result
8
9
10 def Int2Bin(x, k):
11 x = str(bin(x)[2:])
12 result = "0" * (k - len(x)) + x
13 return result
14
15 class SM3:
16
17 def __init__(self):
18 # 常量初始化
19 self.IV = [0x7380166F, 0x4914B2B9, 0x172442D7, 0xDA8A0600, 0xA96F30BC, 0x163138AA, 0xE38DEE4D, 0xB0FB0E4E]
20 self.T = [0x79cc4519, 0x7a879d8a]
21 self.maxu32 = 2 ** 32
22 self.w1 = [0] * 68
23 self.w2 = [0] * 64
24
25 def ff(self, x, y, z, j):
26 # 布尔函数FF
27 result = 0
28 if j < 16:
29 result = x ^ y ^ z
30 elif j >= 16:
31 result = (x & y) | (x & z) | (y & z)
32 return result
33
34 def gg(self, x, y, z, j):
35 # 布尔函数GG
36 result = 0
37 if j < 16:
38 result = x ^ y ^ z
39 elif j >= 16:
40 result = (x & y) | (~x & z)
41 return result
42
43 def p(self, x, mode):
44 result = 0
45 # 置换函数P
46 # 输入参数X的长度为32bit(=1个字)
47 # 输入参数mode共两种取值：0和1
48 if mode == 0:
49 result = x ^ rotation_left(x, 9) ^ rotation_left(x, 17)
50 elif mode == 1:
51 result = x ^ rotation_left(x, 15) ^ rotation_left(x, 23)
52 return result
53
54 def sm3_fill(self, msg):
55 # 填充消息，使其长度为512bit的整数倍
56 # 输入参数msg为bytearray类型
57 # 中间参数msg_new_bin为二进制string类型
58 # 输出参数msg_new_bytes为bytearray类型
59 length = len(msg) # msg的长度（单位：byte）
60 l = length * 8 # msg的长度（单位：bit）
61
62 num = length // 64
63 remain_byte = length % 64
64 msg_remain_bin = ""
65 msg_new_bytes = bytearray((num + 1) * 64) ##填充后的消息长度，单位：byte
66
67 # 将原数据存储至msg_new_bytes中
68 for i in range(length):
69 msg_new_bytes[i] = msg[i]
70
71 # remain部分以二进制字符串形式存储
72 remain_bit = remain_byte * 8 # 单位：bit
73 for i in range(remain_byte):
74 msg_remain_bin += "{:08b}".format(msg[num * 64 + i])
75
76 k = (448 - l - 1) % 512
77 while k < 0:
78 # k为满足 l + k + 1 = 448 % 512 的最小非负整数
79 k += 512
80
81 msg_remain_bin += "1" + "0" * k + Int2Bin(l, 64)
82
83 for i in range(0, 64 - remain_byte):
84 str = msg_remain_bin[i * 8 + remain_bit: (i + 1) * 8 + remain_bit]
85 temp = length + i
86 msg_new_bytes[temp] = int(str, 2) # 将2进制字符串按byte为组转换为整数
87 return msg_new_bytes
88
89 def sm3_msg_extend(self, msg):
90 # 扩展函数: 将512bit的数据msg扩展为132个字（w1共68个字，w2共64个字）
91 # 输入参数msg为bytearray类型,长度为512bit=64byte
92 for i in range(0, 16):
93 self.w1[i] = int.from_bytes(msg[i * 4:(i + 1) * 4], byteorder="big")
94
95 for i in range(16, 68):
96 self.w1[i] = self.p(self.w1[i - 16] ^ self.w1[i - 9] ^ rotation_left(self.w1[i - 3], 15),
97 1) ^ rotation_left(self.w1[i - 13], 7) ^ self.w1[i - 6]
98
99 for i in range(64):
100 self.w2[i] = self.w1[i] ^ self.w1[i + 4]
101
102 # 测试扩展数据w1和w2
103 # print("w1:")
104 # for i in range(0, len(self.w1), 8):
105 # print(hex(self.w1[i]))
106 # print("w2:")
107 # for i in range(0, len(self.w2), 8):
108 # print(hex(self.w2[i]))
109
110 def sm3_compress(self, msg):
111 # 压缩函数
112 # 输入参数v为初始化参数，类型为bytes/bytearray，大小为256bit
113 # 输入参数msg为512bit的待压缩数据
114
115 self.sm3_msg_extend(msg)
116 ss1 = 0
117
118 A = self.IV[0]
119 B = self.IV[1]
120 C = self.IV[2]
121 D = self.IV[3]
122 E = self.IV[4]
123 F = self.IV[5]
124 G = self.IV[6]
125 H = self.IV[7]
126
127 for j in range(64):
128 if j < 16:
129 ss1 = rotation_left((rotation_left(A, 12) + E + rotation_left(self.T[0], j)) % self.maxu32, 7)
130 elif j >= 16:
131 ss1 = rotation_left((rotation_left(A, 12) + E + rotation_left(self.T[1], j)) % self.maxu32, 7)
132 ss2 = ss1 ^ rotation_left(A, 12)
133 tt1 = (self.ff(A, B, C, j) + D + ss2 + self.w2[j]) % self.maxu32
134 tt2 = (self.gg(E, F, G, j) + H + ss1 + self.w1[j]) % self.maxu32
135 D = C
136 C = rotation_left(B, 9)
137 B = A
138 A = tt1
139 H = G
140 G = rotation_left(F, 19)
141 F = E
142 E = self.p(tt2, 0)
143
144 # 测试IV的压缩中间值
145 # print("j= %d：" % j, hex(A)[2:], hex(B)[2:], hex(C)[2:], hex(D)[2:], hex(E)[2:], hex(F)[2:], hex(G)[2:], hex(H)[2:])
146
147 self.IV[0] ^= A
148 self.IV[1] ^= B
149 self.IV[2] ^= C
150 self.IV[3] ^= D
151 self.IV[4] ^= E
152 self.IV[5] ^= F
153 self.IV[6] ^= G
154 self.IV[7] ^= H
155
156 def sm3_update(self, msg):
157 # 迭代函数
158 # 输入参数msg为bytearray类型
159 # msg_new为bytearray类型
160 msg_new = self.sm3_fill(msg) # msg_new经过填充后一定是512的整数倍
161 n = len(msg_new) // 64 # n是整数，n>=1
162
163 for i in range(0, n):
164 self.sm3_compress(msg_new[i * 64:(i + 1) * 64])
165
166 def sm3_final(self):
167 digest_str = ""
168 for i in range(len(self.IV)):
169 digest_str += hex(self.IV[i])[2:]
170
171 return digest_str.upper()
172
173 def hashFile(self, filename):
174 with open(filename, 'rb') as fp:
175 contents = fp.read()
176 self.sm3_update(bytearray(contents))
177 return self.sm3_final()
178
179
180 if __name__ == "__main__":
181 msg1 = bytearray(b"abc")
182 print("msg1:", msg1.hex(), len(msg1))
183
184 test1 = SM3()
185 test1.sm3_update(msg1)
186 digest1 = test1.sm3_final()
187 print("digest1:", digest1)
188
189 msg2 = bytearray(b'abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd')
190 msg2 = bytes(msg2)
191 print("msg2:", msg2.hex(), len(msg2))
192
193 test2 = SM3()
194 test2.sm3_update(msg2)
195 digest2 = test2.sm3_final()
196 print("digest2:", digest2)
197
198 # 求大小为48M的文件的摘要，大约需要7分钟
199 # test3 = SM3()
200 # file_digest = test3.hashFile("test.exe")
201 # print('file_digest', file_digest)
加密结果：
