密码学初探 – MD5 算法详解

最近在一密码学大神同学的引诱下,开始学习密码学,在博客中记录下。

何为不可逆加密

不可逆加密的概念很简单,本质上就是字符串 hash,即由 A 通过 f(A) 函数可以得到加密后的文本 B,由函数的定义:确定 A 的情况下 B 是唯一的,且因为密文的长度可小于明文,所以 B 无法解密还原为 A。

举一个小例子,要对字符串「Imchasingperfection」进行不可逆加密,取其前四位作为密文内容「Imch」,这就是一个非常简单的不可逆加密算法,只是,这个算法太过低劣了。

一个优秀的不可逆加密算法需要难以还原,以及在随机情况下加密冲突概率尽可能的低。

常见不可逆加密算法

常见不可逆加密算法有 MD5,SHA,CRC 等...

本文主要讨论的加密算法是全世界最重要算法之一,MD5。

MD5 算法

介绍

MD5 算法是一种信息摘要算法,该算法的输入是任意长度的信息,产生一个 128 位(16 字节)的报文摘要,两个不同的信息产生相同的摘要概率非常地低,从一个给定的摘要逆向产生原始信息更加困难。

算法流程

说明

中文看起来会比较费力...因为位\((byte)\) 和位\((bit)\) 是两个概念,容易混淆,先说明一下:

以字符串「rainyzou」为例,他的长度为 8 位\((byte)\),但是其二进制位有 64 位\((bit)\),通常,一位\((byte)\) 字符的二进制位为 8 位\((bit)\),在文章将在括号中使用 \((byte)\) 和 \((bit)\) 作区分。

算法每步将给出 C++ 代码(代码丑陋见谅~),文章最后有完整代码下载。

1.第一步补位

设输入的字符串长度为 \(Len(byte)\),则其二进制位为 \((8 \times Len)(bit)\),在进行 MD5 算法之前需要进行补位\((bit)\),设补位后的长度为 \(N(byte)\),即 \((8 \times N)(bit)\)。则需要使:

\[N(byte) \equiv 56(mod~64)\]

即:

\[(N \times 8)(bit) \equiv 448(mod~512)\]

需要注意的是,补位操作必须进行,即使 \(N\) 已经满足同余方程,仍然需要补 512 位\((bit)\)。

所以,补位\((bit)\) 范围为 \([1,~512]\) 位\((bit)\)。

Code   ViewPrint
  1. #define MAXN 1010 //字符串长度
  2. char buff[MAXN]; //输入字符串
  3. uint32_t message[MAXN]; //将字符串转换为整数数组
  4. uint64_t length; //输入原始长度(byte)
  5. uint64_t n; //第一步补位后的长度(byte)
  6. memset(message, 0, sizeof(message));
  7. fread(buff, 1, sizeof(buff), stdin);
  8. n = length = strlen(buff) - 1;
  9. n += (n % 64 == 56) ? 64 : (((56 - n % 64) + 64) % 64); //计算第一步补位后的长度 n
  10. for (int i = 0; (uint64_t)i < length; i++) message[i] = uint_32(buff[i]);
  11. for (int i = length; (uint64_t)i < n; i++) message[i] = ((uint64_t)i == length) ? 128 : 0; //第一步补位
  12. //128 为 (1000 0000)2,即二进制下最高位为 1,其余为 0 的八位整数

2.第二步补位

在第一步补位中将串的长度补到了只差 64 位\((bit)\) 就为 512 的倍数,在这一步补位中,我们会将串的长度\((bit)\) 补位到 512 的倍数。

首先要将串的原始长度\((bit)\) 表示为一个 64 位整数,并将它添加在上一步的结果之后,如果串的原始长度大于 \(2^{64}(bit)\),那么将 64 位以上的高位删去,只保留低的 64 位\((bit)\)。

同时,这个 64 位整数将用两个字来表示,且低位在前(小端排序)。

至此,原串可以被表示为:\([S_0,~S_1,~S_2,~...,~S_{m-2},~S_{m-1}]\),其中 m 为 16 的倍数。

Code   ViewPrint
  1. message[n] = (uint8_t)(length / (uint64_t)pow(256, 7));
  2. for (int i = 1; i < 8; i++) message[n+i] = (length % (uint64_t)pow(256, 8-i)) / (uint64_t)pow(256, 8-i-1); //补位 64 位整数
  3. n += 8;
  4. for (int i = 0; (uint32_t)i < (n>>2); i++) message[i] = message[4*i+3]*(uint32_t)pow(256, 3) + message[4*i+2]*(uint32_t)pow(256, 2) + message[4*i+1]*256 + message[4*i];
  5. //将原串转为 32 位整数
  6. n /= 4;

3.初始化缓冲区

