第四章 公钥密码 本科生必修课《现代密码学》 主讲教师：董庆宽 副教授 研究方向：密码学与信息安全

Presentation on theme: "第四章 公钥密码 本科生必修课《现代密码学》 主讲教师：董庆宽 副教授 研究方向：密码学与信息安全"— Presentation transcript:

1 第四章 公钥密码 本科生必修课《现代密码学》 主讲教师：董庆宽 副教授 研究方向：密码学与信息安全
第四章 公钥密码 主讲教师：董庆宽 副教授 研究方向：密码学与信息安全 个人主页：

2 内容提要 4.1 公钥密码常用知识和算法 4.2 公钥密码体制的基本概念 4.3 RSA算法 4.4 Rabin体制 4.5 背包体制
第四章 公钥密码 内容提要 4.1 公钥密码常用知识和算法 4.2 公钥密码体制的基本概念 4.3 RSA算法 4.4 Rabin体制 4.5 背包体制 4.6 NTRU公钥密码系统 4.7 ElGamal密码体制与DH密钥交换 4.8 椭圆曲线密码体制 4.9 基于身份的密码体制 4.10公钥密码体制的可证明安全性

3 4.1 公钥密码常用知识和算法 一、基本数学知识 群、环、域、素数 模运算 欧几里得算法、扩展欧几里德算法 费尔马定理 欧拉函数
第四章 公钥密码：4.1 公钥密码常用知识和算法 4.1 公钥密码常用知识和算法 一、基本数学知识 群、环、域、素数 模运算 费尔马定理 ap-1=1 mod p ，p是素数 欧拉函数 (n)：小于n的且与n互素的正整数个数 a(n)=1 mod n 素性检验 1.爱拉托斯散筛法(Eratosthenes) 依次删去小于 素数的倍数 2. Miller-Rabin概率检测法 3.AKS 欧几里得算法、扩展欧几里德算法 求最大公约数和乘法的逆元 中国剩余定理 求一次同余方程组的解 离散对数，本原根 平方剩余 计算复杂性

4 4.1 公钥密码常用知识和算法 二、扩展欧几里得算法，有限域上求逆元 计算d mod f 的逆元
第四章 公钥密码：4.1 公钥密码常用知识和算法 4.1 公钥密码常用知识和算法 二、扩展欧几里得算法，有限域上求逆元 计算d mod f 的逆元 1. (X1, X2, X3)(1, 0, f); (Y1, Y2, Y3)(0, 1, d); 2. if Y3=0, then return X3=gcd(f, d) //此时无逆元 3. if Y3=1, then return Y3=gcd(f, d); Y2=d-1 mod f 4. Q=X3/Y3 5. (T1, T2, T3)(X1-QY1, X2-QY2, X3-QY3); 6. (X1, X2, X3)(Y1, Y2, Y3) 7. (Y1, Y2, Y3)  (T1, T2, T3) 8. goto 2

5 4.1 公钥密码常用知识和算法 三、Miller-Rabin概率检测法，找大素数
第四章 公钥密码：4.1 公钥密码常用知识和算法 4.1 公钥密码常用知识和算法 三、Miller-Rabin概率检测法，找大素数 原理：若p是大于2的素数，则x2=1 mod p只有1和-1两个解，所以 如果方程x2=1 mod p有一解x0{-1, 1}，那么p不为素数 算法：(a<n是随机选择的一个数，n是待检验的数，返回False则一 定不是素数，返回True则不一定是素数） 令d=1；n-1的二进制表示为bkbk-1…b0 for i=k downto 0 do { xd; d(dd) mod n; (此时d刚好是x的平方) if d=1 and x1 and xn-1 then return False; if bi=1 then d(da) mod n;} if d1 then return False; Return True; 循环结束后有d=an-1 mod n，若d1，则n不是素数。 x1 and xn-1 意指x2=1 mod p有不在{-1, 1}中的根 该测试如果进行s次，如果都是真T，则n是素数的概率最小为1-2-s

6 4.1 公钥密码常用知识和算法 四、蒙哥马利算法，避免求模运算中的除法
第四章 公钥密码：4.1 公钥密码常用知识和算法 4.1 公钥密码常用知识和算法 四、蒙哥马利算法，避免求模运算中的除法 避免求模过程中复杂耗时的除法（P.L.Montgomery,1985年提出) 计算TR-1 mod N (1) T=(T+MN)/R (2) IF TN return T-N; ELSE return T 其中M=(T mod R)×(N-1 mod R) mod R，且0<T<NR 而且显然有R(R-1 mod N)+N(N-1 mod R)=1+RN (R-1 mod N)以及(N-1 mod R）可预计算，R常取2的幂 一般先计算TR-1 mod N ，若R=2w，再不断左移模N 共w次可得结果

7 4.1 公钥密码常用知识和算法 蒙哥马利模乘算法计算Z=XYR-1 mod M
第四章 公钥密码：4.1 公钥密码常用知识和算法 4.1 公钥密码常用知识和算法 蒙哥马利模乘算法计算Z=XYR-1 mod M 输入：X=(XNw-1 ,…, X0)r， Y=(YNw-1 ,…, Y0)r，M=(MNw-1 ,…, M0)r， M=-(M0)-1 mod r ，其中0X, Y M，2N-1M2N， r =2w，gcd(M, r)=1，Nw=N/w

8 4.2 公钥密码体制的基本概念 公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。为密码学发展提供了新的理论和技术基础
第四章 公钥密码：4.2 公钥密码体制的基本概念 4.2 公钥密码体制的基本概念 公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。为密码学发展提供了新的理论和技术基础 公钥密码算法基本工具不再是代换和置换，而是数学函数 以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。 公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，即密钥分配和数字签字

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

10 4.2 公钥密码体制的基本概念 公钥密码的主要作用 公钥加密 数字签名 (Digital Signature)
第四章 公钥密码：4.2 公钥密码体制的基本概念 4.2 公钥密码体制的基本概念 公钥密码的主要作用 公钥加密 用于加密任何消息，象分组密码一样使用 任何人可以用公钥加密消息，私钥的拥有者可以解密消息 数字签名 (Digital Signature) 用于生成对某消息的数字签名 私钥的拥有者生成数字签名，任何人可以用公钥验证签名 签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法 基于公钥的密钥分配(Key Distribution) 用于交换秘密信息，常用于协商对称加密算法的密钥 可采用公钥加密的算法实现密钥分配 也可使用单独设计的密钥交换算法，如DH密钥交换协议实现密钥分配 参考资料：Arto Salomaa《公钥密码学》芬兰，等

11 4.2 公钥密码体制的基本概念 公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开
第四章 公钥密码：4.2 公钥密码体制的基本概念 4.2 公钥密码体制的基本概念 公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开 一个密钥是公开的，称为公开密钥，简称公开钥，用于加密、验证签名，可以被任何人知道 另一个密钥是为用户专用，因而是保密的，只能被消息的接收者或签名者知道，称为秘密密钥，简称秘密钥，用于解密、产生签名 因此公钥密码体制也称为双钥密码体制 算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的 因此加密和签名的验证者不能解密和生成签名

12 4.2.1 公钥密码体制的原理 公钥体制的加密过程 第四章 公钥密码：4.2 公钥密码体制的基本概念
① 密钥的产生：要求接收消息的端系统，产生一对用来加密和解密的密钥PKB和SKB，如图中的接收者B，其中PKB是公开钥，SKB是秘密钥。因此，公钥可以发布给其他人 ② 公开钥的分发：B将加密密钥(PKB)予以公开。另一密钥则被保密(SKB) ③ 加密：A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKB[m]其中c是密文，E是加密算法 ④ 解密：B收到密文c后，用自己的秘密钥SKB解密，即m=DSKB[c]，其中D是解密算法。因为只有B知道SKB，所以其他人都无法对c解密。

13 4.2.1 公钥密码体制的原理 公钥体制的认证过程 第四章 公钥密码：4.2 公钥密码体制的基本概念
公钥加密不仅能用于加、解密，还能用于对发方A发送的消息m提供认证 用户A用自己的秘密钥SKA对m加密，表示为c=ESKA[m] 将c发往B。B用A的公开钥PKA对c解密，表示为m=DPKA[c] 因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。 任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证，也实现了对身份的认证。

14 4.2.1 公钥密码体制的原理 认证符： 通过单向压缩函数(hash)解决长文件的签字
第四章 公钥密码：4.2 公钥密码体制的基本概念 4.2.1 公钥密码体制的原理 认证符： 通过单向压缩函数(hash)解决长文件的签字 公钥密码算法实质上是一种分组密码算法，但公钥密码算法运算复杂、速度很慢，而且对明文的加密和签名的结果存在很大的数据扩展，因此这对于长文件来说直接使用不可行 改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符，然后对认证符进行处理 认证符具有这样一个性质： 如果保持认证符的值不变而修改文件，在计算上是不可行的 签名过程中，往往用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。(详见第7章)

15 4.2.1 公钥密码体制的原理 公钥体制同时提供加密和认证的过程 第四章 公钥密码：4.2 公钥密码体制的基本概念
为了同时提供认证功能和保密性，可使用双重加、解密 先签名后加密：发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为c=EPKB[ESKA[m]] 先解密再验证：收方的解密过程为m=DPKA[DSKB[c]] 先加密后签名是不安全的，别人可以先将签名去掉，再签上自己的签名，从而实现了篡改，谎称是自己产生了该密文消息。 单纯的先签名再加密有时也不安全，收方解密出签名的消息后，再用其他人公钥加密发给其他人，从而实现冒充签名者发送消息给其它任何人，因此签字中还应该有收方的ID

16 4.2.2 公钥密码算法应满足的要求 公钥密码算法应满足以下要求 以上要求的本质之处在于要求一个陷门单向函数。
第四章 公钥密码：4.2 公钥密码体制的基本概念 公钥密码算法应满足的要求 公钥密码算法应满足以下要求 ① 收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。由私钥及其他密码信息容易计算出公开密钥(P问题) ② 发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKB[m]在计算上是容易的 ③ 收方B用自己的秘密钥对c解密，即m=DSKB[c]在计算上是容易的 ④ 敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的 ⑤ 敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的 ⑥ 加、解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB (m)] 其中最后一条虽然非常有用，但不是对所有的算法都作要求。在构建盲签字等算法时需要类似要求 以上要求的本质之处在于要求一个陷门单向函数。

