《网络安全加密技术》

1、9.1 对称加密体制对称加密体制-DES教材教材5.3 密码学基本原理密码学基本原理6.3 加密技术加密技术 p134DES简介简介第一个也是最重要的现代对称加密算法。第一个也是最重要的现代对称加密算法。1977.1 美国国家标准局，非国家安全级保美国国家标准局，非国家安全级保密数据，用于银行保护资金转帐安全。密数据，用于银行保护资金转帐安全。5年年+3*5使用期使用期分组密码分组密码 每一分组称为一个消息每一分组称为一个消息 M=C=0,164 K=0,156 9.1.1 数据加密标准数据加密标准-DESDES算法总描述：算法总描述：对输入分组进行对输入分组进行固定固定的初始置换的初始置换I

2、P将下面的运算迭代将下面的运算迭代16轮轮 Li= R i-1 R i= L i-1 f(R i-1, Ki ) 1.16轮迭代结果输入到轮迭代结果输入到IP的逆置换。的逆置换。kiFesitel密码密码9.1.1 数据加密标准数据加密标准DESDES-2（核心）：16轮迭代，一轮迭代过程如下图：R i 1(32比特比特)扩展运算扩展运算E48比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PR i (32比特比特)48比特寄存器比特寄存器 子密钥子密钥Ki异或异或(48比特比特)32比特寄存器比特寄存器 L i 1(32比特比特)L i(32比特比特)L i = Ri-1R i

3、 = Li-1 F(Ri-1, Ki )F轮函数9.1.1 数据加密标准数据加密标准-DESDES的核心：消息的随机非线性分布的核心：消息的随机非线性分布 第第i轮轮, f(R i-1, Ki )做下面两个子运算做下面两个子运算 Ri-1（32b）扩展置换运算扩展置换运算(48b)异或异或 ki（56b）收缩置换运算（收缩置换运算（48b） 8个代换盒（个代换盒（S盒），盒）， S盒非线性置换函数盒非线性置换函数 8个个S盒盒 （8*6b 8*4b） 6b地址（地址（1 6b 行行 2 3 4 5b 列列 ） S盒该位置数盒该位置数字数字字数字4b 。例例 第一组第一组011011 对应：对应

4、：S 盒盒S1第一行第一行13列的数字列的数字 S盒盒 4行行*16列列 每行是每行是0-15的一个排列的一个排列 S盒的非线性对盒的非线性对DES的安全非常重要的安全非常重要9.1.1 数据加密标准数据加密标准DES F函数函数-1:扩展运算扩展运算E: P28 E表，表， 标出比特位的读出顺序，其中标出比特位的读出顺序，其中16位被读了两次（位被读了两次（32-48） F函数函数-2：与子密钥（：与子密钥（Ki 48位）的异或运算位）的异或运算 F函数函数-3：选择压缩运算：选择压缩运算(S), P29 8个个S盒盒（4*16） 48位被分成位被分成8组组,每组每组6位位 ，每组对应一个，

5、每组对应一个S盒，盒， 1，6 位确定在位确定在S盒中的盒中的行数行数，2,3,4,5确定确定列数列数，根据，根据行列位置在行列位置在S盒中选取给该盒中选取给该位置对应的数字位置对应的数字（0-15），），得到得到4位位的二元组的二元组.例子例子 F函数函数-4：置换表：置换表PE盒扩展运算盒扩展运算E321234545678912131415161716171819202120212223242524252627282928293031321S1 ，S2S8盒选择函数盒选择函数 s1行/列0123456789101112131415014413121511831061259071015741

6、4213110612119538241148136211151297310503512824917511314100613S盒运算举例 假设假设r i-1经过扩展运算，并与经过扩展运算，并与Ki异或得到异或得到48位二进制数位二进制数 ，分为八组：分为八组：011011 110110 111000 010010 000011 010101 110011 110110输入输入8个个S盒。盒。第一组第一组011011 对应对应S 盒盒S11、6位组成二进制数：位组成二进制数：01 -1 确定在确定在S1中行数中行数12 3 4 5位位 1101-13 确定列数确定列数13在在S1盒盒1行行13列的

7、数字是列的数字是5，换为二进制，换为二进制4位：位：0101。注意：所有注意：所有S盒中的数字都小于等于盒中的数字都小于等于15，相当于，相当于4位二进位二进制数（制数（15-1111），），实现实现6位（位置：行位（位置：行 列）向列）向4位内容位内容的转换的转换9.1.2 DES的核心S盒的非线性对盒的非线性对DES的安全非常重要的安全非常重要代换密码是非线性的，移位密码仿射密码线性代换密码是非线性的，移位密码仿射密码线性线性密码减小密钥空间，对差分分析的脆弱线性密码减小密钥空间，对差分分析的脆弱例差分分析攻击仿射密码例差分分析攻击仿射密码DES的安全性的安全性密钥长度较短：密钥长度较短：

