宣传一波 更好的阅读体验 👉 个人blog

Hash 函数结构

Hash 函数的一般结构如图6-1所示,称为Hash 函数迭代结构，也称为MD 结构。它由 Merkle 和 Damgard 分别独立提出,包括 MD5,SHA1 等目前所广泛使用的大多数 Hash 函数都采用这种结构。MD 结构将输人消息分为L个固定长度的分组,每一分组长为b位,最后一个分组包含输入消息的总长度,若最后一个分组不足b位时,需要将其填充为b位。由于输人包含消息的长度,所以攻击者必须找出具有相同散列值且长度相等的两条消息,或者找出两条长度不等但加入消息长度后散列值相同的消息,从而增加了攻击的难度。

迭代结构包含一个压缩函数f。压缩函数f有两个输入:一个是前一次迭代的n 位输出,称为链接变量;另一个是消息的b位分组，并产生一个n 位的输出。因为一般来说消息分组长度b大于输出长度n,因此称之为压缩函数。第一次迭代输入的链接变量又称为初值变量,由具体算法指定,最后一次迭代的输出即为散列值。

MD5 算法

MD5 算法是美国麻省理工学院著名密码学家 Rivest 设计的,MD(Message Digest)是消息摘要的意思。Rivest 于 1992 年向 IETF 提交的 RFC1321 中对 MD5作了详尽的述 MD5 是在MD2、MD3和MD4基础上发展而来的,尤其在MD4 上增加了 Safety-Belts,所以MD5 又被称为是“系有安全带的 MD4”,它虽然比MD4 要稍慢一些,但更为安全。

1. MD5 算法描述

MD5算法的输人是长度小于$2^{64}$比特的消息,输出为 128 比特的消息摘要。输人消息以512 比特的分组为单位处理,其流程如下:

L为消息的长度;N 为消息扩充后分组个数:$Y_i(0 \leq i \leq N-1)$代表一个分组;IV表示初始链接变量,A、B、C、D是4个32位的寄存器;$CV_i$是链接变量,即是第i个分组处理单元的输出，也是第 i+1 个分组处理单元的输人,最后单元的输出$CV_N$ 即是消息的散列值。

主要流程概括起来便是：消息预处理, 初始化缓冲区, 循环哈希，下面会依次介绍

2.MD5 具体流程

1. 消息预处理

1. 附加补充位

在长度为 K bits 的原始消息数据尾部填充长度为P bits的标识100…0，$1 \leq P \leq 512$(即至少要填充1个bit)，使得填充后的消息位数为：$K + P \equiv 448 (mod 512).$

注意到当 $K \equiv 448 (mod 512)$时，需要 P= 512.

1. 附加信息

原始消息长度（注意是长度）以 64 比特表示附加在填充结果的后面，最后得到一个长度位数为 $K + P + 64 \equiv 0 (mod 512)$的消息。

原因: 增加攻击者伪造明文的难度. 伪造信息的长度必需要与原文长度相等(其实是同余)

将消息长度 $Length(M)(mod2^{64})$ 以小端序的形式附加到第一步预留的 64-bit 空间中.

后面会讲小端序和大端序

按以上步骤处理完消息之后, 将最后的得到的消息结果分割成 L 个 512-bit 分组：$Y_0, Y_1, \ldots ,Y_{L - 1}$

分组结果按32-bit 一组, 被分为 16 组字(Word) (512 = 32 * 16)，$M_0[0],M_0[1],\ldots,M_0[15],M_1[0]\ldots, M_{L - 1}[16]$,在本文中被记作 $M_i[j]$,其中j表示字的组数.

2.初始化缓冲区

算法使用 128-bit 的缓冲区存放中间结果和最终哈希值, 128-bit可以看做 4组32-bit字所占的比特位(128 = 4 * 32)

被记作 $Buffer_A,Buffer_B,Buffer_C,Buffer_D$. 每个缓冲区都以小端序的方式存储数据. 将 4 块 Buffer 组合起来记为链接向量$CV_i$

$$CV_i=CV_{i−1}$$

$CV_0$ 被规定为常量, 如下表格所示.(在最上面的流程图里面现实的$IV$)，即 A、B、C、D 的值分别为 0x67452301，0xEFCDAB89，0x98BADCFE，0x10325476）

每一个变量给出的数值是高字节存于内存低地址，低字节存于内存高地址，即大端字节序

注意一个存储单元可以存储两位，当然也是一个字

3.循环哈希

调用 $H_{MD5}(M_i,CV_i)$ 函数对每组消息分组进行哈希计算.

每一次$H_{MD5}()$ 中有 4 轮结构相同的逻辑函数, 不同轮次间的唯一区别是参与计算的逻辑函数不同, 分别表示为 F、G、H、I.

下面步函数会介绍 F、G、H、I

