SHA-1

一、概述

SHA-1（Secure Hash Algorithm 1）是一种广泛应用的哈希算法，由美国国家安全局（NSA）设计，首次发布于 1993 年。作为 SHA 系列算法的一员，SHA-1 在数字签名、数据完整性验证和密码学应用中有重要意义。然而，随着计算能力的提升，SHA-1 的安全性逐渐受到威胁，已不再推荐用于强安全需求的应用。

SHA-1 是第一代 SHA 算法标准，后来的 SHA-224、SHA-256、SHA-384 和 SHA-512 被统称为 SHA-2。

它可以将长度小于比特的信息输入，输入消息以512比特的分组为单位处理，输出固定长度的160比特（16字节）散列值。主循环4轮，每轮20次操作。

二、主要步骤

数据预处理

• 填充消息：首先，在原始消息的末尾添加一个 1 比特，然后填充 0 比特，直到消息长度模 512 等于 448。
• 附加长度：在填充后的消息末尾附加一个 64 比特的无符号整数，表示原始消息的长度（以比特为单位）。

消息分组

将预处理后的消息分割成多个 512 比特的分组。

初始化常量

初始化 5 个 32 位的常量，这些常量将作为初始的哈希值：

h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

压缩函数处理

总体

对于每个 512 比特的分组，执行以下操作：

• 扩展消息：将 512 比特的分组扩展为 80 个 32 位的字。
• 初始化工作变量：将当前的哈希值赋值给 5 个工作变量（a、b、c、d、e）。
• 80 轮迭代：在每一轮中，根据当前轮数选择不同的逻辑函数和常量，更新工作变量。
• 更新哈希值：将工作变量的值累加到当前的哈希值上。

步函数

对于消息按照如下的方式进行处理:

• 前16个字节([0, 15])，转换成32位无符号整数。
• 对于后面的字节([16, 79])按照下面的公式进行处理

W(t) = ROTL^1 (W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)) //ROTL^n (x):表示对32比特的变量x循环左移n比特。

• 令A = H0, B = H1, C = H2, D = H3, E = H4
• 做如下80轮的散列操作

TEMP = ROTL^5 (A) + f(t;B,C,D) + E + W(t) + K(t);
E = D;
D = C;
C = ROTL^30 (B);
B = A;
A = TEMP;

• 令H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E

解释一下，其中f函数如下:

f(t;B,C,D) = (B AND C) OR ((NOT B) AND D)         ( 0 <= t <= 19)
f(t;B,C,D) = B XOR C XOR D                        (20 <= t <= 39)
f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D)  (40 <= t <= 59)
f(t;B,C,D) = B XOR C XOR D                        (60 <= t <= 79)

k函数如下:

K(t) = 0x5A827999         ( 0 <= t <= 19)
K(t) = 0x6ED9EBA1         (20 <= t <= 39)
K(t) = 0x8F1BBCDC         (40 <= t <= 59)
K(t) = 0xCA62C1D6         (60 <= t <= 79)

输出结果

将最终的 5 个 32 位哈希值（h0、h1、h2、h3、h4）拼接成一个 160 位的哈希结果。

三、完整代码

SHA-1.py

SHA-1_1.py

import math


# 异或算法
def xor_func(a, b):
    a = bin(a)[2:]  #将整数作为参数传递给bin函数，它就会返回一个字符串形式的二进制表示。
    b = bin(b)[2:]  #[2:]去掉二进制表示的'0b'前缀
    while len(a) < 32:
        a = '0' + a
    while len(b) < 32:
        b = '0' + b
    c = ''  #令c初始为空，异或后的值作为字符串拼接
    for i in range(0, 32):
        if a[i] == b[i]:  #对应位数上的值相等异或结果为0
            c = c + '0'
        else:            #反之位数为1
            c = c + '1'
    return c


# 与运算
def and_func(a, b):
    a = bin(a)[2:]
    b = bin(b)[2:]
    while len(a) < 32:
        a = '0' + a
    while len(b) < 32:
        b = '0' + b
    c = ''
    for i in range(0, 32):
        #两位同时为"1"，结果才为"1"，否则为0
        if a[i] == '1' and b[i] == '1':
            c = c + '1'
        else:
            c = c + '0'
    return c


