《公开密钥算法》PPT课件.ppt

《《公开密钥算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《公开密钥算法》PPT课件.ppt（34页珍藏版）》请在装配图网上搜索。

1、5 公开密钥算法,概述 背包算法 RSA算法 其他公开密钥算法 公开密钥数字签名算法 身份验证体制 密钥交换算法,5.1 概述,成对密钥的思想：一个加密密钥和一个解密密钥，而从其中一个密钥推导出另外一个是不能的。 混合密码系统：对称算法用于加密消息，公开密钥算法用于加密密钥。 结论：公开密钥算法是不安全的，那些被认为是安全的算法中，又有许多是不实用的。,5.2 背包算法,背包问题: 已知M1, M2, , Mn和S, 求b1,b2,bn, bi0,1, 使S=b1M1+b2M2+bnMn （1：表示物体放入背包，0：表示物体不放入背包） 背包算法的思想: 明文作为背包问题的解, 对应于bi,

2、密文为重量和。 例：明文：0 1 1 0 1 0 背包：2 5 7 8 13 17 密文：5+7+13=25 算法的关键：两个不同的背包问题，一个在线性时间内 求解，一个不能在线性时间内求解。 超递增序列：其中每个元素都大于前面所有元素的和 例：1，3，6，13，27，52 超递增背包：重量列表为一个超递增序列,超递增背包的解法：对于i=n, n-1, , 1 bi= 0 当 1 当 秘密密钥：超递增背包问题的重量序列 公开密钥：有相同解的一个一般背包问题的重量序列 从秘密密钥建立公开密钥： 选择一个超递增序列作为秘密密钥，如：2，3，6，13，27，52； 将其中每个值都乘以一个数n，对m求

3、余，例如：n=31, m=105； 得到的序列作为公开密钥：62，93，81，88，102，37。,加密：将明文分成长度与背包序列相同的块，计算背包总重量。 例如：背包62，93，81，88，102，37，明文011000，密文为：93+81=174 解密： 先计算n-1，为n关于模m的乘法逆元。 将密文的值与n-1模m相乘 用秘密的背包求解，得到明文 例：n=31, m=105, n-1=61, 174*61 mod 105=9=3+6, 明文为011000,例1：n=31,m=105,秘密密钥为2，3，6，13，27，52，公开密钥：62，93，81，88，102，37，密文C=280，求

4、明文。 例2：设背包公开密钥算法 的公开密钥为向量17，34，2，21，41，某消息M被加密后生成密文C=22，已知系统中模m=50，n=17，试对C解密求出M。,例1：n=31,m=105,秘密密钥为2，3，6，13，27，52，公开密钥：62，93，81，88，102，37，密文C=280，求明文。 解： n-1=61 C* n-1 mod 105=280*61 mod 105=70 70=2+3+13+52 根据秘密密钥2，3，6，13，27，52 明文：110101,例2：设背包公开密钥算法 的公开密钥为向量17，34，2，21，41，某消息M被加密后生成密文C=22，已知系统中模m=

5、50，n=17，试对C解密求出M。 解：根据公开密钥17，34，2，21，41，求秘密密钥 1 * 17 mod 50=17 2 * 17 mod 50=34 6 * 17 mod 50= 2 13*17 mod 50=21 23*17 mod 50=41 秘密密钥为1，2，6，13，23 n-1=3, C* n-1 mod 50=22*3 mod 50=16=1+2+13 明文为：11010,实际实现： 元素个数少的背包序列易解，实际的背包应该包括至少250个元素，超递增背包中每项应该有100到200位长，模200至400位长，不易解。,5.3 RSA算法,第一个成熟的公开密钥算法，可以用作

6、加密和数字签名 算法描述： RSA的安全性基于大整数的因数分解的困难性 首先随机选择两个大素数p和q，计算n = pq 然后随机选择加密密钥e，满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d，使得ed 1 mod (p-1)(q-1) 公开密钥：e和n 秘密密钥：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=3220 d=e-1 mod 3220= 79-1 mod 32

