密码学学习记录｜hash sha1 算法

密码学 · 2021-12-16 · 1503 次浏览

密码学学习记录 4 / 15

维基百科

SHA-1（英语：Secure Hash Algorithm 1，中文名：安全散列算法1）是一种密码散列函数，美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦资料处理标准（FIPS）。SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。

参考资料

  • 1、rfc3174
  • 2、sha1 wikipedia
  • 3、文内关于 sha1 的部分描述，皆是来自网上博客文章

SHA1 算法描述（初学很多原理不太清楚，哪里描述有误，还望巨巨巨佬指点）

  • 1、数据填充

sha1 与 md5 相同

  • 2、长度填充

与 md5 有些区别，大小端相反

  • 3、数据分组处理（比 md5 多的一步）

经过添加位数处理的明文，其长度正好为 512 位的整数倍，然后按 512 位的长度进行分组，可以得到一定数量的明文分组，我们用 Y0，Y1，……YN-1 表示这些明文分组。对于每一个明文分组，都要重复反复的处理，这些与 MD5 都是相同的。
而对于每个 512 位的明文分组，SHA1 将其再分成 16 份更小的明文分组，称为子明文分组，每个子明文分组为 32 位，我们且使用 M[t]（t= 0, 1,……15）来表示这 16 个子明文分组。然后需要将这 16 个子明文分组扩充到 80 个子明文分组，我们将其记为 W[t]（t= 0, 1,……79），扩充的具体方法是：当 0≤t≤15 时，Wt = Mt；当 16≤t≤79 时，Wt = ( Wt-3 xor Wt-8 xor Wt-14 xor Wt-16) <<< 1，从而得到80个子明文分组。

  • 4、初始常量（五个常量，四个常数）
H = [0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0]
K = [0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6]
  • 5、四轮循环计算, 一共 80 步
TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t)
E = D
D = C
C = S^30(B)
B = A
A = TEMP
  • f 函数
f(t;B,C,D) = (B & C) | ((~B) & D)        # ( 0 <= t <= 19)
f(t;B,C,D) = B ^ C ^ D                   # (20 <= t <= 39)
f(t;B,C,D) = (B & C) | (B & D) | (C & D) # (40 <= t <= 59)
f(t;B,C,D) = B ^ C ^ 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)

代码实现 C

没找到 python 的实现，就随便找了个 C 的实现，用作后面参考

#ifndef _SHA1_H_
#define _SHA1_H_
typedef struct SHA1Context {
    unsigned Message_Digest[5];
    unsigned Length_Low;
    unsigned Length_High;
    unsigned char Message_Block[64];
    int Message_Block_Index;
    int Computed;
    int Corrupted;
} SHA1Context;

void SHA1Reset(SHA1Context *);

int SHA1Result(SHA1Context *);

void SHA1Input(SHA1Context *, const char *, unsigned);

#endif

#define SHA1CircularShift(bits, word) ((((word) << (bits)) & 0xFFFFFFFF) | ((word) >> (32-(bits))))

void SHA1ProcessMessageBlock(SHA1Context *);

void SHA1PadMessage(SHA1Context *);

void SHA1Reset(SHA1Context *context) {// 初始化动作
    context->Length_Low = 0;
    context->Length_High = 0;
    context->Message_Block_Index = 0;

    context->Message_Digest[0] = 0x67452301;
    context->Message_Digest[1] = 0xEFCDAB89;
    context->Message_Digest[2] = 0x98BADCFE;
    context->Message_Digest[3] = 0x10325476;
    context->Message_Digest[4] = 0xC3D2E1F0;

    context->Computed = 0;
    context->Corrupted = 0;
}

int SHA1Result(SHA1Context *context) {// 成功返回1，失败返回0
    if (context->Corrupted) {
        return 0;
    }
    if (!context->Computed) {
        SHA1PadMessage(context);
        context->Computed = 1;
    }
    return 1;
}

void SHA1Input(SHA1Context *context, const char *message_array, unsigned length) {
    if (!length) return;

    if (context->Computed || context->Corrupted) {
        context->Corrupted = 1;
        return;
    }

    while (length-- && !context->Corrupted) {
        context->Message_Block[context->Message_Block_Index++] = (*message_array & 0xFF);

        context->Length_Low += 8;

        context->Length_Low &= 0xFFFFFFFF;
        if (context->Length_Low == 0) {
            context->Length_High++;
            context->Length_High &= 0xFFFFFFFF;
            if (context->Length_High == 0) context->Corrupted = 1;
        }

        if (context->Message_Block_Index == 64) {
            SHA1ProcessMessageBlock(context);
        }
        message_array++;
    }
}

