数字加密技术-计算机毕业设计

学院理学学士学位论文

RSA加密算法和信息摘要

摘要

在这个信息爆炸的时代，随著电脑通信与网络的日渐普及，数据传输的平安性愈发受到重视，密码学已成为一个相当重要的课题。在密码系统中，主要可分成私有密钥系统与公开密钥系统。在公开密钥系统中，RSA密码系统是最有名也是最普及的密码系统。根本上，RSA密码系统是由高位元数的模乘法运算以及模指数运算所组成。由于其运算复杂度相当高，想要破解公开密钥以便得到私密密钥是相当困难的事。

随著通信传播上的蓬勃开展，使得互联网越来越受到欢送，以致于，对于类似电子商务的效劳，网络上平安的问题成为主要考虑的课题。而其根本上的平安需求，包含有隐密性，可认证性，数据的完整性和不可否认性。为了提供上述的平安效劳，大多的网络系统使用公开密钥密码系统。而RSA密码系统和MD5信息摘要算法结合可以确保数据的完整性。关键词：公开密钥系统，公钥，私钥，RSA密码系统，MD5信息摘要。Abstract

Withtheincreasingpopularityofelectroniccommunications,datasecurityisbecomingamoreandmoreimportantissue.Therearetwomaintypesofcryptosystems.Oneisprivate-keycryptosystem,andtheotherispublic-keycryptosystem.Themostfamousandpopularpublic-keycryptosystemisRSAscheme.RSAschemeiscomposedoflargebit-lengthmodularmultiplicationandmodularexponentiationinprinciple.Becauseofthehighcomplexityofmodularexponentiation,itisverydifficulttofactoritandobtaintheprivate-keyfromthepublic-key.

AsthetelecommunicationnetworkhasgrownexplosivelyandtheInternethasbecomeincreasinglypopular,securityoverthenetworkisthemainconcernforfurtherserviceslikeelectroniccommerce.Thefundamentalsecurityrequirementsincludeconfidentiality,authentication,dataintegrity,andnonrepudiation.Toprovidesuchsecurityservices,mostsystemsusepublickeycryptography.UseRSAschemeandTheMD5message-digestalgorithmtogether,itmakessuredataintegrityinthetekecommunicationnetwork.Key

Word

:PublicKeycryptography,

PublicKey,

PrivateKey,

