欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

MD5算法的程序设计和实现

程序员文章站 2024-03-19 09:47:16
...

MD5算法的程序设计和实现

算法原理概述

  • MD5 即 Message-Digest Algorithm 5 (信息-摘要算法 5)
    • MD4 (1990)、MD5(1992, RFC 1321) 由 Ron Rivest 发明,是广泛 使用的 Hash 算法,用于确保信息传输的完整性和一致性。
    • MD5 使用 little-endian (小端模式),输入任意不定长度信息,以 512-bit 进行分组,生成四个32-bit 数据,最后联合输出固定 128-bit 的信息摘要。
    • MD5 算法的基本过程为:填充、分块、缓冲区初始化、循环压缩、得出结果。
    • MD5 不是足够安全的。
      • HansDobbertin在1996年找到了两个不同的512-bit块,它们在 MD5 计算下产生相同的 hash 值。
      • 至今还没有真正找到两个不同的消息,它们的MD5的hash值相等。

算法逻辑

  • 填充padding

    • 在长度为 K bits 的原始消息数据尾部填充长度为 P bits 的标识 100…0,1<=P<=512 (即至少要填充1个bit),使得填充后的消息位 数为:K + P = 448 (mod 512).
      • 注意到当 K = 448 (mod 512) 时,需要 P= 512.
    • 再向上述填充好的消息尾部附加 K 值的低64位 (即 K mod 264),最后得到一个长度位数为K+P+64=0(mod512)的消息。
  • 分块

    • 把填充后的消息结果分割为 L 个 512-bit 分组: Y0,Y1,...,YL1Y_0,Y_1,...,Y_{L-1}
    • 分组结果也可表示成 N 个32-bit 字 M0,M1,..,MN1M_0,M_1,..,M_{N-1},N = L*16。
  • 初始化

    • 初始化一个128-bit 的 MD 缓冲区,记为 CVqCV_q,表示成4个32-bit寄存器 (A, B, C, D);CV0=IVCV_0 = IV。迭代在 MD 缓冲区进行,最后一步的128-bit 输出即为算法结果。
    • 寄存器 (A, B, C, D) 置16进制初值作为初始向量 IV,并采用小端 存储 (little-endian) 的存储结构:
      • A = 0x67452301
      • B = 0xEFCDAB89
      • C = 0x98BADCFE
      • D = 0x10325476
  • 总控流程

    • 以512-bit 消息分组为单位,每一分组 YqY_q (q = 0, 1, …, L-1) 经过4 个循环的压缩算法,表示为:
      • CV0=IVCV_0 = IV
      • CVi=HMD5(CVi1,Yi)CV_i = H_{MD5}(CV_{i-1} , Y_i)
    • 输出结果: MD=CVLMD = CV_L .
  • MD5压缩函数HMD5H_{MD5}

    • HMD5H_{MD5}从CV输入128位,从消息分组输入512位,完成 4轮循环后,输出128位, 用于下一轮输入的 CV 值。
    • 每轮循环分别固定不同的生成函数 F, G, H, I,结合指定的 T 表元素 T[] 和消息分组的不同部分 X[] 做16次迭代运算,生成下一轮循环的输入。
    • 4轮循环总共有64次迭代运算。
    • 4轮循环中使用的生成函数(轮函数) g 是一个32位非线性逻辑函数,在相应各轮的定义如下:
      #define F(b,c,d) ((b & c) | (~b & d))
      #define G(b,c,d) ((b & d) | (c & ~d))
      #define H(b,c,d) (b^c^d)
      #define I(b,c,d) (c ^ (b | ~d))
      
    • 每轮循环中的一次迭代运算逻辑
      1. 对A迭代:a=b+((a+g(b,c,d)+X[k]+T[i])&lt;&lt;&lt;s)a = b + ((a + g(b, c, d) + X[k] + T[i]) &lt;&lt;&lt;s)
      2. 缓冲区 (A, B, C, D) 作循环轮换:
        (B,C,D,A)=(A,B,C,D)(B, C, D, A) = (A, B, C, D)
    • 各轮循环中第 i 次迭代 (i = 1…16) 使用的 X[k] 的确定:
      long X[4][16]=
          {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15},
          {1, 6,11, 0, 5,10,15, 4, 9,14, 3, 8,13, 2, 7,12},
          {5, 8,11,14, 1, 4, 7,10,13, 0, 3, 6, 9,12,15, 2},
          {0, 7,14, 5,12, 3,10, 1, 8,15, 6,13, 4,11, 2, 9}};
      
    • T表的生成
      long T[64]=
          {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};
      
    • 各次迭代运算采用的左循环移位的 s 值:
      long s[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++程序共包含4个文件:

文件 功能
main.cpp 主函数
MD5.hpp 构造了MD5类,及算法函数的声明
MD5.cpp 类中各函数的实现
MD5Data.h 算法所需数组的存储

MD5类:2个public函数供主函数调用,其他函数和变量全声明为private。

class MD5 {
private:
    unsigned long A,B,C,D;
    unsigned long result[4];    //记录ABCD

    //迭代运算
    long FF(long a, long b, long c, long d, long x, long s,long t);
    long GG(long a, long b, long c, long d, long x, long s,long t);
    long HH(long a, long b, long c, long d, long x, long s,long t);
    long II(long a, long b, long c, long d, long x, long s,long t);

    //ABCD给result赋值
    void mergeResult(int a,int b,long c,long d);
    //result更新ABCD
    void splitResult(int a,int b,long c,long d);

    //缓冲区 (A, B, C, D) 作循环轮换:
    void resultLeftShift();
    //result每一位分别增加a,b,c,d
    void addResult(long a,long b,long c,long d);

    //输入字符串的填充
    void Padding(unsigned char *input,unsigned char pad[]);
    //分块,合成32位字(4字节)
    void splitBlock(unsigned char *input,int index,long groups[]);
    //四轮循环
    void FourLoop(long groups[]);
    //二进制转无符号类型
    long bin2unsigned(char ch);

public:
    //初始化ABCD
    MD5();
    //加密实现
    string MD5Algorithm(unsigned char *input);

};

模块分解

  • 主函数:输入待处理字符串,MD5加密,输出result(32位16进制)
int main(int argc, const char * argv[]) {

    unsigned char source[2000];
    cout<<"Input string to be encrypted:\n";
    cin>>source;

    MD5 md5;
    string out=md5.MD5Algorithm(source);
    cout<<"MD5 After:"<<out<<endl;
    return 0;
}

  • 加密实现函数:
string MD5::MD5Algorithm(unsigned char *input){
    int byteLen=(int)strlen((char *)input);
    int YCount=(byteLen%64>=56-1)?byteLen/64+1:byteLen/64+2;  //分组个数,64字节(512位)一组

    unsigned char paddingInput[YCount*64];
    Padding(input,paddingInput);

    for(int i=0;i<YCount;i++){
        long groups[16];
        splitBlock(paddingInput,i*64,groups);
        FourLoop(groups);
    }
    string outStr="";
    long templ=0,tempb=0;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            templ=result[i]&0x0F;
            tempb=(result[i]>>4)&0x0F;
            string sl=hexs[(int)templ];
            string sb=hexs[(int)tempb];
            outStr+=sb+sl;
            result[i]=result[i]>>8;
        }
    }
    return outStr;
}