7、20=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 C=15702756209122762423158 解密 ： m1= c1d mod n= 15701019 mod 3337=688,RSA算法用于数字签名：(见148页 7.1.6) 签名： S = Md mod n M:要签名的消息 验证签名： M = Se mod n e:公开密钥 d:秘密密钥

8、,5.4 其他公开密钥算法,Rabin体制：安全性基于求模一个合数的平方根的困难性，等价于因数分解。 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要保密。 验证签名：确认是否有yaab mod p = gM

9、 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=9 gcd(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 10 5=8+9b mod 10 7=9b mod 10 b=7*9-1 mod 10=7*9 mod 10=3 签名为：a=6,b=3,验证签名： 确认yaab mod p=gM mod p是否相等 yaab

10、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=6 b=ykM mod p=39*5 mod 11=9 解密：M=b/ax mod p=9/68 mod 11=9/4 mod

11、 11=9*3 mod 11=5,5.5 公开密钥数字签名算法,数字签名算法（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产生一个比q小的随机数k； A计算

12、 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.6 身份验证体制,Feige-Fiat-Shamir Guillou-Quisquater Schnorr,Feige-Fiat-Shamir,简化的Feige-Fi

13、at-Shamir身份验证体制： 仲裁人选择一个随机模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

14、n，表明甲知道sqrt(v-1)。 以上为一次鉴定。该协议重复t次，直到乙相信甲知道s为止。 甲能欺骗乙一次的机会为50%，能欺骗乙t次的机会为1/2t。 甲永远不能重复使用一个r值。,Feige-Fiat-Shamir身份验证体制： 产生模n，为两个大素数的乘积。 产生密钥：选择k个不同的数v1,v2,vk，其中各个vi为一个模n的二次剩余即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发送给乙；

15、乙向甲发送一个随机的k位串：b1,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、 = 16*(31*41*90*81) mod 35=31，将31发送给乙； 乙验证是否有312*(41*111*160*291) mod 35=11。,5.7 密钥交换算法,Diffie-Hellman 点对点协议 Shamir的三次通过协议 加密的密钥交换,Diffie-Hellman,是最早的公开密钥算法 用于分配密钥，但不能用于加密和解密 甲乙约定一个大素数n和一个数g，g为模n的生成元。g，n公开，可以共享。(gab mod n ) 协议： 甲选择一个随机大整数x，并向乙发送：X = gx mod n 乙选择一个随机大整数y，并向甲发送：Y = gy mod n,甲计算：k = Yx

17、 mod n 乙计算：k = Xy mod n k = 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的

18、三次通过协议,甲乙双方不用交换任何秘密密钥或公开密钥就可安全通信 一个可交换的对称密码：EA(EB(M)= EB(EA(M) 协议： 甲向乙发送 C1 = EA(M)=Me mod p; 乙向甲发送 C2 = EB(EA(M); 甲对C2解密，发送给乙：C3 = DA(EB(EA(M) = DA(EA(EB(M) =C2d mod p; 乙解密C3，恢复M。 P:大素数 e:加密密钥 p-1与e互素 de1 mod (p-1) d是e关于模p-1的乘法逆元,练习,1. 已知RSA密码体制的公开密钥为n = 51，e = 11，试加密明文M1 = 3。通过分解n破译该密码，并对密文C2 = 6解

19、密。 2. 设n=35,公开密钥为9,4,11,29,秘密密钥为2,3,4,8,补充用Feige-Fiat-Shamir 协议进行一圈身份验证的过程。 (1)甲选择一个随机数r=11，计算 ，并发送给乙； (2)乙向甲发送一个随机的二进制串：1，0，1，0； (3)甲计算 发送给乙； (4)乙验证是否有 。,3. 设n = 11, g = 2, x = 3, y = 2，写出甲乙双方用Diffie-Hellman算法约定密钥的过程。 4.设p=11，甲的加密密钥e1=3，乙的加密密钥e2=9，写出甲乙双方用shamir的三次通过协议传输明文M=4的过程。 5.已知：超递增序列为2，3，6，13，27，52 m=105,n=31,密文C=333，求明文。 6.设背包公开密钥算法的公开密钥为向量(27,54,35,97,21)，某消息M被加密后生成密文C=10，已知系统中模m=100,n=27,试对C解密求出M。,