1、1本科生学位课：现代密码学本科生学位课：现代密码学第四章第四章 公钥密码公钥密码主讲教师主讲教师：董庆宽：董庆宽研究方向研究方向：密码学与信息安全：密码学与信息安全Email Email ：qkdongmail.xidian.eduqkdongmail.xidian.edu24.1 密码学中常用数学知识密码学中常用数学知识4.2 公钥密码体制的基本概念公钥密码体制的基本概念4.3 RSA算法算法4.4 背包体制背包体制4.5 Rabin体制体制 4.6 NTRU公钥密码系统公钥密码系统4.7 椭圆曲线密码体制椭圆曲线密码体制4.8 基于身份的密码体制基于身份的密码体制本章提要本章提要34.1
2、密码学中的常用数学知识密码学中的常用数学知识群、环、域、素数群、环、域、素数模运算模运算费尔马定理费尔马定理lap-1=1 mod p，p是素数是素数欧拉函数欧拉函数l(n)：小于：小于n的且与的且与n互素的正互素的正整数个数整数个数la(n)=1 mod n 素性检验素性检验l1.爱拉托斯散筛法爱拉托斯散筛法(Eratosthenes)l依次删去小于依次删去小于 素数的倍数素数的倍数l2.Miller-Rabin概率检测法概率检测法l3.AKS欧几里得算法、扩展欧几里德算欧几里得算法、扩展欧几里德算法法l求最大公约数和乘法的逆元求最大公约数和乘法的逆元中国剩余定理中国剩余定理l求一次同余方程
3、组的解求一次同余方程组的解离散对数，本原根离散对数，本原根平方剩余平方剩余计算复杂性计算复杂性n44.2 公钥密码体制的基本概念公钥密码体制的基本概念公钥密码体制的出现在密码学史上是一个最大的而公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。为密码学发展提供了新的理且是惟一真正的革命。为密码学发展提供了新的理论和技术基础论和技术基础l公钥密码算法公钥密码算法基本工具不再是代换和置换，而是数学函基本工具不再是代换和置换，而是数学函数数l以非对称的形式使用两个密钥以非对称的形式使用两个密钥，两个密钥的使用对保密，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。性、密钥分配
4、、认证等都有着深刻的意义。公钥密码体制的概念公钥密码体制的概念是在解决单钥密码体制中最难是在解决单钥密码体制中最难解决的两个问题时解决的两个问题时提出的提出的，即，即密钥分配和数字签字密钥分配和数字签字5对称密码算法的缺陷对称密码算法的缺陷l密钥分配问题密钥分配问题：通信双方加密通信前通信双方加密通信前要通过秘密的安全要通过秘密的安全信道协商加密密钥，这种安全信道可能很难实现信道协商加密密钥，这种安全信道可能很难实现；对这；对这个个信道安全性的要求信道安全性的要求比正常传送消息信道的安全性要比正常传送消息信道的安全性要高高l密钥管理问题密钥管理问题：在多用户网络中，任何两个用户之间都在多用户网
5、络中，任何两个用户之间都需要有共享的秘密钥，需要有共享的秘密钥，n个用户需要个用户需要Cn2=n(n-1)/2个密钥，个密钥，n=5000时，时，Cn2=12,497,500，系统开销非常大，系统开销非常大l没有签名功能没有签名功能：当主体当主体A收到主体收到主体B的电子文挡时，无的电子文挡时，无法向第三方证明此电子文档确实来源于法向第三方证明此电子文档确实来源于B，传统单钥加传统单钥加密算法无法实现抗抵赖的需求密算法无法实现抗抵赖的需求6公钥密码的主要作用公钥密码的主要作用公钥加密公钥加密l用于加密任何消息，象分组密码一样使用用于加密任何消息，象分组密码一样使用 l任何人可以用公钥加密消息，
6、私钥的拥有者可以解密消息任何人可以用公钥加密消息，私钥的拥有者可以解密消息 数字签名数字签名(Digital Signature)l用于生成对某消息的数字签名用于生成对某消息的数字签名l私钥的拥有者生成数字签名，任何人可以用公钥验证签名私钥的拥有者生成数字签名，任何人可以用公钥验证签名l签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法基于公钥的密钥分配基于公钥的密钥分配(Key Distribution)l用于交换秘密信息，常用于协商对称加密算法的密钥用于交换秘密信息，常用于协商对称加密算法的密钥l可采用公钥加密的算法实现密钥
7、分配可采用公钥加密的算法实现密钥分配l也可使用单独设计的密钥交换算法，如也可使用单独设计的密钥交换算法，如DH密钥交换协议实现密钥分配密钥交换协议实现密钥分配其它应用：其它应用：l零知识证明，公平抛币等等，（用于各种目的的认证）零知识证明，公平抛币等等，（用于各种目的的认证）7公钥密码的发展概况公钥密码的发展概况l1976年年Diffie和和Hellman在其在其“密码学新方向密码学新方向”一文中提出公钥密码：一文中提出公钥密码：lW.Diffie and M.E.Hellman,“New Directions in Cryptography”,IEEE Transaction on Info
8、rmation Theory,V.IT-22.No.6,Nov 1976：644-654l1978年年Merkle和和Hellman基于背包问题提出了首个公钥密码体制，但基于背包问题提出了首个公钥密码体制，但两年后被破译两年后被破译l1978年年Rivest，Shamir&Adleman基于大数分解的困难性提出了基于大数分解的困难性提出了RSA公钥算法，成为迄今为止最为成熟和完善的公钥密码体制公钥算法，成为迄今为止最为成熟和完善的公钥密码体制l1985年出现了基于求解离散对数困难性的公钥密码算法年出现了基于求解离散对数困难性的公钥密码算法DLPl90年代逐步出现椭圆曲线年代逐步出现椭圆曲线(E
9、CC)等其他公钥算法等其他公钥算法l当前的公钥密码算法主要是当前的公钥密码算法主要是基于大数分解困难性基于大数分解困难性和和离散对数困难性离散对数困难性来来构造的，构造的，椭圆曲线椭圆曲线上也可构造这类体制，相同密钥长度下其安全性更上也可构造这类体制，相同密钥长度下其安全性更高高参考资料：参考资料：公钥密码学公钥密码学等等84.2.1 公钥密码体制的原理公钥密码体制的原理公钥密码算法的最大特点是公钥密码算法的最大特点是采用两个相关密钥将采用两个相关密钥将加密和解密能力分开加密和解密能力分开l一个密钥是公开的一个密钥是公开的，称为，称为公开密钥公开密钥，简称，简称公开钥公开钥，用于，用于加密、验
10、证签名加密、验证签名，可以被任何人知道，可以被任何人知道l另一个密钥是为用户专用另一个密钥是为用户专用，因而是保密的因而是保密的，只能被消息，只能被消息的接收者或签名者知道，称为的接收者或签名者知道，称为秘密密钥秘密密钥，简称，简称秘密钥秘密钥，用于用于解密、产生签名解密、产生签名l因此公钥密码体制也称为因此公钥密码体制也称为双钥密码体制双钥密码体制算法有以下重要特性：算法有以下重要特性：已知密码算法和加密密钥，已知密码算法和加密密钥，求解密密钥在计算上是不可行的求解密密钥在计算上是不可行的l因此加密和签名的验证者不能解密和生成签名因此加密和签名的验证者不能解密和生成签名9公钥体制的加密过程公
11、钥体制的加密过程l 密钥的产生密钥的产生：要求接收消息的端系统，产生一对用来加密和解密的：要求接收消息的端系统，产生一对用来加密和解密的密钥密钥PKB和和SKB，如图中的接收者，如图中的接收者B，其中，其中PKB是公开钥，是公开钥，SKB是秘密是秘密钥。因此，公钥可以发布给其他人钥。因此，公钥可以发布给其他人l 公开钥的分发公开钥的分发：端系统：端系统B将加密密钥将加密密钥(PKB)予以公开。另一密钥则被予以公开。另一密钥则被保密保密(SKB)l 加密加密：A要想向要想向B发送消息发送消息m，则使用，则使用B的公开钥加密的公开钥加密m，表示为，表示为c=EPKBm其中其中c是密文，是密文，E是
12、加密算法是加密算法l 解密解密：B收到密文收到密文c后，用自己的秘密钥后，用自己的秘密钥SKB解密，即解密，即m=DSKBc，其中其中D是解密算法。因为只有是解密算法。因为只有B知道知道SKB，所以其他人都无法对，所以其他人都无法对c解密。解密。10公钥体制的认证过程公钥体制的认证过程l公钥加密算法不仅能用于加、解密，还能用于对发方公钥加密算法不仅能用于加、解密，还能用于对发方A发发送的消息送的消息m提供认证提供认证l用户用户A用自己的秘密钥用自己的秘密钥SKA对对m加密，表示为加密，表示为c=ESKAml将将c发往发往B。B用用A的公开钥的公开钥PKA对对c解密，表示为解密，表示为m=DPK
13、Acl因为从因为从m得到得到c是经过是经过A的秘密钥的秘密钥SKA加密，加密，只有只有A才能做才能做到到。因此。因此c可当做可当做A对对m的数字签字。的数字签字。l任何人只要得不到任何人只要得不到A A的秘密钥的秘密钥SKSKA A就不能篡改就不能篡改mm，所以以上过程获，所以以上过程获得了得了对消息来源对消息来源和和消息完整性消息完整性的认证。的认证。11认证符：认证符：l通过通过单向压缩函数解决长文件的签字单向压缩函数解决长文件的签字(hash)l用户数目很多时，单纯加解密的认证方法需要用户数目很多时，单纯加解密的认证方法需要很大的存储空间很大的存储空间l因为每个文件都必须以明文形式存储以
14、方便因为每个文件都必须以明文形式存储以方便实际使用，同时还实际使用，同时还必须存储每个文件被加密必须存储每个文件被加密后的密文形式即数字签字后的密文形式即数字签字，以便在有争议时，以便在有争议时用来认证文件的来源和内容用来认证文件的来源和内容l改进的方法是改进的方法是减小文件的数字签字的大小减小文件的数字签字的大小，即即先将文件经过一个函数压缩成长度较小的先将文件经过一个函数压缩成长度较小的比特串比特串，得到的，得到的比特串称为认证符比特串称为认证符12认证符具有这样一个性质：认证符具有这样一个性质：l如果保持认证符的值不变而修改文件，在计算如果保持认证符的值不变而修改文件，在计算上是不可行的
15、上是不可行的签名过程中，往往用发送者的秘密钥对认签名过程中，往往用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字证符加密，加密后的结果为原文件的数字签字。签字。l(详见第详见第7章章)13公钥体制同时提供加密和认证的过程公钥体制同时提供加密和认证的过程l认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密为了同时提供认证功能和
16、保密性，可使用双重加、解密l先签名后加密先签名后加密：发方首先用自己的秘密钥：发方首先用自己的秘密钥SKA对消息对消息m加密，用于提供数字签加密，用于提供数字签字。再用收方的公开钥字。再用收方的公开钥PKB第第2次加密，表示为次加密，表示为c=EPKBESKAml先解密再验证先解密再验证：解密过程为：解密过程为m=DPKADSKBcl即收方先用自己的秘密钥，再用发方的公开钥对收到的密文两次解密。即收方先用自己的秘密钥，再用发方的公开钥对收到的密文两次解密。l如果先加密后签名是不安全的，别人可以先将签名去掉，再签上自己的签名，如果先加密后签名是不安全的，别人可以先将签名去掉，再签上自己的签名，从
17、而实现了篡改。从而实现了篡改。144.2.2 公钥密码算法应满足的要求公钥密码算法应满足的要求公钥密码算法应满足以下要求公钥密码算法应满足以下要求l 收方收方B产生密钥对产生密钥对（公开钥（公开钥PKB和秘密钥和秘密钥SKB）在）在计算上是容易的计算上是容易的。由私钥及其他密码信息容易计算出公开密钥由私钥及其他密码信息容易计算出公开密钥(P问题问题)l 发方发方A用收方的公开钥对消息用收方的公开钥对消息m加密加密以产生密文以产生密文c，即，即c=EPKBm在在计算上是容易的计算上是容易的l 收方收方B用自己的秘密钥对用自己的秘密钥对c解密解密，即，即m=DSKBc在在计算上是容易计算上是容易的
18、的l 敌手敌手由由B的公开钥的公开钥PKB求秘密钥求秘密钥SKB在在计算上是不可行计算上是不可行的的l 敌手敌手由密文由密文c和和B的公开钥的公开钥PKB恢复明文恢复明文m在在计算上是不可行计算上是不可行的的l 加、解密次序可换加、解密次序可换，即，即EPKBDSKB(m)=DSKBEPKB(m)其中最后一条虽然非常有用，但不是对所有的算法都作要求。在构建盲其中最后一条虽然非常有用，但不是对所有的算法都作要求。在构建盲签字等算法时需要类似要求签字等算法时需要类似要求以上要求的本质之处在于要求一个以上要求的本质之处在于要求一个陷门单向函数陷门单向函数。15单向函数单向函数l是两个集合是两个集合X
19、、Y之间的一个映射之间的一个映射，使得，使得Y中每一中每一元素元素y都有惟一的一个原像都有惟一的一个原像xX，且由，且由x易于计算易于计算它的像它的像y，由，由y计算它的原像计算它的原像x是不可行的是不可行的l“易于计算易于计算”是指函数值能在其输入长度的多项是指函数值能在其输入长度的多项式时间内求出式时间内求出，即如果输入长，即如果输入长n比特，则比特，则求函数值求函数值的计算时间是的计算时间是na 的某个倍数的某个倍数，其中，其中a是一固定的常是一固定的常数数l这时称求函数值的算法属于多项式类这时称求函数值的算法属于多项式类P，否则就是，否则就是不可行的，例如，函数的输入是不可行的，例如，
20、函数的输入是n比特，比特，如果求函如果求函数值所用的时间是数值所用的时间是2n的某个倍数的某个倍数，则认为求函数，则认为求函数值是值是不可行不可行的的16易于计算和不可行两个概念与计算复杂性易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存理论中复杂度的概念极为相似，然而又存在着在着本质的区别本质的区别l在复杂性理论中，算法的复杂度是以算法在复杂性理论中，算法的复杂度是以算法在最在最坏情况或平均情况时坏情况或平均情况时的复杂度来度量的。这时的复杂度来度量的。这时可能对某些情况很容易求解，复杂度很低可能对某些情况很容易求解，复杂度很低l而在此所说的两个概念是指算法在而在此所
21、说的两个概念是指算法在几乎所有情几乎所有情况下的情形况下的情形17陷门单向函数陷门单向函数l称一个函数是陷门单向函数称一个函数是陷门单向函数，是指该函数，是指该函数是易于计算的是易于计算的，但但求它的逆是不可行的求它的逆是不可行的，除非再已知某些附加信息除非再已知某些附加信息。当。当附加信息给定后，求逆可在多项式时间完成附加信息给定后，求逆可在多项式时间完成总结为：总结为：陷门单向函数是一族可逆函数陷门单向函数是一族可逆函数fk，满足，满足l当当k和和X已知时，已知时，Y=fk(X)易于计算易于计算l当当k和和Y已知时，已知时，X=fk-1(Y)易于计算易于计算l当当Y已知但已知但k未知时，未
22、知时，X=fk-1(Y)计算上是不可行的计算上是不可行的研究公钥密码算法就是要找出合适的陷门单向函数研究公钥密码算法就是要找出合适的陷门单向函数184.2.3 对公钥密码体制的攻击对公钥密码体制的攻击 以下讨论的攻击是指对所有公钥密码体制都有效以下讨论的攻击是指对所有公钥密码体制都有效的平凡的攻击的平凡的攻击l涉及到公钥算法所基于的困难问题的安全性和参数空间涉及到公钥算法所基于的困难问题的安全性和参数空间大小的安全性大小的安全性第一种平凡的攻击：（穷搜索攻击与密钥长度）第一种平凡的攻击：（穷搜索攻击与密钥长度）l如果密钥太短如果密钥太短，公钥密码体制也易受到，公钥密码体制也易受到穷搜索穷搜索攻
23、击攻击l然而又由于公钥密码体制所使用的可逆函数的计算复杂然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。性与密钥长度常常不是呈线性关系，而是增大得更快。所以所以密钥长度太大又会使得加解密运算太慢而不实用密钥长度太大又会使得加解密运算太慢而不实用l因此公因此公钥密码体制目前主要用于密钥管理和数字签字钥密码体制目前主要用于密钥管理和数字签字。即即处理短消息如密钥和处理短消息如密钥和hash值值19第二种平凡的攻击第二种平凡的攻击l是寻找从公开钥计算秘密钥的方法是寻找从公开钥计算秘密钥的方法l目前为止，对常用公钥算法还都目前为止，对常用公钥算法还都未能
24、够证明这种攻击是不可行未能够证明这种攻击是不可行的的第三种平凡的攻击：第三种平凡的攻击：(可能字攻击可能字攻击)l仅适用于对公钥密码算法的攻击仅适用于对公钥密码算法的攻击l例如对例如对56比特的比特的DES密钥用公钥密码算法加密后发送，敌手用算密钥用公钥密码算法加密后发送，敌手用算法的公开钥法的公开钥对所有可能的密钥加密后与截获的密文相比较对所有可能的密钥加密后与截获的密文相比较l如果一样，则相应的明文即如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算密钥就被找出。因此不管公钥算法的密钥多长，法的密钥多长，攻击的本质是对攻击的本质是对56比特比特DES密钥的穷搜索攻击密钥的穷搜索攻击
25、l抵抗方法抵抗方法是在欲发送的明文消息后是在欲发送的明文消息后添加一些随机比特添加一些随机比特不同的公钥密码算法在设计和实现中的密码协议是影响安不同的公钥密码算法在设计和实现中的密码协议是影响安全性的主要方面，不同算法的攻击不同。全性的主要方面，不同算法的攻击不同。公钥的安全性是指计算上的安全性公钥的安全性是指计算上的安全性204.3 RSA算法算法1978年由年由R.Rivest,A.Shamir和和L.Adleman提出提出的一种用数论构造的、也是迄今为止理论上最为的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，已得到广泛的应用成熟完善的公钥密码体制，已得到广泛的应用lR
26、 L Rivest,A Shamir,L Adleman,On Digital Signatures and Public Key Cryptosystems,Communications of the ACM,vol 21 no 2,pp120-126,Feb 1978l它既可用于它既可用于加密加密、又可用于、又可用于数字签字数字签字。lRSA算法的安全性是算法的安全性是基于数论中大整数分解的困难性基于数论中大整数分解的困难性(但可能达不到大数分解的困难强度但可能达不到大数分解的困难强度)214.3.1 算法描述算法描述1密钥的产生密钥的产生 选两个保密的大素数选两个保密的大素数p和和q 计
27、算计算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)互素，模互素，模(n)的乘法逆元一定存在的乘法逆元一定存在 以以e,n为公开钥为公开钥,d,p,q为秘密钥为秘密钥l秘密钥也可记为秘密钥也可记为d，或，或d,n，如果是系统负责产生密钥，则用户可，如果是系统负责产生密钥，则用户可能不知道能不知道p,q222加密加密l加密时加密时首先将明文比特串分组首先将明文比特串
28、分组，使得每个分组，使得每个分组对应的十进制数小于对应的十进制数小于n，即分组长度小于，即分组长度小于log2n。l然后对每个明文分组然后对每个明文分组m，作加密运算：，作加密运算：cme mod n3解密解密l对密文分组的解密运算为：对密文分组的解密运算为：mcd mod n23RSA算法中解密过程的正确性证明算法中解密过程的正确性证明证明证明：由由cme mod n，可知，可知 cd mod nmed mod nmk(n)+1 mod n下面分两种情况：下面分两种情况：m与与n互素，互素，则由则由Euler定理得定理得lm(n)1 mod n，mk(n)1 mod n，mk(n)+1m m
29、od nl即即cd mod nm gcd(m,n)1，因，因n=pq，所以所以m是是p的倍数或的倍数或q的倍数，的倍数，不妨设不妨设m=cp，其中其中c为一正整数。为一正整数。此时必有此时必有gcd(m,q)=1，否则，否则m也是也是q的倍数，从而的倍数，从而是是pq的倍数，与的倍数，与mn=pq矛盾。矛盾。l由由gcd(m,q)=1及及Euler定理得定理得m(q)1 mod q，所以，所以lmk(q)1 mod q，(mk(q)(p)1 mod q，即即 mk(n)1 mod ql因此存在一整数因此存在一整数r，使得，使得mk(n)1+rq，l两边同乘以两边同乘以m=cp 得得 mk(n)
30、1m+rcpqm+rcnl即即mk(n)1m mod n，所以，所以cd mod nm。(证毕证毕)24【例【例4-24】：】：l 选选p=7，q=17。求。求n=pq=119，(n)=(p-1)(q-1)=96l取取e=5，满足，满足1e(n)，且，且gcd(n),e)=1l确定满足确定满足de=1 mod 96且小于且小于96的的d，因为，因为775=385=496+1，所以，所以d为为77l公开钥为公开钥为5，119，秘密钥为，秘密钥为77l设明文设明文m=19，则由加密过程得密文为，则由加密过程得密文为lc195 mod 1192476099 mod 11966l解密为解密为6677m
31、od 11919【例【例4-25】略】略l加密长消息时相当于一个分组密码算法加密长消息时相当于一个分组密码算法l首先将明文比特串分组，使得每个分组对应的十进制数小于首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分，即分组长度小于组长度小于log2n254.3.2 RSA算法中的计算问题算法中的计算问题1.RSA的加密与解密过程的加密与解密过程模运算的累次乘法模运算的累次乘法lRSA的加密、解密过程都为的加密、解密过程都为求一个整数的整数次幂，再求一个整数的整数次幂，再取模取模l如果如果按其含义直接计算，则中间结果非常大按其含义直接计算，则中间结果非常大，有可能超出计算有可能超出计算
32、机所允许的整数取值范围机所允许的整数取值范围。如上例中解密运算。如上例中解密运算6677 mod 119，先，先求求6677再取模，则中间结果就已远远超出了计算机允许的整数取再取模，则中间结果就已远远超出了计算机允许的整数取值范围。值范围。l用模运算的性质：即用模运算的性质：即采用累次乘法，采用累次乘法，可减小中间结果可减小中间结果l(ab)mod n=(a mod n)(b mod n)mod n26快速指数算法快速指数算法l考虑如何提高加、解密运算中考虑如何提高加、解密运算中模指数运算的有效性模指数运算的有效性。例。例如求如求x16，直接计算需做，直接计算需做15次乘法。若重复对每个部分次
33、乘法。若重复对每个部分结果做平方运算即求结果做平方运算即求x，x2，x4，x8，x16则只需则只需4次乘法次乘法求求am可如下进行，其中可如下进行，其中a，m是正整数：是正整数：l将将m表示为二进制形式表示为二进制形式bkbk-1b0，即，即lm=bk2k+bk-12k-1+b12+b0因此因此 am l 例如：例如：19=124+023+022+121+120，所以，所以a19=(a1)2a0)2a0)2a1)2a101212222)(bbbbbaaaaakkk27快速指数算法：快速指数算法：lc=0;d=1；lfor i=k downto 0 do l c=2c;/仅为验证以上过程，而在具
34、体算法中可删去仅为验证以上过程，而在具体算法中可删去ld=(dd)mod n;/计算平方计算平方lif bi=1 then lc=c+1;/仅为验证以上过程，而在具体算法中可删去仅为验证以上过程，而在具体算法中可删去ld=(da)mod n /bi=1时与时与a相乘相乘lllreturn d.其中其中d是中间结果，是中间结果，d的终值即为所求结果。的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算对计算结果无任何贡献，算法中完全可将之去掉结果无任何贡献，算法中完全可将之去掉28计算复杂度计算复杂度:llW(m)次模
35、乘（次模乘（m为模指数）为模指数）ll为指数的为指数的bit长，长，W(m)为指数为指数m的重量的重量(二进制比特二进制比特1的个数的个数)例：例：求求7560 mod 561。l将将560表示为表示为1000110000，算法的中间结果如表，算法的中间结果如表4-6所示所示l所以所以7560 mod 561=1l(5613x11x17,(561)=2x10 x16=320,780=1 mod 561)i 9 8 7 6 5 4 3 2 1 0bi 1 0 0 0 1 1 0 0 0 0c0 1 2 4 8 17 35 70 140 280 560d1 7 49 157 526 160 241
36、 298 166 67 129一种改进的一种改进的RSA实现方法实现方法(即即4.3.3节）节）lRSA的加密很快，因为的加密很快，因为加密指数加密指数e一般选择得很小一般选择得很小l解密指数解密指数d很大很大，需要计算模，需要计算模 300digits(or 1024bits)的乘法，计算机的乘法，计算机不能直接处理这么大的数，计算速度很慢，需要考虑其它技术，加速不能直接处理这么大的数，计算速度很慢，需要考虑其它技术，加速RSA的实现的实现l如果知道如果知道p和和q，可采用中国剩余定理，可采用中国剩余定理CRT：lCRT 对对RSA解密算法生成两个解密方程（利用解密算法生成两个解密方程（利用
37、M=Cd mod N，N=pq）l即：即：M1=M mod p=(C mod p)d mod(p-1)mod p l M2=M mod q=(C mod q)d mod(q-1)mod ql解方程解方程 M=M1 mod p l M=M2 mod q l具有唯一解（利用具有唯一解（利用CRT）：）：l M=M1q(q1mod p)+M2p(p1mod q)mod Nl不考虑不考虑CRT的计算代价，改进的算法的解密速度是原来的的计算代价，改进的算法的解密速度是原来的4倍倍l若考虑若考虑CRT的计算代价，改进后的算法解密速度是原来的的计算代价，改进后的算法解密速度是原来的3倍多倍多302.RSA密
38、钥的产生密钥的产生l需考虑需考虑两个大素数两个大素数p、q的选取，以及的选取，以及e的选取和的选取和d的计算的计算ln(=pq)是公开的，为了防止敌手通过穷搜索发现是公开的，为了防止敌手通过穷搜索发现p、q，这这两个素数应是在一个足够大的整数集合中选取的大数两个素数应是在一个足够大的整数集合中选取的大数l(1)如何有效地寻找大素数是第一个需要解决的问题如何有效地寻找大素数是第一个需要解决的问题l寻找大素数时寻找大素数时一般是先随机选取一个大的奇数一般是先随机选取一个大的奇数（例如用伪随机数产（例如用伪随机数产生器），生器），l然后用素性检验算法检验这一奇数是否为素数然后用素性检验算法检验这一奇
39、数是否为素数，如果不是则选取另，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止一大奇数，重复这一过程，直到找到素数为止l素性检验算法通常都是概率性的，素性检验算法通常都是概率性的，常用常用Miller-Rabin概率检测算法概率检测算法实现实现l寻找大素数是一个比较繁琐的工作，然而在寻找大素数是一个比较繁琐的工作，然而在RSA体制中，只有在产体制中，只有在产生新密钥时才需执行这一工作生新密钥时才需执行这一工作31l(2)p和和q决定出后，决定出后，下一个需要解决的问题是下一个需要解决的问题是l如何选取满足如何选取满足1eq，由，由 (n)=(p-1)(q-1)，则有，则有l p+q=
40、n(n)+1，以及，以及l p-q=l由此可见，由由此可见，由p、q确定确定(n)和由和由(n)确定确定p、q是等价的是等价的nnnnqp4 1)(4)(2235为保证算法的安全性，对为保证算法的安全性，对p和和q提出以下要求：提出以下要求：l(1)|p-q|要大要大l由由(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的如下分解步骤：的如下分解步骤：l 顺序检查大于顺序检查大于n的每一整数的每一整数x，直到找到一个，直到找到一个x使得使得x
41、2-n是某一整数（记为是某一整数（记为y）的平方。）的平方。l 由由x2-n=y2，得，得n=(x+y)(x-y)。l(2)p-1和和q-1都应有大素因子都应有大素因子(强素数强素数)l这是因为这是因为RSA算法存在着可能的算法存在着可能的重复加密攻击重复加密攻击法。法。36重复加密攻击法重复加密攻击法l设攻击者截获密文设攻击者截获密文c，可如下进行重复加密：，可如下进行重复加密：l ll若若 ，即，即 ，则有，则有 ，l即即 所以在上述所以在上述重复加密的倒数第重复加密的倒数第2步就已恢复出明文步就已恢复出明文ml这种攻击法只有在这种攻击法只有在 t 较小时才是可行的。较小时才是可行的。为抵
42、抗这种攻击，为抵抗这种攻击，p、q的选取的选取应保证使应保证使 t 很大很大。l设设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能被容易地确定能被容易地确定nmmceeeemod)
43、(2nmmceeeemod)(322nmmcttteeeemod)(11nmmcttteeeemod)(1ncmtemod1ncmeetmod)(nmmtemodnmctemod1nmmtemodnmtemod11374.3.5 对对RSA的攻击的攻击RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的是由于参数选择不当造成的1.共模攻击共模攻击l在实现在实现RSA时，为方便起见，可能给每一用户相同的模数时，为方便起见，可能给每一用户相同的模数n，虽然加解，虽然加解密密钥不同，然而这样做是不行的密密钥不同，然而这样做是不
44、行的l设两个用户的公开钥分别为设两个用户的公开钥分别为e1和和e2，且，且e1和和e2互素（一般情况都成立），互素（一般情况都成立），明文消息是明文消息是m，密文分别是，密文分别是l c1me1(mod n)l c2me2(mod n)l敌手截获敌手截获c1和和c2后，可如下恢复后，可如下恢复m。用推广的。用推广的Euclid算法求出满足算法求出满足 re1+se2=1的两个整数的两个整数r和和s，其中一个为负，设为，其中一个为负，设为r。再次用推广的。再次用推广的Euclid算法求出算法求出c1-1，由此得，由此得(c1-1)-rc2sm(mod n)。382.低指数攻击低指数攻击l假定将假
45、定将RSA算法同时用于多个用户（为讨论方便，以下算法同时用于多个用户（为讨论方便，以下假定假定3个），然而每个用户的加密指数（即公开钥）都个），然而每个用户的加密指数（即公开钥）都很小。很小。l设设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)l由中国剩余定理可求出由中国剩余定理可求出m3(mod n1n
46、2n3)。由于。由于m3n1n2n3，可直接由可直接由m3开立方根得到开立方根得到m。l最初建议使用最初建议使用e=3，不安全，不安全，e是有下限的是有下限的明文消息空间太小时，消息需要填充明文消息空间太小时，消息需要填充394.4 背包密码体制背包密码体制设设A=(a1,a2,an)是由是由n个不同的正整数构成的个不同的正整数构成的n元组，元组，s是另是另一已知的正整数。一已知的正整数。背包问题就是从背包问题就是从A中求出所有的中求出所有的ai，使其，使其和等于和等于s。其中。其中A称为背包向量称为背包向量，s是背包的容积是背包的容积。l例如例如,A=(43,129,215,473,903,
47、302,561,1165,697,1523)，s=3231。l由于由于 3231=129+473+903+561+1165l所以从所以从A中找出的满足要求的数有中找出的满足要求的数有129、473、903、561、1165原则上讲，通过检查原则上讲，通过检查A的所有子集，总可找出问题的解（若的所有子集，总可找出问题的解（若有解的话）有解的话）l本例本例A的子集共有的子集共有210=1024个（包括空集）。然而如果个（包括空集）。然而如果A中元素个数中元素个数n很大，子集个数很大，子集个数2n将非常大。如将非常大。如A中有中有300个元素，个元素，A的子集有的子集有2300。寻找满足要求的寻找满
48、足要求的A的子集没有比穷搜索更好的算法，因此背包问题是的子集没有比穷搜索更好的算法，因此背包问题是NPC问题。问题。40由背包问题构造公钥密码体制同样是要构造一个单向函数由背包问题构造公钥密码体制同样是要构造一个单向函数fl将将x(1x2n-1)写成长为写成长为n的二元表示的二元表示0001,0010，0011,1111,f(x)定义为定义为A中所有中所有ai的和，其中的和，其中x的二元表示的第的二元表示的第i位为位为1，即，即lf(1)=f(0001)=anlf(2)=f(0010)=an-1lf(3)=f(0011)=an-1+anl lf(2n-1)=f(1111)=a1+a2+anl使
49、用向量乘使用向量乘(内积内积)，有，有f(x)=ABx，其中，其中Bx是是x二元表示的列向量。二元表示的列向量。l上例中上例中f(364)=f(0101101100)=129+473+903+561+1165=3231l类似地可求出类似地可求出:lf(609)=2942,f(686)=3584,f(32)=903,f(46)=3326,f(128)=215,f(261)=2817,f(44)=2629,f(648)=819。l由由f的定义可见，已知的定义可见，已知x很容易求很容易求f(x)，但已知但已知f(x)求求x就是要解背包问题就是要解背包问题。当然在实际应用中，当然在实际应用中，n不能太
50、小不能太小，比如说，至少为，比如说，至少为200。41用用f对明文消息对明文消息m加密时，加密时，首先将首先将m写成二元表示写成二元表示，再将其分成长为，再将其分成长为n的的分组（分组（最后一个分组不够长的话，可在后面填充一些最后一个分组不够长的话，可在后面填充一些0），然后求每一），然后求每一分组的函数值，以函数值作为密文分组。分组的函数值，以函数值作为密文分组。l例如，明文消息是英文文本，则可将每个字母用其在字母表中的序号表示，例如，明文消息是英文文本，则可将每个字母用其在字母表中的序号表示，再将该序号转换为二进制形式（再将该序号转换为二进制形式（5位即可），如表位即可），如表4.5所示，
