Dan Boneh密码学笔记11

11.Public Key Encryption from trapdoor permutations

1.Public key encryption: definitions and security

2.Constructions

3.The RSA trapdoor permutation

4.PKCS 1

5.Is RSA a one-way function?

6.RSA in practice

1.Public key encryption: definitions and security

加密用对方的公钥，对方解密用他的私钥

应用：仅针对窃听安全的密钥交换协议

x是共享密钥

公钥加密在非互动应用中非常有用。

Bob用Alice的公钥加密电子邮件后发送给Alice。

公钥加密用于建立会话。

非对称密码与对称密码的窃听安全定义的关系

对称密码中，分为一次加密和多次加密情况，安全性是不同的。

非对称加密中，只要一次加密是安全的，则多次加密也是安全的。

公私钥对天生就是用来加密多个信息的。

现在看看更强大的攻击者，主动攻击。

发送方会通过SSL把邮件加密后发给Gmail服务器，Gmail服务器会中断SSL连接，然后把邮件转发给合适的接收方。假设这份邮件是使用计数器模式加密的（篡改CBC的IV导致重定向）或类似的。，然后当攻击者截获了这个邮件，他可以改变接收方。Gmail服务器收到邮件后会转发给攻击者。

我们的目标是设计安全的公钥系统，即使攻击者可以篡改密文还可以解密特定的密文

有这么一个限制，攻击者可以提交任何他选择的密文，除了挑战密文。

攻击者可以询问他选择的任何密文的解密，除了挑战密文。即使攻击者获得素有的解密，他依然不能分辨出他得到的是m0还是m1的加密。这是一个非常保守的定义。攻击者的目标是判断挑战密文是m0还是m1的加密。

攻击者干了这么多，无法判断挑战密文是m0还是m1的加密。这个系统就是选择密文安全（CCA）的。

前面我们看过的电子邮件的例子的特点，假设选定的加密系统满足给定信息的的加密，攻击者可以改变接收方从to Alice 改成to Charlie。

那么我们可以这样赢得CCA游戏，攻击思路如下：

第一步攻击者得到了公钥，攻击者会发出两个等长度的明文，第一个明文body是0，第二个明文body是1。两个明文都给Alice。Alice回复后，攻击者会得到挑战密文c。现在攻击者会使用他的能力去修改接收方，他会返回给Alice一个密文c'。c'是to Charlie的明文加密结果，其body是挑战密文c记为b。现在因为明文不同，密文也不同，所以c'一定和挑战密文c不一样。因此，挑战者现在必须解密，根据CCA游戏的定义，挑战者必须解密任何不同于挑战密文的密文。 那么挑战者解密了，给攻击者解密结果m'，他给了攻击者b，现在攻击者可以输出挑战结果b了。他以优势1赢得了这个游戏。

因为攻击者能够改变挑战密文从一个接收方改到另一个，使得他能以优势1赢下这个CCA游戏。

2.Constructions

构建CCA安全的系统

陷门置换trapdoor permutation

使用公钥pk计算这个函数在任意点的值，使用私钥sk计算函数的逆

安全的陷门函数

单向函数，这个函数可以在任一点计算，但求它的逆是困难的

简单说，非常容易地从正向计算这个函数，但没人能从反方向计算这个函数。除非他们有这个陷门私钥sk

对称加密系统取K中的密钥，陷门函数取X中的元素作为输入

哈希函数H，从X映射到K，也就是把集合X中的元素映射成密钥用于对称加密系统。开始构建公钥加密系统

陷门函数F只用于随机值x，信息是用对称密钥系统加密的。

ro表示CCA安全性。

这个方案是CCA安全的。

ISO标准定义了这种公钥加密模式

一种错误使用陷门函数来构建的公钥加密系统

为什么不要用陷门函数直接加密信息？是完全不安全的。

这里没有随机性被使用到，不可能是语义安全的。

永远不要这么做！

3.The RSA trapdoor permutation

一个经典的陷门函数叫做RSA

