3个著名加密算法(MD5RSADES)的解析.doc

3个著名加密算法(MD5、RSA、DES)的解析 MD5的全称是Message-Digest Algorithm 5，在90年代初由MIT的计算机科学实验室和RSA Data Security Inc发明，经MD2、MD3和MD4发展而来。 MD5将任意长度的“字节串”变换成一个128bit的大整数，并且它是一个不可逆的字符串变换算法，换句话说就是，即使你看到源程序和算法描述，也无法将一个MD5的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个，这有点象不存在反函数的数学函数。 MD5的典型应用是对一段Message(字节串)产生fingerprint(指纹)，以防止被“篡改”。举个例子，你将一段话写在一个叫 readme.txt文件中，并对这个readme.txt产生一个MD5的值并记录在案，然后你可以传播这个文件给别人，别人如果修改了文件中的任何内容，你对这个文件重新计算MD5时就会发现。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的“抵赖”，这就是所谓的数字签名应用。 MD5还广泛用于加密和解密技术上，在很多操作系统中，用户的密码是以MD5值（或类似的其它算法）的方式保存的， 用户Login的时候，系统是把用户输入的密码计算成MD5值，然后再去和系统中保存的MD5值进行比较，而系统并不“知道”用户的密码是什么。RSA是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：RonRivest,AdiShamir和LeonardAdleman。但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。DES算法美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告。1977年1月，美国政府颁布：采纳IBM公司设计的方案作为非机密数据的正式数据加密标准（DES?DataEncryptionStandard）。1.加密算法之MD5算法在一些初始化处理后，MD5以512位分组来处理输入文本，每一分组又划分为16个32位子分组。算法的输出由四个32位分组组成，将它们级联形成一个128位散列值。首先填充消息使其长度恰好为一个比512位的倍数仅小64位的数。填充方法是附一个1在消息后面，后接所要求的多个0，然后在其后附上64位的消息长度（填充前）。这两步的作用是使消息长度恰好是512位的整数倍（算法的其余部分要求如此），同时确保不同的消息在填充后不相同。四个32位变量初始化为：A=001234567B=089abcdefC=0xfedcba98D=076543210它们称为链接变量（chainingvariable）接着进行算法的主循环，循环的次数是消息中512位消息分组的数目。将上面四个变量复制到别外的变量中：A到a，B到b，C到c，D到d。主循环有四轮（MD4只有三轮），每轮很相拟。第一轮进行16次操作。每次操作对a，b，c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a，b，c或d中之一。最后用该结果取代a，b，c或d中之一。以一下是每次操作中用到的四个非线性函数（每轮一个）。F(X,Y,Z)=(X&Y)|(X)&Z)G(X,Y,Z)=(X&Z)|(Y&(Z)H(X,Y,Z)=XYZI(X,Y,Z)=Y(X|(Z)(&是与,|是或,是非,是异或)这些函数是这样设计的：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。函数F是按逐位方式操作：如果X，那么Y，否则Z。函数H是逐位奇偶操作符。设Mj表示消息的第j个子分组（从0到15），s表示循环左移s位，则四种操作为：FF(a,b,c,d,Mj,s,ti)表示a=b+(a+(F(b,c,d)+Mj+ti)s)GG(a,b,c,d,Mj,s,ti)表示a=b+(a+(G(b,c,d)+Mj+ti)s)HH(a,b,c,d,Mj,s,ti)表示a=b+(a+(H(b,c,d)+Mj+ti)s)II(a,b,c,d,Mj,s,ti)表示a=b+(a+(I(b,c,d)+Mj+ti)s)这四轮（64步）是：第一轮FF(a,b,c,d,M0,7,0xd76aa478)FF(d,a,b,c,M1,12,0xe8c7b756)FF(c,d,a,b,M2,17,0242070db)FF(b,c,d,a,M3,22,0xc1bdceee)FF(a,b,c,d,M4,7,0xf57c0faf)FF(d,a,b,c,M5,12,04787c62a)FF(c,d,a,b,M6,17,0xa8304613)FF(b,c,d,a,M7,22,0xfd469501)FF(a,b,c,d,M8,7,0698098d8)FF(d,a,b,c,M9,12,08b44f7af)FF(c,d,a,b,M10,17,0xffff5bb1)FF(b,c,d,a,M11,22,0895cd7be)FF(a,b,c,d,M12,7,06b901122)FF(d,a,b,c,M13,12,0xfd987193)FF(c,d,a,b,M14,17,0xa679438e)FF(b,c,d,a,M15,22,049b40821)第二轮GG(a,b,c,d,M1,5,0xf61e2562)GG(d,a,b,c,M6,9,0xc040b340)GG(c,d,a,b,M11,14,0265e5a51)GG(b,c,d,a,M0,20,0xe9b6c7aa)GG(a,b,c,d,M5,5,0xd62f105d)GG(d,a,b,c,M10,9,002441453)GG(c,d,a,b,M15,14,0xd8a1e681)GG(b,c,d,a,M4,20,0xe7d3fbc8)GG(a,b,c,d,M9,5,021e1cde6)GG(d,a,b,c,M14,9,0xc33707d6)GG(c,d,a,b,M3,14,0xf4d50d87)GG(b,c,d,a,M8,20,0455a14ed)GG(a,b,c,d,M13,5,0xa9e3e905)GG(d,a,b,c,M2,9,0xfcefa3f8)GG(c,d,a,b,M7,14,0676f02d9)GG(b,c,d,a,M12,20,08d2a4c8a)第三轮HH(a,b,c,d,M5,4,0xfffa3942)HH(d,a,b,c,M8,11,08771f681)HH(c,d,a,b,M11,16,06d9d6122)HH(b,c,d,a,M14,23,0xfde5380c)HH(a,b,c,d,M1,4,0xa4beea44)HH(d,a,b,c,M4,11,04bdecfa9)HH(c,d,a,b,M7,16,0xf6bb4b60)HH(b,c,d,a,M10,23,0xbebfbc70)HH(a,b,c,d,M13,4,0289b7ec6)HH(d,a,b,c,M0,11,0xeaa127fa)HH(c,d,a,b,M3,16,0xd4ef3085)HH(b,c,d,a,M6,23,004881d05)HH(a,b,c,d,M9,4,0xd9d4d039)HH(d,a,b,c,M12,11,0xe6db99e5)HH(c,d,a,b,M15,16,01fa27cf8)HH(b,c,d,a,M2,23,0xc4ac5665)第四轮II(a,b,c,d,M0,6,0xf4292244)II(d,a,b,c,M7,10,0432aff97)II(c,d,a,b,M14,15,0xab9423a7)II(b,c,d,a,M5,21,0xfc93a039)II(a,b,c,d,M12,6,0655b59c3)II(d,a,b,c,M3,10,08f0ccc92)II(c,d,a,b,M10,15,0xffeff47d)II(b,c,d,a,M1,21,085845dd1)II(a,b,c,d,M8,6,06fa87e4f)II(d,a,b,c,M15,10,0xfe2ce6e0)II(c,d,a,b,M6,15,0xa3014314)II(b,c,d,a,M13,21,04e0811a1)II(a,b,c,d,M4,6,0xf7537e82)II(d,a,b,c,M11,10,0xbd3af235)II(c,d,a,b,M2,15,02ad7d2bb)II(b,c,d,a,M9,21,0xeb86d391)常数ti可以如下选择：在第i步中，ti是4294967296*abs(sin(i)的整数部分,i的单位是弧度。(2的32次方)所有这些完成之后，将A，B，C，D分别加上a，b，c，d。然后用下一分组数据继续运行算法，最后的输出是A，B，C和D的级联。MD5的安全性MD5相对MD4所作的改进：1.增加了第四轮.2.每一步均有唯一的加法常数.3.为减弱第二轮中函数G的对称性从(X&Y)|(X&Z)|(Y&Z)变为(X&Z)|(Y&(Z)4.第一步加上了上一步的结果,这将引起更快的雪崩效应.5.改变了第二轮和第三轮中访问消息子分组的次序,使其更不相似.6.近似优化了每一轮中的循环左移位移量以实现更快的雪崩效应.各轮的位移量互不相同.2.加密算法之RSA算法它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：RonRivest,AdiShamir和LeonardAdleman。但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。一、RSA算法:首先,找出三个数,p,q,r,其中p,q是两个相异的质数,r是与(p-1)(q-1)互质的数p,q,r这三个数便是privatekey接著,找出m,使得rm=1mod(p-1)(q-1).这个m一定存在,因为r与(p-1)(q-1)互质,用辗转相除法就可以得到了.再来,计算n=pq.m,n这两个数便是publickey编码过程是,若资料为a,将其看成是一个大整数,假设a=n的话,就将a表成s进位(s=n,通常取s=2t),则每一位数均小於n,然後分段编码接下来,计算b=ammodn,(0=bn),b就是编码後的资料解码的过程是,计算c=brmodpq(0=cpq),於是乎,解码完毕等会会证明c和a其实是相等的如果第三者进行窃听时,他会得到几个数:m,n(=pq),b他如果要解码的话,必须想办法得到r所以,他必须先对n作质因数分解要防止他分解,最有效的方法是找两个非常的大质数p,q,使第三者作因数分解时发生困难若p,q是相异质数,rm=1mod(p-1)(q-1),a是任意一个正整数,b=ammodpq,c=brmodpq,则c=amodpq证明的过程,会用到费马小定理,叙述如下:m是任一质数,n是任一整数,则nm=nmodm(换另一句话说,如果n和m互质,则n(m-1)=1modm)运用一些基本的群论的知识,就可以很容易地证出费马小定理的.因为rm=1mod(p-1)(q-1),所以rm=k(p-1)(q-1)+1,其中k是整数因为在modulo中是preserve乘法的(x=ymodzandu=vmodz=xu=yvmodz),所以,c=br=(am)r=a(rm)=a(k(p-1)(q-1)+1)modpq1.如果a不是p的倍数,也不是q的倍数时,则a(p-1)=1modp(费马小定理)=a(k(p-1)(q-1)=1modpa(q-1)=1modq(费马小定理)=a(k(p-1)(q-1)=1modq所以p,q均能整除a(k(p-1)(q-1)-1=pq|a(k(p-1)(q-1)-1即a(k(p-1)(q-1)=1modpq=c=a(k(p-1)(q-1)+1)=amodpq2.如果a是p的倍数,但不是q的倍数时,则a(q-1)=1modq(费马小定理)=a(k(p-1)(q-1)=1modq=c=a(k(p-1)(q-1)+1)=amodq=q|c-a因p|a=c=a(k(p-1)(q-1)+1)=0modp=p|c-a所以,pq|c-a=c=amodpq3.如果a是q的倍数,但不是p的倍数时,证明同上4.如果a同时是p和q的倍数时,则pq|a=c=a(k(p-1)(q-1)+1)=0modpq=pq|c-a=c=amodpqQ.E.D.这个定理说明a经过编码为b再经过解码为c时,a=cmodn(n=pq).但我们在做编码解码时,限制0=an,0=c：白云学院上网验证漏洞剖析（盗用IP免费上网大揭密）软件使用3MD5加密算法VB源代码 程序乐园 今天在在网页的源代码中找到了MD5加密算法的代码，呵呵，搬过来VB用了直接调用就可以了 使用例子msgbox md5(”加密的字符串”)Private Const BITS_TO_A_BYTE = 8Private Const BYTES_TO_A_WORD = 4Private Const BITS_TO_A_WORD = 32Private m_lOnBits(30)Private m_l2Power(30)Private Function LShift(lValue, iShiftBits)If iShiftBits = 0 ThenLShift = lValueExit FunctionElseIf iShiftBits = 31 ThenIf lValue And 1 ThenLShift = &H80000000ElseLShift = 0End IfExit FunctionElseIf iShiftBits 31 ThenErr.Raise 6End IfIf (lValue And m_l2Power(31 iShiftBits) ThenLShift = (lValue And m_lOnBits(31 (iShiftBits + 1) * m_l2Power(iShiftBits) or &H80000000ElseLShift = (lValue And m_lOnBits(31 iShiftBits) * m_l2Power(iShiftBits)End IfEnd FunctionPrivate Function RShift(lValue, iShiftBits)If iShiftBits = 0 ThenRShift = lValueExit FunctionElseIf iShiftBits = 31 ThenIf lValue And &H80000000 ThenRShift = 1ElseRShift = 0End IfExit FunctionElseIf iShiftBits 31 ThenErr.Raise 6End IfRShift = (lValue And &H7FFFFFFE) m_l2Power(iShiftBits)If (lValue And &H80000000) ThenRShift = (RShift or (&H40000000 m_l2Power(iShiftBits 1)End IfEnd FunctionPrivate Function RotateLeft(lValue, iShiftBits)RotateLeft = LShift(lValue, iShiftBits) or RShift(lValue, (32 iShiftBits)End FunctionPrivate Function AddUnsigned(lX, lY)Dim lX4Dim lY4Dim lX8Dim lY8Dim lResultlX8 = lX And &H80000000lY8 = lY And &H80000000lX4 = lX And &H40000000lY4 = lY And &H40000000lResult = (lX And &H3FFFFFFF) + (lY And &H3FFFFFFF)If lX4 And lY4 ThenlResult = lResult Xor &H80000000 Xor lX8 Xor lY8ElseIf lX4 or lY4 ThenIf lResult And &H40000000 ThenlResult = lResult Xor &HC0000000 Xor lX8 Xor lY8ElselResult = lResult Xor &H40000000 Xor lX8 Xor lY8End IfElselResult = lResult Xor lX8 Xor lY8End IfAddUnsigned = lResultEnd FunctionPrivate Function md5_F(x, y, z)md5_F = (x And y) or (Not x) And z)End FunctionPrivate Function md5_G(x, y, z)md5_G = (x And z) or (y And (Not z)End FunctionPrivate Function md5_H(x, y, z)md5_H = (x Xor y Xor z)End FunctionPrivate Function md5_I(x, y, z)md5_I = (y Xor (x or (Not z)End FunctionPrivate Sub md5_FF(a, b, c, d, x, s, ac)a = AddUnsigned(a, AddUnsigned(AddUnsigned(md5_F(b, c, d), x), ac)a = RotateLeft(a, s)a = AddUnsigned(a, b)End SubPrivate Sub md5_GG(a, b, c, d, x, s, ac)a = AddUnsigned(a, AddUnsigned(AddUnsigned(md5_G(b, c, d), x), ac)a = RotateLeft(a, s)a = AddUnsigned(a, b)End SubPrivate Sub md5_HH(a, b, c, d, x, s, ac)a = AddUnsigned(a, AddUnsigned(AddUnsigned(md5_H(b, c, d), x), ac)a = RotateLeft(a, s)a = AddUnsigned(a, b)End SubPrivate Sub md5_II(a, b, c, d, x, s, ac)a = AddUnsigned(a, AddUnsigned(AddUnsigned(md5_I(b, c, d), x), ac)a = RotateLeft(a, s)a = AddUnsigned(a, b)End SubPrivate Function ConvertToWordArray(sMessage)Dim lMessageLengthDim lNumberOfWordsDim lWordArray()Dim lBytePositionDim lByteCountDim lWordCountConst MODULUS_BITS = 512Const CONGRUENT_BITS = 448lMessageLength = Len(sMessage)lNumberOfWords = (lMessageLength + (MODULUS_BITS CONGRUENT_BITS) BITS_TO_A_BYTE) (MODULUS_BITS BITS_TO_A_BYTE) + 1) * (MODULUS_BITS BITS_TO_A_WORD)ReDim lWordArray(lNumberOfWords 1)lBytePosition = 0lByteCount = 0Do Until lByteCount = lMessageLengthlWordCount = lByteCount BYTES_TO_A_WORDlBytePosition = (lByteCount Mod BYTES_TO_A_WORD) * BITS_TO_A_BYTElWordArray(lWordCount) = lWordArray(lWordCount) or LShift(Asc(Mid(sMessage, lByteCount + 1, 1), lBytePosition)lByteCount = lByteCount + 1LooplWordCount = lByteCount BYTES_TO_A_WORDlBytePosition = (lByteCount Mod BYTES_TO_A_WORD) * BITS_TO_A_BYTElWordArray(lWordCount) = lWordArray(lWordCount) or LShift(&H80, lBytePosition)lWordArray(lNumberOfWords 2) = LShift(lMessageLength, 3)lWordArray(lNumberOfWords 1) = RShift(lMessageLength, 29)ConvertToWordArray = lWordArrayEnd FunctionPrivate Function WordToHex(lValue)Dim lByteDim lCountFor lCount = 0 To 3lByte = RShift(lValue, lCount * BITS_TO_A_BYTE) And m_lOnBits(BITS_TO_A_BYTE 1)WordToHex = WordToHex & Right(”0 & Hex(lByte), 2)NextEnd FunctionPublic Function MD5(sMessage)m_lOnBits(0) = CLng(1)m_lOnBits(1) = CLng(3)m_lOnBits(2) = CLng(7)m_lOnBits(3) = CLng(15)m_lOnBits(4) = CLng(31)m_lOnBits(5) = CLng(63)m_lOnBits(6) = CLng(127)m_lOnBits(7) = CLng(255)m_lOnBits(8) = CLng(511)m_lOnBits(9) = CLng(1023)m_lOnBits(10) = CLng(2047)m_lOnBits(11) = CLng(4095)m_lOnBits(12) = CLng(8191)m_lOnBits(13) = CLng(16383)m_lOnBits(14) = CLng(32767)m_lOnBits(15) = CLng(65535)m_lOnBits(16) = CLng(131071)m_lOnBits(17) = CLng(262143)m_lOnBits(18) = CLng(524287)m_lOnBits(19) = CLng(1048575)m_lOnBits(20) = CLng(2097151)m_lOnBits(21) = CLng(4194303)m_lOnBits(22) = CLng(8388607)m_lOnBits(23) = CLng(16777215)m_lOnBits(24) = CLng(33554431)m_lOnBits(25) = CLng(67108863)m_lOnBits(26) = CLng(134217727)m_lOnBits(27) = CLng(268435455)m_lOnBits(28) = CLng(536870911)m_lOnBits(29) = CLng(1073741823)m_lOnBits(30) = CLng(2147483647)m_l2Power(0) = CLng(1)m_l2Power(1) = CLng(2)m_l2Power(2) = CLng(4)m_l2Power(3) = CLng(8)m_l2Power(4) = CLng(16)m_l2Power(5) = CLng(32)m_l2Power(6) = CLng(64)m_l2Power(7) = CLng(128)m_l2Power(8) = CLng(256)m_l2Power(9) = CLng(512)m_l2Power(10) = CLng(1024)m_l2Power(11) = CLng(2048)m_l2Power(12) = CLng(4096)m_l2Power(13) = CLng(8192)m_l2Power(14) = CLng(16384)m_l2Power(15) = CLng(32768)m_l2Power(16) = CLng(65536)m_l2Power(17) = CLng(131072)m_l2Power(18) = CLng(262144)m_l2Power(19) = CLng(524288)m_l2Power(20) = CLng(1048576)m_l2Power(21) = CLng(2097152)m_l2Power(22) = CLng(4194304)m_l2Pow