md5
- 填充
在消息后面先填充一个1，再填充0，直到消息长度mod 512=448，之后再将消息长度的低64位填充到消息结尾
- 定义几个运算
F(x,y,z)=(x&y)|(~x&z)
G(x,y,z)=(x&z)|(y&~z)
H(x,y,z)=x^y^z
I(x,y,z)=y^(x|~z)
ROL32(x,i) 左移32位
填充后的消息以512为一个分组，每个分组可以分成16个32位子分组$W_j(0<j<15)$
FF(a,b,c,d,M_j,s,t_i): a=b+ROL32(a+(F(b,c,d)+M_j+t_i),s)
GG(a,b,c,d,M_j,s,t_i): a=b+ROL32(a+(G(b,c,d)+M_j+t_i),s)
HH(a,b,c,d,M_j,s,t_i): a=b+ROL32(a+(H(b,c,d)+M_j+t_i),s)
II(a,b,c,d,M_j,s,t_i): a=b+ROL32(a+(I(b,c,d)+M_j+t_i),s)
- 定义初始化向量
A=0x01234567
B=0x89abcdef
C=0xfedcba98
D=0x76543210
- 对于每一个分组，将上一次计算的A,B,C,D复制到a,b,c,d中，进行下面的4轮计算，然后将a,b,c,d分别加到A,B,C,D上，下一组继续运行此算法，最终输出就是A||B||C||D，||在这里代表拼接
# 第一轮
for i in range(0,16,4):
FF(a,b,c,d,M[pos[0][i]],s[0][0],t[0][i])
FF(d,a,b,c,M[pos[0][i+1]],s[0][1],t[0][i+1])
FF(d,a,b,c,M[pos[0][i+2]],s[0][2],t[0][i+2])
FF(d,a,b,c,M[pos[0][i+3]],s[0][3],t[0][i+3])
# 第二轮
for i in range(0,16,4):
GG(a,b,c,d,M[pos[0][i]],s[0][0],t[0][i])
GG(d,a,b,c,M[pos[0][i+1]],s[0][1],t[0][i+1])
GG(d,a,b,c,M[pos[0][i+2]],s[0][2],t[0][i+2])
GG(d,a,b,c,M[pos[0][i+3]],s[0][3],t[0][i+3])
# 第三轮
for i in range(0,16,4):
HH(a,b,c,d,M[pos[0][i]],s[0][0],t[0][i])
HH(d,a,b,c,M[pos[0][i+1]],s[0][1],t[0][i+1])
HH(d,a,b,c,M[pos[0][i+2]],s[0][2],t[0][i+2])
HH(d,a,b,c,M[pos[0][i+3]],s[0][3],t[0][i+3])
# 第四轮
for i in range(0,16,4):
II(a,b,c,d,M[pos[0][i]],s[0][0],t[0][i])
II(d,a,b,c,M[pos[0][i+1]],s[0][1],t[0][i+1])
II(d,a,b,c,M[pos[0][i+2]],s[0][2],t[0][i+2])
II(d,a,b,c,M[pos[0][i+3]],s[0][3],t[0][i+3])
其中pos和t，s数组会在代码中体现
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <inttypes.h>
#include <stdlib.h>
#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 ROL32(x,i) (((x)<<(i))|((x)>>(32-(i))))
#define FF(a,b,c,d,M_j,s,t_i) ((b)+ROL32((a)+(F(b,c,d)+(M_j)+(t_i)),s))
#define GG(a,b,c,d,M_j,s,t_i) ((b)+ROL32((a)+(G(b,c,d)+(M_j)+(t_i)),s))
#define HH(a,b,c,d,M_j,s,t_i) ((b)+ROL32((a)+(H(b,c,d)+(M_j)+(t_i)),s))
#define II(a,b,c,d,M_j,s,t_i) ((b)+ROL32((a)+(I(b,c,d)+(M_j)+(t_i)),s))
uint8_t s[] = {
7,12,17,22,
5,9,14,20,
4,11,16,23,
6,10,15,21
};
uint32_t t[] = {
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
};
void printArray(char *name,uint8_t *data,size_t len){
printf("===========%s==============\n",name);
for(size_t i=0;i<len;i++){
printf("%02x,",data[i]);
}
printf("\n");
}
void md5(uint8_t *data,size_t len,uint32_t res[4]){
uint32_t iv[4] = {0x67452301,0xefcdab89,0x98badcfe,0x10325476};
uint32_t a,b,c,d;
size_t pos;
// 消息填充
size_t plen = ((len+1+63)>>5)<<5;
uint8_t *pdata = alloca(plen);
memcpy(pdata,data,len);
pdata[len]=0x80;
memset(&pdata[len+1],0,plen-len-1);
memcpy(&pdata[plen-8],&plen,8);
// printf("%lld\n",plen);
// printArray("my",pdata,plen);
// 进行计算
for(size_t i=0;i<plen;i+=64){
a = iv[0];
b = iv[1];
c = iv[2];
d = iv[3];
// printf("iv[%d]: %08x %08x %08x %08x\n",i/64,a,b,c,d);
// 第一轮
pos=0;
for(size_t j=0;j<16;j+=4){
a = FF(a,b,c,d,*(uint32_t*)&pdata[pos*4+i*64],s[0],t[j]);
// printf("%08x %08x %08x %08x\n",a,b,c,d);
pos+=1;
d = FF(d,a,b,c,*(uint32_t*)&pdata[pos*4+i*64],s[1],t[j+1]);
pos+=1;
c = FF(c,d,a,b,*(uint32_t*)&pdata[pos*4+i*64],s[2],t[j+2]);
pos+=1;
b = FF(b,c,d,a,*(uint32_t*)&pdata[pos*4+i*64],s[3],t[j+3]);
pos+=1;
}
// 第二轮
pos=1;
for(size_t j=0;j<16;j+=4){
a = GG(a,b,c,d,*(uint32_t*)&pdata[pos*4+i*64],s[4],t[16+j]);
pos=(pos+5)&0xf;
d = GG(d,a,b,c,*(uint32_t*)&pdata[pos*4+i*64],s[5],t[16+j+1]);
pos=(pos+5)&0xf;
c = GG(c,d,a,b,*(uint32_t*)&pdata[pos*4+i*64],s[6],t[16+j+2]);
pos=(pos+5)&0xf;
b = GG(b,c,d,a,*(uint32_t*)&pdata[pos*4+i*64],s[7],t[16+j+3]);
pos=(pos+5)&0xf;
}
// 第三轮
pos=5;
for(size_t j=0;j<16;j+=4){
a = HH(a,b,c,d,*(uint32_t*)&pdata[pos*4+i*64],s[8],t[32+j]);
pos=(pos+3)&0xf;
d = HH(d,a,b,c,*(uint32_t*)&pdata[pos*4+i*64],s[9],t[32+j+1]);
pos=(pos+3)&0xf;
c = HH(c,d,a,b,*(uint32_t*)&pdata[pos*4+i*64],s[10],t[32+j+2]);
pos=(pos+3)&0xf;
b = HH(b,c,d,a,*(uint32_t*)&pdata[pos*4+i*64],s[11],t[32+j+3]);
pos=(pos+3)&0xf;
printf("%08x %08x %08x %08x\n",a,b,c,d);
}
// 第四轮
pos=0;
for(size_t j=0;j<16;j+=4){
a = II(a,b,c,d,*(uint32_t*)&pdata[pos*4+i*64],s[12],t[48+j]);
pos=(pos+7)&0xf;
d = II(d,a,b,c,*(uint32_t*)&pdata[pos*4+i*64],s[13],t[48+j+1]);
pos=(pos+7)&0xf;
c = II(c,d,a,b,*(uint32_t*)&pdata[pos*4+i*64],s[14],t[48+j+2]);
pos=(pos+7)&0xf;
b = II(b,c,d,a,*(uint32_t*)&pdata[pos*4+i*64],s[15],t[48+j+3]);
pos=(pos+7)&0xf;
}
iv[0]+=a;
iv[1]+=b;
iv[2]+=c;
iv[3]+=d;
}
memcpy(res,iv,sizeof(uint32_t)*4);
}
int main(){
uint32_t res[4];
md5("deadbeef",8,res);
printArray("mymd5",(uint8_t*)res,16);
return 0;
}
参考资料
《应用密码学：协议、算法与C源程序》
发表于 2020-12-28 22:27