φ(N)其实和N很接近

意味着，如果我们选取模N中的随机元素，非常有可能这个元素也在Z_N*中。

非常不可能选择一个Z_N中的随机元素得到的元素却是不可逆的。

几乎所有的Z_N中的元素都是可逆的

e加密指数，d解密指数

对教科书式RSA 的攻击

服务器私钥为(N,d)，公钥为(e,N)

浏览器生成随机数叫做预备主密钥K，用RSA直接加密K

双方都有了共享密钥

用RSA直接加密K ，攻击者看到的密文c=k^e in Zn

假设K的一个64位密钥，k是0到2^64-1的一个整数

首先，假设k正好能分解成几个差不多大小的数的乘积，写成k=k1·k2

K1和k2都小于2^34，这有20%的概率会发生，把这个k带入到定义密文的函数值，把k替换成k1·k2，k1移到另一边，得到这个灰色的方程

攻击者知道c、e、N，利用灰色方程进行中间相遇攻击

一旦找到合适的k1和k2，可以很容易地还原k

Step1构建一张表存放左边所有的的可能值

Step2检查右边的这个值是否在第一步构建的表里

暴力破解需要2^64次，这里只要2^34次做第一步。

因为要指数运算，所以整个破解用时2^40次

永远不要直接用RSA加密，必须通过一个加密机制，比如ISO标准

4.PKCS 1

公钥密码学一号标准

实际中，系统生成一个对称加密密钥，然后让RSA去加密这个给定的对称加密密钥，而不是生成对称密钥作为RSA加密的一部分。

实际中，RSA系统有一个输入的对称密钥需要加密。

例如，可能是个AES密钥128位，然后这个密钥被加密。把这128位扩展成整个模的大小，例如模是2048位的。然后应用RSA函数。

如何进行这样的预处理呢？把128扩展成2048再RSA

如何论证得到的系统是安全的呢？

广泛应用PKCS1.5

模式2 表示加密，模式1 表示签名

PKCS1模式2：

取明文比如128位的AES密钥，放在要产生的值的最低128位，接下来在它后面附上16个1，即16进制的FF，然后接下来把它附在这个随机密码本的后面，这个密码本中任何地方都不含FF，这个密码本类似于1900位随机数，但是不含FF。最后在结果的最高位放上02，表示这个明文已经被PKCS1模式2编码了。这就是整个2048位的字符串。作为RSA的输入。

解密的时候，识别02，移除掉前面的密码本直到遇到FF。

这个机制应用非常广泛，比如HTTPS

当PKCS1使用在HTTPS中时，攻击思路

假设攻击者截获了PKCS1的密文

服务器检查密文的前两个字节是不是02。不是就error

攻击者可以测试任意密文的逆是否以02开头，这足以完全解密攻击者想解密的任何密文。

攻击者选择一个随机值r，构建一个新密文c'也就是r^e·c mod N

如果我们把r带入RSA函数，我们只是与RSA明文相乘，PKCS1封装的明文m乘以r，计算整项的e次方。

询问r·x的开头是否是02，数百万次，就可以还原x的全部了。

为什么呢？

举个例子叫做baby bleichenbacher

设想攻击者可以发送密文c，网页服务器会用私钥解密，假设服务器不检查开头是否是02，而是看最高位是否是1. 如果是1，服务器说yes。不是1 返回no。进一步简化，假设RSA的模N是2的某次幂。

现在，通过给服务器发送密文c，攻击者只是学习明文x的最高位。

服务器完全泄露了最高位yes、no。

现在攻击者可以把密文乘以2^e。就有去乘明文x的效果。2x。因为我们是在2的n次方模下的。乘2就意味着左移。

学到2x的最高位，就等于学到了x的次高位。

重复这一步，大约一两千次，就还原了x

需要询问上百万次是因为攻击者要询问开头是否是02.

如何抵抗这一攻击？RFC尽力改动最小。

用RSA解密后，你会获得一个并不是PKCS1编码的明文也就是说不是02开头的。你可以选取某个随机字符串r，只假定明文是一个随机字符串r，当什么也没发生。当然稍后协议会失败。

