网络信息安全第三章-1课件

密钥必须秘密地分配如果密钥被损害了，攻击者就能解密所有消息，并可以假装是其中一方。密钥分配和管理

传统密钥管理两两分别用一对密钥时，则当用户量增大时密钥空间急剧增大如: n=100时C(100,2)=4,995 n=5000时C(5000,2)=12,497,500公钥密码体制的基本原理对称密码体制的缺点

数字签名用户选择一对密钥Ke和Kd，分别为公钥和私钥，并构造加密算法Ee

和解密算法Ed

。公钥密码算法

C=E(M,Ke)M=D(C,Kd)=D(E(M,Ke),Kd)用户公开Ke和Ee

密钥都是成对生成的，由一个公钥和一个私钥组成。注意：公钥密码的基本思想加密算法E解密算法D加密密钥Ke解密密钥Kd明文m明文m公开，其他用户可以像查找电话号码一样查到公开密钥加密方法1用户A用户BCKeBKdBA查到B的公开加密钥KeB,用它加密M后得到C,将C发给B，B收到C以后，用自己保密的解密钥KdB解密C,得到明文M查找找到KeB

方法1缺点任何人都能够冒充用户A给B发消息，B无法察觉用户A用户BCKeBKdB查找找到KeB用户C此消息对用户A可能不利结论方法1无法保证信息的真实性公开密钥加密方法2用户A用户BCKdAKeA查找找到KeAA用自己保密的密钥KdA加密M,得到密文C，将C发给B，B收到C以后，查A的公开加密钥KeA,用KeA解密C后得到明文M。

方法2缺点用户A用户BCKdAKeA查找找到KeA用户C截获密文用户C获取了明文结论方法2无法保证信息的秘密性A用自己保密的密钥KdA加密M,得到中间密文S查到B的公开加密钥KeBA用KeB加密S得到CA发C给BS=D(M,KdA)C=E(S,KeB)用户AB用自己保密的密钥KdB解密C,得到中间密文SB接收C用KeA解密S得到M查到A的公开加密钥KeA用户BD(C,KdB)=SE(S,KeA)=M保证了数据的秘密性和真实性结论单项函数单向函数是满足下列条件的函数f(1)给定x，计算y=f(x)是容易的(2)给定y,计算x使y=f(x)是困难的

(所谓计算x=f-1(Y)困难是指计算上相当复杂已无 实际意义)３大整数分解(FactorrizationProblme)

