首页 > 编程语言 >MD5 哈希加密算法 - C++ 实现

MD5 哈希加密算法 - C++ 实现

时间:2022-10-23 14:24:14浏览次数:90  
标签:函数 16 Buffer 32 C++ 哈希 bit 加密算法 MD5

MD5 加密算法 - C++ 实现

写在前头: 还在学习中! 整个文档写的很匆忙, 肯定还有很多不周到的地方. 欢迎在评论中提出你的宝贵意见!!

算法背景 Background

MD5消息摘要算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16个字符(BYTES))的散列值(hash value),用于确保信息传输完整一致。MD5由美国密码学家罗纳德·李维斯特(Ronald Linn Rivest)设计,于1992年公开,用以取代MD4算法。这套算法的程序在 RFC 1321 中被加以规范。

将数据(如一段文字)运算变为另一固定长度值,是散列算法的基础原理。

1996年后被证实存在弱点,可以被加以破解,对于需要高度安全性的资料,专家一般建议改用其他算法,如SHA-2。2004年,证实MD5算法无法防止碰撞攻击,因此不适用于安全性认证,如SSL公开密钥认证或是数字签名等用途。

--- 摘自 维基百科 MD5 - 维基百科,自由的百科全书 (wikipedia.org)

说明 在 MD5 算法中, 数据的存储均使用 小端序. 即低位存放在内存地址小的位置. (英:little-endian)

Little-Endian.svg

基本结构 Structure

image-20221023133131767

主要有一下几个构件组成.

MD5 算法

输入: 任意长度的明文

输出: 128-bit 的摘要 (digest)

\(H_{MD5}\) (有点像DES)

输入: 512-bit 的明文分组, CV 链接向量(类似Key)

输出: 128-bit 结果

\(Logic\_Function_i()\) 逻辑函数

输入: 三个 32-bit 字

输出: 一个 32-bit 字

以 类似CBC 的模式链接 (即每一组的加密会受到前一组的影响),

算法流程 Process

