《信息安全基础》由会员分享，可在线阅读，更多相关《信息安全基础（28页珍藏版）》请在金锄头文库上搜索。
1、5 公开密钥算法,概述 RSA算法 其他公开密钥算法 公开密钥数字签名算法 身份验证体制 密钥交换算法,5.1 概述,成对密钥的思想：一个加密密钥和一个解密密钥，而从其中一个密钥推导出另外一个是不能的。 混合密码系统：对称算法用于加密消息，公开密钥算法用于加密密钥。,5.2 RSA算法,第一个成熟的公开密钥算法，可以用作加密和数字签名 算法描述： RSA的安全性基于大整数的因数分解的困难性 首先随机选择两个大素数p和q，计算n = pq 然后随机选择加密密钥e，满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d，使得ed 1 mod (p-1)(q-1) 公开密钥：e和n
2、 秘密密钥：d 加密：C = Me mod n 解密：M = Cd mod n,例：已知 n=3337, e=79， M=6882326879666683求 C=？ 解：n=pq=3337=47*71 p=47 q=71(p-1)(q-1)=46*70=3220d=e-1 mod 3220= 79-1 mod 3220=1019将明文3位一组，m1=688, m2=232, m3=687,m4=966, m5=668, m6=003加密： c1= m1e mod n=68879 mod 3337=1570同理： c2=2756， c3=2091， c4=2276，c5=2423， c6=158
3、C=15702756209122762423158解密 ： m1= c1d mod n= 15701019 mod 3337=688,RSA算法用于数字签名：(见148页 7.1.6) 数字签名：手写签名来证明文件的原作者，或至少证明签名者同意文件的内容 签名的特性： 可信性：文件的接收者应该相信签名者慎重签署了该文件； 不可伪造性：能够证明是签名者本人，而不是别人慎重签署了该文件； 不可重用性：签名应该作为文件的一部分，任何人不能将该签名移动到别的文件上去； 不可更改性：任何人不能对签名后的文件内容进行更改； 不可否认性：签名及文件是客观存在的，签名者不能事后否认他签署过该文件。 RSA签名
4、： S = Md mod n M:要签名的消息 验证签名： M = Se mod n e:公开密钥 d:秘密密钥,5.3 ElGamal公开密钥算法,ElGamal：安全性基于有限域内计算离散对数的困难性。 数字签名 加密,ElGamal,产生密钥： 一个素数p和两个随机数g，x，使g和x都小于p。 计算y = gx mod p 公开密钥：y, g和p，g和p由一群用户共享 秘密密钥：x,ElGamal签名 产生签名： 选择一个随机数k，使k与p-1互素。 计算a = gk mod p 用扩展的Euclid算法求b，使M = (xa+kb) mod (p-1) 数字签名为a和b，k要保密。 验
5、证签名：确认是否有yaab mod p = gM mod p,例：选择p=11,g=2,秘密密钥x=8,M=5则 y=gx mod p=28 mod 11=3公开密钥为：y=3,g=2,p=11 产生签名：选择一个随机数k=9gcd(k,p-1)=gcd(9,10)=1 互素 计算：a=gk mod p=29 mod 11=6 用扩展Euclid算法求b: M=(xa+kb) mod (p-1)5=(6*8+9b) mod 105=8+9b mod 107=9b mod 10b=7*9-1 mod 10=7*9 mod 10=3签名为：a=6,b=3,验证签名： 确认yaab mod p=gM
6、 mod p是否相等 yaab mod p= 3663 mod 11=10 gM mod p=25 mod 11=10 等式成立,ElGamal加密 加密M： 选择随机数k，使k与p-1互素 计算a = gk mod p, b = ykM mod p, a和b为密文 解密：计算M = b/ax mod p b/ax mod p = ykM/ax mod p = gkxM/gkx mod p = M 上例：y=3,g=2,p=11,x=8,M=5,k=9 加密：a=gk mod p=29 mod 11=6b=ykM mod p=39*5 mod 11=9 解密：M=b/ax mod p=9/68
7、 mod 11=9/4 mod 11=9*3 mod 11=5,5.4 公开密钥数字签名算法,数字签名算法（DSA） DSA变体 GOST数字签名算法 离散对数签名体制,数字签名算法（DSA）,算法描述 参数： p：一个L位长的二进制素数，L从512到1024，是64的整数倍； q：一个160位的p-1的素数因子； g = h(p-1)/q mod p，其中h是小于p-1的任意数，且h(p-1)/q mod p1； x：一个小于q的数； y = gx mod p。 p, q和g公开，可由一群用户共享 秘密密钥：x，公开密钥：y,一个单向哈希函数H(M)，为安全哈希算法（SHA） 签名： A产生
8、一个比q小的随机数k； A计算 r = (gk mod p) mod q, s = (k-1(H(M)+xr) mod q, r和s为签名。A向B发送r和s； B验证签名：w = s-1 mod q, u1 = (H(M)*w) mod q, u2 = (r*w) mod q, v = (gu1*yu2) mod p) mod q, 如果v = r，则签名有效。 用预先计算加快速度 DSA的素数产生 使用DSA的ElGamal加密 用DSA进行RSA加密,5.5 身份验证体制,身份验证方法 Feige-Fiat-Shamir Guillou-Quisquater Schnorr,身份验证方法,
9、身份验证（Authentication）：当A登录进入邮件服务器、网上银行系统或其他类型的系统，系统需要通过某种方式来验证登录者的身份。 常用的一些身份验证方法： 使用物理标识：护照，驾驶执照、信用卡等 使用人体的生物特征：指纹、视网膜、及其他一些生物特征，或使用人脸识别技术、步态识别技术等 使用口令 使用单向函数：系统存储的是口令的单向函数值，而不是口令本身。容易受到词典攻击的威胁。 使用公钥密码 使用零知识证明协议,零知识证明,零知识： 设A和B是网络上的两个用户，A只想让B知道他掌握某件事，而不想让B知道这件事的内容。 称B对这件事具有零知识。 零知识证明（Zero-Knowledge
10、Proof）： 在协议中，用P（证明者）和V（验证者）分别代表用户A和B。P向V证明他确实具有一条信息，而又不告诉V用什么方法获取该信息。 证明采取相互作用协议的形式： P声称他知道某一条信息，V问P一系列有关该信息的问题，如果P真的知道这条信息，他就能正确回答所有的问题。 如果P不知道这条信息，那么，正确回答问题的概率只有50%。 回答若干个问题后，V就能确定P是否真的知道这条信息 所有这些问题及答案都不能向V提供任何有关P所具有的信息的内容。,洞穴图n次试验：P能够成功欺骗V的概率为1/2n,Feige-Fiat-Shamir,简化的Feige-Fiat-Shamir身份验证体制： 仲裁人
11、选择一个随机模n，为两个大素数的乘积 产生密钥：仲裁人选择一个数v，令v为模n的一个二次剩余即x2v( mod n)，且v-1也存在。v为甲的公开密钥。计算s = sqrt(v-1) mod n的最小的s，为甲的秘密密钥。,协议： 甲方随机选取一个r，使r n。然后计算x = r2 mod n，将x发送给乙方； 乙方向甲方发送一个随机位b； 如果b = 0，则甲向乙发送r。如果b = 1，则甲向乙发送y = r*s mod n； 如果b = 0，则乙验证x = r2 mod n，表明甲知道sqrt(x)。如果b = 1,则乙验证x = y2*v mod n，表明甲知道sqrt(v-1)。 以上
12、为一次鉴定。该协议重复t次，直到乙相信甲知道s为止。 甲能欺骗乙一次的机会为50%，能欺骗乙t次的机会为1/2t。 甲永远不能重复使用一个r值。,Feige-Fiat-Shamir身份验证体制： 产生模n，为两个大素数的乘积。 产生密钥：选择k个不同的数v1,v2,vk，其中各个vi为一个模n的二次剩余即存在x，x2v( mod n) ，且vi-1存在。这串v1,v2,vk为公开密钥。计算满足si = sqrt(vi-1) mod n的最小的si，这一串s1,s2,sk为秘密密钥。 协议： 甲选择一个随机数r，rn。计算x = r2 mod n，将x发送给乙； 乙向甲发送一个随机的k位串：b1
13、,b2,bk； 甲计算y = r*(s1b1*s2b2*skbk) mod n，将y发送给乙； 乙验证是否有x = y2*(v1b1*v2b2*vkbk) mod n。,甲乙将这个协议重复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 = 162 mod 35=11，将11发送给乙； 乙向甲发送一个随机的二进制串：1，1，0，1； 甲计算y = 16*(31*41*90*
14、81) mod 35=31，将31发送给乙； 乙验证是否有312*(41*111*160*291) mod 35=11。,5.6 密钥交换算法,Diffie-Hellman 点对点协议 Shamir的三次通过协议 加密的密钥交换,Diffie-Hellman,是最早的公开密钥算法 用于分配密钥，但不能用于加密和解密 甲乙约定一个大素数n和一个数g，g为模n的生成元。g，n公开，可以共享。 协议： 甲选择一个随机大整数x，并向乙发送：X = gx mod n 乙选择一个随机大整数y，并向甲发送：Y = gy mod n,甲计算：k = Yx mod n 乙计算：k = Xy mod n k =
15、k = gxy mod n，为秘密的密钥 三方或多方的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(M) 协议： 甲向乙发送 C1 = EA(M); 乙向甲发送 C2 = EB(EA(M); 甲对C2解密，发送给乙：C3 = DA(EB(EA(M) = DA(EA(EB(M); 乙解密C3，恢复M。 例如：可交换的对称密码 p:大素数 e:加密密钥 p-1与e互素 de1 mod (p-1) d是e关于模p-1的乘法逆元 C=M e mod p M=C d mod p,
