单向散列函数算法（Hash算法）：.doc

《单向散列函数算法（Hash算法）：.doc》由会员分享，可在线阅读，更多相关《单向散列函数算法（Hash算法）：.doc（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、单向散列函数算法（Hash算法）： 一种将任意长度的消息压缩到某一固定长度（消息摘要）的函数（过程不可逆），常见的单向散列算法有MD5,SHA.RIPE-MD,HAVAL,N-Hash由于Hash函数的为不可逆算法，所以软件智能使用Hash函数作为一个加密的中间步骤MD5算法： 即为消息摘要算法（Message Digest Algorithm），对输入的任意长度的消息进行预算，产生一个128位的消息摘要简易过程：1、数据填充.即填出消息使得其长度与448（mod 512）同余，也就是说长度比512要小64位（为什么数据长度本身已经满足却仍然需要填充？直接填充一个整数倍）填充方法是附一个1在后

2、面，然后用0来填充.2、添加长度.在上述结果之后附加64位的消息长度，使得最终消息的长度正好是512的倍数.3、初始化变量.用到4个变量来计算消息长度（即4轮运算），设4个变量分别为A,B,C,D（全部为32位寄存器）A=1234567H,B=89abcdefH,C=fedcba98H,D=7654321H4、数据处理.首先进行分组，以512位为一个单位，以单位来处理消息.首先定义4个辅助函数，以3个32为双字作为输入，输出一个32为双字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)其中，是异或操作这

3、4轮变换是对进入主循环的512为消息分组的16个32位字分别进行如下操作：（重点）将A,B,C,D的副本a,b,c,d中的3个经F,G,H,I运算后的结果与第四个相加，再加上32位字和一个32位字的加法常数（所用的加法常数由这样一张表Ti定义，期中i为1至64之中的值，Ti等于4294967296乘以abs(sin(i)所得结果的整数部分）（什么是加法常数），并将所得之值循环左移若干位（若干位是随机的？），最后将所得结果加上a,b,c,d之一（这个之一也是随机的？）（一轮运算中这个之一是有规律的递增的.如下运算式），并回送至A,B,C,D，由此完成一次循环。（这个循环式对4个变量值进行计算还是

4、对数据进行变换？）For i=0 to N/16 do For j=0 to 15 do Set Xi to Mi*16+jEndAA = ABB=BCC=CDD=D/第一轮，令ABCD K S I表示下面的操作：/A=B+(A+F(B,C,D)+XK+TI)S)/做如下16次操作ABCD 0 7 1DABC 1 12 2CDAB 2 17 3BCDA 3 22 4ABCD 4 7 5DABC 5 12 6CDAB 6 17 7BCDA 7 22 8ABCD 8 7 9.有一共16次 /第二轮，令ABCD K S I表示如下操作/A=B+(A+G(B,C,D)+XK+TI)S)/操作循环16次

5、ABCD 1 5 17DABC 6 9 18CDAB 11 14 19BCDA 0 20 20ABCD 5 5 21DABC 10 9 22CDAB 15 14 23.进行有规律的16运算/第三轮，令ABCD K S I表示如下操作/A=B+(A+H(B,C,D)+XK+TI)S)/做如下16次操作ABCD 5 4 33DABC 8 11 34CDAB 11 16 35BCDA 14 23 36/第四轮，令ABCD K S I表示如下运算/A=B+(A+I(B,C,D)+XK+TI)S)/做如下16次运算.ABCD 0 6 49DABC 7 10 50CDAB 14 15 51BCDA 5 2

6、1 52然后做如下加法运算A=A+AAB=B+BBC=C+CCD=D+DDEND当所有的512位分组运算完毕后，ABCD的级联将被输出成为MD5散列结果SHA算法即安全散列算法（Secure Hash Algorithm），有SHA-1,SHA-256,SHA-384和SHA-512几种分别产生160位，256位，384位和512位的散列值简易过程：1、 消息分组和填充方式与MD5相同2、 使用了f0,f1,f79这样一个逻辑函数序列，每一个ft(0=t=79)对3个32位的双字B,C,D进行操作，产生一个32位双字的输出。Ft(B,C,D)定义如下：Ft(B,C,D)=(B&C)|(B)&D

