Chinaunix首页 | 论坛 | 博客
  • 博客访问: 664398
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1114
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2016-01-02 22:24:35

MD5 的RFC文档路径:
或者 

MD5算法过程:

    对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位分组级联后将生成一个128位散列值。

     第一步、填充:如果输入信息的长度(bit)对512求余的结果不等于448,就需要填充使得对512求余的结果等于448。填充的方法是填充一个1和n个0。填充完后,信息的长度就为N*512+448(bit);

     第二步、记录信息长度:用64位来存储填充前信息长度。这64位加在第一步结果的后面,这样信息长度就变为N*512+448+64=(N+1)*512位。

     第三步、装入标准的幻数(四个整数):标准的幻数(物理顺序)是(A=(01234567)16,B=(89ABCDEF)16,C=(FEDCBA98)16,D=(76543210)16)。如果在程序中定义应该是(A=0X67452301L,B=0XEFCDAB89L,C=0X98BADCFEL,D=0X10325476L)。有点晕哈,其实想一想就明白了。

     第四步、四轮循环运算:循环的次数是分组的个数(N+1) 

     1)将每一512字节细分成16个小组,每个小组64位(8个字节)
     
     2)先认识四个线性函数(&是与,|是或,~是非,^是异或)
  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))
    
    3)设Mj表示消息的第j个子分组(从0到15),<<
  FF(a,b,c,d,Mj,s,ti)表示a=b+((a+F(b,c,d)+Mj+ti)<<<s)
  GG(a,b,c,d,Mj,s,ti)表示a
=b+((a+G(b,c,d)+Mj+ti)<<<s)
  HH(a,b,c,d,Mj,s,ti)表示a
=b+((a+H(b,c,d)+Mj+ti)<<<s)
  II(a,b,c,d,Mj,s,ti)表示a
=b+((a+I(b,c,d)+Mj+ti)<<<s)

    4)四轮运算
第一轮
a
=FF(a,b,c,d,M0,7,0xd76aa478)
b
=FF(d,a,b,c,M1,12,0xe8c7b756)
c
=FF(c,d,a,b,M2,17,0x242070db)
d
=FF(b,c,d,a,M3,22,0xc1bdceee)
a
=FF(a,b,c,d,M4,7,0xf57c0faf)
b
=FF(d,a,b,c,M5,12,0x4787c62a)
c
=FF(c,d,a,b,M6,17,0xa8304613)
d
=FF(b,c,d,a,M7,22,0xfd469501)
a
=FF(a,b,c,d,M8,7,0x698098d8)
b
=FF(d,a,b,c,M9,12,0x8b44f7af)
c
=FF(c,d,a,b,M10,17,0xffff5bb1)
d
=FF(b,c,d,a,M11,22,0x895cd7be)
a
=FF(a,b,c,d,M12,7,0x6b901122)
b
=FF(d,a,b,c,M13,12,0xfd987193)
c
=FF(c,d,a,b,M14,17,0xa679438e)
d
=FF(b,c,d,a,M15,22,0x49b40821)

第二轮
a
=GG(a,b,c,d,M1,5,0xf61e2562)
b
=GG(d,a,b,c,M6,9,0xc040b340)
c
=GG(c,d,a,b,M11,14,0x265e5a51)
d
=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a
=GG(a,b,c,d,M5,5,0xd62f105d)
b
=GG(d,a,b,c,M10,9,0x02441453)
c
=GG(c,d,a,b,M15,14,0xd8a1e681)
d
=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a
=GG(a,b,c,d,M9,5,0x21e1cde6)
b
=GG(d,a,b,c,M14,9,0xc33707d6)
c
=GG(c,d,a,b,M3,14,0xf4d50d87)
d
=GG(b,c,d,a,M8,20,0x455a14ed)
a
=GG(a,b,c,d,M13,5,0xa9e3e905)
b
=GG(d,a,b,c,M2,9,0xfcefa3f8)
c
=GG(c,d,a,b,M7,14,0x676f02d9)
d
=GG(b,c,d,a,M12,20,0x8d2a4c8a)