MD5 算法可以大致分为三个步骤: 消息预处理, 初始化缓冲区, 循环哈希.

  1. 消息预处理

    该步骤可以分为两个小点: ① 填充消息; ② 附加信息.

    • 填充消息

      填充输入的原消息, 使消息的长度 $Length(M') \equiv 448 \pmod{512} $

      必须对输入消息进行填充, 即使消息原本就已经满足如上要求, 也要进行填充. 这是为了第二步操作预留 64-bit 空间.

      填充内容: 第一位为1, 其余位为零.

    • 附加信息

      在第一步预留出的空间里附加上明文消息的长度.

      原因: 增加攻击者伪造明文的难度. 伪造信息的长度必需要与原文长度相等(其实是同余)

      将消息长度 \(Length(M) \pmod{2^{64}}\) 以小端序的形式附加到第一步预留的 64-bit 空间中.

    按以上步骤处理完消息之后, 每一组消息可以按 32-bit 一组, 被分为 16组字(Word) (512 = 32 * 16)

    在本文中被记作 \(M_i[j]\) j表示字的组数.

  2. 初始化缓冲区

    算法使用 128-bit 的缓冲区存放中间结果和最终哈希值, 128-bit 可以看做 4 组 32-bit 字所占的比特位(128 = 4 * 32)

    被记作 \(Buffer_A, Buffer_B,Buffer_C, Buffer_D\). 每个缓冲区都以小端的方式存储数据. 将 4 块 Buffer 组合起来记为链接向量 \(CV_i\)

    \(CV_i = CV_{i - 1}\)

    \(CV_0\) 被规定为常量, 如下表格所示.

    字节序 存储内容
    小端序 Buffer[4] = {0x01234567, 0x89ABCDEF, 0xFEDCBA98, 0x76543210};
    大端序 Buffer[4] = {0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476};
  3. 循环哈希

    调用 \(H_{MD5}(M_i, CV_i)\) 函数对每组消息分组进行哈希计算.

    image-20221023133359530

    每一次 \(H_{MD5}()\) 中有 4 轮结构相同的逻辑函数, 不同轮次间的唯一区别是参与计算的逻辑函数不同, 分别表示为 FGHI.

    此外, \(H_{MD5}()\) 还有一个常数表 T, 常数表 T 为定义为 \(T[i] = 2^{32} \times \abs{\sin{i}}\) (也就是 \(\abs{\sin i}\) 的前 32-bit 小数.) (i 是弧度)

    在本文中把 \(H_{MD5}\) 的轮函数记为 \(R(M_i, Buffer, T[], function_i())\). 其中, 轮函数每次调用是都会读取缓存区中的数据. 而且不同轮次之间所调用的逻辑函数也是不一样的. 此外, 每一次调用轮函数会用到不同 16 组 T 元素(对应轮函数内部的中 16 次迭代).

    \(H_{MD5}()\) 完成第四轮轮函数处理之后, 将得到的结果和输入的 $CV_i $按字(每 32-bit) 分组按位加. 得到最终输出结果 \(CV_{i+1}\).

函数定义 Function define

轮函数(压缩函数)的具体实现

轮函数每次调用内部有 16 次迭代计算, 将轮函数当前迭代的次数记作 i

image-20221023133505106

读取缓冲区中的数据, 将缓冲区按字 32-bit 分为 4 组, 记作 ABCD

  • 第一步

    BCD 暂时不动, A 有以下 x 层计算:

    • \(A + Logic\_Function_{轮数}(B, C, D)\)

      \(\begin{array}{l} F(b, c, d) &=& (b \wedge c) \vee(\bar{b} \wedge d) \\ G(b, c, d) &=& (b \wedge d) \vee(c \wedge \bar{d}) \\ H(b, c, d) &=& b \oplus c \oplus d \\ I(b, c, d) &=& c \oplus(b \vee \bar{d}) \end{array}\)

    • \(A + M_i[k]\) (k 受到当前轮数以及迭代次数 i 的影响)

    • \(A + T[i]\) (受到输入影响, 与当前轮数有关)

    • A 循环左移 s 位 (s 由一个常量表给出)

      \(\begin{array}{l} \rho_{1}(i) = i\\ \rho_{2}(i)=(1+5 i) \bmod 16 \\ \rho_{3}(i)=(5+3 i) \bmod 16 \\ \rho_{4}(i)=7 i \bmod 16 \\ \end{array}\)

    • A + B

  • 第二步

    对缓冲区中的四个字按字右循环位移 1 个字 即新的缓冲区 \(Buffer' = D' || A' || B' || C'\)

也就是说, 一组消息的压缩要经过这样的过程:

轮次 1

/* [abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  0 7  1][DABC  1 12  2][CDAB  2 17  3][BCDA  3 22  4]
[ABCD  4 7  5][DABC  5 12  6][CDAB  6 17  7][BCDA  7 22  8]
[ABCD  8 7  9][DABC  9 12 10][CDAB 10 17 11][BCDA 11 22 12]
[ABCD 12 7 13][DABC 13 12 14][CDAB 14 17 15][BCDA 15 22 16]

轮次 2

/* [abcd k s i] a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  1 5 17][DABC  6 9 18][CDAB 11 14 19][BCDA  0 20 20]
[ABCD  5 5 21][DABC 10 9 22][CDAB 15 14 23][BCDA  4 20 24]
[ABCD  9 5 25][DABC 14 9 26][CDAB  3 14 27][BCDA  8 20 28]
[ABCD 13 5 29][DABC  2 9 30][CDAB  7 14 31][BCDA 12 20 32]

轮次 3

/* [abcd k s i] a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  5 4 33][DABC  8 11 34][CDAB 11 16 35][BCDA 14 23 36]
[ABCD  1 4 37][DABC  4 11 38][CDAB  7 16 39][BCDA 10 23 40]
[ABCD 13 4 41][DABC  0 11 42][CDAB  3 16 43][BCDA  6 23 44]
[ABCD  9 4 45][DABC 12 11 46][CDAB 15 16 47][BCDA  2 23 48]

轮次 4

/* [abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  0 6 49][DABC  7 10 50][CDAB 14 15 51][BCDA  5 21 52]
[ABCD 12 6 53][DABC  3 10 54][CDAB 10 15 55][BCDA  1 21 56]
[ABCD  8 6 57][DABC 15 10 58][CDAB  6 15 59][BCDA 13 21 60]
[ABCD  4 6 61][DABC 11 10 62][CDAB  2 15 63][BCDA  9 21 64]

代码实现 Implement

代码测试 Test

参考 Rivest 在 RFC 1321 规范中给出的结果, 对上述代码进行测试.

----------------- MD5 -----------------
INFO: Input a line of text, ended with an enter. (to end program input CTRL + C)
-----------------------
text:
result: d41d8cd98f00b204e9800998ecf8427e
-----------------------
text: a
result: 0cc175b9c0f1b6a831c399e269772661
-----------------------
text: abc
result: 900150983cd24fb0d6963f7d28e17f72
-----------------------
text: message digest
result: f96b697d7cb7938d525a2f31aaf161d0
-----------------------
text: abcdefghijklmnopqrstuvwxyz
result: c3fcd3d76192e4007dfb496cca67e13b
-----------------------
text: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
result: d174ab98d277d9f5a5611c2c9f419d9f
-----------------------
text: 12345678901234567890123456789012345678901234567890123456789012345678901234567890
result: 57edf4a22be3c955ac49da2e2107b67a
-----------------------

与规范中给出的结果一致, 测试通过!

MD5 test suite:
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("123456789012345678901234567890123456789012345678901234567890123456
78901234567890") = 57edf4a22be3c955ac49da2e2107b67a

参考资料 Reference

字节顺序 - 维基百科,自由的百科全书 (wikipedia.org)

MD5 - 维基百科,自由的百科全书 (wikipedia.org)

RFC 1321: The MD5 Message-Digest Algorithm (rfc-editor.org)

杨波. 现代密码学(第四版). 清华大学出版社, 2003.

标签:函数,16,Buffer,32,C++,哈希,bit,加密算法,MD5
From: https://www.cnblogs.com/zenor0/p/16818483.html

相关文章

  • c++对象的拷贝、构造、虚构
    抽象基类​ 现有如下代码:classAbstract_base{public:virtual~Abstract_base()=0;virtualvoidinterface()const=0;virtualconstchar*mumble......
  • 大规模C++软件开发 卷1 过程与架构 电子书 pdf
    链接:大规模C++软件开发卷1过程与架构  本书通过具体示例演示了基本的设计概念,为各种规模的项目奠定了基础,并演示了成功进行大规模实际开发所需的过程、方法、技......
  • 实验3 数组、指针与现代C++标准库
    5.实验任务5info.hpp#pragmaonce#include<iostream>#include<string>#include<iomanip>usingstd::string;usingstd::cout;usingstd::endl;classinfo{......
  • C++基础
    C++基础VS快捷键Ctrl+或-跳转到上次鼠标焦点位置CtrlKF按住Ctrl然后按K然后按FCtrlJ代码提示变量声明方式:数据类型变量名=变量初始值#include<iostre......
  • C/C++ 中的几种调试技巧(待续)
    1、利用#define宏定义作为调试开关include<stdio.h>defineDEBUG//可以注释或打开输出intmain(void){inti,sum;for(i=1,sum=0;i<=5;i++){......
  • C++ 函数返回指针
    C++中返回值为指针或者引用的时候,不可以返回局部变量的指针或者引用,因为当此段代码块执行完之后,相应的局部变量,就会被系统释放,指针所指向的那块内存会被操作系统用来做其......
  • 实验三 数组、指针与现代c++标准库
    task5#pragmaonce#include<iostream>#include<string>#include<vector>#include<iomanip>usingnamespacestd;classInfo{public:Info(string......
  • 数组,指针与现代c++标准
    #include<iostream>#include<algorithm>#include<math.h>#include<string>usingnamespacestd;classInfo{public:Info(stringnickname,stringcon......
  • 【leetcode_C++_哈希表_day5】242. 有效的字母异位词&&349. 两个数组的交集&&202.快乐
    C++知识补充:(不完全,仅针对本题用的知识点)1.C++类&对象关键字public确定了类成员的访问属性。在类对象作用域内,公共成员在类的外部是可访问的。您也可以指定类的成......
  • C++模板编程学习-using-declaration中的依赖型名称
    《C++Templates》9.3.4using-declaration中的依赖型名称学无止境,看到C++模板的第九章中的使用声明从两个位置(类和名字空间)引入名称,当引入名字空间不会涉及上下文问题......