也就是说，如果PKCS1编码失败 ，你会说预备主密钥是这个随机字符串，我们继续协议，然后建立会话失败。导致会话终止。

不告诉攻击者开头是否是02，只是假定明文是某个随机值

用一种不同的方法来进行使用RSA的加密，即所谓的优化非对称加密补齐OAEP。

OAEP是更好的使用RSA加密的方法。

128位的AES，再附上01，然后再加一组0，然后也选择一个随机值，使得整个字符串与你的RSA模一样大比如说2047位。

在你应用RSA函数之前，首先选取你选的随机数把它交给哈希函数。

这个哈希函数产生一个值与你编码的左边一样大。把输出求异或。把得到的结果交给另一个哈希函数G。用一个随机值去异或，最后得到两个值。联结起来得到2047位长的字符串。

后来有人证明了事实上如果只假设RSA函数是陷门函数，是一个安全的陷门函数。使用RSA加密是CCA安全的话，我们还必须假设函数H和G是某种理想的哈希函数才行。这些叫做随机神谕。假设H和G 是随机函数。

在实际中，实现OAEP时，对于H和G，人们就使用SHA-256

为什么要叫做优化非对称加密补齐呢？Optimalasymmetric encryption padding

为什么要说优化呢？

如果你看密文，会注意到其密文是尽可能短的。密文与RSA输出一样长。

在ISO标准中，加密非常短的明文，必须使用RSA加密x，在x后面附上使用对称加密系统加密的短消息，即使你必须加密128位AES密钥，根据ISO标准，你会获得一个RSA输出加上一段对称密码。而在OAEP中，只获得了一个RSA输出，没有其他东西。

所以密文长度是优化的。

这个定理依赖于RSA的性质，事实上，如果你使用一个普通的陷门置换，那么这个定理不成立。其他的置换未必具备RSA的代数性质。

如果只有一个普通的陷门置换，如何正确的使用OAEP呢？

OAEP+, padding不是固定的010000

而是m和r的哈希值，这种方案是CCA安全的

SAEP+,当RSA的公钥指数等于3时，实际上不需要第二阶段的加密工作G

如何解密SAEP的密文ct。

先RSA逆得到x和r

最后我们要确保补齐w(m,r)是正确的。

如果是，输出m，不是，输出无效

检查补齐是否正确是很重要的

实际上，实现OAEP可能是很困难的。这对计时攻击来说是脆弱的。

5.Is RSA a one-way function?

在不知道陷门的情况下，求RSA的逆真的有这么难 吗？

如果可以分解模，使用中国剩余定理可解。

但是分解模是非常困难的问题。

一定要分解模N吗？

规约reduction，有一个计算模N的e次方根的算法，我们就能获得一个分解合数的算法。任何人都不能计算模N的e次方根以比分解模更快的速度

Φ(N)是偶数，e、d与φ(N)互质，e=2偶数不能拿来当作RSA指数，真正合法的最小的RSA指数等于3

如果我给你一个有效算法来计算模N的立方根，你能使用这个算法来分解模N吗？

提高RSA加解密的性能，用一个小的d

正常情况下，d约与模一般大，比如2000位，通过使用仅为128位的d，我可以提高RSA解密速度20倍。这是个非常糟糕的点子。

Michael wiener有个攻击，一旦私钥指数d小于模的4次方，如果模大约是2048位，这意味着如果d小于2的512次方，那么RSA是完全不安全的。

给定一个公钥e，可以很快地还原出私钥d。

所以有传言说，这个攻击可以针对最多512位，那么为什么不让这个模，比如530位，那么这个攻击就不能用了。但我们依然可以加速RSA解密4倍，因为我们把指数从2000位降到比如说530位。事实上还是不安全的。

wiener攻击有个扩展，如果d小于N^0.292，那么RSA也是不安全的。

即使d大约为N^0.4999，RSA依然是不安全的。