第三轮
a
=HH(a,b,c,d,M5,4,0xfffa3942)
b
=HH(d,a,b,c,M8,11,0x8771f681)
c
=HH(c,d,a,b,M11,16,0x6d9d6122)
d
=HH(b,c,d,a,M14,23,0xfde5380c)
a
=HH(a,b,c,d,M1,4,0xa4beea44)
b
=HH(d,a,b,c,M4,11,0x4bdecfa9)
c
=HH(c,d,a,b,M7,16,0xf6bb4b60)
d
=HH(b,c,d,a,M10,23,0xbebfbc70)
a
=HH(a,b,c,d,M13,4,0x289b7ec6)
b
=HH(d,a,b,c,M0,11,0xeaa127fa)
c
=HH(c,d,a,b,M3,16,0xd4ef3085)
d
=HH(b,c,d,a,M6,23,0x04881d05)
a
=HH(a,b,c,d,M9,4,0xd9d4d039)
b
=HH(d,a,b,c,M12,11,0xe6db99e5)
c
=HH(c,d,a,b,M15,16,0x1fa27cf8)
d
=HH(b,c,d,a,M2,23,0xc4ac5665)

第四轮
a
=II(a,b,c,d,M0,6,0xf4292244)
b
=II(d,a,b,c,M7,10,0x432aff97)
c
=II(c,d,a,b,M14,15,0xab9423a7)
d
=II(b,c,d,a,M5,21,0xfc93a039)
a
=II(a,b,c,d,M12,6,0x655b59c3)
b
=II(d,a,b,c,M3,10,0x8f0ccc92)
c
=II(c,d,a,b,M10,15,0xffeff47d)
d
=II(b,c,d,a,M1,21,0x85845dd1)
a
=II(a,b,c,d,M8,6,0x6fa87e4f)
b
=II(d,a,b,c,M15,10,0xfe2ce6e0)
c
=II(c,d,a,b,M6,15,0xa3014314)
d
=II(b,c,d,a,M13,21,0x4e0811a1)
a
=II(a,b,c,d,M4,6,0xf7537e82)
b
=II(d,a,b,c,M11,10,0xbd3af235)
c
=II(c,d,a,b,M2,15,0x2ad7d2bb)
d
=II(b,c,d,a,M9,21,0xeb86d391)

    5)每轮循环后,将A,B,C,D分别加上a,b,c,d,然后进入下一循环。

下面是C语言的一个实现:

头文件md5.h

点击(此处)折叠或打开

  1. #ifndef MD5_H
  2. #define MD5_H
  3.  
  4. typedef struct {
  5.   int state[4];                /* state (ABCD) */
  6.   int count[2];                /* 记录处理bit数 */
  7.   unsigned char buffer[64]; /* input buffer */
  8. } MD5_CTX;
  9.  

  10. #define S11 7
  11. #define S12 12
  12. #define S13 17
  13. #define S14 22

  14. #define S21 5
  15. #define S22 9
  16. #define S23 14
  17. #define S24 20

  18. #define S31 4
  19. #define S32 11
  20. #define S33 16
  21. #define S34 23

  22. #define S41 6
  23. #define S42 10
  24. #define S43 15
  25. #define S44 21

  26. #define F(x,y,z) (((x) & (y)) | (~(x) & (z)))
  27. #define G(x,y,z) (((x) & (z)) | ((y) & ~(z)))
  28. #define H(x,y,z) ((x) ^ (y )^ (z))
  29. #define I(x,y,z) ((y) ^ ((x) | ~(z)))

  30. //将x循环右移n位
  31. #define ROTATE_LEFT(x,n) (((x) << (n)) | ((x) >> (32-(n))))

  32. #define FF(a,b,c,d,x,s,ac) \
  33.       do { \
  34.           a += F(b,c,d) + x + ac; \
  35.           a = ROTATE_LEFT(a,s); \
  36.           a += b; \
  37.       } while(0)

  38. #define GG(a,b,c,d,x,s,ac) \
  39.     do { \
  40.           a += G(b,c,d) + x + ac; \
  41.           a = ROTATE_LEFT(a,s); \
  42.           a += b; \
  43.     } while(0)

  44. #define HH(a,b,c,d,x,s,ac) \
  45.     do { \
  46.           a += H(b,c,d) + x + ac; \
  47.           a = ROTATE_LEFT(a,s); \
  48.           a += b; \
  49.     } while(0)

  50. #define II(a,b,c,d,x,s,ac) \
  51.     do { \
  52.           a += I(b,c,d) + x + ac; \
  53.           a = ROTATE_LEFT(a,s); \
  54.           a += b; \
  55.     } while(0)


  56. void MD5Init(MD5_CTX *context);
  57. void MD5Update(MD5_CTX *context,unsigned char *input,unsigned int inputlen);
  58. void MD5Final(MD5_CTX *context,unsigned char digest[16]);
  59. void MD5Transform(unsigned int state[4],unsigned char block[64]);
  60. void MD5Encode(unsigned char *output,unsigned int *input,unsigned int len);
  61. void MD5Decode(unsigned int *output,unsigned char *input,unsigned int len);
  62.  
  63. #endif

