SHA1算法分析与实现

简介

SHA(Secure Hash Algorithm) 安全哈希算法中的 SHA-1 产生 160 位的散列值,该算法的消息分组与填充方式都与 MD5 相同

算法实现过程

数据填充

SHA-1 与 MD5 一样。以 512bit 一个分组来处理数据,填充的方式与 MD5 一样。最终要处理的数据 bit 数需要满足 n(bit) = N*512+R

N 取自然数,R 为余数

当 R < 448 时,需要填充到 448 bit
当 R > 448 时,需要填充 512bit-R+448 bit
当 R = 448 时,仍然要填上一个 512bit 分组

添加长度信息

经过数据填充之后,还需要添加原文的二进制数据长度信息(原文的 bit 数),共 64bit (8 Bytes),若原文二进制数据长度大于 2^64bit,则只使用低 64bit 位

定义常量和操作

定义常量

常量 K(t) =
{
    0x5A827999 (0 <= t <= 19),
    0x6ED9EBA1 (20 <= t <= 39),
    0x8F1BBCDC (40 <= t <= 59),
    0xCA62C1D6 (60 <= t <= 79)
}

5 个初始的链接变量值为

H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0

定义操作

ft(B,C,D) =
{
    (B & C) | ((~B) & D)     ( 0 <= t <= 19),
    B ^ C ^ D     (20 <= t <= 39),
    (B & C) | (B & D) | (C & D)     (40 <= t <= 59),
    B ^ C ^ D     (60 <= t <= 79)
}

也有另外一种定义方法,两种方法算出的 Hash 值是相等的

#define F0(x,y,z) z^((x&(y^z)))
#define F1(x,y,z) (x^y^z)
#define F2(x,y,z) ((x&y) | (z&(x|y)))
#define F3(x,y,z) (x^y^z)

信息分组处理

将经过数据填充的信息以 512bit 为一组的标准来分组,用 Y0,Y1,……YN-1 表示这些分组
对于每一个 Y 分组,我们再将它分为 16 个 M 子分组(32bit,4字节,双字),用 M[t](t= 0, 1,……15)来表示这些子分组
然后需要将这 16 个子分组扩充到 80 个子分组,记为 W[t](t= 0, 1,……79)

扩充的具体方法是:
当 0 ≤ t≤ 15 时,W[t] = M[t]
当 16 ≤ t≤ 79 时,W[t] = ( W[t]-3 ⊕ W[t]-8 ⊕ W[t]-14 ⊕ W[t]-16) <<< 1
从而得到 80 个子分组(32bit)

哈希计算

每个分组进行一次处理,每次处理都要先进行扩充分组操作,扩充完之后再进行 80 个子分组的处理

对于 t = 0 到 79 执行如下计算

TEMP = S5(A) + ft(B,C,D) + E + W[t] + K[t];
E = D; D = C; C = S30(B); B = A; A = TEMP;

S 为循环左移函数

在处理完所有的子分组之后,执行

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

在所有的分组计算结束之后,最后的 H0 H1 H2 H3 H4 拼接即是 hash 结果

算法实现

Cpp

#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<int> X;//8*64=512,每个下标存放8位
int W[80];//32位为一组
int A, B, C, D, E;
int H0, H1, H2, H3, H4;//缓冲区寄存器,产生最后结果
int Turn;//加密分组数量
void printX() {//输出填充后的文本
    for (int i = 0; i < X.size(); i++) {
        printf("%02x", X[i]);
        if ((i + 1) % 4 == 0)
            printf(" ");
        if ((i + 1) % 16 == 0)
            printf("\n");
    }
}
int S(unsigned int x, int n) {//循环左移
    return x >> (32 - n) | (x << n);
}
void append(string m) {//文本的填充处理
    Turn = (m.size() + 8) / 64 + 1;
    X.resize(Turn * 64);
    int i = 0;
    for (; i < m.size(); i++) {
        X[i] = m[i];
    }
    X[i++] = 0x80;
    while (i < X.size() - 8) {
        X[i] = 0;
        i++;
    }
    long long int a = m.size() * 8;
    for (i = X.size() - 1; i >= X.size() - 8; i--) {
        X[i] = a % 256;
        a /= 256;
    }
}
void setW(vector<int> m, int n) {//W数组的生成
    n *= 64;
    for (int i = 0; i < 16; i++) {
        W[i] = (m[n + 4 * i] << 24) + (m[n + 4 * i + 1] << 16)
            + (m[n + 4 * i + 2] << 8) + m[n + 4 * i + 3];
    }
    for (int i = 16; i < 80; i++) {
        W[i] = S(W[i - 16] ^ W[i - 14] ^ W[i - 8] ^ W[i - 3], 1);
    }
}
int ft(int t) {//ft(B,C,D)函数
    if (t < 20)
        return (B & C) | ((~B) & D);
    else if (t < 40)
        return B ^ C ^ D;
    else if (t < 60)
        return (B & C) | (B & D) | (C & D);
    else
        return B ^ C ^ D;
}
int Kt(int t) {//常量K
    if (t < 20)
        return 0x5a827999;
    else if (t < 40)
        return 0x6ed9eba1;
    else if (t < 60)
        return 0x8f1bbcdc;
    else
        return 0xca62c1d6;
}
void sha1(string text) {
    H0 = A = 0x67452301;
    H1 = B = 0xefcdab89;
    H2 = C = 0x98badcfe;
    H3 = D = 0x10325476;
    H4 = E = 0xc3d2e1f0;
    append(text);
    printX();
    for (int i = 0; i < Turn; i++) {
        setW(X, i);
        for (int t = 0; t < 80; t++) {
            int temp = E + ft(t) + S(A, 5) + W[t] + Kt(t);
            E = D;
            D = C;
            C = S(B, 30); 
            B = A; 
            A = temp;
        }
        H0 = A = A + H0;
        H1 = B = B + H1;
        H2 = C = C + H2;
        H3 = D = D + H3;
        H4 = E = E + H4;
    }
    printf("%08x%08x%08x%08x%08x\n\n", H0, H1, H2, H3, H4);
}

int main() {

    string text;
    while (true)
    {
        cin >> text;
        sha1(text);
    }
    return 0;
}

python hashlib

import hashlib

sha1 = hashlib.sha1()
sha1.update(b'abc')
sha1.digest() # b'\xa9\x99>6G\x06\x81j\xba>%qxP\xc2l\x9c\xd0\xd8\x9d'
sha1.hexdigest() # a9993e364706816aba3e25717850c26c9cd0d89d

参考

1.FIPS PUB 180-1

Be the first to reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注

7 − 6 =