此外, $H_{MD5}()$ 还有一个常数表 T, 常数表 T 为定义为 $T[i]=[2^{32} \times abs(sin(i))]=[4294967296 \times abs(sin(i))],1 \leq i \leq 64$ (前 32-bit 小数.) (i 是弧度),如$T[28]=[4294967296 \times abs(sin(28))] \approx [1163531501.079 3967247]$,然后其整数部分转化为十六进制$T[28]=(1163531501)_{10}=(455A14ED)_{16}$。T[i]是一个伪随机的常数,可以消除输入数据的规律性,其详细取值见表 6-1。

//常熟T[i](i = 1,...,64)
const uint32_t T[64] = {
    0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
    0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
    0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
    0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
    0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
    0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
    0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
    0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};

在本文中把 $H_{MD5}$ 的轮函数记为 $R(M_i,Buffer,T[],function_i())$. 其中, 轮函数每次调用是都会读取缓存区中的数据. 而且不同轮次之间所调用的逻辑函数也是不一样的. 此外, 每一次调用轮函数会用到不同 16 组 T 元素(对应轮函数内部的中 16 次迭代).

$H_{MD5}()$ 完成第四轮轮函数处理之后, 将得到的结果和输入的$CV*i$按字(每 32-bit) 分组按位加. 得到最终输出结果$CV*{i+1}$.

3.轮函数(压缩函数)的具体实现

MD5算法的分组处理(压缩函数)与分组密码的分组处理相似,如图 6-3 所示。它由4轮组成,512比特的消息分组M被均分为16个子分组(每个子分组为 32比特)参与每轮16步函数运算，即每轮包括16个步骤。每步的输人是4个 32比特的链接变量和一个32比特的消息子分组,输出为32位值。经过4轮共64 步后,得到的个存器值分别与输人链接变量进行模加，即得到此次分组处理的输出链接变量。

4 轮操作开始前,先将前一分组的链接变量(A、BC 和 D 的值)复制到另外 4 个备用记录单元AA、BB、CC和DD,以便执行最后的模加运算。

轮函数每次调用内部有 16 次迭代计算, 将轮函数当前迭代的次数记作 i

读取缓冲区中的数据, 将缓冲区按字32-bit 分为4组, 记作 A、B、C、D

• 第一步

BCD 暂时不动, A 有以下 x 层计算:

• $A+Logic_Function_{轮数}(B,C,D)$

  $F(b,c,d)=(b∧c)∨(\overline b∧d)$

  $G(b,c,d)=(b∧d)∨(c∧\overline d)$

  $H(b,c,d)=b⊕c⊕d$

  $I(b,c,d)=c⊕(b∨\overline d)$

• $A+M_i[k]$ (k 受到当前轮数以及迭代次数 i 的影响)

• $A+T[i]$ (受到输入影响, 与当前轮数有关)

  $ρ_1(i)=i$

  $ρ_2(i)=(1+5i)mod16$

  $ρ_3(i)=(5+3i)mod16$

  $ρ_4(i)=7imod16$

• A 循环(注意是循环）左移 s 位 (s 由一个常量表给出)

  s[ 1…16] = { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22 }
  s[17…32] = { 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20 }
  s[33…48] = { 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23 }
  s[49…64] = { 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21 }

• A + B

• 第二步

对缓冲区中的四个字按字右循环位移 1 个字 即新的缓冲区$Buffer′=D′||A′||B′||C′$

也就是说, 一组消息的压缩要经过这样的过程:

1. 轮次一(F)

cpp /* [abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */ [ABCD 0 7 1][DABC 1 12 2][CDAB 2 17 3][BCDA 3 22 4] [ABCD 4 7 5][DABC 5 12 6][CDAB 6 17 7][BCDA 7 22 8] [ABCD 8 7 9][DABC 9 12 10][CDAB 10 17 11][BCDA 11 22 12] [ABCD 12 7 13][DABC 13 12 14][CDAB 14 17 15][BCDA 15 22 16]

1. 轮次二(G)

cpp /* [abcd k s i] a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */ [ABCD 1 5 17][DABC 6 9 18][CDAB 11 14 19][BCDA 0 20 20] [ABCD 5 5 21][DABC 10 9 22][CDAB 15 14 23][BCDA 4 20 24] [ABCD 9 5 25][DABC 14 9 26][CDAB 3 14 27][BCDA 8 20 28] [ABCD 13 5 29][DABC 2 9 30][CDAB 7 14 31][BCDA 12 20 32]

1. 轮次三(H)

cpp /* [abcd k s i] a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */ [ABCD 5 4 33][DABC 8 11 34][CDAB 11 16 35][BCDA 14 23 36] [ABCD 1 4 37][DABC 4 11 38][CDAB 7 16 39][BCDA 10 23 40] [ABCD 13 4 41][DABC 0 11 42][CDAB 3 16 43][BCDA 6 23 44] [ABCD 9 4 45][DABC 12 11 46][CDAB 15 16 47][BCDA 2 23 48]

1. 轮次四 (I)

cpp /* [abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */ [ABCD 0 6 49][DABC 7 10 50][CDAB 14 15 51][BCDA 5 21 52] [ABCD 12 6 53][DABC 3 10 54][CDAB 10 15 55][BCDA 1 21 56] [ABCD 8 6 57][DABC 15 10 58][CDAB 6 15 59][BCDA 13 21 60] [ABCD 4 6 61][DABC 11 10 62][CDAB 2 15 63][BCDA 9 21 64]

4. 案例

用 MD5 算法处理 ASCII 码序列“iscbupt”




在此特别强调的是,尽管前面提到 MD5的初始链接变量是:

A=0x01234567,B=0x89ABCDEF,C=0xFEDCBA98,D=0x76543210

但在运算过程中涉及大端(Big Endian)和小端Little Endian)的转换问题，所以计算时首先应该将初始链接变量进行大小端的转换,运算结束后再进行一次大小端的转换即得 MD5散列值。