主要实现md5.c

点击(此处)折叠或打开

  1. #include <memory.h>
  2. #include "md5.h"
  3.  
  4. unsigned char PADDING[]={ // 16 Bety one line, 64 Bety in total
  5.     0x80,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0, //填充数据第一个bit为1,其余为0
  6.      0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
  7.        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
  8.        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0
  9. };
  10.                          
  11. void MD5Init(MD5_CTX *context)
  12. {
  13.      context->count[0] = 0;
  14.      context->count[1] = 0;
  15.      context->state[0] = 0x67452301;
  16.      context->state[1] = 0xEFCDAB89;
  17.      context->state[2] = 0x98BADCFE;
  18.      context->state[3] = 0x10325476;
  19. }

  20. /*
  21. * 处理输入数据(同一批数据处理,可以多次调用)
  22. *
  23. * 1. 按64字节一个分组,循环处理输入数据;
  24. * 2. 如果上次处理有剩余数据(不足一个分组的数据被保留),新输入数据拼接其后,组成一个新分组优先处理;
  25. * 3. 如果处理后有不足一个分组的数据剩余,那么把这部分数据保留到缓冲区中,待后续数据或最终PADDING处理。
  26. */
  27. void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputlen)
  28. {
  29.     unsigned int i = 0;
  30.     unsigned int index = 0;
  31.     unsigned int partlen = 0;


  32.     index = (context->count[0] >> 3) & 0x3F; // 转换为字节数并对64取模,等价于 (count[0] >> 3) % 64
  33.     partlen = 64 - index; //待补齐的字节数(上次处理不足一个分组的部分被保留未处理,本次先补齐一个组)

  34.     context->count[0] += inputlen << 3; //新输入bit数

  35.     if(context->count[0] < (inputlen << 3)) //count[0]溢出,记录到count[1]
  36.        context->count[1]++;

  37.     context->count[1] += inputlen >> 29; //新输入bit数溢出,记录到count[2]
  38.     
  39.     if(inputlen >= partlen) // 至少可以凑足一个分组
  40.     {
  41.         // 优先使用缓冲中的数据拼接一个分组,并处理该分组
  42.         memcpy(&context->buffer[index],input,partlen);
  43.         MD5Transform(context->state,context->buffer);

  44.         // 按64字节一个分组循环处理输入数据
  45.         for(i = partlen;i+64 <= inputlen;i+=64)
  46.             MD5Transform(context->state,&input[i]);

  47.         index = 0; //缓冲区偏移index置0(缓冲区已经被处理)
  48.     }
  49.     else
  50.     {
  51.         i = 0;
  52.     }

  53.     // 将不足一个分组的数据保存到缓冲区中,等待后续数据补齐或最终PADDING处理
  54.     memcpy(&context->buffer[index],&input[i],inputlen-i);
  55. }

  56. /*
  57. * 处理缓冲区中的剩余数据,输出最终的数据特征码到digest
  58. */
  59. void MD5Final(MD5_CTX *context, unsigned char digest[16])
  60. {
  61.     unsigned int index = 0;
  62.     unsigned int padlen = 0;
  63.     unsigned char bits[8];

  64.     index = (context->count[0] >> 3) & 0x3F;

  65.     /*
  66.     * 最后一个分组:(部分原数据)+ (填充数据)+ (长度信息[8字节]
  67.     * 所以剩余部分原始数据长度如果超过56字节,那么填充数据和长度信息在本分组中无法容纳
  68.     * 那么需要再额外填充一个分组。
  69.     */
  70.     padlen = (index < 56) ? (56-index) : (120-index);
  71.     MD5Encode(bits, context->count, 8);
  72.     MD5Update(context, PADDING, padlen);
  73.     MD5Update(context, bits, 8);
  74.     MD5Encode(digest,context->state,16);
  75. }

  76. /*
  77. * 把输入的整形数组转换为字符数组
  78. *
  79. * TODO:
  80. * 是否需要考虑大小端?
  81. */
  82. void MD5Encode(unsigned char *output,unsigned int *input,unsigned int len)
  83. {
  84.     unsigned int i = 0,j = 0;
  85.     while(j < len)
  86.     {
  87.          output[j] = input[i] & 0xFF;
  88.          output[j+1] = (input[i] >> 8) & 0xFF;
  89.          output[j+2] = (input[i] >> 16) & 0xFF;
  90.          output[j+3] = (input[i] >> 24) & 0xFF;
  91.          i++;
  92.          j+=4;
  93.     }
  94. }

  95. /*
  96. * 把输入的char类型的数据转换为int类型,要求len是4的倍数
  97. *
  98. * TODO:
  99. * 是否需要考虑大小端?
  100. */
  101. void MD5Decode(unsigned int *output,unsigned char *input,unsigned int len)
  102. {
  103.      unsigned int i = 0,j = 0;
  104.      while(j < len)
  105.      {
  106.            output[i] = (input[j]) |
  107.                        (input[j+1] << 8) |
  108.                        (input[j+2] << 16) |
  109.                        (input[j+3] << 24);
  110.            i++;
  111.            j+=4;
  112.      }
  113. }


  114. /*
  115. * 处理一个分组
  116. */
  117. void MD5Transform(unsigned int state[4],unsigned char block[64])
  118. {
  119.      unsigned int a = state[0];
  120.      unsigned int b = state[1];
  121.      unsigned int c = state[2];
  122.      unsigned int d = state[3];
  123.      unsigned int x[64];

  124.      MD5Decode(x,block,64);

  125.      /* Round 1*/
  126.      FF(a, b, c, d, x[ 0], 7,    0xd76aa478); /* 1 */
  127.      FF(d, a, b, c, x[ 1], 12,    0xe8c7b756); /* 2 */
  128.      FF(c, d, a, b, x[ 2], 17,    0x242070db); /* 3 */
  129.      FF(b, c, d, a, x[ 3], 22,    0xc1bdceee); /* 4 */
  130.      FF(a, b, c, d, x[ 4], 7,    0xf57c0faf); /* 5 */
  131.      FF(d, a, b, c, x[ 5], 12,    0x4787c62a); /* 6 */
  132.      FF(c, d, a, b, x[ 6], 17,    0xa8304613); /* 7 */
  133.      FF(b, c, d, a, x[ 7], 22,    0xfd469501); /* 8 */
  134.      FF(a, b, c, d, x[ 8], 7,    0x698098d8); /* 9 */
  135.      FF(d, a, b, c, x[ 9], 12,    0x8b44f7af); /* 10 */
  136.      FF(c, d, a, b, x[10], 17,    0xffff5bb1); /* 11 */
  137.      FF(b, c, d, a, x[11], 22,    0x895cd7be); /* 12 */
  138.      FF(a, b, c, d, x[12], 7,    0x6b901122); /* 13 */
  139.      FF(d, a, b, c, x[13], 12,    0xfd987193); /* 14 */
  140.      FF(c, d, a, b, x[14], 17,    0xa679438e); /* 15 */
  141.      FF(b, c, d, a, x[15], 22,    0x49b40821); /* 16 */
  142.  
  143.      /* Round 2 */
  144.      GG(a, b, c, d, x[ 1], 5,    0xf61e2562); /* 17 */
  145.      GG(d, a, b, c, x[ 6], 9,    0xc040b340); /* 18 */
  146.      GG(c, d, a, b, x[11], 14,    0x265e5a51); /* 19 */
  147.      GG(b, c, d, a, x[ 0], 20,    0xe9b6c7aa); /* 20 */
  148.      GG(a, b, c, d, x[ 5], 5,    0xd62f105d); /* 21 */
  149.      GG(d, a, b, c, x[10], 9,    0x2441453); /* 22 */
  150.      GG(c, d, a, b, x[15], 14,    0xd8a1e681); /* 23 */
  151.      GG(b, c, d, a, x[ 4], 20,    0xe7d3fbc8); /* 24 */
  152.      GG(a, b, c, d, x[ 9], 5,    0x21e1cde6); /* 25 */
  153.      GG(d, a, b, c, x[14], 9,    0xc33707d6); /* 26 */
  154.      GG(c, d, a, b, x[ 3], 14,    0xf4d50d87); /* 27 */
  155.      GG(b, c, d, a, x[ 8], 20,    0x455a14ed); /* 28 */
  156.      GG(a, b, c, d, x[13], 5,    0xa9e3e905); /* 29 */
  157.      GG(d, a, b, c, x[ 2], 9,    0xfcefa3f8); /* 30 */
  158.      GG(c, d, a, b, x[ 7], 14,    0x676f02d9); /* 31 */
  159.      GG(b, c, d, a, x[12], 20,    0x8d2a4c8a); /* 32 */
  160.  
  161.      /* Round 3 */
  162.      HH(a, b, c, d, x[ 5], 4,    0xfffa3942); /* 33 */
  163.      HH(d, a, b, c, x[ 8], 11,    0x8771f681); /* 34 */
  164.      HH(c, d, a, b, x[11], 16,    0x6d9d6122); /* 35 */
  165.      HH(b, c, d, a, x[14], 23,    0xfde5380c); /* 36 */
  166.      HH(a, b, c, d, x[ 1], 4,    0xa4beea44); /* 37 */
  167.      HH(d, a, b, c, x[ 4], 11,    0x4bdecfa9); /* 38 */
  168.      HH(c, d, a, b, x[ 7], 16,    0xf6bb4b60); /* 39 */
  169.      HH(b, c, d, a, x[10], 23,    0xbebfbc70); /* 40 */
  170.      HH(a, b, c, d, x[13], 4,    0x289b7ec6); /* 41 */
  171.      HH(d, a, b, c, x[ 0], 11,    0xeaa127fa); /* 42 */
  172.      HH(c, d, a, b, x[ 3], 16,    0xd4ef3085); /* 43 */
  173.      HH(b, c, d, a, x[ 6], 23,    0x4881d05); /* 44 */
  174.      HH(a, b, c, d, x[ 9], 4,    0xd9d4d039); /* 45 */
  175.      HH(d, a, b, c, x[12], 11,    0xe6db99e5); /* 46 */
  176.      HH(c, d, a, b, x[15], 16,    0x1fa27cf8); /* 47 */
  177.      HH(b, c, d, a, x[ 2], 23,    0xc4ac5665); /* 48 */
  178.  
  179.      /* Round 4 */
  180.      II(a, b, c, d, x[ 0], 6,    0xf4292244); /* 49 */
  181.      II(d, a, b, c, x[ 7], 10,    0x432aff97); /* 50 */
  182.      II(c, d, a, b, x[14], 15,    0xab9423a7); /* 51 */
  183.      II(b, c, d, a, x[ 5], 21,    0xfc93a039); /* 52 */
  184.      II(a, b, c, d, x[12], 6,    0x655b59c3); /* 53 */
  185.      II(d, a, b, c, x[ 3], 10,    0x8f0ccc92); /* 54 */
  186.      II(c, d, a, b, x[10], 15,    0xffeff47d); /* 55 */
  187.      II(b, c, d, a, x[ 1], 21,    0x85845dd1); /* 56 */
  188.      II(a, b, c, d, x[ 8], 6,    0x6fa87e4f); /* 57 */
  189.      II(d, a, b, c, x[15], 10,    0xfe2ce6e0); /* 58 */
  190.      II(c, d, a, b, x[ 6], 15,    0xa3014314); /* 59 */
  191.      II(b, c, d, a, x[13], 21,    0x4e0811a1); /* 60 */
  192.      II(a, b, c, d, x[ 4], 6,    0xf7537e82); /* 61 */
  193.      II(d, a, b, c, x[11], 10,    0xbd3af235); /* 62 */
  194.      II(c, d, a, b, x[ 2], 15,    0x2ad7d2bb); /* 63 */
  195.      II(b, c, d, a, x[ 9], 21,    0xeb86d391); /* 64 */

  196.      state[0] += a;
  197.      state[1] += b;
  198.      state[2] += c;
  199.      state[3] += d;
  200. }


下面是测试main函数,main.c

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "md5.h"

  4. /*
  5. MD5 test suite:
  6. MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
  7. MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
  8. MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
  9. MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
  10. MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
  11. MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f
  12. MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a
  13. */
  14. int main(int argc, char *argv[])
  15. {
  16.     int i;
  17.     unsigned char encrypt[] ="a";
  18.     unsigned char encrypt2[] ="bc";
  19.     //unsigned char encrypt[] ="admin";//21232f297a57a5a743894a0e4a801fc3
  20.     unsigned char decrypt[16];
  21.     MD5_CTX md5;

  22.     MD5Init(&md5);

  23.     MD5Update(&md5,encrypt,strlen((char *)encrypt));
  24.     MD5Update(&md5,encrypt2,strlen((char *)encrypt2));

  25.     MD5Final(&md5, decrypt);

  26.     printf("加密前:%s\n加密后:",encrypt);
  27.     for(i=0;i<16;i++)
  28.     {
  29.         printf("%02x",decrypt[i]);
  30.     }
  31.     
  32.     getchar();
  33.     
  34.     return 0;
  35. }

阅读(2140) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~