RSA,MD5message-digest.目录摘要 IAbstract II目录 III第一章RSA公钥密码简介 11.1公开密钥密码系统 11.2RSA加密算法 21.3RSA公钥密码的平安 5第二章RSA加密算法的有关数学知识 72.1数论 72.1.1模运算 7素数 7最大公因子 9幂模运算 112.1.5乘法逆元 132.2RSA中重要定理 152.2.1费马定理 152.2.2欧拉定理 162.2.3欧几里德算法 19第三章MD5算法简介 243.1MD5算法的开展史 243.2MD5算法的应用 253.3MD5算法描述 263.3.1MD5算法的步骤 263.3.2MD5的压缩函数 333.4MD5算法的平安 38第四章MD5算法在RSA算法中应用 394.1RSA算法加密文件 394.1.1加密过程 394.1.2解密过程 404.2文件的信息摘要 434.3MD5算法在RSA算法中的应用 444.4补充说明 45参考文献 47致谢 48APPENDIX 49文献报告 53第一章RSA公钥密码简介1.1公开密钥密码系统一个好的加密算法的重要特点之一是具有这种能力：可以指定一个密码或密钥，并用它来加密明文，不同的密码或密钥产生不同的密文。这又分为两种方式：对称密钥算法和非对称密钥算法。所谓对称密钥算法就是加密解密都使用相同的密钥，非对称密钥算法就是加密解密使用不同的密钥。非常著名的pgp公钥加密以及RSA加密方法都是非对称加密算法。加密密钥，即公钥，与解密密钥，即私钥，是非常的不同的。从数学理论上讲，几乎没有真正不可逆的算法存在。公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向〞一文中提出的。他是用一个密钥进行加密，而用另一个不同但是有关的密钥进行解密。图给出了公开密钥加密过程。其中重要步骤如下：网络中的每个端系统都产生一对用于它将接收的报文进行加密和解密的密钥。每个系统都通过把自己的加密密钥放进一个登记或者文件来公布告它，这就是公开密钥。另一个密钥那么是私有的。如果A想给B发送一个报瘪他就用B的公开密钥加密这个报文。B收到这个报文后就用他的保密密钥解密报文。其他所有收到这个报文的人都无法解密它，因为只有B才有B的私有密钥。图加密过程非对称密钥算法RSA算法于1977年由美国麻省理工学院MIT(MessachusettsInstituteofTechnology)的RonalRivest,AdiShamir和LenAdleman三位年轻教授提出，并以三人的姓氏Rivest,shamir和Adlernan命名为RSA算法。该算法利用了数论领域的一个事实，那就是虽然把两大质数相乘生成一个合数是件十分容易的事情，但是把一个合数分解为两个质数却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。RSA算法无须收发双方同时参与加密过程，且非常适合于电子函数系统的加密。1.2RSA加密算法RSA算法可以表述如下：密钥配制。假设m是想要传送的报文，现任选两个很大的质数p与q，使得：选择正整数e,使得e与互质,且e小于；再利用相除法，求得d,使得到：这里表示n=q*p,其中xmody是整数求模运算，其结果是x整除以y后剩余的余数，如果5mod3=2。所以密钥是：(e,n)，是用于加密的公共密钥，可以公开出去；而(d,n)是用于解密的专用钥匙，必须保密。用VC++求的RSA加密解密参数和密钥是：结果分析是：由上图得知，公钥是{931,1067},私钥是{331，1067}。加密过程。使用(e,n)对明文m进行加密得到密文c，算法为：c=memodn.加密结果为：使明文变成了不能读的密文。解密过程。使用(d,n)对密文c进行解密，算法为：m=cemodn求得的m是对应于密文c的明文。解密结果为：解密的结果是使密文变成原文。RSA公共密钥加密算法的核心是欧拉(Euler)函数。对于正整数n,定义为小于n且与n互素的正整数的个数。例如=2，这是因为小于6且与6互素的数有1和5共两个数。欧拉定义有两个重要性质：性质1：如果p是质数，那么：性质2：如果p与q均为互质数，那么：RSA算法正是注意到这两条性质设计公共密钥系统的，p与q的乘积n可以说作为公共密钥公布出来，而n的因子p与q那么包在专用密钥中，可以用来解密。如果解密需要用到接收方由于知道因子p和q，可以方便地算出：如果窃听得了n，但由于不知道它的因子p与q，那么很难求出。这时，窃听者要么强行算出，要么对n进行因数分解求得p与q。然而，我们知道，在大数范围内作合数分解是十分困难的，困此窃听者很难成功。1.3RSA公钥密码的平安RSA的平安性完全依赖于大数分解问题只是一个推测，目前，还未能从理论上证明由c和e计算出m一定需要分解n。还不能证明对RSA攻击的难度和分解n的难度相当，但也没有比因式分解n更好的攻击方法。n，求得〔的欧拉函数〕，那么p和q可以求得。因为根据欧拉定理：据此列出方程，求得p和q。然而，如果新方法能使密码分析者推算出d,它也就成为大数分解的一个新方法。通过猜想的值，可以攻击RSA，但这种方法并不比分解n容易。分解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的平安性不能仅靠密钥的长度来保证。在RSA算法中，还有一种值得注意的现象，那就是存在一些，使得待加密消息经过假设干次RSA变换后就会恢复成原文。这不能不说是RSA本身具有的一个缺点，选择密钥时必须注意防止这种数。第二章RSA加密算法的有关数学知识2.1数论本节主要介绍RSA算法所用到的数论事实。模运算定义：给定一个整数n，如果用n去除两个整数a和b所得的余数相同，那么称a和b关于模n同余，记为ab(modn)。从0到处n–1的整数a，它的模n剩余是从0到n–1之间的某个整数。运算amodn表示a被n除的剩余，称为模n运算。例如，8mod5=3。模算术同普通的算术一样，是可交换的、可结合的和可分配的。而且，模n运算的每一个中间结果，与先进行全部运算，再对最后的结果模n，其作用是一样的。模运算的性质如下(a+b)modn=((amodn)+(bmodn))modn(a-b)modn=((amodn)-(bmodn))modn(a*b)modn=(amodn)*(bmodn)modna(b+c)modn=((abmodn)+(acmodn))modn密钥学中用了很多有关模的运算，因为像计算离散对数和模n平方根这样的问题是困难的。模运算也很容易在计算机上实现，因为它将所有中间值和最后结果限制在一个范围内。对一个k特的模n，任何加、减或乘的中间结果都不会超过2k比特长。因此我们可以用模算术做指数运算而又不会产生巨大的中间结果。素数数论研究的重点是素数。素数是指一个大于1且因子只有1和它本身的整数。除此之外没有其他数可以整除它。2是一个素数学，其他素数如79，2821，236537734359等。素数有无限多。密码学，特别是公钥密码学，使用大素数学。用VC++来判断素数为：voidCRsaMY::OnButtonRandom()//随机产生P，Q，N，D，E{ //TODO:Addyourcontrolnotificationhandlercodehere longq,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); CStringsetstr; srand((unsigned)time(NULL));strat0: p=rand(); if(!sushu(p)||p>200) gotostrat0; else m_p=p;//产生密钥参数P strat1: q=rand(); if(!sushu(q)||q>200) gotostrat1; else m_q=q;//产生密钥参数Q if(!dengch(p,q)||abs(q-p)<50)gotostrat0; fn=(q-1)*(p-1); n=p*q; strat2: e=rand(); if(gcd(e,fn)==1&&e>1&&e<fn) { m_e=e; d=euclib(e,fn); if(d<1||!sushu(d)) gotostrat2; } else gotostrat2;//产生私有密钥e fm_d=d; fm_e=e; fm_n=n;//初始化全局变量 m_d=d; m_n=n; UpdateData(false);}结果分析：由于产生的随机数的速度比拟慢，所以在加密解密产生的密钥小一点儿，这样加密解密过程也快一点儿。最大公因子符号gcd(a,b)用作表示a和b的最大公因子。正整数c是a和b的最大公因子，如果满足以下条件[2]：c是a和b的因子任何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|。如果将两个整数分别表示为素数的乘积，那么很容易确定它们的最大公因子。例如：gcd(18,300)=如果有两个数，它们除此而外之外没有他共同的因子，那么称这两个数是互素的。换言之，如果整数a和n的最大公因子(gcd())等于1，那么认为a和b互素，即：gcd(a,b)=1如15和28，13和500是互素的，而15和27不是。一个素数与它的倍数以外的任何的其他数都是互素的。计算两个数的最大公因子最容易的方法是古老的欧几里德〔Euclidean〕算法。算法：计算最大公因子的Euclidean算法输入：整数x,y。输出：gcd(x,y)。如果x<0,那么x-x。如果y<0，那么y-y。gy。当x>0,执行：a:gx;b:xymodx;c:yg.(5)返回g。上述方法可求得最大公因子。用VC++描述为：longCRsaMY::gcd(longx,longy)//最大公因子{ longg; g=y;while(x>0) { g=x; x=y%x; y=g; } returng;}g是x,y的最大公因子。结果分析：当g=1时，