17 第四章 公钥密码：4.2 公钥密码体制的基本概念 公钥密码算法应满足的要求 单向函数 两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个 原像x∈X，且由x易于计算它的像y，由y计算它的原像x是不可行的 “易于计算”是指函数值能在其输入长度n的多项式时间内求出，即 求函数值的计算时间复杂度O(na),其中a是一固定的常数 这时称求函数值的算法属于多项式类P，否则就是不可行的，例如， 函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则 认为求函数值是不可行的。 易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似， 然而又存在着本质的区别 在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时 的复杂度来度量的。这时可能对某些情况很容易求解，复杂度很低 而在此所说的两个概念是指算法在几乎所有情况下的情形

18 4.2.2 公钥密码算法应满足的要求 陷门单向函数 总结为： 陷门单向函数是一族可逆函数fk，满足
第四章 公钥密码：4.2 公钥密码体制的基本概念 公钥密码算法应满足的要求 陷门单向函数 称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成 总结为： 陷门单向函数是一族可逆函数fk，满足 ①当k和X已知时，Y=fk(X)易于计算 ②当k和Y已知时，X=fk-1(Y)易于计算 ③当Y已知但k未知时，X=fk-1(Y)计算上是不可行的 研究公钥密码算法就是要找出合适的陷门单向函数

19 4.2.2 公钥密码算法应满足的要求 用于构造单向陷门函数的典型困难问题及算法 RSA(基于大数分解困难问题)
第四章 公钥密码：4.2 公钥密码体制的基本概念 公钥密码算法应满足的要求 用于构造单向陷门函数的典型困难问题及算法 RSA(基于大数分解困难问题) RSA系列算法，Rabin体制 DLP (基于求解有限域上离散对数困难问题) ElGamal加密体制，DH密钥交换 ECC(椭圆曲线离散对数问题) ECC上双线性对，ECC上基于身份的密码体制 基于格的概率加密体制(基于求解格上最短向量等问题) NTRU… 基于纠错码的体制McElice… 背包体制

20 4.2.2 公钥密码算法应满足的要求 量子公钥密码 后量子密码学post-quantum cryptography
第四章 公钥密码：4.2 公钥密码体制的基本概念 公钥密码算法应满足的要求 量子公钥密码 基于量子编码、量子不可克隆定理、子集和问题等困难性的公钥密码算法，但是目前这些问题的困难性也受到质疑 后量子密码学post-quantum cryptography 量子计算具有内在并行性，能攻破RSA、离散对数、ECC等体制 06年在比利时鲁汶天主教大学召开了第一次后量子密码学国际会议 Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen, “Post-Quantum Cryptography,” Springer-Verlag, pp.245, 2009. 几种量子计算尚不能征服的密码体制 基于Hash的密码（Hash-based cryptography） 如Merkle于1979年提出的hash树公钥签名体制，按Lamport和Diffie的单消息签名概念构建的

21 4.2.2 公钥密码算法应满足的要求 基于编码（纠错码）的密码（Code-based cryptography）
第四章 公钥密码：4.2 公钥密码体制的基本概念 公钥密码算法应满足的要求 基于编码（纠错码）的密码（Code-based cryptography） 如McEliece1978年提出的隐Goppa码公钥加密体制。 王新梅教授提出的新梅算法 基于格的密码（Lattice-based cryptography） Hoffstein-Pipher-Silverman于1998年提出的“NTRU”公钥加密体制，虽不是第一个，但为最引人注目的一个 多变量二次方程密码（Multivariate-quadratic-equations cryptography) 如Patarin于1996年提出的“HFEv-”公钥签名体制就是几个重要例子中的一个，此例后为Matsumoto和Imai所推广 秘密（单）钥密码（Secret-key cryptography） 如高级数据加密标准AES

22 4.2.3 对公钥密码体制的攻击 以下讨论的攻击是指对所有公钥密码体制都有效的平凡的攻击 第一种平凡的攻击：（穷搜索攻击与密钥长度）
第四章 公钥密码：4.2 公钥密码体制的基本概念 4.2.3 对公钥密码体制的攻击 以下讨论的攻击是指对所有公钥密码体制都有效的平凡的攻击 涉及到公钥算法所基于的困难问题的安全性和参数空间大小的安全性 第一种平凡的攻击：（穷搜索攻击与密钥长度） 如果密钥太短，公钥密码体制也易受到穷搜索攻击 然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用 因此公钥密码体制目前主要用于密钥管理和数字签字。即处理短消息如密钥和hash值

23 4.2.3 对公钥密码体制的攻击 第二种平凡的攻击 第三种平凡的攻击：(可能字攻击)
第四章 公钥密码：4.2 公钥密码体制的基本概念 4.2.3 对公钥密码体制的攻击 第二种平凡的攻击 是寻找从公开钥计算秘密钥的方法 目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的 第三种平凡的攻击：(可能字攻击) 仅适用于对公钥密码算法的攻击 例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较 如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，攻击的本质是对56比特DES密钥的穷搜索攻击 抵抗方法是在欲发送的明文消息后添加一些随机比特 不同的公钥密码算法在设计和实现中的密码协议是影响安全性的主要方面，不同算法的攻击不同。 公钥的安全性是指计算上的安全性

24 第四章 公钥密码：4.3 RSA算法 4.3 RSA算法 从本节开始，我们介绍分别介绍基于不同困难问题的公钥密码体制，这些体制在实际中都是不安全的，实用的体制都是在这些基本原型基础上进行了较大的修改而设计的。 但这些体制会启发我们如何根据不同的数学困难问题构造陷门单向函数，并进而构造公钥密码算法 1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，已得到广泛的应用 R L Rivest, A Shamir, L Adleman, "On Digital Signatures and Public Key Cryptosystems", Communications of the ACM, vol 21 no 2, pp , Feb. 1978 它既可用于加密、又可用于数字签字。 RSA算法的安全性是基于数论中大整数分解的困难性(但可能达不到大数分解的困难强度) IEEE P1363 公钥密码标准

25 4.3.1 算法描述 1．密钥的产生 ① 选两个保密的大素数p和q
第四章 公钥密码：4.3 RSA算法 算法描述 1．密钥的产生 ① 选两个保密的大素数p和q ② 计算n=p×q，(n)=(p-1)(q-1)，其中(n)是n的欧拉函数值 ③ 选一整数e，满足1<e< (n)，且gcd((n),e)=1 ④ 计算d，满足d·e≡1 mod (n)，即d是e在模(n)下的乘法逆元，因e与(n)互素，模(n)的乘法逆元一定存在 ⑤ 以{e,n}为公开钥,{d,p,q}为秘密钥 秘密钥也可记为d，或{d, n}，如果是系统负责产生密钥，则用户可能不知道p,q

26 4.3.1 算法描述 2．加密 3．解密 c≡me mod n m≡cd mod n
第四章 公钥密码：4.3 RSA算法 算法描述 2．加密 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。 然后对每个明文分组m，作加密运算： c≡me mod n 3．解密 对密文分组的解密运算为： m≡cd mod n RSA的模很长，如模n为1024比特的RSA一次加密约1024比特明文，相当于16次DES加密，但一次RSA比16次DES要慢很多，不在一个数量级上），所以公钥密码算法不适合加密长消息

