密码学4公钥密码ppt课件

《密码学4公钥密码ppt课件》由会员分享，可在线阅读，更多相关《密码学4公钥密码ppt课件（90页珍藏版）》请在金锄头文库上搜索。

1、本科生学位课：现代密码学,第四章 公钥密码,主讲教师：董庆宽 研究方向：密码学与信息安全 Email ：qkdongmail.xidian.edu,2,4.1 密码学中常用数学知识 4.2 公钥密码体制的基本概念 4.3 RSA算法 4.4 背包体制 4.5 Rabin体制 4.6 NTRU公钥密码系统 4.7 椭圆曲线密码体制 4.8 基于身份的密码体制,本章提要,3,4.1 密码学中的常用数学知识,群、环、域、素数 模运算 费尔马定理 ap-1=1 mod p ，p是素数 欧拉函数 (n)：小于n的且与n互素的正整数个数 a(n)=1 mod n 素性检验 1.爱拉托斯散筛法(Eratos

2、thenes) 依次删去小于 素数的倍数 2. Miller-Rabin概率检测法 3.AKS,欧几里得算法、扩展欧几里德算法 求最大公约数和乘法的逆元 中国剩余定理 求一次同余方程组的解 离散对数，本原根 平方剩余 计算复杂性,4,4.2 公钥密码体制的基本概念,公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。为密码学发展提供了新的理论和技术基础 公钥密码算法基本工具不再是代换和置换，而是数学函数 以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。 公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，即密钥分配和数字签字,5

3、,对称密码算法的缺陷 密钥分配问题： 通信双方加密通信前要通过秘密的安全信道协商加密密钥，这种安全信道可能很难实现；对这个信道安全性的要求比正常传送消息信道的安全性要高 密钥管理问题： 在多用户网络中，任何两个用户之间都需要有共享的秘密钥，n个用户需要Cn2=n(n-1)/2个密钥，n=5000时，Cn2=12,497,500，系统开销非常大 没有签名功能： 当主体A收到主体B的电子文挡时，无法向第三方证明此电子文档确实来源于B， 传统单钥加密算法无法实现抗抵赖的需求,6,公钥密码的主要作用 公钥加密 用于加密任何消息，象分组密码一样使用 任何人可以用公钥加密消息，私钥的拥有者可以解密消息 数

4、字签名 (Digital Signature) 用于生成对某消息的数字签名 私钥的拥有者生成数字签名，任何人可以用公钥验证签名 签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法 基于公钥的密钥分配(Key Distribution) 用于交换秘密信息，常用于协商对称加密算法的密钥 可采用公钥加密的算法实现密钥分配 也可使用单独设计的密钥交换算法，如DH密钥交换协议实现密钥分配 其它应用： 零知识证明，公平抛币等等，（用于各种目的的认证）,7,公钥密码的发展概况 1976年Diffie和Hellman在其“密码学新方向”一文中提出公钥密码： W.Diffie and M.E.Hellm

5、an, “New Directions in Cryptography”, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976：644-654 1978年Merkle和Hellman基于背包问题提出了首个公钥密码体制，但两年后被破译 1978年Rivest，Shamir d=1； for i=k downto 0 do c=2c; /仅为验证以上过程，而在具体算法中可删去 d=(dd) mod n;/计算平方 if bi=1 then c=c+1; /仅为验证以上过程，而在具体算法中可删去 d=(da) mod n /

6、bi=1时与a相乘 return d. 其中d是中间结果，d的终值即为所求结果。 c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉,28,计算复杂度: lW(m)次模乘（m为模指数） l为指数的bit长，W(m)为指数m的重量(二进制比特1的个数) 例： 求7560 mod 561。 将560表示为1000110000，算法的中间结果如表4-6所示 所以7560 mod 561=1 (5613x11x17, (561)=2x10 x16=320, 780=1 mod 561),29,一种改进的RSA实现方法 (即4.3.3节） RSA的加密很快

7、，因为加密指数e一般选择得很小 解密指数d很大，需要计算模 300digits (or 1024bits) 的乘法，计算机不能直接处理这么大的数，计算速度很慢，需要考虑其它技术，加速RSA的实现 如果知道p和q，可采用中国剩余定理CRT： CRT 对RSA解密算法生成两个解密方程（利用M=Cd mod N，N=pq） 即：M1 = M mod p = (C mod p)d mod (p-1) mod p M2 = M mod q = (C mod q)d mod (q-1) mod q 解方程 M = M1 mod p M = M2 mod q 具有唯一解（利用CRT ）： M = M1q(q

8、1mod p)+ M2p(p1mod q) mod N 不考虑CRT的计算代价，改进的算法的解密速度是原来的4倍 若考虑CRT的计算代价，改进后的算法解密速度是原来的3倍多,30,2. RSA密钥的产生 需考虑两个大素数p、q的选取，以及e的选取和d的计算 n(=pq) 是公开的，为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数 (1) 如何有效地寻找大素数是第一个需要解决的问题 寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器）， 然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止 素性检验算法通

9、常都是概率性的，常用Miller-Rabin概率检测算法实现 寻找大素数是一个比较繁琐的工作，然而在RSA体制中，只有在产生新密钥时才需执行这一工作,31,(2) p和q决定出后，下一个需要解决的问题是 如何选取满足1e(n)和gcd(n),e)=1的e，并计算满足de1 mod (n)的d 这一问题可由推广的Euclid算法完成 注意：RSA的模很长，如模n为1024比特的RSA一次加密约1024比特明文，相当于16次DES加密，但一次RSA比16次DES要慢很多，不在一个数量级上）,32,4.3.4 RSA的安全性,RSA的安全性是基于分解大整数的困难性假定 之所以为假定是因为至今还未能证