用四字\((byte)\) 的缓冲器来计算 MD5,在 MD5 算法中有四个 32 位\((bit)\) 16 进制的整数的寄存器,称为链接变量,低字节在前,我们按如下设置:

\[Word~A~=~0x~67452301\]

\[Word~B~=~0x~efcdab89\]

\[Word~C~=~0x~98badcfe\]

\[Word~D~=~0x~10325476\]

4.主要循环

首先我们定义 4 个非线性的辅助函数,函数的参数和返回值均为 32 位\(bit\) 字。

\[F(X,~Y,~Z)~=~(X\wedge Y) \vee (\neg X\wedge Z)\]

\[G(X,~Y,~Z)~=~(X\wedge Z) \vee (Y\wedge \neg Z)\]

\[H(X,~Y,~Z)~=~X\oplus Y\oplus Z\]

\[I(X,~Y,~Z)~=~Y\oplus (X \vee \neg Z)\]

其中,\(\oplus、\wedge、\vee、\neg,~分别表示~xor、and、or、not\)

在上述函数的基础上,我们定义四个宏:

\[FF(A,~B,~C,~D,~k,~s,~j)~\Longleftrightarrow~a = b + ((a + F(b,c,d) + k + j) << s)\]

\[GG(A,~B,~C,~D,~k,~s,~j)~\Longleftrightarrow~a = b + ((a + G(b,c,d) + k + j) << s)\]

\[HH(A,~B,~C,~D,~k,~s,~j)~\Longleftrightarrow~a = b + ((a + H(b,c,d) + k + j) << s)\]

\[II(A,~B,~C,~D,~k,~s,~j)~\Longleftrightarrow~a = b + ((a + I(b,c,d) + k + j) << s)\]

具体代码如下:

Code   ViewPrint
  1. for (int i = 0; i < (N>>4); i++) {
  2.     for (int j = 0; j < 16; j++) T[j] = message[i*16 + j]; //从原串数组复制
  3.     TA = A; TB = B; TC = C; TD = D; //因会修改 ABCD,所以先备份信息
  4.     //第一轮循环
  5.     FF (a, b, c, d, T[0], S[0][0], 0xd76aa478); FF (d, a, b, c, T[1], S[0][1], 0xe8c7b756); FF (c, d, a, b, T[2], S[0][2], 0x242070db); FF (b, c, d, a, T[3], S[0][3], 0xc1bdceee); //第一轮第一次循环
  6.     FF (a, b, c, d, T[4], S[0][0], 0xf57c0faf); FF (d, a, b, c, T[5], S[0][1], 0x4787c62a); FF (c, d, a, b, T[6], S[0][2], 0xa8304613); FF (b, c, d, a, T[7], S[0][3], 0xfd469501); //第一轮第二次循环
  7.     FF (a, b, c, d, T[8], S[0][0], 0x698098d8); FF (d, a, b, c, T[9], S[0][1], 0x8b44f7af); FF (c, d, a, b, T[10], S[0][2], 0xffff5bb1); FF (b, c, d, a, T[11], S[0][3], 0x895cd7be); //第一轮第三次循环
  8.     FF (a, b, c, d, T[12], S[0][0], 0x6b901122); FF (d, a, b, c, T[13], S[0][1], 0xfd987193); FF (c, d, a, b, T[14], S[0][2], 0xa679438e); FF (b, c, d, a, T[15], S[0][3], 0x49b40821); //第一轮第四次循环
  9.     //第二轮循环
  10.     GG (a, b, c, d, T[1], S[1][0], 0xf61e2562); GG (d, a, b, c, T[6], S[1][1], 0xc040b340); GG (c, d, a, b, T[11], S[1][2], 0x265e5a51); GG (b, c, d, a, T[0], S[1][3], 0xe9b6c7aa); //第二轮第一次循环
  11.     GG (a, b, c, d, T[5], S[1][0], 0xd62f105d); GG (d, a, b, c, T[10], S[1][1], 0x2441453); GG (c, d, a, b, T[15], S[1][2], 0xd8a1e681); GG (b, c, d, a, T[4], S[1][3], 0xe7d3fbc8); //第二轮第二次循环
  12.     GG (a, b, c, d, T[9], S[1][0], 0x21e1cde6); GG (d, a, b, c, T[14], S[1][1], 0xc33707d6); GG (c, d, a, b, T[3], S[1][2], 0xf4d50d87); GG (b, c, d, a, T[8], S[1][3], 0x455a14ed); //第二轮第三次循环
  13.     GG (a, b, c, d, T[13], S[1][0], 0xa9e3e905); GG (d, a, b, c, T[2], S[1][1], 0xfcefa3f8); GG (c, d, a, b, T[7], S[1][2], 0x676f02d9); GG (b, c, d, a, T[12], S[1][3], 0x8d2a4c8a); //第二轮第四次循环
  14.     //第三轮循环
  15.     HH (a, b, c, d, T[5], S[2][0], 0xfffa3942); HH (d, a, b, c, T[8], S[2][1], 0x8771f681); HH (c, d, a, b, T[11], S[2][2], 0x6d9d6122); HH (b, c, d, a, T[14], S[2][3], 0xfde5380c); //第三轮第一次循环
  16.     HH (a, b, c, d, T[1], S[2][0], 0xa4beea44); HH (d, a, b, c, T[4], S[2][1], 0x4bdecfa9); HH (c, d, a, b, T[7], S[2][2], 0xf6bb4b60); HH (b, c, d, a, T[10], S[2][3], 0xbebfbc70); //第三轮第二次循环
  17.     HH (a, b, c, d, T[13], S[2][0], 0x289b7ec6); HH (d, a, b, c, T[0], S[2][1], 0xeaa127fa); HH (c, d, a, b, T[3], S[2][2], 0xd4ef3085); HH (b, c, d, a, T[6], S[2][3],  0x4881d05); //第三轮第三次循环
  18.     HH (a, b, c, d, T[9], S[2][0], 0xd9d4d039); HH (d, a, b, c, T[12], S[2][1], 0xe6db99e5); HH (c, d, a, b, T[15], S[2][2], 0x1fa27cf8); HH (b, c, d, a, T[2], S[2][3], 0xc4ac5665); //第三轮第四次循环
  19.     //第四轮循环
  20.     II (a, b, c, d, T[0], S[3][0], 0xf4292244); II (d, a, b, c, T[7], S[3][1], 0x432aff97); II (c, d, a, b, T[14], S[3][2], 0xab9423a7); II (b, c, d, a, T[5], S[3][3], 0xfc93a039); //第四轮第一次循环
  21.     II (a, b, c, d, T[12], S[3][0], 0x655b59c3); II (d, a, b, c, T[3], S[3][1], 0x8f0ccc92); II (c, d, a, b, T[10], S[3][2], 0xffeff47d); II (b, c, d, a, T[1], S[3][3], 0x85845dd1); //第四轮第二次循环
  22.     II (a, b, c, d, T[8], S[3][0], 0x6fa87e4f); II (d, a, b, c, T[15], S[3][1], 0xfe2ce6e0); II (c, d, a, b, T[6], S[3][2], 0xa3014314); II (b, c, d, a, T[13], S[3][3], 0x4e0811a1); //第四轮第三次循环
  23.     II (a, b, c, d, T[4], S[3][0], 0xf7537e82); II (d, a, b, c, T[11], S[3][1], 0xbd3af235); II (c, d, a, b, T[2], S[3][2], 0x2ad7d2bb); II (b, c, d, a, T[9], S[3][3], 0xeb86d391); //第四轮第四次循环
  24.     //循环结束
  25.     A += TA, B += TB, C += TC, D += TD; //由低位到高位得到 A, B, C, D
  26. }