27 4.3.1 算法描述 RSA算法中解密过程的正确性证明
算法描述 RSA算法中解密过程的正确性证明 证明： 由c≡me mod n，可知 cd mod n≡med mod n≡mk(n)+1 mod n 下面分两种情况： ① m与n互素，则由Euler定理得 m(n)≡1 mod n，mk(n)≡1 mod n，mk(n)+1≡m mod n, 即cd mod n≡m ② gcd(m,n)≠1，因n=pq，所以m是p的倍数或q的倍数，不妨设m=cp，其中c为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与m<n=pq矛盾。 由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)＋1＝m mod n，所以cd mod n≡m。(证毕)

28 4.3.2 RSA算法中的计算问题 1. RSA的加密与解密过程 ①模运算的累次乘法 RSA的加密、解密过程都为求一个整数的整数次幂，再取模
如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如计算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。 用模运算的性质：即采用累次乘法，可减小中间结果 (a×b) mod n=[(a mod n)×(b mod n)] mod n

29 4.3.2 RSA算法中的计算问题 ③快速指数算法 求am可如下进行，其中a，m是正整数： 因此 am＝
考虑如何提高加、解密运算中模指数运算的有效性。例如求x16，直接计算需做15次乘法。若重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法 求am可如下进行，其中a，m是正整数： 将m表示为二进制形式bkbk-1…b0，即 m=bk2k+bk-12k-1+…+b12+b0 因此 am＝ 例如：19=1×24+0×23+0×22+1×21+1×20，所以a19=((((a1)2a0)2a0)2a1)2a1

30 4.3.2 RSA算法中的计算问题 快速指数算法：计算am mod n c=0; d=1； for i=k downto 0 do {
c=2×c; //仅为验证以上过程，而在具体算法中可删去 d=(d×d) mod n;//计算平方 if bi=1 then { c=c+1; //仅为验证以上过程，而在具体算法中可删去 d=(d×a) mod n // bi=1时与a相乘 } return d. 其中d是中间结果，d的终值即为所求结果。c的终值为指数m

31 4.3.2 RSA算法中的计算问题 计算复杂度: l＋W(m)-2次模乘（m为模指数）
l为指数的bit长，W(m)为指数m的重量(二进制比特1的个数) T进制快速模指数算法：求am可如下进行： 将m表示为T进制形式bkbk-1…b0，即 m=bkTk+bk-1Tk-1+…+b1T+b0 取T=2w am= 首先预计算出ai mod n，其中i=1,2，…，2w-1 再用快速模指数运算 w的选择与预计算需要的存储空间有关

32 ④一种改进的RSA实现方法 (即4.3.3节） RSA的加密很快，因为加密指数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 = M1×q×(q－1mod p)+ M2×p×(p－1mod q) mod N 不考虑CRT的计算代价，改进的算法的解密速度是原来的4倍 若考虑CRT的计算代价，改进后的算法解密速度是原来的3倍多

33 4.3.2 RSA算法中的计算问题 2. RSA密钥的产生 需考虑两个大素数p、q的选取，以及e的选取和d的计算
n(=pq) 是公开的，为了防止敌手通过穷搜索发现p、q，这两个素数应足够大，且具有好的随机性 (1) 如何有效地寻找大素数 一般是先随机选取一个大的奇数（例如用伪随机数产生器）， 然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止 素性检验算法通常都是概率性的，常用Miller-Rabin概率检测算法实现，只有在产生新密钥时才需执行这一工作 (2) 如何选取满足gcd((n),e)=1的e，并计算满足d·e≡1 mod (n)的d 这一问题可由推广的Euclid算法完成

34 4.3.3 RSA的安全性 一. 平凡攻击下的安全性 (1) 大整数分解问题
RSA的安全性是基于大整数分解的困难性假定，至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法 随着计算能力不断提高，被分解的大数越来越大 例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-155（512bit）已于1999年8月被成功分解，RSA-158，2002年被成功分解，现在768比特的模值已经不安全 对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进，已知的各种算法的渐近运行时间约为： 试除法：n/2；二次筛(QS)： 椭圆曲线(EC)： ， 数域筛(NFS)： 512bit RSA只能提供60比特的安全性

35 4.3.3 RSA的安全性 将来也可能还有更好的分解算法 量子计算如果成功的话，可解决大整数分解问题
(2) 用于产生大素数的随机数必须是不可预测的，即密码上是安全的 特别的如果要生成多个大素数，这一要求尤为重要，因为敌手可能会猜测随机数，进而获得可能的素数 要求产生大素数的随机数采用安全性能良好的伪随机数产生器，在引入一些真随机因素，如时间、键盘敲击记录等 (3) 由n直接确定φ(n)等价于对n的分解 由RSA密钥产生容易推出p+q=n－(n)+1； 以及 由此可见，由p、q确定(n)和由(n)确定p、q是等价的

36 4.3.3 RSA的安全性 (4) 研究表明，如果e<n且d<n1/4，则d能被容易地确定 (5) 对p和q提出以下要求
D.Boneh证明了RSA中私有密钥长度小于ｎ0.292时方案容易被攻破 (5) 对p和q提出以下要求 1) |p-q|要大 由(p+q)2/4－n=(p+q)2/4－pq=(p－q)2/4，如果|p-q|小，则(p－q)2/4也小，因此(p+q)2/4稍大于n，(p+q)/2稍大于n1/2。可得n的如下分解步骤： ① 顺序检查大于n1/2的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。 ② 由x2-n=y2，得n=(x+y)(x-y)。 2) p-1和q-1都应有大素因子(强素数) 这是因为RSA算法存在着可能的重复加密攻击法

37 4.3.3 RSA的安全性 (6) 重复加密攻击 设攻击者截获密文c，可如下进行重复加密： ， … , 若 ，则有 ，
… , 若 ，则有 ， 即 ，所以重复加密的倒数第2步就已恢复出明文m t 较小时攻击是可行的。为抵抗这种攻击，p、q的选取应保证使 t 很大。 设m在模n下阶为k，由 得 ， 所以k|(et-1)，即et≡1(mod k)，t 取为满足前式的最小值（为e在模k下的阶）。 又当e与k互素时t|(k)。为使t大，k就应大且(k)应有大的素因子。又由k|(n)，所以为使k大，p-1和q-1都应有大的素因子

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

39 4.3.3 RSA的安全性 (2) 低指数攻击 假定将RSA算法同时用于多个用户（以下假定3个），然而每个用户的加密指数（即公开钥）都很小。
设3个用户的模数分别为ni(i=1,2,3)，当i≠j时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。 设明文消息是m，加密指数e＝3， 密文分别是: c1≡m3(mod n1) c2≡m3(mod n2) c3≡m3(mod n3) 由中国剩余定理可求出m3(mod n1n2n3)。由于m3<n1n2n3，可直接由m3开立方根得到m。 最初建议使用e=3，不安全，e是有下限的

40 4.3.3 RSA的安全性 三、RSA体制的同态攻击 根据RSA加密算法，如果c1=m1e mod n； c2=m2e mod n
那么我们构造密文c1c2其对应的明文刚好是m1m2 这种性质就称为同态特性。攻击者在不知道两个明文的情况下，完成了两个明文乘积的加密 然而这种攻击对于今天的云计算而言，确是一个很好的性质，计算方在不知道明文的情况下仍旧可以对明文进行处理 抵抗这种攻击的方法是对加密的明文再填加一个验证符，从而抵消同态特性， 在实际的加密中为了有效增大明文空间，并消除明文泄露，还要填充一定长度的随机数。这既是概率加密

41 4.3.3 RSA的安全性 三、RSA体制的同态攻击 根据RSA加密算法，如果c1=m1e mod n； c2=m2e mod n
那么我们构造密文c1c2其对应的明文刚好是m1m2 这种性质就称为同态特性。攻击者在不知道两个明文的情况下，完成了两个明文乘积的加密 然而这种攻击对于今天的云计算而言，确是一个很好的性质，计算方在不知道明文的情况下仍旧可以对明文进行处理 抵抗这种攻击的方法是对加密的明文再填加一个验证符，从而抵消同态特性， 在实际的加密中为了有效增大明文空间，并消除明文泄露，还要填充一定长度的随机数。这既是概率加密

42 第四章 公钥密码：4.3 RSA算法 4.3.3 RSA的安全性 概率加密体制 1982年，Shafi Goldwasser和Silvio Micali 提出了概率加密( Probabilistic Encryption) 的概念, 基本思想是使公钥体制的信息泄露为0, 其相应的密码体制称作概率加密公钥体制( Probabilistic Encryption Cryptosystem)，简称PEC。概率加密公钥体制具有多项式安全性。一个明文在加密后得到的密文是一个随机变量