x和y是互素的，用这个函数来判断两个数是否互素。幂模运算RSA加、解密变换都要进行xrmodn的幂运算。求(modp)可通过对指数r的二进制数化来实现。例如求(mod17),7=，即7=故：mod17=**11(mod17)下面给出一种比拟实用的方法。在此前，先通过实例观察运算的计算步骤。P=(mod2537)=(mod2537)=(mod2537)其中：(欧拉定理，将在下一节介绍)因此：p=而：因此：=而：现在模拟这个过程给出计算流程如以下图所示：例如：求〔1〕〔2〕〔3〕〔4〕〔5〕，〔6〕〔7〕〔8〕〔9〕因为所以不过，这里还存在问题，因为a，b，c都很小我们不能发现问题。现在我们拿大一些的做运算，实际结果如下：(49022*49022)mod61771=2403156484mod61771=17500但是用计算机计算的结果如下：(49022*49022)mod61771=2403156484mod61771=-14260这是因为2403156484已经溢出了长整数的范围，得到的结果是未知的。我们用乘法性质和模性质做特殊处理。乘法性质：49022*words[i]*其中：words[i]={2，2，0，9，4}，i是49022的位数。再利用模的性质：(a+b)modn=((amodn)+(bmodn))modn(a*b)modn=(amodn)*(bmodn)modn尽可以把a*c，a*a的范围缩的很小。这样中间结果就不会超出整数范围。乘法逆元如果[1]，那么如果a与n互素例如：为了说明这一点，考虑一个附加条件不满足的例子：6×3＝186×7＝42但。造成这个奇怪结果的原因是对于乘数a，模n的乘法运算返回的结果是0到n-1之间的数，如果a和n有除1以外的共同因子时将不会产生完整的余数集合。例如：取a=6和n=8；因为乘以6的模8运算不会产生完整的余数集．中的多个数将映射到同一个余数上。如：因为这是一个多对一的映射，对乘法运算不存在惟一的逆元。然而，如果取a=5,n=8：余数行以不同的顺序包含了集合中所有的数。最后，还可观察到如果P是一个素数．那么集合中的所有数均与p互素

