NTL密码算法开源库拓展——MD5

2021-08-29 00:23:41

2021SC@SDUSC

MD5加密过程

十进制是逢十进一
二进制是逢二进一
十六进制是逢十六进一

字节序的概念

计算机的存储单位为字节，一个字节对应8个二进制位，共可以表示2^8也就是256种状态。若表示数的话，最多只能表示256个数。

如一个字节可以表示非负整数的0~255，而表示更大的数，则需要占用多个字节，如表示256至少需要两个字节。

256的二进制形式为 00000001 00000000。这样在计算机存储上就存在一个问题：是先存储00000001这个字节，还是先存储00000000这个字节呢？实际上，采用这两种存储方式的都有，取决于CPU架构和编译器。这就引出了字节序的概念。

小端字节序（Little Endian）：低位字节存放在低内存地址，高位字节存放在高内存地址端。

大端字节序（Big Endian）：高位字节存放在低内存地址，低位字节存放在高内存地址端。

256作为无符号数在计算机内存中的存储：

接下来这篇文章的所有关于存储的描述都是基于小端字节序的，内存地址都是从左往右从低到高的，而且带[存储]字样。（这很关键）

如：00000001 00000010 [存储] 表示的是十六进制的0x201，十进制的513，二进制的1000000001b

(一个数以0x开头意味着这个数是采用的十六进制，以b结尾意味着采用二进制)

任何计算机文件都是可以看作一串二进制位。

例如：一个最普通的内容为hello的ASCII文本文件，在计算机中的存储是这样的：

01101000 01100101 01101100 01101100 01101111 [存储]

（这和UTF-8编码的字符串”hello”，在内存中的存储是一样的。）

MD5算法描述

MD5算法就像一个函数，任意一个二进制串都可以作为自变量进入这个“函数”，然后会出来一个固定为128位的二进制串。

我们先用一个例子来过一下这个过程，然后用文字描述算法细节。

比如加密一个普通的内容为hello的ASCII文本文件，这个文件由40个二进制位存储在计算机上：

01101000 01100101 01101100 01101100 01101111 [存储]

算法开始：

进行二进制位补充。具体这样补充：

从这40位的后面开始，先补充一个1位，再补充0位，一直到总共448位长度（也就是补充407个0位）。接着在后面写入原始信息长度与2^64的模。也就是40mod(2^64)=40，40转化为2进制为101000，用64存储就是：

00101000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [存储]

二进制位补充完成。

得到内容（共512位）：

01101000 01100101 01101100 01101100 01101111 1 (407个0)00101000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [存储]

然后对这个512个位平均分成16组，每组32个位：

第1组：01101000 01100101 01101100 01101100

第2组：01101111 10000000 00000000 00000000

…

第32组：00000000 00000000 00000000 00000000

然后使用四个常数进行运算，分别是：

A=0x67452301,B=0xefcdab89,C=0x98badcfe,D=0x10325476。

A： 00000001 00100011 01000101 01100111 [存储]

B： 10001001 10101011 11001101 11101111 [存储]

C： 11111110 11011100 10111010 10011000 [存储]

D： 01110110 01010100 00110010 00010000 [存储]

一共进行64轮运算：

先说明运算符：

=赋值运算符： i=0意味着把0赋值给i，也就是让i的值为0

&按位与运算符：1010b & 1100b的值为1000b

or按位或运算符：1010b or 1100b的值为1110b

^按位异或运算符：1010b ^ 1100b的值为0110b

~按位取反运算符：~1010b的值为0101b

<<按位循环左移运算符：1100b << 3的值为0110b

mod是取模运算符：33 mod 16 的值为1

i==64是判断i是否和64相等

以上计算由一个地方需要说明，就是给t赋值计算的时候，不考虑进位，每个数都是由32位二进制串表示，加的时候若有进位则进位丢失，得到的t也用32位二进制串表示。
以上数还有两个没有提到，k[i]和s[i]：

s[i]取值为以下数组的第i+1个数

{ 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 }

如s[0]==7,s[3]=22...

k[i]取值为以下数组的第i+1个数

{ 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 }

进行完这些运算后，A,B,C,D的值都获得了更新

A： xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx [存储]

B： xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx [存储]

C： xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx [存储]

D： xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx [存储]

把这四个数A -> B -> C -> D按照从低内存到高内存排列起来，共128位，这就是MD5算法的输出。

MD5算法流程

unsigned int g_nTable[4][16] = {

{ 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 }};

b) 初始化每步左循环移位的位数 g_nMove[4][16]，对应每轮处理的 4×16＝64 步处理。由于是常量，也可以在计算时直接嵌入数据。此数据有规律，可以只用 16 个。

int g_nMove[4][16] = {

{	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	}};

c) 初始化 g_nResult[4]。g_nResult 参与下一组消息的处理过程，同时存放该组计算结果,新的

g_nResult 又参与下一组消息的处理，直至最后一组计算结束，g_nResult 即为所需的 MD5 码。

g_nResult 数组成员应为 32 位长，这样总计 32×4＝128 位。

unsigned int g_nResult[4] = { 0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476 };

二. 消息读取与填充

a) 将一段未处理消息（如文件内容）读取到缓冲区（如某一较大数组或动态申请的内存）中，最好一次读取 64n 个字节，这样就是 n 组，方便处理。

b) 判断消息是否已经读完，没有则直接前往三.分组处理进行计算，如果已经读完了就应该进行适

当的填充。