8、 穷举（强力）测试穷举（强力）测试 利用已知明文和密文消息对利用已知明文和密文消息对解决方法：不同密钥加密解决方法：不同密钥加密-解密解密-加密三重加密三重DES方案方案DES的短密钥弱点的短密钥弱点90 年代变明显：年代变明显：1998.7.15 250,000 $,构造构造DES解密高手，解密高手，56个小时成个小时成功找到密码。功找到密码。9.2 公钥密码体制公钥密码体制 公钥密码体制是密码公钥密码体制是密码 史上一次革命史上一次革命。 编码系统基于数学中的单向陷门函数编码系统基于数学中的单向陷门函数 采用了两个不同的密钥，对在公开网络上进采用了两个不同的密钥，对在公开网络上进行保密通信

9、、密钥分配、数字签名和认证有行保密通信、密钥分配、数字签名和认证有深远影响。深远影响。内容内容 公钥密码体制的基本原理公钥密码体制的基本原理 RSA算法算法 重点重点9.2 .1 公钥密码体制基本原理公钥密码体制基本原理 对称密码体制的一个缺点：双双如何建立会密对称密码体制的一个缺点：双双如何建立会密钥话；密钥分配成本高钥话；密钥分配成本高。尤其是对公开网络的尤其是对公开网络的电子商务安全应用。电子商务安全应用。 1976年，年，Diffie 和和Hellman提出：提出：密码学利用密码学利用NP复杂性理论复杂性理论；陷门单向函数陷门单向函数 单向函数单向函数：一个函数：一个函数f 对定义域上

10、任意一个对定义域上任意一个x, f(x)容易计算；但对容易计算；但对f值域上的任意值域上的任意y, f-1(y)都都在计算上不可行。在计算上不可行。 陷门单向函数陷门单向函数：单向函数：单向函数f(x)，如果进一步如果进一步给定某些辅助信息（如解密密钥），计算给定某些辅助信息（如解密密钥），计算f-1(y)又变得容易。又变得容易。9.2.1 公钥密码体制基本原理公钥密码体制基本原理 可信单向函数举例：可信单向函数举例： 假设假设n是两个是两个大素数大素数p和和q 的乘积，分解的乘积，分解n 是是一个非常困难的问题（一个非常困难的问题（NP-完全问题）。完全问题）。 设设b是一个正整数，定义函数

11、是一个正整数，定义函数f: ZnZn, f(x)=x b mod n , f是一个单向函数。是一个单向函数。但知道但知道n的因子是的因子是p或或q时时，计算，计算f-1是容易，因而是容易，因而f是是陷门陷门单向函数。单向函数。 秘密的秘密的陷门陷门被嵌在单向函数求逆问题中。这被嵌在单向函数求逆问题中。这个陷门信息就是私人密钥。个陷门信息就是私人密钥。9.2.2 RSA算法算法 1978年，年，Rivest Shamir和和Adleman 三人最早三人最早实现实现Diffie和和 Hellman的想法。的想法。 RSA算法安全：算法安全： 利用陷门单向函数的一种利用陷门单向函数的一种可逆可逆模指

12、数模指数运算，安全性基于大整数分解因子的困运算，安全性基于大整数分解因子的困难性。难性。9.2.2 RSA算法算法-描述描述 建立建立RSA密码体制的过程密码体制的过程 选择两个大素数选择两个大素数p ,q 计算乘积计算乘积n=pq 和和 (n) = (p-1)(q-1) 选择大于选择大于1小于小于 (n) 的随机数的随机数e,使得使得gcd(e, (n) )=1 计算计算d 使得使得 de=1 mod( (n) ) 对每一个密钥对每一个密钥k=(n,p,q,d,e),定义加密变换为：定义加密变换为：Ek(x)=xe mod n, 解密变换为：解密变换为：Dk(x)=yd mod n,这里这里

13、x,y Zn; 以以e,n为公开密钥，为公开密钥， p,q,d为私有密钥为私有密钥 。陷门陷门9.2.2 RSA算法算法-描述描述 如上建立一个明文如上建立一个明文空间空间P和密文和密文空间空间C为为P=C= Zn,密钥空间为密钥空间为K=n,p,q,d,e:n=pq，p和和q是大素数，是大素数，1e,d (n) :de=1 mod (n) 的的RSA密码体制。密码体制。9.2.2 RSA算法算法-正确性正确性 RSA算法基础（算法基础（解密正确性证明解密正确性证明-欧拉定理）欧拉定理） 对任意的对任意的e Zn *,有有e (n) =1 mod n, 其中其中Zn*=x Zn | gcd(n

14、,x)=1,函数函数 是欧拉函数。是欧拉函数。 由于选择的由于选择的ed=1 mod (n) 所以所以 ed=k (n) +1 Cd = Med = M k (n) +1=( M (n) k *M M mod n9.2.2 RSA算法算法-实例实例RSA算法实例：算法实例：P=7,q=17;N=pq=7*17=119 ， (n) =(p-1)(q-1) =(7-1)(17-1)=96； 选择随机整数选择随机整数5 (n) ,且与且与96互素；互素；求出求出d, de=1 mod 96, 得到得到d=77,因为因为77*5=96*4+1；输入明文输入明文M=19,计算计算C=Me=195=66

15、mod 119接收密文接收密文C=66,解密计算解密计算M=Cd=6677=19 mod119实际计算中实际计算中p,q,n,e,d要大得多。要大得多。9.2.2 RSA算法中的计算技巧 加密和解密运算。加密和解密运算。 模运算性质模运算性质(基础基础) ： (a b) mod n = (a mod n)(b mod n) mod n标准的标准的RSA要求要求p q是是128以上，以上，e,d也接近这样的也接近这样的数量级。数量级。 计算计算Me, e化成二进制形式化成二进制形式b kb k-1b0, e = bi 0 2i Me=M bi 0 2 i =(M bk)2M bk-1) 2 )