。这样就能在之前所列的性质中再加上一条性质：乘法逆元()对每一个，存在一个z，使得因为与P互素，如果用乘以中的所有数模P，得到的余数将以不同次序涵盖中的所有数。那么，至少有一个余数的值为1。因此，在中的某个数与相乘模p的余数为1。这个数就是的乘法逆元，命名为。这样．等式：与存在乘法逆元是一致的。对上等式的两边乘以a的乘法逆元，有：最后一点：某些整数但不是全部整数存在一个乘法逆元就将使模数不是一个素数。如果如gcd(a,n)=1，那么能在中找到b，使得：原因与前一段是相同的。因为a与n互素，如果用a与中的所有数相乘模n，得到的余数将以不同次序涵盖中的所有数。因此在中存在某个数b，使得：2.2RSA中重要定理费马定理费马定理可表述为：如果p是素数，a是个不能被p整除的正整数，那么：证明[1]：从以前的讨论得出，如果中的所有数均与a相乘模p，结果将以某种次序涵盖中的数。并且：因此，(p—1)个数：}恰好是某种次序的{1,2,…,(p-1)}。将这些数相乘可得：但：因此可在两端去掉(p-1)!，因为它与p互素，这可以得到费马定理。例如：a=7,p=19费马定理的另一种等价形式也很有用：如果p是素数,a是任意正整数，那么：欧拉定理在引入欧拉定理之前，需首先介绍数论中的一个重要的量，即欧拉函数(Euler’stotientfunction),记为，表示小于n的且与n互素的正整数个数。例如；下表列出了30以内的整数的值，被定义为1，但没有实际意义。某些欧拉函数的值很显然，对于一个素数p，有：现假定有两个不同的素数p和q，那么对n=q*p，有：为了证明这一命题[1]，考虑的完全余数集为：{0,1,2,…,(pq-1)}而不与n互素的余数包括0和集合{p,2p,…,(q-1)p}{q,2q,…,(p-1)1}因此，有：欧拉定理可表述为对于任何互素的整数a和n，有：例如：a=3;n=10;=4;证明：如果n为素数，那么等式为真，因为此时根据费马定理可证。然而，对于其他任意整数，它也成文：表示不小于n且与n互素的正整数个数，假定这样的整数集合标记如下：现在对该集合中的每个整数乘以a模n：集合s是集合R的—个置换，原因如下：1.因为a与n互素，也与n互素，那么一定与n互素。因此，S中的所有数均小于n且与n互素。2.有s个不存在重复的整数。根据等式：如果，那么如果a与n互素如果：那么：。因此：欧拉定理的另一种等价形式也很有用：欧拉定理的推论在说明RSA算法的有效时是很有用的。给定两个素数p和q，以及整数n=p*q和m,其中0<m<n，那么下面关系成立：如果如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<p*q。如果gcd(m，q)=1，那么根据欧拉定理并且：但根据模运算的规那么，有：因此，存在某个整数k使得：在等式两边同乘m＝cp，有：m是q的倍数的情况也可采用类似的方法得出，故等式：得证。这个推论的另一等价形式也很有用。欧几里德算法欧几里德算法是数论中的一项根本技术，它通过简单的过程来确定两个正整数的最大公因子。扩展的欧几里德算法不仅能确定两个正整数的最大公出于，如果这两个数互素，还能确定它们各自的乘法逆元。欧几里德算法基于下面的定理[1]：对任何非负整数a和非负整数b例如：证明[1]：假定d。根据的定义，有和。对任何正整数b，a可表示为如下形式：因此，有：其中k为某个整数。但由于，b也能整除kb，而，故有：这说明d也是b和的公因子。由于这是可逆的，如果d是b和的公因子，那么，且，这等同于。这样a和b的公因子集合等同于b和的公因子集合。因此它们的最大公因子相同。定理得证。可重复使用等式：来求出最大公因子。例如：下面的欧几里德算法重复使用等式：来求出最大公因子。算法假定。限制算法仅考虑正整数是可以接受的，因为：EUCLID(d,f)，即d和f的最大公因子例如：1)2)ifreturn3)4)5)6)goto2要找出因此：我们会发现这个过程是在中时停止的〔为正整数〕，即如何确定在某一点上整除?如果不能，这就将得到一个无穷尽的正整数序列，序列中每一个均比前面的整数小，这显然是不可能的。如果：那么d有一个模f的乘法逆元。即对小于f的正整数d，存在一个小于f的整数，使得：对欧几里德算法进行扩展使得它不仅能找出，如果，算法还能返回d的乘法逆元。EXTENDEDEUCLIB(d,f)(语言描写)1)2)ifreturn；无逆元3)ifreturn；4)5)6)7)8)goto2VC++的描述：longCRsaMY::euclib(longx,longy)//求乘法逆元，或者私钥，扩展欧几里德算法{ longx1,x2,x3; longy1,y2,y3; longt1,t2,t3; longm,d;x1=1;x2=0;x3=y; y1=0;y2=1;y3=x; if(gcd(x,y)==1) { while(y3!=1){m=x3/y3;t1=x1-m*y1;t2=x2-m*y2;t3=x3-m*y3;x1=y1;x2=y2;x3=y3;y1=t1;y2=t2;y3=t3; } } d=y2;if(d>0) returnd; elsereturnd=y+d;}结果分析：d是要求的私钥。通过计算，厂面的关系成立：下面说明算法能正确返回。如果将欧几里德算法中的和看作是扩展欧几里德算法中的和，那么这两个变量的处理是完全相同的。在欧几里德算法的每次迭代中，被设置为前一个值，而被设置为前一个。同样．在扩展的欧几里德算法中，x3被设置为前一个值，而被设置为前一个减大除以的商，后一个数即为除以所得的余数，然后再乘以，也就是。另外，如果，那么最后一个步骤可得=0且=1。因此在之前的步骤中有。但如果＝1，那么有：并且是d模f的乘法逆元。例如：下表是扩展欧几里德算法执行的一个例子。算法显示：且550模1769的乘法逆元就是其本身；即：扩展的Euclib(550,1769)第三章MD5算法简介3.1MD5算法的开展史MD5[1]的全称是message-digestalgorithm5〔信息-摘要算法〕，在90年代初由mitaboratoryforcomputerscience和rsadatasecurityinc的ronaldl.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整除〔信息字节长度mod512=448〕。然后，一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位迭代结构的模块，而且每个模块要通过三个不同步骤的处理。denboer和bosselaers以及其他人很快的发现了攻击md4版本中第一步和第三步的漏洞。dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到md4完整版本中的冲突〔这个冲突实际上是一种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密后结果〕。毫无疑问，md4就此被淘汰掉了。尽管md4算法在平安上有个这么大的漏洞，但它对在其后才被开发出来的好几种信息平安加密算法的出现却有着不可无视的引导作用。除了md5以外，其中比拟有名的还有sha-1、ripe-md以及haval等。一年以后，即1991年，rivest开发出技术上更为趋近成熟的md5算法。它在md4的根底上增加了"平安-带子"〔safety-belts〕的概念。虽然md5比md4稍微慢一些，但却更为平安。这个算法很明显的由四个和md4设计有少许不同的步骤组成。在md5算法中，信息-摘要的大小和填充的必要条件与md4完全相同。denboer和bosselaers曾发现md5算法中的假冲突〔pseudo-collisions〕，但除此之外就没有其他被发现的加密后结果了。vanoorschot和wiener曾经考虑过一个在散列值中暴力搜寻冲突的函数〔brute-forcehashfunction〕，而且他们猜想一个被设计专门用来搜索md5冲突的机器〔这台机器在1994年的制造本钱大约是一百万美元〕可以平均每24天就找到一个冲突。但单从1991年到2001年这10年间，竟没有出现替代md5算法的md6或被叫做其他什么名字的新算法这一点，我们就可以看出这个瑕疵并没有太多的影响md5的平安性。上面所有这些都缺乏以成为md5的在实际应用中的问题。并且，由于md5算法的使用不需要支付任何版权费用的，所以在一般的情况下(非绝密应用领域。但即便是应用在绝密领域内，md5也不失为一种非常优秀的中间技术)，md5怎么都应该算得上是非常平安的了。3.2MD5算法的应用MD5的全称是Message-DigestAlgorithm5.Message-Digest泛指字节串(Message)的Hash变换，就是把一个任意长度的字节串变换成一定长的大整数。请注意我使用了“字节串〞而不是“字符串〞这个词，是因为这种变换只与字节的值有关，与字符集或编码方式无关。MD5将任意长度的“字节串〞变换成一个128bit的大整数，并且它是一个不可逆的字符串变换算法，换句话说就是，即使你看到源程序和算法描述，也无法将一个MD5的值变换回原始的字符串，在数学原理上，是因为原始的字符串有无穷多个，这有点像不存在反函数的数学函数。MD5的典型应用是对一段Message(字节串)产生fingerprint(指纹)，以防止被“篡改〞。举个例子，你将一段话写在一个叫readmem.txt文件中，并对这个readmem.txt产生一个MD5的值并记录在案，然后你可以传播这个文件给别人，别人如果修改了文件中的任何内容，你对这个文件重新计算MD5时就会发现。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的“抵赖〞，这就是所谓的数字签名应用。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是一种最常用的根本功能，尽管很多ApplicationServer提供了这些根本组件，但很多应用开发者为了管理的更大的灵活性还是喜欢采用关系数据库来管理用户，懒惰的做法是用户的密码往往使用明文或简单的变换后直接保存在数据库中，因此这些用户的密码对软件开发者或系统管理员来说可以说毫无保密可言，本文的目的是介绍MD5的JavaBean的实现，同时给出用MD5来处理用户的Account密码的例子，这种方法使得管理员和程序设计者都无法看到用户的密码，尽管他们可以初始化它们。但重要的一点是对于用户密码设置习惯的保护。3.3MD5算法描述MD5算法的步骤该算法以一个任意长度的报文作为输入，产生—个128bit的报文摘要作为输出。输入是按512bit的分组进行处理的。图描述了处理报文产生摘要的总的过程。处理操作包括以下几步：步骤1：附加填充比持。对报文进行填充使报文的长度(比特数)与448模512同余(长度)。即填充长度为512的整数倍减去64。例如，如果报文是448bit长，那么将填充512bit形成960bit的报文。填充比特串的最高位为1，其余各位均为0。步骤2：附加长度值。将用64bit表示的初始报文(填充前)的位长度附加在步骤1的结果后(低位字节优先)。如果初始长度大于，仅使用该长度的低64bit。这样，该区域所包含的长度值为初始报文长度模的值。这两步的结果将产生一个长度为512整数倍比特的报文。在图中，经扩展的报文表示成512bit的分组序列，因此扩展的报文长度等于。与之等价的是，该结果也等于字长为16bit或32bit的整数倍。让表示扩展报文包含的字数，其中N是16的整数倍。因此，N=。图使用MD5产生摘要的过程步骤3：初始化MD缓存。使用一个128bit的缓存来存放该散列函数的中间及最终结果。该缓存可表示为4个32bit的存放器(state0，state1，state2，state3)。这些存放器被初始化为如下32bit长的整数(十六进制表示)：state0:0x01234567state1:0x89abcdefstate2:0xfedcba98state3:0x76543210这些值以小数次序的格式存储，即字的低位字节放在低地址字节上。像32bit的串，初始化的值(十六进制表示)以如下方式存储：字state0：0l234567字state1；89abcdef字state2：fedcba98字state3：765432l0步骤4：处理512bit(16个字)报文分组序列。算法的核心是一个包含4个“循环〞的压缩函数；这个模块在上图中标识为HMD5，说明了它的逻辑。4个循环有相似的结构，但每次循环使用不同的原始逻辑函数，在说明中分别表示为F，G，H和I。它们的定义如下：CMDHash::f(DWORDx,DWORDy,DWORDz)//第一个非线性运算函数{return((x&y)|((~x)&z));}CMDHash::g(DWORDx,DWORDy,DWORDz)//第二个非线性运算函数{ return((x&y)|(y&(~z)));}CMDHash::h(DWORDx,DWORDy,DWORDz)//第三个非线性运算函数{ return(x^y^z);}CMDHash::i(DWORDx,DWORDy,DWORDz)//第四个非线性运算函数{return(y^(x|(~z)));}每一循环都以当前的正在处理的512bit分组()和128bit的缓存值state0,state1,state2,state3为输人，然后更新缓存的内容。每一循环还使用一个64元素表的四分之一，该表通过正弦函数构建。T的第i个元素(表示为)的值等于的整数局部值．其中i的单位是弧度。因为是0到l之间的数．因此每个T中的元素值均能用32bit表示。这个表提供了一个“随机化〞的32bit模式集，它将消除输入数据的任何规律性。表列出了T的所有值。第4次循环的输出加到第1次循环的输入()上产生。相加是缓存中4个字分别与中对应的4个字以模相加。图单位个512bit分组的MD5处理系统过程表逻辑函数的真值表表由整弦函数构造的表T步骤5：输出L所有L个512bit的分组处理完成后，第L阶段产生的输出便是128比的报文摘要。以上用VC++描述为了：实现步骤1的函数是filelengsub(intn)CStringCMDHash::filelengsub(intn)//n为字符串的长度余数418，0=<n<512{ CStringgetstr,stringlen=""; inti=1; inta; while(n!=448) { if(i==1) { a=1; getstr.Format("%d",a); stringlen=getstr; i++; }else{ a=0; getstr.Format("%d",a); stringlen=stringlen+getstr; } n++; if(n>448&&n==512) n=0; } i=1; getstr.Empty(); returnstringlen;//先填充这个，再填充64位}结果如上图：〔字符串是：nihaoni不覆在za〕结果分析：字符串的长度为15，15%512=15，所以在字符串后要加1个1和432个0。实现步骤2的函数是filelen(longn)CStringCMDHash::filelen(longn)//64位二进制表示的填充前信息长度{ inti=0; inta[64],g[64]; while(n!=0) { a[i++]=n%2; n=n/2; }//求文件长度的二进制数 a[i]=1; intk=i; intk1=k-1; for(i=0;i<k;i++) g[k1--]=a[i];//文件长度值的二进制表示 CStringgetstr,fileleng=""; for(i=0;i<64-k;i++) { inta=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(); returnfileleng;//返回长度为64的字符串}结果加以下图:〔字符串是：nihaoni不覆在za〕结果分析：15的二进制表示为1111，在其高位要加60个0。步骤1和2使原字符串的长度变为nmod512=448.MD5的压缩函数现在了解四次循环处理一个512bit分组中64次循环的逻辑。每一循环由对缓存数state0,state1,state2,state3的16步操作组成。每一步操作的形式为：其中：a=state0;b=state1;c=state2;d=state3;a,b,c,d缓存中的4个字，在不同步骤中有指明的顺序<<s是32bit参数循环左移(旋转)s个比特是第g个长度为512bit报文分组中的第k个32bit字是矩阵T中的第i个32bit字+＝模加法图说明这个步骤的操作。在每—步中，四个字(a,b,c,d)被用来产生字级别的循环右移以更新这些字的内容。图根本的MD5操作用VC++描述压缩函数：voidCMDHash::round4(CStrings,intn)//n是处理后的字符或文件的长度,s为文件或字符{ DWORDa,b,c,d; a=state0;//state0,state1,state2,state3的入口 b=state1; c=state2; d=state3; DWORDx[16]; intm=n/16; for(intj=0;j<m;j++)//s是字符串,其长度为N=L*512,q=0toN/16-1; { for(inti=0;i<16;i++) x[i]=(unsignedlong)s[j*16+i];/*round1*/ a=ff(a,b,c,d,x[0],7,0xd76aa478); d=ff(d,a,b,c,x[1],12,0xe8c7b756); c=ff(c,a,b,d,x[2],17,0x242070db); b=ff(b,a,c,d,x[3],22,0xc1bdceee); a=ff(a,b,c,d,x[4],7,0xf57c0faf); d=ff(d,a,b,c,x[5],12,0x4787c62a c=ff(c,a,b,d,x[6],17,0xa8304613); b=ff(b,a,c,d,x[7],22,0xfd469501); a=ff(a,b,c,d,x[8],7,0x698098d8); d=ff(d,a,b,c,x[9],12,0x8b44f7af); c=ff(c,a,b,d,x[10],17,0xffff5bb1); d=ff(d,a,c,d,x[11],22,0x895cd7be); a=ff(a,b,c,d,x[12],7,0x6b901122); d=ff(d,a,b,c,x[13],12,0xfd987193); c=ff(c,a,b,d,x[14],17,0xa679438e); b=ff(b,a,c,d,x[15],22,0x49b40821); /*round2*/ a=gg(a,b,c,d,x[1],5,0xf61e2562); d=gg(d,a,b,c,x[6],9,0xc040b340); c=gg(c,a,b,d,x[11],14,0x265e5a51); b=gg(b,a,c,d,x[0],20,0xe9b6c7aa); a=gg(a,b,c,d,x[5],5,0xd62f105d); d=gg(d,a,b,c,x[10],9,0x02441453); c=gg(c,a,b,d,x[15],14,0xd8a1e681); b=gg(b,a,c,d,x[4],20,0xe7d3fbc8); a=gg(a,b,c,d,x[9],5,0x21e1cde6); d=gg(d,a,b,c,x[14],9,0xc33707d6); c=gg(c,a,b,d,x[3],14,0xf4d50d87); b=gg(b,a,c,d,x[8],20,0x455a14ed); a=gg(a,b,c,d,x[13],5,0xa9e3e905); d=gg(d,a,b,c,x[2],9,0xfcefa3f8); c=gg(c,a,b,d,x[7],14,0x676f02d9); b=gg(b,a,c,d,x[12],20,0x8d2a4c /*round3*/ a=hh(a,b,c,d,x[5],4,0xfffa3942); d=hh(d,a,b,c,x[8],11,0x8771f681); c=hh(c,a,b,d,x[11],16,0x6d9d6122); b=hh(b,a,c,d,x[14],23,0xfde5380c); a=hh(a,b,c,d,x[1],4,0xa4beea44); d=hh(d,a,b,c,x[4],11,0x4bdecfa9); c=hh(c,a,b,d,x[7],16,0xf6bb4b60); b=hh(b,a,c,d,x[10],23,0xbebfbc70); a=hh(a,b,c,d,x[13],4,0x289b7ec6); d=hh(d,a,b,c,x[0],11,0xeaa127fa); c=hh(c,a,b,d,x[3],16,0xd4ef3085); b=hh(b,a,c,d,x[6],23,0x04881d05); a=hh(a,b,c,d,x[9],4,0xd9d4d039); d=hh(d,a,b,c,x[12],11,0xe6db99e5); c=hh(c,a,b,d,x[15],16,0x1fa27cf8); b=hh(b,a,c,d,x[2],23,0xc4ac5665); /