【Python实现】SHA-1单向散列函数

前言

这是我大三上学期的一个作品。然后为了能够显示中间过程，用面向过程的思想编写。

注：强烈建议用 jupyter 运行代码
n 代表运行顺序
- In [n]: 代表第 n 步运行
- Out [n]: 代表第 n 步运行对应的输入
- In [ ]: 代表不运行

准备统一数据结构（以65535为例）

In [1]:

import numpy as np

32位二进制（列表形式）

In [2]:

# 示例：array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], dtype=np.uint8)

# 十进制 转 32位二进制
def Dec_to_Bin(Dec):
    Dec %= 2**32
    return np.array([Dec >> tmp & 1 for tmp in range(32)][::-1], dtype = np.uint8)

# 十六进制 转 32位二进制
def Hex_to_Bin(Hex):
    return Dec_to_Bin(eval('0x' + Hex))

十进制

In [3]:

# 示例：65535

# 二进制 转 十进制
def Bin_to_Dec(Bin):
    Dec = 0
    for i in range(len(Bin)):
        Dec += Bin[-i-1] * 2 ** i
    return Dec

# 十六进制 转 十进制
def Hex_to_Dec(Hex):
    return eval('0x' + Hex)

8位十六进制（字符串形式）

In [4]:

# 示例：'0000ffff'