7、) 0=t=19 Ft(B,C,D)=BCD 20=t=39 Ft(B,C,D)=(B&C)|(B&D)|(C&D) 40=t=59 Ft(B,C,D)=BCD 60=t=79在C语言中常用宏定义进行初始化同样SHA-1也使用了一系列的常数K(0),K(1),.,K(79).用十六进制表示就是Kt=5A827999 0=t=19Kt =6ED9EBA1 20=t=39Kt =8F1BBCDC 40=t=59Kt =CA62C1D6 60=t0)sum+=delta;y+=(z5)+k1);z+=(y5)+k3);v0=y;v1=z;其中，delta是由黄金分割得来的，解密算法是加密算法的逆过程

8、.2,弱点：比如相关密钥攻击对其可以造成很大威胁，也提出了改进算法XTEA.IDEA算法IDEA(International Data Encryption Algorithm)(国际数据加密算法)简易原理：1,分组密码IDEA明文和密文的分组长度为64位，密钥长度为128位。特点是使用了3中不同的代数群（在代数几何中，一个代数群（或群簇）是一个群是一个代数簇，其簇之乘与逆由正则函数提供。以范畴论描述，一个代数群是一个于代数簇范畴 (数学)中的群对象）（还是不懂.囧！）上的操作。2,子密钥的产生：IDEA共使用52个16位的子密钥，其由输入的128为密钥生成。过程如下l 首先，输入的128位密

9、钥被分成8个16位的分组，直接作为前8个子密钥。l 128位密钥循环左移25位，生成的新的128位密钥被重新分成8组16位的分组，作为后面的8个子密钥。l 重复上述步骤，直至52个子密钥全部生成。（52个子密钥不是8的倍数，最后一次分组只分了4组，这样的话128位被分成4组，每组的数量就不同了.？还是分组方式我理解错了？）3,加密算法：IDEA的加密过程由8个相同的加密步骤（称为加密轮函数）和一个输出变换组成，过程如图（图看不懂！）： 4,过程：首先，64位明文（明文在加密过程中呈什么形式？是一些2进制数据？为什么说是64位明文？）（这里是因为IDEA加密算法对明文进行分组，即64位一组，以组

10、为单位来处理数据）被分成4个16位分组，每一轮加密都需要6个子密钥，最后的输出变换需要4个子密钥，在第一轮加密中，4个16位的子密钥分别通过两个模216+1的乘法运算和两个模216的加法运算与明文进行混合，结果用两个16位的子密钥以及按位异或操作。第一轮加密的结果，在进行部分交换后，作为第二轮加密的输入。如此在重复进行7轮，在接下来的输出变换（Output Transform）中，使用52个子密钥中的最后4个，通过模加和模乘运算与第八轮的结果进行混合，产生最后的密文.5,IDEA解密算法： 过程同加密相同，不同之处在于：使用的子密钥不相同，解密所使用的子密钥是加密的子密钥的相应于不同操作运算的

11、逆元。其次，解密时子密钥必须以相反的顺序使用。IDEA中的加法与乘法逆元的规则定义如下：X+addinv(x) = 0 (mod 65535)X*mulinv(x) = 1 (mod 65537)其中，模216+1的乘法逆元的计算可以使用欧几里得算法（查！主要查这个算法是用来解决什么问题的。）来求，代码如下：Unsigned inv (unsigned xin)Long n1,n2,q,r,b1,b2,t;If(xin = 0) b2=0;Elsen1 = maxim;n2=xin;b2=1;b1=0;dor = (n1 % n2); q = (n1-r)/n2;if(r=0)if(b20)

12、b2=maxim+b2;else n1=n2; n2 = r ; t=b2 ; b2=b1-q*b2; b1=t while(r!=0);Return (unsigned)b2;BlowFish算法BIowFish算法是一个64位分组及可变密钥长度的分组密码算法。简易原理：BlowFish算法基于Feistel网络（Feistel网络是基于Shannon1945年的设计提出的，为现在正使用所有重要的分组密码都几乎沿用着这种结构，Feistel的思路是可以用乘积密码的概念来近似简单的代替密码。乘积密码就是以某种方式连续执行两个或多个密码，以使所得到的“乘积”从密码编码的角度，比任意一个组成密码都

13、强，特别是Feistel提出的用“代替”和“置换”交替的方式）（详细见文档）（替换/置换网络的典型代表），加密函数迭代执行16轮，分组长度为64位（这里长度为64位，不够是否要进行填充？），密钥长度可以从32位到448位。算法由两个部分组成：密钥扩展部分和数据加密部分。1,密钥扩展部分：这部分将最长为448位的密钥转化成共4168字节长度的子密钥数组。其中，数据加密由一个16轮的Feistel网络来完成。每一轮由一个密钥相关置换和一个密钥与数据相关的替换组成，2,子密钥：BlowFish使用大量的子密钥。这些密钥必须在进行加密前预计算产生。l P数组由18个32位字的子密钥组成：P1，P2，P