# ROTL运算 即轮函数运算，压缩函数由 轮函数运算组成
def ROTL_func(a, n):
    a = a * 2 ** n  #幂运算符 ** 来表示次方，也可以用内置函数pow()
    #a=a*pow(2,n)
    t = int(a / 2 ** 32)
    a = a % (2 ** 32) + t
    return a


# 非门：输入端和输出端的电平状态总是反相的，所以非门运算就是1取0，0则取1
def NOT_func(a):
    a = bin(a)[2:]
    while len(a) < 32:
        a = '0' + a
    c = ''
    for ch in a:
        if ch == '0':
            c = c + '1'
        else:
            c = c + '0'
    return c


# 步函数算法编写
def step_func(W, list):
    A = list[0]
    B = list[1]
    C = list[2]
    D = list[3]
    E = list[4]
    t = 0
    # t=0-19的计算
    while t <= 19:
        k = 0x5A827999  # K1
        if t <= 15:
            w = W[t]
        else:
            #int(x,base) 可选参数 base，用于指定输入字符串的进制
            #下面即是将x转化为对应进制再进行异或运算
            w = xor_func(int(W[t - 3], 16), int(W[t - 8], 16))  # t>15后进行新的赋值
            w = xor_func(int(w, 2), int(W[t - 14], 16))
            w = xor_func(int(w, 2), int(W[t - 16], 16))
            temp = w[0]
            w = w[1:] + temp
            w = hex(int(w, 2))
            W.append(w)
        t += 1
        x = and_func(int(B), int(C))  #与
        y = NOT_func(B)  #非
        z = and_func(int(y, 2), int(D))  #与
        a = int(xor_func(int(x, 2), int(z, 2)), 2)  # Ch(x,y,z)
        e = E
        E = D
        D = C
        C = ROTL_func(int(B), 30) % (2 ** 32)
        B = A
        A = int(ROTL_func(int(A), 5) + a + int(e) + int(w, 16) + int(k)) % (2 ** 32)

    # t=20-39的计算
    while t <= 39 and t >= 20:
        k = 0x6ED9EBA1  # K2
        w = xor_func(int(W[t - 3], 16), int(W[t - 8], 16))
        w = xor_func(int(w, 2), int(W[t - 14], 16))
        w = xor_func(int(w, 2), int(W[t - 16], 16))
        temp = w[0]
        w = w[1:] + temp
        w = hex(int(w, 2))
        W.append(w)

        x = int(xor_func(B, C), 2)  #
        y = int(xor_func(x, D), 2)  # Parity(x,y,z)
        e = E
        E = D
        D = C
        C = ROTL_func(int(B), 30) % (2 ** 32)
        B = A
        A = int(ROTL_func(int(A), 5) + y + int(e) + int(w, 16) + int(k)) % (2 ** 32)
        t += 1

    # t=40-59的计算
    while t <= 59 and t >= 40:
        k = 0x8f1bbcdc  # K3
        w = xor_func(int(W[t - 3], 16), int(W[t - 8], 16))
        w = xor_func(int(w, 2), int(W[t - 14], 16))
        w = xor_func(int(w, 2), int(W[t - 16], 16))
        temp = w[0]
        w = w[1:] + temp
        w = hex(int(w, 2))
        W.append(w)

        x = int(and_func(B, C), 2)  #
        y = int(and_func(B, D), 2)  #
        z = int(and_func(C, D), 2)  #
        xx = int(xor_func(x, y), 2)  #
        yy = int(xor_func(xx, z), 2)  # Maj(x,y,z)
        e = E
        E = D
        D = C
        C = ROTL_func(int(B), 30) % (2 ** 32)
        B = A
        A = int(ROTL_func(int(A), 5) + yy + int(e) + int(w, 16) + int(k)) % (2 ** 32)
        t += 1

    # t=60-79的计算
    while t <= 79 and t >= 60:
        k = 0xca62c1d6  # K4
        w = xor_func(int(W[t - 3], 16), int(W[t - 8], 16))
        w = xor_func(int(w, 2), int(W[t - 14], 16))
        w = xor_func(int(w, 2), int(W[t - 16], 16))
        temp = w[0]
        w = w[1:] + temp
        w = hex(int(w, 2))
        W.append(w)

        x = int(xor_func(B, C), 2)  #
        y = int(xor_func(x, D), 2)  # Parity(x,y,z)
        e = E
        E = D
        D = C
        C = ROTL_func(int(B), 30) % (2 ** 32)
        B = A
        A = int(ROTL_func(int(A), 5) + y + int(e) + int(w, 16) + int(k)) % (2 ** 32)
        t += 1

    AA = 0x67452301
    BB = 0xEFCDAB89
    CC = 0x98BADCFE
    DD = 0x10325476
    EE = 0xC3D2E1F0

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

    # 给列表传值
    list[0] = A
    list[1] = B
    list[2] = C
    list[3] = D
    list[4] = E


