本文大纲

简介
MD5
SHA
- 实现流程
- 代码

Leopold

文章

分类

标签

github.com/SayNop

gitee.com/WhenTimeGoesBy

fur999immer@gmail.com

消息摘要算法

2024-04-06

CryptographyCryptographyMD5SHA

简介

消息摘要（Message Digest）是数字签名算法的核心，常用于验证数据完整性，包含MD，SHA，MAC三大种类
java中的equals方法在比较对象时，实际上比较的是两个对象的散列值hashCode()是否相同
任何消息经过散列函数处理后，都会得到唯一的散列值。这一过程称为“消息摘要”，其散列值称为“数字指纹”，自然其算法就是“消息摘要算法”
通过散列函数可获得对应的散列值，但不可通过该散列值反推其原始信息。这是消息摘要算法安全性的根本所在

MD5

MD5算法是典型的消息摘要算法，是计算机广泛使用的杂凑算法之一（又译摘要算法、散列算法）

补充：杂凑（Hash）算法的输出被称作杂凑值（hash value），输出长度与算法有关，与原文长度无关

MD5算法会输出128位的二进制摘要信息，转换为16进制得到32位字符串

实现流程

目标字符串以字符为单位转换成字符编码（ascii码/unicode码等），将字符编码转换为二进制码
明文末尾补1个1和n个0，使其对512取余为448
二进制码进行分组转换。即每以512位二进制码一组，最后一组数据位数448（保留64位）
保留64位处表明原文长度信息，记录原文的位长。以使最后一组也保持512位
将每个512分组再分出16个32位子分组

初始化幻数

A: 01 23 45 67 （16进制）
B: 89 ab cd ef （16进制）
C: fe dc ba 98 （16进制）
D: 76 54 32 10 （16进制）

A: 0x67452301
B: 0xefcdab89
C: 0x98badcfe
D: 0x10325476

A: 1732584193
B: 4023233417
C: 2562383102
D: 271733878

32位分组与幻数组合进行4轮（FF，GG，HH，II），每轮16次，共64次的位运算

位运算涉及常量：位移S与正弦函数表（sine table）

// 向左位移数
const unsigned int s[]={7,12,17,22,7,12,17,22,7,12,17,22,7,
    12,17,22,5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
    4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,6,10,
    15,21,6,10,15,21,6,10,15,21,6,10,15,21};

// unsigned int(abs(sin(i+1))*(2pow32))
const unsigned int k[] = {
    0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
    0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
    0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
    0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
    0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
    0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
    0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
    0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};
/* [
    3614090360, 3905402710, 606105819, 3250441966, 4118548399,1200080426, 2821735955, 4249261313,
    1770035416, 2336552879, 4294925233, 2304563134, 1804603682, 4254626195, 2792965006, 1236535329,
    4129170786, 3225465664, 643717713, 3921069994, 3593408605, 38016083, 3634488961, 3889429448,
    568446438, 3275163606, 4107603335, 1163531501, 2850285829, 4243563512, 1735328473, 2368359562,
    4294588738, 2272392833, 1839030562, 4259657740, 2763975236, 1272893353, 4139469664, 3200236656,
    681279174, 3936430074, 3572445317, 76029189, 3654602809, 3873151461, 530742520, 3299628645,
    4096336452, 1126891415, 2878612391, 4237533241, 1700485571, 2399980690, 4293915773, 2240044497,
    1873313359, 4264355552, 2734768916, 1309151649, 4149444226, 3174756917, 718787259, 3951481745
] */

A + BCD进行位运算结果 + 明文块 + 正弦常量。得到的结果，循环左移指定常量位数。得到的结果 + B = 返回值。示例代码FF，参考文章https://www.cnblogs.com/xiaxveliang/p/15004954.htmlopen in new window