完成第一个分组(即最后一个分组)处理后得散列值为:
$A=(0xDA456015+0x67452301)mod 2^{23}=0x418A8316$

$B=(0x231F2EC1+0xEFCDAB89)mod 2^{32}=0x12ECDA4A$

$C=(0xDAB4FBDA+0x98BADCFE)mod 2^{32} = 0x736FD8D8$

$D=(0xA7517CE9+0x10325476)mod2^{32}=0xB783D15F$

由此可得:
MD5(“iscbupt”)=“16838A414ADAEC12D8D86F735FD183B7”

5.代码实现

大量注释来袭 o((>ω< ))o

还有就是注意一个字就是 8bit，注意有地方看不懂是不是没换算的问题，如果还是不懂请评论留眼

#include <iostream>
#include <string>
#include <stdint.h> // for uint* type,无符号的n位整数（unsigned n-bit integer）
#include <limits.h> // for CHAR_BIT
using namespace std;

// 默认的T
const uint32_t T[64] = {
   0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
   0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
   0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
   0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
   0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
   0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
   0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
   0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};

// 用于获取循环左移的次数
const unsigned int SHIFT[4][4]{
   {7, 12, 17, 22},
   {5, 9, 14, 20},
   {4, 11, 16, 23},
   {6, 10, 15, 21}};