43 4.3.4 RSA-OAEP算法 随机预言机模型下安全的RSA算法
最佳非对称加密填充（OAEP）是一个通常和RSA一起使用的填充方案。OAEP由Bellare和Rogaway 提出的

44 第四章 公钥密码：4.4 Rabin密码体制 4.4 Rabin密码体制 RSA密码体制破译RSA的难度不超过大整数的分解。但还不能证明破译RSA和分解大整数是等价的，虽然这一结论已得到普遍共识 Rabin密码体制已被证明对该体制的破译等价于对大整数的分解 RSA中选取的公开钥e满足1<e< (n)，且gcd(e, (n))=1。Rabin密码体制则取e=2 1. 密钥的产生 随机选择两个大素数p、q，满足p≡q≡3 mod 4，Blum数，即这两个素数形式为4k+3；计算n=p×q。以n作为公开钥，p、q作为秘密钥。 2. 加密： c≡m2 mod n 其中m是明文分组，c是对应的密文分组。 3. 解密 解密就是求c模n的平方根，即解x2≡c mod n，因此，Rabin体制也被称为基于环上二次剩余困难性构造，由中国剩余定理知解该方程等价于解方程组

45 第四章 公钥密码：4.4 Rabin密码体制 4.4 Rabin密码体制 由于p≡q≡3 mod 4，方程组的解可容易地求出，其中每个方程都有两个解，即 x≡m1 mod p， x≡m2 mod q， 经过组合可得4个同余方程组 ， ， ， 由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。 为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。 当p≡q≡3 mod 4时，两个方程的平方根m1 、m2易于求出 因c是模p的平方剩余，故 ≡c(p-1)/2≡1 mod p，易于验证 即为方程x2≡c mod p的两个根，同理 即为方程x2≡c mod q的两个平方根

46 第四章 公钥密码：4.4 Rabin密码体制 4.4 Rabin密码体制 由以前知识知，求解方程x2≡a mod n与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。 Rabin密码在选择密文攻击CCA下是不安全的。 二次剩余有四个根分成两组m1 和m2，如果每组中分别获得一个，则可分解模n，这是因为m12 =m22 mod n，即m12 -m22 =kn，从而gcd(m1-m2,n)应该恢复p和q其中的一个 如果敌手控制解密机，那么随机选一个x加密后给解密机，解密机解密出x返回，若x x则完成了攻击 和RSA一样，安全的Rabin算法也必须对消息进行padding 明文消息空间太小时，消息需要填充

47 第四章 公钥密码：4.5 背包密码体制 4.5 背包密码体制 设A=(a1,a2,…,an)是由n个不同的正整数构成的n元组，s是另一已知的正整数。背包问题就是从A中求出所有的ai，使其和等于s。其中A称为背包向量，s是背包的容积。 例如,A=(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523)，s=3231。 由于 3231= 所以从A中找出的满足要求的数有129、473、903、561、1165 原则上讲，通过检查A的所有子集，总可找出问题的解（若有解的话） 本例A的子集共有210=1024个（包括空集）。 然而如果A中元素个数n很大，子集个数2n将非常大。 如A中有300个元素，A的子集有2300。寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题( Knapsack)是NPC问题。

48 4.5 背包密码体制 由背包问题构造公钥密码体制同样是要构造一个(陷门)单向函数f
第四章 公钥密码：4.5 背包密码体制 4.5 背包密码体制 由背包问题构造公钥密码体制同样是要构造一个(陷门)单向函数f 将x(1≤x≤2n-1)写成长为n的二元表示, f(x)定义为A中所有ai的和，其中x的二元表示的第i位为1，即 f(1)=f(0…001)=an ; f(2)=f(0…010)=an-1 ; f(3)=f(0…011)=an-1+an … f(2n-1)=f(1…111)=a1+a2+…+an 使用向量乘(内积)，有f(x)=A·Bx，其中Bx是x二元表示的列向量。 上例中f(364) =f( )= = 3231 显然，已知x很容易求f(x)，但已知f(x)求x就是要解背包问题。 为使接收方能够解密，就需找出单向函数f(x)的陷门。为此需引入一种特殊类型的背包向量。

49 4.5 背包密码体制 定义背包向量A=(a1,a2,…,an)称为超递增的，如果 超递增背包向量对应的背包问题很容易通过以下算法求解。
第四章 公钥密码：4.5 背包密码体制 4.5 背包密码体制 定义背包向量A=(a1,a2,…,an)称为超递增的，如果 ，j＝1,2,…,n 超递增背包向量对应的背包问题很容易通过以下算法求解。 已知s为背包容积，对A从右向左检查每一元素，以确定是否在解中。 若s≥an，则an在解中，令xn=1； 若s<an，则an不在解中，令xn=0。 下面令 s＝ 对an-1重复上述过程，一直下去，直到检查出a1是否在解中。 检查结束后得 x=(x1x2…xn)，Bx=(x1x2…xn)T

50 4.5 背包密码体制 基于背包问题构造公钥密码体制 1. 密钥产生 2.加密 选一个超递增背包向量A=(a1,a2,…,an)
第四章 公钥密码：4.5 背包密码体制 4.5 背包密码体制 基于背包问题构造公钥密码体制 1. 密钥产生 选一个超递增背包向量A=(a1,a2,…,an) 用模乘对A进行伪装，模乘的模数k和乘数t皆取为常量，满足 ，gcd(t,k)=1，即t在模k下有乘法逆元。 设 bi≡t·ai mod k, i=1,2,…,n，得一新的背包向量B=(b1,b2,…,bn)，记为B≡t·A mod k 用户以B作为自己的公开钥，A, t, k为私钥 2.加密 对明文分组x=(x1x2…xn)的加密运算为c=f(x)=B·Bx mod k

51 4.5 背包密码体制 3. 解密 首先由s≡t-1c mod k，求出s作为超递增背包向量A的容积，
第四章 公钥密码：4.5 背包密码体制 4.5 背包密码体制 3. 解密 首先由s≡t-1c mod k，求出s作为超递增背包向量A的容积， 再由超递增背包向量A解背包问题即得x=(x1x2…xn)。 这是因为t-1c mod k≡t-1tABx mod k≡ABx mod k，而由 ，知ABx<k，所以t-1c mod k=ABx是惟一的。 背包密码体制是Diffie和Hellman 1976年提出公钥密码体制的设想后的第一个公钥密码体制，由Merkle和Hellman 1978年提出。它表示了如何将NP完全问题用于公开密钥算法。 然而又过了两年该体制即被破译 破译的基本思想是不必找出正确的模数k和乘数t（即陷门信息），只须找出任意模数k′和乘数t′，使得用k′和t′去乘公开的背包向量B时，能够产生超递增的背包向量即可

52 4.6.1 NTRU密码体制 NTRU是一种环上基于格的公钥密码系统，由Jeffrey Hoffstein 等人在1998年提出
密钥短且容易产生，算法的运算速度快，所需存储空间小。 系统建立在整系数多项式环上（＋Abel群，×半群，可分配）。 设R表示最高次数不超过N－1的所有整系数多项式集合 设a＝a0+a1x+…+aN－1xN－1, b＝a0+b1x+…+bN－1xN－1是R上两个元素 R上的加法定义为a+b＝(a0+b0)+(a1+b1)x+…+(aN-1+bN-1)xN－1, R上的乘法定义为a*b＝c0+c1x+…+cN-1xN－1 其中k阶系数ck＝a0bk+a1bk-1+…+akb0+ak+1bN-1+ak+2bN-2+…+aN-1bk+1 ＝ 算法的参数 参数包括3个整数(N,p,q)和4个次数为N-1的整系数多项式集合Lf , Lg, L, Lm，其中p是小的奇素数，但满足gcd(p,q)=1，且q>2p (modq)和(modp)运算的结果分别限制在区间(-q/2, q/2]和(-p/2, p/2]内

53 第四章 公钥密码：4.6 NTRU公钥密码系统 4.6.1 NTRU密码体制 1. 密钥的产生 随机选取两个多项式f, gLg，它们的系数均属于{0, ±1}，其中多项式f在(mod q, mod xN-1)和(mod p, mod xN-1)均可逆，其逆元分别表示为Fq和Fp，即：Fq*f=1 mod q 和 Fp*f=1 mod p。 计算h＝Fq*g mod q，以h为公钥，f和g作为秘密钥，接收方同时还需保存Fp 2. 加密 设发送方欲将消息mLm发送给接收方，可对m作如下加密：随机选取多项式L ，用公钥h对消息进行加密 e＝p*h+m (mod q, mod xN-1) 将e发送给接收方。