// FF,GG,HH和II调用F,G,H,I函数进行进一步变换
private long FF(long a, long b, long c, long d, long x, long s, long ac) {
    a += F(b, c, d) + x + ac;
    // 循环左移s位
    //这里long型数据右移时使用无符号右移运算符>>>
    a = ((int) a << s) | ((int) a >>> (32 - s));
    a += b;
    return a;
}

计算过程中幻数ABCD也会改变。运算后每个512分组得到4个数值A、B、C、D，与拿到的A、B、C、D求和，作为下一组的幻数

// 一组中的第一轮运算FF为例
// 参数[4]: 明文数据块  参数[5]: 位移  参数[6]: 正弦函数表
// 返回值 - 新的A、B、C、D
a = FF(a, b, c, d, M0, 7, 0xd76aa478L);
d = FF(d, a, b, c, M1, 12, 0xe8c7b756L);
c = FF(c, d, a, b, M2, 17, 0x242070dbL);
b = FF(b, c, d, a, M3, 22, 0xc1bdceeeL);
a = FF(a, b, c, d, M4, 7, 0xf57c0fafL);
d = FF(d, a, b, c, M5, 12, 0x4787c62aL);
c = FF(c, d, a, b, M6, 17, 0xa8304613L);
b = FF(b, c, d, a, M7, 22, 0xfd469501L);
a = FF(a, b, c, d, M8, 7, 0x698098d8L); 
d = FF(d, a, b, c, M9, 12, 0x8b44f7afL);
c = FF(c, d, a, b, M10, 17, 0xffff5bb1L);
b = FF(b, c, d, a, M11, 22, 0x895cd7beL);
a = FF(a, b, c, d, M12, 7, 0x6b901122L);
d = FF(d, a, b, c, M13, 12, 0xfd987193L);
c = FF(c, d, a, b, M14, 17, 0xa679438eL);
b = FF(b, c, d, a, M15, 22, 0x49b40821L);

// a、b、c、d 为每一512bit分组的运算结果； 
// A、B、C、D 是下一组计算的输入参数；
// 若无下一个512bit分组 A、B、C、D 则为最终计算结果；
A = a + A;  
B = b + B; 
C = c + C; 
D = d + D;

字符串拼接最后一个512分组计算出的ABCD得到MD5结果

例子：目标字符串 A

A 的ascii码为65，ascii码的二进制码01000001。因此只有一个512分组
填充 0 位，直到总长度达到 448 位。01000001 10000000 00000000 ... (共 439 个 0)
补充长度信息。原文共一个字符，8位，保留64位为00000000 00000000 00000000 00000000 00000000 00000000 00000000 00001000

将其分为16个32位分组

01000001 10000000 00000000 00000000
... 14个全0分组 ...
00000000 00000000 00000000 00001000

与幻数进行4*16次位运算得到计算后的ABCD
将计算后的A 7fc56270 B e7a70fa8 C 1a5935b7 D 2eacbe29 拼接得到结果7fc56270e7a70fa81a5935b72eacbe29

代码

Java API

import java.io.UnsupportedEncodingException;

public class MD5 {

    public static String getMD5 (String data) {
        // 初始化
        MessageDigest messageDigest = null;
        try {
            // 获取md5算法
            messageDigest = MessageDigest.getInstance("MD5");
            messageDigest.reset();
            // 传入明文
            messageDigest.update(data.getBytes("UTF-8"));
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        }
    
        // 执行摘要
        byte[] byteArray = messageDigest.digest();
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < byteArray.length; i++) {
            // toHexString: 无符号生疏参数所表示的值转16进制
            // 取低8位后转16进制
            String hex = Integer.toHexString(0xFF & byteArray[i]);
      
            if (hex.length == 1)
                res.append("0");
            res.append(hex);
        }
        // 返回16位则切9-25
        return res.substring(8, 24).toString().toUpperCase();
        // 返回正常的32位 
        return res.toString().toUpperCase();
    }
}

Python实现。代码出自GPT：使用python编写md5算法的实现流程

import math
import struct


