MD5算法基础实现

发表于 更新于 分类于
密码学作业

MD5算法基础实现

第6章Hash函数与消息认证.ppt 下载

源码：https://blog.csdn.net/adidala/article/details/28677393 ，为python2实现

改为python3：https://blog.csdn.net/sjxgghg/article/details/106361977

本贴代码引用自后者

方法

python内置map() 会根据提供的函数对指定序列做映射。

第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表。

总之就是可以少写很多range

1
2
3
4
5
6
7
8
9
10
11
12
13
# map(function, iterable, ...)

>>> def square(x) :            # 计算平方数
...     return x ** 2
>>> map(square, [1,2,3,4,5])   # 计算列表各个元素的平方
[1, 4, 9, 16, 25]

>>> map(lambda x: x ** 2, [1, 2, 3, 4, 5])  # 使用 lambda 匿名函数
[1, 4, 9, 16, 25]
 
# 提供了两个列表，对相同位置的列表数据进行相加
>>> map(lambda x, y: x + y, [1, 3, 5, 7, 9], [2, 4, 6, 8, 10])
[3, 7, 11, 15, 19]

代码

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
# 引入math模块，因为要用到sin函数
import math

# 定义常量，用于初始化128位变量，注意字节顺序，文中的A=0x01234567，这里低值存放低字节，即01 23 45 67，所以运算时A=0x67452301，其他类似。
# 这里用字符串的形势，是为了和hex函数的输出统一，hex(10)输出为'0xA',注意结果为字符串。
A = '0x67452301'
B = '0xefcdab89'
C = '0x98badcfe'
D = '0x10325476'
# 定义每轮中用到的函数。L为循环左移，注意左移之后可能会超过32位，所以要和0xffffffff做与运算，确保结果为32位。
F = lambda x, y, z: ((x & y) | ((~x) & z))
G = lambda x, y, z: ((x & z) | (y & (~z)))
H = lambda x, y, z: (x ^ y ^ z)
I = lambda x, y, z: (y ^ (x | (~z)))
L = lambda x, n: (((x << n) | (x >> (32 - n))) & 0xffffffff)
# 定义每轮中循环左移的位数，这里用4个元组表示,用元组是因为速度比列表快。
shi_1 = (7, 12, 17, 22) * 4
shi_2 = (5, 9, 14, 20) * 4
shi_3 = (4, 11, 16, 23) * 4
shi_4 = (6, 10, 15, 21) * 4
# 定义每轮中用到的M[i]次序。
m_1 = (i for i in range(16))
m_2 = ((1 + 5 * i) % 16 for i in range(16))
m_3 = ((5 + 3 * i) % 16 for i in range(16))
m_4 = (7 * i % 16 for i in range(16))


def reverse_hex(hex_str):
    """翻转十六进制数的顺序：'0x01234567' => '0x67452301'"""
    hex_str = hex_str[2:]
    hex_str_list = []
    for i in range(0, len(hex_str), 2):
        hex_str_list.append(hex_str[i:i + 2])
    hex_str_list.reverse()
    hex_str_result = '0x' + ''.join(hex_str_list)
    return hex_str_result


def T(i):
    """定义函数，用来产生常数T[i]，常数有可能超过32位，同样需要&0xffffffff操作。注意返回的是十进制的数。"""
    result = (int(2 ** 32 * abs(math.sin(i)))) & 0xffffffff
    return result


def shift(shift_list):
    """用来将列表中的元素循环右移。"""
    shift_list = [shift_list[3], shift_list[0], shift_list[1], shift_list[2]]
    return shift_list


def fun(fun_list, f, m, shi):
    """主要的函数，参数为当做种子的列表，每轮用到的F，G，H，I，生成的M[]，以及循环左移的位数。该函数完成一轮运算。"""
    count = 0
    global Ti_count
    # 引入全局变量，T(i)是从1到64循环的。
    while count < 16:
        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)
        fun_list = shift(fun_list)
        count += 1
        Ti_count += 1
        # print (fun_list)
    return fun_list