54 4.6.1 NTRU密码体制 4. 解密 接收方收到e后，使用秘密钥f对其作如下解密。
①首先计算a=f*e(mod q), a的系数选在-q/2到q/2之间. ②将a作为一个整系数多项式，计算Fp*a(mod p)即可恢复明文m 解密原理： a=f*e＝f*p*h+f*m (mod q) ＝f*p*Fq*g +f*m (mod q) ＝ p*g +f*m (mod q) ＝ p*g +f*m 最后一步是由于若选择的参数合适，可保证多项式p*g +f*m的系数在-q/2到q/2之间，而无mod q，所以对p*g +f*m模q运算后结果不变 而Fp*a＝Fp*p*g +Fp*f*m (mod p)＝m (mod p) 当然也可能因为系数没控制在-q/2到q/2之间而解密失败

55 第四章 公钥密码：4.6 NTRU公钥密码系统 4.6.2 NTRU的安全性 一、若f和pg的系数绝对值之和不超过(q-1)/p，则对任何明文m(x)都保证：pgr(x)+f(x)m(x) (modxN-1)的每个系数都不超出区间(-q/2, q/2] 二、一般， f(x)和pg(x) 的系数恰当地设计，可以对绝大多数明文m(x)都保证： p*g +f*m (modxN-1)的每个系数都不超出区间(-q/2, q/2]。 对于公钥h，如果s L满足 t=h*s (modq, modxN-1)， 且多项式pt* +s*m (modxN-1) 的每个系数都在区间(-q/2, q/2]内，则此{t, s}就是能够将此{ , m}进行解密的一个局部有效私钥。这是因为 h=t*s-1(modq, modxN-1)， 因此，e=p*h+m (modq, modxN-1)； a=s*e = pt* +s*m (modq, modxN-1)； = pt* +s*m (modxN-1)；//上式系数都在(-q/2, q/2]内，所以无mod q 进而有s-1*a (modp, modxN-1)=s-1*s*m (modp, modxN-1)=m

56 第四章 公钥密码：4.6 NTRU公钥密码系统 4.6.2 NTRU的安全性 当{t, s}的尺寸比较小时，就可能有{, m} 使pt* +s*m (modxN-1) 的每个系数都在区间(-q/2, q/2]内，因而{t, s}能作为有效私钥对{, m}成功解密 {t, s}的尺寸越较小， {t, s}能够成功解密的{, m}越多。 寻找满足方程t=h*s(modq, modxN-1)、且尺寸足够小的{t, s}是攻破NTRU的关键。方程t=h*s(modq, modxN-1) 的全部解{t, s}构成了一个格，称为CS格。真正的私钥{g, f}属于此CS格。 CS 格归约被用来寻找“尺寸”足够小的{t, s} ，来作为NTRU的有效私钥或局部有效私钥。 CS 格归约的方法主要是LLL算法和各种改进算法 只要N足够大（N≥251），在当前CS 格归约还不能成功。 格的定义 若干个N维向量组成的集合，如果满足“集合中任何若干个向量的整数线性组合仍是集合中的一个向量。”则该结合称为一个格。

57 4.6.2 NTRU的安全性 格的最小向量问题(SVP) 关于格有以下的性质和概念。
如果格中存在这样的几个向量，满足①它们（实数）线性无关；② 格中的任何其它向量都能唯一地表示为这几个向量的整数线性组合 。则这几个向量构成的向量组称为基。 基中的向量的个数称为格的维数。 格的维数总是不超过N。 给定一个格的一组基。寻找格中的“尺寸最小”的向量（即模最小的向 量），称为格的最小向量问题（shortest vector problem；SVP）。又称 为格归约 实际上，格归约的传统算法为LLL算法，以后又有各种改进的算法。 当格的维数比较大时（比如，维数大于200），当前的所有格归约算法 都不是有效算法。

58 4.7.1 离散对数问题及其困难性 有限域GF(p)上的离散对数问题
第四章 公钥密码：4.7 ElGamal密码体制与DH密钥交换 4.7.1 离散对数问题及其困难性 有限域GF(p)上的离散对数问题 若已知y，g，p，求x满足y=gxmodp，称为求解离散对数问题。记为x=logg y mod p。 求解离散对数问题的“最笨的方法”当然就是穷举，运算次数约为( p－1)/2。 许多求解离散对数问题的算法比穷举快得多，比如Shanks算法，Pohlig-Hellman算法等。 最快求解法的运算次数约为数量级 这个计算量称为亚指数计算量，当log2p≈1024时，亚指数计算量不小于2100数量级，因此是安全的 如果p-1不含大素因子，很多情况下也是容易计算的，这时x=x mod p-1,如果都是小因子，则可分别求出模小因子，再用CRT定理。

59 第四章 公钥密码：4.7 ElGamal密码体制与DH密钥交换
1. 密钥产生 选择一个大的素数p；选择g，1<g <p；选择x，1<x <p-1； 计算y=gxmod p，公钥是(p, g, y)，私钥是x 2. 加密 设欲加密明文消息M，0< M <p 随机选一整数k ,满足 gcd(k,p－1)=1 计算对C1≡gk mod p,C2≡ykM mod p，密文为C = C1||C2 (级联) 3. 解密 M=C2/C1x mod p 这是因为C2/C1x mod p＝ykM/gkx mod p＝ykM/yk mod p＝M mod p 特点：密文由明文和所选随机数k来定，因而是一种概率加密体制，代价是使数据扩展一倍

60 4.7.3 Diffie-Hellman 密钥交换 ElGamal加密体制的本质是使用了DH密钥交换技术
DH密钥交换是W.Diffie和M.Hellman于1976年提出的第一个公钥密码算法，已在很多商业产品中得以应用 算法的唯一目的是使得两个用户能够安全地交换密钥，得到一个共享地会话密钥，算法本身不能用于加、解密 算法的安全性基于求离散对数的困难性 假设p是大素数，g是p的本原根，p和g作为公开元素，协议如下： ① 用户Alice选择随机数x，计算a=gx mod p，保密x，发送a给Bob ② 用户Bob选择随机数y，计算b=gy mod p，保密y，发送b给Alice ③ Bob和Alice各自计算 k=bx mod p和k=ay mod p, 从而得到共享密钥k 这是因为k=bx mod p=(gy)xmod p=(gx)ymod p=ay mod p

61 4.8 椭圆曲线密码体制 为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。
第四章 公钥密码：4.8 椭圆曲线密码体制 4.8 椭圆曲线密码体制 为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。 相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景，软硬件实现都有优势 ECC已被IEEE公钥密码标准P1363采用 1985年，N. Koblitz和V. Miller独立将其引入密码学中，成为构造双钥密码体制的一个有力工具 其安全性主要基于ECDLP椭圆曲线离散对数问题 有限域上的方案都可以用椭圆曲线实现

62 第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.1 椭圆曲线 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e (4-1) 其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。 从图可见，椭圆曲线关于x轴对称。

63 第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.1 椭圆曲线 椭圆曲线上的加法运算定义如下： 如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）： ① O为加法单位元，即对椭圆曲线上任一点P，有 P+O=P (这是因为P与-P在曲线的第三个交点是O) ② 设P1=(x,y)是椭圆曲线上的一点（如图所示），它的加法逆元定义为P2=－P1=(x, -y) 这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。 由O+O=O，还可得O= -O

64 4.8.1 椭圆曲线 ③ 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1
第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.1 椭圆曲线 ③ 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1 这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q或P1=R 由Q+R+P1=O 得 Q+R=-P1 ④ 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…， 以上定义的加法具有加法运算的一般性质，如交换律、结合律等

65 第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.2 有限域上的椭圆曲线 密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式(4-1)中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数） 其中最为常用的是由方程(4-2)定义的曲线 y2≡x3+ax+b(mod p) (4-2) (a,bGF(p),4a3+27b2(mod p)≠0) 因为＝(a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b＝0的判别式，当4a3+27b2 ＝0时方程有重根，设为x0，则点Q0＝(x0,0)是方程(4-2)的重根 即x3+ax+b＝(x-x0)3或者＝(x-x0)2(x-x1)，重根将使得一阶导数3x2＋a在该Q0点为0 令F(x,y)=y2－x3－ax－b，则F/x|Q0=F/y|Q0=0 所以dy/dx=－(F/x)/(F/y)＝(3x2＋a)/2y在Q0点无定义，即曲线y2≡x3+ax+b在Q0点的切线无定义，因此点Q0的倍点运算无定义

66 4.8.2 有限域上的椭圆曲线 有限域上的椭圆曲线群定义如下：
第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.2 有限域上的椭圆曲线 有限域上的椭圆曲线群定义如下： 设Ep(a,b)表示方程(4-2)所定义的椭圆曲线上的点集{(x,y)|0x<p,0y<p，且x,y均为整数}并上无穷远点O 一般来说，Ep(a,b)由以下方式产生： ① 对每一x(0x<p且x为整数），计算x3+ax+b(mod p)。 ② 决定①中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根 (y=0 时只有一个平方根)。即判断是否是模p的平方剩余 例：椭圆曲线E23(1, 1)，4a3+27b2(mod 23)≡8≠0，方程为y2≡x3+x+1(mod 23)，那么曲线在GF(23)中的整数点，注意点和其逆元，表中未给出O (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)

67 4.8.2 有限域上的椭圆曲线 Ep(a,b)上的加法定义如下： 设P，QEp(a,b)，则 ① P+O=P；
第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.2 有限域上的椭圆曲线 Ep(a,b)上的加法定义如下： 设P，QEp(a,b)，则 ① P+O=P； ② 若P=(x,y)，那么(x, y)+(x, -y)=O，即 (x, -y)是P的加法逆元，记为-P。 显然任一点P和其逆元-P都是Ep(a,b)中的点， 如上例，P=(13,7)和-P=(13, -7)=(13, 16)E23(1,1) ③ 设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下规则确定： x3≡λ2－x1－x2(mod p) y3≡λ(x1－x3)－y1(mod p) 其中 λ＝ 切线 提示： 计算中凡是除法b/a在约减后一定要先求a的逆元，再乘法ba-1 另外，计算点加后可带入原方程验证

68 第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.2 有限域上的椭圆曲线 公式推导示例

69 4.8.2 有限域上的椭圆曲线 倍点运算仍定义为重复加法，如4P=P+P+P+P 快速倍点运算 kP Ep(a,b)是一个Abel群
第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.2 有限域上的椭圆曲线 倍点运算仍定义为重复加法，如4P=P+P+P+P 快速倍点运算 kP 可采用类似于快速指数运算的相同算法 即令k=bt2t+bt-12t-1+…+b12+b0，则可写出2倍点和加法运算的迭代形式 Ep(a,b)是一个Abel群 对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，有单位元O，所以Ep(a,b)是一个Abel群

70 4.8.3 椭圆曲线上的点数 一条椭圆曲线Ep(a,b)（含无穷远点O)的总点数关系到运算群的规模，即建立的密码系统的安全性，有以下定理：
第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.3 椭圆曲线上的点数 一条椭圆曲线Ep(a,b)（含无穷远点O)的总点数关系到运算群的规模，即建立的密码系统的安全性，有以下定理： 定理4-13 GF(p)上的椭圆曲线y2＝x3+ax+b(a,bGF(p), 4a3+27b2(mod p)≠0)在第一象限中的整数点加无穷远点O共有 1+p = 1+p+个，其中 是Legendre符号 定理中的由以下定理给出 定理4-14(Hasse定理) |  |

71 4.8.4 明文消息到椭圆曲线上的嵌入 使用椭圆曲线构造密码体制前，需要将明文消息镶嵌到椭圆曲线上去，作为椭圆曲线上的点。
第四章 公钥密码：4.8 椭圆曲线密码体制 4.8.4 明文消息到椭圆曲线上的嵌入 使用椭圆曲线构造密码体制前，需要将明文消息镶嵌到椭圆曲线上去，作为椭圆曲线上的点。 设明文消息是m(0mM)，k是一个足够大的整数，使得将明文消息镶嵌到椭圆曲线上时，错误的概率是2-k 实际情况中，k可在3050之间取值。不妨设k＝30，对明文消息m，如下计算一系列x： x＝{mk+j,j=0,1,2,…}={30m,30m+1,30m+2,…}直到x3+ax+b(mod p)是平方剩余，即得到椭圆曲线上的点 (x, )。因为在0到p的整数中，有一半是模p的平方剩余，一半是模p的非平方剩余。所以k次找到x，使得x3+ax+b(mod p)是平方根的概率不小于1－2-k。 反之，为从椭圆曲线上的点(x,y)得到明文消息m，只须求m＝x/30

72 4.8.5 椭圆曲线上的密码 为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题
第四章 公钥密码：4.8 椭圆曲线密码体制 椭圆曲线上的密码 为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题 在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，QEp(a,b)，k<p，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。 Diffie-Hellman密钥交换和ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制