# 左旋转函数
def left_rotate(x, amount):
    x &= 0xFFFFFFFF  # 确保 x 是 32 位
    return ((x << amount) | (x >> (32 - amount))) & 0xFFFFFFFF

# MD5 主算法类
class MD5:
    def __init__(self):
        # 初始化常量
        self.s = [
            7, 12, 17, 22,  # 轮 1
            5, 9, 14, 20,   # 轮 2
            4, 11, 16, 23,  # 轮 3
            6, 10, 15, 21   # 轮 4
        ]
        
        # 常数 T(i) - 正弦表
        self.K = [int(abs(math.sin(i + 1)) * (2**32)) & 0xFFFFFFFF for i in range(64)]
        
        # 初始化缓冲区
        self.A = 0x67452301
        self.B = 0xEFCDAB89
        self.C = 0x98BADCFE
        self.D = 0x10325476

    def process_block(self, block):
        # 把 512 位块拆成 16 个 32 位的小块
        M = struct.unpack('<16I', block)
        
        A, B, C, D = self.A, self.B, self.C, self.D
        
        # 主循环
        for i in range(64):
            if 0 <= i <= 15:
                F = (B & C) | (~B & D)
                g = i
            elif 16 <= i <= 31:
                F = (D & B) | (~D & C)
                g = (5 * i + 1) % 16
            elif 32 <= i <= 47:
                F = B ^ C ^ D
                g = (3 * i + 5) % 16
            elif 48 <= i <= 63:
                F = C ^ (B | ~D)
                g = (7 * i) % 16
            
            F = (F + A + self.K[i] + M[g]) & 0xFFFFFFFF
            A = D
            D = C
            C = B
            B = (B + left_rotate(F, self.s[i % 4 + (i // 16) * 4])) & 0xFFFFFFFF
        
        # 更新缓冲区
        self.A = (self.A + A) & 0xFFFFFFFF
        self.B = (self.B + B) & 0xFFFFFFFF
        self.C = (self.C + C) & 0xFFFFFFFF
        self.D = (self.D + D) & 0xFFFFFFFF

    def update(self, message):
        # 预处理步骤：填充消息
        original_length_in_bits = (len(message) * 8) & 0xFFFFFFFFFFFFFFFF
        message += b'\x80'
        while len(message) % 64 != 56:
            message += b'\x00'
            
        # 添加消息长度 - 小端长整数 - Q: unsigned long long
        message += struct.pack('<Q', original_length_in_bits)
            
        # 处理每个 512 位块
        for i in range(0, len(message), 64):
            self.process_block(message[i:i+64])
    
    def digest(self):
        # 输出最终的 128 位摘要 - 小端 unsigned int
        return struct.pack('<4I', self.A, self.B, self.C, self.D)
    
    def hexdigest(self):
        # 将摘要转换为十六进制字符串
        # 02表示大端补0填充到2位，x表示16进制 - b二进制，o八进制，d十进制
        return ''.join(f'{x:02x}' for x in self.digest())

# 测试 MD5 算法
def md5(message):
    md5_obj = MD5()
    md5_obj.update(message)
    return md5_obj.hexdigest()
    
# 示例
message = "hello world"
print(f"MD5(\"hello world\") = {md5(message.encode())}")

C++实现。代码参考百度百科MD5open in new window

#include<iostream>
#include<string>
using namespace std;
#define shift(x, n) (((x) << (n)) | ((x) >> (32-(n))))//右移的时候，高位一定要补零，而不是补充符号位
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))    
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))
#define A 0x67452301
#define B 0xefcdab89
#define C 0x98badcfe
#define D 0x10325476
//strBaye的长度
unsigned int strlength;
//A,B,C,D的临时变量
unsigned int atemp;
unsigned int btemp;
unsigned int ctemp;
unsigned int dtemp;
//常量ti unsigned int(abs(sin(i+1))*(2pow32))
const unsigned int k[]={
    0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
    0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,0x698098d8,
    0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193,
    0xa679438e,0x49b40821,0xf61e2562,0xc040b340,0x265e5a51,
    0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
    0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,
    0xfcefa3f8,0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681,
    0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60,
    0xbebfbc70,0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
    0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,0xf4292244,
    0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,
    0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314,
    0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391};