c) 对消息进行填充，使其字节数除以 64 时余数为 56。比如在处理一个文件时,

1) 最后一次读取为 70 字节，70％64＝6 小于 56，则对其填充 56－6＝50 个字节，得（70＋50）

％64＝56。注：若消息为 64n 倍数字节，则最后一次读取 0 字节，据本规则将填充 56 字节。 2) 最后一次读取为 124 字节，124％64＝60 大于 56 了，则先将这一组填满（此处为 4 字节）再

在下一组空间上填 56 个字节，得（124＋4＋56）％64＝56。

3) 最后一次读取为 120 字节，120％64＝56 等于 56，此时仍需填充，填充字节总数为 64，即一组，得（120＋64）％64＝56。

知道了填充方法，那用什么填充呢？填充的第一个字节为 128，其余全为 0，此处 128 二进制表示为 1000 0000（vc 中如(unsigned char）128），0 的二进制应为 0000 0000。经过上面的填充后最后一组只有 56 字节，还有 8 字节干吗呢？这 8 个字节用于存放消息填充前的总长度，而且单位不是字节，是位。vc 下可以用 unsigned int64 类型变量保存消息总长度，操作文件时直接取得文件长度后乘 8 保存到变量中，填充时用内存拷贝函数拷贝过去即可。

d) 进入三.分组处理进行最后一次计算

三. 分组处理

这是最核心的环节了，在这里对每一组消息进行 4 轮、每轮 16 步、总计 64 步的处理。这里需要先引

入 4 个逻辑函数，分别对应 4 轮运算，它们将参与运算。第一轮逻辑函数：F(b,c,d)=(b&c)|((~b)&d) 参与第一轮的 16 步运算第二轮逻辑函数：G(b,c,d)=(b&d)|(c&(~d)) 参与第二轮的 16 步运算第三轮逻辑函数：H(b,c,d)= b^c^d 参与第三轮的 16 步运算第四轮逻辑函数：I(b,c,d)= c^(b|(~d)) 参与第四轮的 16 步运算

再引入一个移位函数 MOVE(X,n)，它将整型变量 X 左循环移 n 位，如变量 X 为 32 位，则 MOVE(X,n)= (X

<< n) | (X >> (32 - n))。

& 为按位与，| 为按位或，~ 为按位取非，^ 为按位异或。b、c、d、F、G、H、I 均为 unsigned int。

处理开始：

将数组 g_nResult 内容复制到数组 g_nTemp（类型大小与 g_nResult 同）。
将新的一组内容从缓冲区读到 unsigned int unBuff[16]中。

c) 第一轮计算：j 从 0 循环到 15，轮数 ln=0，i=j%16=j。将下面 1）- 4）执行 16 遍。

1. unsigned int Temp = g_nTemp[0] + F(g_nTemp[1], g_nTemp[2], g_nTemp[3]) + unBuff[i]

+ g_nTable[ln][i]。

1. Temp = MOVE(Temp, g_nMove[ln][j])。
2. g_nTemp[0] = g_nTemp[1] + Temp。

4) 将 g_nTemp 数组右循环移位 4 字节，即{Temp = g_nTemp[3]; g_nTemp[3]= g_nTemp[2]; g_nTemp[2]= g_nTemp[1]; g_nTemp[1]= g_nTemp[0]; g_nTemp[0]= Temp;}

d) 第二轮计算：j 从 0 循环到 15, 轮数 ln=1，i=(1+5*j)%16，使用循环函数 G，其他同第一轮。 e) 第三轮计算：j 从 0 循环到 15, 轮数 ln=2，i=(5+3*j)%16，使用循环函数 H，其他同第一轮。 f) 第四轮计算：j 从 0 循环到 15, 轮数 ln=3，i=(7*j)%16，使用循环函数 I，其他同第一轮。

g) 累加结果：g_nResult[0] += g_nTemp [0]; g_nResult[1] += g_nTemp [1]; g_nResult[2] += g_nTemp [2]; g_nResult[3] += g_nTemp [3];

h) 如果缓冲区中还有分组未处理完，则转回到 a）。

四. 输出结果

判断消息（或文件）是否已经处理完了，如果没有则转到二.消息读取与填充，如果已经处理完了，则 g_nResult 就是结果，从低地址开始用 16 进制逐个输出字节便得 MD5 码。

部分代码

void MD5::encode(const bit32* input, byte* output, size_t length) {

  for (size_t i = 0, j = 0; j < length; ++i, j += 4) {
    output[j]= (byte)(input[i] & 0xff);
    output[j + 1] = (byte)((input[i] >> 8) & 0xff);
    output[j + 2] = (byte)((input[i] >> 16) & 0xff);
    output[j + 3] = (byte)((input[i] >> 24) & 0xff);
  }
}
void MD5::decode(const byte* input, bit32* output, size_t length) {
  for (size_t i = 0, j = 0; j < length; ++i, j += 4) {
    output[i] = ((bit32)input[j]) | (((bit32)input[j + 1]) << 8) |
    (((bit32)input[j + 2]) << 16) | (((bit32)input[j + 3]) << 24);
  }
}
string MD5::toStr() {
  const byte* digest_ = getDigest();
  string str;
  str.reserve(16 << 1);
  for (size_t i = 0; i < 16; ++i) {
    int t = digest_[i];
    int a = t / 16;
    int b = t % 16;
    str.append(1, HEX_NUMBERS[a]);
    str.append(1, HEX_NUMBERS[b]);
  }
  return str;
}

码农公寓

相关文章