# 32位二进制 转 8位十六进制
def Bin_to_Hex(Bin):
    Hex = ''
    for i in range(len(Bin)//4):
        tmp = hex(Bin_to_Dec(Bin[4 * i : 4 * (i + 1)]))[-1]
        Hex += str(tmp)
    return Hex

# 十进制 转 8位十六进制
def Dec_to_Hex(Dec):
    Dec %= 2**32
    Hex = ''
    for tmp1 in [hex(Dec >> (tmp2 * 4) & 0xf)[-1] for tmp2 in range(8)][::-1]:
        Hex += str(tmp1)
    return Hex

64位十六进制（字符串形式）

In [5]:

# 十进制 转 64位十六进制
def Dec_to_Hex_64(Dec):
    Hex = ''
    for tmp1 in [hex((Dec) >> (tmp2 * 4) & 0xf)[-1] for tmp2 in range(64)][::-1]:
        Hex += str(tmp1)
    return Hex

定义循环左移和按位取反函数

In [6]:

# 循环左移
def cycle_left(X, n, dtype):
    if dtype == 'Bin':
        n = n % 32
        return Bin_to_Dec(np.append(X[n:], X[:n]))
    elif dtype == 'Dec':
        return cycle_left(Dec_to_Bin(X), n, 'Bin')
    elif dtype == 'Hex':
        return cycle_left(Hex_to_Bin(X), n, 'Bin')
    else:
        raise TypeError("二进制请输入np_bin和Bin，十进制请输入num和Dec，十六进制请输入str和Hex")

In [7]:

# 按位取反
def invert(X, dtype):
    if dtype == 'Bin':
        for i in range(len(X)):
            if X[i] == 0:
                X[i] = 1
            else:
                X[i] = 0
        return Bin_to_Dec(X)
    elif dtype == 'Dec':
        return invert(Dec_to_Bin(X), 'Bin')
    elif dtype == 'Hex':
        return invert(Hex_to_Bin(X), 'Bin')
    else:
        raise TypeError("二进制请输入np_bin和Bin，十进制请输入num和Dec，十六进制请输入str和Hex")

单向散列函数SHA-1

In [8]:

%%html

Out [8]:

第一步：填充

对消息进行填充，使其长度为512比特的整数倍。512比特作为一个分组。
In [9]:

# 消息m
m = b'Hello.' * 1

In [10]:

# 消息 -> ASCII码 -> 二进制
ASCII = np.frombuffer(m, dtype = np.uint8)
Bit = np.unpackbits(ASCII)

In [11]:

# 假设消息 m 的长度为 l 比特
l = len(Bit)
print("原始消息长度为 %d 比特" % l)

Out [11]:

原始消息长度为 48 比特

In [12]:

# 在消息的末尾添加一个1比特的数值"1"，N_512_Bit 代表 512整数倍比特
ONE = np.ones(1, dtype = np.uint8)
N_512_Bit = np.append(Bit, ONE)

In [13]:

# N 为512比特长度的倍数
# k 为需要添加的0的个数，满足 l + 1 + k = 448mod512
N = 1
while True:
    if l + 1 + 64 <= 512 * N:
        k = 512 * N - l - 1 - 64
        break
    N += 1

In [14]:

# 添加消息长度（不包括最后一个分组）
print("需要添加 %d 个'0'" % k)
ZEROS = np.zeros(k, dtype = np.uint8)
N_512_Bit = np.append(N_512_Bit, ZEROS)

Out [14]:

需要添加 399 个'0'

In [15]:

# 保存原始消息的长度到最后一个分组的最后64比特
last_64_bit = [l >> d & 1 for d in range(64)][::-1]
last_64_bit = np.array(last_64_bit, dtype = np.uint8)
N_512_Bit = np.append(N_512_Bit, last_64_bit)

In [16]:

# 填充后的结果展示（二进制表示）
for i in range(len(N_512_Bit)):
    print(N_512_Bit[i], end = '')
    if (i + 1) % 64 == 0:
        print()
    elif (i + 1) % 8 == 0:
        print(end = ' ')
    else:
        pass

Out [16]:

01001000 01100101 01101100 01101100 01101111 00101110 10000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00110000

计算每个分组的 W0 ~ W79

根据输入分组的512比特,计算出80个32比特的值（W0 ~ W79）
In [17]:

def message_extension(_512_bit):
    
    # 存放 W0 ~ W79
    W = {}
    
    for i in range(80):
        # 将输入分组的512比特分成32比特×16组，并命名为W0-W15
        if i < 16:
            W["W" + str(i)] = Bin_to_Dec(_512_bit[32*i:32*(i+1)])
        
        # 计算剩下的W16-W79
        else:
            W_i_16 = W["W" + str(i - 16)]
            W_i_14 = W["W" + str(i - 14)]
            W_i_8  = W["W" + str(i - 8)]
            W_i_3  = W["W" + str(i - 3)]
            result = W_i_16 ^ W_i_14 ^ W_i_8 ^ W_i_3
            
            # 循环左移1比特
            W["W" + str(i)] = cycle_left(result, 1, 'Dec')

    return W

分组处理

对每个输入分组依次进行80个步骤的处理：将5个缓冲区中的值与与输入分组的信息进行混合后在进行80个步骤的处理
算出W0-W79之后，对输入分组还要进行下一页图所示的80个步骤的处理，其目的是根据输入分组的信息来改变内部状态。所有的输入分组都要执行这一操作。
160比特的内部状态是通过名为A,B,C,D,E的5个32比特的缓冲区来表示的。这些缓冲区和W0-W79是不同的概念。这一步是将5个缓冲区的值与输入分组的信息进行混合，然后再执行80个步骤的处理。
这80个步骤所完成的操作，就是将输入分组的512比特的数据与SHA-1所保持的160比特的内部状态（5个缓冲区）进行混合。通过上述80个步骤的反复执行，SHA-1就能够将已经填充的消息全部混入这160比特的内部状态中，而SHA-1所输出的散列值就是所有处理结束之后最终的内部状态（160比特）。
In [18]:

%%html

Out [18]:

In [19]:

# 按512比特进行分组
def split_group(N_512_Bit, N):
    print("有 %d 个组" % N)
    Group = {}
    for i in range(N):
        Group["Group" + str(i)] = message_extension(N_512_Bit[512 * i : 512 * (i + 1)])
    return Group

In [20]:

# 将填充后的消息 m' 按512比特进行分组（程序中用 m_ 代替 m'）
Group = split_group(N_512_Bit, N)

Out [20]:

有 1 个组

单步处理

分组处理是由80个步骤的处理组成的，其中每个步骤都是基于W0-W79使内部状态进行复杂变化的处理
在完成一个步骤后，缓冲区A,B,C,D的内容会被分别复制到B,C,D,E中（其中B要循环左移30比特之后再复制），而缓冲分区E的内容则会与其它缓冲区的内容以及Wt、Kt相加后再被复制到缓冲区A中
In [21]:

%%html

Out [21]:

In [22]:

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
E = 0xC3D2E1F0

In [23]:

for j in range(len(Group)):
    
    A_ori = A
    B_ori = B
    C_ori = C
    D_ori = D
    E_ori = E
    
    for i in range(80):
        
        if i < 20:
            f = (B & C) | (invert(B, 'Dec') & D)
            K = 0x5A827999
        elif 20 <= i < 40:
            f = B ^ C ^ D
            K = 0x6ED9EBA1
        elif 40 <= i < 60:
            f = (B & C) | (C & D) | (D & B)
            K = 0x8F1BBCDC
        elif 60 <= i < 80:
            f = B ^ C ^ D
            K = 0xCA62C1D6
        
        W = Group['Group' + str(j)]['W' + str(i)]
        
        tmp = D
        D = C
        C = cycle_left(B, 30, "Dec")
        B = A
        A = E + f + cycle_left(A, 5, "Dec") + W + K
        E = tmp
        
    A = A + A_ori
    B = B + B_ori
    C = C + C_ori
    D = D + D_ori
    E = E + E_ori

结果

In [24]:

def Binary_to_Hexadecimal(np_bin):
    SHA1 = ''
    for i in range(len(sha1)//4):
        H = hex(Bin_to_Dec(sha1[4 * i : 4 * (i + 1)]))[-1]
        SHA1 += str(H)
    return SHA1

sha1 = np.array([], dtype = np.uint8)
for each in [A, B, C, D, E]:
    sha1 = np.append(sha1, Dec_to_Bin(each))
SHA1 = Bin_to_Hex(sha1)

验证

In [25]:

import hashlib
sha1 = hashlib.sha1(b'Hello.').hexdigest()

In [26]:

print(SHA1)
print(sha1)
SHA1 == sha1

Out [26]:

9b56d519ccd9e1e5b2a725e186184cdc68de0731
9b56d519ccd9e1e5b2a725e186184cdc68de0731
True

【Python实现】SHA-1单向散列函数

Python相关栏目本月热门文章