公钥密码-信息安全概论课件

信息安全与保密概论

第五章

公钥密码学信息安全与保密概论

第五章

1起源公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126起源公钥密码又称为双钥密码和非对称密码，是1976年由Dif2公开密钥密码的重要特性加密与解密由不同的密钥完成 加密:XY:Y=EKU(X) 解密:YX:X=DKR(Y)=DKR(EKU(X))知道加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密 X=DKR(EKU(X))=EKU(DKR(X))公开密钥密码的重要特性加密与解密由不同的密钥完成3基于公开密钥的加密过程基于公开密钥的加密过程4基于公开密钥的鉴别过程基于公开密钥的鉴别过程5

用公钥密码实现保密用户拥有自己的密钥对(KU,KR)公钥KU公开,私钥KR保密AB:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X用公钥密码实现保密用户拥有自己的密钥对(KU,KR)6

用公钥密码实现鉴别条件:两个密钥中任何一个都可以用作加密而另一个用作解密鉴别: AALL:Y=DKRa(X) ALL:EKUa(Y)=EKUa(DKRa(X))=X鉴别+保密: AB:Z=EKUb(DKRa(X)) B:EKUa(DKRb(Z))=X用公钥密码实现鉴别条件:两个密钥中任何一个都可以用作加7

公钥密钥的应用范围加密/解密数字签名(身份鉴别)密钥交换算法加/解密数字签名密钥交换RSA是是是Dieffie-Hellman否否是DSS否是否公钥密钥的应用范围加密/解密算法加/解密数字签名密钥交换8基本思想和要求涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换基本思想和要求涉及到各方：发送方、接收方、攻击者9陷门单向函数单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fk(x)是容易的；(2)给定y,计算x使x=fk-1(y)是不可行的。(3)存在k’，已知k’时,对给定的任何y，若相应的x存在，则计算x使x=fk’-1(y)是容易的。陷门单向函数单向陷门函数是满足下列条件的函数f：10

公钥密码基于的数学难题

背包问题大整数分解问题（TheIntegerFactorizationProblem,RSA体制）有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem,ElGamal体制）椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,类比的ElGamal体制）公钥密码基于的数学难题

背包问题11数学基础同余：给定任意整数a和m，以q除a，余数是r，则可以表示为a=sm+r,0r<m，其中s=[a/m],表示小于a/m的最大整数。定义r为amodm的剩余，记为ramodq.若整数a和b有(amodm)=(bmodm)，则称a与b在modm下同余。同余关系的性质：（1）为等价关系，即具有自反性，对称性和可传递性自反性：aamodm对称性：若abmodm，则bamodm传递性：若abmodm且bcmodm，则acmodm数学基础同余：12同余（2）同余式可以进行运算若abmodm，cdmodm，则a+cb+dmodm，acbdmodm，anbnmodm（3）若acbcmodm，且（c，m）＝d，则abmodm/d；特别的，若(c,m)=1，则abmodm（4）若m≥1，(a,m)=1，则存在c使得ac1modm，称c是a对模m的逆，记做a-1同余（2）同余式可以进行运算13同余（5）设a1和a2为任意整数，op为操作符，如＋、－等，则：

(a1opa2)modm=((a1modm)op(a2modm))modmeg.a1=23，a2=8，m=323＋8mod3＝31mod3＝1（23mod3＋8mod3）＝2＋2mod3＝123×8mod3＝184mod3＝1（23mod3×8mod3）＝2×2mod3＝1同余（5）设a1和a2为任意整数，op为操作符，如＋、－等，14同余（剩余）类假定m为正整数，任一整数除m得到的最小非负剩余必定为0，1，......，m-1中的一个，即任一整数对于模m必定与0，1，......，m-1中的某一个同余。因此，我们把全体整数分成若干两两不相交的集合，使得在同一个集合中的任意两个数对模m同余，而属于不同集合的两个数对模m一定不同余。每一个这样的集合称作关于模m的同余类。完全剩余系从模m的每一个同余类中任取一数就得到m个数，这m个数称作m的完全剩余系。如模4的一个完全剩余系{0，5，2，11}。通常选取的不大于m的m个非负整数集合{0，1，2，......，m-1}。同余类同余（剩余）类同余类15既约（互素）同余类和既约剩余系对于模m的同余类rmodm，如果(r,m)=1，则称该同余类是模m的既约同余类。在模m的一个完全剩余系中，所有与m互素的数的集合构成模m的既约剩余系。eg.m=5{0,1,2,3,4}{1,2,3,4}m=10{0,1,2,...9}{1,3,7,9}欧拉函数模m的所有既约同余类的个数记为φ(m)，通常称作Euler函数。eg.φ(5)＝4，φ(10)＝4欧拉函数既约（互素）同余类和既约剩余系欧拉函数16Euler函数和Euler定理p是素数，φ(p)=p-1若gcd(m,n)=1,则φ(mn)=φ(m)φ(n),特别地,若pq且都是素数,φ(pq)=(p-1)(q-1)

eg.φ(10)＝φ(2)φ(5)＝1×4＝4Euler定理：若(a,m)=1，则aφ(m)