// 填充位，0x80是一个十六进制数，表示一个二进制数10000000
//是因为填充的bit需要是一个1和若干个0
const uint8_t PADDING[] = {
   0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

// 用于循环左移
inline uint32_t Left_Rotate32(uint32_t x, unsigned int num)
{
   num &= 31;
   return (x << num) | (x >> (-num & 31));
}

// 非线性函数FGHI
inline uint32_t Logic_Function(int Round_i, uint32_t b, uint32_t c, uint32_t d)
{
   switch (Round_i)
   {
   case 3:
    return c ^ (b | ~d);
   case 2:
    return b ^ c ^ d;
   case 1:
    return (b & d) | (c & ~d);
   case 0:
    return (b & c) | (~b & d);
   }
   return 0;
}

//获取T[i]中的i (受到输入影响, 与当前轮数有关)
inline unsigned int Substituion(int Round_i, int i)
{
   switch (Round_i)
   {
   case 0:
    return i;
   case 1:
    return (1 + 5 * i) % 16;
   case 2:
    return (5 + 3 * i) % 16;
   case 3:
    return (7 * i) % 16;
   }
   return 0;
}

// 参数是第i轮，ABCD，和消息分组M
void Round_Function(int Round_i, uint32_t buffer[4], const uint32_t message_block[16])
{
   //每轮需要进行16个步骤
   for (int i = 0; i < 16; i++)
   {
       // 1.步函数执行
    // A + +Logic_Function_{轮数}(B,C,D)
    buffer[0] += Logic_Function(Round_i, buffer[1], buffer[2], buffer[3]);
    // A+M_i[k] (k 受到当前轮数以及迭代次数 i 的影响)
    buffer[0] += message_block[Substituion(Round_i, i)];
    // A+T[i] (受到输入影响, 与当前轮数有关)
    buffer[0] += T[Round_i * 16 + i];
    // A 循环左移 s 位 (s 由一个常量表给出)
    buffer[0] = Left_Rotate32(buffer[0], SHIFT[Round_i][i % 4]);
    // 最后A + B
    buffer[0] += buffer[1];

    // 2. 对缓冲区中的四个字按字右循环位移 1 个字
    // Buffer′=D′||A′||B′||C′
    uint32_t bufferCache = buffer[3];
    buffer[3] = buffer[2];
    buffer[2] = buffer[1];
    buffer[1] = buffer[0];
    buffer[0] = bufferCache;
   }
   return;
}

//chain_vector即ABCD，消息分组message_block有16个子分组，每个子分组位32bit
void Hash_MD5(uint32_t chain_vector[4], const uint32_t message_block[16])
{
   // 将chain_vector赋给buffer，buffer作为中间tmp
   uint32_t buffer[4];
   memcpy(buffer, chain_vector, 128 / CHAR_BIT);

   // 进行四轮迭代
   for (int i = 0; i < 4; i++)
    Round_Function(i, buffer, message_block);

   // 将得到的结果和输入的CV_i按字(每 32-bit) 分组按位加. 得到最终输出结果CV_{i+1}.

   for (int i = 0; i < 4; i++)
    chain_vector[i] += buffer[i];
}

__uint128_t MD5(string _message)
{
   /*
   //  1.预处理的消息
   //  填充和追加长度信息
   //  填充缓存数组
   //  附加messageBITcount，在c++中自然以尾序存储
   */

   // 获取信息的长度,_message是还未处理的信息
   uint64_t messageLength = _message.length();
   // 将信息的字节长度转换为位（bit）长度，CHAR_BIT通常指的是8
   uint64_t messageBitCount = messageLength * CHAR_BIT;

   //计算需要多少个512位的块来存储信息
   //这里先将messageBitCount加上64，是因为后面需要填充原始消息开头的低64位
   //+1是为了C++默认向下取整，我们需要向上取整
   int blockCount = (messageBitCount + 64 - 1) / 512 + 1;
   //数组的大小是64 * blockCount，这样可以使信息的长度恰好是blockCount个512位的块的倍数。
   uint8_t message[64 * blockCount];
   memcpy(message, _message.c_str(), messageLength);
   //在信息的末尾填充特定的填充字符，直到信息长度达到64的倍数,for语句中-8是为了填充原始消息开头的低64位
   for (int i = messageLength, j = 0; i < (64 * blockCount - 8); i++)
    message[i] = PADDING[j++];
   //在最后空缺的64位上填充  以64比特表示的原始消息长度
   //实际上是将messageBitCount的低64位添加到了message + (64 * blockCount - 8)后面
   memcpy(message + (64 * blockCount - 8), &messageBitCount, 64 / CHAR_BIT);

   // 构建对象M，每一个M有16个子分组，每个子分组位32bit
   uint32_t *messageBuffer = new uint32_t[16];

   /*
   //  2.初始化CV
   //  注意CV1 的ABCD位大端序
   */
   uint32_t res[4] = {0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476};
   for (int i = 0; i < blockCount; i++)
   {
    // 更新 Message_Block，即M0，M1，M2。。。
    memcpy(messageBuffer, message + 64 * i, 64);
    //对每一个M进行hash压缩函数
    Hash_MD5(res, messageBuffer);
   }

   /*
   //  3.将最后得到的ABCD即res返回md5
   */
   __uint128_t md5 = 0;
   for (int i = 0; i < 4; i++)
        md5 += (__uint128_t)res[i] << (i * 32);

       //释放动态分配的内存
       //当你使用 new 关键字动态地分配内存时，在不再使用那块内存后使用 delete[] 来释放它
       //不释放动态分配的内存，那么程序可能会消耗掉所有的可用内存，导致所谓的内存泄漏
    delete[] messageBuffer;
    return md5;
}

void MD5_Print(__uint128_t in)//将128位整数的每一个字节以十六进制形式打印出来。
{
   //__uint128_t 是128位，但 printf 函数只能按字节（即8位）来处理数据。
   //所以，我们需要利用unsigned char逐个访问128位的整数按字节并拆分，然后逐个字节地打印。
   unsigned char *ptr = (unsigned char *)&in;
   for (int i = 0; i < 16; i++)
       //%02x 是一个格式说明符，它将以两位十六进制格式打印一个字节，并在需要时在前面补零。
    printf("%02x", ptr[i]);
}

int main(void)
{
   cout << "----------------- MD5 -----------------\n";
   cout << "请输入要加密的明文. (如果要终止程序请按CTRL + C)\n";
   string str;
   cout << "text: ";
   getline(cin, str);
   //__uint128_t一个无符号的128位整数,可存储的值（2^128 - 1）
   __uint128_t md5 = MD5(str);

   cout << "result: ";
   // 注意这个md5类型是__uint128_t，我们需要的是能将这个整数以16进制输出
   MD5_Print(md5);

   return 0;
}

结果

----------------- MD5 -----------------
请输入要加密的明文. (如果要终止程序请按CTRL + C)
text: iscbupt
result: 16838a414adaec12d8d86f735fd183b7