//向左位移数
const unsigned int s[]={7,12,17,22,7,12,17,22,7,12,17,22,7,
    12,17,22,5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
    4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,6,10,
    15,21,6,10,15,21,6,10,15,21,6,10,15,21};
const char str16[]="0123456789abcdef";
void mainLoop(unsigned int M[]) {
    unsigned int f,g;
    unsigned int a=atemp;
    unsigned int b=btemp;
    unsigned int c=ctemp;
    unsigned int d=dtemp;
    for (unsigned int i = 0; i < 64; i++) {
        if(i<16){
            // 第一轮
            f=F(b,c,d); // BCD的位运算
            g=i;  // 明文数据块下标
        } else if (i<32) {
            f=G(b,c,d);
            g=(5*i+1)%16;
        } else if(i<48) {
            f=H(b,c,d);
            g=(3*i+5)%16;
        } else {
            f=I(b,c,d);
            g=(7*i)%16;
        }
        unsigned int tmp=d;
        d=c;
        c=b;
        b=b+shift((a+f+k[i]+M[g]),s[i]);  // 求和并位移，再与B求和
        a=tmp;
    }
    atemp=a+atemp;
    btemp=b+btemp;
    ctemp=c+ctemp;
    dtemp=d+dtemp;
}
/*
*填充函数
*处理后应满足bits≡448(mod512),字节就是bytes≡56（mode64)
*填充方式为先加一个1,其它位补零
*最后加上64位的原来长度
*/
unsigned int* add(string str) {
    unsigned int num=((str.length()+8)/64)+1;  // 以512位,64个字节为一组
    unsigned int *strByte=new unsigned int[num*16];  // 64/4=16,所以有16个整数
    strlength=num*16;
    for (unsigned int i = 0; i < num*16; i++)
        strByte[i]=0;
    for (unsigned int i=0; i <str.length(); i++) {
        strByte[i>>2]|=(str[i])<<((i%4)*8);  // 一个整数存储四个字节，i>>2表示i/4 一个unsigned int对应4个字节，保存4个字符信息
    }
    strByte[str.length()>>2]|=0x80<<(((str.length()%4))*8);  // 尾部添加1 一个unsigned int保存4个字符信息,所以用128左移
    /*
    *添加原长度，长度指位的长度，所以要乘8，然后是小端序，所以放在倒数第二个,这里长度只用了32位
    */
    strByte[num*16-2] = str.length()*8;
    return strByte;
}

string changeHex(int a) {
    int b;
    string str1;
    string str="";
    for (int i = 0; i < 4; i++) {
        str1="";
        b = ((a>>i*8)%(1<<8))&0xff;  //逆序处理每个字节
        for (int j = 0; j < 2; j++) {
            str1.insert(0,1,str16[b%16]);
            b = b / 16;
        }
        str += str1;
    }
    return str;
}

string getMD5(string source) {
    atemp=A;  //初始化
    btemp=B;
    ctemp=C;
    dtemp=D;
    unsigned int *strByte=add(source);
    for(unsigned int i = 0; i < strlength/16; i++) {
        unsigned int num[16];
        for(unsigned int j=0;j<16;j++)
            num[j] = strByte[i*16+j];
        mainLoop(num);
    }
    return changeHex(atemp).append(changeHex(btemp)).append(changeHex(ctemp)).append(changeHex(dtemp));
}

unsigned int main() {
    string ss;
    // cin>>ss;
    string s=getMD5("abc");
    cout<<s;
    return 0;
}

加盐

原文保持不变的情况下，md5得到的值也会不变，这是撞库的原理。通过加盐方式防止撞库，比如原文后拼接特定字符串