10、明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法 如果RSA的模数n被成功地分解为pq，则立即求得(n)，从而能够确定e模(n)的乘法逆元d，即de-1 mod (n)，因此攻击成功 随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解 例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解 RSA-130 已于2019年4月被成功分解 RSA-140 已于2019年2月被成功分解 RSA-155（512bit）已于2019年8月被成功分解 RSA-158，2019年被成功分解,33,量子计算：可能

11、解决大整数分解问题 （分解15和21） 对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进 分解算法过去都采用二次筛法，如对RSA-129的分解 而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%。 对RSA-140和RSA-155的分解也采用此法 将来也可能还有更好的分解算法 因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的,34,是否有不通过分解大整数的其他攻击途径？ 下面证明由n直接确定(n)等价于对n

12、的分解 设n=pq中，pq，由 (n)=(p-1)(q-1)，则有 p+q=n(n)+1，以及 p-q= 由此可见，由p、q确定(n)和由(n)确定p、q是等价的,35,为保证算法的安全性，对p和q提出以下要求： (1) |p-q|要大 由(p+q)2/4n=(p+q)2/4pq=(pq)2/4，如果|p-q|小，则(pq)2/4也小，因此(p+q)2/4稍大于n，(p+q)/2稍大于n1/2。可得n的如下分解步骤： 顺序检查大于n的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。 由x2-n=y2，得n=(x+y)(x-y)。 (2) p-1和q-1都应有大素因子(强素数)

13、 这是因为RSA算法存在着可能的重复加密攻击法。,36,重复加密攻击法 设攻击者截获密文c，可如下进行重复加密： 若 ，即 ，则有 ， 即 所以在上述重复加密的倒数第2步就已恢复出明文m 这种攻击法只有在 t 较小时才是可行的。为抵抗这种攻击，p、q的选取应保证使 t 很大。 设m在模n下阶为k，由 得 ，所以k|(et-1)，即et1(mod k)，t 取为满足前式的最小值（为e在模k下的阶）。又当e与k互素时t|(k)。为使t大，k就应大且(k)应有大的素因子。又由k|(n)，所以为使k大，p-1和q-1都应有大的素因子 此外，研究表明，如果en且dn1/4，则d能被容易地确定,37,4.

14、3.5 对RSA的攻击,RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的 1. 共模攻击 在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的 设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明文消息是m，密文分别是 c1me1(mod n) c2me2(mod n) 敌手截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足 re1+se2=1的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c1-1，由此得(c1-1)-rc2sm(mod n)。,38,2. 低指

15、数攻击 假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。 设3个用户的模数分别为ni(i=1,2,3)，当ij时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，加密指数e3，密文分别是: c1m3(mod n1) c2m3(mod n2) c3m3(mod n3) 由中国剩余定理可求出m3(mod n1n2n3)。由于m3n1n2n3，可直接由m3开立方根得到m。 最初建议使用e=3，不安全，e是有下限的 明文消息空间太小时，消息需要填充,39,4.4 背包密码体制,设A=(a1,a2,

16、an)是由n个不同的正整数构成的n元组，s是另一已知的正整数。背包问题就是从A中求出所有的ai，使其和等于s。其中A称为背包向量，s是背包的容积。 例如,A=(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523)，s=3231。 由于 3231=129+473+903+561+1165 所以从A中找出的满足要求的数有129、473、903、561、1165 原则上讲，通过检查A的所有子集，总可找出问题的解（若有解的话） 本例A的子集共有210=1024个（包括空集）。然而如果A中元素个数n很大，子集个数2n将非常大。如A中有300个元素，A的子集有2300。寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题是NPC问题。,40,由背包问题构造公钥密码体制同样是要构造一个单向函数f 将x(1x2n-1)写成长为n的二元表示0001, 0010， 001