5.输出

\(N \div 16\) 次大循环结束后,得到了四个 32 位\((bit)\) 的整数,A 是最低位,D 是最高位,将其按 16 进制拼接起来就得到了 MD5 的值。

Code   ViewPrint
  1. char ch[MAXN], ans[MAXN];
  2. ans = "";
  3. sprintf(ch, "%x", A); strcat(ans, ch);
  4. sprintf(ch, "%x", B); strcat(ans, ch);
  5. sprintf(ch, "%x", C); strcat(ans, ch);
  6. sprintf(ch, "%x", D); strcat(ans, ch);

ans 中存放的就是加密的 MD5 了~至此算法全部结束~

p.s.MD5 算法本身非常简单,代码也很短,但是这篇文章前前后后写了超过十个小时:

密码学初探 - MD5 算法详解

密码学初探 - MD5 算法详解

包括反复的调代码,MD5 算法虽然简单...但是坑还是挺多的~不过能学会 MD5 的算法也算是我学习密码学万里长征的第一步(ง •̀_•́)ง...共勉~

文件下载

zyq

如果我的文章对您有帮助,请我喝杯咖啡吧~

支付宝转账打赏⬆️

微信钱包转账打赏⬆️

目前评论:5   其中:访客  5   博主  0

  1. 韩国时尚购物起义 0

    我们的网页不是网页,那是活动的人。

  2. Xbin'Blog 0

    MD5,现在的用处还不错

  3. 个人小站 0

    佩服

  4. 崔可 0

    这个,太深奥了,我完全看不懂

  5. Unee Wang 2

    嗯,大概是理解了。不过不打算深入了

评论加载中...

发表评论

:?::razz::sad::evil::!::smile::oops::grin::eek::shock::???::cool::lol::mad::twisted::roll::wink::idea::arrow::neutral::cry::mrgreen: