[计算机软件及应用]5公开密钥算法

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

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

3、秘密密钥,如:2,3,6,13,27,52;n将其中每个值都乘以一个数n,对m求余,例如:n=31, m=105;n得到的序列作为公开密钥:62,93,81,88,102,37。()sjjijinM bM 1()sjjijinM bM 12021/3/135n加密:将明文分成长度与背包序列相同的块,计算背包总重量。n例如:背包62,93,81,88,102,37,明文011000,密文为:93+81=174n解密:n先计算n-1,为n关于模m的乘法逆元。n将密文的值与n-1模m相乘n用秘密的背包求解,得到明文n例:n=31, m=105, n-1=61, 174*61 mod 105=9=3+

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

5、=2+3+13+52 n 根据秘密密钥2,3,6,13,27,52n 明文:1101012021/3/138n例2:设背包公开密钥算法 的公开密钥为向量17,34,2,21,41,某消息M被加密后生成密文C=22,已知系统中模m=50,n=17,试对C解密求出M。n解:根据公开密钥17,34,2,21,41,求秘密密钥n1 * 17 mod 50=17n2 * 17 mod 50=34n6 * 17 mod 50= 2n13*17 mod 50=21n23*17 mod 50=41n 秘密密钥为1,2,6,13,23nn-1=3, C* n-1 mod 50=22*3 mod 50=16=1+

6、2+13n明文为:11010 2021/3/139n实际实现:n元素个数少的背包序列易解,实际的背包应该包括至少250个元素,超递增背包中每项应该有100到200位长,模200至400位长,不易解。2021/3/13105.3 RSA算法n第一个成熟的公开密钥算法,可以用作加密和数字签名n算法描述:nRSA的安全性基于大整数的因数分解的困难性n首先随机选择两个大素数p和q,计算n = pqn然后随机选择加密密钥e,满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d,使得ed 1 mod (p-1)(q-1)n公开密钥:e和nn秘密密钥:dn加密:C = Me mod nn

7、解密:M = Cd mod n2021/3/1311n例:已知 n=3337, e=79, M=6882326879666683n 求 C=?n解:n=pq=3337=47*71 p=47 q=71n (p-1)(q-1)=46*70=3220n d=e-1 mod 3220= 79-1 mod 3220=1019n 将明文3位一组,m1=688, m2=232, m3=687,n m4=966, m5=668, m6=003n 加密: c1= m1e mod n=68879 mod 3337=1570n 同理: c2=2756, c3=2091, c4=2276,n c5=2423, c6=

8、158n C=122762423158n 解密 : m1= c1d mod n= 15701019 mod 3337=6882021/3/1312nRSA算法用于数字签名:(见148页 7.1.6)n签名: S = Md mod n M:要签名的消息n验证签名: M = Se mod n e:公开密钥 d:秘密密钥2021/3/13135.4 其他公开密钥算法nRabin体制:安全性基于求模一个合数的平方根的困难性,等价于因数分解。nElGamal:安全性基于有限域内计算离散对数的困难性。n数字签名n加密2021/3/1314ElGamaln产生密钥:n一个素数p和两个随机数g,x,使g和x都

9、小于p。n计算y = gx mod pn公开密钥:y, g和p,g和p由一群用户共享n秘密密钥:x2021/3/1315nElGamal签名n产生签名:n选择一个随机数k,使k与p-1互素。n计算a = gk mod pn用扩展的Euclid算法求b,使M = (xa+kb) mod (p-1)n数字签名为a和b,k要保密。n验证签名:确认是否有yaab mod p = gM mod p2021/3/1316n例:选择p=11,g=2,秘密密钥x=8,M=5n 则 y=gx mod p=28 mod 11=3n 公开密钥为:y=3,g=2,p=11n产生签名:选择一个随机数k=9n gcd(k

10、,p-1)=gcd(9,10)=1 互素n计算:a=gk mod p=29 mod 11=6n用扩展Euclid算法求b: M=(xa+kb) mod (p-1)n 5=(6*8+9b) mod 10n 5=8+9b mod 10n 7=9b mod 10n b=7*9-1 mod 10=7*9 mod 10=3n 签名为:a=6,b=32021/3/1317n验证签名:n确认yaab mod p=gM mod p是否相等nyaab mod p= 3663 mod 11=10ngM mod p=25 mod 11=10n等式成立2021/3/1318nElGamal加密n加密M:n选择随机数k

11、,使k与p-1互素n计算a = gk mod p, b = ykM mod p, a和b为密文n解密:计算M = b/ax mod pnb/ax mod p = ykM/ax mod p = gkxM/gkx mod p = Mn上例:y=3,g=2,p=11,x=8,M=5,k=9n加密:a=gk mod p=29 mod 11=6n b=ykM mod p=39*5 mod 11=9n解密:M=b/ax mod p=9/68 mod 11=9/4 mod 11=9*3 mod 11=52021/3/13195.5 公开密钥数字签名算法n数字签名算法（DSA）nDSA变体nGOST数字签名算