输入:待加密字符串
输出:加密后32位16进制串
YCount表示分组个数。当输入串长度mod 64为55时,padding需要填充512/8=64byte,所以组数得加2,一般情况下加一。
先后调用了:

  1. Padding(input,paddingInput):填充函数,得到长度为64字节倍数的填充后字符串。
void Padding(unsigned char *input,unsigned char pad[]){
    string str=(char*)input;

    int len=(int)str.size();
    //padding第一步
    str+=(char)0x80;

    while (str.size()%64!=56) {
        str+=(char)0;
    }
    //padding第二步
    string ss="";
    len=len<<3;
    for(int i=0;i<8;i++){
        ss+=(char)(len&0xFF);
        len=len>>8;
    }
    str+=ss;

    memcpy(pad, str.c_str(), str.size());
}

padding第一步:填充0x80,0,…,0直到size%64=56(56字节448bit);
padding第二步:填充长度K值后64位。
memcpy函数调用将str赋值给pad。

  1. splitBlock(paddingInput,i*64,groups):分块函数
void splitBlock(unsigned char *input,int index,long groups[]){
    for(int i=0;i<16;i++){
        groups[i]=bin2unsigned(input[index+4*i]);
        groups[i]|=bin2unsigned(input[index+4*i+1])<<8;
        groups[i]|=bin2unsigned(input[index+4*i+2])<<16;
        groups[i]|=bin2unsigned(input[index+4*i+3])<<24;
    }
}

分块函数将从index开始合成16个32位字,共512bits.
3. FourLoop(groups):四轮循环函数

void FourLoop(long groups[]){
    splitResult(0,1,2,3);

    for(int i=0;i<16;i++){
        A=FF(A,B,C,D,groups[X[0][i]],s[0][i],T[i]);
        resultLeftShift();
    }
    for(int i=0;i<16;i++){
        A=GG(A,B,C,D,groups[X[1][i]],s[1][i],T[16+i]);
        resultLeftShift();
    }
    for(int i=0;i<16;i++){
        A=HH(A,B,C,D,groups[X[2][i]],s[2][i],T[32+i]);
        resultLeftShift();
    }
    for(int i=0;i<16;i++){
        A=II(A,B,C,D,groups[X[3][i]],s[3][i],T[48+i]);
        resultLeftShift();
    }
    addResult(A, B, C, D);
}

splitResult:此时的result数组更新ABCD值。

四次循环分别调用FF,GG,HH,II函数:

#define ROTATE_LEFT(x,n) (((x&0xFFFFFFFF) << n) | ((x&0xFFFFFFFF) >> (32-n)))

long MD5::FF(long a, long b, long c, long d, long x, long s,long t){
    a += (F(b, c, d) & 0xFFFFFFFF) + x + t;
    a = ROTATE_LEFT(a, s);
    a += b;
    return a & 0xFFFFFFFF;
}
long MD5::GG(long a, long b, long c, long d, long x, long s,long t){
    a += (G(b, c, d) & 0xFFFFFFFF) + x + t;
    a = ROTATE_LEFT(a, s);
    a += b;
    return a & 0xFFFFFFFF;
}
long MD5::HH(long a, long b, long c, long d, long x, long s,long t){
    a += (H(b, c, d) & 0xFFFFFFFF) + x + t;
    a = ROTATE_LEFT(a, s);
    a += b;
    return a & 0xFFFFFFFF;
}
long MD5::II(long a, long b, long c, long d, long x, long s,long t){
    a += (I(b, c, d) & 0xFFFFFFFF) + x + t;
    a = ROTATE_LEFT(a, s);
    a += b;
    return a & 0xFFFFFFFF;
}

ROTATE_LEFT(x,n)宏定义:x循环左移n位。
4轮循环,共64轮迭代,每轮迭代之后(A, B, C, D) 作循环轮换:(B,C,D,A)=(A,B,C,D)(B, C, D, A) = (A, B, C, D),可调用 resultLeftShift()函数。

编译运行结果

可与MD5在线加密对比,证明算法的正确性。

相关标签: MD5算法