《密码学4－公钥密码ppt课件》由会员分享，可在线阅读，更多相关《密码学4－公钥密码ppt课件（90页珍藏版）》请在金锄头文库上搜索。
1、本科生学位课：现代密码学本科生学位课：现代密码学第四章第四章 公钥密码公钥密码主讲教师：董庆宽研究方向：密码学与信息安全Email ：4.1 密码学中常用数学知识密码学中常用数学知识4.2 公钥密码体制的基本概念公钥密码体制的基本概念4.3 RSA算法算法4.4 背包体制背包体制4.5 Rabin体制体制 4.6 NTRU公钥密码系统公钥密码系统4.7 椭圆曲线密码体制椭圆曲线密码体制4.8 基于身份的密码体制基于身份的密码体制本章提要本章提要24.1 密码学中的常用数学知识密码学中的常用数学知识群、环、域、素数群、环、域、素数模运算模运算费尔马定理费尔马定理lap-1=1 mod p ，p是
2、素数是素数欧拉函数欧拉函数l (n)：小小于于n的的且且与与n互互素素的的正正整数个数整数个数la (n)=1 mod n 素性检验素性检验l1.爱爱拉拉托托斯斯散散筛筛法法(Eratosthenes)l依次删去小于依次删去小于 素数的倍数素数的倍数l2. Miller-Rabin概率检测法概率检测法l3.AKS欧几里得算法、扩展欧几里德算法欧几里得算法、扩展欧几里德算法l求最大公约数和乘法的逆元求最大公约数和乘法的逆元中国剩余定理中国剩余定理l求一次同余方程组的解求一次同余方程组的解离散对数，本原根离散对数，本原根平方剩余平方剩余计算复杂性计算复杂性34.2 公钥密码体制的基本概念公钥密码体
3、制的基本概念公钥密码体制的出现在密码学史上是一个最大的而公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。且是惟一真正的革命。为密码学发展提供了新的理为密码学发展提供了新的理论和技术基础论和技术基础l公钥密码算法公钥密码算法基本工具不再是代换和置换，而是数学函基本工具不再是代换和置换，而是数学函数数l以非对称的形式使用两个密钥以非对称的形式使用两个密钥，两个密钥的使用对保密，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。性、密钥分配、认证等都有着深刻的意义。公钥密码体制的概念公钥密码体制的概念是在解决单钥密码体制中最难是在解决单钥密码体制中最难解决的两个问题时解决的两
4、个问题时提出的提出的，即，即密钥分配和数字签字密钥分配和数字签字4对称密码算法的缺陷对称密码算法的缺陷l密钥分配问题密钥分配问题： 通信双方加密通信前通信双方加密通信前要通过秘密的安全要通过秘密的安全信道协商加密密钥，这种安全信道可能很难实现信道协商加密密钥，这种安全信道可能很难实现；对这；对这个个信道安全性的要求信道安全性的要求比正常传送消息信道的安全性要比正常传送消息信道的安全性要高高l密钥管理问题密钥管理问题： 在多用户网络中，任何两个用户之间都在多用户网络中，任何两个用户之间都需要有共享的秘密钥，需要有共享的秘密钥，n个用户需要个用户需要Cn2=n(n-1)/2个密钥，个密钥，n=50
5、00时，时，Cn2=12,497,500，系统开销非常大，系统开销非常大l没有签名功能没有签名功能： 当主体当主体A收到主体收到主体B的电子文挡时，无的电子文挡时，无法向第三方证明此电子文档确实来源于法向第三方证明此电子文档确实来源于B， 传统单钥加传统单钥加密算法无法实现抗抵赖的需求密算法无法实现抗抵赖的需求5公钥密码的主要作用公钥密码的主要作用公钥加密公钥加密l用于加密任何消息，象分组密码一样使用用于加密任何消息，象分组密码一样使用 l任何人可以用公钥加密消息，私钥的拥有者可以解密消息任何人可以用公钥加密消息，私钥的拥有者可以解密消息 数字签名数字签名 (Digital Signature
6、) l用于生成对某消息的数字签名用于生成对某消息的数字签名l私钥的拥有者生成数字签名，任何人可以用公钥验证签名私钥的拥有者生成数字签名，任何人可以用公钥验证签名l签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法基于公钥的密钥分配基于公钥的密钥分配(Key Distribution)l用于交换秘密信息，常用于协商对称加密算法的密钥用于交换秘密信息，常用于协商对称加密算法的密钥l可采用公钥加密的算法实现密钥分配可采用公钥加密的算法实现密钥分配l也可使用单独设计的密钥交换算法，如也可使用单独设计的密钥交换算法，如DH密钥交换协议实现
7、密钥分配密钥交换协议实现密钥分配其它应用：其它应用：l零知识证明，公平抛币等等，（用于各种目的的认证）零知识证明，公平抛币等等，（用于各种目的的认证）6公钥密码的发展概况公钥密码的发展概况l1976年年Diffie和和Hellman在其在其“密码学新方向密码学新方向”一文中提出公钥密码：一文中提出公钥密码：lW.Diffie and M.E.Hellman, “New Directions in Cryptography”, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976：644-654l1978年年Merkle和和
8、Hellman基于背包问题提出了首个公钥密码体制，但基于背包问题提出了首个公钥密码体制，但两年后被破译两年后被破译l1978年年Rivest，Shamir & Adleman基于大数分解的困难性提出了基于大数分解的困难性提出了RSA公钥算法，成为迄今为止最为成熟和完善的公钥密码体制公钥算法，成为迄今为止最为成熟和完善的公钥密码体制l1985年出现了基于求解离散对数困难性的公钥密码算法年出现了基于求解离散对数困难性的公钥密码算法DLPl90年代逐步出现椭圆曲线年代逐步出现椭圆曲线(ECC)等其他公钥算法等其他公钥算法l当前的公钥密码算法主要是当前的公钥密码算法主要是基于大数分解困难性基于大数分解
9、困难性和和离散对数困难性离散对数困难性来构来构造的，造的，椭圆曲线椭圆曲线上也可构造这类体制，相同密钥长度下其安全性更高上也可构造这类体制，相同密钥长度下其安全性更高参考资料：参考资料：公钥密码学公钥密码学等等74.2.1 公钥密码体制的原理公钥密码体制的原理公钥密码算法的最大特点是公钥密码算法的最大特点是采用两个相关密钥将采用两个相关密钥将加密和解密能力分开加密和解密能力分开l一个密钥是公开的一个密钥是公开的，称为，称为公开密钥公开密钥，简称，简称公开钥公开钥，用于，用于加密、验证签名加密、验证签名，可以被任何人知道，可以被任何人知道l另一个密钥是为用户专用另一个密钥是为用户专用，因而是保密
10、的因而是保密的，只能被消息，只能被消息的接收者或签名者知道，称为的接收者或签名者知道，称为秘密密钥秘密密钥，简称，简称秘密钥秘密钥，用于用于解密、产生签名解密、产生签名l因此公钥密码体制也称为因此公钥密码体制也称为双钥密码体制双钥密码体制算法有以下重要特性：算法有以下重要特性： 已知密码算法和加密密钥，已知密码算法和加密密钥，求解密密钥在计算上是不可行的求解密密钥在计算上是不可行的l因此加密和签名的验证者不能解密和生成签名因此加密和签名的验证者不能解密和生成签名8公钥体制的加密过程公钥体制的加密过程l 密钥的产生密钥的产生：要求接收消息的端系统，产生一对用来加密和解密的：要求接收消息的端系统，
11、产生一对用来加密和解密的密钥密钥PKB和和SKB，如图中的接收者，如图中的接收者B，其中，其中PKB是公开钥，是公开钥，SKB是秘密是秘密钥。因此，公钥可以发布给其他人钥。因此，公钥可以发布给其他人l 公开钥的分发公开钥的分发：端系统：端系统B将加密密钥将加密密钥(PKB)予以公开。另一密钥则被予以公开。另一密钥则被保密保密(SKB)l 加密加密：A要想向要想向B发送消息发送消息m，则使用，则使用B的公开钥加密的公开钥加密m，表示为，表示为c=EPKBm其中其中c是密文，是密文，E是加密算法是加密算法l 解密解密：B收到密文收到密文c后，用自己的秘密钥后，用自己的秘密钥SKB解密，即解密，即m
12、=DSKBc，其中其中D是解密算法。因为只有是解密算法。因为只有B知道知道SKB，所以其他人都无法对，所以其他人都无法对c解密。解密。9公钥体制的认证过程公钥体制的认证过程l公钥加密算法不仅能用于加、解密，还能用于对发方公钥加密算法不仅能用于加、解密，还能用于对发方A发发送的消息送的消息m提供认证提供认证l用户用户A用自己的秘密钥用自己的秘密钥SKA对对m加密，表示为加密，表示为c=ESKAml将将c发往发往B。B用用A的公开钥的公开钥PKA对对c解密，表示为解密，表示为m=DPKAcl因为从因为从m得到得到c是经过是经过A的秘密钥的秘密钥SKA加密，加密，只有只有A才能做才能做到到。因此。因
13、此c可当做可当做A对对m的数字签字。的数字签字。l任何人只要得不到任何人只要得不到A A的秘密钥的秘密钥SKSKA A就不能篡改就不能篡改m m，所以以上过程获得，所以以上过程获得了了对消息来源对消息来源和和消息完整性消息完整性的认证。的认证。10认证符：认证符：l通过通过单向压缩函数解决长文件的签字单向压缩函数解决长文件的签字(hash)l用户数目很多时，单纯加解密的认证方法需要用户数目很多时，单纯加解密的认证方法需要很大的存储空间很大的存储空间l因为每个文件都必须以明文形式存储以方便因为每个文件都必须以明文形式存储以方便实际使用，同时还实际使用，同时还必须存储每个文件被加密必须存储每个文件
14、被加密后的密文形式即数字签字后的密文形式即数字签字，以便在有争议时，以便在有争议时用来认证文件的来源和内容用来认证文件的来源和内容l改进的方法是改进的方法是减小文件的数字签字的大小减小文件的数字签字的大小，即即先将文件经过一个函数压缩成长度较小的先将文件经过一个函数压缩成长度较小的比特串比特串，得到的，得到的比特串称为认证符比特串称为认证符11认证符具有这样一个性质：认证符具有这样一个性质： l如果保持认证符的值不变而修改文件，在计算如果保持认证符的值不变而修改文件，在计算上是不可行的上是不可行的签名过程中，往往用发送者的秘密钥对认签名过程中，往往用发送者的秘密钥对认证符加密，加密后的结果为原
15、文件的数字证符加密，加密后的结果为原文件的数字签字。签字。l(详见第详见第7章章)12公钥体制同时提供加密和认证的过程公钥体制同时提供加密和认证的过程l认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密为了同时提供认证功能和保密性，可使用双重加、解密l先签名后加密先签名后加密：发方首先用自己的秘密钥：发方首先用自己的秘密钥SKA对消
16、息对消息m加密，用于提供数字签加密，用于提供数字签字。再用收方的公开钥字。再用收方的公开钥PKB第第2次加密，表示为次加密，表示为c=EPKBESKAml先解密再验证先解密再验证：解密过程为：解密过程为m=DPKADSKBcl即收方先用自己的秘密钥，再用发方的公开钥对收到的密文两次解密。即收方先用自己的秘密钥，再用发方的公开钥对收到的密文两次解密。l如果先加密后签名是不安全的，别人可以先将签名去掉，再签上自己的签名，如果先加密后签名是不安全的，别人可以先将签名去掉，再签上自己的签名，从而实现了篡改。从而实现了篡改。 134.2.2 公钥密码算法应满足的要求公钥密码算法应满足的要求公钥密码算法应
17、满足以下要求公钥密码算法应满足以下要求l 收方收方B产生密钥对产生密钥对（公开钥（公开钥PKB和秘密钥和秘密钥SKB）在）在计算上是容易的计算上是容易的。由私钥及其他密码信息容易计算出公开密钥由私钥及其他密码信息容易计算出公开密钥(P问题问题) l 发方发方A用收方的公开钥对消息用收方的公开钥对消息m加密加密以产生密文以产生密文c，即，即c=EPKBm在在计算上是容易的计算上是容易的l 收方收方B用自己的秘密钥对用自己的秘密钥对c解密解密，即，即m=DSKBc在在计算上是容易计算上是容易的的l 敌手敌手由由B的公开钥的公开钥PKB求秘密钥求秘密钥SKB在在计算上是不可行计算上是不可行的的l 敌
18、手敌手由密文由密文c和和B的公开钥的公开钥PKB恢复明文恢复明文m在在计算上是不可行计算上是不可行的的l 加、解密次序可换加、解密次序可换，即，即EPKBDSKB(m)=DSKBEPKB (m)其中最后一条虽然非常有用，但不是对所有的算法都作要求。在构建盲其中最后一条虽然非常有用，但不是对所有的算法都作要求。在构建盲签字等算法时需要类似要求签字等算法时需要类似要求以上要求的本质之处在于要求一个以上要求的本质之处在于要求一个陷门单向函数陷门单向函数。 14单向函数单向函数l是两个集合是两个集合X、Y之间的一个映射之间的一个映射，使得，使得Y中每一中每一元素元素y都有惟一的一个原像都有惟一的一个原
19、像xX，且由，且由x易于计算易于计算它的像它的像y，由，由y计算它的原像计算它的原像x是不可行的是不可行的l“易于计算易于计算”是指函数值能在其输入长度的多项是指函数值能在其输入长度的多项式时间内求出式时间内求出，即如果输入长，即如果输入长n比特，则比特，则求函数值求函数值的计算时间是的计算时间是na 的某个倍数的某个倍数，其中，其中a是一固定的常是一固定的常数数l这时称求函数值的算法属于多项式类这时称求函数值的算法属于多项式类P，否则就是，否则就是不可行的，例如，函数的输入是不可行的，例如，函数的输入是n比特，比特，如果求函如果求函数值所用的时间是数值所用的时间是2n的某个倍数的某个倍数，则
20、认为求函数，则认为求函数值是值是不可行不可行的的15易于计算和不可行两个概念与计算复杂性易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存理论中复杂度的概念极为相似，然而又存在着在着本质的区别本质的区别l在复杂性理论中，算法的复杂度是以算法在复杂性理论中，算法的复杂度是以算法在最在最坏情况或平均情况时坏情况或平均情况时的复杂度来度量的。这时的复杂度来度量的。这时可能对某些情况很容易求解，复杂度很低可能对某些情况很容易求解，复杂度很低l而在此所说的两个概念是指算法在而在此所说的两个概念是指算法在几乎所有情几乎所有情况下的情形况下的情形16陷门单向函数陷门单向函数l称一个函数
21、是陷门单向函数称一个函数是陷门单向函数，是指该函数，是指该函数是易于计算的是易于计算的，但但求它的逆是不可行的求它的逆是不可行的，除非再已知某些附加信息除非再已知某些附加信息。当。当附加信息给定后，求逆可在多项式时间完成附加信息给定后，求逆可在多项式时间完成总结为：总结为： 陷门单向函数是一族可逆函数陷门单向函数是一族可逆函数fk，满足，满足l当当k和和X已知时，已知时，Y=fk(X)易于计算易于计算l当当k和和Y已知时，已知时，X=fk-1(Y)易于计算易于计算l当当Y已知但已知但k未知时，未知时，X=fk-1(Y)计算上是不可行的计算上是不可行的研究公钥密码算法就是要找出合适的陷门单向函数
22、研究公钥密码算法就是要找出合适的陷门单向函数174.2.3 对公钥密码体制的攻击对公钥密码体制的攻击 以下讨论的攻击是指对所有公钥密码体制都有效以下讨论的攻击是指对所有公钥密码体制都有效的平凡的攻击的平凡的攻击l涉及到公钥算法所基于的困难问题的安全性和参数空间涉及到公钥算法所基于的困难问题的安全性和参数空间大小的安全性大小的安全性第一种平凡的攻击：（穷搜索攻击与密钥长度）第一种平凡的攻击：（穷搜索攻击与密钥长度）l如果密钥太短如果密钥太短，公钥密码体制也易受到，公钥密码体制也易受到穷搜索穷搜索攻击攻击l然而又由于公钥密码体制所使用的可逆函数的计算复杂然而又由于公钥密码体制所使用的可逆函数的计算
23、复杂性与密钥长度常常不是呈线性关系，而是增大得更快。性与密钥长度常常不是呈线性关系，而是增大得更快。所以所以密钥长度太大又会使得加解密运算太慢而不实用密钥长度太大又会使得加解密运算太慢而不实用l因此公因此公钥密码体制目前主要用于密钥管理和数字签字钥密码体制目前主要用于密钥管理和数字签字。即即处理短消息如密钥和处理短消息如密钥和hash值值18第二种平凡的攻击第二种平凡的攻击l是寻找从公开钥计算秘密钥的方法是寻找从公开钥计算秘密钥的方法l目前为止，对常用公钥算法还都目前为止，对常用公钥算法还都未能够证明这种攻击是不可行未能够证明这种攻击是不可行的的第三种平凡的攻击：第三种平凡的攻击：(可能字攻击
24、可能字攻击)l仅适用于对公钥密码算法的攻击仅适用于对公钥密码算法的攻击l例如对例如对56比特的比特的DES密钥用公钥密码算法加密后发送，敌手用算密钥用公钥密码算法加密后发送，敌手用算法的公开钥法的公开钥对所有可能的密钥加密后与截获的密文相比较对所有可能的密钥加密后与截获的密文相比较l如果一样，则相应的明文即如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算密钥就被找出。因此不管公钥算法的密钥多长，法的密钥多长，攻击的本质是对攻击的本质是对56比特比特DES密钥的穷搜索攻击密钥的穷搜索攻击l抵抗方法抵抗方法是在欲发送的明文消息后是在欲发送的明文消息后添加一些随机比特添加一些随机比特不同的
25、公钥密码算法在设计和实现中的密码协议是影响安不同的公钥密码算法在设计和实现中的密码协议是影响安全性的主要方面，不同算法的攻击不同。全性的主要方面，不同算法的攻击不同。公钥的安全性是指计算上的安全性公钥的安全性是指计算上的安全性194.3 RSA算法算法1978年由年由R.Rivest, A.Shamir和和L.Adleman提出提出的一种用数论构造的、也是迄今为止理论上最为的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，已得到广泛的应用成熟完善的公钥密码体制，已得到广泛的应用lR L Rivest, A Shamir, L Adleman, On Digital Signat
26、ures and Public Key Cryptosystems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978l它既可用于它既可用于加密加密、又可用于、又可用于数字签字数字签字。lRSA算法的安全性是算法的安全性是基于数论中大整数分解的困难性基于数论中大整数分解的困难性(但可能达不到大数分解的困难强度但可能达不到大数分解的困难强度)204.3.1 算法描述算法描述1密钥的产生密钥的产生 选两个保密的大素数选两个保密的大素数p和和q 计算计算n=pq， (n)=(p-1)(q-1)，其中，其中 (n)是是n的欧拉函数值
27、的欧拉函数值 选一整数选一整数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,q212加密加密l加密时加密时首先将明文比特串分组首先将明文比特串分组，使得每个分组，使得每个分组对应的十进制数小于对应的十进制数小于
28、n，即分组长度小于，即分组长度小于log2n。l然后对每个明文分组然后对每个明文分组m，作加密运算：，作加密运算： cme mod n3解密解密l对密文分组的解密运算为：对密文分组的解密运算为： mcd mod n22RSA算法中解密过程的正确性证明算法中解密过程的正确性证明证明证明： 由由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 mod nl即即cd mod nm gcd(m,n)1
29、，因，因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)1m+rcpqm+rcnl即即mk (
30、n)1m mod n，所以，所以cd mod nm。(证毕证毕)23【例例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解密为解密为6677mod 11919【例例4-25】略
31、略l加密长消息时相当于一个分组密码算法加密长消息时相当于一个分组密码算法l首先将明文比特串分组，使得每个分组对应的十进制数小于首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分，即分组长度小于组长度小于log2n244.3.2 RSA算法中的计算问题算法中的计算问题1. RSA的加密与解密过程的加密与解密过程模运算的累次乘法模运算的累次乘法lRSA的加密、解密过程都为的加密、解密过程都为求一个整数的整数次幂，再求一个整数的整数次幂，再取模取模l如果如果按其含义直接计算，则中间结果非常大按其含义直接计算，则中间结果非常大，有可能超出计算有可能超出计算机所允许的整数取值范围机所允许的整数
32、取值范围。如上例中解密运算。如上例中解密运算6677 mod 119，先，先求求6677再取模，则中间结果就已远远超出了计算机允许的整数取再取模，则中间结果就已远远超出了计算机允许的整数取值范围。值范围。l用模运算的性质：即用模运算的性质：即采用累次乘法，采用累次乘法，可减小中间结果可减小中间结果l(ab) mod n=(a mod n)(b mod n) mod n25快速指数算法快速指数算法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)2a126快速指数算法：快速指数算法：lc=0; d=1；lfor i=k downto 0 do l c=2c; /仅为验证以上过程，而在具体算法中可删去仅为验证以上过程，而在具体算法中可删去ld=(dd) mo
34、d n;/计算平方计算平方lif bi=1 then lc=c+1; /仅为验证以上过程，而在具体算法中可删去仅为验证以上过程，而在具体算法中可删去ld=(da) mod n / bi=1时与时与a相乘相乘lllreturn d.其中其中d是中间结果，是中间结果，d的终值即为所求结果。的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算对计算结果无任何贡献，算法中完全可将之去掉结果无任何贡献，算法中完全可将之去掉27计算复杂度计算复杂度:llW(m)次模乘（次模乘（m为模指数）为模指数）ll为指数的为指数的bit长，
35、长，W(m)为指数为指数m的重量的重量(二进制比特二进制比特1的个数的个数)例：例： 求求7560 mod 561。l将将560表示为表示为1000110000，算法的中间结果如表，算法的中间结果如表4-6所示所示l所以所以7560 mod 561=1l(5613x11x17, (561)=2x10x16=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 298 166 67 128一种改进的一种改进的RSA实现
36、方法实现方法 (即即4.3.3节）节） lRSA的加密很快，因为的加密很快，因为加密指数加密指数e一般选择得很小一般选择得很小l解密指数解密指数d很大很大，需要计算模，需要计算模 300digits (or 1024bits) 的乘法，计算机的乘法，计算机不能直接处理这么大的数，计算速度很慢，需要考虑其它技术，加速不能直接处理这么大的数，计算速度很慢，需要考虑其它技术，加速RSA的实现的实现l如果知道如果知道p和和q，可采用中国剩余定理，可采用中国剩余定理CRT：lCRT 对对RSA解密算法生成两个解密方程（利用解密算法生成两个解密方程（利用M=Cd mod N，N=pq）l即：即：M1 =
37、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倍多倍多292. RSA密钥的产生
38、密钥的产生l需考虑需考虑两个大素数两个大素数p、q的选取，以及的选取，以及e的选取和的选取和d的计算的计算ln(=pq) 是公开的，为了防止敌手通过穷搜索发现是公开的，为了防止敌手通过穷搜索发现p、q，这这两个素数应是在一个足够大的整数集合中选取的大数两个素数应是在一个足够大的整数集合中选取的大数l(1) 如何有效地寻找大素数是第一个需要解决的问题如何有效地寻找大素数是第一个需要解决的问题l寻找大素数时寻找大素数时一般是先随机选取一个大的奇数一般是先随机选取一个大的奇数（例如用伪随机数产（例如用伪随机数产生器），生器），l然后用素性检验算法检验这一奇数是否为素数然后用素性检验算法检验这一奇数是
39、否为素数，如果不是则选取另，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止一大奇数，重复这一过程，直到找到素数为止l素性检验算法通常都是概率性的，素性检验算法通常都是概率性的，常用常用Miller-Rabin概率检测算法概率检测算法实现实现l寻找大素数是一个比较繁琐的工作，然而在寻找大素数是一个比较繁琐的工作，然而在RSA体制中，只有在产体制中，只有在产生新密钥时才需执行这一工作生新密钥时才需执行这一工作30l(2) p和和q决定出后，决定出后，下一个需要解决的问题是下一个需要解决的问题是l如何选取满足如何选取满足1eq，由，由 (n)=(p-1)(q-1)，则有，则有l p+q=n
40、 (n)+1，以及，以及l p-q= l由此可见，由由此可见，由p、q确定确定 (n)和由和由 (n)确定确定p、q是等价的是等价的34为保证算法的安全性，对为保证算法的安全性，对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使得使得x2-n是某一整数（
41、记为是某一整数（记为y）的平方。）的平方。l 由由x2-n=y2，得，得n=(x+y)(x-y)。l(2) p-1和和q-1都应有大素因子都应有大素因子(强素数强素数)l这是因为这是因为RSA算法存在着可能的算法存在着可能的重复加密攻击重复加密攻击法。法。 35重复加密攻击法重复加密攻击法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能被容易地确定能被容易地确定364.3.5 对对RSA的攻
43、击的攻击RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的是由于参数选择不当造成的1. 共模攻击共模攻击l在实现在实现RSA时，为方便起见，可能给每一用户相同的模数时，为方便起见，可能给每一用户相同的模数n，虽然加解，虽然加解密密钥不同，然而这样做是不行的密密钥不同，然而这样做是不行的l设两个用户的公开钥分别为设两个用户的公开钥分别为e1和和e2，且，且e1和和e2互素（一般情况都成立），互素（一般情况都成立），明文消息是明文消息是m，密文分别是，密文分别是l c1me1(mod n)l c2me2(mod n)l敌手
44、截获敌手截获c1和和c2后，可如下恢复后，可如下恢复m。用推广的。用推广的Euclid算法求出满足算法求出满足 re1+se2=1的两个整数的两个整数r和和s，其中一个为负，设为，其中一个为负，设为r。再次用推广的。再次用推广的Euclid算法求出算法求出c1-1，由此得，由此得(c1-1)-rc2sm(mod n)。372. 低指数攻击低指数攻击l假定将假定将RSA算法同时用于多个用户（为讨论方便，以下算法同时用于多个用户（为讨论方便，以下假定假定3个），然而每个用户的加密指数（即公开钥）都个），然而每个用户的加密指数（即公开钥）都很小。很小。l设设3个用户的模数分别为个用户的模数分别为ni
45、(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 n1n2n3)。由于。由于m3n1n2n3，可直接由，可直接由m3开立方根得到开立方根得到m。l最初建议使用最初建议使用e=3，不安全，不安全，e是有下限的是有下限的明文消息空间太小时，消息需要填充明文消息空间太小时，消息需要填充384.4
46、 背包密码体制背包密码体制设设A=(a1,a2,an)是由是由n个不同的正整数构成的个不同的正整数构成的n元组，元组，s是是另一已知的正整数。另一已知的正整数。背包问题就是从背包问题就是从A中求出所有的中求出所有的ai，使，使其和等于其和等于s。其中。其中A称为背包向量称为背包向量，s是背包的容积是背包的容积。l例如例如,A=(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523)，s=3231。l由于由于 3231=129+473+903+561+1165l所以从所以从A中找出的满足要求的数有中找出的满足要求的数有129、473、903、561、
47、1165原则上讲，通过检查原则上讲，通过检查A的所有子集，总可找出问题的解（若的所有子集，总可找出问题的解（若有解的话）有解的话）l本例本例A的子集共有的子集共有210=1024个（包括空集）。然而如果个（包括空集）。然而如果A中元素个数中元素个数n很大，子集个数很大，子集个数2n将非常大。如将非常大。如A中有中有300个元素，个元素，A的子集有的子集有2300。寻找满足要求的寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题是的子集没有比穷搜索更好的算法，因此背包问题是NPC问题。问题。39由背包问题构造公钥密码体制同样是要构造一个单向函数由背包问题构造公钥密码体制同样是要构造一个单
48、向函数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使用向量乘使用向量乘(内积内积)，有，有f(x)=ABx，其中，其中Bx是是x二元表示的列向量。二元表示的列向量。l上例中上例中f(364) =f(0101101100)= 129+473+903+561
49、+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不能太小不能太小，比如说，至少为，比如说，至少为200。 40用用f对明文消息对明文消息m加密时，加密时，首先将首先将m写成二元表示写成二元表示，再将其分成长为，再将其分成长为n的的分组
50、（分组（最后一个分组不够长的话，可在后面填充一些最后一个分组不够长的话，可在后面填充一些0），然后求每一），然后求每一分组的函数值，以函数值作为密文分组。分组的函数值，以函数值作为密文分组。l例如，明文消息是英文文本，则可将每个字母用其在字母表中的序号表示，例如，明文消息是英文文本，则可将每个字母用其在字母表中的序号表示，再将该序号转换为二进制形式（再将该序号转换为二进制形式（5位即可），如表位即可），如表4.5所示，其中符号所示，其中符号 表示空格。表示空格。l表表47 英文字母表及字母的二进制表示英文字母表及字母的二进制表示字母字母序号序号二进制二进制字母字母序号序号二进制二进制字母字母序
51、号序号二进制二进制 000000I901001R1810010A100001J1001010S1910011B200010K1101011T2010100C300011L1201100U2110101D400100M1301101V2210110E500101N1401110W2310111F600110O1501111X2411000G700111P1610000Y2511001H801000Q1710001Z261101041背包向量仍取上例中的背包向量仍取上例中的A，设待加密的明文是，设待加密的明文是SAUNA AND HEALTH。l因为因为A长为长为10，所以应将明文分成长为，所以应
52、将明文分成长为10比特（即两个明比特（即两个明文字母）的分组文字母）的分组SA，UN，A ，AN，D ，HE，AL，TH相应的二元序列为相应的二元序列为l1001100001，1010101110，0000100000，0000101110，0010000000，0100000101，0000101100，1010001000。l分别对以上二元序列作用于函数分别对以上二元序列作用于函数f，得密文为，得密文为l（2942，3584，903，3326，215，2817，2629，819）。）。l为使接收方能够解密，就需找出单向函数为使接收方能够解密，就需找出单向函数f(x)的陷门。为的陷门。为此需
53、引入一种特殊类型的背包向量。此需引入一种特殊类型的背包向量。42定义背包向量定义背包向量A=(a1,a2,an)称为称为超递增的超递增的，如，如果果 ，j1,2,n超递增背包向量对应的背包问题很容易通过以下超递增背包向量对应的背包问题很容易通过以下算法求解。算法求解。l已知已知s为背包容积，对为背包容积，对A从右向左检查每一元素，以确定从右向左检查每一元素，以确定是否在解中。是否在解中。l若若san，则，则an在解中，令在解中，令xn=1；若；若san，则，则an不在解中，不在解中，令令xn=0。下面令。下面令ls l对对an-1重复上述过程，一直下去，直到检查出重复上述过程，一直下去，直到检
54、查出a1是否在是否在解中。检查结束后得解中。检查结束后得 x=(x1x2xn)，Bx=(x1x2xn)T43l敌手如果也知道超递增背包向量，同样也很容易解密敌手如果也知道超递增背包向量，同样也很容易解密l为此可用模乘对为此可用模乘对A进行伪装进行伪装，模乘的模数，模乘的模数k和乘数和乘数t皆取为常量，满足皆取为常量，满足 ，gcd(t,k)=1，即，即t在模在模k下有乘法逆元。设下有乘法逆元。设 bitai mod k, i=1,2,nl得一新的背包向量得一新的背包向量B=(b1,b2,bn)，记为，记为BtA mod k，用户以，用户以B作为自作为自己的公开钥，己的公开钥，A,t,k为私钥为
55、私钥【例4-10】lA=(1, 3, 5, 11, 21, 44, 87, 175, 349, 701)是一超递增背包向量，取是一超递增背包向量，取k=1590，t=43， gcd(43, 1590)=1，得，得B=(43,129,215,473,903,302,561,1165,697, 1523)。l得到得到B后，对明文分组后，对明文分组x=(x1x2xn)的加密运算为的加密运算为c=f(x)=BBxtABx mod kl对单向函数对单向函数f(x)，t、t-1和和k可作为其秘密的陷门信息，即解密密钥。可作为其秘密的陷门信息，即解密密钥。44l解密时首先由解密时首先由st-1c mod k
56、，求出，求出s作为超递增背包向量作为超递增背包向量A的的容积，再解背包问题即得容积，再解背包问题即得x=(x1x2xn)。这是因为。这是因为t-1c mod kt-1tABx mod kABx mod k，而由，而由 ，知，知ABx701，得，得x10=1；令；令s=734-701=33，由，由33349，得，得x9=0；重；重复该过程得第一个明文分组是复该过程得第一个明文分组是1001100001，它对应的英文文本是，它对应的英文文本是SA；类似地；类似地得其他明文分组，解密结果为得其他明文分组，解密结果为SAUNA AND HEALTH。45背包密码体制是背包密码体制是Diffie和和He
57、llman 1976年提出公年提出公钥密码体制的设想后的第一个公钥密码体制，由钥密码体制的设想后的第一个公钥密码体制，由Merkle和和Hellman 1978年提出。年提出。它表示了如何将它表示了如何将NP完全问题用于公开密钥算法。完全问题用于公开密钥算法。然而又过了两年该体制即被破译然而又过了两年该体制即被破译l破译的基本思想是不必找出正确的模数破译的基本思想是不必找出正确的模数k和乘数和乘数t（即陷（即陷门信息），只须找出任意模数门信息），只须找出任意模数k和乘数和乘数t，使得用，使得用k和和t去乘公开的背包向量去乘公开的背包向量B时，能够产生超递增的背包向量时，能够产生超递增的背包向量
58、即可。即可。464.5 Rabin密码体制密码体制对对RSA密码体制，密码体制，n被分解成功，该体制便被破译，即破被分解成功，该体制便被破译，即破译译RSA的难度不超过大整数的分解。的难度不超过大整数的分解。l但还不能证明破译但还不能证明破译RSA和分解大整数是等价的，虽然这一结论已和分解大整数是等价的，虽然这一结论已得到普遍共识得到普遍共识lRabin密码体制已被证明对该体制的破译与分解大整数一样困难密码体制已被证明对该体制的破译与分解大整数一样困难Rabin密码体制是对密码体制是对RSA的一种修正，它有以下两个特点：的一种修正，它有以下两个特点： l它不是以一一对应的单向陷门函数为基础，对
59、同一密文，可能有它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文两个以上对应的明文;l破译该体制等价于对大整数的分解。破译该体制等价于对大整数的分解。lRSA中选取的公开钥中选取的公开钥e满足满足1ep2.密钥的产生密钥的产生l密钥的产生由接收方完成：随即选取两个多项式密钥的产生由接收方完成：随即选取两个多项式f, g Lg，其中多，其中多项式项式f在模在模q和模和模p下均可逆，其逆元分别表示为下均可逆，其逆元分别表示为Fq和和Fp，即：，即：Fq*f=1 mod q 和和 Fp*f=1 mod p。计算。计算hFq*g mod q，以，以h为公钥，为公钥，f作为秘密
60、钥，接收方同时还需保存作为秘密钥，接收方同时还需保存Fp 3.加密加密l设发送方欲将消息设发送方欲将消息m Lm发送给接收方，可对发送给接收方，可对m作如下加密：随机作如下加密：随机选取多项式选取多项式 L ，用公钥，用公钥h对消息进行加密对消息进行加密lep *h+m (mod q)l将将e发送给接收方。发送给接收方。524.解密l接收方收到接收方收到e后，使用秘密钥后，使用秘密钥f对其作如下解密。对其作如下解密。l首先计算首先计算a=f*e(mod q), a的系数选在的系数选在-q/2到到q/2之间之间.l将将a作为一个整系数多项式，计算作为一个整系数多项式，计算Fp*a(mod p)即
61、可恢复明文即可恢复明文ml解密原理：解密原理：la=f*ef*p *h+f*m (mod q)l f*p *Fq*g +f*m (mod q)l p *g +f*m (mod q)l p *g +f*m l最后一步是由于若选择的参数合适，可保证多项式最后一步是由于若选择的参数合适，可保证多项式p *g +f*m的系的系数在数在-q/2到到q/2之间，所以对之间，所以对p *g +f*m模模q运算后结果不变运算后结果不变l而而Fp*aFp*p *g +Fp*f*m (mod p)m (mod p)534.7 椭圆曲线密码体制椭圆曲线密码体制l为保证为保证RSA算法的安全性，它的密钥长度需一算法的
62、安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。再增大，使得它的运算负担越来越大。l相比之下，椭圆曲线密码体制相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景同样的安全性，因此具有广泛的应用前景ECC已被IEEE公钥密码标准P1363采用544.7.1 椭圆曲线椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：l y2+axy+by=x3+cx2+dx+e (4-1)l其中其中a
63、，b，c，d，e是满足某些简单条件的实数。是满足某些简单条件的实数。定义中包括一个定义中包括一个称为无穷点的元素，记为称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。下图是椭圆曲线的两个例子。l从图可见，椭圆曲线关于从图可见，椭圆曲线关于x轴对称。轴对称。 55椭圆曲线上的加法运算定义如下： l如果其上的如果其上的3个点位于同一直线上，那么它们的和为个点位于同一直线上，那么它们的和为O。进。进一步可如下定义椭圆曲线上的加法律（加法法则）：一步可如下定义椭圆曲线上的加法律（加法法则）： l O为加法单位元为加法单位元，即对椭圆曲线上任一点，即对椭圆曲线上任一点P，有，有 P+O=Pl 设设P
64、1=(x,y)是椭圆曲线上的一点（如图所示），它的是椭圆曲线上的一点（如图所示），它的加加法逆元法逆元定义为定义为P2=P1=(x, -y)l这是因为这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的，即椭圆曲线上的3点点P1、P2，O共线，所以共线，所以P1+P2+O=O，P1+P2=O，即，即P2=-P1。l由由O+O=O，还可得，还可得O= -O56l 设设Q和和R是椭圆曲线上是椭圆曲线上x坐标不同的两点，坐标不同的两点，Q+R的定义的定义如下：如下： 画一条通过画一条通过Q、R的直线与椭圆曲线交于的直线与椭圆曲线
65、交于P1l这一交点是惟一的，除非所做的直线是这一交点是惟一的，除非所做的直线是Q点或点或R点的切线，此时点的切线，此时分别取分别取P1=Q或或P1=R 由由Q+R+P1=O 得得 Q+R=-P1l 点点Q的倍数定义的倍数定义如下：如下： 在在Q点做椭圆曲线的一条切线，点做椭圆曲线的一条切线，设切线与椭圆曲线交于点设切线与椭圆曲线交于点S，定义，定义2Q=Q+Q=-S。类似地。类似地可定义可定义3Q=Q+Q+Q+，l以上定义的加法具有加法运算的一般性质，如以上定义的加法具有加法运算的一般性质，如交换律、交换律、结合律结合律等。等。574.7.2 有限域上的椭圆曲线有限域上的椭圆曲线密码中普遍采用
66、的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式(4-1)中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）l其中最为常用的是由方程其中最为常用的是由方程(4-2)定义的曲线定义的曲线 ly2x3+ax+b(mod p) (4-2)l (a,b GF(p),4a3+27b2(mod p)0)58l因为因为 (a/3)3+(b/2)2=(4a3+27b2)/108是方程是方程x3+ax+b0的判别式，的判别式，当当4a3+27b2 0时方程有时方程有重根，设为重根，设为x0，则点，则点Q0(x0,0)是方程是方程(4-2)的重的重根根l即即x3+ax+b(x-x0)3或
67、者或者(x-x0)2(x-x1)，重根重根将使得一阶导数将使得一阶导数3x2a在该在该Q0点为点为0l令令F(x,y)=y2x3axb，则，则 F/ x|Q0= F/ y|Q0=0l所以所以dy/dx= F/ x/ F/ y(3x2a)/2y在在Q0点无点无定义，即曲线定义，即曲线y2x3+ax+b在在Q0点的切线无定义，点的切线无定义，因此因此点点Q0的倍点运算无定义的倍点运算无定义59例： p=23，a=b=1，4a3+27b2(mod 23)80，方程为y2x3+x+1(mod 23)，感兴趣的是曲线在GF(23)中的整数点l设设Ep(a,b)表示表示方程方程(4-2)所定义的所定义的椭
68、圆曲线上的点集椭圆曲线上的点集(x,y)|0 xp,0 yp，且，且x,y均为整数均为整数并上无穷远点并上无穷远点Ol本例中本例中E23(1,1)由表由表4-8给出，表中未给出给出，表中未给出Ol表表46 椭圆曲线上的点集椭圆曲线上的点集E23(1,1)(0，1)(0，22)(1，7)(1，16)(3，10)(3，13)(4，0)(5，4)(5，19)(6，4)(6，19)(7，11)(7，12)(9，7)(9，16)(11，3)(11，20)(12，4)(12，19)(13，7)(13，16)(17，3)(17，20)(18，3)(18，20)(19，5)(19，18)60一般来说，Ep(a
69、,b)由以下方式产生： l 对每一对每一x(0 xp且且x为整数），计算为整数），计算x3+ax+b(mod p)。 l 决定决定中求得的值在模中求得的值在模p下是否有平方根，如果没有，则曲线下是否有平方根，如果没有，则曲线上没有与这一上没有与这一x相对应的点；如果有，则求出两个平方根相对应的点；如果有，则求出两个平方根 (y=0 时时只有一个平方根只有一个平方根)。即判断是否是模。即判断是否是模p的平方剩余的平方剩余Ep(a,b)上的加法定义如下： l设设P，Q Ep(a,b)，则，则l P+O=Pl 如果如果P=(x,y)，那么，那么(x, y)+(x, -y)=O，即，即 (x, -y)
70、是是P的加法逆元，的加法逆元，表示为表示为-P。l由由Ep(a,b)的产生方式知，的产生方式知，-P也是也是Ep(a,b)中的点，如上例，中的点，如上例，P=(13,7) E23(1,1)，-P=(13, -7)，而，而-7 mod 2316，所以，所以-P=(13, 16)，也在，也在E23(1,1)中。中。61l 设设P=(x1,y1)，Q=(x2,y2)，P-Q，则，则P+Q=(x3,y3)由以下规则确定：由以下规则确定：l x32x1x2(mod p)l y3(x1x3)y1(mod p)l其中其中 l 切线切线【例429】仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，
71、则l(7-10)/(9-3)=-1/2=12111 mod 23lx31123910917 mod 23ly311(317)1016420 mod 23l所以所以P+Q=（17,20），），仍为仍为E23(1,1)中的点中的点。l若求若求2P则则 (3321)/(210)=5/20=14112206 mod 23l x36233307 mod 23l y36(37)103412 mod 23l 所以所以2P=(7,12)62公式推导示例公式推导示例63倍点运算仍定义为重复加法，如4P=P+P+P+P快速倍点运算 kPl可采用类似于快速指数运算的相同算法可采用类似于快速指数运算的相同算法l即令即
72、令k=bt2t+bt-12t-1+b12+b0，则可写出，则可写出2倍点和加法运倍点和加法运算的迭代形式算的迭代形式Ep(a,b)是一个Abel群l对一般的对一般的Ep(a,b)，可证其上的，可证其上的加法运算是封闭的加法运算是封闭的、满足、满足交换律交换律，同样还能证明其上的加法，同样还能证明其上的加法逆元逆元运算也是封闭的，运算也是封闭的，有单位元有单位元O，所以，所以Ep(a,b)是一个是一个Abel群群644.7.3 椭圆曲线上的点数椭圆曲线上的点数一条椭圆曲线Ep(a,b)（含无穷远点O)的总点数关系到运算群的规模，即建立的密码系统的安全性，有以下定理：定理4-13 GF(p)上的椭
73、圆曲线y2x3+ax+b(a,bGF(p), 4a3+27b2(mod p)0)在第一象限中的整数点加无穷远点O共有l1+p+ = 1+p+ 个，其中个，其中 是是Legendre符号符号l定理中的定理中的 由以下定理给出由以下定理给出定理4-14(Hasse定理) l| |654.7.4 明文消息到椭圆曲线上的嵌入明文消息到椭圆曲线上的嵌入使用椭圆曲线构造密码体制前，需要将明文消息镶嵌到椭圆曲线上去，作为椭圆曲线上的点。l设明文消息是设明文消息是m(0 m M)，k是一个足够大的整数，使得将明文消是一个足够大的整数，使得将明文消息镶嵌到椭圆曲线上时，错误的概率是息镶嵌到椭圆曲线上时，错误的概
74、率是2-kl实际情况中，实际情况中，k可在可在30 50之间取值。不妨设之间取值。不妨设k30，对明文消息，对明文消息m，如下计算一系列，如下计算一系列x：lxmk+j,j=0,1,2,=30m,30m+1,30m+2,直到直到x3+ax+b(mod p)是平方剩余，即得到椭圆曲线上的点是平方剩余，即得到椭圆曲线上的点l(x, )。因为在。因为在0到到p的整数中，有一半是模的整数中，有一半是模p的平方剩的平方剩余，一半是模余，一半是模p的非平方剩余。所以的非平方剩余。所以k次找到次找到x，使得，使得x3+ax+b(mod p)是平方根的概率不小于是平方根的概率不小于12-k。l反之，为从椭圆曲
75、线上的点反之，为从椭圆曲线上的点(x,y)得到明文消息得到明文消息m，只须求，只须求m x/30 664.7.5 椭圆曲线上的密码椭圆曲线上的密码为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题l在椭圆曲线构成的在椭圆曲线构成的Abel群群Ep(a,b)上考虑方程上考虑方程Q=kP，其，其中中P，Q Ep(a,b)，kp，则，则由由k和和P易求易求Q，但，但由由P、Q求求k则是困难则是困难的，这就是的，这就是椭圆曲线上的离散对数问题椭圆曲线上的离散对数问题，可应用于公钥密码体制。可应用于公钥密码体制。lDiffie-Hellman密钥交换密钥交换和和ElGamal密码体制密码体制是
76、基于有是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制。曲线来实现这两种密码体制。671. Diffie-Hellman密钥交换l首先取一素数首先取一素数p2180和两个参数和两个参数a、b，则得椭圆曲线上，则得椭圆曲线上面的点及无穷远点构成面的点及无穷远点构成Abel群群Ep(a,b)l第第2步，取步，取Ep(a,b)的一个生成元的一个生成元G(x1,y1)，要求，要求G的的阶是一个非常大的素数，阶是一个非常大的素数，G的阶是满足的阶是满足nG=O的最小正整的最小正整数数n。Ep(a,b)和和G作为公开参数作为公
77、开参数l两用户两用户A和和B之间的密钥交换如下进行：之间的密钥交换如下进行： l A选一小于选一小于n的整数的整数nA，作为秘密钥，并由，作为秘密钥，并由PA=nAG产生产生Ep(a,b)上的一点作为公开钥上的一点作为公开钥l B类似地选取自己的秘密钥类似地选取自己的秘密钥nB和公开钥和公开钥PBl A、B分别由分别由K=nAPB和和K=nBPA产生出双方共享的秘密钥产生出双方共享的秘密钥 这是因为这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPAl攻击者若想获取攻击者若想获取K，则必须由，则必须由PA和和G求出求出nA，或由，或由PB和和G求出求出nB，即需要求椭圆曲线上的离散对
78、数，因此是不可行的，即需要求椭圆曲线上的离散对数，因此是不可行的68【例414】: p=211，Ep(0,4)，即椭圆曲线为y2x34lG=(2,2)是是E211(0,-4)的阶为的阶为241的一个生成元，即的一个生成元，即241G=O。A的秘密钥的秘密钥为为nA=121，公开钥为，公开钥为PA=121(2,2)=(115,48)。B的秘密钥取为的秘密钥取为nB=203，公，公开钥为开钥为PB=203(2,2)=(130,203)。由此得共享密钥为。由此得共享密钥为121(130,203) =203(115,48)=(161,169)，即共享密钥是一对数。，即共享密钥是一对数。l如果将这一密钥
79、用作单钥加密的会话密钥，则可简单地取其中的一个，如果将这一密钥用作单钥加密的会话密钥，则可简单地取其中的一个，如取如取x坐标，或取坐标，或取x坐标的某一简单函数。或计算坐标的某一简单函数。或计算hash值值2. ElGamal密码体制l原理：原理：密钥产生过程密钥产生过程： 首先选择一素数首先选择一素数p以及两个小于以及两个小于p的随机数的随机数g和和x，计算，计算ygx mod p。以。以(y, g, p)作为公开密钥，作为公开密钥，x作为秘密密钥。作为秘密密钥。l加密过程：加密过程： 设欲加密明文消息设欲加密明文消息M，随机选一与，随机选一与p-1互素的整数互素的整数k l计算对计算对C1
80、gk mod p,C2ykM mod p，密文为，密文为C = C1,C2 l解密过程：解密过程：M=C2/C1x mod p l这是因为这是因为C2/C1x mod pykM/gkx mod pykM/yk mod pM mod p 69(2) 利用椭圆曲线实现ElGamal密码体制l首先首先选取一条椭圆曲线，并得选取一条椭圆曲线，并得Ep(a,b)，将，将明文消息明文消息m通过编码嵌入通过编码嵌入到曲线上得点到曲线上得点Pm，再对点，再对点Pm做加密变换。如做加密变换。如4.7.4l取取Ep(a,b)的一个的一个生成元生成元G，Ep(a,b)和和G作为公开参数。作为公开参数。l用户用户A选
81、选nA作为秘密钥作为秘密钥，并以，并以PA=nAG作为公开钥作为公开钥l任一用户任一用户B若想向若想向A发送消息发送消息Pm，可选取一随机正整数，可选取一随机正整数k，产生以下，产生以下点对作为密文：点对作为密文： Cm=kG，Pm+kPA存在密文扩展问题存在密文扩展问题lA解密解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点时，以密文点对中的第二个点减去用自己的秘密钥与第一个点倍乘，即倍乘，即l Pm+kPAnAkG=Pm+k(nAG)nAkG =Pml攻击者若想由攻击者若想由Cm得到得到Pm，就必须知道，就必须知道k。而要得到。而要得到k，只有通过椭圆，只有通过椭圆曲线上的两个已
82、知点曲线上的两个已知点G和和kG，这意味着必须求椭圆曲线上的离散对，这意味着必须求椭圆曲线上的离散对数，因此不可行。数，因此不可行。 70【例415】：l取取p=751，Ep(-1,188)，即椭圆曲线为，即椭圆曲线为y2x3-x+188lEp(-1,188)的一个生成元是的一个生成元是G=(0,376)，A的公开钥为的公开钥为PA=(201,5)。l假定假定B已将欲发往已将欲发往A的消息嵌入到椭圆曲线上的点的消息嵌入到椭圆曲线上的点Pm=(562,201)，lB选取随机数选取随机数k=386，由，由kG=386(0,376)=(676,558)，Pm+kPA=(562，201)+386(20
83、1,5)=(385,328)，得密文为，得密文为(676,558),(385,328)。3. 椭圆曲线密码体制的优点l与基于有限域上离散对数问题的公钥体制（如与基于有限域上离散对数问题的公钥体制（如Diffie-Hellman密钥交换密钥交换和和ElGamal密码体制）相比，椭圆曲线密码体制有如下优点密码体制）相比，椭圆曲线密码体制有如下优点:(1) 安全性高l攻击有限域上的离散对数问题可以用攻击有限域上的离散对数问题可以用指数积分法指数积分法，其运算复杂度为，其运算复杂度为lO(exp )，其中，其中p是模数（为素数）。而是模数（为素数）。而它对椭圆曲线上它对椭圆曲线上的离散对数问题并不有效
84、的离散对数问题并不有效。71l目前攻击椭圆曲线上的离散对数问题的方法只有适合攻目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群上离散对数问题的击任何循环群上离散对数问题的大步小步法大步小步法，其运算复，其运算复杂度为杂度为O(exp )l其中其中pmax是椭圆曲线所形成的是椭圆曲线所形成的Abel群的阶的最大素因子。群的阶的最大素因子。l如果如果p有大素因子有大素因子q，且，且p2q1，则非常安全，则非常安全l因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全。钥体制更安全。(2) 密钥量小l由攻击两者的算法复杂
85、度可知，在实现相同的由攻击两者的算法复杂度可知，在实现相同的安全性能条件下，椭圆曲线密码体制所需的密安全性能条件下，椭圆曲线密码体制所需的密钥量远比基于有限域上的离散对数问题的公钥钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小。体制的密钥量小。72(3) 灵活性好l有限域有限域GF(q)一定的情况下，其上的一定的情况下，其上的循环群循环群（即（即GF(q)-0）就定了就定了lGF(q)上的椭圆曲线上的椭圆曲线可以通过改变曲线参数，得到不同可以通过改变曲线参数，得到不同的曲线，形成不同的循环群。因此，椭圆曲线具有丰富的曲线，形成不同的循环群。因此，椭圆曲线具有丰富的群结构和多选择性的群结
86、构和多选择性l因此可在保持因此可在保持和和RSA/DSA体制同样安全性能的前提下大体制同样安全性能的前提下大大缩短密钥长度大缩短密钥长度（目前（目前160比特足以保证安全性），因比特足以保证安全性），因而在密码领域有着广阔的应用前景而在密码领域有着广阔的应用前景l表表4-7给出了椭圆曲线密码体制和给出了椭圆曲线密码体制和RSA/DSA体制在保持体制在保持同等安全的条件下各自所需的密钥的长度同等安全的条件下各自所需的密钥的长度RSA/DSA5127681024204821000ECC106132160211600734.8 基于身份的密码基于身份的密码4.8.1引言l1984年年Shamir提出
87、了一种基于身份的加密方案提出了一种基于身份的加密方案(简称简称IBE(identity-based encryption)的思想，并征询具体的思想，并征询具体实现方案，方案中不使用任何证书，直接将用户的身份实现方案，方案中不使用任何证书，直接将用户的身份作为公钥，以此来简化公钥基础设施作为公钥，以此来简化公钥基础设施PKI(Public key infrastructure)中基于证书的密钥管理过程。中基于证书的密钥管理过程。l例如：用户例如：用户A给用户给用户B发加密的电子邮件，发加密的电子邮件，B的邮件地址是的邮件地址是, A只要将只要将“” 作为作为B的公钥来加密邮件即可。当的公钥来加密
88、邮件即可。当bob收到加密的邮件后，他与收到加密的邮件后，他与一个第三方密钥服务器联系，和向一个第三方密钥服务器联系，和向CA证明自己身份一样，证明自己身份一样，B向服务器证明自己，并从服务器获得解密用的秘密密钥，向服务器证明自己，并从服务器获得解密用的秘密密钥，再解密就可以阅读邮件。再解密就可以阅读邮件。74l与现有的安全电子邮件相比，即使与现有的安全电子邮件相比，即使B还未建立他的公钥证书，还未建立他的公钥证书，A也可以也可以向他发送加密的邮件。因此这种方法避免了公钥密码体制中公钥证书向他发送加密的邮件。因此这种方法避免了公钥密码体制中公钥证书从生成、签发、存储、维护、更新、撤销这一复杂的
89、生命周期过程从生成、签发、存储、维护、更新、撤销这一复杂的生命周期过程自Shamir提出这种新思想后，由于没有找到有效的实现工具，其实现一直是一公开问题。直到2001年，Dan Boneh和Matt Franklin获得了数学上的突破，提出了第一个实用的基于身份的公钥加密方案。l他们的方案使用椭圆曲线上的双线性映射他们的方案使用椭圆曲线上的双线性映射(称为称为Weil配对和配对和Tate配对配对)，将用户的身份映射为一对公开钥，将用户的身份映射为一对公开钥/秘密钥对秘密钥对l双线性映射是满足双线性映射是满足Pair(aX,bY)Pair(bX,aY)的映射的映射Pair，其中，其中a和和b是是
90、整数，整数，X和和Y是椭圆曲线上的点。是椭圆曲线上的点。方案由四步组成，简单描述如下：(1)初始化l密钥服务器选取一条椭圆曲线、秘密整数密钥服务器选取一条椭圆曲线、秘密整数s、椭圆曲线上的一点、椭圆曲线上的一点P，公，公开开P和和sP75(2) 加密l发送方发送方A想向接收方想向接收方B发送消息发送消息Ml首先将首先将B的身份的身份(如如)经杂凑函数映射到椭圆曲线上经杂凑函数映射到椭圆曲线上的一个点，记为的一个点，记为QID，l然后取一秘密的随机数然后取一秘密的随机数r，计算，计算kPair(rQID,sP)作为加密密钥。作为加密密钥。l最后将加密结果最后将加密结果Ek(M)和和rP发送给接收
91、方发送给接收方B。其中。其中E是一单钥加密算法是一单钥加密算法(3)密钥产生l接收方接收方B收到收到Ek(M)和和rP后，向密钥服务器提出申请，服务器在对后，向密钥服务器提出申请，服务器在对B认认证后，计算证后，计算sQID并发送给并发送给B，B以以sQID作为秘密钥作为秘密钥(4)解密lB收到秘密钥后，计算收到秘密钥后，计算kPair(sQID,rP)，使用，使用k及及E对密文解密。对密文解密。l由于映射由于映射Pair的性质，的性质，B计算的计算的k与与A使用的使用的k相等，其他人不知道秘密相等，其他人不知道秘密钥钥sQID ，所以无法得到，所以无法得到k。764.8.2 双线性映射和双线
92、性双线性映射和双线性D-H假设假设l以以Zq表示表示mod q加法下的群加法下的群0,1,q-1l对于阶为素数的群对于阶为素数的群G，用，用G*代表集合代表集合GO，O为为G中的单位元中的单位元l用用Z+代表正整数集代表正整数集1.双线性映射l设设q是一大素数，是一大素数，G1和和G2是两个阶为是两个阶为q的群，其上的运算分别称为加法的群，其上的运算分别称为加法和乘法。和乘法。G1到到G2的双线性映射的双线性映射e:G1G1G2，满足下面的性足下面的性质：l双双线性：如果性：如果对任意任意P,Q,R G1和和a,b Z，有，有e(aP,bQ)=e(P,Q)ab，或，或e(P+Q,R)=e(P,
93、R)e(Q,R) 和和e(P,Q+R)=e(P,Q)e(P,R)，那么就称该映射为，那么就称该映射为双线性映射双线性映射 l非非退化性：映射不把退化性：映射不把G1G1中的所有元素中的所有元素对(即序偶即序偶)映射到映射到G2中的中的单位元。由于位元。由于G1，G2都是都是阶为素数的群，素数的群，这意味着，如果意味着，如果P是是G1的生成的生成元，那么元，那么e(P,P) 就是就是G2中的生成元中的生成元l可可计算性：对任意的计算性：对任意的P,Q G1，存在一个有效算法计算，存在一个有效算法计算e(P,Q)。lWeil配对和配对和Tate配对是满足上述配对是满足上述3条性质的双线性映射。条性
94、质的双线性映射。772. MOV 规约lG1中的离散对数问题是指已知中的离散对数问题是指已知P,Q G1 ，求，求 Zq，使，使得得Q=P。已知这是一个困难问题。已知这是一个困难问题l然而如果记然而如果记ge(P,P)，he(Q,P)，则由，则由e的双线性可知的双线性可知hg，因此可以将，因此可以将G1中的离散对数问题归结为中的离散对数问题归结为G2中的中的离散对数问题，若离散对数问题，若G2中的离散对数问题可解，则中的离散对数问题可解，则G1中的中的离散对数问题可解。离散对数问题可解。lMOV规约规约(也称也称MOV攻击攻击)是指将攻击是指将攻击G1中的离散对数中的离散对数问题转变为攻击问题
95、转变为攻击G2中的离散对数问题。所以要使中的离散对数问题。所以要使G1中的中的离散对数问题为困难问题，那么必须选择适当参数使离散对数问题为困难问题，那么必须选择适当参数使G2中的离散对数问题为困难问题。中的离散对数问题为困难问题。783. DDH问题lG1中的判定性中的判定性DiffieHellman问题简称问题简称DDH(decision DiffieHellman)问题，是指已知问题，是指已知P,aP,bP,cP，判定，判定cab mod q是否成立，是否成立，其中其中P是是G1*中的随机元素，中的随机元素，a,b,c是是Zq*中的随机数。中的随机数。由双线性映射的性质可知：lcab mo
96、d qe(P,cP)e(aP,bP)l因此可将判定因此可将判定cab mod q是否成立转变为判定是否成立转变为判定e(P,cP)e(aP,bP)是是否成立，所以否成立，所以G1中的中的DDH问题是简单的。问题是简单的。4.CDH问题lG1中的计算性中的计算性DiffieHellman问题简称问题简称CDH(computational DiffieHellman)问题，是指已知问题，是指已知P,aP,bP，求，求abP，其中，其中P是是G1*中的随机中的随机元素，元素，a,b是是Zq*中的随机数。中的随机数。l与与G1中的中的DDH问题不同，问题不同， G1中的中的CDH问题不因引入双线性映射
97、而问题不因引入双线性映射而解决，因此它仍是困难问题。解决，因此它仍是困难问题。795. BDH问题和BDH假设l由于由于G1中的中的DDH问题简单，那么就不能用它来构造问题简单，那么就不能用它来构造G1中的密码体制。中的密码体制。IBE体制的安全性是基于体制的安全性是基于CDH问题的一问题的一种变形，称为双线性种变形，称为双线性DH假设假设。l双线性双线性DH问题简称为问题简称为BDH(bilinear DiffieHellman)问问题，是指给定题，是指给定(P,aP,bP,cP)(a,b,c Zq*)中，计算中，计算we(P,P)abc G2，其中，其中e是一个双线性映射，是一个双线性映射
98、，P是是G1的生成的生成元，元，G1,G2是阶为是阶为q的两个群，设算法的两个群，设算法A用来解决用来解决BDH问问题，其优势定义为题，其优势定义为，如果，如果lPr|A(P,aP,bP,cP)=e(P,P)abc |l目前还没有有效的算法解决目前还没有有效的算法解决BDH问题，因此可假设问题，因此可假设BDH问题是一困难问题，这就是问题是一困难问题，这就是BDH假设。假设。804.8.3 IBE方案描述方案描述令k是安全参数，g是BDH参数生成算法，其输出包括素数q，两个阶为q的群G1,G2，一个双线性映射e:G1G1G2的描述。k用来确定q的大小，例如可以取q为k比特长。(1)初始化l给定
99、安全参数定安全参数k Z+，算法运行如下：，算法运行如下：l输入输入k后运行后运行g，产生素数，产生素数q，两个阶为，两个阶为q的群的群G1,G2，一个双线性，一个双线性映射映射e:G1G1G2，选择一个随机生成元一个随机生成元P G1l随机选取一个随机选取一个s Zq*，PpubsPl选取一杂凑函数选取一杂凑函数H1:0,1*G1*，对某个某个n，再，再选一个一个杂凑函数凑函数H2 :G20,1n，安全分析，安全分析时则把把H1,H2视为随机随机预言机言机l消息空消息空间为M0,1n，密文空，密文空间为C=G1*0,1n 。系。系统参数参数为params，是公开的。，是公开的。s为主密主密钥
100、，是，是保密的。保密的。81(2)加密l用接收方的身份用接收方的身份ID作为公钥作为公钥,加密消息加密消息M M，有三步，有三步:l计算计算QID=H1(ID) G1*l选择一个随机数选择一个随机数r Zq*l确定密文确定密文C，这里，这里gIDe(QID,Ppub) G2*,(3) 密钥产生l对于一个给定的比特串对于一个给定的比特串ID 0,1*,首先计算首先计算QID=H1(ID) G1*，然后确定，然后确定秘密密钥秘密密钥dID= sQID,其中其中s为主密钥。为主密钥。(4)解密l设密文为设密文为C= C，用秘密，用秘密钥dID计算算V H2(e(dID,U)Ml这是因为这是因为e(d
101、ID,U)e(sQID,rP)e(QID,P)sre(QID,Ppub)rgrID*随机预言l杂凑函数有一个性质杂凑函数有一个性质”对任一输入，其输出对概率分布与均匀分布在计算对任一输入，其输出对概率分布与均匀分布在计算上是不可区分的上是不可区分的”。若这一性质改为。若这一性质改为”对任一输入，其输出是均匀分布的对任一输入，其输出是均匀分布的”，这样的杂凑函数是理想的。若把杂凑函数看作这样一个假想的理想函，这样的杂凑函数是理想的。若把杂凑函数看作这样一个假想的理想函数，就称为随机预言数，就称为随机预言(Random oracle).824.8.4 IBE方案的安全性方案的安全性1.语义安全的基
102、于身份的加密l公钥密码体制的语义安全的标准定义如下公钥密码体制的语义安全的标准定义如下l(1)攻击算法已知一个由系统产生的随机公钥攻击算法已知一个由系统产生的随机公钥l(2)攻击算法输出两个长度相同的消息攻击算法输出两个长度相同的消息M0，M1，再从系统接收，再从系统接收Mb的的密文，其中随机值密文，其中随机值b 0,1l(3)攻攻击算法算法输出出b ，如果，如果bb 则成功。如果没有多成功。如果没有多项式式时间的攻的攻击算法能以不可忽略的算法能以不可忽略的优势成功，那么成功，那么该密密码体制就是体制就是语义安全的。安全的。要定义基于身份的密码体制的语义安全，应允许攻击算法根据自己的选择进行秘
103、密钥询问，即攻击算法可根据自己的选择询问公钥ID对应的秘密钥，一次来加强标准定义。l如果不存在多如果不存在多项式式时间的攻的攻击算法算法A，以不可忽略的以不可忽略的优势在下面的攻在下面的攻击中中获得成功得成功，那么就称此方案是，那么就称此方案是语义安全的。安全的。83Gamel(1)初始化：系统输入安全参数初始化：系统输入安全参数k，产生公开的系统参数，产生公开的系统参数params和保密和保密的主密钥。的主密钥。l(2)阶段阶段1:攻击算法发出对攻击算法发出对ID1,ID2,IDm的秘密钥产生询问。系统运的秘密钥产生询问。系统运行秘密钥产生算法，产生与公钥行秘密钥产生算法，产生与公钥IDi对
104、应的秘密钥对应的秘密钥di(i=1,m)，并把，并把它发送给攻击算法。它发送给攻击算法。l询问：攻击算法输出两个长度相等的明文询问：攻击算法输出两个长度相等的明文M0，M1，和一个意欲询问的，和一个意欲询问的公开钥公开钥ID。唯一的限制是。唯一的限制是ID不在阶段不在阶段1中的任何秘密钥询问中出现。中的任何秘密钥询问中出现。系统随机选取一个比特值系统随机选取一个比特值b 0,1，计算算CEncrypt(params,ID,Mb),并将并将C发送送给攻攻击算法。算法。l(3)阶段阶段2：攻击算法发出对：攻击算法发出对IDm+1,IDn的秘密钥产生询问，唯一的限的秘密钥产生询问，唯一的限制是制是I
105、DiID(i=m+1,n)，系，系统以以阶段段1中的方式中的方式进行回行回应。l猜测：最后，攻击算法输出猜测猜测：最后，攻击算法输出猜测b0,1，如果，如果bb 则成功成功l攻攻击算法的算法的优势可定可定义为参数参数k的函数：的函数：l Adv ,A(k)=|Prbb 1/2|84定义4-9 如果对任何多项式时间的攻击算法，Adv,A(k)可忽略，那么就称这个IBE体制是语义安全的l一个函数一个函数g:RR是可以忽略的，意指是可以忽略的，意指对任意任意d0和一个充分大的和一个充分大的k有有|g(k)|1/kd定理4-15 设杂凑函数H1,H2是随机预言机，如果在g产生的群中BDH问题是困难的，
106、那么上述IBE方案是语义安全的基于身份的加密方案。2.选择密文安全l选择密文安全是公钥加密方案的一个标准安全概念，在选择密文安全是公钥加密方案的一个标准安全概念，在IBE体制中体制中这个要求需再加强些，因为在这个要求需再加强些，因为在IBE体制中，攻击算法攻击公钥体制中，攻击算法攻击公钥ID(即即获取与之对应的秘密钥获取与之对应的秘密钥)时，他可能已有所选用户时，他可能已有所选用户ID1,ID2,IDn的的秘密钥，因此选择密文安全的定义就应允许攻击算法获取与其所选秘密钥，因此选择密文安全的定义就应允许攻击算法获取与其所选身份身份(但不是但不是ID)相应的秘密密钥，可把这一要求看作对密钥产生算相
107、应的秘密密钥，可把这一要求看作对密钥产生算法的询问。法的询问。85一个IBE加密方案是抗自适应性选择密文攻击语义安全的，如果不存在多项式时间的攻击算法，它在下面的攻击过程中有不可忽略的概率。Gamel(1)初始化：系统输入安全参数初始化：系统输入安全参数k，产生公开的系统参数，产生公开的系统参数params和和保密的主密钥。保密的主密钥。l(2)阶段阶段1:攻击算法执行攻击算法执行q1,q2,qm,这里这里qi是下面询问之一：是下面询问之一：l对对的秘密钥产生询问。系统运行秘密钥产生算法，产生与公钥的秘密钥产生询问。系统运行秘密钥产生算法，产生与公钥IDi对应的秘密钥对应的秘密钥di，并把它发
108、送给攻击算法。，并把它发送给攻击算法。l对对的解密询问。系统运行秘密钥产生算法，产生与公钥的解密询问。系统运行秘密钥产生算法，产生与公钥IDi对对应的秘密钥应的秘密钥di，再运行解密算法，用，再运行解密算法，用di解密解密Ci ，并将所得明文发送给攻，并将所得明文发送给攻击算法。击算法。l上面的询问可以自适应的进行，是指执行每个上面的询问可以自适应的进行，是指执行每个qi时可以依赖于执行时可以依赖于执行q1,q2,qi1时得到的询问结果。时得到的询问结果。86l询问：攻击算法输出两个长度相等的明文询问：攻击算法输出两个长度相等的明文M0，M1，和一个要被询问，和一个要被询问的身份的身份ID。唯
109、一的限制是。唯一的限制是ID不在阶段不在阶段1中的任何秘密钥询问中出现。中的任何秘密钥询问中出现。系统随机选取一个比特值系统随机选取一个比特值b 0,1，产生生CEncrypt(params,ID,Mb),并将并将C作作为应答答发送送给攻攻击算法。算法。l(3) 阶段段2:攻攻击算法算法产生更多生更多询问qm+1,qn，qi是下面询问之一：是下面询问之一：l对对的秘密钥产生询问。系统以阶段的秘密钥产生询问。系统以阶段1中的方式进行回应。中的方式进行回应。l对对的解密询问。系统以阶段的解密询问。系统以阶段1中的方式进行回应。中的方式进行回应。l猜测：最后，攻击算法输出猜测猜测：最后，攻击算法输出
110、猜测b0,1，如果，如果bb 则成功成功l以上攻以上攻击过程也称程也称为“午餐午餐时间攻攻击”或或“午夜攻午夜攻击”，相当于有一个，相当于有一个执行解密运算的黑盒，掌握黑盒的人在午餐行解密运算的黑盒，掌握黑盒的人在午餐时间离开后，攻离开后，攻击者能者能够用黑盒用黑盒对自己自己选择的密文解密。午餐的密文解密。午餐过后，后，给攻攻击者一个目者一个目标密密文，攻文，攻击者者试图对目目标密文解密，但不能再使用黑盒了。密文解密，但不能再使用黑盒了。l攻攻击算法的算法的优势可定可定义为参数参数k的函数：的函数：l Adv ,A(k)=|Prbb 1/2|87定义4-10 如果对任何多项式时间的攻击算法，函
111、数Adv,A(k)可忽略，那么就称该IBE体制是抗自适应性选择密文攻击语义安全的l为使上述方案称为在随机预言机模型中是选择密文安全的，还需要其为使上述方案称为在随机预言机模型中是选择密文安全的，还需要其加以修改。以加以修改。以 pk(M,r)表示用随机比特表示用随机比特r在公在公钥pk下加密下加密M的公的公钥加密加密算法，算法，lFujisaki-Okamto指出，如果指出，如果 pk是是单向加密的，向加密的，则 pkhy在随机在随机预言机模型下是言机模型下是选择密文安全的，密文安全的，其中其中 是随机是随机产生的比特串，生的比特串，H3,H4是是杂凑函数。凑函数。单向加密粗略的讲就是对一个给
112、定的随机密文，攻击算法无法产生明文。单向加密是一个弱安全概念，这是因为它没有阻止攻击算法获得明文的部分比特值。88修改后的加密方案如下：(1)初始化l和基本方案相同，此外和基本方案相同，此外还需要需要选取两个取两个杂凑函数凑函数H3:0,1n0,1nZq*和和H4:0,1n 0,1n，其中，其中n是待加密消息的是待加密消息的长度度(2)加密l用公钥用公钥ID加密加密M 0,1nl计算计算QID=H1(ID) G1*l选择一个随机串选择一个随机串 0,1nl计算计算rH3( ,M),l确定密文确定密文Cl这里这里gIDe(QID,Ppub) G2*,(3)密钥产生l和基本方案相同。和基本方案相同。89(4)解密l令令C=是用是用ID加密所得的密文。如果加密所得的密文。如果U G1*，拒，拒绝这个密个密文。否文。否则，用秘密，用秘密钥dID G1*对C如下加密如下加密l计算计算V H2(e(dID,U) l计算计算W H4( )Ml确定确定rH3( ,M),检验U=rP是否成立，不成立是否成立，不成立则拒拒绝密文密文l把把M作为作为C的明文的明文定理4-16 设杂凑函数H1，H2，H3，H4是随机预言机，假设在由g生成的群中BDH问题是困难的，那么上述修改后的IBE是选择密文安全的。作业：lp131：4，10，11，12，13，14，15，16，17，18，19，2090