SHA

SHA算法（Secure Hash Algorithm，安全散列算法）基于MD4算法基础。与MD算法不同之处主要在于摘要长度，SHA算法的摘要长度更长，安全性更高
SHA算法家族目前共有SHA-1、SHA-224、SHA-256、SHA-384和SHA-512五种算法。通常将后四种算法并称为SHA-2算法

实现流程

目标字符串以字符为单位转换成字符编码（ascii码/unicode码等），将字符编码转换为二进制码
明文末尾补1个1和n个0，使其对512取余为448
二进制码进行分组转换。即每以512位二进制码一组，最后一组数据位数448（保留64位）
保留64位处表明原文长度信息，记录原文的位长。以使最后一组也保持512位
将每个512分组再分出16个32位子分组
将16个32位子分组扩展到80个32位子分组
- 对于前 16 个子块（0 ≤ t ≤15），直接将 W[t] 赋值为 M[t]
- 从第 17 个子块开始（16 ≤ t ≤ 79），使用以下公式进行扩展： W[t]=(W[t−3]⊕W[t−8]⊕W[t−14]⊕W[t−16])≪1

初始化幻数

uint32_t H0 = 0x67452301;   // 0x01, 0x23, 0x45, 0x67
uint32_t H1 = 0xEFCDAB89;   // 0x89, 0xAB, 0xCD, 0xEF
uint32_t H2 = 0x98BADCFE;   // 0xFE, 0xDC, 0xBA, 0x98
uint32_t H3 = 0x10325476;   // 0x76, 0x54, 0x32, 0x10
uint32_t H4 = 0xC3D2E1F0;   // 0xF0, 0xE1, 0xD2, 0xC3

/* 前4个数字与MD5幻数一致
A: 1732584193
B: 4023233417
C: 2562383102
D: 271733878
E: 3285377520
*/

进行4轮，每轮20次，共80次运算。每轮运算时使用不同的值求和

/* SHA1 Constants */
static uint32_t K[4] = {
    0x5A827999,     /* [0,  19] */
    0x6ED9EBA1,     /* [20, 39] */
    0x8F1BBCDC,     /* [40, 59] */
    0xCA62C1D6      /* [60, 79] */
};
/*
1518500249
1859775393
2400959708
3395469782
*/

计算过程中幻数ABCDE也会改变。运算后每个512分组得到幻数，与该分组计算前传入的幻数求和，作为下一分组的传入幻数
字符串拼接最后一个512分组计算出的ABCDE得到SHA1结果

例子：目标字符串abc

字符串abcascii码的二进制码01100001 01100010 01100011
补位以便进行分组01100001 01100010 01100011 100...0共计423个0（423个0 + 1个1 + 原文3*8 = 448），16进制如下所示 (512位二进制 -> 128位16进制)
```
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
```

附加长度信息：原文长度：3*8 = 24位二进制，24的16进制为18

61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000018

先分出32个子分组，再通过公示扩展成80个子分组
进行位运算得到最终幻数H0 = H0+A、H1=H1+B、H2=H2+C、H3=H3+D、H4=H4+E
拼接最后一个分组得到的ABCDE即为最终结果

代码

JAVA API

import java.security.MessageDigest;

public class SHA {
    // SHA-1 : 160位二进制 - 40位16进制字符串（每4位二进制得到一个16进制字符）
    public static byte[] encodeSHA1(byte[] data) throws Exception {
        MessageDigest md = MessageDigest.getInstance("SHA");
        return md.digest(data);
    }

    // SHA-256 : 256位二进制 - 64位16进制字符串
    public static byte[] encodeSHA256(byte[] data) throws Exception {
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        return md.digest(data);
    }

    // SHA-384 : 384位二进制 - 96位16进制字符串
    public static byte[] encodeSHA384(byte[] data) throws Exception {
        MessageDigest md = MessageDigest.getInstance("SHA-384");
        return md.digest(data);
    }

