非对称密码体制

1、信息安全概论2007年8月2022/7/291第4章 非对称密码体制 4.1 概述 4.2 RSA密码算法4.3 其它密码算法 2022/7/2924.1 概述4.1.1 对称密码面临的困难4.1.2 非对称密码的产生4.1.3 非对称密码体制4.1.4 单向函数2022/7/2934.1.1 对称密码面临的困难密钥的管理、分发与协商假设某个系统有N个用户相互进行保密通信，任意两个用户使用互不相同的密钥。密钥管理问题：每个用户需要保存N-1个密钥。（如果N非常大，如何解决？）密钥分发问题：系统总共需要N*(N-1)/2个密钥：例如N =1000时, 999 *1000/2 = 499500。密

2、钥协商问题：第一次协商好密钥后，以后可以通过当前密钥秘密发送新密钥。但第一次如何协商密钥？（用户秘密会面协商？陌生人怎么办？远距离怎么办？）消息发送者的身份确认问题2022/7/2944.1.2 非对称密码的产生非对称密码的发展历程计算机网络特别是Internet的发展，促使非对称密码的出现。1976年，Diffie和Hellman在密码学的新方向中提出来非对称密码的思想。（单向函数）1977年，RSA加密算法问世，名字来自3位作者Rivest, Shamir和Adleman。2022/7/2954.1.3 非对称密码体制密钥(PK, SK)公钥PK (Public Key)：通常公钥是公开的

3、，可以被任何实体通过有效渠道获取；私钥SK (Secret Key)：通常私钥是保密的，不能被任何实体通过非法渠道获取；加密器EK解密器DK密文明文明文PK密钥产生器SK2022/7/2964.1.3 非对称密码体制密码算法组成密钥生成KG( )：根据输入的安全参数 ，输出密钥对(PK, SK)。加密E( )：根据输入的公钥和消息，输出密文。解密D( )：根据输入的解密私钥和密文，算法输出消息或输出表示密文不合法的特殊符号“?”。2022/7/2974.1.3 非对称密码体制设计要求参与方容易通过计算产生一对密钥；在知道公开密钥和待加密消息的情况下，发送方A容易产生密文；接收方B使用私有密钥容

4、易通过计算解密所得密文，以便恢复原来的消息；敌手在知道公开密钥的情况下，确定私有密钥计算上不可行；敌手在知道公开密钥和密文的情况下，恢复消息计算上不可行；两个密钥中的任何一个可以用来加密，对应的另一个用来解密。2022/7/2984.1.3 非对称密码体制非对称密码的特点基于数学函数，而非替换和换位。加密密钥和解密密钥不同，且不能相互推理。解决了密码管理、身份认证和数字签名等问题。非对称密码的关键非对称密码的安全性主要取决于构造非对称算法所依赖的数学问题。要求加密函数具有单向性，即求逆的困难性。设计非对称密码体制的关键是寻求一个合适的单向函数。2022/7/2994.1.4 单向函数令函数f是

5、集A到集B的映射，以f：AB表示。若对任意x1x2，x1, x2A，有f(x1)f(x2)，则称f为单射，或1-1映射，或可逆的函数。f为可逆的充要条件是：存在函数g:BA，使对任意xA有gf(x)=x。一个可逆函数f：AB，若它满足：对所有xA，易于计算f(x)；对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“极为困难”是对现有的计算资源和算法而言。2022/7/29104.1.4 单向函数例一：令f是在有限域GF(p)中的指数函数，其中p是大素数，即 y = f(x) = ax。式中，xGF(p)，x为满足0 xp1的整

6、数，其逆运算是GF(p)中定义的对数运算，即 x=logay (0 xp1)由x求y：即使当p很大，也不难实现。为方便计算令a=2。例如p=2100时，需作100乘法。利用高速计算机由x计算ax可在0.1毫秒内完成。从ax计算x：当p=2100时，以平均速度的计算机进行计算需时约1010.7秒(1年=107.5秒，故约为1600年！其中假定存储量的要求能够满足)。2022/7/29114.1.4 单向陷门函数满足下列条件的函数f称为单向陷门函数：给定x，计算y = f(x)是容易的；给定y，计算x使y = f(x)是困难的；存在z，已知z时, 对给定的任何y，若相应的x存在，则计算x使y =

7、f(x)是容易的。两个难题陷门函数实际上不是单向函数，因为单向函数是在任何条件下求逆都是困难的；陷门可能不止一个，通过试验一个个陷门就能容易地找到逆。如果陷门信息的保密性不强，求逆也就不难。2022/7/29124.2 RSA公钥密码体制4.2.1 概述4.2.2 算法描述4.2.3 算法举例4.2.4 算法安全性2022/7/29134.2.1 概述RSA算法是1977年由MIT三位密码学家Rivest、Shamirh和Adleman发明，是迄今为止最为成熟完善的公钥密码体制。RSA算法基于数论构造，具体难度问题是大素数乘积的因子分解。将两个大素数相乘十分容易，但对其乘积进行因式分解却极其困

