没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
!
1!
第五章 基于
MD5
算法的文件完整性校验程序
5.1
本章训练目的与要求
MD5 算法是目前最流行的一种信息摘要算法,在数字签名,加密与解密技术,以及文
件完整性检测等领域中发挥着巨大的作用。熟悉 MD5 算法对开发网络应用程序,理解网络
安全的概念具有十分重要的意义。
本章编程训练的目的如下:
① 深入理解 MD5 算法的基本原理。
② 掌握利用 MD5 算法生成数据摘要的所有计算过程。
③ 掌握 Linux 系统中检测文件完整性的基本方法。
④ 熟悉 Linux 系统中文件的基本操作方法。
本章编程训练的要求如下:
① 准确地实现 MD5 算法的完整计算过程。
② 对于任意长度的字符串能够生成 128 位 MD5 摘要。
③ 对于任意大小的文件能够生成 128 位 MD5 摘要。
④ 通过检查 MD5 摘要的正确性来检验原文件的完整性。
5.2
相关背景知识
5.2.1 MD5
简介
MD5(message-digest algorithm 5 的缩写)是一种信息摘要算法。信息摘要算法的研究
由来已久,早在 1990 年 Ronald L. Rivest 就提出了与 MD5 属于同一系列的散列函数 MD4。
经过大量的密码学分析与不断的攻击检测,Rivest 于 1991 年提出了它的改进算法 MD5。目
前 MD5 已经得到了广泛的应用,成为许多机构和组织的散列函数标准。
作为散列函数,MD5 有两个重要的特性:第一、任意两组数据经过 MD5 运算后,生成
相同摘要的概率微乎其微;第二、即便在算法与程序已知的情况下,也不能够从 MD5 摘要
中获得原始的数据。
MD5 的典型应用就是为一段信息(message)生成信息摘要(message-digest), 以 防 止
被篡改。Linux 系统自带了计算和校验 MD5 摘要的工具程序—md5sum。用户可以在命令行
终端直接运行该程序。md5sum 程序可以创建一个与原始文件名称相同,后缀为.md5 的文件,
并将原始文件的 MD5 摘要保存在该文件中。如下所示,对于文件 nankai.txt,利用 md5sum
!
2!
程序计算出它的摘要(3c771aea5b7e191408ab6b0372ecbf0c)并保存在文件 nankai.md5 中。
[root@localhost MD5]# cd md5sum/
[root@localhost md5sum]# ls
nankai.txt
[root@localhost md5sum]# md5sum nankai.txt > nankai.md5
[root@localhost md5sum]# ls
nankai.md5 nankai.txt
[root@localhost md5sum]# vim nankai.md5
1 3c771aea5b7e191408ab6b0372ecbf0c nankai.txt
…
另外,md5sum 程序可以对文件的完整性进行检测。它通过重新计算原始文件的 MD5
摘要,将计算结果与同名的.md5 文件中的摘要进行对比,若相同,则文件完整;否则,原
文件受到了破坏。如下所示,共包含了 2 次检验。第一次通过比较 nankai.md5 中的摘要验
证文件 nankai.txt 是完整的。第二次修改了 nankai.txt 文件的内容(在标题后面增加了 written
by sky), 导 致 校 验 失 败 。
[root@localhost md5sum]# md5sum -c nankai.md5
nankai.txt: OK
[root@localhost md5sum]# vim nankai.txt
1 About Nankai University (written by sky)
2
3 A key multidisciplinary and research-oriented university directly under the jurisdiction of
the Ministry of Education, Nankai University, located in Tianjin on the border of the sea of
Bohai, is also the alma mater of our beloved late Premier Zhou Enlai.
…
[root@localhost md5sum]# md5sum -c nankai.md5
nankai.txt: FAILED
md5sum: WARNING: 1 of 1 computed checksum did NOT match
5.2.2 MD5
算法分析
MD5 算法分为 3 个部分:消息的填充与分割、消息块的循环运算、摘要的生成。
1.
消息的填充与分割
MD5 算法以 512 比特为单位对输入消息进行分组。每个分组是一个 512 比特的数据块。
同时每个数据块又由 16 个 32 比特的子分组构成。摘 要 的 计 算 过 程 就 是 以 512 比特数据块为
单位进行的。
在 MD5 算法中,首先需要对输入消息进行填充,使其比特长度对 512 求余的结果等于
448。也就是说,消息的比特长度将被扩展至 N×512+448,即 N×64+56 个字节,其中 N 为
正整数。
!
3!
具体的填充方法如下:在消息的最后填充一位 1 和若干位 0,直到满足上面 的条 件时才
停止用 0 对信息进行填充。然后在这个结果后面加上一个以 64 位二进制表示的填充前的消
息长度。经过这两步的处理,现在消息比特长度=N×512+448+64=(N+1) ×512。因为长度恰
好是 512 的整数倍,所以在下一步中可以方便地对消息进行分组运算。
2.
消息块的循环运算
MD5 算法包含 4 个初始向量,5 种基本运算,以及 4 个基本函数。
(1) 初始向量
MD5 算法中有四个 32 比特的初始向量。它们分别是:A=0x01234567,B=0x89abcdef,
C=0xfedcba98,D=0x76543210。
(2) 基本运算
5 种基本运算是指:
a.
X
:X 的逐比特逻辑“非”运算;
b.
XY∧
:X,Y 的逐比特逻辑“与”运算;
c.
XY∨
:X,Y 的逐比特逻辑“或”运算;
d.
XY⊕
:X,Y 的逐比特逻辑“异或”运算;
e.
Xs<<<
:X 循环左移 s 位。
(3) 基本函数
MD5 算法中 4 个非线性基本函数分别用于 4 轮计算。它们分别是:
a.
(, ,) ( ) ( )Fxyz x y x z=∧∨∧
b.
(, ,) ( ) ( )Gxyz x z y z=∧∨∧
c.
(, ,)Hxyz x y z=⊕⊕
d.
(, ,) ( )Ixyz y x z=⊕ ∨
在设置好 4 个初始向量以后,就进入了 MD5 的循环过程。循环过程就是对每一个消息
分组的计算过程。每一次循环都会对一个 512 比特消息块进行计算,因此循环的次数就是消
息中 512 比特分组的数目,即上面的(N+1)。
如下式所示,在一次循环开始时,首先要将初始向量 A、B、C、D 中的值保存到向量
A
0
、B
0
、C
0
、D
0
中,然后再继续后面的操作。
0
AA=
0
BB=
0
CC=
0
DD=
!
4!
MD5 循环体中包含了 4 轮计算(MD4 只有 3 轮),每一轮计算进行 16 次操作。每一次
操作可概括如下:
a. 将向量 A、B、C、D 中的其中三个作一次非线性函数运算。
b. 将所得结果与剩下的第四个变量、一个 32 比特子分组 X[k]和一个常数 T[i]相加。
c. 将所得结果循环左移 s 位,并加上向量 A、B、C、D 其中之一;最后用该结果取
代 A、B、C、D 其中之一的值。
在第一轮计算中,如果用表达式 FF[abcd, k, s, i]表示如下的计算过程,那么第一轮的 16
次操作可以表示为:
( )
( )
(,, ) [] []ab aIbcd Xk Ti s=+ + + + <<<
FF[ABCD, 0, 7, 1]
FF [DABC, 1, 12, 2]
FF [CDAB, 2, 17, 3]
FF [BCDA, 3, 22, 4]
FF [ABCD, 4, 7, 5]
FF [DABC, 5, 12, 6]
FF [CDAB, 6, 17, 7]
FF [BCDA, 7, 22, 8]
FF [ABCD, 8, 7, 9]
FF [DABC, 9, 12, 10]
FF [CDAB, 10, 17, 11]
FF [BCDA, 11, 22, 12]
FF [ABCD, 12, 7, 13]
FF [DABC, 13, 12, 14]
FF [CDAB, 14, 17, 15]
FF [BCDA, 15, 22, 16]
在第二轮计算中,如果用表达式 GG[abcd, k, s, i]表示如下的计算过程,那么第二轮的
16 次操作可以表示为:
( )
( )
(,, ) [] []ab aGbcd Xk Ti s=+ + + + <<<
GG [ABCD, 1, 5, 17]
GG [DABC, 6, 9, 18]
GG [CDAB, 11, 14, 19]
GG [BCDA, 0, 20, 20]
GG [ABCD, 5, 5, 21]
GG [DABC, 10, 9, 22]
GG [CDAB, 15, 14, 23]
GG [BCDA, 4, 20, 24]
GG [ABCD, 9, 5, 25]
GG [DABC, 14, 9, 26]
GG [CDAB, 3, 14, 27]
GG [BCDA, 8, 20, 28]
GG [ABCD, 13, 5, 29]
GG [DABC, 2, 9, 30]
GG [CDAB, 7, 14, 31]
GG [BCDA, 12, 20, 32]
在第三轮计算中,如果用表达式 HH[abcd, k, s, i]表示如下的计算过程,那么第三轮的
16 次操作可以表示为:
( )
( )
(,, ) [] []ab aHbcd Xk Ti s=+ + + + <<<
HH [ABCD, 5, 4, 33]
HH [DABC, 8, 11, 34]
HH [CDAB, 11, 16, 35]
HH [BCDA, 14, 23, 36]
HH [ABCD, 1, 4, 37]
HH [DABC, 4, 11, 38]
HH [CDAB, 7, 16, 39]
HH [BCDA, 10, 23, 40]
HH [ABCD, 13, 4, 41]
HH [DABC, 0, 11, 42]
HH [CDAB, 3, 16, 43]
HH [BCDA, 6, 23, 44]
HH [ABCD, 9, 4, 45]
HH [DABC, 12, 11, 46]
HH [CDAB, 15, 16, 47]
HH [BCDA, 2, 23, 48]
在第四轮计算中,如果用表达式 II[abcd, k, s, i]表示如下的计算过程,那么第四轮的 16
次操作可以表示为:
( )
( )
(,, ) [] []ab aIbcd Xk Ti s=+ + + + <<<
II [ABCD, 0, 6, 49]
II [DABC, 7, 10, 50]
II [CDAB, 14, 15, 51]
II [BCDA, 5, 21, 52]
II [ABCD, 12, 6, 53]
II [DABC, 3, 10, 54]
II [CDAB, 10, 15, 55]
II [BCDA, 1, 21, 56]
剩余18页未读,继续阅读
ai
- 粉丝: 62
- 资源: 315
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0