void SHA1ProcessMessageBlock(SHA1Context *context) {
    const unsigned K[] = {0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6};
    int t;
    unsigned temp;
    unsigned W[80];
    unsigned A, B, C, D, E;

    for (t = 0; t < 16; t++) {
        W[t] = ((unsigned) context->Message_Block[t * 4]) << 24;
        W[t] |= ((unsigned) context->Message_Block[t * 4 + 1]) << 16;
        W[t] |= ((unsigned) context->Message_Block[t * 4 + 2]) << 8;
        W[t] |= ((unsigned) context->Message_Block[t * 4 + 3]);
    }

    for (t = 16; t < 80; t++) W[t] = SHA1CircularShift(1, W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16]);

    A = context->Message_Digest[0];
    B = context->Message_Digest[1];
    C = context->Message_Digest[2];
    D = context->Message_Digest[3];
    E = context->Message_Digest[4];

    for (t = 0; t < 20; t++) {
        temp = SHA1CircularShift(5, A) + ((B & C) | ((~B) & D)) + E + W[t] + K[0];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = SHA1CircularShift(30, B);
        B = A;
        A = temp;
    }
    for (t = 20; t < 40; t++) {
        temp = SHA1CircularShift(5, A) + (B ^ C ^ D) + E + W[t] + K[1];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = SHA1CircularShift(30, B);
        B = A;
        A = temp;
    }
    for (t = 40; t < 60; t++) {
        temp = SHA1CircularShift(5, A) + ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = SHA1CircularShift(30, B);
        B = A;
        A = temp;
    }
    for (t = 60; t < 80; t++) {
        temp = SHA1CircularShift(5, A) + (B ^ C ^ D) + E + W[t] + K[3];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = SHA1CircularShift(30, B);
        B = A;
        A = temp;
    }
    context->Message_Digest[0] = (context->Message_Digest[0] + A) & 0xFFFFFFFF;
    context->Message_Digest[1] = (context->Message_Digest[1] + B) & 0xFFFFFFFF;
    context->Message_Digest[2] = (context->Message_Digest[2] + C) & 0xFFFFFFFF;
    context->Message_Digest[3] = (context->Message_Digest[3] + D) & 0xFFFFFFFF;
    context->Message_Digest[4] = (context->Message_Digest[4] + E) & 0xFFFFFFFF;
    context->Message_Block_Index = 0;
}

void SHA1PadMessage(SHA1Context *context) {
    if (context->Message_Block_Index > 55) {
        context->Message_Block[context->Message_Block_Index++] = 0x80;
        while (context->Message_Block_Index < 64) context->Message_Block[context->Message_Block_Index++] = 0;
        SHA1ProcessMessageBlock(context);
        while (context->Message_Block_Index < 56) context->Message_Block[context->Message_Block_Index++] = 0;
    } else {
        context->Message_Block[context->Message_Block_Index++] = 0x80;
        while (context->Message_Block_Index < 56) context->Message_Block[context->Message_Block_Index++] = 0;
    }
    context->Message_Block[56] = (context->Length_High >> 24) & 0xFF;
    context->Message_Block[57] = (context->Length_High >> 16) & 0xFF;
    context->Message_Block[58] = (context->Length_High >> 8) & 0xFF;
    context->Message_Block[59] = (context->Length_High) & 0xFF;
    context->Message_Block[60] = (context->Length_Low >> 24) & 0xFF;
    context->Message_Block[61] = (context->Length_Low >> 16) & 0xFF;
    context->Message_Block[62] = (context->Length_Low >> 8) & 0xFF;
    context->Message_Block[63] = (context->Length_Low) & 0xFF;

    SHA1ProcessMessageBlock(context);
}

代码实现 python

  • 1、定义常量
class SHA1(object):
    def __init__(self):
        self.H = [0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0]
        self.K = [0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6]
  • 2、循环左移函数
@staticmethod
def left_circular_shift(bits, k):
    bits = bits % (2 ** 32)
    k = k % (2 ** 32)
    return ((bits << k) ^ (bits >> (32 - k))) % (2 ** 32)
  • 3、数据填充函数
@staticmethod
def padding(input_str):
    input_str_bit_len = len(input_str) * 8
    input_str_len = input_str_bit_len % (2 ** 32)
    input_str += b'\x80'
    pad_leg = ((448 - (input_str_len + 8) % 512) % 512) // 8
    input_str = input_str + b'\x00' * pad_leg + input_str_len.to_bytes(8, byteorder='big')
    return input_str
  • 4、四个 F 函数
@staticmethod
def F1(b, c, d):
    return ((b & c) | ((~b) & d)) % (2 ** 32)

@staticmethod
def F2(b, c, d):
    return (b ^ c ^ d) % (2 ** 32)

@staticmethod
def F3(b, c, d):
    return ((b & c) | (b & d) | (c & d)) % (2 ** 32)

@staticmethod
def F4(b, c, d):
    return (b ^ c ^ d) % (2 ** 32)
  • 5、transform 函数

参考上述资料逻辑自行编写

最后

运行代码，结果相同

全部代码

您需要先支付 29.9元 才能查看此处内容！立即支付

注意该订单不支持退款，如有问题可联系博主

标签:
暂无评论

小爬爬

本文作者：
本文链接： https://www.qinless.com/?p=1262
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 qinless 的博客！
100

发表评论

返回顶部