8、难，因此可以将乘积作为加密密钥公开。RSA算法的缺陷是无法从理论上把握它的保密性RSA算法的安全性依赖于大数的因子分解，但并没有从理论上证明RSA算法的破译难度等价于大数分解难度。2022/7/29144.2.2 算法描述密钥对生成选取两个大素数p和q，n=p*q；计算n的欧拉函数(n) =(p-1)*(q-1)；随机选取与(n)互素的加密密钥e（公开），即 gcd(e, (n)=1；利用扩展欧几里德算法计算解密密钥d，满足de=1 mod (n)；公钥为(n, e)，私钥为(n, d)。2022/7/29154.2.2 算法描述加密过程y =E(x) =xe mod n. (xn)解密过程x

9、 =D(y) =yd mod n正确性验证yd mod n = xed mod n = xk(n)+1 mod n = x*xk(n) mod n = x*1 mod n = x欧拉定理：若n, x为正整数，且n, x互素，即gcd(x, n) = 1，则x(n) 1 (mod n)2022/7/29164.2.2 算法描述正确性验证（欧拉定理）x与n互素，则由欧拉定理x (p-1)(q-1) mod n 1 mod n得x*xk (p-1)(q-1) mod n x mod n gcd(x,n)1，由于n=pq，且p和q都是素数，则x是p或q的倍数。设x=tp，其中t为一正整数，而gcd(x

10、,q) =1(mn)。由欧拉定理xq-1 mod q 1 mod q得1) xk(p-1)(q-1) mod q 1 mod q xk(p-1)(q-1) =1+rq (两边同时乘以x=tp)2) x*xk(p-1)(q-1) =(1 + rq) tp = tp + rtpq = x + rtn3) x*xk(p-1)(q-1)modn (x + rtn)modn x modn 2022/7/29174.2.3 算法举例产生密钥对选取p=17，q=13，则n=p*q=221，(n)=(p-1)*(q-1)= 192再选取与(n)互素的e=11，则公钥为(n, e)= (221,11)根据扩展欧

11、几里得算法求得d =e-1 mod (n) =11-1 mod 192 =35，则私钥为(n, d)= (221, 35)加解密过程设明文x=9，加密：y =xe mod n = 911 mod 221 = 185。解密：x =yd mod n = 18535 mod 221 = 9。2022/7/29184.2.3 算法举例加解密的计算问题18535 mod 221，如果先计算18535再模221，那么中间结果远远超出了计算机所允许的整数取值范围。(a b) mod n (a mod n) (b mod n)mod n计算yd (18535)d = dk2k + dk-12k-1 + d12

12、 + d0，其中di0或1 (i= 0, , k)yd = (ydk)2ydk-1)2ydk-2)2yd1)2yd0例如35 =125 + 024 + 023 + 022 + 121 + 120 y35= (y1)2y0)2y0)2y0)2y1)2y12022/7/29194.2.4 算法安全性RSA算法的安全性依赖于大数分解的难度从数学上从未证明过需要分解n才能从y和e中计算出x；可通过猜测(p-1)(q-1)的值来攻击RSA，但这种攻击没有分解n容易；可尝试每一种可能的d，直到获得正确的一个，这种穷举攻击还没有试图分解n更有效；129位十进制数字的模数是能分解的临界数，n应该大于这个数。1

13、994年4月26日，RSA-129被因子分解，并破解了附带的密文。2022/7/29204.2.4 算法安全性人类数学史上最给力的数学论文之一论文标题：RSA-129。 论文作者： （六百多位）论文内容：11438 16257 57888 86766 92357 79976 14661 20102 18296 72124 23625 62561 84293 57069 35245 73389 78305 97123 56395 87050 58989 07514 75992 90026 87954 3541 =34905 29510 84765 09491 47849 61990 38981

14、33417 76463 84933 87843 99082 0577 * 32769 13299 32667 09549 96198 81908 34461 41317 76429 67992 94253 97982 885332022/7/2921对RSA的选择密文攻击例一(对协议的攻击)：Eve在Alice的通信过程中进行窃听，设法成功选取了一个用她的公开密钥加密的密文c。Eve想读出信息m，m = cd。Eve选取一个随机数r，满足r小于n。她得到Alice的公钥e：x re modn y xc modn t r-1 modnEve让Alice用她的私人密钥对y签名，以便解密y：u yd

15、 modnEve计算：tu modn r-1yd modn r-1xdcd modn cd modn m2022/7/2922对RSA的选择密文攻击例二(对协议的攻击)：Trend是一个公开的计算机公证人，Mallory想让Trend对一个本来不愿意签名的消息签名，例如m1。Mallory计算(如果可能的话)：m1 m2m3 modnEve让Alice用她的私人密钥对m2和m3分别签名；Eve计算：m1d (m2d modn) (m3d modn)利用的缺陷：指数运算保持了输入的乘法结构(xm)d modn = xdmd modn2022/7/2923对RSA的公共模数攻击不同的使用者采用相同

