非对称密码体制

《非对称密码体制》由会员分享，可在线阅读，更多相关《非对称密码体制（38页珍藏版）》请在金锄头文库上搜索。

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

2、 =1000时, 999 *1000/2 = 499500。 密钥协商问题：第一次协商好密钥后，以后可以通过当前密钥秘密发送新密钥。但第一次如何协商密钥？（用户秘密会面协商？陌生人怎么办？远距离怎么办？） 消息发送者的身份确认问题,2018/10/16,4,4.1.2 非对称密码的产生,非对称密码的发展历程 计算机网络特别是Internet的发展，促使非对称密码的出现。 1976年，Diffie和Hellman在密码学的新方向中提出来非对称密码的思想。（单向函数） 1977年，RSA加密算法问世，名字来自3位作者Rivest, Shamir和Adleman。,2018/10/16,5,4.1.

3、3 非对称密码体制,密钥(PK, SK) 公钥PK (Public Key)：通常公钥是公开的，可以被任何实体通过有效渠道获取； 私钥SK (Secret Key)：通常私钥是保密的，不能被任何实体通过非法渠道获取；,2018/10/16,6,4.1.3 非对称密码体制,密码算法组成 密钥生成KG( )：根据输入的安全参数 ，输出密钥对(PK, SK)。 加密E( )：根据输入的公钥和消息，输出密文。 解密D( )：根据输入的解密私钥和密文，算法输出消息或输出表示密文不合法的特殊符号“?”。,2018/10/16,7,4.1.3 非对称密码体制,设计要求 参与方容易通过计算产生一对密钥； 在知

4、道公开密钥和待加密消息的情况下，发送方A容易产生密文； 接收方B使用私有密钥容易通过计算解密所得密文，以便恢复原来的消息； 敌手在知道公开密钥的情况下，确定私有密钥计算上不可行； 敌手在知道公开密钥和密文的情况下，恢复消息计算上不可行； 两个密钥中的任何一个可以用来加密，对应的另一个用来解密。,2018/10/16,8,4.1.3 非对称密码体制,非对称密码的特点 基于数学函数，而非替换和换位。 加密密钥和解密密钥不同，且不能相互推理。 解决了密码管理、身份认证和数字签名等问题。 非对称密码的关键 非对称密码的安全性主要取决于构造非对称算法所依赖的数学问题。 要求加密函数具有单向性，即求逆的困

5、难性。 设计非对称密码体制的关键是寻求一个合适的单向函数。,2018/10/16,9,4.1.4 单向函数,令函数f是集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)函数。 定义中的“极为困难”是对现有的计算资源和算法而言。,2018/10/16,10,4.1.4 单向函

6、数,例一：令f是在有限域GF(p)中的指数函数，其中p是大素数，即 y = f(x) = ax。式中，xGF(p)，x为满足0 xp1的整数，其逆运算是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年！其中假定存储量的要求能够满足)。,2018/10/16,11,4.1.4 单向陷门函数,满足下列条件的函数f称为单向陷门函数

7、： 给定x，计算y = f(x)是容易的； 给定y，计算x使y = f(x)是困难的； 存在z，已知z时, 对给定的任何y，若相应的x存在，则计算x使y = f(x)是容易的。 两个难题 陷门函数实际上不是单向函数，因为单向函数是在任何条件下求逆都是困难的； 陷门可能不止一个，通过试验一个个陷门就能容易地找到逆。如果陷门信息的保密性不强，求逆也就不难。,2018/10/16,12,4.2 RSA公钥密码体制,4.2.1 概述 4.2.2 算法描述 4.2.3 算法举例 4.2.4 算法安全性,2018/10/16,13,4.2.1 概述,RSA算法是1977年由MIT三位密码学家Rivest、

8、Shamirh和Adleman发明，是迄今为止最为成熟完善的公钥密码体制。 RSA算法基于数论构造，具体难度问题是大素数乘积的因子分解。 将两个大素数相乘十分容易，但对其乘积进行因式分解却极其困难，因此可以将乘积作为加密密钥公开。 RSA算法的缺陷是无法从理论上把握它的保密性 RSA算法的安全性依赖于大数的因子分解，但并没有从理论上证明RSA算法的破译难度等价于大数分解难度。,2018/10/16,14,4.2.2 算法描述,密钥对生成 选取两个大素数p和q，n=p*q； 计算n的欧拉函数(n) =(p-1)*(q-1)； 随机选取与(n)互素的加密密钥e（公开），即 gcd(e, (n)=1

9、； 利用扩展欧几里德算法计算解密密钥d，满足de=1 mod (n)； 公钥为(n, e)，私钥为(n, d)。,2018/10/16,15,4.2.2 算法描述,加密过程 y =E(x) =xe mod n. (xn) 解密过程 x =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,2018/10/16,16,欧拉定理：若n, x为正整数，且n, x互素，即gcd(x, n) = 1，则x(n) 1 (mod n),4.2.2 算法描述,正确性验证（欧拉定理）

10、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,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 + rtn 3) x*xk(p-1)(q-1)modn

11、(x + rtn)modn x modn,2018/10/16,17,4.2.3 算法举例,产生密钥对 选取p=17，q=13，则n=p*q=221，(n)=(p-1)*(q-1)= 192 再选取与(n)互素的e=11，则公钥为(n, e)= (221,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。,2018/10/16,18,4.

12、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 + 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)2y1,2018/10/16,19,4.2.4 算法

13、安全性,RSA算法的安全性依赖于大数分解的难度 从数学上从未证明过需要分解n才能从y和e中计算出x； 可通过猜测(p-1)(q-1)的值来攻击RSA，但这种攻击没有分解n容易； 可尝试每一种可能的d，直到获得正确的一个，这种穷举攻击还没有试图分解n更有效； 129位十进制数字的模数是能分解的临界数，n应该大于这个数。 1994年4月26日，RSA-129被因子分解，并破解了附带的密文。,2018/10/16,20,4.2.4 算法安全性,人类数学史上最给力的数学论文之一 论文标题：RSA-129。 论文作者： （六百多位） 论文内容： 11438 16257 57888 86766 92357

14、 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 33417 76463 84933 87843 99082 0577 * 32769 13299 32667 09549 96198 81908 34461 41317 76429 67992 94253 97982 88533,2018/10/16,21,2

15、018/10/16,Page: 22,对RSA的选择密文攻击,例一(对协议的攻击)：Eve在Alice的通信过程中进行窃听，设法成功选取了一个用她的公开密钥加密的密文c。Eve想读出信息m，m = cd。 Eve选取一个随机数r，满足r小于n。她得到Alice的公钥e： x re modn y xc modn t r-1 modn Eve让Alice用她的私人密钥对y签名，以便解密y： u yd modn Eve计算： tu modn r-1yd modn r-1xdcd modn cd modn m,2018/10/16,Page: 23,对RSA的选择密文攻击,例二(对协议的攻击)：Tre

16、nd是一个公开的计算机公证人，Mallory想让Trend对一个本来不愿意签名的消息签名，例如m1。 Mallory计算(如果可能的话)： m1 m2m3 modn Eve让Alice用她的私人密钥对m2和m3分别签名； Eve计算： m1d (m2d modn) (m3d modn),利用的缺陷：指数运算保持了输入的乘法结构(xm)d modn = xdmd modn,2018/10/16,Page: 24,对RSA的公共模数攻击,不同的使用者采用相同模数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 modn,