公钥密码体制及典型算法-RSA-PPT.ppt

《公钥密码体制及典型算法-RSA-PPT.ppt》由会员分享，可在线阅读，更多相关《公钥密码体制及典型算法-RSA-PPT.ppt（147页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、公钥密码体制及典型算法-RSA 在公钥密码体制以前的整个密码学史中，所在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。这两个基本工具。而公钥密码体制则为密码学的发展提供了新的而公钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥密码算法的基本工具理论和技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数；另一方面公钥不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式使用

2、两个密钥，两个密密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码学史上的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。是一个最大的而且是惟一真正的革命。1 公钥密码体制的基本概念公钥密码体制的基本概念2 公钥密码体制的概念是在解决单钥密码体制中公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。分配和数字签字。单钥密码体制在进行密钥分配时单钥密码体制在进

3、行密钥分配时,要求通信双要求通信双方或者已经有一个共享的密钥，或者可籍助于一个方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常可用人工方式密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。赖于密钥分配中心的可靠性。第二个问题数字签字考虑的是如何为数字化的第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的消息或文件提供一种类似于为书面文件手书

4、签字的方法。方法。1976年年W.Diffie和和M.Hellman对解决上述两对解决上述两个问题有了突破，从而提出了公钥密码体制。个问题有了突破，从而提出了公钥密码体制。公钥密码体制的基本概念公钥密码体制的基本概念3对称密码体制的缺陷对称密码体制的缺陷 n密钥分配问题密钥分配问题 通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；n密钥管理困难问题密钥管理困难问题 在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大。n用户保密通信网，用户彼此间进行保密通信需要用户保密通信网，用户彼此间进行保密通

5、信需要 个密钥。个密钥。n=1000：499500个密钥个密钥 n=5000：个密钥：个密钥n没有签名功能，无法实现抗抵赖问题：没有签名功能，无法实现抗抵赖问题：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。n陌生人间不便进行保密通信问题陌生人间不便进行保密通信问题4n别名：别名：公钥密码体制，双钥密码体制公钥密码体制，双钥密码体制n两个密钥：两个密钥：公开密钥（公钥）：可以被任何人知道公开密钥（公钥）：可以被任何人知道,用于加密或用于加密或验证签名验证签名 秘密密钥（私钥）：只能被消息的接收者或签名者知秘密密钥（私钥）：只能被消息的接收者或签名者知道道,

6、用于解密或签名。用于解密或签名。加密或验证签名者不能解密或生成签名（已知密码算加密或验证签名者不能解密或生成签名（已知密码算法和加密密钥，求解密密钥在计算上是不可行的）。法和加密密钥，求解密密钥在计算上是不可行的）。n安全性基础：安全性基础：基于数学难题基于数学难题n标志性文献标志性文献 W.Diffie and M.E.Hellman,New Directions in W.Diffie and M.E.Hellman,New Directions in Cryptography,IEEE Transaction on Information Cryptography,IEEE Transa

7、ction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654Theory,V.IT-22.No.6,Nov 1976,PP.644-654公钥密码体制的基本概念公钥密码体制的基本概念5n由私钥及其他密码信息容易计算出公开密钥(a polynomial time(P-time)problem)n由公钥及算法描述,计算私钥是难的(an NP-time problem)n因此,公钥可以发布给其他人(wishing to communicate securely with its owner)n密钥分配问题不是一个容易的问题(the key

8、distribution problem)公钥密码体制的基本概念公钥密码体制的基本概念6公钥算法分类公钥算法分类nPublic-Key Distribution Schemes(PKDSPublic-Key Distribution Schemes(PKDS，公钥分配系统，公钥分配系统)w用于交换秘密信息(依赖于双方主体)w常用于对称加密算法的密钥nPublic Key Encryption(PKEPublic Key Encryption(PKE，公钥加密，公钥加密)w用于加密任何消息 w任何人可以用公钥加密消息 w私钥的拥有者可以解密消息 w任何公钥加密方案能够用于密钥分配方案PKDS w

9、许多公钥加密方案也是数字签名方案nSignature SchemesSignature Schemes（签名方案）（签名方案）w用于生成对某消息的数字签名w私钥的拥有者生成数字签名w任何人可以用公钥验证签名 7大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流8n公钥密码系统可用于以下三个方面：(1)通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。9(2)数字签名：将私钥作为加密密钥，公钥作为解 密密钥，可实现由一个用户对数据加密而使多个用户解读。10(3)密

10、钥交换：通信双方交换会话密钥，以 加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥，用完就丢弃。11公开密钥算法的特点公开密钥算法的特点:（1）发送者用加密密钥PK对明文X加密后，在接收者用解密密钥SK解密，即可恢复出明文，或写为：DSK(EPK(X)X 解密密钥是接收者专用的秘密密钥，对其他人都保密。此外，加密和解密的运算可以对调，即 EPK(DSK(X)X（2）加密密钥是公开的，但不能用它来解密，即DPK(EPK(X)X 12公开密钥算法的特点公开密钥算法的特点:（3）在计算机上可以容易地产生成对的PK和SK。（4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计

11、算上不可能的”。（5）加密和解密算法都是公开的。13 公钥密码算法的最大特点是采用两个相公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公钥密码体制也称为双钥密码于解密。因此公钥密码体制也称为双钥密码体制。算法有以下重要特性：体制。算法有以下重要特性：已知密码算法已知密码算法和加密密钥，求解密密钥

12、在计算上是不可行和加密密钥，求解密密钥在计算上是不可行的。的。公钥密码体制的原理公钥密码体制的原理14图 公钥体制加密的框图15加密过程有以下几步：加密过程有以下几步：要求接收消息的端系统，产生一对用来加要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者密和解密的密钥，如图中的接收者B，产生，产生一对密钥一对密钥PKB，SKB，其中，其中PKB是公开钥，是公开钥，SKB是秘密钥。是秘密钥。端系统端系统B将加密密钥（如图中的将加密密钥（如图中的PKB）予）予以公开。另一密钥则被保密（图中的以公开。另一密钥则被保密（图中的SKB）。）。公钥密码体制的原理公钥密码体制的原理16n A

13、要想向要想向B发送消息发送消息m，则使用，则使用B的公开的公开钥加密钥加密m，表示为，表示为c=EPKBm,其中其中c是密文，是密文，E是加密算法。是加密算法。n B收到密文收到密文c后，用自己的秘密钥后，用自己的秘密钥SKB解解密，表示为密，表示为m=DSKBc，其中，其中D是解密算法。是解密算法。公钥密码体制的原理公钥密码体制的原理17公钥密码体制认证框图公钥密码体制认证框图18 因为只有因为只有B知道知道SKB，所以其他人都无，所以其他人都无法对法对c解密。解密。公钥加密算法不仅能用于加、解密，还公钥加密算法不仅能用于加、解密，还能用于对发方能用于对发方A发送的消息发送的消息m提供认证，

14、如提供认证，如下图所示。用户下图所示。用户A用自己的秘密钥用自己的秘密钥SKA对对m加加密，表示为密，表示为c=ESKAm 将将c发往发往B。B用用A的公开钥的公开钥PKA对对c解密，解密，表示为表示为m=DPKAc公钥密码体制认证的原理公钥密码体制认证的原理19 因为从因为从m得到得到c是经过是经过A的秘密钥的秘密钥SKA加加密，只有密，只有A才能做到。因此才能做到。因此c可当做可当做A对对m的的数字签字。数字签字。另一方面，任何人只要得不到另一方面，任何人只要得不到A的秘密钥的秘密钥SKA就不能篡改就不能篡改m，所以以上过程获得了对，所以以上过程获得了对消息来源和消息完整性的认证。消息来源

15、和消息完整性的认证。公钥密码体制认证的原理公钥密码体制认证的原理20 在实际应用中，特别是用户数目很多时，以在实际应用中，特别是用户数目很多时，以上认证方法需要很大的存储空间，因为每个文件都上认证方法需要很大的存储空间，因为每个文件都必须以明文形式存储以方便实际使用，同时还必须必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容。改进的便在有争议时用来认证文件的来源和内容。改进的方法是减小文件的数字签字的大小，即先将文件经方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩

16、成长度较小的比特串，得到的比特过一个函数压缩成长度较小的比特串，得到的比特串称为认证符。串称为认证符。认证符具有这样一个性质：如果保持认证符的认证符具有这样一个性质：如果保持认证符的值不变而修改文件这在计算上是不可行的。用发送值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证符加密，加密后的结果为原文件者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。的数字签字。公钥密码体制认证的原理公钥密码体制认证的原理21 以上认证过程中，由于消息是由用户自以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这

17、是因为任何人都改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。供认证功能和保密性，可使用双重加、解密。如下图所示。如下图所示。公钥密码体制认证的原理公钥密码体制认证的原理22公钥密码体制的认证、保密框图公钥密码体制的认证、保密框图23 发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为 c=EPKBESKAm解密过程为 m=DPKADSKBc 即收方先用自己的秘密钥,再用发方的公开钥对收到的密文两次解密。公钥密码体制认证的原理公钥密码体制认

18、证的原理24公钥保密和认证体制公钥保密和认证体制 2023/5/2925公钥密码算法应满足以下要求:接收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKBm在计算上是容易的。收方B用自己的秘密钥对c解密，即m=DSKBc在计算上是容易的。公钥密码算法应满足的要求公钥密码算法应满足的要求26 敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的。敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的。加、解密次序可换，即EPKBDSKB(m)=DSKBEPKB(m)其中最后一条虽然非常有用，但不是对所有的算法都作要求。

19、公钥密码算法应满足的要求公钥密码算法应满足的要求27 以上要求的本质之处在于要求一个陷门单向以上要求的本质之处在于要求一个陷门单向函数。函数。单向函数是两个集合单向函数是两个集合X、Y之间的一个映射，之间的一个映射，使得使得Y中每一元素中每一元素y都有惟一的一个原像都有惟一的一个原像x X，且由，且由x易于计算它的像易于计算它的像y，由，由y计算它的原像计算它的原像x是不可行是不可行的。这里所说的易于计算是指函数值能在其输入长的。这里所说的易于计算是指函数值能在其输入长度的多项式时间内求出，即如果输入长度的多项式时间内求出，即如果输入长n比特，则比特，则求函数值的计算时间是求函数值的计算时间是

20、na的某个倍数，其中的某个倍数，其中a是一是一固定的常数。这时称求函数值的算法属于多项式类固定的常数。这时称求函数值的算法属于多项式类P，否则就是不可行的。例如，函数的输入是，否则就是不可行的。例如，函数的输入是n比比特，如果求函数值所用的时间是特，如果求函数值所用的时间是2n的某个倍数，则的某个倍数，则认为求函数值是不可行的。认为求函数值是不可行的。公钥密码算法应满足的要求公钥密码算法应满足的要求28 注意这里的易于计算和不可行两个概念与计注意这里的易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别。在复杂性理论

21、中，算法的复杂度在着本质的区别。在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量是以算法在最坏情况或平均情况时的复杂度来度量的。而在此所说的两个概念是指算法在几乎所有情的。而在此所说的两个概念是指算法在几乎所有情况下的情形。况下的情形。称一个函数是陷门单向函数，是指该函数是易称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式些附加信息。当附加信息给定后，求逆可在多项式时间完成。时间完成。公钥密码算法应满足的要求公钥密码算法应满足的要求29 总结为：陷

22、门单向函数是一族可逆函数fk，满足 Y=fk(X)易于计算（当k和X已知时）。X=f-1k(Y)易于计算（当k和Y已知时）。X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）。因此，研究公钥密码算法就是要找出合适的陷门单向函数。公钥密码算法应满足的要求公钥密码算法应满足的要求30 和单钥密码体制一样，如果密钥太短，公钥密和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所才能抗击穷搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是使用的可逆函

23、数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。体制目前主要用于密钥管理和数字签字。对公钥密码算法的第对公钥密码算法的第2种攻击法是寻找从公开种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。还都未能够证明这种攻击是不可行的。对公钥密码体制的攻击对公钥密码体制的攻击31 还有一种仅适用于对公钥密码算法的攻击法，

24、还有一种仅适用于对公钥密码算法的攻击法，称为可能字攻击。例如对称为可能字攻击。例如对56比特的比特的DES密钥用公密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较。有可能的密钥加密后与截获的密文相比较。如果一样，则相应的明文即如果一样，则相应的明文即DES密钥就被找密钥就被找出。因此不管公钥算法的密钥多长，这种攻击的本出。因此不管公钥算法的密钥多长，这种攻击的本质是对质是对56比特比特DES密钥的穷搜索攻击。抵抗方法密钥的穷搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。是在欲发送的明文消息后添加一些

25、随机比特。对公钥密码体制的攻击对公钥密码体制的攻击32n强力攻击强力攻击(对密钥对密钥)密钥不能太短，防止密钥穷举密钥不能太短，防止密钥穷举 但也不能太长，以免影响速度但也不能太长，以免影响速度n公开密钥算法本身可能被攻破公开密钥算法本身可能被攻破 赖以安全的基石赖以安全的基石-数学难题被破解数学难题被破解n可能报文攻击可能报文攻击(对报文本身的强力攻击对报文本身的强力攻击)对所有可能报文加密，直到与截获密文相同对所有可能报文加密，直到与截获密文相同对公钥密码体制的攻击对公钥密码体制的攻击33 RSA算法是1978年由罗纳德李维斯特（Ron Rivest）、阿迪萨莫尔（Adi Shamir）和

26、伦纳德阿德曼（Leonard Adleman）提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。R L Rivest,A Shamir,L Adleman,On Digital Signatures and Public Key Cryptosystems,Communications of the ACM,vol 21 no 2,pp120-126,Feb 19782 RSA算法算法34n由由Rivest,Shamir和和 Adleman在在1978年提出年提出n数学

27、基础数学基础:大整数因子分解的困难性，大整数因子分解的困难性，Euler定理定理351.密钥的产生 选两个保密的大素数p和q(各各100200位十进制位十进制数字，且数字，且p不等于不等于q)。计算n=pq，(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。随机选一整数e，满足1e(n)，且gcd(n),e)=1。计算d，满足de1 mod(n),即d是e在模(n)下的乘法逆元，因e与(n)互素，由模运算可知，它的乘法逆元一定存在。d=e-1 (mod (n)以e,n为公开钥,d,n为秘密钥。(p,q不再需要，不再需要，可以销毁可以销毁)算法描述算法描述362.加密 加密时首先将明文比

28、特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：cme mod nRSA加密算法描述加密算法描述373.解密对密文分组的解密运算为：mcd mod n 下面证明下面证明RSA算法中解密过程的正确性。算法中解密过程的正确性。证明：由加密过程知cme mod n，所以cd mod nmed mod nm1 mod(n)mod nmk(n)+1 mod nRSA解密算法描述解密算法描述38下面分两种情况：m与n互素，则由Euler定理得m(n)1 mod n,mk(n)1 mod n,mk(n)+1m mod n即cd mod nm。gcd(m

29、,n)1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)1意味着m是p的倍数或q的倍数，不妨设m=cp，其中c为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾。39 由gcd(m,q)=1及Euler定理得m(q)1 mod q，所以mk(q)1 mod q,mk(q)(p)1 mod q,mk(n)1 mod q 因此存在一整数r，使得mk(n)=1+rq，两边同乘以m=cp 得mk(n)+1=m+rcpq=m+rcn 即mk(n)+1m mod n，所以cd mo

30、d nm。(证毕)RSA解密算法证明解密算法证明40例：例：选选p=7，q=17。求。求n=pq=119，(n)=(p-1)(q-1)=96。取。取e=5，满足，满足1e(n)，且，且gcd(n),e)=1。确定满足确定满足de=1 mod 96且小于且小于96的的d，因为，因为775=385=496+1，所以，所以d为为77，因此公开钥为，因此公开钥为5，119，秘密钥为，秘密钥为77，119。设明文设明文m=19，则由加密过程得密文为，则由加密过程得密文为 c195 mod 1192476099 mod 11966解密为解密为 6677mod 11919RSA解密算法证明解密算法证明41R

31、SA算法实例例例 假设假设Alice和和Bob 使用使用RSA密码体制进行全密码体制进行全英文字符的保密通信。假设英文字符的保密通信。假设Alice 选择选择 、，Bob选择选择 、，并采用双字母加、解密方式。并采用双字母加、解密方式。（1 1）说明）说明AliceAlice和和BobBob建立建立RSARSA密码体制的方法。密码体制的方法。（2 2）若）若AliceAlice欲秘密发送消息欲秘密发送消息“public”public”给给BobBob，试给出加密和解密过程。，试给出加密和解密过程。424、RSA算法实例例例（1 1）说明）说明AliceAlice和和BobBob建立建立RSAR

32、SA密码体制的方法。密码体制的方法。解解 Alice Alice计算：计算：434、RSA算法实例例例（1 1）说明）说明AliceAlice和和BobBob建立建立RSARSA密码体制的方法。密码体制的方法。解解 Bob Bob计算计算 ：444、RSA算法实例例例5-1（2 2）若）若AliceAlice欲秘密发送消息欲秘密发送消息“public”public”给给BobBob，试给，试给出加密和解密过程。出加密和解密过程。解解 Alice Alice加密：加密：“public”public”代换为数字并按双字母分组：代换为数字并按双字母分组：1520 0111 0802 1520 011

33、1 0802 454、RSA算法实例例例（2 2）若）若AliceAlice欲秘密发送消息欲秘密发送消息“public”public”给给BobBob，试给，试给出加密和解密过程。出加密和解密过程。解解 Bob Bob解密解密 ：密文密文“0095 1649 1410”0095 1649 1410”明文明文:public:public461.RSA的加密与解密过程 RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的

34、整数取值范围。而用模运算的性质：(ab)mod n=(a mod n)(b mod n)mod n就可减小中间结果。RSA算法中的计算问题算法中的计算问题47再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bk bk-1b0，即 m=bk2k+bk-12k-1+b12+b0因此RSA算法中的计算问题算法中的计算问题48例如：19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1

35、)2a1从而可得以下快速指数算法：c=0;d=1；For i=k downto 0 do c=2c;d=(dd)mod n;if bi=1 then c=c+1;d=(da)mod nreturn d.RSA算法中的计算问题算法中的计算问题49 其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉。RSA算法中的计算问题算法中的计算问题50 例求7560 mod 561。将560表示为1000110000，所以7560 mod 561=1。512.RSA密钥的产生 产生密钥时，需要考虑两个大素数p、q的选取，

36、以及e的选取和d的计算。因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（102002664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。RSA密钥产生密钥产生52 寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。

37、素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。例如Miller-Rabin算法。RSA密钥产生密钥产生53 可见寻找大素数是一个比较繁琐的工作。然而在RSA体制中，只有在产生新密钥时才需执行这一工作。p和q决定出后，下一个需要解决的问题是如何选取满足1eq，由(n)=(p-1)(q-1)，则有 p+q=n-(n)+1以及 由此可见，由p、q确定(n)和由(n)确定p、q是等价的。RSA的安全性的安全性58为保证算法的安全性，还对p和q提出以下要求：（1）|p-q|要大由 ，如果

38、|p-q|小，则 也小，因此 稍大于n，稍大于 。可得n的如下分解步骤：顺序检查大于 的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。由x2-n=y2，得n=(x+y)(x-y)。RSA的安全性的安全性59RSA中中p、q选择不当选择不当(|p-q|不大不大)的举例的举例n例：n=143,目标：分解n解：60（2）p-1和q-1都应有大素因子 这是因为RSA算法存在着可能的重复加密攻击法。设攻击者截获密文c，可如下进行重复加密：RSA的安全性的安全性61RSA的安全性的安全性62 设m在模n下阶为k，由 得 ，所以k|(et-1)，即et1(mod k)，t取为满足上式的最

39、小值（为e在模k下的阶）。又当e与k互素时t|(k)。为使t大，k就应大且(k)应有大的素因子。又由k|(n)，所以为使k大，p-1和q-1都应有大的素因子。此外，研究结果表明，如果en且dn1/4，则d能被容易地确定。RSA的安全性的安全性63RSA中中P、q选择不当选择不当(p-1或或q-1没有大素因子没有大素因子)的举例的举例例：p=17，q=11，e=7，则n=187。设m=123，则：C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文m经过4次加密，恢复成明文。64 RSA存在以

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

41、数攻击 假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni(i=1,2,3)，当ij时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，密文分别是:c1m3(mod n1)c2m3(mod n2)c3m3(mod n3)由中国剩余定理可求出m3(mod n1n2n3)。由于m3n1n2n3，可直接由m3开立方根得到m。67另一种欺骗性的攻击另一种欺骗性的攻击RSA68思考题思考题1.2.69RSA 参数选择参数选择n需要选择足够大的素数 p,q n通常选择小的加密指

42、数e,且与(N)互素ne 对所有用户可以是相同的 n最初建议使用e=3n现在3太小n常使用 e=216-1=65535 n解密指数比较大70(1)n=pq的确定：的确定：p与与q必须为强素数必须为强素数强素数强素数p的条件的条件：(a)存存在在两两个个大大素素数数p1和和p2，p1|(p1)，p2|(p1)(b)存存在在4个个大大素素数数r1,s1,r2及及s2，使使r1|(p11),r2|(p21),s1|(p11),s2|(p21)。p1和和p2为二级素数；为二级素数；r1,r2,s1和和s2为三级素数为三级素数RSA参数的选择参数的选择71采用强素数的理由如下：采用强素数的理由如下：若若

43、 ，pi为素数，为素数，ai为正整数为正整数 分解式中分解式中piB，B为已知一个小整数为已知一个小整数 则存在一种则存在一种p1的分解法，使我们易于分解的分解法，使我们易于分解n 令令n=pq，且，且p1满足上述条件，满足上述条件，piB 令令a ai，i=1,2,t 可构造可构造 显然显然(p1)R，由费尔马定理由费尔马定理2R 1 mod p 令令2R=x mod n，若，若x=1则选则选3代代2，直到出现，直到出现x 1 此时，此时，kR=1 mod p 有解的充要条件是有解的充要条件是 kR=x mod n (p,n)=p|x-1 由由GCD(x1,n)=p，就得到，就得到n的分解因

44、子的分解因子p和和qRSA参数的选择参数的选择72p与与q之差要大之差要大 若若p与与q之差很小，则可由之差很小，则可由n=pq估计估计(pq)/2=n1/2，由由(pq)/2)2n=(pq)/2)2，等等式式右右边边为为小小的的平平方数，方数，可以试验给出可以试验给出p,q的值的值 例：例：n=164009，估计，估计(pq)/2 405，由由4052n=16=42，可得，可得 (pq)/2=405，(pq)/2=4，p=409，q=401RSA参数的选择参数的选择73p1与与q1的最大公因子要小的最大公因子要小惟密文攻击下，设破译者截获密文惟密文攻击下，设破译者截获密文y=x e mod

45、n破译者做下述递推计算：破译者做下述递推计算：xi=xi-1e mod n=(xe)i mod n 若若ei=1 mod (n)，则有，则有xi=x mod n，且，且ei+1=e mod (n)，即，即xi+1=x 若若i小，则由此攻击法易得明文小，则由此攻击法易得明文x。由由Euler定理知，定理知，i=(p1)(q1)，若若p1和和q1的最大公因子小，则的最大公因子小，则i值大，值大，如如i=(p1)(q1)/2，此攻击法难于奏效。，此攻击法难于奏效。RSA参数的选择参数的选择74p，q要足够大，以使要足够大，以使n分解在计算上不可行分解在计算上不可行RSA参数的选择参数的选择75e的选

46、取原则的选取原则(e,(n)=1条件易于满足，因为两个随机数互素的概率约为条件易于满足，因为两个随机数互素的概率约为3/5ue不不可可过过小小：若若e小小，x小小，y=xe mod n，当当xen，则则未未取取模模，由由y直接开直接开e次方可求次方可求x，易遭低指数攻击易遭低指数攻击 e小时，加密速度快，小时，加密速度快，Knuth和和Shamir曾建议采用曾建议采用e=3 但但e太小存在一些问题太小存在一些问题 选选e在在mod (n)中的阶数中的阶数i(ei 1 mod (n)达到达到(p1)(q1)/2p，q要足够大，以使要足够大，以使n分解在计算上不可行分解在计算上不可行RSA参数的选

47、择参数的选择76d的选择的选择 e选定后可用选定后可用Euclidean算法在多项式时间内求出算法在多项式时间内求出dd小，签字和解密快，在小，签字和解密快，在IC卡中尤为重要卡中尤为重要(复杂的加密和验证签字可由主机来做复杂的加密和验证签字可由主机来做)d要大于要大于n1/4：类似于加密下的情况，：类似于加密下的情况，d不能太小不能太小 否则由已知明文攻击，构造否则由已知明文攻击，构造y=xe mod n，猜测猜测d的的值：值：做做yd mod n，直到试凑出，直到试凑出yd x mod n Wiener给出对小给出对小d的系统攻击法，的系统攻击法，证明了当证明了当d长度小于长度小于n的的1

48、/4时，时，由连分式算法，可在多项式时间内求出由连分式算法，可在多项式时间内求出d值值RSA参数的选择参数的选择77不可用公共模不可用公共模 由由一一密密钥钥产产生生中中心心(KGC)采采用用一一公公共共模模，分分发发多多对对密密钥钥，公公布相应公钥布相应公钥ei 这当然使密钥管理简化，存储空间小，且无重新分组问题这当然使密钥管理简化，存储空间小，且无重新分组问题 但如前所述，它在安全上会带来问题。但如前所述，它在安全上会带来问题。明文熵要尽可能地大明文熵要尽可能地大 明文熵要尽可能地大，以使在已知密文下，明文熵要尽可能地大，以使在已知密文下，要猜测明文无异于完全随机等概情况。要猜测明文无异于

49、完全随机等概情况。用于签字时，要采用用于签字时，要采用Hash函数函数 RSA体制实用中的其它问题体制实用中的其它问题78RSA理论nRSA 基于Fermats Theorem:nif N=pq where p,q are primes,then:X(N)=1 mod N nfor all x not divisible by p or q,ie gcd(x,(N)=1 nwhere(N)=(p-1)(q-1)n但在 RSA 中，e&d 是特殊选择的nie e.d=1 mod(N)或e.d=1+R(N)nhence have:M=Cd=Me.d=M1+R(N)=M1.(M(N)R=M1.(1)

50、R=M1 mod N 79RSA举例举例例子：例子：1.选素数选素数p=47和和q71，得，得n=3337,(n)=46703220；2.选择选择e=79，求得私钥，求得私钥d=e-1 1019(mod 3220）。）。3.公开公开n=3337和和e=79.4.现要发送明文现要发送明文688，计算：，计算：68879(mod 3337)=15705.收到密文收到密文1570后，用私钥后，用私钥d1019进行解密：进行解密：15701019（mod 3337)=68880RSARSA的实现问题的实现问题n需要计算模 300 digits(or 1024+bits)的乘法n计算机不能直接处理这么大