若已知两个大素数p,q，求n=p×q仅需一次乘法，但已知n求p,q则是几千年来数论专家的一道难题。４菲-赫尔曼(Diffie-Hellman）问题给定素数p，可构造一乘群Z*p，令α为Z*p的生成元，若已知αa,αb，求αab问题为菲-赫尔曼问题。５二次剩余问题给定一个奇合数n和整数a，决定是否a为modn平方剩余问题。

几个典型的公开钥密码系统菲-赫尔曼（Diffie-Hellman）密码系统RSA系统背包系统椭圆曲线密码体制RSA算法RSA公钥算法是由Rivest,ShamirAdleman在1978年提出来的。该算法的数学基础是初等数论中的Euler(欧拉)定理,并建立在大整数因子的困难性之上。RSA算法起源欧拉定理

aφ(m)≡1modm

其中,φ(m)是比m小，且与m互素的正整数个数。

若整数a和m互素，则素数

一个大于1的整数，如果它的正因数只有1和它本身，就叫做质数（素数），否则就叫做合数。素因子分解数n的因子分解是把它写成其它数的乘积

n=a×b×c素因子分解是把一个数写成素数的乘积形式

eg.91=7×13相对于把因子相乘得到一个数，进行一个数的因子分解是困难的。

例：利用Euclid算法求gcd(1694，917)

得gcd(1694，917)=7RSA算法描述选择两个素数p,q,对外界保密计算n=p*q计算Ø(n)=(p-1)(q-1)选择e,使它成为是Ø(n)的一个互质数确定d,使得d*e=1modØ(n),并且d<Ø(n)数字n应该为200位或者是一个更大的数字。这样，p和q都至少在100位。实际使用中，密钥至少要1024位。对于敏感信息，可以考虑2048位或者以上1.生成RSA密钥d为私钥，e为公钥，p、q不再需要，丢弃。例3.2p=43,q=59,n=pq=43×59=2537φ(n)=42×58=2436,e=13解：利用Euclid算法求d，解方程

d×e≡1mod2436。

对明文publickeyencryptions，用RSA算法求密文。（假定s=2）左右同时模2436，即937×13≡1mod2436即取e=13,d=937

设张小姐需要发送机密信息（明文）m=85给李先生，她已经从公开媒体得到了李先生的公开密钥（n，e）=（143，7），计算密文为：

c=memodn=857mod143=123

并发送给李先生。

李先生在收到密文c=123后，利用只有他自己知道的秘密密钥(d=103),计算：

m=cdmodn=123103mod143=85，所以，李先生可以得到张小姐发给他的真正的信息m=85。例题：例题：选择p=7,q=17N=pq=119,Ø(n)=(p-1)(q-1)=6*16=96选择随机整数e=5，与96互素找出d,使得d*e=1mod96,选择d=77算法C=MemodnM=Cdmodn选择明文19，C=195mod119=66密文66，M=6677mod119=19RSA算法的安全性对RSA算法的攻击实际上等效于对n的乘积分解。由于M=Cdmodn,n公开,则需要求出d由于de=1modØ(n),e已知需要求出Ø(n)由于Ø(n)=(p-1)(q-1)，所以必须求出p,qn=pq,所以必须对n进行分解

若n|（2n-2），则n为素数。若p为素数，则Mp=2p-1为素数

Fermat推测Fn=22n+1为素数,n为正整数RSA算法中的计算问题问题1.如何选取大的素数?×

素数在数轴上的分布情况是 如x=10,π(x)=4,该式所含的素数为2、3、5、7。问题2.有多少素数?

答案是有无穷多个。

素数位数

所含素数个数

64bit2.05×1017128bit1.9×1036256bit3.25×1074

①概率测试素数法问题3.如何产生一个素数?

方法：对于一个给定的大正整数N，每进行一次检验，给出yes：N为素数的概率为1/2，或者no：N不是素数，若N通过r次检验，则N不是素数的概率为ε=2-r

，则N为素数的概率为1-ε

，若r足够大(如r=100)，则几乎认为N是素数。

②确定性验证素数法定理令pi+1=hipi+1，若满足下述条件，则pi+1必为素数。

(1)pi是奇素数;(2)hi<4(pi+1),hi为偶数;(3)(4)幂剩余函数的特性周期性即反复运算C=Memodn

若干次后，将还原为最初始的M。

例如,p=17,q=11,n=pq=187,e=7,m=123。m1=123,1237≡183mod187m2=183,183+7≡72mod187m3=72,72+7≡30mod187m4=30,30+7≡123mod187

所谓安全素数p，应满足：(1)p是一个位数足够大的随机素数;(2)p-1含有一个大的素数因子r;(3)p+1含有一个大的素数因子;(4)r-1含有一个大的素数因子t。

安全素数(1)选择两个指定长度的奇数a,b。(2)在a附近产生随机素数s，在b附近产生随机素数t。(3)由t产生素数r：①r=1+2t;②若r非素数，则r=r+2直到r是素数。(4)由r,s生成p:①p=(sr-1-rs-1)mod(rs);②若p为偶数,则p=p+rs;③p=p+2rs直到p为素数。如何获得安全素数？高次幂的求模算法步骤如下：将e用二进制表示,e=kt,kt-1,…,k0,ki∈{0,1},0≤i≤t

c=1Fori=t~0

C=C2modp

若ki=1，则C=C(Mmodp)modpC=Memodp，已知M、e、p，如何求C？例，求117mod17RSA的实用性加密解密模型认证模型RSA算法和DES算法

加密体制。处理效率。密钥管理。安全性。应用。

设在一个有限域GF(P)上讨论，P为素数，令g∈GF(q)，g为非零元素，明文为m，密文为c。菲-赫尔曼（Diffie-Hellman）密码系统

(1)密钥的生成(用户A)

私钥：α,0<α<P

公钥：β≡gα

(2)加密

B

Amc

①B在区间［1,P-1］内选取一个随机数k,计算y=gkc=mβk=m(gα)k②找A的公钥,计算(3)解密A收到B的密文c后，计算

思考1.