14、18。l 4个8*32的包含总共1024个32位字的S-box（什么是S-box?）：子密钥的扩展算法如下：-1,按顺序使用常数的小数部分初始化P数组和S-box。比如： P1=0x243f6a88 P2=0x85a308d3-2,对P数组的密钥进行逐位异或，需要时重用密钥（什么事重用密钥？什么时候才算是需要时？）。-3,使用当前的P数组和S-box对全0的64位分组（怎么会有全0的分组？）使用BlowFish算法进行加密，用输出替代P1,P2。-4,使用当前的P和S对第三部的输出进行加密，并用输出替代P3，P4。-5,继续上面的过程，知道按顺序替代所有的P数组和S-box中的元素。3,加密：

15、BlowFish是由16轮的Feistel网络组成的。输入时一个64位的数据元素x，将x分成两个32位的部分，xL，xR。加密算法的伪代码如下：For(i=1;i=16;i+)xRi=xLi-1 Pi;xLi=F(xRi xRi-1);xL17=xR16P18;xR17=xL16P17;其中函数F的输入时一个32位双字，共四个字节，分别作为4个S-box的索引（索引？），取出相应的S-box的值，然后进行模232加运算。解密与加密完全相同，只不过P1,P2,P18以相反的顺序使用。AES算法AES(Advandced Encryption Standard)(高级加密标准)，是NIST(Nat

16、ional Institute of Standards Technology)(国家标准技术研究所)与1997年开始向世界范围内征集的加密算法，用于替代DES成为新一代的加密标准。最终，由比利时密码学加Joan Daemen和Vincent Rijmen设计的Rijndael当选，实际上，Rijndael算法和AES的唯一区别在于各自所支持的分组长度和密码密钥长度的范围不同，Rijndael是具有可变分组长度和可变密钥长度的分组密码，其分组长度和密钥长度均可独立的设定为32比特的任意倍数，最小值为128bit，最大值为256bit。AES将分组长度固定为128位，而且仅支持128,192,和

17、256位的密钥长度，分别称作AES-128,AES-192,AES-256。下面提到的AES算法专指FIPS-197（什么组织？）中规定的AES算法。1,基本术语：(1),字节：AES算法的基本处理单元叫字节，由八个比特序列组成，被看成一个整体，这些字节以有限域上的多项式（什么是有限域上的多项式？）来表示(2),状态（State）:AES的所有操作都是在一个称作状态的二维字节数组上进行的。状态由4行字节组成，每行包括Nb个字节，Nb为分组长度除以32的值。用s来表示状态，状态数组中的每个字节有两个坐标，行号r的范围为0=r4，列号c的范围为0=cNb。可用sr,c来应用状态中的每个字节。在AE

18、S算法的加密和解密开始，输入字节数组in0,in1,in15复制到状态中，然后对状态数组中的元素进行加解密操作，最后将结果复制到输出字节数组out0,out1,out15,如图：3,数学背景：(1),加法：有限域上的两个元素的画法运算是通过对相应的多项式中的相同次幂的系数进行相加来实现的。其加法是模2的运算.也就是异或操作.简易原理：对于AES算法来讲，输入分组，输出分组及状态数组的长度都是128bit，即Nb=4,密钥K的长度为128,192或者256bit，用Nk=4,6或者8来表示。加密或者解密函数所执行的轮数取决于密钥的长度。轮数用Nr来表示，分别对应10,12,14。1,加密过程：先

19、将输入复制待状态数组。在进行一个初始轮密钥加操作(Round Key Addition)(这是什么操作？)之后，执行Nr次轮函数对状态数组进行变换，其中最后一轮不同于前Nr-1轮。最终的状态数组复制到输出即为最后的密文。轮函数有4个部分组成，分别是Subytes(),ShiftRows(),MixColumns(),AddRoundKey(),加密算法 的伪代码如下：轮函数介绍：1,SubBytes(),字节替换，实际上就是一个简单的查表操作。AES定义了一个16*16的字节的S盒，以状态数组中的每个字节元素的高4位作为行标，低4位作为列标，取出相应的元素啊作为SubBytes()操作的结果。