    // SHA-512 : 512位二进制 - 128位16进制字符串
    public static byte[] encodeSHA512(byte[] data) throws Exception {
        MessageDigest md = MessageDigest.getInstance("SHA-512");
        return md.digest(data);
    }
}

Python实现。代码出自GPT：使用python编写sha1算法的实现流程

import struct

# 定义循环左移函数
def left_rotate(n, b):
    return ((n << b) | (n >> (32 - b))) & 0xFFFFFFFF

# SHA-1 主算法类
class SHA1:
    def __init__(self):
        # 初始化五个缓冲区变量（五个32位寄存器）
        self.h0 = 0x67452301
        self.h1 = 0xEFCDAB89
        self.h2 = 0x98BADCFE
        self.h3 = 0x10325476
        self.h4 = 0xC3D2E1F0 
    
    def update(self, message):
        # 预处理：填充消息
        original_length = len(message) * 8  # 以位为单位 - 一字节8位
        message += b'\x80'  # 先添加 1 位，后跟随 0 位填充
        
        # 填充0直到消息长度模512等于448位（即最后64位用来存储长度）
        # while (len(message) * 8 + 64) % 512 != 0:  # 化简后为 56 = 448 / 8
        while len(message) % 64 != 56:
            message += b'\x00'  # 补充全0字节
        
        # 以大端格式附加消息的原始长度
        message += struct.pack('>Q', original_length)
        
        # 按 512 位（64 字节）块处理消息
        for i in range(0, len(message), 64):
            self.process_block(message[i:i + 64])
        
    def process_block(self, block):
        # 将 512 位块分成 16 个 32 位的字
        w = list(struct.unpack('>16I', block))  # 长度16的数组
        
        # 扩展到 80 个 32 位字
        for i in range(16, 80):  # 补充index 16 - 79
            w.append(left_rotate(w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16], 1))

        # 初始化五个变量
        a, b, c, d, e = self.h0, self.h1, self.h2, self.h3, self.h4

        # 主循环
        for i in range(80):
            if 0 <= i <= 19:
                f = (b & c) | (~b & d)
                k = 0x5A827999
            elif 20 <= i <= 39:
                f = b ^ c ^ d
                k = 0x6ED9EBA1
            elif 40 <= i <= 59:
                f = (b & c) | (b & d) | (c & d)
                k = 0x8F1BBCDC
            else:
                f = b ^ c ^ d
                k = 0xCA62C1D6

            temp = (left_rotate(a, 5) + f + e + k + w[i]) & 0xFFFFFFFF
            e = d
            d = c
            c = left_rotate(b, 30)
            b = a
            a = temp

        # 更新缓冲区
        self.h0 = (self.h0 + a) & 0xFFFFFFFF
        self.h1 = (self.h1 + b) & 0xFFFFFFFF
        self.h2 = (self.h2 + c) & 0xFFFFFFFF
        self.h3 = (self.h3 + d) & 0xFFFFFFFF
        self.h4 = (self.h4 + e) & 0xFFFFFFFF
    
    def digest(self):
        # 拼接返回 160 位哈希值 - 指定'>5I'拼接
        return struct.pack('>5I', self.h0, self.h1, self.h2, self.h3, self.h4)

    def hexdigest(self):
        # 将哈希值转换为十六进制字符串
        # 指定'>5I'解包后
        return ''.join(f'{x:08x}' for x in struct.unpack('>5I', self.digest()))
        # 等效为''.join(f'{x:08x}' for x in [h0, h1, h2, h3, h4])

# 测试 SHA-1 算法
def sha1(message):
    sha1_obj = SHA1()
    sha1_obj.update(message)
    return sha1_obj.hexdigest()

# 示例
message = b"hello world"
print(f"SHA-1(\"hello world\") = {sha1(message)}")

C实现参考https://www.cnblogs.com/Kingfans/p/16561821.htmlopen in new window