16、2 M b2)2M b1 )2M b0 例例 6677 mod 119 77=1*26+ 0*25 +1*23+1*22+1*20 = （(1*2+0)*2+)*2+1 6677 = ( ( (661)2*660)2)2*661 mod 1199.2.2 RSA算法中的计算技巧 构造构造Me mod n 的算法的算法d=1For i=k down to 0 do d=d2 mod n; if bi=1 then d=(d * m) mod n; return dMe=M bi 0 2 i =(M bk)2M bk-1) 2 ) 2 M b2)2M b1 )2M b09.2.2 RSA算法中的计

17、算技巧算法中的计算技巧-求逆求逆 从从e计算计算d, 其中其中gcd( (n) ,e)=1， 求求 d=e-1 mod (n) ，计算计算e mod (n) 的逆元的逆元 方法：推广的欧几里德算法。方法：推广的欧几里德算法。注注 xe+y (n) =1 mod (n) 扩展欧几里德算法不但能计算扩展欧几里德算法不但能计算(a,b)的最大公约的最大公约数，而且能计算数，而且能计算a模模b及及b模模a的乘法逆元。的乘法逆元。 int gcd(int a, int b , int& ar,int & br) int x1,x2,x3; int y1,y2,y3; int t1,t2,

18、t3; if(0 = a) /有一个数为有一个数为0，就不存在乘法逆，就不存在乘法逆元元 x1 = 1; x2 = 0; x3 = a; y1 = 0; y2 = 1; y3 = b; int k; for( t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3) k = x3 / y3; t2 = x2 - k * y2; t1 = x1 - k * y1; x1 = y1; x1 = y2; x2 x3 = y3; y1 = t1; y2 = t2; y3 = t3; if( y3 = 1) /有乘法逆元有乘法逆元 ar = y2; br = x1; return 1

19、; else /公约数不为公约数不为1，无乘，无乘法逆元法逆元 ar = 0; br = 0; return y3; 算法2 Function euclid(a,b:longint; var x,y:longint):longint;Var t:longint;Beginif b=0 then begineuclid:=a; x:=1; y:=0;endElsebegineuclid:=euclid(b,a mod b,x,y);t:=x; x:=y; y:=t-(a div b)*y;end;End; 例子：例子： 157 1 mod 2668=17 5-1 mod 96=-19 (-19+

20、96=77)9.2.3 RSA算法的安全性算法的安全性 安全：采用大的密钥，安全：采用大的密钥，e,d 的比特数越大越好，的比特数越大越好， 但加解密速度慢，二者之间但加解密速度慢，二者之间折中折中。 对对RSA算法的算法的攻击难度攻击难度相当于对模数相当于对模数n进行乘进行乘积因子分解。积因子分解。 目前目前密钥长度密钥长度界于界于1024 -2048比特之间，比特之间，RSA算法是安全的。算法是安全的。 RSA限制条件限制条件：素数：素数p q的长度不能相差太大，的长度不能相差太大，p-1,q-1都应该有大的素数因子，都应该有大的素数因子，gcd(p-1,q-1)应该偏小。应该偏小。9.2

21、.4 RSA试验试验试验目的：试验目的：掌握有关掌握有关RSA密码体制编程计算方法密码体制编程计算方法掌握使用特定的平台掌握使用特定的平台Vb, VC,Turbo c 对算法正确对算法正确编程调试正确运行。编程调试正确运行。实验报告分析编程的约束条件。实验报告分析编程的约束条件。实验过程及算法实验过程及算法 1 小程序过程：试除法判断大奇数小程序过程：试除法判断大奇数p是否素数是否素数 循环判断循环判断p是否能被一个小于是否能被一个小于p 的数（的数（2+奇数）整除，奇数）整除，如果被整除，如果被整除，p不是素数不是素数; 否则否则 循环数循环数+1，回到循环开，回到循环开头头 都不能整除，都不能整除，p 是素数是素数 2. 输入给出大素数输入给出大素数p1,p2, e ,判断判断e是否合法，计算是否合法，计算d 根