20、S盒如下：（这里X为行标，Y为列标）按照此操作，将状态数组中的所有值都替换成S盒中对应的数值。2,ShiftRows：此操作规则是状态数组的第一行保持不变，第二行循环左移一个字节，第三行循环左移两个字节，第四行循环左移3个字节3,MixColims：MixColums操作是以列为单位，把状态中的每一列看做一个系数在(GF是什么？)GF(28)上的四项多项式，然后乘以一个固定的多项式a(x),再模(x4+1).a(x)的定义如下： a(x)=03x3+01x2+01x+02 4,AddRoundKey():此操作是将状态中的元素同轮密钥（论密钥是由用户输入的密钥通过密钥扩展过程生成的，同样可以看

21、作一个状态数组）通过简单的异或运算相加。密钥扩展（Key Expansion）：密钥扩展算法通过对用户输入的128,192或者256位的密钥进行处理，共生成Nb(Nr+1)个32位双子，为加解密算法的论函数提供轮密钥。 其中，SubWord函数以一个4个字节的双字作为输入，然后对每个字节利用S盒进行替换作为输出。函数RotWord以双字a0,a1,a2,a3作为输入，做循环左移操作，输出为a1,a2,a3,a0。轮常量数组Rcon中的每一个元素Rconi为一个32位双字，且低24位恒为0高8位，即一个字节按如下规则定义：Rcon1=1,Rconi=2*Rconi-1,乘法定义与GF(28)上，

22、解密过程：解密过程的轮函数有4个部分组成InvShiftEows(),InvSubBytes(),InvMixColums(),AddRoundKey().InvShiftRows是ShiftRows的逆过程，即相应的进行循环右移操作。InvSubBytes是SubBytes的逆过程，AES同时也定义了一个逆S盒。InvMixColums与MixColums的原理是相同的，不同的是使用了不同的多项式。AddRoundKey的逆过程就是他本身，因为异或操作时其本身的逆在加解密及逆向工程中，常见的AES算法的事项与上述的过程是不同的。实际的软件实现采用了以空间换时间的方法，将轮函数的几个步骤合并为

23、一组简单的查表操作。DES算法公开密钥加密算法（非对称加密算法）对称加密算法的缺点在于一旦加解密密钥被获取，那么加密保护立即失效，1976年提出了公开密钥加密算法。公钥加密算法加密与解密使用不同的密钥，加密所使用的叫做公钥，解密所使用的叫做私钥，任何人都可以使用公钥分配者分配的公开密钥对信息进行加密，但是只有拥有私钥的人才能解密。公钥加密算法的设计都是基于NP完全问题（详见计算机密码学）如果软件设计者在生成注册码时采用解密算法（私钥），而在软件检测注册码时使用加密算法（公钥），即使解密者能够用调试器在自己的机器上对软件进行跟踪得到公钥，他也不一定能够计算出私钥。RSA算法RSA是第一个既能用于

24、数据加密也能用于数字签名，其安全性依赖于大整数因子分解。简易原理：1,选取两个大素数（选取随机素数？）：p和q，为了获得最大程度的安全性，两数的长度一样2,计算n=p*q,n称为模。3,计算欧拉函数：n=p-1*(q-1);4,选取加密密钥e，其与n互素，选择合适的e的值，RSA算法的加解密的速度要快的多，常用的e的值3,17,65537.5,使用扩展欧几里德算法（欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数！而扩展欧几里德算法是用来在已知a,b求解一组p,q使得p*a+q*b=Gcd(a,b)，常用在求解模线性方程及方程组中。）求出e模n的逆元d，即 ed=1 mod n6

25、,公钥为e和n，私钥为d,p和q可以丢弃，但是必须保密。7,加密消息m时，将其看成一个大整数，把它分成比n小的数据分组，按下列式子进行加密： Ci=mie mod n8,对密文C进行解密时，取每一个加密后的分组Ci并计算： miCid mod n大致算法原理如下表：攻击RSA最有效的方法就是分解模n。为了保证RSA系统的安全性，一般认为RSA需要1024位或更长的模数才有安全保障，常见的因子分解算法有试除法(Trial Division)，Pollard 因子分解算法，Pollard p-1因子分解算法，椭圆曲线因子分解算法(Ellipic Curve Factoring Algorithm)

26、,随机平方因子分解算法(Random Square Factoring Algorithm),连分式因子分解算法(Continued Factoring Algotithm),二次筛法，数域筛法等等ElGamal公钥算法其安全性依赖于有限域上计算离散对数的困难性。简易原理：1,密钥产生办法：首先生成一个大素数p，模p的乘法群（什么是乘法群？）Zp*上的一个生成原g和一个小于p的大数x，然后计算ygx mod p公钥位y,g和p，私钥是x。其中g和p可以由一组用户共享。2,ElGamal签名：对消息M签名时，生成一个随机数k，1=k=p-2，且gcd(k,p-1)=1,计算： agk mod p

