信息安全基础5公开密钥算法教学教案

5公开密钥算法概述RSA算法其他公开密钥算法公开密钥数字签名算法身份验证体制密钥交换算法5.1概述成对密钥的思想：一个加密密钥和一个解密密钥，而从其中一个密钥推导出另外一个是不能的。混合密码系统：对称算法用于加密消息，公开密钥算法用于加密密钥。5.2RSA算法第一个成熟的公开密钥算法，可以用作加密和数字签名算法描述：RSA的安全性基于大整数的因数分解的困难性首先随机选择两个大素数p和q，计算n=pq然后随机选择加密密钥e，满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d，使得ed

1mod(p-1)(q-1)公开密钥：e和n秘密密钥：d加密：C=Memodn解密：M=CdmodnRSA算法用于数字签名：(见148页7.1.6)数字签名：手写签名来证明文件的原作者，或至少证明签名者同意文件的内容签名的特性：可信性：文件的接收者应该相信签名者慎重签署了该文件；不可伪造性：能够证明是签名者本人，而不是别人慎重签署了该文件；不可重用性：签名应该作为文件的一部分，任何人不能将该签名移动到别的文件上去；不可更改性：任何人不能对签名后的文件内容进行更改；不可否认性：签名及文件是客观存在的，签名者不能事后否认他签署过该文件。RSA签名：S=MdmodnM:要签名的消息验证签名：M=Semodne:公开密钥d:秘密密钥5.3ElGamal公开密钥算法ElGamal：安全性基于有限域内计算离散对数的困难性。数字签名加密ElGamal产生密钥：一个素数p和两个随机数g，x，使g和x都小于p。计算y=gxmodp公开密钥：y,g和p，g和p由一群用户共享秘密密钥：xElGamal签名产生签名：选择一个随机数k，使k与p-1互素。计算a=gkmodp用扩展的Euclid算法求b，使M=(xa+kb)mod(p-1)数字签名为a和b，k要保密。验证签名：确认是否有yaabmodp=gMmodp例：选择p=11,g=2,秘密密钥x=8,M=5则y=gxmodp=28mod11=3公开密钥为：y=3,g=2,p=11产生签名：选择一个随机数k=9gcd(k,p-1)=gcd(9,10)=1互素计算：a=gkmodp=29mod11=6用扩展Euclid算法求b:M=(xa+kb)mod(p-1)5=(6*8+9b)mod105=8+9bmod107=9bmod10

b=7*9-1mod10=7*9mod10=3签名为：a=6,b=3验证签名：确认yaabmodp=gMmodp是否相等yaabmodp=3663mod11=10gMmodp=25mod11=10等式成立ElGamal加密加密M：选择随机数k，使k与p-1互素计算a=gkmodp,b=ykMmodp,a和b为密文解密：计算M=b/axmodpb/axmodp=ykM/axmodp=gkxM/gkxmodp=M上例：y=3,g=2,p=11,x=8,M=5,k=9加密：a=gk

modp=29mod11=6

b=ykMmodp=39*5mod11=9解密：M=b/axmodp=9/68mod11=9/4mod11=9*3mod11=55.4公开密钥数字签名算法数字签名算法（DSA）DSA变体GOST数字签名算法离散对数签名体制数字签名算法（DSA）算法描述参数：p：一个L位长的二进制素数，L从512到1024，是64的整数倍；q：一个160位的p-1的素数因子；g=h(p-1)/qmodp，其中h是小于p-1的任意数，且h(p-1)/qmodp>1；x：一个小于q的数；y=gxmodp。p,q和g公开，可由一群用户共享秘密密钥：x，公开密钥：y一个单向哈希函数H(M)，为安全哈希算法（SHA）签名：A产生一个比q小的随机数k；A计算r=(gkmodp)modq,s=(k-1(H(M)+xr))modq,r和s为签名。A向B发送r和s；B验证签名：w=s-1modq,u1=(H(M)*w)modq,u2=(r*w)modq,v=((gu1*yu2)modp)modq,