这不是正确的提高RSA性能的方法。

Wkener攻击的细节

我们有（N,e）目标是还原私钥指数d

d是小于N的四次方根的

两边同时除以d·φ(N)

加上绝对值

φ(N)与N非常接近

我们只需要这个分式小于1/根号N

我们知道e，不知道φ(N)，所以不知道e/φ(N)

e/φ(N)与e/N 接近

p和q大约是N长度的一半

两边平方后再取倒数再乘0.5

中间那块红色，根据三角不等式推出，是绝对值的性质

满足这个条件的分式最多也只有log(N)个

这是一个著名的连分式算法continued fraction algorithm，它从分式e/N开始，他会还原log(N)个可能的k/d的值，我们只需要一个一个去试，直到我们找到正确的k/d，分母一定是d

如果私钥太小，小于N的四次方根的话，我们就可以轻松地完全还原d

6.RSA in practice

加速RSA，可以选择小点的e，推荐值，使用重复平方法，加密只要17次乘法。

标准的RSA解密，RSA-CRT，带中国剩余的RSA，这个方法让RSA解密速度加速4倍

如果使用128位的AES加密，应该使用一个3000位的模，尽管大家都用2048位模

一些针对RSA的攻击，数学上成功实现。但是这些实现对特定的侧信道攻击是脆弱的。

计时攻击、功耗分析攻击，错误攻击。

RSA解密时发生了某个错误，一个错误将完全泄露密钥。

许多密码学库都会检查RSA解密的结果在返回结果给调用者之前。

检查方法是取这个指数的输出，计算它的e次方，检查是否又回到了c mod N。如果是这样，说明这个解密是正确的。e比d小很多，所以这么做。这依然引入一个10%的开销。

展示一个这些攻击的例子

错误攻击，针对带中国剩余定理的RSA的

假设计算一个质数模q的时候发生错误，另一个模p没有发生错误

组合这两个结果后，会得到一个输出x'。

p能整除这个量，q不能

我们一旦获得N的因子分解，就可以计算φ(N)了，就可以自己根据公钥计算解密指数了，还原了私钥

另一种针对RSA的攻击，RSA密钥生成算法是有问题的。当它的熵不够时，（熵不够意味着随机性不强）这里会发生错误。

OpenSSL生成RSA密钥的方法如下：

先给这个伪随机数发生器以种子，然后他使用了伪随机数发生器生成的随机字符串来生成第一个质数p，他还会继续给伪随机数发生器种子，然后从伪随机数发生器生成q。最后输出p和q的乘积。

假设密钥生成正好是在防火墙启动后，prng还没有多少熵，防火墙很可能生成的质数p来自于一个低熵的集合，这意味着p的可能取值不多。在我们生成了p之后，生成质数实际上花了不少时间，几毫秒。防火墙生成的密钥会有更多熵，q来自高熵的集合。

现在的问题是，许多不同的防火墙，如果他们生成一个RSA密钥，他们中的许多最后会使用同样的质数p，但q不同。

如果我们看两个不同防火墙上的两个RSA模N1，N2，如果我们计算N1和N2的gcd，他们有着不同的q，但是p是一样的。所以如果我们计算gcd，会得到一个N的因子分解，还包括N1和N2，然后我们可以解出N1，N2的私钥了。

计算大量的公钥对N1和N2的gcd，发现了很多这些密钥都有公因子，就可以分解这些模了

许多网页服务器公钥都是脆弱的，只是因为它们使用了低熵的RSA密钥

生成密钥时，重要的是你的发生器的种子是合理选取的，不要在机器刚刚启动时就生成密钥。

第一篇，选择密文安全对公钥密码是如此重要，除了bleichenbacher攻击，还有许多其他攻击

第二篇，survey综述，讨论了许多RSA系统上的不同的攻击

第三篇，OAEP

第四篇，对RSA和其他公钥系统的密钥长度分析，为你的公钥系统选取合适密钥长度。即使你是在使用对称密钥系统。

补充。中国剩余定理CRT