27、再用扩展欧几里德算法对下面的方程求解b： M xa+xb mos (p-1)当k与(p-1)互素时，b有一个解。签名即为(a,b).随机数k必须丢弃。验证签名时，需要满足下式： yaab gM mod p同时要检验是否满足1=ap,否则签名容易伪造（为什么？）3,ElGamal加密算法：被加密的信息为M，首先选择一个随机数k，且k与p-1互素，计算： a gk mod p b ykM mod p其中(a,b)为密文，是明文的两倍长。解密时计算： M bak (mod p)缺点十分明显，就是密文的长度是明文的两倍4,ElGamal算法在加密上的应用：(1)随机生成密钥对，(2)在软件中判断注册码

28、，5,攻击ElGamal算法保护：ElGamal在签名验证过程中用到了参数y,g,p。解密思路就是根据y gx mod p，求离散对数获得x的值。6,ElGamal算法的一些注意事项：(1)如果m-xa出现负值，即最后得到的签名b为负数，一般来说这时需要将b不断的加上p-1，直到出现一个小于p-1的非负值时为止，此时这个非负值就是要求的签名b。(2)签名时随机生成的k必须要同p-1互素，g必须为乘法群的一个生成单元。(3)当签名出现b=0的时候，一定要重新对消息进行签名，不然很容易求出私钥x。(4)共享软件作者在给用户分发注册码时，一定不要用同一个k对不同的用户名进行签名，并将签名分发给用户。

29、DSA数字签名算法DSS（Digital Signature Strandard）（数字签名标准）采用算法为DSA（Digital Signature Algorithm）（数字签名算法），现今版本为FIPS 186-2（Federal Information Processing Standards）（联邦信息处理标准）。简易原理：DSA使用如下的一些参数：P: L位长的素数。L是64的倍数，范围512到1024q: p-1的素因子，取值范围为2159q2160g: g= h(p-1)/q mod p 其中h满足h1x: 0xq 其中x为私钥y: y = gx mod p 其中(p,q,g,

30、y)为公钥k: 随机或伪随机数，0kq整数p,q和g可以公开，并且可由一组用户共享，每个用户分别具有各自的私钥x和公钥y。为了保证最大限度的安全，x和y需要在一段时间内进行更新。参数x和k仅用于生成签名，必须保密。对每个不同的签名，k必须不同签名及验证协议如下：输入：待签名的消息M，公钥p,g,q，私钥x，随机数k输出：签名r,s算法：DSA签名验证算法：输入：待验证的消息M，公钥p,g,q，公钥y，签名r，s输出：若签名正确返回TRUE,否则返回FALSE算法：其他算法CRC32算法：CRC全称”Cyclic Redundancy Chrcksum”是对数据的效验值，即循环冗余效验码，常用于

31、效验数据的完整性。Base64编码：Base64编码是将二进制数据编码为可显示的字母和数字，用于传送图形，声音和传真等分文本数据。常用于MIME电子邮件格式中。其使用含有65个字符的ASCII，并用6个进制位表示一个可显示字符。加密算法库Miracl大数运算库：全称Multiprecision Integer and Rational Arithmetic C/C+ Library,即多精度整数和有理数算术运算C/C+库。这是一个大数库，实现了设计使用大数的加密技术的最基本函数。支持RSA公钥系统,Diffie-Hellman密钥交换，DSA数字签名系统及基于GF(p)和GF(2m)的椭圆曲线

32、加密系统。FGInt：全称Fast Gigantic Integers，是用于Delphi的一种可以实现常见的公钥加密系统的库。FreeLIP：最初设计是用于进行RSA-129挑战大数计算的大数库Crypto+：是一个实现了相当数量的加密算法的加密库，LibTomCrypt：其中包括了常见的散列算法，对称算法及公钥加密系统。GMP：全称GNU Multiple Precision Arithmetic Library，其核心采用汇编实现，速度非常快，常用于实现大整数因子的分解，以提高速度OpenSSL：主要用于网络安全，其中也包含了一些加密算法的实现，BlowFish，IDEA，DES,CAST,RSA,DSA,MD5,RIPEMD,SHA等。DCP和DEC：DCP全称为Delphi Cryptography package,是用于Delphi的一个加密算法库，DEC全称为Delphi Encryption Compendium，这两个加密算法库实现了大部分常见的散列算法及对称算法。Microsoft Crypto API：NTL：是一个可以用于数论相关计算的库