如果v=r，则签名有效。用预先计算加快速度DSA的素数产生使用DSA的ElGamal加密用DSA进行RSA加密5.5身份验证体制身份验证方法Feige-Fiat-ShamirGuillou-QuisquaterSchnorr身份验证方法身份验证（Authentication）：当A登录进入邮件服务器、网上银行系统或其他类型的系统，系统需要通过某种方式来验证登录者的身份。常用的一些身份验证方法：使用物理标识：护照，驾驶执照、信用卡等使用人体的生物特征：指纹、视网膜、及其他一些生物特征，或使用人脸识别技术、步态识别技术等使用口令使用单向函数：系统存储的是口令的单向函数值，而不是口令本身。容易受到词典攻击的威胁。使用公钥密码使用零知识证明协议零知识证明零知识：设A和B是网络上的两个用户，A只想让B知道他掌握某件事，而不想让B知道这件事的内容。称B对这件事具有零知识。零知识证明（Zero-KnowledgeProof）：在协议中，用P（证明者）和V（验证者）分别代表用户A和B。P向V证明他确实具有一条信息，而又不告诉V用什么方法获取该信息。证明采取相互作用协议的形式：P声称他知道某一条信息，V问P一系列有关该信息的问题，如果P真的知道这条信息，他就能正确回答所有的问题。如果P不知道这条信息，那么，正确回答问题的概率只有50%。回答若干个问题后，V就能确定P是否真的知道这条信息所有这些问题及答案都不能向V提供任何有关P所具有的信息的内容。洞穴图n次试验：P能够成功欺骗V的概率为1/2nCDBAFeige-Fiat-Shamir简化的Feige-Fiat-Shamir身份验证体制：仲裁人选择一个随机模n，为两个大素数的乘积产生密钥：仲裁人选择一个数v，令v为模n的一个二次剩余即x2

v(modn)，且v-1也存在。v为甲的公开密钥。计算s=sqrt(v-1)modn的最小的s，为甲的秘密密钥。协议：甲方随机选取一个r，使r<n。然后计算x=r2modn，将x发送给乙方；乙方向甲方发送一个随机位b；如果b=0，则甲向乙发送r。如果b=1，则甲向乙发送y=r*smodn；如果b=0，则乙验证x=r2modn，表明甲知道sqrt(x)。如果b=1,则乙验证x=y2*vmodn，表明甲知道sqrt(v-1)。以上为一次鉴定。该协议重复t次，直到乙相信甲知道s为止。甲能欺骗乙一次的机会为50%，能欺骗乙t次的机会为1/2t。甲永远不能重复使用一个r值。Feige-Fiat-Shamir身份验证体制：产生模n，为两个大素数的乘积。产生密钥：选择k个不同的数v1,v2,…,vk，其中各个vi为一个模n的二次剩余即存在x，x2

v(modn)，且vi-1存在。这串v1,v2,…,vk为公开密钥。计算满足si=sqrt(vi-1)modn的最小的si，这一串s1,s2,…,sk为秘密密钥。协议：甲选择一个随机数r，r<n。计算x=r2modn，将x发送给乙；乙向甲发送一个随机的k位串：b1,b2,…,bk；甲计算y=r*(s1b1*s2b2*…*skbk)modn，将y发送给乙；乙验证是否有x=y2*(v1b1*v2b2*…*vkbk)modn。甲乙将这个协议重复t次，每次用一个不同的随机值r直到乙相信甲知道s1,s2,…,sk为止。甲能欺骗乙的机会为1/2kt。建议至少取k=5和t=4。举例：设模n=35，k=4。公开密钥：{4，11，16，29}，秘密密钥：{3，4，9，8}。协议的一圈：甲选择一个随机数r=16，计算x=162mod35=11，将11发送给乙；乙向甲发送一个随机的二进制串：{1，1，0，1}；甲计算y=16*(31*41*90*81)mod35=31，将31发送给乙；乙验证是否有312*(41*111*160*291)mod35=11。5.6密钥交换算法Diffie-Hellman点对点协议Shamir的三次通过协议加密的密钥交换Diffie-Hellman是最早的公开密钥算法用于分配密钥，但不能用于加密和解密甲乙约定一个大素数n和一个数g，g为模n的生成元。g，n公开，可以共享。协议：甲选择一个随机大整数x，并向乙发送：X=gxmodn乙选择一个随机大整数y，并向甲发送：Y=gymodn甲计算：k=Yxmodn乙计算：k’=Xymodnk=k’=gxymodn，为秘密的密钥三方或多方的Diffie-Hellman体制Hughes不用交换密钥的密钥交换点对点协议甲产生一个随机数x，将它发送给乙；乙产生一个随机数y，用Diffie-Hellman协议计算基于x和y的共享密钥k。乙对x和y签名，并用k加密签名。然后将签名和y一起发送给甲：y,Ek(SB(x,y))；甲也计算k。将乙的消息的后面部分解密，并验证乙的签名。然后对一个由x,y组成的消息签名，并用共享密钥对签名进行加密，再发送给乙：Ek(SA(x,y))；乙解密消息，并验证甲的签名。Shamir的三次通过协议甲乙双方不用交换任何秘密密钥或公开密钥就可安全通信一个可交换的对称密码：EA(EB(M))=EB(EA(