#include <string.h>
#include <stdio.h>

#define HASH_BLOCK_SIZE         64  /* 512 bits = 64 bytes */
#define HASH_LEN_SIZE           8   /* 64 bits =  8 bytes */
#define HASH_LEN_OFFSET         56  /* 64 bytes - 8 bytes */
#define HASH_DIGEST_SIZE        16  /* 128 bits = 16 bytes */
#define HASH_ROUND_NUM          80 

typedef unsigned char       uint8_t;
typedef unsigned short int  uint16_t;
typedef unsigned int        uint32_t;
typedef unsigned long long  uint64_t;

/* Swap bytes in 32 bit value. 0x01234567 -> 0x67452301 */
// 大端小端互转
#define __bswap_32(x)    \
    ((((x) & 0xff000000) >> 24)  \
    | (((x) & 0x00ff0000) >>  8) \
    | (((x) & 0x0000ff00) <<  8) \
    | (((x) & 0x000000ff) << 24))

/* SHA1 Constants */
static uint32_t K[4] = {
    0x5A827999,     /* [0,  19] */
    0x6ED9EBA1,     /* [20, 39] */
    0x8F1BBCDC,     /* [40, 59] */
    0xCA62C1D6      /* [60, 79] */
};

/*                  f(X, Y, Z)                      */
/* [0,  19] */
static uint32_t Ch(uint32_t X, uint32_t Y, uint32_t Z) {
    return (X & Y) ^ ((~X) & Z);
}
/* [20, 39] */  /* [60, 79] */
static uint32_t Parity(uint32_t X, uint32_t Y, uint32_t Z) {
    return X ^ Y ^ Z;
}
/* [40, 59] */
static uint32_t Maj(uint32_t X, uint32_t Y, uint32_t Z) {
    return (X & Y) ^ (X & Z) ^ (Y & Z);
}

/* 循环向左移动offset个比特位 */
static uint32_t MoveLeft(uint32_t X, uint8_t offset) {
    uint32_t res = (X << offset) | (X >> (32 - offset));
    return res;
}

#define ASSERT_RETURN_INT(x, d) if(!(x)) { return d; }