12、法n离散对数签名体制2021/3/1320数字签名算法（DSA）n算法描述n参数:np:一个L位长的二进制素数,L从512到1024,是64的整数倍;nq:一个160位的p-1的素数因子;ng = h(p-1)/q mod p,其中h是小于p-1的任意数,且h(p-1)/q mod p1;nx:一个小于q的数;ny = gx mod p。np, q和g公开,可由一群用户共享n秘密密钥:x,公开密钥:y2021/3/1321n一个单向哈希函数H(M),为安全哈希算法（SHA）n签名:1.A产生一个比q小的随机数k;2.A计算 r = (gk mod p) mod q, s = (k-1(H(M)

13、+xr) mod q, r和s为签名。A向B发送r和s;3.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,则签名有效。n用预先计算加快速度nDSA的素数产生n使用DSA的ElGamal加密n用DSA进行RSA加密2021/3/13225.6 身份验证体制nFeige-Fiat-ShamirnGuillou-QuisquaternSchnorr2021/3/1323Feige-Fiat-Shamirn简化的Feige-Fiat-Shamir身份验证体制

14、:n仲裁人选择一个随机模n,为两个大素数的乘积n产生密钥:仲裁人选择一个数v,令v为模n的一个二次剩余即x2v( mod n),且v-1也存在。v为甲的公开密钥。计算s = sqrt(v-1) mod n的最小的s,为甲的秘密密钥。2021/3/1324n协议:1.甲方随机选取一个r,使r n。然后计算x = r2 mod n,将x发送给乙方;2.乙方向甲方发送一个随机位b;3.如果b = 0,则甲向乙发送r。如果b = 1,则甲向乙发送y = r*s mod n;4.如果b = 0,则乙验证x = r2 mod n,表明甲知道sqrt(x)。如果b = 1,则乙验证x = y2*v mod

15、n,表明甲知道sqrt(v-1)。n以上为一次鉴定。该协议重复t次,直到乙相信甲知道s为止。n甲能欺骗乙一次的机会为50%,能欺骗乙t次的机会为1/2t。n甲永远不能重复使用一个r值。2021/3/1325nFeige-Fiat-Shamir身份验证体制:n产生模n,为两个大素数的乘积。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为秘密密钥。n协议:1.甲选择一个随机数r,rn。计算x = r2 mo

16、d n,将x发送给乙;2.乙向甲发送一个随机的k位串:b1,b2,bk;3.甲计算y = r*(s1b1*s2b2*skbk) mod n,将y发送给乙;4.乙验证是否有x = y2*(v1b1*v2b2*vkbk) mod n。2021/3/1326n甲乙将这个协议重复t次,每次用一个不同的随机值r直到乙相信甲知道s1,s2,sk为止。n甲能欺骗乙的机会为1/2kt。n建议至少取k=5和t=4。n举例:n设模n=35,k=4。n公开密钥:4,11,16,29,秘密密钥:3,4,9,8。2021/3/1327n协议的一圈:1.甲选择一个随机数r = 16,计算x = 162 mod 35=11

17、,将11发送给乙;2.乙向甲发送一个随机的二进制串:1,1,0,1;3.甲计算y = 16*(31*41*90*81) mod 35=31,将31发送给乙;4.乙验证是否有312*(41*111*160*291) mod 35=11。2021/3/13285.7 密钥交换算法nDiffie-Hellmann点对点协议nShamir的三次通过协议n加密的密钥交换2021/3/1329Diffie-Hellmann是最早的公开密钥算法n用于分配密钥,但不能用于加密和解密n甲乙约定一个大素数n和一个数g,g为模n的生成元。g,n公开,可以共享。(gab mod n )n协议:n甲选择一个随机大整数x

18、,并向乙发送:X = gx mod nn乙选择一个随机大整数y,并向甲发送:Y = gy mod n2021/3/13303)甲计算:k = Yx mod n4)乙计算:k = Xy mod nnk = k = gxy mod n,为秘密的密钥n三方或多方的Diffie-Hellman体制nHughesn不用交换密钥的密钥交换2021/3/1331点对点协议n甲产生一个随机数x,将它发送给乙;n乙产生一个随机数y,用Diffie-Hellman协议计算基于x和y的共享密钥k。乙对x和y签名,并用k加密签名。然后将签名和y一起发送给甲:y, Ek(SB(x,y);n甲也计算k。将乙的消息的后面部分解密,并验证乙的签名。然后对一个由x, y组成的消息签名,并用共享密钥对签名进行加密,再发送给乙:Ek(SA(x,y);n乙解密消息,并验证甲的签名。2021/3/1332Shamir的三次通过协议n甲乙双方不用交换任何秘密密钥或公开密钥就可安全通信n一个可交换的对称密码:EA(EB(M)= EB(EA(M)n协议:n甲向乙发送 C1 = EA(M)=Me mod p;n乙向甲发送