# 读取需要加密的明文
def main():
    A = 0x67452301
    B = 0xEFCDAB89
    C = 0x98BADCFE
    D = 0x10325476
    E = 0xC3D2E1F0
    list = [A, B, C, D, E]

    print('请输入明文:')
    m = input()

    W = []
    l = len(m)
    x = hex(len(m) * 8)
    n = 0  # 字符串的读取位置
    while 1:
        # 长度大于64，即所占字节大于512，需要分段处理
        if l > 64:
            m = m[n:]
            nn = 0
            p = ''
            for i in range(1, 64):
                if int(nn / 4) * 4 + 4 <= len(m):
                    p = p + hex(ord(m[nn]))[2:4]
                    if (nn + 1) % 4 == 0:
                        W.append(p)
                        p = ''
                    nn = nn + 1
            step_func(W, list)
            n += 64
            l -= 64
            W = []
        # 长度在56与64之间，若要字节在448到512之间，若要其字节满足与512模448同余，还需额外添加使其达到1024字节
        elif l >= 56 and l <= 64:
            mm = m[n:]
            nn = 0
            p = ''
            j = 0
            for i in range(1, 64):
                if int(nn / 4) * 4 + 4 <= len(mm):
                    p = p + hex(ord(mm[nn]))[2:4]
                    if (nn + 1) % 4 == 0:
                        W.append(p)
                        j += 1
                        p = ''
                    nn = nn + 1
                else:
                    break
            judge = 0
            for i in range(0, 4):
                if nn < len(mm):
                    p = p + hex(ord(mm[nn]))[2:4]
                    nn = nn + 1
                else:
                    if judge == 0:
                        p = p + '80'
                        judge = 1
                    elif judge == 1:
                        p = p + '00'
            W.append(p)
            j += 1
            if j == 15:
                p = '00000000'
                W.append(p)
            step_func(W, list)
            W = []
            p = '00000000'
            for i in range(0, 14):
                W.append(p)
            length = len(x) - 2
            p = ''
            for i in range(0, 16 - length):
                p = p + '0'
            p = p + x[2:]
            W.append(p[0:8])
            W.append(p[8:16])
            step_func(W, list)
            break
        # 长度小于56，字节数在0到448之间，需要补全字节使其长度为512
        elif l < 56:
            mm = m[n:]
            nn = 0
            p = ''
            for i in range(1, 56):
                if int(nn / 4) * 4 + 4 <= len(mm):
                    p = p + hex(ord(mm[nn]))[2:4]
                    if (nn + 1) % 4 == 0:
                        W.append(p)
                        p = ''
                    nn = nn + 1
                else:
                    break
            judge = 0
            for i in range(0, 4):
                if nn < len(mm):
                    p = p + hex(ord(mm[nn]))[2:4]
                    nn = nn + 1
                else:
                    if judge == 0:
                        p = p + '80'
                        judge = 1
                    elif judge == 1:
                        p = p + '00'
            W.append(p)
            for i in range(int(len(mm) / 4) + 1, 14):
                p = '00000000'
                W.append(p)
            length = len(x) - 2
            p = ''
            for i in range(0, 16 - length):
                p = p + '0'
            p = p + x[2:]
            W.append(p[0:8])
            W.append(p[8:16])
            step_func(W, list)
            break

    c = hex(list[0])[2:] + hex(list[1])[2:] + hex(list[2])[2:] + hex(list[3])[2:] + hex(list[4])[2:]
    print('\n最终密文为:', c)

main()

四、实例

SHA1(“iscbupt”)=”664dc9f017dc1aee4a4366bcfb8511afc89f9430”