int sha1(unsigned char *out, const unsigned char* in, const int inlen) {
    ASSERT_RETURN_INT(out && in && (inlen >= 0), 1);
    int i = 0, j = 0, t = 0;

    // step 1: 字节填充(Append Padding Bytes)
    // 数据先补上1个1比特，再补上k个0比特，使得补位后的数据比特数(n+1+k)满足(n+1+k) mod 512 = 448，k取最小正整数
    int iX = inlen / HASH_BLOCK_SIZE;
    int iY = inlen % HASH_BLOCK_SIZE;
    iX = (iY < HASH_LEN_OFFSET) ? iX : (iX + 1);

    int iLen = (iX + 1) * HASH_BLOCK_SIZE;
    unsigned char* X = malloc(iLen);
    memcpy(X, in, inlen);
    // 先补上1个1比特+7个0比特
    X[inlen] = 0x80;
    // 再补上(k-7)个0比特
    for (i = inlen + 1; i < (iX * HASH_BLOCK_SIZE + HASH_LEN_OFFSET); i++) {
        X[i] = 0;
    }

    // step 2: 追加长度信息(Append Length)
    uint8_t *pLen = (uint64_t*)(X + (iX * HASH_BLOCK_SIZE + HASH_LEN_OFFSET));
    uint64_t iTempLen = inlen << 3;
    uint8_t *pTempLen = &iTempLen;
    pLen[0] = pTempLen[7]; pLen[1] = pTempLen[6]; pLen[2] = pTempLen[5];  pLen[3] = pTempLen[4];
    pLen[4] = pTempLen[3]; pLen[5] = pTempLen[2]; pLen[6] = pTempLen[1];  pLen[7] = pTempLen[0];

    // Step 3. 初始化MD Buffer(Initialize MD Buffer)
    uint32_t H0 = 0x67452301;   // 0x01, 0x23, 0x45, 0x67
    uint32_t H1 = 0xEFCDAB89;   // 0x89, 0xAB, 0xCD, 0xEF
    uint32_t H2 = 0x98BADCFE;   // 0xFE, 0xDC, 0xBA, 0x98
    uint32_t H3 = 0x10325476;   // 0x76, 0x54, 0x32, 0x10
    uint32_t H4 = 0xC3D2E1F0;   // 0xF0, 0xE1, 0xD2, 0xC3

    uint32_t M[HASH_BLOCK_SIZE / 4] = { 0 };
    uint32_t W[HASH_ROUND_NUM] = { 0 };

    // step 4: 处理消息块(Process Message in 64-Byte Blocks)
    for (i = 0; i < iLen / HASH_BLOCK_SIZE; i++) {
        /* Copy block i into X. */
        for (j = 0; j < HASH_BLOCK_SIZE; j = j + 4) {
            uint64_t k = i * HASH_BLOCK_SIZE + j;
            M[j / 4] = (X[k] << 24) | (X[k + 1] << 16) | (X[k + 2] << 8) | X[k + 3];
        }

        /*  a. Divide M(i) into 16 words W(0), W(1), ..., W(15), where W(0) is the left - most word. */
        for (t = 0; t <= 15; t++) {
            W[t] = M[t];
        }

        /*  b. For t = 16 to 79 let
        W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)). */
        for (t = 16; t <= 79; t++) {
            W[t] = MoveLeft(W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16], 1);
        }

        /*  c. Let A = H0, B = H1, C = H2, D = H3, E = H4. */
        uint32_t A = H0;
        uint32_t B = H1;
        uint32_t C = H2;
        uint32_t D = H3;
        _t E = H4;

        /*  d. For t = 0 to 79 do
        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; */
        for (t = 0; t <= 19; t++) {
            uint32_t temp = MoveLeft(A, 5) + Ch(B, C, D) + E + W[t] + K[0];
            E = D;
            D = C;
            C = MoveLeft(B, 30);
            B = A;
            A = temp;
        }
        for (t = 20; t <= 39; t++) {
            uint32_t temp = MoveLeft(A, 5) + Parity(B, C, D) + E + W[t] + K[1];
            E = D;
            D = C;
            C = MoveLeft(B, 30);
            B = A;
            A = temp;
        }
        for (t = 40; t <= 59; t++) {
            uint32_t temp = MoveLeft(A, 5) + Maj(B, C, D) + E + W[t] + K[2];
            E = D;
            D = C;
            C = MoveLeft(B, 30);
            B = A;
            A = temp;
        }
        for (t = 60; t <= 79; t++) {
            uint32_t temp = MoveLeft(A, 5) + Parity(B, C, D) + E + W[t] + K[3];
            E = D;
            D = C;
            C = MoveLeft(B, 30);
            B = A;
            A = temp;
        }

        /*  e. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E. */
        H0 = H0 + A;
        H1 = H1 + B;
        H2 = H2 + C;
        H3 = H3 + D;
        H4 = H4 + E;
    }

    // step 5: 输出ABCD
    uint32_t* pOut = (uint8_t*)out;
    pOut[0] = __bswap_32(H0);
    pOut[1] = __bswap_32(H1);
    pOut[2] = __bswap_32(H2);
    pOut[3] = __bswap_32(H3);
    pOut[4] = __bswap_32(H4);
    free(X);

    return 0;
}

int main() {
    unsigned char digest[20] = { 0 };

    sha1(digest, "Hello World!", strlen("Hello World!"));

    return 0;
}

消息摘要算法

# 简介

# MD5

# 实现流程

# 代码

# 加盐

# SHA

# 实现流程

# 代码

简介

MD5

实现流程

代码

加盐

SHA

实现流程

代码