16、模数n，即使e和d不同，假如两个公钥互素，则无需任何的解密技术就可以恢复明文。设m位明文，两个公钥为e1和e2，模数为n，两个密文为：c1 me1 modn c2 me2 modn由于e1和e2互素，根据扩展欧几里德算法找出r和s，满足：re1 + se2 = 1假定r是负数(r或s中有一个必须是负数)，用欧几里德算法可计算c1-1：(c1-1)-r c2s = m modn2022/7/2924对RSA的低加/解密指数攻击对RSA的低加密指数攻击选取较低的e值可以加快计算速度；采用不同的RSA公钥及相同的e值，对e(e+1)/2个线形相关的消息加密，则存在一种能攻击该系统的方法阻止该攻击的方

17、法是用独立随机值填充消息，使得m和n大小一样。对RSA的低解密指数攻击如果d达到n的1/4大小，且e比n小，那么存在一种攻击能够恢复d；假如e和d随机选择，该攻击很少发生；假如e的值很小，则d的值会比较大，该攻击不可能发生。消息比较短，则md和ce都小于n保证memodn me2022/7/2925实现RSA密码方案的限制根据前面成功的攻击，Jadith Moore列出了使用RSA的一些限制知道了对于一个给定模数的一个加/解密密钥指数对，攻击者就能分解这个模数；知道了对于一个给定模数的一个加/解密密钥指数对，攻击者无需分解n就可以计算出别的加/解密对；在通信网络中，利用RSA的协议不应该使用公

18、共模数；消息应用随机数填充以避免对加密指数的攻击；解密指数应该大。2022/7/29264.2.4 算法安全性不能证明RSA密码破译等同于大数因子分解速度问题：提高pq将使开销指数级增长至少有9个明文，加密后不变，即xe mod n=x普通用户难于选择p、q。对p、q的基本要求：p、q不相同，即不要太接近，又不能差别太大p-1、q-1都有大素数因子，增加猜测(n) 难度gcd( p-1,q-1)应当小p、q选择不当，则变换周期性、封闭性而泄密。例：p=17，q=11，e=7，则n=187。设x=123，则明文x经过4次加密，恢复成明文。2022/7/29274.3 其它密码算法 4.3.1 D

19、iffie-Hellman密码算法4.3.2背包密码算法4.3.3 ElGamal密码算法 4.3.4 椭圆曲线密码算法2022/7/29284.3.1 Diffie-Hellman密码算法Diffie和Hellman在密码学新方向一文中给出了非对称密码算法的思想。它不是真正意义上的非对称密码实例，仅仅是一个单向函数；算法的目的是使得两个用户安全地交换一个会话密钥。密钥交换(秘密共享)发送方和接受方基于公钥密码体制交换会话密钥；会话密钥采用对称加密体制加密需要保密传输的消息。2022/7/29294.3.1 Diffie-Hellman密码算法密钥交换系统工作原理发送者接收者接收者的公钥加密接

20、收者的私钥解密加密解密会话密钥交换阶段保密信息交换阶段2022/7/29304.3.2背包密码算法Ralph Merkle和Martin Hellman开发了第一个非对称密码算法背包算法。(背包算法只能用于加密)背包问题的描述：给定一堆物品，每个重量不同，能否将这些物品中的几件放入一个背包中，使之等于一个给定的重量？给定一系列值m1,m2,mn和一个和s，计算bi使之满足s = b1m1 + b2m2 + + bimi背包密码体制的安全性基于背包难题，它证明了如何将一个NP完全问题应用到非对称密码学，后来被证明是不安全的。2022/7/29314.3.3 ElGamal密码算法 ElGamal

21、密码算法由T.ElGamal在1985年提出ElGamal的安全性基于求解离散对数问题的困难性 ElGamal算法描述所有的用户都共享一个素数p以及一个Zp的生成元a，系统中每一个用户U都随机挑选一个整数mu， 并计算Cu =amu mod p，然后用户U公开Cu作为公开密钥，并保存整数mu作为自己的私钥。2022/7/29324.3.3 ElGamal密码算法 密钥对产生办法首先选择一个素数p，两个随机数g和x(g, x p)，计算 y = gx (mod p)，则其公钥为g和p，私钥是x。g和p可由一组用户共享。ElGamal 加解密过程被加密信息为m，首先选择一个随机数k，k与 p-1互质，计算a = gk ( mod p) ，b =m*yk ( mod p ) ( a, b )为密文，是明文的两倍长。解密时计算m = b / ax ( mod p) 2022/7/29334.3.3 ElGamal密码算法 ElGamal密码算法最大的特点是非确定性由于密文依赖于执行加密过程所选择的随机数k，所以加密相同的明文可能会产生不同的密文。ElGamal密码算法的安全性依赖于乘法群 上的离散对数计算复杂度。一般