≡1modm

eg.a＝7，m＝5，则74=72×72=4×4mod5＝1通过欧拉定理，可以求得a的逆a-1＝aφ(m)-1

modmEuler函数和Euler定理p是素数，φ(p)=p-117Euler定理若(a,m)=1，则aφ(m)

1modm证明:R={x1，x2，…，xφ(m)}为所有小于m且与m互素的正整数，即为一个既约剩余系，考虑集合S={ax1modm,ax2modm

，…，axφ(m)modm}

aximodm与m互素

aximodm与axjmodm不同余，其中i≠j:

axi=axjmodmxi=xjmodn

故S也是一个剩余系，那么ximodm=(aximodm)((axi))modm

(aφ(m)xi)modm

aφ(m)1modmEuler定理若(a,m)=1，则aφ(m)1mod18

Fermat小定理Fermat小定理:p素数,(a,p)=1,则:ap-1

1modp推论:p素数,a是任意整数,则:ap

amodp定理若(a,m)=1，则同余方程ax1modm有唯一的解eg.7x1mod5x=3,8,13,...证明：一定有解，因为aaφ(m)-11modm若有不同的解x1,x2，则ax1ax2modm由于(a,m)=1，则x1x2modm用于在RSA中计算密钥Fermat小定理Fermat小定理:p素数,(a,p)19

Euler定理推论推论:若m=pq,pq都是素数,k是任意整数,则 ak(p-1)(q-1)+1

amodm,对任意0a<m证明:若(a,m)＝1，φ(m)=(p-1)(q-1),由Euler定理有aφ(m)

1modm，所以有结论成立；

否则a必定是p或者q的倍数,不妨设a=sp,则0<s<q为正整数,a与q互素,由Euler定理得到:aφ(q)

1modq(aφ(q))kφ(p)

1modq

ak(p-1)(q-1)

=tq+1t是整数等式两边乘以a=sp,得到:ak(p-1)(q-1)+1=(tq+1)sp=tspq+spamodmEuler定理推论推论:若m=pq,pq都是素数,20

原根(primitiveroot)Euler定理表明,对两个互素的整数a,n, aφ(n)

1modn定义：素数p的原根定义：如果a是素数p的原根，则数 amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整数的某种排列。对任意的整数b且(b,p)=1，我们可以找到唯一的幂i满足b=aimodp0≦i≦(p-1)原根(primitiveroot)Euler定理表明21

离散对数若a是素数p的一个原根,则对任意整数b,

(b,p)=1,存在唯一的整数i,1i(p-1),使得:

baimodp

i称为b以a为基模p的指数(离散对数),记作inda,p(b).容易知道:

inda,p(xy)=[inda,p(x)+inda,p(y)]modφ(p)

inda,p(xr)=[rinda,p(x)]modφ(p)离散对数的计算:

ygxmodp已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的离散对数若a是素数p的一个原根,则对任意整数b,

