1、 一个强碰撞自由的Hash函数是满足下列条件的一个函数h：（1）h的输入可以是任意长度的任何消息或文件M；（2）h输出的长度是固定的（该长度必须足够长，以抵抗所谓的生日攻击，根据今天的计算技术和能力，至少应为128比特长）；（3）给定h和m，计算 h（M）是容易的；（4）给定h的描述，找 两 个不同的消息（信息）M1 和 M2，使得 h（M1）=h（M2）是计算上不可行的。（如果这两个消息M1，M2，M1M2，使得 h（M1）=h（M2），则称这两个消息是碰撞消息碰撞消息或称这两个消息碰撞这两个消息碰撞。）一个弱碰撞自由的Hash函数与一个强碰撞自由的Hash函数的前三个条件（1）-（3）完全
2、一样，不同的只是第（4）个条件。在一个弱碰撞自由的Hash函数中。（5）给定h的描述和一个随机选择的消息M1，找另一个消息M2，M2M1，使得h（M1）=h（M2）是计算上不可行的。实际受到的附件 附件所期望的附件如果两者一样，则认为消息是完整的 产生附件 消息 附件产生附件 消息 消息接收者发送者传输的消息比较一般的封装机制 二、消息摘录技术的应用二、消息摘录技术的应用 1 1、用于计算消息完整码用于计算消息完整码 消息m 附件F将F与收到的附件F进行比较如果F=F则认为消息是完整的，否则不是完整的消息m 附件FMD（m|K AB）重新根据m,由m|K AB计算附件F 消息m 密匙K AB消
3、息m 发方A 收方B传输的消息2、使用MD进行双向鉴别 rA rB A BMD(KABrA)MD(KABrA)基于的双向MD鉴别机制 一、概、概 述述 MD4的设计是面向32比特字的，更适合于32位计算机，效率比MD2高。MD4计算出的消息摘录长度为128比特，用4个字表示，分别记为A，B，C，D，在计算开始时被分别初始化为常数。输入信息被分成512比特的等长块，逐块 处 理。每 块 包 含 1 6 个 字，分 别 记 为 m0，m1，m15。每块的处理分三遍扫描，每遍对A，B，C，D使用不同的扰乱函数。在处理前需将当前的消息摘录备份，在处理后将这个备份加到新产生的消息摘录上，并将其作为下一块
4、处理时消息摘录的当前值。最后一块信息处理之后的消息摘录当前值，即为最终的消息摘录值。3.1.13.1.1、MD4MD4二、二、MD4MD4信息填充信息填充 给定一个X，将X进行填充，使其成为一个512比特的倍数串M=M0M1MN-1 ，这里每个Mi(0 i N-1)是长为32比特的串，N0(mod16)（即N是16的倍数。）我们将每个Mi称为一个字（32位），由X产生M的算法如下：d=447-(xmod512)（当d0时，按模512处理）l表示x的长度，即x。l=64（即用64比特表示x的长度）M=x10dl 初始信息（x）1000 初始信息的 比特数（l）即使原来的信息已是512比特的倍数，
5、也要进行填充。三、直接构造法三、直接构造法 现在我们从M开始构造一个128比特长的消息摘录，其构造过程如下：（1）给四个寄存器A、B、C、D赋初始值（用十六进制表示）：A=67452301 B=efcdab89 C=98badcfe D=10325476（2）for i=0 to N/16 -1 do；（3）for j=0 to 15 do mj=M16i+j （4）将四个寄存器A、B、C、D的值存储到另外四个寄存器AA，BB，CC，DD之中，AA=A；BB=B；CC=C；DD=D （5）执行第一轮；（6）执行第二轮；（7）执行第三轮；（8）A=A+AA ；B=B+BB；C=C+CC；D=D+
6、DD X取整二进制求补；xyx与y按位逻辑“与（and）”；xyx与y按位逻辑“或（or）”；x x y x与y按位逻辑“异或（xor）”；x+y二进制加运算（即整数模232加法运算）；xyx循环左移y个位置（0y31）。MD4中的三个轮是不同的。1、第一轮 第一轮使用一个如下定义的函数f（x，y，z）=（xy）（xz）(1）for k=0 to 3 do；（2）A=（A+f（B，C，D）+m4k 3 （3）D=（D+f（A，B，C）+m4k+1 7 （4）C=（C+f（D，A，B）+m4k+2 11 (5)B=（B+f（C，D，A）+m4k+3 15 2、第二轮 第二轮使用一个如下定义的函数
7、：g（x，y，z）=（xy）（xz）（yz）取常数C2=2=5a827999H 注意：在第二轮中mi不是顺序处理的。1）A=（A+g（B，C，D）+m0+5a827999）3；2）D=（D+g（A，B，C）+m4+5a827999）5；3）C=（C+g（D，A，B）+m8+5a827999）9；4）B=（B+g（C，D，A）+m12+5a827999）13；5）A=（A+g（B，C，D）+m1+5a827999）3；(6)D=（D+g（A，B，C）+m5+5a827999）5；(7)C=（C+g（D，A，B）+m9+5a827999）9；(8)B=（B+g（C，D，A）+m13+5a82799
8、9）13；(9)A=（A+g（B，C，D）+m2+5a827999）3；(10)D=（D+g（A，B，C）+m6+5a827999）5；(11)C=（C+g（D，A，B）+m10+5a827999）9；(12)B=（B+g（C，D，A）+m14+5a827999）13；(13)A=（A+g（B，C，D）+m3+5a827999）3；(14)D=（D+g（A，B，C）+m7+5a827999）5;(15)C=（C+g（D，A，B）+m11+5a827999）9；(16)B=（B+g（C，D，A）+m15+5a827999）13；第第 三三 轮轮第三轮定义扰乱函数如下：h（X，y，Z）=x y z
9、 取常数 C3=2 =6edgebalH 302302 与第二遍扫描类似，第三遍扫描时对Mi的处理也不是顺序的，具体为:(1)A=（A+h（B，C，D）+m0+C3）3；(2)D=（D+h（A，B，C）+m8 +C3）9 ；(3)C=（C+h（D，A，B）+m4+C3）11；(4)B=（B+h（C，D，A）+m12+C3）15；(5)A=（A+h（B，C，D）+m2+C3）3；(6)D=（D+h（A，B，C）+m10 +C3）9；(7)C=（C+h（D，A，B）+m 6+C3）11；(8)B=（B+h（C，D，A）+m 14+C3）15；(9)A=（A+h（B，C，D）+m 1+C3）3；（1
10、0）D=（D+h（A，B，C）+m 9 +C3）9；（11）C=（C+h（D，A，B）+m 5+C3）11；（12）B=（B+h（C，D，A）+m 13+C3）15；（13）A=（A+h（B，C，D）+m 3+C3）3；（14）D=（D+h（A，B，C）+m 11 +C3）9；（15）C=（C+h（D，A，B）+m 7+C3）11；（16）B=（B+h（C，D，A）+m 15+C3）15；MD5v第一轮 F(x,y,z)=(x y)V(z)A=B+(A+f(B,C,D)+m0+d7aa78)7)D=A+(D+f(A,B,C)+m1+e8c7b756)12)C=D+(C+f(D,A,B)+m2+
11、242070db)17)B=C+(B+f(C,D,A)+m3+c1bdceee)22)A=B+(A+f(B,C,D)+m4+f57c0faf)7)D=A+(D+f(A,B,C)+m5+4787c62a)12)C=D+(C+f(D,A,B)+m6+a8304613)17)xB=C+(B+f(C,D,A)+m7+fd469501)22)A=B+(A+f(B,C,D)+m8+698098db)7)D=A+(D+f(A,B,C)+m9+8b44f7af)12)C=D+(C+f(D,A,B)+m10+ffff5bb1)17)B=C+(B+f(C,D,A)+m11+895cd7be)22)A=B+(A+f
12、(B,C,D)+m12+6b901122)7)D=A+(D+f(A,B,C)+m13+fd987193)12)C=D+(C+f(D,A,B)+m14+a679438e)17)B=C+(B+f(C,D,A)+m15+49b40821)22)第二轮 g(x,y,z)=(xz)V(y )A=B+(A+g(B,C,D)+m1+f61e2562)5)D=A+(D+g(A,B,C)+m6+c04ob34o)9)C=D+(C+g(D,A,B)+m11+265e5a51)14)B=C+(B+g(C,D,A)+m0+egb6c7aa)20)A=B+(A+g(B,C,D)+m5+d62f105d)5)D=A+(D
13、+g(A,B,C)+m10+02441453)9)C=D+(C+g(D,A,B)+m15+d8a1e681)14)B=C+(B+g(C,D,A)+m4+e7d3fbc8)20)A=B+(A+g(B,C,D)+m9+21e1cde6)5)zD=A+(D+g(A,B,C)+m14+c33707d6)9)C=D+(C+g(D,A,B)+m3+f4d5od87)14)B=C+(B+g(C,D,A)+m8+455a14ed)20)A=B+(A+g(B,C,D)+m13+a9e3e9o5)5)D=A+(D+g(A,B,C)+m2+fcefa3f8)9)C=D+(C+g(D,A,B)+m7+676fo2d9
14、)14)B=C+(B+g(C,D,A)+m12+8d2a4c8a)20)第三轮 h(x,y,z)=xyzA=B+(A+h(B,C,D)+m5+fffa3942)4)D=A+(D+h(A,B,C)+m8+8771f681)11)C=D+(C+h(D,A,B)+m11+6d9d6122)16)B=C+(B+h(C,D,A)+m14+fde5380c)23)A=B+(A+h(B,C,D)+m1+a4beea44)4)D=A+(D+h(A,B,C)+m4+4dbecfa9)11)C=D+(C+h(D,A,B)+m7+f6b46bo)16)B=C+(B+h(C,D,A)+m10+bebfbc70)23)
15、A=B+(A+h(B,C,D)+m13+289b7ecb)4)D=A+(D+h(A,B,C)+m0+eaa127fa)11)C=D+(C+h(D,A,B)+m3+d4ef3085)16)B=C+(B+h(C,D,A)+m6+04881d05)23)A=B+(A+h(B,C,D)+m9+d9d4d039)4)D=A+(D+h(A,B,C)+m12+e6db99e5)11)C=D+(C+h(D,A,B)+m15+1fa27cf8)16)B=C+(B+h(C,D,A)+m2+c4ac5665)23)第四轮 I(x,y,z)=y(xV )A=B+(A+I(B,C,D)+m0+f4292244)6)D=
16、A+(D+I(A,B,C)+m7+432aff97)10)C=D+(C+I(D,A,B)+m14+ab9423a7)15)B=C+(B+I(C,D,A)+m5+fc93a039)21)A=B+(A+I(B,C,D)+m12+655b59c3)6)D=A+(D+I(A,B,C)+m3+8foccc92)10)C=D+(C+I(D,A,B)+m10+ffeff47d)15)B=C+(B+I(C,D,A)+m1+85845dd1)21)zA=B+(A+I(B,C,D)+m8+6fa87e4f)6)D=A+(D+I(A,B,C)+m15+fe2ce6e0)10)C=D+(C+I(D,A,B)+m6+a
17、3014314)15)B=C+(B+I(C,D,A)+m13+4e0811a1)21)A=B+(A+I(B,C,D)+m4+f7537e82)6)D=A+(D+I(A,B,C)+m11+bd3af235)10)C=D+(C+I(D,A,B)+m2+2ad7d2bb)15)B=C+(B+I(C,D,A)+m9+eb86d391)21)常数 可以如下选择:在第i步中,是|sin(i)|的整数部分，i的单位是弧度。所有这些完成之后，将A,B,C,D分别加上AA,BB,CC,DD，然后用下一组数据继续运行算法，最后的输出是A,B,C和D的级联，即128位长的字。对单轮的MD5已有攻击结果，但对4轮MD
18、5则还没有有效的方法。即使采用生日攻击，寻找具有相同Hash值的两个信息需要试验 个信息，而差分攻击也对MD5的安全性步构成威胁。ititit322642 MD5与MD4相比较,主要作了以下六点改进:(1)增加了第四轮，第四轮所使用的函数为 （x，y，z）=（x ）y；z(2)第二轮的函数g变为g（x，y，z）=（xz）（y ），以减弱它的对称性；z(3)进入第二轮和第三轮的输入字的次序被改 变；(4)每一轮中的移位数已改变，并且各轮中的移位数互不相同；(5)每一步有一个唯一的加法常数；(6)每一步加上了上一步的结果，这样会产生更好的“雪崩效应”。3.1.2 Hash3.1.2 Hash函数的
19、攻击方法函数的攻击方法 生日攻击生日攻击 生日攻击这个术语来自于所谓的生日问生日问题：题：在一个教室中最少应有多少学生,才使得至少有两个学生的生日在同一天的概率不小于？21 设hxy是一个Hash函数，x和y都是有限的集合，并且x=m，y=n。显然至少有个碰撞，问题是如何去找这些碰撞。一个很自然的方法是随机选择k个不同的元素x1，x2，xkx，计算yi=h(xi)，1 i k，然后确定是否有一个碰撞发生。这表明，仅杂凑（随机拼凑）个x的随机的元素就能以50%的概率产生一个碰撞。n 注意注意:的不同选择将导致一个不同的常数因子，但k与 仍成正比例。n 如前面的例子，x是一个教室中所有学生的集合，
20、y是一个非润年的365天的集合，h(x)表示学生x的生日，现在我们类处理生日问题。这时n=365,=,由k1.17,=1.17,22.3，知教室中至少要有23名学生。12n365 生日攻击隐含着消息摘要的长度的一个下界。3 32 2数字签名技术数字签名技术 一、数字签名一、数字签名 为了具有通常手书签名的功效，数字签名应满足以下条件：（1）收方能够鉴别其收到的报文确实是发方发送来的，其内容是真实的；（2）发方事后不能根据自己的利益来否认他所发送过的报文；（3）包括收方在内的任何人都不能伪造报文或签名。二、利用公钥密码体制实现的数字签名 1、在公钥密码系统的通信中，实现数据的保密性和真实性。(1
21、)数据的保密性 设用户A要发送消息M给用户B，A B ,为了使M在传送过程中不被泄露，A可用B的公开密钥PKB对M加密，将密文传送给B。M M DSKB（EPKB（M）=M A方 PKB SKB B方)(MECPKBED 用公钥体制实现数据的保密性。(2)数据的真实性条件：条件：该公钥密码体制的公开密钥既能作加密密钥，又能作解密密钥使用，即 DSK（EPK（M）=EPK（DSK（M）=M M M=EPKA（DSKA（M）A方 SKA PKA B方ED)(MDCSKA 公钥密码体制实现真实性。（丧失了保密 性）(3)(3)既实现数据的保密性又实现数既实现数据的保密性又实现数据的真实性据的真实性
22、数据 M M A方 SKA PKB SKB PKA B方 )(MDECSKAPKBDEDE 用公钥密码体制实现数据的保密性和真实性 2 2、用公钥密码体制实现的数字签名、用公钥密码体制实现的数字签名 设A要向B发送一份报文M，该报文由两部分组成：一部分称作报头H，它包括发方的身份，收方的身份及发送序号等。即H=发方的ID，收方的ID，发送序号；另一部分是要发送的报文数据M，若需要可附上时间T。签名者用他的秘密密钥SKA对M或（M，T）进行变换（解密运算）得S=DSKA（M）或S=DSKA（M，T），实现对报文的签名，然后用收方B的公开密钥PKB对MS=（H，S）进行加密运算，并将结果EPKB（
23、MS）发送给B，实现保密通信。)(MDSSKA M M A方 SKA PKB SKB PKA B方 DEDDHH)(,(MDHESKAPKB签名保密通信加密 脱密 验证签名 B收到报文后操作：（1）B用自己的秘密密钥SKB先对收到的报文解密，得MS，根据H中的信息识别出发送者的身份是A。（2）在公开的签名信息簿中查出A用于签名验证的公开密钥PKA。（3）用PKA对S进行变换 EPKA（S）=EPKA（DSKA（M）=M。（4）检查M是否正确。三、基于对称密码体制的数字签名三、基于对称密码体制的数字签名 LD方法利用一组密钥，其个数由报文的长度决定，对 报文进行逐位的签名。LD方法分为准备、签名
24、和验证三部分。准备的内容为：（1）若报文长度为n，则设置由发方A秘密保存的2n个签名密钥，记为1，1，2，2，n，n；（2）A随机地选择2n个数：u1，u2，un U1，U2，Un 并分别用第一步产生的密钥对这2n个数据加密，得到2n个密文：vi=Ei(ui)i=1,2,，n vi=Ei(ui)i=1,2,，n A将u1,u2,u3,un u1,u2,u3,un这2n个数据和2n个密文v1,v2,v3,vn v1,v2,v3,vn作密文验证信息公开交给B和仲裁者。(3)若报文M=m1m2mn的第i位mi为1，则签名的第i位取i，否则取i，最终构成一个元素个数与报文长度相同的密钥序列。SA=K1
25、K2Kn。Ki=i mi=1i mi=0 i=1,2,n其中A将 A将SA留底后，发送给B.B收 B收到签名数据后，验证签名的方法为：根据报文的内容确定密钥的内容，然后按报文的各位根据预先计算好的那两组数来验证收到的签名是否正确；（4）B用Ki分别对vi和Vi解密，若解得明文为ui，则断定mi=0；若为Ui，则断定mi=1。否则说明签名有错误或有篡改伪造行为。0 Dki(vi)=ui1 Dki(Vi)=Ui Mi=B将收到的SA留底。该方法存在两个严重缺陷：（1）签名比报文长的多，例如若使用DES作为加密算法，则每个密钥有56位，即签名的长度是报文长度的56倍。（2）签名密钥若不采用一次一密方
26、式，则每次签名都会把n个密钥泄露出去，重复使用相同的签名密钥是很不安全的；而一次一密的密钥管理负担很重。四、仲裁者签名四、仲裁者签名 通过第三者介入的传统密码数字签名（仲裁签名）通信的双方A，B把各自的秘密密钥交给可信的第三者了，通信过程如图所示，设发方A要将信息M发送给B。S方仲裁者)(MECKAM A方KA E M=DKA(C)C=EKB(M)C=EKB(M)D KBB方4.数据加密标准（DES）（Data Encryption Standard）4、1分组密码概述 一、分组密码体制的设计有下面的技术要求：（1）分组长度m要足够大，以防止明文穷举的攻击。（2）密钥量应足够大，以防止密钥穷举
27、的攻击。（3）密码的法足够复杂，使破译者除了采用穷举法攻击以外，找不到其它简洁的数字破译算法。二、密文块的长度与明文块长度间关系。4.2 4.2 数据加密标准（数据加密标准（DESDES）一、DES加密算法简介 二、DES加密算法的粗框 以每一个明文块的加密过程为例给出DES加密的过程，简单的用一句话可概述这个加密过程：将64bit的明文块在56bit的密钥控制下变换为64bit的密文块，其加密过程包括16次选代（即16圈）每次选代都由替代和移位的复合而形成的。g明文块 X=x1 x2。x 64简单移位变换K（1）32位32位 48位R（1）=r1（1），r32（1）初始置换IP L（0）=l
28、1（0），l32（0）R（0）=r1（0），r32（0）L（1）=l1（0），l32（0）g48位K（2）R（2）=r1（1），r32（1）L（2）=l1（0），l32（0）逆初始置换（IP）密文块y=y1y2y64 L（16）R（16）R（16）=r1（16），r32（16）gR（15）=r1（15），r32（15）R（2）=r1（2），r32（2）L（2）=l1（2），l32（2）K（16）48位L（15）=l1（2），l32（2）L（16）=l1（2），l32（2）粗框说明粗框说明 第i圈：输入：L（i-1）R（i-1）输出：L（i）=R（i-1）R（i）=gk（i）（R（i-1）)L（
29、i-1）或令 Pi-1=gk（i）（R（i-1）则 R（i）=P i-1 L（i-1）R（i）=gk（i）(L（i-1）)L（i-1）三、三、DESDES加密算法的详细说明加密算法的详细说明 1、内部密钥的派生 对于每一个明文信息，其加密过程要给定一个56位的密钥K来确定明密文块的对应关系，16个内部密钥K（1），K（2），K（16）如何由给定的密钥K（外部密钥）产生，其过程如下：28位 外部密钥K=K1 K2K64 置换选择1 PC-1 C0 D0循环左移h（1）位循环左移h（1）位 C1 D1循环左移h（2）位循环左移h（2）位 置换选择2 PC-2 48位28位56位 56位K(1)内部
30、密钥产生过程28位 C2 D2PC-2.C15 D15循环左移h（16）位循环左移h（16）位 C16 D16置换选择2 PC-2 48位56位循环左移h（2）位循环左移h（2）位 48位K(2)K(15)K(16)置换选择2 PC-2表1 对应不同i的左循环移位位数 说说 明：明：（1）外部密钥，K=K1K2K3K64是64bit,但其中K8,K16,K24,K32,K40,K48,K56,K64这8位是奇偶校验位，在进入置换选择1之前就已被去掉了。（2）置换选择1 C-1的作用是将外部密钥剩下的56位分成两个部分，称 为左半部分C0和右半部分D0，各具28位。具体分割算法如下：选 代 次数
31、i12345678910111213141516左 移 位数h（i）1122222212222221 左半部分 C0=K57 K49 K41 K33 K25 K17 K9 K1 K58 K50 K42 K34 K26 K18 K10 K2 K59 K51 K43 K35 K27 K19 K11 K3 K60 K52 K44 K36 右半部分 D0=K63 K55 K47 K39 K31 K23 K15 K7 K62 K54 K46 K38 K30 K22 K14 K6 K61 K53 K45 K37 K29 K21 K13 K5 K28 K20 K12 K4 分划的规则是什么呢？我们用下面的方
32、法来描述它的分划原则：将外部密钥K=K1 K2K64的各位排成8行8列的矩阵。K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K25 K27 K28 K29 K30 K31 K32 K33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48 K49 K50 K51 K52 K53 K54 K55 K56 K57 K58 K59 K60 K61 K62 K63 K64 （3）C0和D0生成后，生成
33、K（1）按如下步骤进行：（a）将C0 和D0各循环左移h（1）=1位，分别得到C1和D1。（b）通过置换选择2（PC-2），将56位的向量（C1，D1）变成48位的密钥向量 K（1）。（4）置换选择2（PC-2）假设C=c1c2c28 ，D=d29d30d56 ，去掉c9，c18，c22，c25，d35，d38，d43，d54，然后按下表置换：14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50
34、36 29 32 得K（1）=c14 c17 c11 c24 c1 c5 c3 c28 c15 c6 c21 c10 c23 c19 c12 c4 c26 c8 c16 c7 c27 c20 c13 c2 d41 d52 d31 d37 d47 d55 d30 d40 d51 d45 d33 d48 d44 d49 d39 d56 d34 d53 d46 d42 d50 d36 d29 d32（5）Ci-1 和D i-1生成后，生成K（i）的步骤与（3）相同（a）将Ci-1 和D i-1各循环左移h（i）位，分别得到Ci 和 D i左移位数h（i）随着i的不同，而有所差异（见表1）（b）通过置
35、换选择2将56位的向量（Ci D i）变换成48位的密钥向量K（i）K（i）=K1（i）K2（i）K24（i）K25（i）K48（i）。DES进入加密算法之前，首先必须将内部密钥K（1），K（16）派生 出来。2、初始置换IP：初始置换的作用是将64位的明文块 X 分成两部分，左半部分L（0）和右半部分R（0），每一部分均匀为32位。具体分法是：L（0）=X58 X50 X42 X34 X26 X18 X10 X2 X60 X52 X44 X36 X28 X20 X12 X4 X62 X54 X46 X38 X30 X22 X14 X6 X64 X56 X48 X40 X32 X24 X16
36、X8 R（0）=X57 X49 X41 X33 X25 X17 X9 X1 X59 X51 X43 X35 X27 X19 X11 X3 X61 X53 X45 X37 X29 X21 X13 X5 X63 X55 X47 X39 X31 X23 X15 X7 分割的规则是什么呢？亦即如何确定L（0）和R（0）各是由些什么位组成，按什么样的次序组成呢？下面介绍生成L（0）和R（0）的方法。R(0)X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15 X16 X17 X18 X19 X20 X21 X22 X23 X24 X25 X25 X27 X
37、28 X29 X30 X31 X32 X33 X34 X35 X36 X37 X38 X39 X40 X41 X42 X43 X44 X45 X46 X47 X48 X49 X50 X51 X52 X53 X54 X55 X56 X57 X58 X59 X60 X61 X62 X63 X64 L(0)L(0)3、逆初始置换（IP-1）两个32bit的预输出数据块R（16），L（16）要经过逆初始置换，才能产生出真正的64bit的密文块y=y1 y1y64。假设:R(16)=r1(16)r2(16)r32(16)，L(16)=l1(16)l2(16)l32(16),简记作：R（16）=r1 r2
38、 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 r16 r17 r18 r19 r20 r21 r22 r23 r24 r25 r26 r27 r28 r29 r30 r30 r32 L（16）=l1 l2 l3 l4 l5 l6 l7 l8 l 9 l10 l11 l12 l13 l14 l15 l16 l17 l18 l19 l20 l21 l22 l23 l24 l25 l26 l27 l28 l29 l30 l31 l32 l8 r8 l16 r16 l24 r24 l32 r32 l7 r7 l15 r15 l23 r23 l31 r31
39、l6 r6 l14 r14 l22 r22 l30 r30 l5 r5 l13 r13 l21 r21 l29 r29 l4 r4 l12 r12 l20 r20 l28 r28 l3 r3 l11 r11 l19 r19 l27 r27 l2 r2 l10 r10 l18 r18 l26 r26 l1 r1 l9 r9 l17 r17 l25 r25 初始置换与逆初始置换的比较初始置换与逆初始置换的比较：（1）将X按行的自然递增次序逐位填入8*8矩阵的各行中。（2）在矩阵中按照从下至上的方式依次取出2、4、6、8列中的元素构成左半部L（0）的32bit。（3）在矩阵中按照从下至上的方式依次取
40、出1、3、5、7列中的元素构成右半部R（0）的32bit。初始置换：明文块X=X1X2X64 L（0）,R（0）逆初始置换：R（16），L（16）密文块Y=y1y2 y64 (2)-1 将左半部R（16）的32bit按照（2）中取出的方式逐位还原填入矩阵的2、4、6、8列中；(3)-1 将右半部L（16）的32bit按照（3）中取出的方式逐位还原填入矩阵的1、3、5、7列中。(1)-1 将8*8矩阵中的元素按照行的自然递增顺序逐位取出。由上述可见，逆初始置换是初始置换的逆变换。gK(i)(R(i-1)=Pi-1(B)R(i)=L(i-1)P(B)A=E(R(i-1)K(i)R（i-1）E扩展
41、E（R（i-1）K(i)S8 S1 B P(B)L(i)=R(i-1)L(i-1)-32位32位48位48位48位32位32位32位三、加密函数g的详细说明 1、E扩展 R(i-1)是32位，E扩展将它扩展为48位的E(R(i-1)，其扩展方法如下：设R(i-1)=r1r2r3 r31r32 将其分成8组，每4位一组（每一组扩展成6位）。r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 r16 r32 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 r4 r5 r8 r9 r12 r13
42、r16 r17 r17 r18 r19 r20 r21 r22 r23 r24 r25 r26 r27 r28 r29 r30 r31 r32r16 r17 r18 r19 r20 r21 r22 r23 r24 r25 r26 r27 r28 r29 r30 r31 r20 r21 r24 r25 r28 r29 r32 r1 则E(R(i-1)=r32 r1 r2 r3 r4 r5 r6 r7 r8 r9 r8 r9 r10 r11 r12 r13 r14 r15 r16 r17 r16 r17 r18 r19 r20 r21 r22 r23 r24 r25 r24 r25 r26 r27
43、 r28 r29 r30 r30 r32 r1 2、替代运算（S盒）S1盒 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8S1 2 4 1 1 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 1、P置换（移位变换）设B=b1b2 b32 则P（B）=b16 b7 b20 b21 b29 b12 b28 b17 b1
44、b15 b23 b26 b5 b18 b31 b10 b2 b8 b24 b14 b32 b27 b3 b9 b19 b13 b30 b6 b22 b11 b4 b25 DESDES解脱密算解脱密算一、一、DESDES脱密算法脱密算法 （1）初始置换：是将一个64bit的数据块分成两个32位的数据块。（2）逆初始置换：是将两个32位的数据合并成一个64位的数据块合并的方法是（例如XL XR）逆初始置换是初始置换的逆变换。X 初始置换 逆初始置换XLXRX （3）每一圈输出与输入的关系：每一圈中输出对输入的一个函数依赖关系。由于（1）式，故（2）式又可写成：R（i）=L（i-1）gK（16）（L
45、（i-1）（2）进行第一圈脱密时，使用密钥K(16)，则L(16)经过变换后的输出应该是：R（16）gk(16)(L(16)（由脱密过程的框图的第一圈知）由加密算法中得出的（2）式可知有关系式：R（16）=L(15)gK（16）（R（15）=L(15)gK（16）(L(16)由异或运算的性质（若A B=C则B C=A，A C=B）可得。L（i）=R（i-1）（i=1，2，16）（1）R（i）=L（i-1）gK（16）（R（i-1）（2）g g R（16）L（16）密文块y=y1y2 y64 初始置换 L（15）R（15）K(16)K(15)L（14）R（14）DES脱密算法 R（1）L（0）R
46、（0）L（0）逆初始置换逆初始置换 L（1）g L（14）R（14）明文快明文快X=xX=x1 1x x2 2xxn nK(1)R（0）5.5.公开密钥密码体制公开密钥密码体制5.1 5.1 公开密钥密码体制概论公开密钥密码体制概论 一、公钥密码体制 公开密码体制具有以下的特征：（1）用户必须能够有效地计算公开的和秘密的密钥对，PK和SK。（2）如果不知道SK，那么即使知道PK，算法E和D以及密文Y，确定明文 X的计算也是不可行的。（3）继加密之后再脱密，应还原出原来的明文X，即：DSK（EPK（X）=X （*）上式对EPK域中的全部X都成立。E EPKPK（D DSKSK （X X）=X =
47、X （*）公钥密码体制有以下特点：密钥分发简单。秘密保存的密钥量减少。可以满足互不相识的人之间的私人谈话的保密性要求。可以完成数字签名。（以后解释）二、两种密码体制的差异 1、算法：公钥密码体制的算法容易用精确的数学术语描述。它建立在特定的已知数学问题上，安全性依赖于这种数学问题的求解是计算上不可能的。与此相对，传统密码体制的算法以复杂紊乱的数学方程为基础。虽然求解单个方程并不困难，但由于它被多次迭代和搅乱，以至无法用解析法求解。2、密钥：这两种密码体制的密钥产生方式也不同。在传统密码体制中，加密密钥和解密密钥可以简单的互相推导，因此它们是以简单的方法随机选择的。在公开密钥密码体制中，由公开密
48、钥不能简单地推出秘密密钥。秘密密钥是按照特定的要求选择的，而公开密钥又是由秘密密钥利用确定的步骤有效地计算出来的。5.2 RSA5.2 RSA密码体制和预备知识密码体制和预备知识 一、数论的基本性质：一、数论的基本性质：定义定义1 1：只能被1和它自身整除，而不能被其它正整数整除的大于1的正整数称为素数（质数）素数（质数）。定理定理1 1：设a 和r 是两个整数，r0 则必有二整数 q 及i 存在，使得 a=qr+i 0 i r定理定理2 2：设a 和 b是两个整数，且(a,b)=d (d是a与b的最大公因数)则存在整数 s 和 t使得 d=sa+tb。定理定理3 3(素因数分解定理)：每个大
49、于1的正整数恰有一种方法表示成素数的乘积（不计素数因子出现的先后次序）。二、同余的概念及基本性质：二、同余的概念及基本性质：定义定义2 2：如果两个整数a和b的差a-b能被另一个整数r整除，即r/a-b,则称 a,b 关于模r 同余，用符号ab(modr)表示。（即a和b有相同的余数）。若ab(modr)即a-b=mr.即a=b+mr 也就是说a,b被r除时余数相同。显然同余关系是一个等价关系，即 自反的：aa(modr)对称的：若ab(modr),则ba(modr)可传递的：如果ab,bc(modr),则ac(modr)推论推论1 1：如果ab(modr),则对于任意正整数n,anbn(mo
50、dr)推论推论2 2：如果ab(modr),则对于任意整数c，acbc(modr)定理定理4 4：如果 a1b1(modr),a2b2(modr),an bn(modr)则 a1a2anb1b2bn(modr)定理定理5 5：对于任意的整数a和m及任意的正整数n，有an(a+mr)n (modr)命题1：若cacb(modr)且(c,r)=1,则ab(modr)定理（按模计算原理）：设a1和a2为整数，op表示二元操作符,，则(a1opa2)modr=(a1 modr)op(a2 modr)modr 其中amodr表示a被r除后的余,amodr=resr(a)定理定理6 6：若(a,r)=1,
