数字加密技术毕业论文.doc

学院理学学士学位论文学院理学学士学位论文 RSA 加密算法和信息摘要加密算法和信息摘要 杨丽彬 二零零五年六月九日 分类号 学校代码 UDC 密级 学 号 2001162135 学院学院 信息工程学院毕业论文信息工程学院毕业论文 RSA 加密算法和信息摘要加密算法和信息摘要 杨丽彬杨丽彬 指导教师 填写名字 职务或职称 校外指导教师的单位名称 申请学位级别 专业名称 论文提交日期 论文答辩日期 学位授予单位和日期 答辩委员会主席 论文评阅人 20年 月 学院理学学士学位论 摘要 I 摘要摘要 在这个信息爆炸的时代 随著电脑通信与网络的日渐普及 数据传输的安全性愈 发受到重视 密码学已成为一个相当重要的课题 在密码系统中 主要可分成私有密 钥系统与公开密钥系统 在公开密钥系统中 RSA 密码系统是最有名也是最普及的密 码系统 基本上 RSA 密码系统是由高位元数的模乘法运算以及模指数运算所组成 由于其运算复杂度相当高 想要破解公开密钥以便得到私密密钥是相当困难的事 随著通信传播上的蓬勃发展 使得互联网越来越受到欢迎 以致于 对于类似电 子商务的服务 网络上安全的问题成为主要考虑的课题 而其基本上的安全需求 包 含有隐密性 可认证性 数据的完整性和不可否认性 为了提供上述的安全服务 大 多的网络系统使用公开密钥密码系统 而 RSA 密码系统和 MD5 信息摘要算法结合可 以确保数据的完整性 关键词 公开密钥系统 公钥 私钥 RSA 密码系统 MD5 信息摘要 学院理学学士学位论文 Abstract II Abstract With the increasing popularity of electronic communications data security is becoming a more and more important issue There are two main types of cryptosystems One is private key cryptosystem and the other is public key cryptosystem The most famous and popular public key cryptosystem is RSA scheme RSA scheme is composed of large bit length modular multiplication and modular exponentiation in principle Because of the high complexity of modular exponentiation it is very difficult to factor it and obtain the private key from the public key As the telecommunication network has grown explosively and the Internet has become increasingly popular security over the network is the main concern for further services like electronic commerce The fundamental security requirements include confidentiality authentication data integrity and nonrepudiation To provide such security services most systems use public key cryptography Use RSA scheme and The MD5 message digest algorithm together it makes sure data integrity in the tekecommunication network Key Word Public Key cryptography Public Key Private Key RSA MD5 message digest 学院理学学士学位论文 目录 III 目录目录 摘要摘要 I I ABSTRACTABSTRACT IIII 目录目录 IIIIII 第一章第一章 RSARSA 公钥密码简介公钥密码简介 1 1 1 1 公开密钥密码系统 1 1 2 RSA 加密算法 2 1 3 RSA 公钥密码的安全 5 第二章第二章 RSARSA 加密算法的有关数学知识加密算法的有关数学知识 7 7 2 1 数论 7 2 1 1 模运算 7 2 1 2 素数 7 2 1 3 最大公因子 9 2 1 4 幂模运算 11 2 1 5 乘法逆元 13 2 2 RSA 中重要定理 15 2 2 1 费马定理 15 2 2 2 欧拉定理 16 2 2 3 欧几里德算法 19 第三章第三章 MD5MD5 算法简介算法简介 2424 3 1 MD5 算法的发展史 24 3 2 MD5 算法的应用 25 3 3 MD5 算法描述 26 3 3 1 MD5 算法的步骤 26 3 3 2 MD5 的压缩函数 33 3 4 MD5 算法的安全 38 学院理学学士学位论文 目录 IV 第四章第四章 MD5MD5 算法在算法在 RSARSA 算法中应用算法中应用 3939 4 1 RSA 算法加密文件 39 4 1 1 加密过程 39 4 1 2 解密过程 40 4 2 文件的信息摘要 43 4 3 MD5 算法在 RSA 算法中的应用 44 4 4 补充说明 45 参考文献参考文献 4747 致致 谢谢 4848 APPENDIXAPPENDIX 4949 文献报告文献报告 5353 学院理学学士学位论 第一章 RSA 公钥密码简介 1 第一章第一章 RSA 公钥密码简介公钥密码简介 1 1 公开密钥密码系统公开密钥密码系统 一个好的加密算法的重要特点之一是具有这种能力 可以指定一个密码或密钥 并用它来加密明文 不同的密码或密钥产生不同的密文 这又分为两种方式 对称密 钥算法和非对称密钥算法 所谓对称密钥算法就是加密解密都使用相同的密钥 非对 称密钥算法就是加密解密使用不同的密钥 非常著名的 pgp 公钥加密以及 RSA 加密 方法都是非对称加密算法 加密密钥 即公钥 与解密密钥 即私钥 是非常的不同 的 从数学理论上讲 几乎没有真正不可逆的算法存在 公钥密码又称为双钥密码和非对称密码 是 1976 年由 Diffie 和 Hellman 在其 密 码学新方向 一文中提出的 他是用一个密钥进行加密 而用另一个不同但是有关的 密钥进行解密 图 1 1 1 给出了公开密钥加密过程 其中重要步骤如下 1 网络中的每个端系统都产生一对用于它将接收的报文进行加密和解密的密 钥 2 每个系统都通过把自己的加密密钥放进一个登记或者文件来公布告它 这 就是公开密钥 另一个密钥则是私有的 3 如果 A 想给 B 发送一个报瘪他就用 B 的公开密钥加密这个报文 4 B 收到这个报文后就用他的保密密钥解密报文 其他所有收到这个报文的 人都无法解密它 因为只有 B 才有 B 的私有密钥 学院工学学士学位论文 第一章 RSA 公钥密码简介 2 图 1 1 1 加密过程 非对称密钥算法 RSA 算法于 1977 年由美国麻省理工学院 MIT Messachusetts Institute of Technology 的 Ronal Rivest Adi Shamir 和 Len Adleman 三位年轻教授提出 并以三人的姓氏 Rivest shamir 和 Adlernan 命名为 RSA 算法 该算法利用了数论领域 的一个事实 那就是虽然把两大质数相乘生成一个合数是件十分容易的事情 但是把 一个合数分解为两个质数却十分困难 合数分解问题目前仍然是数学领域尚未解决的 一大难题 至今没有任何高效的分解方法 RSA 算法无须收发双方同时参与加密过程 且非常适合于电子函数系统的加密 1 2 RSA 加密算法加密算法 RSA 算法可以表述如下 1 密钥配制 假设 m 是想要传送的报文 现任选两个很大的质数 p 与 q 使得 选择正整数 e 使得 e 与互质 且 e 小于 1 1 npq 再利用相除法 求得 d 使得到 1 1 npq 1 mod edn 这里表示 n q p 其中 x mod y 是整数求模运算 其结果是 x 整除以 y 后剩余 的余数 如果 5 mod 3 2 所以密钥是 e n 是用于加密的公共密钥 可以公开 出去 而 d n 是用于解密的专用钥匙 必须保密 用 VC 求的 RSA 加密解密参数和密钥是 学院工学学士学位论文 第一章 RSA 公钥密码简介 3 结果分析是 由上图得知 公钥是 931 1067 私钥是 331 1067 2 加密过程 使用 e n 对明文 m 进行加密得到密文 c 算法为 c me mod n 加密结果为 使明文变成了不能读的密文 3 解密过程 使用 d n 对密文 c 进行解密 算法为 m ce mod n 求得的 m 是对应于密文 c 的明文 学院工学学士学位论文 第一章 RSA 公钥密码简介 4 解密结果为 解密的结果是使密文变成原文 RSA 公共密钥加密算法的核心是欧拉 Euler 函数 对于正整数 n 定义 n n 为小于 n 且与 n 互素的正整数的个数 例如 2 这是因为小于 6 且与 6 互素 6 的数有 1 和 5 共两个数 欧拉定义有两个重要性质 性质性质 1 如果 p 是质数 则 1pp 性质性质 2 2 如果 p 与 q 均为互质数 则 1 1 pqpq RSA 算法正是注意到这两条性质设计公共密钥系统的 p 与 q 的乘积 n 可以说 作为公共密钥公布出来 而 n 的因子 p 与 q 则包在专用密钥中 可以用来解密 如 果解密需要用到接收方由于知道因子 p 和 q 可以方便地算出 n 1 1 npq 如果窃听得了 n 但由于不知道它的因子 p 与 q 则很难求出 这时 窃 n 听者要么强行算出 要么对 n 进行因数分解求得 p 与 q 然而 我们知道 在 n 大数范围内作合数分解是十分困难的 困此窃听者很难成功 学院工学学士学位论文 第一章 RSA 公钥密码简介 5 1 3 RSA 公钥密码的安全公钥密码的安全 RSA 的安全性完全依赖于大数分解问题只是一个推测 目前 还未能从理论上证 明由 c 和 e 计算出 m 一定需要分解 n 还不能证明对 RSA 攻击的难度和分解 n 的难度 相当 但也没有比因式分解 n 更好的攻击方法 已知 n 求得 的欧拉函数 n 则 p 和 q 可以求得 因为根据欧拉定理 1 1 npq 1pqpq 22 4pqpqpq 据此列出方程 求得 p 和 q 然而 如果新方法能使密码分析者推算出 d 它也就成 为大数分解的一个新方法 通过猜测的值 可以攻击 RSA 但这种方法并不比分解 n 容易 1 1 npq 分解 n 是最显而易见的攻击方法 敌方手中有公钥 e 和模 n 要得到解密密 d 他就要 分解 n 目前 129 位长的数也被分解 因此 n 应大于这些数 目前 已有人在用 1024bit 308 位 n 值的 RSA 一个密码分析者完全可能去尝试每一个可能的 d 值 直到碰上一个正确的为止 这种 蛮力 攻击甚至不如尝试分解 n 有效 为安全起见 对 p 和 q 要求 p 和 q 的相差不大 p 1 和 q 1 有大素数因子 gcd p 1 q 1 很小 满足这样条件的素数称做安全素数 RSA 的出现使得大整数分解因 式这一古老的问题再次被重视 近些年来出现的不少比较高级的因数分解方法使 安 全素数 的概念也在不停的演化 所以 选择传统上认为是 安全素数 并不一定有 效的增加安全性 比较保险的方法就是选择足够大的素数 因为一个数越大 对其分 解因式的难度也就越大 对 n 和密钥长度的选择取决于用户保密的需要 密钥长度越 大 安全性也就越高 但是相应的计算速度也就越慢 由于高速计算机的出现 以前 认为已经很具安全性的 512 位密钥长度已经不再满足人们的需要 1997 年 RSA 组织 公布当时密钥长度的标准 个人使用 768 位密钥 公司使用 1024 位密钥 而一些非常 重要的机构使用 2048 位密钥 当时的人们预计到个人使用的 768 位密钥将在两年后就 会生存期满 那么也就是指今年 所以密钥长度的选取也要考虑到这个长度不再具效 力的预计时间 学院工学学士学位论文 第一章 RSA 公钥密码简介 6 RSA 的安全性不能仅靠密钥的长度来保证 在 RSA 算法中 还有一种值得注意的 现象 那就是存在一些 使得待加密消息经过若干次 RSA 变换后就会恢复成npq 原文 这不能不说是 RSA 本身具有的一个缺点 选择密钥时必须注意避免这种数 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 7 第二章第二章 RSA 加密算法的有关数学知识加密算法的有关数学知识 2 1 数论数论 本节主要介绍 RSA 算法所用到的数论事实 2 1 1 模运算模运算 定义 定义 给定一个整数 n 如果用 n 去除两个整数 a 和 b 所得的余数相同 则称 a 和 b 关于模 n 同余 记为 ab mod n 从 0 到处 n 1 的整数 a 它的模 n 剩余是从 0 到 n 1 之间的某个整数 运算 a mod n 表示 a 被 n 除的剩余 称为模 n 运算 例如 8mod5 3 模算术同普通的算术一样 是可交换的 可结合的和可分配的 而且 模 n 运算 的每一个中间结果 与先进行全部运算 再对最后的结果模 n 其作用是一样的 模运算的性质如下 a b mod n a mod n b mod n mod n a b mod n a mod n b mod n mod n a b mod n a mod n b mod n mod n a b c mod n ab mod n ac mod n mod n 密钥学中用了很多有关模的运算 因为像计算离散对数和模 n 平方根这样的问题 是困难的 模运算也很容易在计算机上实现 因为 它将所有中间值和最后结果限制在 一个范围内 对一个 k 特的模 n 任何加 减或乘的中间结果都不会超过 2k 比特长 因此我们可以用模算术做指数运算而又不会产生巨大的中间结果 2 1 2 素数素数 数论研究的重点是素数 素数是指一个大于 1 且因子只有 1 和它本身的整数 除 此之外没有其他数可以整除它 2 是一个素数学 其他素数如 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 8 79 2821 236537734359 等 素数有无限多 密码学 特别是公钥密码学 使用大素 数学 用 VC 来判断素数为 void CRsaMY OnButtonRandom 随机产生P Q N D E TODO Add your control notification handler code here long q p e fn d n GetDlgItem IDC EDIT P EnableWindow false GetDlgItem IDC EDIT Q EnableWindow false GetDlgItem IDC EDIT E EnableWindow false GetDlgItem IDC EDIT D EnableWindow false GetDlgItem IDC EDIT N EnableWindow false CString setstr srand unsigned time NULL strat0 p rand if sushu p p 200 goto strat0 else m p p 产生密钥参数P strat1 q rand if sushu q q 200 goto strat1 else m q q 产生密钥参数Q if dengch p q abs q p 1 d euclib e fn if d 1 sushu d goto strat2 else goto strat2 产生私有密钥e fm d d fm e e fm n n 初始化全局变量 m d d m n n UpdateData false 结果分析 由于产生的随机数的速度比较慢 所以在加密解密产生的密钥小一点儿 这样加密解密过程也快一点儿 2 1 3 最大公因子最大公因子 符号 gcd a b 用作表示 a 和 b 的最大公因子 正整数 c 是 a 和 b 的最大公因子 如 果满足下列条件 2 c 是 a 和 b 的因子 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 10 任何 a 和 b 的公因子也是 c 的因子 此外 还有如下的等价定义 gcd a b max k k a 且 k b 因为通常要求最大公因子为正 而 gcd a b gcd a b gcd a b gcd a b 即 gcd a b gcd a b 此外 由于 0 均能被所有非零整数整除 因此有 gcd a 0 a 如果将两个整数分别表示为素数的乘积 则很容易确定它们的最大公因子 例如 212 300235 12 1823 gcd 18 300 110 2356 如果有两个数 它们除此而外 之外没有他共同的因子 则称这两个数是互素的 换言之 如果整数 a 和 n 的最大公因子 gcd 等于 1 则认为 a 和 b 互素 即 gcd a b 1 如 15 和 28 13 和 500 是互素的 而 15 和 27 不是 一个素数与它的倍数以外的 任何的其他数都是互素的 计算两个数的最大公因子最容易的方法是古老的欧几里德 Euclidean 算法 算法 计算最大公因子的 Euclidean 算法 输入 整数 x y 输出 gcd x y 1 如果 x 0 则 x x 2 如果 y 0 执行 a gx b xy mod x c yg 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 11 5 返回 g 上述方法可求得最大公因子 用 VC 描述为 long CRsaMY gcd long x long y 最大公因子 long g g y while x 0 g x x y x y g return g g 是 x y 的最大公因子 结果分析 当 g 1 时 x 和 y 是互素的 用这个函数来判断两个数是否互素 2 1 4 幂模运算幂模运算 RSA 加 解密变换都要进行 xrmod n 的幂运算 求 mod p 可通过对指数 r 的二进制数化来实现 例如求 mod 17 7 r x 7 11 2 111 即 7 2102 22222 1 故 mod 17 11 mod 17 7 11 2 2 11 2 11 下面给出一种比较实用的方法 在此前 先通过实例观察运算的计算步骤 P mod 2537 13 1520 mod 2537 2 6 1 1520 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 12 mod 2537 6 2 1520 1520 其中 欧拉定理 将在下一节介绍 2 1520 1730 mod2537 因此 p 6 1730 1520 mod2537 2 3 1730 1520 mod2537 而 2 1730 1777 mod2537 因此 3 1777 1520 mod2537 p 2 1777 1777 1520 mod2537 而 2 1777 mod2537 1701 1777 1520 mod2537 1672 现在模拟这个过程给出计算流程如下图所示 mod r xp 例如 求 15 16 mod4731 1 16 15 1abc 2 14 16bc 3 2 7 16 mod4731 256 256ba 4 6 256 16 mod4731 4096 256bc 5 2 3 256 mod4731 4033b 4033a 6 2 4033 4096 mod4731 3247 3247bc 7 2 1 4033 mod4731 4642 4642ba 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 13 8 0 4642 3247 mod4731 4339 4339bc 9 因为 所以0 b 15 16 mod4731 4339 不过 这里还存在问题 因为 a b c 都很小我们不能发现问题 现在我们拿大 一些的做运算 实际结果如下 49022 49022 mod 61771 2403156484 mod 61771 17500 但是用计算机计算的结果如下 49022 49022 mod 61771 2403156484 mod 61771 14260 这是因为 2403156484 已经溢出了长整数的范围 得到的结果是未知的 我们用乘法性 质和模性质做特殊处理 乘法性质 49022 words i 10i 其中 words i 2 2 0 9 4 i 是 49022 的位数 再利用模的性质 a b mod n a mod n b mod n mod n a b mod n a mod n b mod n mod n 尽可以把 a c a a 的范围缩的很小 这样中间结果就不会超出整数范围 2 1 5 乘法逆元乘法逆元 如果 1 则 如果 a 与 n 互素 moda ba cn modbcn 例如 为了说明这一点 考虑一个附加条件不满足的例子 6 3 182mod8 6 7 422mod8 但 37mod8 造成这个奇怪结果的原因是对于乘数 a 模 n 的乘法运算返回的结果是 0 到 n 1 之间的数 如果 a 和 n 有除 1 以外的共同因子时将不会产生完整的余数集合 例如 取 a 6 和 n 8 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 14 因为乘以 6 的模 8 运算不会产生完整的余数集 中的多个数将映射到同一个余 8 z 数上 如 6 0mod86 4mod8 6 1mod86 5mod8 因为这是一个多对一的映射 对乘法运算不存在惟一的逆元 然而 如果取 a 5 n 8 余数行以不同的顺序包含了集合中所有的数 最后 还可观察到如果 P 是一个 8 z 素数 则集合中的所有数均与 p 互素 这样就能在之前 所列的性质中再加上一条性质 乘法逆元 对每一个 存在一个 z 使得 1 w p wz 1modwzp 因为与 P 互素 如果用乘以中的所有数模 P 得到的余数将以不同次序涵ww p z 盖中的所有数 那么 至少有一个余数的值为 1 因此 在中的某个数与相乘 p z p zw 模 p 的余数为 1 这个数就是的乘法逆元 命名为 这样 等式 w 1 w moda ba cn 与存在乘法逆元是一致的 对上等式的两边乘以 a 的乘法逆元 有 11 modaa baa cn modbcn 最后一点 某些整数但不是全部整数存在一个乘法逆元就将使模数不是一个素数 如果如 gcd a n 1 则能在中找到 b 使得 n z 1moda bp 原因与前一段是相同的 因为 a 与 n 互素 如果用 a 与中的所有数相乘模 n 得到的 n z 余数将以不同次序涵盖中的所有数 因此在中存在某个数 b 使得 n z n z 1moda bp 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 15 2 2 RSA 中重要定理中重要定理 2 2 1 费马定理费马定理 费马定理可表述为 如果 p 是素数 a 是个不能被 p 整除的正整数 则 1 1mod p ap 证明 1 从以前的讨论得出 如果中的所有数均与 a 相乘模 p 结果将以某种 p z 次序涵盖中的数 并且 p z 00modap 因此 p 1 个数 mod 2 mod 1 modapappap 恰好是某种次序的 1 2 p 1 将这些数相乘可得 2 1 mod 2 mod 1 mod modaapaapappapp 1 modpp 但 1 2 1 1 p aapapa 因此 1 1 1 mod p papp 可在两端去掉 p 1 因为它与 p 互素 这可以得到费马定理 例如 a 7 p 19 2 4 8 16 118162 74911mod19 71217mod19 74911mod19 71217mod19 7777 111mod19 p a 费马定理的另一种等价形式也很有用 如果 p 是素数 a 是任意正整数 则 mod p aap 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 16 2 2 2 欧拉定理欧拉定理 在引入欧拉定理之前 需首先介绍数论中的一个重要的量 即欧拉函数 Euler s totient function 记为 表示小于 n 的且与 n 互素的正整数个数 n n 例如 下表列出了 30 以内的整数的值 被定义为 1 但没有实际意义 n 1 某些欧拉函数的值 n 很显然 对于一个素数 p 有 1pp 现假定有两个不同的素数 p 和 q 则对 n q p 有 npq pq 1 1 pq 为了证明这一命题 1 考虑的完全余数集为 n z 0 1 2 p q 1 而不与 n 互素的余数包括 0 和集合 p 2p q 1 p q 2q p 1 1 因此 有 1 1 1 npqqp 1pqpq 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 17 1 1 pq pq 欧拉定理可表述为对于任何互素的整数 a 和 n 有 1mod n an 例如 a 3 n 10 4 10 4 3811mod10 证明 如果 n 为素数 则等式为真 因为此时 1mod n an 1 nn 根据费马定理可证 然而 对于其他任意整数 它也成文 表示不小于 n 且与 n 互素的正整数个数 n 假定这样的整数集合标记如下 12 n Rx xx 现在对该集合中的每个整数乘以 a 模 n 12 mod mod mod n saxnaxnaxn 集合 s 是集合 R 的 个置换 原因如下 1 因为 a 与 n 互素 也与 n 互素 则一定与 n 互素 因此 S 中的所有数均小于 i x i ax n 且与 n 互素 2 有 s 个不存在重复的整数 根据等式 如果 则 如果 a 与 n 互素 moda ba cn modbcn 如果 modmod ij axnaxn 则 ij xx 因此 11 mod nn ii ii axnx 11 mod nn ii ii axxn 11 mod nn n ii ii axxn 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 18 1mod n an 欧拉定理的另一种等价形式也很有用 1 mod n aan 欧拉定理的推论在说明 RSA 算法的有效时是很有用的 给定两个素数 p 和 q 以及整 数 n p q 和 m 其中 0 m n 则下面关系成立 1 1 1 1 mod npq mmmn 如果如 gcd m n 1 即如果 m 和 n 互素 则根据欧拉定理上面等式显然成立 假设 gcd m n 1 这意味着什么 因为 n p q 等式 gcd m n 1 等价于逻辑表达式 m 不是 p 的倍数 和 n 不是 q 的倍数 如果 m 是 p 的倍数 则 m 和 n 有公因子 p 因而 不可能是互素的 同样 如果 m 是 q 的倍数 则 m 和 n 有公因子 q 因而也不可能是 互素的 因此 表达式 gcd m n 1 必须等价于前面逻辑表达式的非 故 gcd m n 1 等价于 m 是 p 的倍数 或者 m 是 q 的倍数 下面讨论一下 m 是 p 倍数的情况 显然 m c p c 为某个正整数 在这种情况 下 必然有 gcd m n 1 有 m 是 p 倍数 也是 q 的倍数 但 m 0 return d else return d y d 结果分析 d 是要求的私钥 通过计算 厂面的关系成立 123ftdtt 123fxdxx 123fydyy 下面说明算法能正确返回 如果将欧几里德算法中的和看作是扩展gcd d fxy 欧几里德算法中的和 那么这两个变量的处理是完全相同的 在欧几里德算法的3x3y 每次迭代中 被设置为前一个值 而被设置为前一个 同样 在扩展的xyymodxy 欧几里德算法中 x3 被设置为前一个值 而被设置为前一个减大除以的3y3y3x3x3y 商 后一个数即为除以所得的余数 然后再乘以 也就是 3x3y3y3mod 3xy 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识 23 另外 如果 则最后一个步骤可得 0 且 1 因此在之前的步骤gcd 1d f 3y3x 中有 但如果 1 则有 31y 3y 123 121 21 1 21mod fydyy fydy dyyf dyf 并且是 d 模 f 的乘法逆元 2y 例如 下表是扩展欧几里德算法执行的一个例子 算法显示 gcd 550 1769 1 且 550 模 1769 的乘法逆元就是其本身 即 550 5501mod1769 扩展的 Euclib 550 1769 学院理学学士学位论文 第三章 MD5 算法简介 24 第三章第三章 MD5 算法简介算法简介 3 1 MD5 算法的发展史算法的发展史 MD5 1 的全称是 message digest algorithm 5 信息 摘要算法 在 90 年代初由 mitaboratory for computer science 和 rsa data security inc 的 ronald l rivest 开发出来 经 md2 md3 和 md4 发展而来 它的作用是让大容量信息在用数字签名软件签署私人密 钥前被 压缩 成一种保密的格式 就是把一个任意长度的字节串变换成一定长的大整 数 不管是 md2 md4 还是 md5 它们都需要获得一个随机长度的信息并产生一个 128 位的信息摘要 虽然这些算法的结构或多或少有些相似 但 md2 的设计与 md4 和 md5 完全不同 那是因为 md2 是为 8 位机器做过设计优化的 而 md4 和 md5 却是面 向 32 位的电脑 rivest 在 1989 年开发出 md2 算法 在这个算法中 首先对信息进行数据补位 使 信息的字节长度是 16 的倍数 然后 以一个 16 位的检验和追加到信息末尾 并且根 据这个新产生的信息计算散列值 后来 rogier 和 chauvaud 发现如果忽略了检验和将 产生 md2 冲突 md2 算法的加密后结果是唯一的 既没有重复 为了加强算法的安全性 rivest 在 1990 年又开发出 md4 算法 md4 算法同样需要 填补信息以确保信息的字节长度加上 448 后能被 512 整除 信息字节长度 mod 512 448 然后 一个以 64 位二进制表示的信息的最初长度被添加进来 信息被处理成 512 位迭代结构的模块 而且每个模块要通过三个不同步骤的处理 den boer 和 bosselaers 以及其他人很快的发现了攻击 md4 版本中第一步和第三步的漏洞 dobbertin 向大家演示了如何利用一部普通的个人电脑在几分钟内找到 md4 完整版本中的冲突 这个冲突实际上是一种漏洞 它将导致对不同的内容进行加密却可能得到相同的加 密后结果 毫无疑问 md4 就此被淘汰掉了 尽管 md4 算法在安全上有个这么大的漏洞 但它对在其后才被开发出来的好几种 信息安全加密算法的出现却有着不可忽视的引导作用 除了 md5 以外 其中比较有名 的还有 sha 1 ripe md 以及 haval 等 一年以后 即 1991 年 rivest 开发出技术上更为趋近成熟的 md5 算法 它在 md4 学院理学学士学位论文 第三章 MD5 算法简介 25 的基础上增加了 安全 带子 safety belts 的概念 虽然 md5 比 md4 稍微慢一些 但 却更为安全 这个算法很明显的由四个和 md4 设计有少许不同的步骤组成 在 md5 算 法中 信息 摘要的大小和填充的必要条件与 md4 完全相同 denboer 和 bosselaers 曾发 现 md5 算法中的假冲突 pseudo collisions 但除此之外就没有其他被发现的加密后结 果了 van oorschot 和 wiener 曾经考虑过一个在散列值中暴力搜寻冲突的函数 brute forcehash function 而且他们猜测一个被设计专门用来搜索 md5 冲突的机器 这台机 器在 1994 年的制造成本大约是一百万美元 可以平均每 24 天就找到一个冲突 但单 从 1991 年到 2001 年这 10 年间 竟没有出现替代 md5 算法的 md6 或被叫做其他什么 名字的新算法这一点 我们就可以看出这个瑕疵并没有太多的影响 md5 的安全性 上 面所有这些都不足以成为 md5 的在实际应用中的问题 并且 由于 md5 算法的使用不 需要支付任何版权费用的 所以在一般的情况下 非绝密应用领域 但即便是应用在绝 密领域内 md5 也不失为一种非常优秀的中间技术 md5 怎么都应该算得上是非常安 全的了 3 2 MD5 算法的应用算法的应用 MD5 的全称是 Message Digest Algorithm 5 Message Digest 泛指字节串 Message 的 Hash 变换 就是把一个任意长度的字节串变换成一定长的大整数 请注意我使用了 字节串 而不是 字符串 这个词 是因为这种变换只与字节的值有关 与字符集 或编码方式无关 MD5 将任意长度的 字节串 变换成一个 128bit 的大整数 并且它是一个不可逆 的字符串变换算法 换句话说就是 即使你看到源程序和算法描述 也无法将一个 MD5 的值变换回原始的字符串 在数学原理上 是因为原始的字符串有无穷多个 这 有点像不存在反函数的数学函数 MD5 的典型应用是对一段 Message 字节串 产生 fingerprint 指纹 以防止被 篡 改 举个例子 你将一段话写在一个叫 readmem txt 文件中 并对这个 readmem txt 产 生一个 MD5 的值并记录在案 然后你可以传播这个文件给别人 别人如果修改了文件 中的任何内容 你对这个文件重新计算 MD5 时就会发现 如果再有一个第三方的认证 机构 用 MD5 还可以防止文件作者的 抵赖 这就是所谓的数字签名应用 学院理学学士学位论文 第三章 MD5 算法简介 26 MD5 还广泛用于加密和解密技术上 在很多操作系统中 用户的密码是以 MD5 值 或类似的其它算法 的方式保存的 用户 Login 的时候 系统是把用户输入的密 码计算成 MD5 值 然后再去和系统中保存的 MD5 值进行比较 而系统并不 知道 用户的密码是什么 某些黑客破获这种密码的方法是一种被称为 跑字典 的方法 有两种方法得到 字典 一种是日常搜集的用做密码的字符串表 另一种是用排列组合方法生成的 先 用 MD5 程序计算出这些字典项的 MD5 值 然后再用目标的 MD5 值在这个字典中检 索 即使假设密码的最大长度为 8 同时密码只能是字母和数字 共 26 26 10 62 个 字符 排列组合出的字典的项数则是 P 62 1 P 62 2 P 62 8 那也已经是一个很大 的天文数字了 存储这个字典就需要 TB 级的磁盘组 而且这种方法还有一个前提 就 是能获得目标账户的密码 MD5 值的情况下才可以 在很多电子商务和社区应用中 管理用户的 Account 是一种最常用的基本功能 尽管很多 Application Server 提供了这些基本组件 但很多应用开发者为了管理的更大 的灵活性还是喜欢采用关系数据库来管理用户 懒惰的做法是用户的密码往往使用明 文或简单的变换后直接保存在数据库中 因此这些用户的密码对软件开发者或系统管 理员来说可以说毫无保密可言 本文的目的是介绍 MD5 的 Java Bean 的实现 同时给 出用 MD5 来处理用户的 Account 密码的例子 这种方法使得管理员和程序设计者都无 法看到用户的密码 尽管他们可以初始化它们 但重要的一点是对于用户密码设置习 惯的保护 3 3 MD5 算法描述算法描述 3 3 1 MD5 算法的步骤算法的步骤 该算法以一个任意长度的报文作为输入 产生 个 128bit 的报文摘要作为输出 输入是按 512bit 的分组进行处理的 图 3 3 1 描述了处理报文产生摘要的总的过程 处理操作包括以下几步 步骤步骤 1 附加填充比持 对报文进行填充使报文的长度 比特数 与 448 模 512 同余 长度 即填充长度为 512 的整数倍减去 64 例如 如果报文是 448bit448mod512 学院理学学士学位论文 第三章 MD5 算法简介 27 长 那么将填充 512bit 形成 960bit 的报文 填充比特串的最高位为 1 其余各位均为 0 步骤步骤 2 附加长度值 将用 64bit 表示的初始报文 填充前 的位长度附加在步骤 1 的结果后 低位字节优先 如果初始长度大于 仅使用该长度的低 64bit 这样 该 64 2 区域所包含的长度值为初始报文长度模的值 64 2 这两步的结果将产生一个长度为 512 整数倍比特的报文 在图 3 3 1 中 经扩展的 报文表示成 512bit 的分组序列 因此扩展的报文长度等于 与之 011 L Y YY 512L 等价的是 该结果也等于字长为 16bit 或 32bit 的整数倍 让表示扩展报文包含的字数 其中 N 是 16 的整数倍 因此 N 512L 图图 3 3 1 使用使用 MD5 产生摘要的过程产生摘要的过程 步骤步骤 3 初始化 MD 缓存 使用一个 128bit 的缓存来存放该散列函数的中间及最 终结果 该缓存可表示为 4 个 32bit 的寄存器 state0 state1 state2 state3 这些寄存 器被初始化为如下 32bit 长的整数 十六进制表示 state0 0 x01234567 state1 0 x89abcdef state2 0 xfedcba98 state3 0 x76543210 这些值以小数次序的格式存储 即字的低位字节放在低地址字节上 像 32bit 的串 初 始化的值 十六进制表示 以如下方式存储 学院理学学士学位论文 第三章 MD5 算法简介 28 字 state0 0l 23 45 67 字 state1 89 ab cd ef 字 state2 fe dc ba 98 字 state3 76 54 32 l0 步骤步骤 4 处理 512bit 16 个字 报文分组序列 算法的核心是一个包含 4 个 循环 的压缩函数 这个模块在上图中标识为 HMD5 说明了它的逻辑 4 个循环有相似的 结构 但每次循环使用不同的原始逻辑函数 在说明中分别表示为 F G H 和 I 它 们的定义如下 CMDHash f DWORD x DWORD y DWORD z 第一个非线性运算函数 return x CMDHash g DWORD x DWORD y DWORD z 第二个非线性运算函数 return x CMDHash h DWORD x DWORD y DWORD z 第三个非线性运算函数 return x y z CMDHash i DWORD x DWORD y DWORD z 第四个非线性运算函数 return y x z 每一循环都以当前的正在处理的 512bit 分组 和 128bit 的缓存值 q Y state0 state1 state2 state3 为输人 然后更新缓存的内容 每一循环还使用一个 64 元素 表的四分之一 该表通过正弦函数构建 T 的第 i 个元素 表示为 的值等 0 64 T T i 于的整数部分值 其中 i 的单位是弧度 因为是 0 到 l 之间的 32 2 sin absi sin absi 数 因此每个 T 中的元素值均能用 32bit 表示 这个表提供了一个 随机化 的 32bit 模式集 它将消除输入数据的任何规律性 表 3 3 2 列出了 T 的所有值 第 4 次循环的输出加到第 1 次循环的输入 上产生 相加是缓存中 q CV 1q CV 4 个字分别与中对应的 4 个字以模相加 32 2 学院理学学士学位论文 第三章 MD5 算法简介 29 图图 3 3 2 单位个单位个 512bit 分组的分组的 MD5 处理系统过程处理系统过程 表表 3 3 1 逻辑函数的真值表逻辑函数的真值表 学院理学学士学位论文 第三章 MD5 算法简介 30 表表 3 3 2 由整弦函数构造的表由整弦函数构造的表 T 步骤步骤 5 输出 L 所有 L 个 512bit 的分组处理完成后 第 L 阶段产生的输出便是 128 比的报文摘要 以上用 VC 描述为了 实现步骤 1 的函数是 filelengsub int n CString CMDHash filelengsub int n n为字符串的长度余数418 0 n448 i 1 getstr Empty return stringlen 先填充这个 再填充64位 结果如上图 字符串是 nihaoni不覆在za 结果分析 字符串的长度为15 15 512 15 所以在字符串后要加1个1和432个0 实现步骤2的函数是filelen long n CString CMDHash filelen long n 64位二进制表示的填充前信息长度 int i 0 int a 64 g 64 while n 0 a i n 2 学院理学学士学位论文 第三章 MD5 算法简介 32 n n 2 求文件长度的二进制数 a i 1 int k i int k1 k 1 for i 0 i k i g k1 a i 文件长度值的二进制表示 CString getstr fileleng for i 0 i 64 k i int a 0 getstr Format d a fileleng getstr k1 0 for i 64 k i 64 i getstr Format d g k1 fileleng getstr getstr Empty return fileleng 返回长度为64的字符串 结果加下图 字符串是 nihaoni不覆在za 学院理学学士学位论文 第三章 MD5 算法简介 33 结果分析 15的二进制表示为1111 在其高位要加60个0 步骤1和2使原字符串的长 度变为 n mod 512 448 3 3 2 MD5 的压缩函数的压缩函数 现在了解四次循环处理一个 512bit 分组中 64 次循环的逻辑 每一循环由对缓存数 state0 state1 state2 state3 的 16 步操作组成 每一步操作的形式为 abag b