(b,22经典例子Diffie-Hellman密钥交换算法背包算法RSA算法

经典例子Diffie-Hellman密钥交换算法23

Diffie-Hellman密钥交换允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程算法的安全性依赖于计算离散对数的难度素数p的原根定义：如果a是素数p的原根，则数 amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整数的某种排列。对任意的整数b，(b,p)=1,我们可以找到唯一的幂i满足 b=aimodp0<=i<=(p-1)i在离散对数算法中称为以a为基的指数modp。记为inda,p(b)Diffie-Hellman密钥交换允许两个用户可以安全24Diffie-Hellman密钥交换算法：双方选择素数p以及p的一个原根a用户A选择一个随机数Xa<p，计算Ya=aXamodp用户B选择一个随机数Xb<p，计算Yb=aXbmodp每一方保密X值，而将Y值交换给对方用户A计算出K=YbXamodp用户B计算出K=YaXbmodp双方获得一个共享密钥(aXaXbmodp)素数p以及p的原根a可由一方选择后发给对方Diffie-Hellman密钥交换算法：25

GeneraterandomXa<pCalculateYa=aXamodpGeneraterandomXb<pCalculateYb=aXbmodpUserAUserBYaYbCalculateK=(Yb)XamodpCalculateK=(Ya)XbmodpDiffie-HellmanKeyExchangeGeneraterandomGeneraterand26

Diffie-Hellman密钥交换的攻击中间人攻击图示ABK=aXaXoOK=aXbXoDiffie-Hellman密钥交换的攻击中间人攻击图示27

Diffie-Hellman密钥交换的攻击中间人攻击1双方选择素数p以及p的一个原根a(假定O知道)2A选择Xa<p,计算Ya=aXamodp,AB:Ya3O截获Ya,选Xo,计算Yo=aXomodp,冒充AB:Yo4B选择Xb<p,计算Yb=aXbmodp,BA:Yb5O截获Yb,冒充BA:Yo6A计算:(Xo)Xa(aXo)XaaXoXamodp7B计算:(Xo)Xb(aXo)XXbaXoXbmodp8O计算:(Ya)XoaXaXomodp,(Yb)XoaXbXomodpO无法计算出aXaXbmodpO永远必须实时截获并冒充转发,否则会被发现Diffie-Hellman密钥交换的攻击中间人攻击28

经典例子Diffie-Hellman密钥交换算法背包算法RSA算法

经典例子Diffie-Hellman密钥交换算法29背包问题

背包问题描述：给定重量分别为a1,a2,…an的n个物品,装入一个背包中,要求重量等于一个给定值，那么，究竟是那些物品？0-1背包问题：给定一个正整数S和一个背包向量A=(a1,…,an)，其中ai是正整数，求满足方程

S=∑aixi的二进制向量X=(x1,…,xn)。这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长背包问题

背包问题描述：给定重量分别为a1,a2,…an的n30背包问题用于公钥密码学做法：明文为X，S为密文奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解的背包问题修改成难解的背包问题公开密钥使用难解的背包问题私钥使用易解的背包问题背包问题用于公钥密码学做法：明文为X，S为密文31

易解的背包问题——超递增背包满足下列条件的背包 ai>∑aj(j=1,…,i-1)这样的背包也被称为超递增背包求解从最大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包结果为{2,3,13,52}所以，密文70对应的明文为110101易解的背包问题——超递增背包满足下列条件的背包32

转换背包简单背包用作私钥如何产生相应的公钥——转换做法：选择一个整数m>∑ai(i=1,…,n)然后选择一个与m互素的整数w，然后

ai'=wai(modm)(i=1,…,n)这里的ai'是伪随机分布的这样得到的背包是非超递增背包转换背包简单背包用作私钥33

基于背包问题的公钥密码系统

——MH公钥算法加密将明文分为长度为n的块X=(x1,…,xn)然后用公钥A'=(a1',…,an')，将明文变为密文S=E(X)=∑ai'

xi解密先计算S'=w-1Smodm再求解简单背包问题S'=∑aixi基于背包问题的公钥密码系统

——MH公钥算法加密34Eaxmple-从私钥计算公钥私钥{2,3,6,13,27,52}w=31,m=1052*31mod105=623*31mod105=936*31mod105=8113*31mod105=8827*31mod105=10252*31mod105=37公钥{62,93,81,88,102,37}Eaxmple-从私钥计算公钥私钥{2,3,6,13,27,35Eaxmple-加密消息=011000110101101110明文:011000背包:6293818810237密文:93+81=174011000对应于93+81=174110101对应于62+93+88+37=280101110对应于62+81+88+102=333Eaxmple-加密消息=01100011010110136Eaxmple-解密解密者知道{2,3,6,13,27,52},w,m计算w(w-1)=1mod(m)w-1=61密文为174,280,333174*61mod105=9=3+6,对应于011000280*61mod105=70=2+3=13+52,对应于110101333*61mod105=48=2+6+13+27,对应于101110因此,消息=011000110101101110Eaxmple-解密解密者知道{2,3,6,13,27,5237

背包密码系统的意义是第一个公钥密码系统有较好的理论价值在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷背包密码系统的意义是第一个公钥密码系统38

经典例子Diffie-Hellman密钥交换算法背包算法RSA算法

经典例子Diffie-Hellman密钥交换算法39

RSA算法1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布是一种分组加密算法。明文和密文在0~n-1之间,n是一个正整数应用最广泛的公钥密码算法只在美国申请专利，且已于2000年9月到期RSA算法1977年由RonRivest、AdiSh40

RSA算法描述

RSA加、解密算法(1978Rivest,Shamir,Adelman)

分组大小为k,2k<n2k+1公开密钥n(两素数p和q的乘积)（推荐p,q等长）e，满足（e，φ(n)）＝1（其中φ(n)=(p-1)(q-1)－保密）ed1(modφ(n))私人密钥d（e-1mod(p-1)(q-1))

加密c=memodn解密m=cdmodnRSA算法描述

RSA加、解密算法(1978Riv41

42

RSA密钥生成原理令n=pq,pq都是素数,(n)=(p-1)(q-1)是n的Euler数Euler定理推论:若n=pq,pq都是素数,k是任意整数,则

mk(p-1)(q-1)+1

mmodn,对任意0mn只要选择e,d,满足ed=k(n)+1,即

ed1mod(n)de-1mod(n)公钥:KU={e,n},私钥:KR={d,n}RSA密钥生成原理令n=pq,pq都是素数,(n)43

example（1）若Bob选择了p=7和q＝5（2）那么，n=35,(n)=6×4＝24；（3）然而24＝23×3，一个正整数e能用作加密指数，当且仅当e不能被2，3所整除。假设Bob选择了e=11，（4）那么用Euclidean算法将求得：d=e-1

11(mod24),于是Bob的解密密钥d=11.（5）Bob在一个目录中公开n=35和e=11（6）现假设Alice想发送明文2给Bob，她计算：211(mod35)=2526(mod35)=32*64=32*29=928(mod35)=18，且在一个信道上发送密文18。（7）当Bob接收到密文18时，他用他的秘密解密指数（私钥）d＝11进行解密：1811（mod35)=(18)2*5+1=182*182*182*182*182*18=9*9*9*9*9*18=11*11*162=16*22=352=2mod35example（1）若Bob选择了p=7和q＝544RSA安全性依据

RSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知(n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d.（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！！！）RSA安全性依据RSA的安全性是基于45

每个合数都可以唯一地分解出素数因子 6=2·3 999999=3·3·3·7·11·13·37 27641=131·121 从2开始试验每一个小于等于√27641的素数。素数：只能被1和它本身整除的自然数；否则为合数。整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次） 50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年每个合数都可以唯一地分解出素数因子素数：只能被1和它本身46对RSA的攻击方法

1、强力攻击（穷举法）：尝试所有可能的私有密钥2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解3、对RSA实现的攻击对RSA的攻击方法

1、强力攻击（穷举法）：尝试所有可能的私47对RSA的攻击对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。对RSA的选择密文攻击对RSA的公共模攻击对RSA的小加密指数攻击对RSA的小解密指数攻击时间性攻击：取决于解密算法的运算时间对RSA的攻击对RSA的具体实现存在一些攻击方法，但不是针对48对RSA的选择密文攻击例1：E监听A的通信，收集由A的公开密钥加密的密文c，E想知道消息的明文m,使m=cdmodn他首先选择随机数r,使r<n.然后用A的公开密钥e计算x=remodny=xcmodnt=r-1modn如果x=remodn，则r=xdmodn现在E让A对y签名，即解密y,A向E发送u=ydmodn而E计算tumodn=r-1ydmodn=r-1xdcdmodn=cdmodn=m对RSA的选择密文攻击例1：E监听A的通信，收集由A的公开密49对RSA的选择密文攻击例2：E让A对m3签名。他产生两个消息m1和m2，满足m3=m1m2(modn)如果E能让A分别对m1和m2签名，则可以计算m3：m3d=(m1dmodn)(m2dmodn)注意：不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数对RSA的选择密文攻击例2：E让A对m3签名。他产生两个50对RSA的公共模攻击一种可能的RSA实现方法是给每个人相同的n,但指数d和e不同。问题：如果相同的消息曾用两个不同的指数加密，而这两个指数是互素的，则明文可以不用任何一个解密密钥来恢复。令m为明文消息，两个加密密钥为e1，e2,两个密文消息为c1,c2c1=me1modnc2=me2modn由于e1和e2互素，所以可以用扩展的Euclid算法找到r,s使re1+se2=1,假设r是负数，可以用扩展的Euclid算法计算c1-1,而(c1-1)-r*c2s=mmodn注意:不要让一群用户共享一个模n对RSA的公共模攻击一种可能的RSA实现方法是给每个人相同的51

对RSA的小加密指数攻击如果使用一个较小的e值，则进行RSA签名和加密会很快，但也不安全。如果用相同e值的不同公开密钥加密e(e+1)/2个线性相关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。比如：消息为mj,使用同样的指数e,模数分别为q1,q2,…qs（两两互素）,则密文为mjemodq1，mjemodq2，…mjemodqs，根据中国剩余定理，m'=mjemodq1q2…qs.可以计算出来，对于较小的e，可以解出mj。解决办法：加密前将消息与随机值混合，并保证m与n有相同的长度。对RSA的小加密指数攻击如果使用一个较小的e值，则进行R52对RSA的小解密指数攻击使用较小的d会产生穷尽解密攻击的可能当d为n的1/4长度时，而e小于n时，可以恢复d，当e,d是随机选择的时，这种情况很少发生，当e很小时不会发生。注意：应选择一个大的d值对RSA的小解密指数攻击使用较小的d会产生穷尽解密攻击的可能53RSA密码体制的实现实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和(n)=(p-1)(q-1).(3)Bob选择一个随机数e(0<e<(n))，满足（e，(n)）＝1(4)Bob使用辗转相除法计算d=e-1(mod(n))(5)Bob在目录中公开n和e作为她的公开钥。选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0<m<n。加密P时，计算C＝Pe(modn)，解密C时计算P＝Cd(modn)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。RSA密码体制的实现实现的步骤如下：Bob为实现者54实现要求于是要求：若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC9796中规定n的长度位512比特位.至1996年，建议使用768位的模n。实现要求于是要求：若使RSA安全，p与q必为足够大的素数，使55素数的选取为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1和q-1分别含有大素因子p1和q1(3)P1-1和q1-1分别含有大素因子p2和q2(4)p+1和q+1分别含有大素因子p3和q3素数的选取为了抵抗现有的整数分解算法，对RSA模n的素因子56加密指数e的选取为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e＝216＋1，ISO/IEC9796中甚至允许取e＝3。这时加密速度一般比解密速度快10倍以上。

e＝216＋1优于e＝3之处在于它能够抵抗对RSA的小加密指数攻击加密指数e的选取为了提高加密速度，通常取e为特定的小整数，如57实现中的问题

（1）如何计算abmodn （2）如何判定一个给定的整数是素数？ （3）如何找到足够大的素数p和q?实现中的问题（1）如何计算abmodn58

(1)要点1：(axb)modn=[(amodn)x(bmodn)]modn]

要点2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的问题：am m的二进制表示为bkbk-1…b0,则m=2ii0c0;d1forikdownto0 doc2xc d(dd)modn ifbi=1 thencc+1 d(da)modnreturnd计算ammodnammodn=[

a(2i)]modn =[a(2i)modn]bi0bi0(1)更一般性的问题：ami0c0;d1计算a59检测素数直接判断一个整数是否为素数是困难的命题:如果p是素数,则方程 x2

1modp只有平凡解x1modp.证明:x2

1modp p|(x2-1) p|(x+1)(x-1) p|(x+1),或者p|(x-1) x+1=kp,或者x-1=jp,k,j是整数 x=kp-1,或者x=jp+1 x1modp,或者x

-1modp若方程x2

1modp存在的解不是x1，则P不是素数。检测素数直接判断一个整数是否为素数是困难的60

(2)目前还没有一个高效的办法，实际中应用最多MillerandRabin,WITNESS算法 WITNESS(a,n)判定n是否为素数，a是某些小于n的整数1.令bkbk-1…b0为(n-1)的二进制表示，2.d13.forikdownto04. doxd5. d(dd)modn6. ifd=1andx1andxn-17. thenreturnTRUE8. ifbi=19. thend(da)modn10.ifd111.thenreturnTRUE12.returnFALSE

返回值：TRUE:n一定不是素数FALSE:n可能是素数应用：随机选择a<n,计算s次，如果每次都返回FALSE，则这时n是素数的概率为 (1-1/2s)(2)目前还没有一个高效的办法，实际中应用最多1.令61

(3)通常的办法是随机选取一个大的奇数，然后进行素性检验1.随机选一个奇数n(如:可使用伪随机数发生器)2.随机选择一个整数a<n3.执行概率素数判定测试(如:用WITNESS(a,n)),如果n未测试通过,则拒绝数值n,转向步骤14.如果n已通过足够的测试,则接受n,否则转向步骤2;说明：①随机选取大约用ln(N)/2的次数，如ln(2200)/2=70②好在生成密钥对时才用到，慢一点还可忍受。 ③确定素数p和q以后，只需选取e,满足gcd(e,(n))=1,计算 d=e-1mod(n)（sieve扩展的欧拉算法）(3)通常的办法是随机选取一个大的奇数，然后进行素性检验62

信息安全与保密概论

第五章

公钥密码学信息安全与保密概论

第五章

63起源公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126起源公钥密码又称为双钥密码和非对称密码，是1976年由Dif64公开密钥密码的重要特性加密与解密由不同的密钥完成 加密:XY:Y=EKU(X) 解密:YX:X=DKR(Y)=DKR(EKU(X))知道加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密 X=DKR(EKU(X))=EKU(DKR(X))公开密钥密码的重要特性加密与解密由不同的密钥完成65基于公开密钥的加密过程基于公开密钥的加密过程66基于公开密钥的鉴别过程基于公开密钥的鉴别过程67

用公钥密码实现保密用户拥有自己的密钥对(KU,KR)公钥KU公开,私钥KR保密AB:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X用公钥密码实现保密用户拥有自己的密钥对(KU,KR)68

用公钥密码实现鉴别条件:两个密钥中任何一个都可以用作加密而另一个用作解密鉴别: AALL:Y=DKRa(X) ALL:EKUa(Y)=EKUa(DKRa(X))=X鉴别+保密: AB:Z=EKUb(DKRa(X)) B:EKUa(DKRb(Z))=X用公钥密码实现鉴别条件:两个密钥中任何一个都可以用作加69

公钥密钥的应用范围加密/解密数字签名(身份鉴别)密钥交换算法加/解密数字签名密钥交换RSA是是是Dieffie-Hellman否否是DSS否是否公钥密钥的应用范围加密/解密算法加/解密数字签名密钥交换70基本思想和要求涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换基本思想和要求涉及到各方：发送方、接收方、攻击者71陷门单向函数单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fk(x)是容易的；(2)给定y,计算x使x=fk-1(y)是不可行的。(3)存在k’，已知k’时,对给定的任何y，若相应的x存在，则计算x使x=fk’-1(y)是容易的。陷门单向函数单向陷门函数是满足下列条件的函数f：72

公钥密码基于的数学难题

背包问题大整数分解问题（TheIntegerFactorizationProblem,RSA体制）有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem,ElGamal体制）椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,类比的ElGamal体制）公钥密码基于的数学难题

背包问题73数学基础同余：给定任意整数a和m，以q除a，余数是r，则可以表示为a=sm+r,0r<m，其中s=[a/m],表示小于a/m的最大整数。定义r为amodm的剩余，记为ramodq.若整数a和b有(amodm)=(bmodm)，则称a与b在modm下同余。同余关系的性质：（1）为等价关系，即具有自反性，对称性和可传递性自反性：aamodm对称性：若abmodm，则bamodm传递性：若abmodm且bcmodm，则acmodm数学基础同余：74同余（2）同余式可以进行运算若abmodm，cdmodm，则a+cb+dmodm，acbdmodm，anbnmodm（3）若acbcmodm，且（c，m）＝d，则abmodm/d；特别的，若(c,m)=1，则abmodm（4）若m≥1，(a,m)=1，则存在c使得ac1modm，称c是a对模m的逆，记做a-1同余（2）同余式可以进行运算75同余（5）设a1和a2为任意整数，op为操作符，如＋、－等，则：

(a1opa2)modm=((a1modm)op(a2modm))modmeg.a1=23，a2=8，m=323＋8mod3＝31mod3＝1（23mod3＋8mod3）＝2＋2mod3＝123×8mod3＝184mod3＝1（23mod3×8mod3）＝2×2mod3＝1同余（5）设a1和a2为任意整数，op为操作符，如＋、－等，76同余（剩余）类假定m为正整数，任一整数除m得到的最小非负剩余必定为0，1，......，m-1中的一个，即任一整数对于模m必定与0，1，......，m-1中的某一个同余。因此，我们把全体整数分成若干两两不相交的集合，使得在同一个集合中的任意两个数对模m同余，而属于不同集合的两个数对模m一定不同余。每一个这样的集合称作关于模m的同余类。完全剩余系从模m的每一个同余类中任取一数就得到m个数，这m个数称作m的完全剩余系。如模4的一个完全剩余系{0，5，2，11}。通常选取的不大于m的m个非负整数集合{0，1，2，......，m-1}。同余类同余（剩余）类同余类77既约（互素）同余类和既约剩余系对于模m的同余类rmodm，如果(r,m)=1，则称该同余类是模m的既约同余类。在模m的一个完全剩余系中，所有与m互素的数的集合构成模m的既约剩余系。eg.m=5{0,1,2,3,4}{1,2,3,4}m=10{0,1,2,...9}{1,3,7,9}欧拉函数模m的所有既约同余类的个数记为φ(m)，通常称作Euler函数。eg.φ(5)＝4，φ(10)＝4欧拉函数既约（互素）同余类和既约剩余系欧拉函数78Euler函数和Euler定理p是素数，φ(p)=p-1若gcd(m,n)=1,则φ(mn)=φ(m)φ(n),特别地,若pq且都是素数,φ(pq)=(p-1)(q-1)

eg.φ(10)＝φ(2)φ(5)＝1×4＝4Euler定理：若(a,m)=1，则aφ(m)

≡1modm

eg.a＝7，m＝5，则74=72×72=4×4mod5＝1通过欧拉定理，可以求得a的逆a-1＝aφ(m)-1

modmEuler函数和Euler定理p是素数，φ(p)=p-179Euler定理若(a,m)=1，则aφ(m)

1modm证明:R={x1，x2，…，xφ(m)}为所有小于m且与m互素的正整数，即为一个既约剩余系，考虑集合S={ax1modm,ax2modm

，…，axφ(m)modm}

aximodm与m互素

aximodm与axjmodm不同余，其中i≠j:

axi=axjmodmxi=xjmodn

故S也是一个剩余系，那么ximodm=(aximodm)((axi))modm

(aφ(m)xi)modm

aφ(m)1modmEuler定理若(a,m)=1，则aφ(m)1mod80

Fermat小定理Fermat小定理:p素数,(a,p)=1,则:ap-1

1modp推论:p素数,a是任意整数,则:ap

amodp定理若(a,m)=1，则同余方程ax1modm有唯一的解eg.7x1mod5x=3,8,13,...证明：一定有解，因为aaφ(m)-11modm若有不同的解x1,x2，则ax1ax2modm由于(a,m)=1，则x1x2modm用于在RSA中计算密钥Fermat小定理Fermat小定理:p素数,(a,p)81

Euler定理推论推论:若m=pq,pq都是素数,k是任意整数,则 ak(p-1)(q-1)+1

amodm,对任意0a<m证明:若(a,m)＝1，φ(m)=(p-1)(q-1),由Euler定理有aφ(m)

1modm，所以有结论成立；

否则a必定是p或者q的倍数,不妨设a=sp,则0<s<q为正整数,a与q互素,由Euler定理得到:aφ(q)

1modq(aφ(q))kφ(p)

1modq

ak(p-1)(q-1)

=tq+1t是整数等式两边乘以a=sp,得到:ak(p-1)(q-1)+1=(tq+1)sp=tspq+spamodmEuler定理推论推论:若m=pq,pq都是素数,82

原根(primitiveroot)Euler定理表明,对两个互素的整数a,n, aφ(n)

1modn定义：素数p的原根定义：如果a是素数p的原根，则数 amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整数的某种排列。对任意的整数b且(b,p)=1，我们可以找到唯一的幂i满足b=aimodp0≦i≦(p-1)原根(primitiveroot)Euler定理表明83

离散对数若a是素数p的一个原根,则对任意整数b,

(b,p)=1,存在唯一的整数i,1i(p-1),使得:

baimodp

i称为b以a为基模p的指数(离散对数),记作inda,p(b).容易知道:

inda,p(xy)=[inda,p(x)+inda,p(y)]modφ(p)

inda,p(xr)=[rinda,p(x)]modφ(p)离散对数的计算:

ygxmodp已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的离散对数若a是素数p的一个原根,则对任意整数b,

(b,84经典例子Diffie-Hellman密钥交换算法背包算法RSA算法

经典例子Diffie-Hellman密钥交换算法85

Diffie-Hellman密钥交换允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程算法的安全性依赖于计算离散对数的难度素数p的原根定义：如果a是素数p的原根，则数 amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整数的某种排列。对任意的整数b，(b,p)=1,我们可以找到唯一的幂i满足 b=aimodp0<=i<=(p-1)i在离散对数算法中称为以a为基的指数modp。记为inda,p(b)Diffie-Hellman密钥交换允许两个用户可以安全86Diffie-Hellman密钥交换算法：双方选择素数p以及p的一个原根a用户A选择一个随机数Xa<p，计算Ya=aXamodp用户B选择一个随机数Xb<p，计算Yb=aXbmodp每一方保密X值，而将Y值交换给对方用户A计算出K=YbXamodp用户B计算出K=YaXbmodp双方获得一个共享密钥(aXaXbmodp)素数p以及p的原根a可由一方选择后发给对方Diffie-Hellman密钥交换算法：87

GeneraterandomXa<pCalculateYa=aXamodpGeneraterandomXb<pCalculateYb=aXbmodpUserAUserBYaYbCalculateK=(Yb)XamodpCalculateK=(Ya)XbmodpDiffie-HellmanKeyExchangeGeneraterandomGeneraterand88

Diffie-Hellman密钥交换的攻击中间人攻击图示ABK=aXaXoOK=aXbXoDiffie-Hellman密钥交换的攻击中间人攻击图示89

Diffie-Hellman密钥交换的攻击中间人攻击1双方选择素数p以及p的一个原根a(假定O知道)2A选择Xa<p,计算Ya=aXamodp,AB:Ya3O截获Ya,选Xo,计算Yo=aXomodp,冒充AB:Yo4B选择Xb<p,计算Yb=aXbmodp,BA:Yb5O截获Yb,冒充BA:Yo6A计算:(Xo)Xa(aXo)XaaXoXamodp7B计算:(Xo)Xb(aXo)XXbaXoXbmodp8O计算:(Ya)XoaXaXomodp,(Yb)XoaXbXomodpO无法计算出aXaXbmodpO永远必须实时截获并冒充转发,否则会被发现Diffie-Hellman密钥交换的攻击中间人攻击90

经典例子Diffie-Hellman密钥交换算法背包算法RSA算法

经典例子Diffie-Hellman密钥交换算法91背包问题

背包问题描述：给定重量分别为a1,a2,…an的n个物品,装入一个背包中,要求重量等于一个给定值，那么，究竟是那些物品？0-1背包问题：给定一个正整数S和一个背包向量A=(a1,…,an)，其中ai是正整数，求满足方程

S=∑aixi的二进制向量X=(x1,…,xn)。这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长背包问题

背包问题描述：给定重量分别为a1,a2,…an的n92背包问题用于公钥密码学做法：明文为X，S为密文奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解的背包问题修改成难解的背包问题公开密钥使用难解的背包问题私钥使用易解的背包问题背包问题用于公钥密码学做法：明文为X，S为密文93

易解的背包问题——超递增背包满足下列条件的背包 ai>∑aj(j=1,…,i-1)这样的背包也被称为超递增背包求解从最大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包结果为{2,3,13,52}所以，密文70对应的明文为110101易解的背包问题——超递增背包满足下列条件的背包94

转换背包简单背包用作私钥如何产生相应的公钥——转换做法：选择一个整数m>∑ai(i=1,…,n)然后选择一个与m互素的整数w，然后

ai'=wai(modm)(i=1,…,n)这里的ai'是伪随机分布的这样得到的背包是非超递增背包转换背包简单背包用作私钥95

基于背包问题的公钥密码系统

——MH公钥算法加密将明文分为长度为n的块X=(x1,…,xn)然后用公钥A'=(a1',…,an')，将明文变为密文S=E(X)=∑ai'

xi解密先计算S'=w-1Smodm再求解简单背包问题S'=∑aixi基于背包问题的公钥密码系统

——MH公钥算法加密96Eaxmple-从私钥计算公钥私钥{2,3,6,13,27,52}w=31,m=1052*31mod105=623*31mod105=936*31mod105=8113*31mod105=8827*31mod105=10252*31mod105=37公钥{62,93,81,88,102,37}Eaxmple-从私钥计算公钥私钥{2,3,6,13,27,97Eaxmple-加密消息=011000110101101110明文:011000背包:6293818810237密文:93+81=174011000对应于93+81=174110101对应于62+93+88+37=280101110对应于62+81+88+102=333Eaxmple-加密消息=01100011010110198Eaxmple-解密解密者知道{2,3,6,13,27,52},w,m计算w(w-1)=1mod(m)w-1=61密文为174,280,333174*61mod105=9=3+6,对应于011000280*61mod105=70=2+3=13+52,对应于110101333*61mod105=48=2+6+13+27,对应于101110因此,消息=011000110101101110Eaxmple-解密解密者知道{2,3,6,13,27,5299

背包密码系统的意义是第一个公钥密码系统有较好的理论价值在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷背包密码系统的意义是第一个公钥密码系统100

经典例子Diffie-Hellman密钥交换算法背包算法RSA算法

经典例子Diffie-Hellman密钥交换算法101

RSA算法1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布是一种分组加密算法。明文和密文在0~n-1之间,n是一个正整数应用最广泛的公钥密码算法只在美国申请专利，且已于2000年9月到期RSA算法1977年由RonRivest、AdiSh102

RSA算法描述

RSA加、解密算法(1978Rivest,Shamir,Adelman)

分组大小为k,2k<n2k+1公开密钥n(两素数p和q的乘积)（推荐p,q等长）e，满足（e，φ(n)）＝1（其中φ(n)=(p-1)(q-1)－保密）ed1(modφ(n))私人密钥d（e-1mod(p-1)(q-1))

加密c=memodn解密m=cdmodnRSA算法描述

RSA加、解密算法(1978Riv103

104

RSA密钥生成原理令n=pq,pq都是素数,(n)=(p-1)(q-1)是n的Euler数Euler定理推论:若n=pq,pq都是素数,k是任意整数,则

mk(p-1)(q-1)+1

mmodn,对任意0mn只要选择e,d,满足ed=k(n)+1,即

ed1mod(n)de-1mod(n)公钥:KU={e,n},私钥:KR={d,n}RSA密钥生成原理令n=pq,pq都是素数,(n)105

example（1）若Bob选择了p=7和q＝5（2）那么，n=35,(n)=6×4＝24；（3）然而24＝23×3，一个正整数e能用作加密指数，当且仅当e不能被2，3所整除。假设Bob选择了e=11，（4）那么用Euclidean算法将求得：d=e-1

11(mod24),于是Bob的解密密钥d=11.（5）Bob在一个目录中公开n=35和e=11（6）现假设Alice想发送明文2给Bob，她计算：211(mod35)=2526(mod35)=32*64=32*29=928(mod35)=18，且在一个信道上发送密文18。（7）当Bob接收到密文18时，他用他的秘密解密指数（私钥）d＝11进行解密：1811（mod35)=(18)2*5+1=182*182*182*182*182*18=9*9*9*9*9*18=11*11*162=16*22=352=2mod35example（1）若Bob选择了p=7和q＝5106RSA安全性依据

RSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知(n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d.（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！！！）RSA安全性依据RSA的安全性是基于107

每个合数都可以唯一地分解出素数因子 6=2·3 999999=3·3·3·7·11·13·37 27641=131·121 从2开始试验每一个小于等于√27641的素数。素数：只能被1和它本身整除的自然数；否则为合数。整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次） 50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年每个合数都可以唯一地分解出素数因子素数：只能被1和它本身108对RSA的攻击方法

1、强力攻击（穷举法）：尝试所有可能的私有密钥2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解3、对RSA实现的攻击对RSA的攻击方法

1、强力攻击（穷举法）：尝试所有可能的私109对RSA的攻击对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。对RSA的选择密文攻击对RSA的公共模攻击对RSA的小加密指数攻击对RSA的小解密指数攻击时间性攻击：取决于解密算法的运算时间对RSA的攻击对RSA的具体实现存在一些攻击方法，但不是针对110对RSA的选择密文攻击例1：E监听A的通信，收集由A的公开密钥加密的密文c，E想知道消息的明文m,使m=cdmodn他首先选择随机数r,使r<n.然后用A的公开密钥e计算x=remodny=xcmodnt=r-1modn如果x=remodn，则r=xdmodn现在E让A对y签名，即解密y,A向E发送u=ydmodn而E计算tumodn=r-1ydmodn=r-1xdcdmodn=cdmodn=m对RSA的选择密文攻击例1：E监听A的通信，收集由A的公开密111对RSA的选择密文攻击例2：E让A对m3签名。他产生两个消息m1和m2，满足m3=m1m2(modn)如果E能让A分别对m1和m2签名，则可以计算m3：m3d=(m1dmodn)(m2dmodn)注意：不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数对RSA的选择密文攻击例2：E让A对m3签名。他产生两个112对RSA的公共模攻击一种可能的RSA实现方法是给每个人相同的n,但指数d和e不同。问题：如果相同的消息曾用两个不同的指数加密，而这两个指数是互素的，则明文可以不用任何一个解密密钥来恢复。令m为明文消息，两个加密密钥为e1，e2,两个密文消息为c1,c2c1=me1modnc2=me2modn由于e1和e2互素，所以可以用扩展的Euclid算法找到r,s使re1+se2=1,假设r是负数，可以用扩展的Euclid算法计算c1-1,而(c1-1)-r*c2s=mmodn注意:不要让一群用户共享一个模n对RSA的公共模攻击一种可能的RSA实现方法是给每个人相同的113

对RSA的小加密指数攻击如果使用一个较小的e值，则进行RSA签名和加密会很快，但也不安全。如果用相同e值的不同公开密钥加密e(e+1)/2个线性相关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。