计算机安全与保密5讲述.ppt

5 公开密钥算法 n概述 n背包算法 nRSA算法 n其他公开密钥算法 n公开密钥数字签名算法 n身份验证体制 n密钥交换算法 5.1 概述 n成对密钥的思想：一个加密密钥和一个解密密 钥，而从其中一个密钥推导出另外一个是不能 的 n混合密码系统：对称算法用于加密消息，公开 密钥算法用于加密密钥 n结论：公开密钥算法是不安全的，那些被认为 是安全的算法中，又有许多是不实用的 5.2 背包算法 n背包问题: 已知M1, M2, …, Mn和S, 求b1,b2,…,bn, bi{0,1}, 使S=b1M1+b2M2+…+bnMn （1：表示物体放入背包，0：表 示物体不放入背包） n背包算法的思想: 明文作为背包问题的解, 对应于bi, 密 文为重量和 n例：明文：0 1 1 0 1 0 n 背包：2 5 7 8 13 17 n 密文：5+7+13=25 n算法的关键：两个不同的背包问题，一个性时间 内 求解，一个不能性时间内求解 n超递增序列：其中每个元素都大于前面所有元素的和 n例：1，3，6，13，27，52…… n超递增背包：重量列表为一个超递增序列 n超递增背包的解法：对于i=n, n-1, …, 1 bi= 0 当 1 当 n秘密密钥：超递增背包问题的重量序列 n公开密钥：有相同解的一个一般背包问题的重量序列 n从秘密密钥建立公开密钥： n选择一个超递增序列作为秘密密钥，如：{2，3，6，13，27 ，52}； n将其中每个值都乘以一个数n，对m求余，例如：n=31, m=105； n得到的序列作为公开密钥：{62，93，81，88，102，37}。

n加密：将明文分成长度与背包序列相同的块， 计算背包总重量 n例如：背包{62，93，81，88，102，37}，明文 011000，密文为：93+81=174 n解密： n先计算n-1，为n关于模m的乘法逆元 n将密文的值与n-1模m相乘 n用秘密的背包求解，得到明文 n例：n=31, m=105, n-1=61, 174*61 mod 105=9=3+6, 明 文为011000 n例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 n例1：n=31,m=105,秘密密钥为{2，3，6，13， 27，52}，公开密钥：{62，93，81，88，102， 37}，密文C=280，求明文 n解： n-1=61 n C* n-1 mod 105=280*61 mod 105=70 n 70=2+3+13+52 n 根据秘密密钥{2，3，6，13，27，52} n 明文：110101 n例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=17 n2 * 17 mod 50=34 n6 * 17 mod 50= 2 n13*17 mod 50=21 n23*17 mod 50=41 n 秘密密钥为{1，2，6，13，23} nn-1=3, C* n-1 mod 50=22*3 mod 50=16=1+2+13 n明文为：11010 n实际实现： n元素个数少的背包序列易解，实际的背包应该包括 至少250个元素，超递增背包中每项应该有100到200 位长，模200至400位长，不易解 5.3 RSA算法 n第一个成熟的公开密钥算法，可以用作加密和数字签 名 n算法描述： nRSA的安全性基于大整数的因数分解的困难性 n首先随机选择两个大素数p和q，计算n = pq n然后随机选择加密密钥e，满足e与(p-1)(q-1)互素用扩展的 Euclid算法计算解密密钥d，使得ed  1 mod (p-1)(q-1) n公开密钥：e和n n秘密密钥：d n加密：C = Me mod n n解密：M = Cd mod n n例：已知 n=3337, e=79， M=6882326879666683 n 求 C=？ n解：n=pq=3337=47*71 p=47 q=71 n (p-1)(q-1)=46*70=3220 n d=e-1 mod 3220= 79-1 mod 3220=1019 n 将明文3位一组，m1=688, m2=232, m3=687, n m4=966, m5=668, m6=003 n 加密： c1= m1e mod n=68879 mod 3337=1570 n 同理： c2=2756， c3=2091， c4=2276， n c5=2423， c6=158 n C=15702756209122762423158 n 解密 ： m1= c1d mod n= 15701019 mod 3337=688 nRSA算法用于数字签名：(见148页 7.1.6) n签名： S = Md mod n M:要签名的消息 n验证签名： M = Se mod n e:公开密钥 d:秘密密钥 5.4 其他公开密钥算法 nRabin体制：安全性基于求模一个合数的平方根 的困难性，等价于因数分解。

