斯坦福大学密码学-基于陷门置换的公钥加密 11

昨天事情有点多，没有看完，今天争取看完！！！！！！

ppt链接：

公钥加密机制：定义与安全

公钥加密。

注意：公钥和私钥都是由Bob生成的。

应用。

公钥加密用来会话建立。用于建立起一个浏览器与网络服务器之间的安全密钥。

公钥加密对非互动的应用也很实用。

定义。

注意：G在现实中有一个参数，叫安全参数，指定了这个密钥生成算法将要生成的密钥大小。

安全性：对抗窃听。

与对称密码的窃听攻击对比。

在公钥加密中，不必赋予攻击者请求加密他选择明文的能力。因为他有公钥，他可以加密任何消息。

对抗主动攻击的安全性。

公钥加密的选择密文攻击安全性定义。

赋予给了攻击者比上一个举例更多的能力，举例中攻击者只能解密以 "to:attacker" 开头的密文，现在攻击者可以解密除了挑战密文以外的任何密文。

如果攻击者可以改变邮件的接收者，那么可以以优势1得到b的值，赢得游戏。

构建公钥加密

陷门函数。

陷门函数的安全性。

陷门函数是安全的，攻击者求出在点Y的逆的概率是可以忽略的，这点对所有有效函数都成立。

可以很容易正向计算F函数，但是没有人可以反向计算这个函数，除非他们有陷门私钥sk。

从陷门函数构造公钥加密。

陷门函数只用于加密一个随机值x，而实际的明文信息是使用对称系统加密的。

CCA上的ro表示安全性是建立在随机神谕(oracle)模型上的。

陷门函数是安全的陷门函数，对称加密是安全的，能抵抗篡改，所以提供了认证加密，H是某种意义上讲是个好哈希函数，是一个随机函数（SHA-256），那么我们构建的系统就是CCA安全的。

不能直接使用TDF进行构建公钥加密系统！！！

RSA陷门置换

陷门置换。

合数模。

事实上几乎所有 Z_N 中的元素都是可逆的。

广泛应用。

RSA陷门置换的构造。

RSA假设。

RSA公钥加密。

教科书RSA是错误的。

它是一个确定性加密，不具备语义安全。

注意：RSA只是一个陷门置换，不是一个加密机制。

教科书RSA加密的中间相遇攻击。

公钥密码学一号标准 PKCS1

实际中，系统生成一个对称加密密钥，然后用RSA去加密这个给定的对称加密密钥。

PKCS mode2。

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

注意：随机数中不含有FF。

PKCS1 攻击。

假设了一个简单的攻击。

注意：乘2相当于左移1位。这样就可以获得密文x的第二位，第三位。。。。。。

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

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

HTTPS防御办法。

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

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

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

另一种使用RSA加密的方法，优化非对称加密补齐OAEP。

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

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

只有假设RSA函数是陷门函数，才是一个安全的陷门函数。使用RSA加密是CCA安全的话，我们还必须假设函数H和G是某种理想的哈希函数才行。

只有一个普通的陷门置换，正确的使用OAEP：

1.OAEP+, 填充不是固定的010000，而是m和r的哈希值，这种方案是CCA安全的。

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

加密中的补齐检查在我们看到过的所有机制中都是很重要的，比如 OAEP+ 和 SAEP+。在OAEP中，检查补齐值，补齐值为0100...000，如果不是的话，就输出 \perp ,说明密文无效。

实现OAEP是困难的，存在计时攻击。不要自己实现。

RSA真的是一个单向函数吗？

为了计算模N的e次方根，我们真的一定要分解N吗？存在一条捷径，不需要分解N就可以计算出模N的e次方根。

为了证明这是不可能的，必须证明一个归约。也就是说必须证明，如果给大家一个有效算法，可以计算模N的e次方根，那么这个算法也可以被改造成一个计算因子分解的算法，这叫做一个归约。这证明任何人以比分解模更快的速度计算模N的e次方根。

对任意 Z_N 中的 x，这个算法可以计算出 x 的模N的立方根，使用这个算法，可以分解模N吗？这个不清楚。

但是计算模 N 平方根的算法，蕴含着分解模的算法。计算平方根与分解模一样困难。但是，偶数不能被拿来当作RSA的指数。

真正合法的最小的RSA指数等于3。这是一个公开问题。

提高RSA的性能？计算明文就是计算c的d次方，指数算法的时间与 log(d) 成线性。用一个小d。

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

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

Michael wiener攻击有个扩展，即使d小于N的0.292次方，那么RSA也是不安全的。

任何人都不应该在d上强加任何结构以期提高RSA性能。

Michael wiener攻击。

目标：(N,e) \Rightarrow d\ \ \ d< \sqrt[4]{N}/3 3不重要，起主要作用的项，d小于N的4次方根。

注意：1/\varphi(N) 是在 1/N 数量级的。 1/\varphi(N) 远远小于 1/\sqrt{N} 。

对于 d< \sqrt[4]{N}/3 ，两边平方后再取倒数再乘0.5。

连分式算法从分式e/N开始，他会还原log(N)个可能的k/d的值，我们只需要一个一个去试，使得 |\frac{e}{N}-\frac{k}{d}|\leq \frac{1}{2d^2}，直到我们找到正确的k/d，因为 gcd(d,k)=1，分母一定是d。

RSA应用

加速RSA，选择小点的e，推荐使用65537，重复平方法加密只要17次乘法。 标准的RSA解密，RSA-CRT让RSA解密速度加速4倍。但是平均来看，RSA加解密速度比为1：30。

密钥长度。

针对RSA的攻击。计时攻击，功耗分析攻击，错误攻击。

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

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

很多密码学库都会在返回结果给调用者之前，检查RSA解密的结果。引进了10%的开销。

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的私钥了。

教训。

不要在机器刚刚启动时就生成密钥，必须确保发生器的取种需要充分的时间获得足够的熵，然后才能开始生成密钥。

文献推荐。