NTL密码算法开源库拓展——MD5
2021/12/25 14:07:33
本文主要是介绍NTL密码算法开源库拓展——MD5,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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 遍。
-
- unsigned int Temp = g_nTemp[0] + F(g_nTemp[1], g_nTemp[2], g_nTemp[3]) + unBuff[i]
+ g_nTable[ln][i]。
-
- Temp = MOVE(Temp, g_nMove[ln][j])。
- 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; }
这篇关于NTL密码算法开源库拓展——MD5的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-25初学者必备:订单系统资料详解与实操教程
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南
- 2024-12-24微信支付系统资料入门教程
- 2024-12-24微信支付资料详解:新手入门指南
- 2024-12-24Hbase资料:新手入门教程
- 2024-12-24Java部署资料
- 2024-12-24Java订单系统资料:新手入门教程
- 2024-12-24Java分布式资料入门教程
- 2024-12-24Java监控系统资料详解与入门教程