nElGamal：安全性基于有限域内计算离散对数的 困难性 n数字签名 n加密 ElGamal n产生密钥： n一个素数p和两个随机数g，x，使g和x都小于p n计算y = gx mod p n公开密钥：y, g和p，g和p由一群用户共享 n秘密密钥：x nElGamal签名 n产生签名： n选择一个随机数k，使k与p-1互素 n计算a = gk mod p n用扩展的Euclid算法求b，使M = (xa+kb) mod (p-1) n数字签名为a和b，k要保密 n验证签名：确认是否有yaab mod p = gM mod p n例：选择p=11,g=2,秘密密钥x=8,M=5 n 则 y=gx mod p=28 mod 11=3 n 公开密钥为：y=3,g=2,p=11 n产生签名：选择一个随机数k=9 n gcd(k,p-1)=gcd(9,10)=1 互素 n计算：a=gk mod p=29 mod 11=6 n用扩展Euclid算法求b: M=(xa+kb) mod (p-1) n 5=(6*8+9b) mod 10 n 5=8+9b mod 10 n 7=9b mod 10 n b=7*9-1 mod 10=7*9 mod 10=3 n 签名为：a=6,b=3 n验证签名： n确认yaab mod p=gM mod p是否相等 nyaab mod p= 3663 mod 11=10 ngM mod p=25 mod 11=10 n等式成立 nElGamal加密 n加密M： n选择随机数k，使k与p-1互素 n计算a = gk mod p, b = ykM mod p, a和b为密文 n解密：计算M = b/ax mod p nb/ax mod p = ykM/ax mod p = gkxM/gkx mod p = M n上例：y=3,g=2,p=11,x=8,M=5,k=9 n加密：a=gk mod p=29 mod 11=6 n b=ykM mod p=39*5 mod 11=9 n解密：M=b/ax mod p=9/68 mod 11=9/4 mod 11=9*3 mod 11=5 5.5 公开密钥数字签名算法 n数字签名算法（DSA） nDSA变体 nGOST数字签名算法 n离散对数签名体制 数字签名算法（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 p>1； nx：一个小于q的数； ny = gx mod p。

np, q和g公开，可由一群用户共享 n秘密密钥：x，公开密钥：y n一个单向哈希函数H(M)，为安全哈希算法（SHA） n签名： •A产生一个比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，则签名有效 n用预先计算加快速度 nDSA的素数产生 n使用DSA的ElGamal加密 n用DSA进行RSA加密 5.6 身份验证体制 nFeige-Fiat-Shamir nGuillou-Quisquater nSchnorr Feige-Fiat-Shamir n简化的Feige-Fiat-Shamir身份验证体制： n仲裁人选择一个随机模n，为两个大素数的乘积 n产生密钥：仲裁人选择一个数v，令v为模n的一个二 次剩余即x2v( mod n)，且v-1也存在v为甲的公开 密钥。

计算s = sqrt(v-1) mod n的最小的s，为甲的秘 密密钥 n协议： –甲方随机选取一个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) n以上为一次鉴定该协议重复t次，直到乙相信甲知 道s为止 n甲能欺骗乙一次的机会为50%，能欺骗乙t次的机会 为1/2t n甲永远不能重复使用一个r值 nFeige-Fiat-Shamir身份验证体制： n产生模n，为两个大素数的乘积 n产生密钥：选择k个不同的数v1,v2,…,vk，其中各个vi为 一个模n的二次剩余即x2v( mod n) ，且vi-1存在这 串v1,v2,…,vk为公开密钥计算满足si = sqrt(vi-1) mod n 的最小的si，这一串s1,s2,…,sk为秘密密钥 n协议： –甲选择一个随机数r，r

计算x = r2 mod n，将x发送给乙 ； –乙向甲发送一个随机的k位串：b1,b2,…,bk； –甲计算y = r*(s1b1*s2b2*…*skbk) mod n，将y发送给乙； –乙验证是否有x = y2*(v1b1*v2b2*…*vkbk) mod n n甲乙将这个协议重复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} n协议的一圈： –甲选择一个随机数r = 16，计算x = 162 mod 35=1。