73 4.8.5 椭圆曲线上的密码 1. Diffie-Hellman密钥交换(GF(p)上的方案见5.2.3节)
第四章 公钥密码：4.8 椭圆曲线密码体制 椭圆曲线上的密码 1. Diffie-Hellman密钥交换(GF(p)上的方案见5.2.3节) 第1步：取一素数p≈2180和两个参数a、b，则得椭圆曲线上面的点及无穷远点构成Abel群Ep(a,b)，a，b应使群的阶n具有大素因子 第2步: 取Ep(a,b)的一个生成元G＝(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数 第3步: 两用户A和B之间的密钥交换如下进行： ① A随机选整数nA<n，保密nA，计算PA=nAG产生Ep(a,b)上的一点发给B ② B类似地选取秘密的nB并计算PB发给A ③ A、B分别由K=nAPB和K=nBPA产生出双方共享的秘密钥 这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA 攻击者若想获取K，则必须由PA和G求出nA，或由PB和G求出nB，即需要求椭圆曲线上的离散对数，因此是不可行的 如果将这一密钥用作单钥加密的会话密钥，则可简单地取其中的一个，如取x坐标，或取x坐标的某一简单函数。或计算hash值

74 4.8.5 椭圆曲线上的密码 2. 利用椭圆曲线实现ElGamal密码体制
第四章 公钥密码：4.8 椭圆曲线密码体制 椭圆曲线上的密码 2. 利用椭圆曲线实现ElGamal密码体制 首先选取一条椭圆曲线，并得Ep(a,b)，将明文消息m通过编码嵌入到曲线上得点Pm，再对点Pm做加密变换。如4.7.4 取Ep(a,b)的一个生成元G，Ep(a,b)和G作为公开参数。 用户A选nA作为秘密钥，并以PA=nAG作为公开钥 任一用户B若想向A发送消息Pm，可选取一随机正整数k，产生以下点对作为密文： Cm={kG，Pm+kPA}《存在密文扩展问题》 A解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点倍乘，即 (Pm+kPA)－nAkG=Pm+k(nAG)－nAkG =Pm 攻击者若想由Cm得到Pm，就必须知道k。而要得到k，只有通过椭圆曲线上的两个已知点G和kG，这意味着必须求椭圆曲线上的离散对数，因此不可行

75 第四章 公钥密码：4.8 椭圆曲线密码体制 椭圆曲线上的密码 3. 椭圆曲线密码体制的优点 与基于有限域上离散对数问题的公钥体制（如Diffie-Hellman密钥交换 和ElGamal密码体制）相比，椭圆曲线密码体制有如下优点: (1) 安全性高 攻击有限域上的离散对数问题可以用指数积分法，其运算复杂度为 O(exp )，其中p是模数（为素数）。而它对椭圆曲线 上的离散对数问题并不有效。 目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群 上离散对数问题的大步小步法，其运算复杂度为O(exp ) 其中pmax是椭圆曲线所形成的Abel群的阶的最大素因子。 如果p有大素因子q，且p＝2q＋1，则非常安全 因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体 制更安全

76 第四章 公钥密码：4.8 椭圆曲线密码体制 椭圆曲线上的密码 (2) 密钥量小 由攻击两者的算法复杂度可知，在实现相同的安全性能条件下，椭圆曲线密码体制所需的密钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小。 (3) 灵活性好 有限域GF(q)一定的情况下，其上的循环群（即GF(q)-{0}）就定了 GF(q)上的椭圆曲线可以通过改变曲线参数，得到不同的曲线，形成不同的循环群。因此，椭圆曲线具有丰富的群结构和多选择性 可在保持和RSA/DSA体制同样安全性能的前提下大大缩短密钥长度(目前160比特足以保证安全性)，因而在密码领域有着广阔的应用前景 表4-7给出了椭圆曲线密码体制和RSA/DSA体制所需的密钥的长度 RSA/DSA 512 768 1024 2048 21000 120000 ECC 106 132 160 211 600 1200 MIPS-年，(每秒百万条指令) 1012 1036 1078 10168

77 第四章 公钥密码：4.9 基于身份的密码体制 4.9.1 概述 1984年Shamir提出了一种基于身份的加密方案(简称IBE(identity-based encryption))的思想，并征询具体实现方案，方案中不使用任何证书，直接将用户的身份作为公钥，以此来简化公钥基础设施PKI(Public key infrastructure)中基于证书的密钥管理过程。 作为B的公钥来加密邮件即可。当bob收到后，他与一个第三方－密钥服务器联系，和向CA证明自己身份一样，B向服务器证明自己，并从服务器获得解密用的秘密密钥，再解密就可以阅读邮件 这种方法避免了公钥密码体制中公钥证书从生成、签发、存储、维护、更新、撤销这一复杂的生命周期过程

78 4.9.1 概述 自Shamir提出这种新思想后，由于没有找到有效的实现工具，其实现一直是一公开问题。
第四章 公钥密码：4.9 基于身份的密码体制 4.9.1 概述 自Shamir提出这种新思想后，由于没有找到有效的实现工具，其实现一直是一公开问题。 直到2001年，Dan Boneh和Matt Franklin获得了数学上的突破，提出了第一个实用的基于身份的公钥加密方案。 他们的方案使用椭圆曲线上的双线性映射(分别称为Weil配对和Tate配对)，将用户的身份映射为一对公开钥/秘密钥对 双线性映射是满足Pair(aX,bY)＝Pair(bX,aY)的映射Pair，其中a和b是整数，X和Y是椭圆曲线上的点。

79 4.9.2 双线性映射和双线性D-H假设 以Zq表示mod q加法下的群{0,1,…,q-1}，用Z+代表正整数集
第四章 公钥密码：4.9 基于身份的密码体制 4.9.2 双线性映射和双线性D-H假设 以Zq表示mod q加法下的群{0,1,…,q-1}，用Z+代表正整数集 对于阶为素数的群G，用G*代表集合G－{O}，O为G中的单位元 1.双线性映射 设q是一大素数，G1和G2是两个阶为q的群，其上的运算分别称为加法和乘法。G1到G2的双线性映射e:G1×G1→G2，满足下面的性质： ①双线性：如果对任意P,Q,RG1和a,bZ，有e(aP,bQ)=e(P,Q)ab，或e(P+Q,R)=e(P,R)•e(Q,R) 和e(P,Q+R)=e(P,Q)•e(P,R)，那么就称该映射为双线性映射 ②非退化性：映射不把G1×G1中的所有元素对(即序偶)映射到G2中的单位元。由于G1，G2都是阶为素数的群，这意味着，如果P是G1的生成元，那么e(P,P) 就是G2中的生成元 ③可计算性：对任意的P,QG1，存在一个有效算法计算e(P,Q)。 Tate配对、 Weil配对、Ate配对是满足上述3条性质的双线性映射

80 第四章 公钥密码：4.9 基于身份的密码体制 4.9.2 双线性映射和双线性D-H假设 2. MOV 规约 G1中的离散对数问题是指已知P,QG1 ，求αZq，使得Q=αP。已知这是一个困难问题 然而如果记g＝e(P,P)，h＝e(Q,P)，则由e的双线性可知h＝gα，因此可以将G1中的离散对数问题归结为G2中的离散对数问题，若G2中的离散对数问题可解，则G1中的离散对数问题可解。 MOV规约(也称MOV攻击)是指将攻击G1中的离散对数问题转变为攻击G2中的离散对数问题。所以要使G1中的离散对数问题为困难问题，那么必须选择适当参数使G2中的离散对数问题为困难问题

81 4.9.2 双线性映射和双线性D-H假设 3. DDH问题 由双线性映射的性质可知： 4.CDH问题
第四章 公钥密码：4.9 基于身份的密码体制 4.9.2 双线性映射和双线性D-H假设 3. DDH问题 G1中的判定性Diffie－Hellman问题简称DDH(decision Diffie－Hellman)问题，是指已知P,aP,bP,cP，判定c＝ab mod q是否成立，其中P是G1*中的随机元素，a,b,c是Zq*中的随机数。 由双线性映射的性质可知： c＝ab mod qe(P,cP)＝e(aP,bP) 因此可将判定c＝ab mod q是否成立转变为判定e(P,cP)＝e(aP,bP)是否成立，所以G1中的DDH问题是简单的。ECC群上的DDH问题简单 4.CDH问题 G1中的计算性Diffie－Hellman问题简称CDH(computational Diffie－Hellman)问题，是指已知P,aP,bP，求abP，其中P是G1*中的随机元素，a,b是Zq*中的随机数。 与G1中的DDH问题不同， G1中的CDH问题不因引入双线性映射而解决，因此它仍是困难问题

82 4.9.2 双线性映射和双线性D-H假设 5. BDH问题和BDH假设
第四章 公钥密码：4.9 基于身份的密码体制 4.9.2 双线性映射和双线性D-H假设 5. BDH问题和BDH假设 由于G1中的DDH问题简单，那么就不能用它来构造G1中的密码体制。IBE体制的安全性是基于CDH问题的一种变形，称为双线性DH假设。 双线性DH问题简称为BDH(bilinear Diffie－Hellman)问题，是指给定(P,aP,bP,cP)(a,b,cZq*)中，计算w＝e(P,P)abcG2，其中e是一个双线性映射，P是G1的生成元，G1,G2是阶为q的两个群，设算法A用来解决BDH问题，其优势定义为τ，如果 Pr|A(P,aP,bP,cP)=e(P,P)abc |≥τ 目前还没有有效的算法解决BDH问题，因此可假设BDH问题是一困难问题，这就是BDH假设

83 第四章 公钥密码：4.9 基于身份的密码体制 4.9.3 IBE方案描述 令k是安全参数，g是BDH参数生成算法，其输出包括素数q，两个阶为q的群G1,G2，一个双线性映射e:G1×G1→G2的描述。k用来确定q的大小，例如可以取q为k比特长。 (1)初始化 给定安全参数kZ+，算法运行如下： ①输入k后运行g，产生素数q，两个阶为q的群G1,G2，一个双线性映射e:G1×G1→G2，选择一个随机生成元PG1 ②随机选取一个sZq*，Ppub＝sP ③选取一杂凑函数H1:{0,1}*→G1*，对某个n，再选一个杂凑函数H2 :G2→{0,1}n，安全分析时则把H1,H2视为随机预言机 消息空间为M＝{0,1}n，密文空间为C=G1*×{0,1}n 。系统参数为params＝<q,G1,G2,e,n,P,Ppub,H1,H2 >，是公开的。s为主密钥，是保密的

84 4.9.3 IBE方案描述 这个方案在选择明文攻击CCA下并不安全，需要修改 (2)加密 (3) 密钥产生 (4)解密
第四章 公钥密码：4.9 基于身份的密码体制 4.9.3 IBE方案描述 (2)加密 用接收方的身份ID作为公钥,加密消息MM，有三步: ①计算QID=H1(ID)G1* ②选择一个随机数rZq* ③确定密文C＝<rP,MH2(grID)>，这里gID＝e(QID,Ppub)G2*, (3) 密钥产生 对于一个给定的比特串ID{0,1}*,首先计算QID=H1(ID)G1*，然后确定秘密密钥dID= sQID,其中s为主密钥。 (4)解密 设密文为C=<U,V> C，用秘密钥dID计算VH2(e(dID,U))＝M 这是因为e(dID,U)＝e(sQID,rP)＝e(QID,P)sr＝e(QID,Ppub)r＝grID 这个方案在选择明文攻击CCA下并不安全，需要修改

85 第四章 公钥密码：4.10 公钥密码体制的可证明安全性
公钥体制的安全性定义 为了设计出安全的公钥密码体制，需要对公钥体制的安全性进行形式化 的定义，给出精确的度量，然后设计出能够证明满足所定义安全性的密 码算法，才是有安全性保障的算法。 公钥密码体制按照可能的攻击目标，可以分为： 单向性、不可区分性、语义安全性、不可展性、明文可意识性 1. 单向性OW(One-Way)：由密文不能直接恢复明文 单向性在公钥密码中是最基本的概念，对于公钥密码算法而言，陷 门单向置换OWPT更为重要，是构建公钥密码算法的最基础本原。 前面的各种基本公钥密码算法中都是基于OWPT而构建的 但由签名各类算法中所述的攻击问题可知，仅仅依靠OWPT是不能 实现安全的，我们需要在OWPT的基础上给出一些更强的安全性定 义

86 4.10.1 公钥体制的安全性定义 2. 不可区分性IND( indistinguishability)
第四章 公钥密码：4.10 公钥密码体制的可证明安全性 公钥体制的安全性定义 2. 不可区分性IND( indistinguishability) 对已知给定的两个明文m0，m1(可以是敌手选的)，加密者随机一致的选择其 中一个进行加密，攻击者无法从密文中知道是对哪个明文的加密。也就是说， 从密文中无法获得明文1bit的信息 敌手不能以明显大于1/ 2 的概率正确猜测选择的是哪一个明文 攻击算法的优势可定义为参数k的函数： Adv,A(k)=|Pr[b＝b]－1/2| 对应于现代公钥密码算法多数，这个安全性概念可以成为加密的多项式 不可区分性，或者更为精确的表述是多项式不可区分选择明文攻击的安 全性，这时因为，攻击者选择的两条明文之间的不可区分性 不可区分性实际上几乎等价于另一个概念：语义安全性

87 4.10.1 公钥体制的安全性定义 3. 语义安全性SEM ( semantic security) ：
第四章 公钥密码：4.10 公钥密码体制的可证明安全性 公钥体制的安全性定义 3. 语义安全性SEM ( semantic security) ： 敌手在知道密文的条件下能有效计算出的有关明文的信息量，除了明文的长度，并不比它不知道密文时的多 在一定条件下，不可区分性和语义安全性是等价的。 如果不存在多项式时间的攻击算法A，以不可忽略的优势攻击获得成功，那么就称此方案是语义安全的。 4. 非延展性（NM）安全：攻击者无法以不可忽略的概率构造与已给密文相关的新密文，使得它们相应的明文有一定的联系 以上安全性概念依次加强：NM比IND强，IND比OW强 5. 明文可意识性(PA) 　敌手不能以一个不可忽略的概率,在不知道相应明文的情况下,构造一个密文

88 4.10.2 公钥体制的攻击模型 按照可能的攻击模型可分为：
第四章 公钥密码：4.10 公钥密码体制的可证明安全性 公钥体制的攻击模型 前述的几种安全性定义都是在一定的攻击背景下给出的。比如IND-CPA安全(有时直接用语义安全称呼)中，敌手获得加密机的帮助，可以选择两个明文m0, m1 敌手如果进一步获得解密机的帮助，可以有效的选择密文攻击，则这些安全性未必可靠。因此有必要对攻击的模型做一个定义 按照可能的攻击模型可分为： 选择明文（CPA）攻击：攻击者可以先适应性选择明文，获得相应的密文（公钥体制中加密密钥Pk是公开的），比如IND-CPA 非适应性选择密文（CCA1）攻击：攻击者除了可以适应性选择明文攻击外，在给定Challenge密文(要破译的密文)前，还可以选择密文获得相应的解密（可询问解密预言机）。 也称“午餐攻击”，攻击者在其他员工不在的情况下(比如午餐时间)询问该机构中的解密机，从而获得密码分析的经验或信息 在询问应答等机制中都可能实现这种攻击

89 第四章 公钥密码：4.10 公钥密码体制的可证明安全性
公钥体制的攻击模型 适应性选择密文（CCA2）攻击：攻击者的唯一限制就是不可以直接用Challenge密文获得相应的明文，即还可以在给定Challenge密文后，选择密文获得相应的解密。 也称“凌晨攻击”，攻击者可以在午餐攻击前后都永远可得到解密机的帮助，除了要破译的密文。攻击者作为员工可以熬通宵使用解密机而不被注意，这时有足够的时间以更有意义的方式使用解密机，即利用从午餐攻击中得到的信息以及接下来得到的相应的询问密文，适应性地选择明文提问，得到询问密文后仍然可以适应性选择密文，这在某种程度与询问密文相关，因为其对应明文是他自己选择的。 同时考虑攻击目标和攻击模型，可以获得不同的安全，其中最重要的是IND-CCA2和NM-CCA2安全（它们的安全性是最强的），而二者被证明是等价的，所以加密中通常所说的选择密文安全是指IND-CCA2安全(即适应性选择密文攻击下不可区分性安全)。 其中挑战密文Challenge是指攻击者要攻击的那个密文，即真正要解密的对象

90 4.10.3 随机预言机模型下可证明安全的体制 目前可证明安全体制的标准是能够抗IND-CCA2的体制
第四章 公钥密码：4.10 公钥密码体制的可证明安全性 随机预言机模型下可证明安全的体制 目前可证明安全体制的标准是能够抗IND-CCA2的体制 实际有效的体制使用消息完整性检验机制加强基本公钥算法来实现，这样使得攻击者通过修改密文来以一种可控的方式修改明文会有极大的困难 另一个很重要的方法叫明文随机化，如果输入明文分布随机，那么该函数就为隐藏明文信息提供了一个强保护，甚至是单比特级，比如概率加密体制。 那么将明文进行填充进行完整性验证，并且在填充中有一个随机输入值，这样的随机填充与OWPT进行组合可以得到强的安全算法。填充中往往需要使用杂凑函数hash，如RSA-OAEP 有一类可证明安全的公钥密码体制的构造，其形式化的安全性证明基于一个非常有效的技术，随机预言机 Random Ocracle Model简称ROM.

91 4.10.3 随机预言机模型下可证明安全的体制 该模型下的经典方案是RSA-OAEP，
第四章 公钥密码：4.10 公钥密码体制的可证明安全性 随机预言机模型下可证明安全的体制 在ROM模型中密码体制安全性的证明是在假设所使用的杂凑函数是性能完全和随机函数一样，这种随机函数是在确定的输入下，其输出是均匀随机的 杂凑函数有一个性质”对任一输入，其输出对概率分布与均匀分布在计算上是不可区分的”。若这一性质改为”对任一输入，其输出是均匀分布的”，这样的杂凑函数是理想的。若把杂凑函数看作这样一个假想的理想函数，就称为随机预言(Random oracle) 该模型下的经典方案是RSA-OAEP， 被国际工业标准组织接受为RSA加密标准，PKCS#1，IEEE P1363 随机预言机假设有理想的随机函数存在，而对于实用方案则以hash函数来替代该随机函数，这可能使实际方案达不到可证明安全，因为hash函数的输出并不是随机的，只是计算上不可预测的，但这种思想设计出的方案实用性强 在随机预言机模型中最强的安全性是明文可意识性PA

92 第四章 公钥密码：4.10 公钥密码体制的可证明安全性
标准模型下可证明安全的体制 著名的Cramer-Shoup公钥密码体制也是一个再标准模型下可证明 安全的体制，满足IND-CCA2安全 可证明安全性的证明思路是所谓规约 即将对密码方案所谓的攻击“规约”到一个著名的困难问题(密码原型)的解 (即利用所谓攻击成功者，把它当做一个黑盒，解决著名的困难问题)。 如果对于公钥密码体制，安全性的形式化证明只依赖于所基于的OWTP的困 难性，那么该证明就称为是在标准困难性假设下的证明，称为标准模型， Standard Model Cramer-Shoup体制 假设G是一个具有大素数阶q的Abel群，明文空间是G 密钥产生： 选择两个随机元g1,g2,UG; 选择五个随机数x1，x2，y1，y2，z U[0,q) 计算c=g1x1g2x2， d=g1y1g2y2， h=g1z， 选择一个密码学杂凑函数H:G3->[0,q) 公钥：(g1,g2,c,d,h,H)；私钥(x1，x2，y1，y2，z )

93 4.10.4 标准模型下可证明安全的体制 加密 对于明文消息m，发送者Bob选择一个随机数r U[0,q)，并计算
第四章 公钥密码：4.10 公钥密码体制的可证明安全性 标准模型下可证明安全的体制 加密 对于明文消息m，发送者Bob选择一个随机数r U[0,q)，并计算 u1=g1r， u2=g2r ，e=hrm，=H(u1, u2,e),v=erdr 密文是(u1, u2,e,v) 解密 1. 计算=H(u1, u2,e)； 2. 验证u1x1+y1 + u2x2+y2 =v，若不成立则拒绝该密文，否则计算明文 m=e/u1z 该方案中的典型特征是明文m参与了验证 在该方案中，hash函数只假设其为单向的，而不是输出随机的 标准模型仅假设hash函数的单向性和无碰撞性，因而更为合理，但所设计出来的方案一般比较复杂

94 4.10.5 可证明安全的混合密码体制 实际上就是一种数字信封技术 对于长消息加密非常重要
第四章 公钥密码：4.10 公钥密码体制的可证明安全性 可证明安全的混合密码体制 实际上就是一种数字信封技术 对于长消息加密非常重要 混合体制输出的密文包括两个部分：密钥封装机制(KEM)和数据封装机制(DEM) 即KEM||DEM=Epkasym(k)||Eksym(m) 收到这个密文对后，接收者用其私钥解密KEM块得到会话密钥k，然后用k解密DEM块，恢复消息m 如果KEM是一个可证明IND-CCA2安全的非对称加密方案的输出，那么DEM块的IND特性就是短暂密钥随机性的自然结果。显然KEM-DEM结构的混合体制是IND-CCA2安全的，也是构造IND-CCA2安全体制的实际有效的公钥加密的最自然方法 前述的可证明安全的公钥方案可以作为混合加密体制中的KEM模块

95 作业： 复习题中的作业：4.16、5.3 作业题目修正 编程作业
p131：4，10，11，12，13，14，15，16，17，18，19，20 复习题中的作业：4.16、5.3 作业题目修正 第13题中k=2改为k＝3，因为要求gcd(k,p-1)=1 第17题p＝53改为47，因为要求p为blum数 编程作业 编写一个模长为32bit的RSA加解密算法，即寻找两个16bit的素数，以e=5为公钥，计算相应的私钥，并对消息abc(ASCII码表示)用基本的RSA算法加密，并进行解密

96 谢谢！