def genM16(order, ascii_list, f_offset):
    """该函数生成每轮需要的M[]，最后的参数是为了当有很多分组时，进行偏移。"""
    ii = 0
    m16 = [0] * 16
    f_offset = f_offset * 64
    for i in order:
        i = i * 4
        m16[ii] = '0x' + ''.join((ascii_list[i + f_offset] + ascii_list[i + 1 + f_offset] + ascii_list[
            i + 2 + f_offset] + ascii_list[i + 3 + f_offset]).split('0x'))
        ii += 1
    for c in m16:
        ind = m16.index(c)
        m16[ind] = reverse_hex(c)
    return m16


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


def fill_input():
    """输入数据并填充，非中文"""
    input_m = input('msg > ')
    # 填充过程中需要1个‘1’和(488-msg_lenth-1)个‘0’
    ascii_list = list((map(hex, map(ord, input_m))))
    msg_lenth = len(ascii_list) * 8
    # 对每一个输入先添加一个'0x80'，即'10000000',后填入(488-msg_lenth-8)个0
    ascii_list.append('0x80')
    while (len(ascii_list) * 8 + 64) % 512 != 0:
        ascii_list.append('0x00')
    # 附加消息，如果附加消息长度大于2**64，使用低64位
    # 最后64为存放消息长度，注意长度存放顺序低位在前,所以是左填充0后反转
    msg_lenth_0x = hex(msg_lenth)[2:]
    msg_lenth_0x = '0x' + msg_lenth_0x.rjust(16, '0') # 0，高位，低位
    msg_lenth_0x_big_order = reverse_hex(msg_lenth_0x)[2:]  # 低位，高位，0
    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])
    ascii_list.extend(msg_lenth_0x_list)
    return ascii_list


if __name__ == '__main__':
    """主函数"""
    abcd_list = [A, B, C, D]
    Ti_count = 1
    ascii_list = fill_input()
    # 对每个分组进行4轮运算
    for i in range(0, len(ascii_list) // 64):
        # 将最初128位种子存放在变量中，
        aa, bb, cc, dd = abcd_list
        # 根据顺序产生每轮M[]列表
        order_1 = genM16(m_1, ascii_list, i)
        order_2 = genM16(m_2, ascii_list, i)
        order_3 = genM16(m_3, ascii_list, i)
        order_4 = genM16(m_4, ascii_list, i)
        # 主要四轮运算，注意打印结果列表已经被进行过右移操作！
        abcd_list = fun(abcd_list, F, order_1, shi_1)
        # print ('--------------------------------------')
        abcd_list = fun(abcd_list, G, order_2, shi_2)
        # print ('--------------------------------------')
        abcd_list = fun(abcd_list, H, order_3, shi_3)
        # print ('--------------------------------------')
        abcd_list = fun(abcd_list, I, order_4, shi_4)
        # print ('--------------------------------------')
        # 将最后输出与最初128位种子相加，注意，最初种子不能直接使用abcd_list[0]等，因为abcd_list已经被改变
        output_a = hex((int(abcd_list[0], 16) + int(aa, 16)) & 0xffffffff)
        output_b = hex((int(abcd_list[1], 16) + int(bb, 16)) & 0xffffffff)
        output_c = hex((int(abcd_list[2], 16) + int(cc, 16)) & 0xffffffff)
        output_d = hex((int(abcd_list[3], 16) + int(dd, 16)) & 0xffffffff)
        # 将输出放到列表中，作为下一次128位种子
        abcd_list = [output_a, output_b, output_c, output_d]
        # 将全局变量Ti_count恢复，一遍开始下一个分组的操作。
        Ti_count = 1
        # 最后调用函数，格式化输出
    print('md5 > ' + show_result(abcd_list))