资源目录
压缩包内文档预览：(预览前20页/共61页)
编号：58722630
类型：共享资源
大小：2.32MB
格式：RAR
上传时间：2020-03-17
上传人：qq77****057
认证信息
个人认证
李**（实名认证）
江苏
IP属地：江苏
7.2
积分
- 关 键 词：
-
VC020
数字
加密
技术
- 资源描述：
-
VC020数字加密技术1,VC020,数字,加密,技术
- 内容简介：
-
学院理学学士学位论文学院理学学士学位论文 RSA 加密算法和信息摘要加密算法和信息摘要 杨丽彬 二零零五年六月九日分类号 学校代码 UDC 密级 学 号 2001162135 学院学院信息工程学院毕业论文信息工程学院毕业论文RSA 加密算法和信息摘要加密算法和信息摘要杨丽彬杨丽彬指导教师 （填写名字、职务或职称，校外指导教师的单位名称） 申请学位级别 专业名称 论文提交日期 论文答辩日期 学位授予单位和日期 答辩委员会主席 论文评阅人 20年 月 学院理学学士学位论 摘要I摘要摘要 在这个信息爆炸的时代，随著电脑通信与网络的日渐普及，数据传输的安全性愈发受到重视，密码学已成为一个相当重要的课题。在密码系统中，主要可分成私有密钥系统与公开密钥系统。在公开密钥系统中，RSA 密码系统是最有名也是最普及的密码系统。基本上，RSA 密码系统是由高位元数的模乘法运算以及模指数运算所组成。由于其运算复杂度相当高，想要破解公开密钥以便得到私密密钥是相当困难的事。 随著通信传播上的蓬勃发展，使得互联网越来越受到欢迎，以致于，对于类似电子商务的服务，网络上安全的问题成为主要考虑的课题。而其基本上的安全需求，包含有隐密性，可认证性，数据的完整性和不可否认性。为了提供上述的安全服务，大多的网络系统使用公开密钥密码系统。而 RSA 密码系统和 MD5 信息摘要算法结合可以确保数据的完整性。关键词 ：公开密钥系统，公钥，私钥，RSA 密码系统，MD5 信息摘要。 学院理学学士学位论文 AbstractIIAbstract 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 IABSTRACTABSTRACT .IIII目录目录 .IIIIII第一章第一章 RSARSA 公钥密码简介公钥密码简介 .1 11.1 公开密钥密码系统.11.2 RSA 加密算法 .21.3 RSA 公钥密码的安全 .5第二章第二章 RSARSA 加密算法的有关数学知识加密算法的有关数学知识 .7 72. 1 数论.72.1.1 模运算.72.1.2 素数 .72.1.3 最大公因子 .92.1.4 幂模运算 .112.1.5 乘法逆元.132.2 RSA 中重要定理 .152.2.1 费马定理.152.2.2 欧拉定理.162.2.3 欧几里德算法.19第三章第三章 MD5MD5 算法简介算法简介.24243.1 MD5 算法的发展史 .243.2 MD5 算法的应用 .253.3 MD5 算法描述.263.3.1 MD5 算法的步骤 .263.3.2 MD5 的压缩函数 .333.4 MD5 算法的安全 .38 学院理学学士学位论文 目录IV第四章第四章 MD5MD5 算法在算法在 RSARSA 算法中应用算法中应用.39394.1 RSA 算法加密文件 .394.1.1 加密过程.394.1.2 解密过程.404.2 文件的信息摘要.434.3 MD5 算法在 RSA 算法中的应用 .444.4 补充说明.45参考文献参考文献 .4747致致 谢谢 .4848APPENDIXAPPENDIX .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)npq1(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)pqpqRSA 算法正是注意到这两条性质设计公共密钥系统的，p 与 q 的乘积 n 可以说作为公共密钥公布出来，而 n 的因子 p 与 q 则包在专用密钥中，可以用来解密。如果解密需要用到接收方由于知道因子 p 和 q，可以方便地算出：( )n( )(1) (1)npq如果窃听得了 n，但由于不知道它的因子 p 与 q，则很难求出。这时，窃( )n听者要么强行算出，要么对 n 进行因数分解求得 p 与 q。然而，我们知道，在( )n大数范围内作合数分解是十分困难的，困此窃听者很难成功。 学院工学学士学位论文 第一章 RSA 公钥密码简介 51.3 RSA 公钥密码的安全公钥密码的安全RSA 的安全性完全依赖于大数分解问题只是一个推测，目前，还未能从理论上证明由 c 和 e 计算出 m 一定需要分解 n。还不能证明对 RSA 攻击的难度和分解 n 的难度相当，但也没有比因式分解 n 更好的攻击方法。已知 n，求得（的欧拉函数） ，( )n则 p 和 q 可以求得。因为根据欧拉定理：( )(1) (1)npq () 1pqpq22()()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 公钥密码简介 6RSA 的安全性不能仅靠密钥的长度来保证。在 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 加密算法的有关数学知识879，2821，236537734359 等。素数有无限多。密码学，特别是公钥密码学，使用大素数学。用 VC+来判断素数为 ：void CRsaMY:OnButtonRandom() /随机产生P，Q，N，D，E/ TODO: Add your control notification handler code herelong 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; /产生密钥参数Pstrat1 :q = rand();if(!sushu(q) | q 200)goto strat1;elsem_q = q; /产生密钥参数Qif(!dengch(p,q) | abs(q - p) 1 & efn)m_e = e;d = euclib(e,fn);if(d1 | !sushu(d)goto strat2;else goto strat2; /产生私有密钥efm_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) = maxk,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|。如果将两个整数分别表示为素数的乘积，则很容易确定它们的最大公因子。例如 ：212300235 121823 gcd(18,300) = 1102356 如果有两个数，它们除此而外 之外没有他共同的因子，则称这两个数是互素的。换言之，如果整数 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(x0)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=，rx7112(111)即7 = 210222222 1故： mod 17 = *11(mod 17)71122(11)2(11)下面给出一种比较实用的方法。在此前，先通过实例观察运算的计算步骤。P = (mod 2537)131520 = (mod 2537)2 6 1(1520) 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识12 = (mod 2537)62(1520 )1520其中 ： (欧拉定理，将在下一节介绍)2(1520)1730(mod2537)因此 ：p6(1730)1520(mod2537) =2 3(1730 )1520(mod2537)而 ：2(1730)1777(mod2537)因此 ：3(1777)1520(mod2537)p = 2(1777)(1777 1520)(mod2537)而 ：21777 (mod2537)17011777 1520(mod2537)1672现在模拟这个过程给出计算流程如下图所示 ：(mod)rxp例如 ： 求15(16) (mod4731)（1）16,15,1abc（2）14,16bc（3）27,(16) (mod4731)256,256ba（4）6,256 16(mod4731)4096,256bc（5），23,(256) (mod4731)4033b 4033a （6）2,4033 4096(mod4731)3247,3247bc（7）21,4033 (mod4731)4642,4642ba 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识13（8）0,4642 3247(mod4731)4339,4339bc（9）因为 所以0,b 1516 (mod4731)4339不过，这里还存在问题，因为 a，b，c 都很小我们不能发现问题。现在我们拿大一些的做运算，实际结果如下：(49022*49022) mod 61771 = 2403156484 mod 61771 = 17500但是用计算机计算的结果如下：(49022*49022) mod 61771 = 2403156484 mod 61771 = -14260这是因为 2403156484 已经溢出了长整数的范围，得到的结果是未知的。我们用乘法性质和模性质做特殊处理。乘法性质：49022*wordsi* 10i其中：wordsi = 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 cnmodbcn 例如：为了说明这一点，考虑一个附加条件不满足的例子： 63182mod8 67422mod8但。37mod8造成这个奇怪结果的原因是对于乘数 a，模 n 的乘法运算返回的结果是 0 到 n-1之间的数，如果 a 和 n 有除 1 以外的共同因子时将不会产生完整的余数集合。例如：取 a = 6 和 n = 8； 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识14因为乘以 6 的模 8 运算不会产生完整的余数集中的多个数将映射到同一个余8z数上。如：6 0mod86 4mod86 1mod86 5mod8因为这是一个多对一的映射，对乘法运算不存在惟一的逆元。 然而，如果取 a = 5, n = 8 ：余数行以不同的顺序包含了集合中所有的数。最后，还可观察到如果 P 是一个8z素数则集合中的所有数均与 p 互素 。 这样就能在之前所列的性质中再加上一条性质： 乘法逆元()对每一个，存在一个 z，使得1wpwz1modwzp因为与 P 互素，如果用乘以中的所有数模 P，得到的余数将以不同次序涵wwpz盖中的所有数。那么，至少有一个余数的值为 1。因此，在中的某个数与相乘pzpzw模 p 的余数为 1。这个数就是的乘法逆元，命名为。这样等式：w1w()()moda ba cn与存在乘法逆元是一致的。对上等式的两边乘以 a 的乘法逆元，有：11()()modaa baa cn modbcn最后一点：某些整数但不是全部整数存在一个乘法逆元就将使模数不是一个素数。如果如 gcd(a,n)= 1，则能在中找到 b，使得：nz1moda bp原因与前一段是相同的。因为 a 与 n 互素，如果用 a 与中的所有数相乘模 n，得到的nz余数将以不同次序涵盖中的所有数。因此在中存在某个数 b，使得：nznz1moda bp 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识152.2 RSA 中重要定理中重要定理2.2.1 费马定理费马定理费马定理可表述为：如果 p 是素数，a 是个不能被 p 整除的正整数，则：11modpap证明1：从以前的讨论得出，如果中的所有数均与 a 相乘模 p，结果将以某种pz次序涵盖中的数。并且 ：pz00modap因此，(p1)个数： mod ,2 mod ,.,(1) modapappap恰好是某种次序的1,2,(p-1)。将这些数相乘可得：2. (1) )( mod) (2 mod) . (1) mod)modaapaapappapp (1)!modpp但 ：12. (1) )(1)!paapapa因此1(1)!(1)!modppapp可在两端去掉(p-1)!，因为它与 p 互素，这可以得到费马定理。例如 ：a = 7,p = 192481611816274911mod1971217mod1974911mod1971217mod197777 111mod19pa费马定理的另一种等价形式也很有用：如果 p 是素数,a 是任意正整数，则 ：modpaap 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识162.2.2 欧拉定理欧拉定理在引入欧拉定理之前，需首先介绍数论中的一个重要的量，即欧拉函数 (Eulers totient function ),记为，表示小于 n 的且与 n 互素的正整数个数。( )n( )n例如；下表列出了 30 以内的整数的值，被定义为 1，但没有实际意义。( )n(1)某些欧拉函数的值( )n很显然，对于一个素数 p，有：( )1pp现假定有两个不同的素数 p 和 q， 则对 n=q*p，有：( )()npq( )( )pq (1) (1)pq为了证明这一命题1，考虑的完全余数集为：nz0,1,2,(p q-1)而不与 n 互素的余数包括 0 和集合p,2p,(q-1)pq,2q,(p-1)1因此，有 ：( )(1)(1) 1npqqp () 1pqpq 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识17 (1) (1)pq ( )( )pq欧拉定理可表述为对于任何互素的整数 a 和 n，有：( )1modnan例如 ：a = 3;n = 10; = 4;(10)43811mod10证明：如果 n 为素数，则等式为真，因为此时( )1modnan( )(1)nn根据费马定理可证。然而，对于其他任意整数，它也成文：表示不小于 n 且与 n 互素的正整数个数，( )n假定这样的整数集合标记如下：12( ) ,.,nRx xx 现在对该集合中的每个整数乘以 a 模 n：12( )(mod ),(mod ),.,(mod )nsaxnaxnaxn 集合 s 是集合 R 的个置换，原因如下：1. 因为 a 与 n 互素，也与 n 互素，则一定与 n 互素。因此，S 中的所有数均小于ixiaxn 且与 n 互素。2. 有 s 个不存在重复的整数。根据等式：如果，则 如果 a 与 n 互素()()moda ba cnmodbcn如果：modmodijaxnaxn则 ：。ijxx因此 ：( )( )11(mod )nniiiiaxnx ( )( )11(mod )nniiiiaxxn ( )( )( )11(mod )nnniiiiaxxn 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识18( )1modnan欧拉定理的另一种等价形式也很有用：( ) 1(mod )naan欧拉定理的推论在说明 RSA 算法的有效时是很有用的。给定两个素数 p 和 q，以及整数 n=p*q 和 m,其中 0mn，则下面关系成立 ：( ) 1(1) (1) 1modnpqmmmn 如果如 gcd(m,n)=1，即如果 m 和 n 互素，则根据欧拉定理上面等式显然成立。假设gcd(m，n)1，这意味着什么?因为 np*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 是要求的私钥。通过计算，厂面的关系成立：123ftdtt123fxdxx123fydyy下面说明算法能正确返回。如果将欧几里德算法中的和看作是扩展gcd( ,)d fxy欧几里德算法中的和，那么这两个变量的处理是完全相同的。在欧几里德算法的3x3y每次迭代中，被设置为前一个值，而被设置为前一个。同样在扩展的xyymodxy欧几里德算法中，x3 被设置为前一个值，而被设置为前一个减大除以的3y3y3x3x3y商，后一个数即为除以所得的余数，然后再乘以，也就是。3x3y3y3mod 3xy 学院理学学士学位论文 第二章 RSA 加密算法的有关数学知识23另外，如果，则最后一个步骤可得=0 且=1。因此在之前的步骤gcd( ,)1d f3y3x中有。但如果1，则有：31y 3y12312121 (1)21modfydyyfydydyyfdyf 并且是 d 模 f 的乘法逆元。2y 例如：下表是扩展欧几里德算法执行的一个例子。算法显示：gcd(550,1769)1且 550 模 1769 的乘法逆元就是其本身；即 ：550 5501mod1769扩展的 Euclib(550,1769) 学院理学学士学位论文 第三章 MD5 算法简介24第三章第三章 MD5 算法简介算法简介3.1 MD5 算法的发展史算法的发展史MD51的全称是 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 算法简介26MD5 还广泛用于加密和解密技术上，在很多操作系统中，用户的密码是以 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。这样，该642区域所包含的长度值为初始报文长度模的值。642这两步的结果将产生一个长度为 512 整数倍比特的报文。在图 3.3.1 中，经扩展的报文表示成 512bit 的分组序列，因此扩展的报文长度等于。与之011,.,LY YY512L等价的是，该结果也等于字长为 16bit 或 32bit 的整数倍。让表示扩展报文包含的字数，其中 N 是 16 的整数倍。因此，N = 。512L图图 3.3.1 使用使用 MD5 产生摘要的过程产生摘要的过程步骤步骤 3：初始化 MD 缓存。使用一个 128bit 的缓存来存放该散列函数的中间及最终结果。该缓存可表示为 4 个 32bit 的寄存器(state0，state1，state2，state3)。这些寄存器被初始化为如下 32bit 长的整数(十六进制表示)：state0 :0x01234567state1 :0x89abcdefstate2 :0xfedcba98state3 :0x76543210这些值以小数次序的格式存储，即字的低位字节放在低地址字节上。像 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&y) | (x)&z);CMDHash:g(DWORD x, DWORD y, DWORD z) /第二个非线性运算函数return (x&y) | (y&(z);CMDHash:h(DWORD x, DWORD y, DWORD z)/第三个非线性运算函数return (xyz);CMDHash:i(DWORD x, DWORD y, DWORD z) /第四个非线性运算函数 return (y(x|(z);每一循环都以当前的正在处理的 512bit 分组()和 128bit 的缓存值qYstate0,state1,state2,state3 为输人，然后更新缓存的内容。每一循环还使用一个 64 元素表的四分之一，该表通过正弦函数构建。T 的第 i 个元素(表示为)的值等0.64T T i于的整数部分值其中 i 的单位是弧度。因为是 0 到 l 之间的322(sin( )absi(sin( )absi数因此每个 T 中的元素值均能用 32bit 表示。这个表提供了一个“随机化”的 32bit模式集，它将消除输入数据的任何规律性。表 3.3.2 列出了 T 的所有值。 第 4 次循环的输出加到第 1 次循环的输入()上产生。相加是缓存中qCV1qCV4 个字分别与中对应的 4 个字以模相加。322 学院理学学士学位论文 第三章 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 & n = 512)n = 0;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 a64,g64;while( n != 0)ai+ = n % 2; 学院理学学士学位论文 第三章 MD5 算法简介32n = n / 2; /求文件长度的二进制数ai = 1;int k = i;int k1 = k-1;for(i=0;ik;i+)gk1- = ai; /文件长度值的二进制表示 CString getstr,fileleng = ;for(i=0; i64-k; i+)int a=0;getstr.Format(%d,a);fileleng += getstr;k1 = 0;for(i=64-k; i64; i+)getstr.Format(%d,gk1+);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 c dX kT is其中：a = state0; b = state1; c = state2; d = state3;a,b,c,d 缓存中的 4 个字，在不同步骤中有指明的顺序s 是 32bit 参数循环左移(旋转)s 个比特 是第 g 个长度为 512bit 报文分组中的第 k 个 32bit 字 16X kM qk是矩阵 T 中的第 i 个 32bit 字 T i + 模加法 图 3.3.3 说明这个步骤的操作。在每步中，四个字(a,b,c,d)被用来产生字级别的循环右移以更新这些字的内容。 学院理学学士学位论文 第三章 MD5 算法简介34图图 3.3.3 基本的基本的 MD5 操作操作用 VC+描述压缩函数：void CMDHash:round4(CString s, int n)/n是处理后的字符或文件的长度,s为文件或字符DWORD a,b,c,d;a = state0; /state0,state1,state2,state3的入口b = state1;c = state2;d = state3;DWORD x16;int m = n/16;for(int j=0;jm;j+) /s是字符串,其长度为N = L*512,q=0 to N/16-1; for(int i=0;i16;i+) 学院理学学士学位论文 第三章 MD5 算法简介35xi = (unsigned long)sj*16+i; /*round 1*/ a = ff(a,b,c,d,x0,7,0xd76aa478); d = ff(d,a,b,c,x1,12,0xe8c7b756); c = ff(c,a,b,d,x2,17,0x242070db); b = ff(b,a,c,d,x3,22,0xc1bdceee); a = ff(a,b,c,d,x4,7,0xf57c0faf); d = ff(d,a,b,c,x5,12,0x4787c62a); c = ff(c,a,b,d,x6,17,0xa8304613); b = ff(b,a,c,d,x7,22,0xfd469501); a = ff(a,b,c,d,x8,7,0x698098d8); d = ff(d,a,b,c,x9,12,0x8b44f7af); c = ff(c,a,b,d,x10,17,0xffff5bb1); d = ff(d,a,c,d,x11,22,0x895cd7be); a = ff(a,b,c,d,x12,7,0x6b901122); d = ff(d,a,b,c,x13,12,0xfd987193); c = ff(c,a,b,d,x14,17,0xa679438e); b = ff(b,a,c,d,x15,22,0x49b40821);/*round 2*/ a = gg(a,b,c,d,x1,5,0xf61e2562); d = gg(d,a,b,c,x6,9,0xc040b340); c = gg(c,a,b,d,x11,14,0x265e5a51); b = gg(b,a,c,d,x0,20,0xe9b6c7aa); a = gg(a,b,c,d,x5,5,0xd62f105d); d = gg(d,a,b,c,x10,9,0x02441453); c = gg(c,a,b,d,x15,14,0xd8a1e681); b = gg(b,a,c,d,x4,20,0xe7d3fbc8); a = gg(a,b,c,d,x9,5,0x21e1cde6); d = gg(d,a,b,c,x14,9,0xc33707d6); c = gg(c,a,b,d,x3,14,0xf4d50d87); 学院理学学士学位论文 第三章 MD5 算法简介36 b = gg(b,a,c,d,x8,20,0x455a14ed); a = gg(a,b,c,d,x13,5,0xa9e3e905); d = gg(d,a,b,c,x2,9,0xfcefa3f8); c = gg(c,a,b,d,x7,14,0x676f02d9); b = gg(b,a,c,d,x12,20,0x8d2a4c8a);/*round 3*/ a = hh(a,b,c,d,x5,4,0xfffa3942); d = hh(d,a,b,c,x8,11,0x8771f681); c = hh(c,a,b,d,x11,16,0x6d9d6122); b = hh(b,a,c,d,x14,23,0xfde5380c); a = hh(a,b,c,d,x1,4,0xa4beea44); d = hh(d,a,b,c,x4,11,0x4bdecfa9); c = hh(c,a,b,d,x7,16,0xf6bb4b60); b = hh(b,a,c,d,x10,23,0xbebfbc70); a = hh(a,b,c,d,x13,4,0x289b7ec6); d = hh(d,a,b,c,x0,11,0xeaa127fa); c = hh(c,a,b,d,x3,16,0xd4ef3085); b = hh(b,a,c,d,x6,23,0x04881d05); a = hh(a,b,c,d,x9,4,0xd9d4d039); d = hh(d,a,b,c,x12,11,0xe6db99e5); c = hh(c,a,b,d,x15,16,0x1fa27cf8); b = hh(b,a,c,d,x2,23,0xc4ac5665);/*round 4*/ a = ii(a,b,c,d,x0,6,0xf4292244); d = ii(d,a,b,c,x7,10,0x432aff97); c = ii(c,a,b,d,x14,15,0xab9423a7); b = ii(b,a,c,d,x5,21,0xfc93a039); a = ii(a,b,c,d,x12,6,0x655b59c3); d = ii(d,a,b,c,x3,10,0x8f0ccc92); c = ii(c,a,b,d,x10,15,0xffeff47d); 学院理学学士学位论文 第三章 MD5 算法简介37 b = ii(b,a,c,d,x1,21,0x85845dd1); a = ii(a,b,c,d,x8,6,0x6fa87e4f); d = ii(d,a,b,c,x15,10,0xfe2ce6e0); c = ii(c,a,b,d,x6,15,0xa3014314); b = ii(b,a,c,d,x13,21,0x4e0811a1); a = ii(a,b,c,d,x4,6,0xf7537e82); d = ii(d,a,b,c,x11,10,0xbd3af235); c = ii(c,a,b,d,x2,15,0x2ad7d2bb); b = ii(b,a,c,d,x9,21,0xeb86d391); state0 += a; state1 += b; state2 += c; state3 += d; /缓存state0,state1,state2,state3，并对它重新重值 MD5 对信息摘要的结果是：1. 对字符串做摘要2. 对文件做摘要 学院理学学士学位论文 第三章 MD5 算法简介383.4 MD5 算法的安全算法的安全md5 相对 md4 所作的改进1： 1. 增加了第四轮； 2. 每一步均有唯一的加法常数； 3. 为减弱第二轮中函数 g 的对称性从(x&y)|(x&z)|(y&z)变为(x&z)|(y&(z)； 4. 第一步加上了上一步的结果，这将引起更快的雪崩效应； 5. 改变了第二轮和第三轮中访问消息子分组的次序，使其更不相似； 6. 近似优化了每一轮中的循环左移位移量以实现更快的雪崩效应。各轮的位移量互不相同。 学院理学学士学位论文 第四章 MD5 算法在 RSA 算法中的应用39第四章第四章 MD5 算法在算法在 RSA 算法中应用算法中应用4.1 RSA 算法加密文件算法加密文件RSA 加密算法是主要应用于网络传输方面。比如 A 发给 B 一封秘密文件，A 现在采用 RSA 加密算法加密文件。发送方 A 通过某种途径知道了接收方 B 的公钥，并对发送文件加密，产生密文在网络上传输，而此密文只有知道 B 的公钥才能解密。4.1.1 加密过程加密过程RSA 加密算法采用分组的方法对文件加密，在这里分组长度为 1000 个字节。我的加密思想是：步骤步骤 1 ：n 为文件的长度，把文件分为(n/1000+1)组，对每个组进行加密。步骤步骤 2 ：建立一个临时文件。在原文件中读取第 i 组，把第 i 组中的每个字强制转化为整型，就可以实现 RSA 算法对数据加密。由于文件中可能有英文，有数字和汉字，他们的字节数不同。并且强制转化为整数时，它们的符号也不同：汉字有两个字节，他们都为负整数，数字和英文有一个字节，他们都为正整数（加密过程不会改变它们的符号） 。再对转化后的每个字节加密成为新的数，把它们连成字符串，并用空格隔开。把加密后的字符串读入临时文件中。如：加密字符串：“你 ni 你 12” 。结果如下：图 4.1.1再对他们做异或运算，结果如下： 学院理学学士学位论文 第四章 MD5 算法在 RSA 算法中的应用40图 4.1.2这就是加密的最后结果。步骤步骤 3 ：把临时文件的内容复制到原文中，代替原文，并删除临时文件。 对比以上两个图，图 4.1.2 比图 4.1.1 保密性要好一些。所以在加密后再做异或运算。4.1.2 解密过程解密过程步骤步骤 1 ：n 为加密后文件的长度，把文件分为(n/10000+1)组，对每个组进行加密。由于加密后的文件比没加密的文件要长 4-5 倍，所以分组要大一些。步骤步骤 2 ：建立一个临时文件。在原文件中读取第 i 组，把第 i 组中的每个字做异或运算，就可以得到表 4.1.1。可以实现 RSA 算法对数据解密。这样的密文中只有：-（负号） ，空格和数字（从 0 到 9） 。把每 10000 个字节长的字符串，转化成整数，放在数组中。 分组的时候，可能的情况是：1）最后一个字符是“-” 。2）最后一个字符是空格。3）也许是一个整数被分割开来。4）也许是汉字的两个字节被分开了。5）最后一组的最后一个整数后没有空格，要对其特殊处理。 考虑到这样的问题，如果最后一个字符是“-” ，就把他放在下组中。最后一个字符是空格，要检验负数的个数，如果就偶数个，就把空格放在下组，如果是奇数个，就把最后的负数和空格放在下组。具体描述如下：CString CRsaFile:GetNumberValue(CString pString, long lenth) / 算法 学院理学学士学位论文 第四章 MD5 算法在 RSA 算法中的应用41long getlength;getlength = pString.GetLength(); /分组加密后的字符串长度CString getnumstring,m_wpstring,m_wppstring;long *direction;direction = new longlenth; /建立数组int top = 0;getnumstring = ;int count;int getnumcount = 0;if(m_getlongstring != )directiontop+ = atoi(m_getlongstring);for(count = 0;count getlength; count+)if(count = 0 & m_gettempstr != )if(atoi(m_gettempstr) != 0)getnumstring = m_gettempstr;CString a = pStringcount;if(a != ) getnumstring +=a;elsedirectiontop+ = atoi(getnumstring);getnumstring = ;m_gettempstr = ; 学院理学学士学位论文 第四章 MD5 算法在 RSA 算法中的应用42 if(getnumstring =-)m_gettempstr = -; elseif(getnumstring != )m_gettempstr.Format(%d,atoi(getnumstring);int directionnum = top;int getrealnum;m_wppstring = ;for(top = 0;top directionnum;top+)if(directiontop 0)getnumcount+;if(top =directionnum-1)&(directiontop 0)&(getnumcount % 2 = 1)m_getlongstring.Format(%d,directiontop);elsegetrealnum = GettPow(directiontop,fm_d,fm_n); /加密解密函数m_wpstring.Format(%c,getrealnum);m_wppstring += m_wpstring;m_getlongstring = ;delete direction;return m_wppstring; 学院理学学士学位论文 第四章 MD5 算法在 RSA 算法中的应用434.2 文件的信息摘要文件的信息摘要对文件的摘要和对字符串摘要是一样的。步骤步骤 1 ：把文件分组。这里 512 个字节分为一组（512%16 = 0） 。步骤步骤 2：对除最后一组做摘要。对第一组做摘要时，把 state0,state1,state2,state3 的值赋给 a,b,c,d,再使用压缩函数。所有这些完成之后，将 state0、state1、state2、state3分别加上 a、b、c、d。然后用下一分组数据继续运行算法。步骤步骤 3 ：对最后一组 filelengsub(long n) 和 filelen(long n)两个函数加长为 512 个字节,再用使用压缩函数，最后输出 state0,state1,state2,state3 的级取。最后结果如下图:4.3 MD5 算法在算法在 RSA 算法中的应用算法中的应用虽然用 RSA 加密后的文件不容易被人看懂，但是在传输中有没有被人篡改过就不能确定了。而 MD5 算法就可以确定这一点。MD5 算法是对文件中的每个字节做运算，只要对文件中的字节稍微做改动就会被发现。所以，MD5 算法和 RSA 算法结合在一起用，既能确保文件的保密性，又可以知道文件有没有被篡改。 学院理学学士学位论文 第四章 MD5 算法在 RSA 算法中的应用44步骤步骤 1 ：对加密前的文件做信息摘要，把摘要放在文件的后面。a161a87fcc579f670efdc6b41799c2f20 是文件的摘要。步骤步骤 2：对文件加密。密文如下：把光标前的 8 该成 7，如下图 ：步骤步骤 3 ：对文件解密。文件在传输的过程中被改过了，解密的文件如下 ：步骤步骤 4 ：检验文件是否被改过了。再对文件做 MD5 摘要。如下图 ： 学院理学学士学位论文 第四章 MD5 算法在 RSA 算法中的应用45解密后的文件的 MD5 摘要是 ：8b5adf75aacd4530823bf90ff05e413e。和原文 MD5的摘要不相同，说明文件在传输的过程中被人篡改了。MD5 是对文件的每个字符做运算，所以只要稍有改动摘要就不相同。这就是 MD5 摘要在加密算法中的作用。4.4 补充说明补充说明本次设计在实现 RSA 算法中，虽然可对单一文本进行加密解密和 MD5 信息摘要，但是还未实现对多个文本进行加密解密和 MD5 信息摘要，并且不能加密解密如 word 文档一些复杂形式的文本，因为 word 文档不像常规的文本文档如.txt 文档。在.txt 文档中，不对文字或者段落进行像 word 文档一样的规划排版，因为本次实验只实现了对文字进行加密解密，而没实现对文字字体、段落格式等数据进行加密解密。 学院理学学士学位论文 第四章 MD5 算法在 RSA 算法中的应用46参考文献参考文献1 eCool.MD5 算法研究./Articles/Program/Abstract/Arithmetic/MD5.htm.2 杨明等.密码编码学与网络安全：原理与实践（第二版）M . 电子工业出版社.2003-4. 学院理学学士学位论文 参考文献473 周玉洁 冯登国.公开密钥密码算法及其快速实现M.国防工业出版社.2002-9-1.4 卢开澄.计算机密码学-计算机网络中的数据保密与安全M.清华大学出版社.2003-12-1.5 蔡乐才.应用密码学M.中国电力出版社.2005-2.致致 谢谢 我要感谢我的指导老师赵丽萍，在她的指导下我才能顺利的完成我的工作。还要感谢机房的所以老师，在他们的监督下，使机房有个好的环境，让我们静心的学习。最后，我也感谢信息工程学院所有给我关怀和照顾的各位领导和老师。系领导和各位老师想方设法为我们提供良好的环境，并且为我们的毕业设计牺牲了大量的时间和精力。他们为我们良好地完成设计提供了保证。 学院理学学士学位论文 致谢48这次的毕业设计凝聚了导师和所以老师的心血。他们在百忙中指导我，给我相关的资料，并仔细的审阅了全部论文。这半个学期里，在老师带领下，我顺利的完成了我的毕业课题，我要对所有参与答辩工作的老师表示深深的感谢。附录 1 ： 学院理学学士学位论文 Appendix 49APPENDIXRSA 算法Key Generation Algorithm1. Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits. 2. Compute n = pq and () phi = (p-1)(q-1). 3. Choose an integer e, 1 e phi, such that gcd(e, phi) = 1.4. Compute the secret exponent d, 1 d phi, such that ed 1 (mod phi). The public key is (n, e) and the private key is (n, d). The values of p, q, and phi should also be kept secret. n is known as the modulus. e is known as the public exponent or encryption exponent. d is known as the secret exponent or decryption exponent.Summary of RSAn = pq where p and q are distinct primes. phi, = (p-1)(q-1) e n such that gcd(e, phi)=1 d = e-1 mod phi. c = me mod n. m = cd mod n. A very simple example of RSA encryptionThis is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 can probably even do it by hand on paper). Select primes p=11, q=3. n = pq = 11*3 = 33 学院理学学士学位论文 Appendix 50phi = (p-1)(q-1) = 10*2 = 20 Choose e=3Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),and check gcd(e, q-1) = gcd(3, 2) = 1therefore gcd(e, phi) = gcd(e, (p-1)(q-1) = gcd(3, 20) = 1 Compute d such that ed 1 (mod phi)i.e. compute d = e(-1) mod phi = 3(-1) mod 20i.e. find a value for d such that phi divides (ed=1)i.e. find d such that 20 divides 3d-1.Simple testing (d = 1, 2, .) gives d = 7Check: ed-1 = 3*7 - 1 = 20, which is divisible by phi. Public key = (n, e) = (33, 3)Private key = (n, d) = (33, 7). This is actually the smallest possible value for the modulus n for which the RSA algorithm works. Now say we want to encrypt the message m = 7,c = me mod n = 73 mod 33 = 343 mod 33 = 13.Hence the ciphertext c = 13. To check decryption we computem = cd mod n = 137 mod 33 = 7. Note that we dont have to calculate the full value of 13 to the power 7 here. We can make use of the fact that a = bc mod n = (b mod n).(c mod n) mod n so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the finalvalue. One way of calculating m is as follows:-m = 137 mod 33 = 13(3+3+1) mod 33 = 133.133.13 mod 33= (133 mod 33).(133 mod 33).(13 mod 33) mod 33= (2197 mod 33).(2197 mod 33).(13 mod 33) mod 33= 19*19*13 mod 33 = 4693 mod 33= 7. 学院理学学士学位论文 Appendix 51Now if we calculate the ciphertext c for all the possible values of m (0 to 32), we get m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16c 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32c 29 24 28 14 21 22
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号