9 非对称加密

9.1 概述

目前为止，本书中只讨论到对称加密。假设一个密码系统不只有一个密钥，而是有一对密钥，其中公钥可以自由地发布，而私钥由自己保管。其他人可以使用你的公钥来加密数据，这个信息只有你的私钥可以解密，这个被称为公钥加密（public-key encryption）

很长一段时间，这都被认为是不可能的。然而从1970年开始，这一类型的算法开始出现。第一个广为流传的是MIT的三位密码学家：Ron Rivest，Adi Shamir 和Leonard Adleman提出的RSA。

公钥算法并不仅仅用来加密，实际上本书之前的部分已经提到过公钥算法而其不是直接用在加密上。有三个与公钥算法相关的主题

密钥交换算法，例如Diffie-Hellman，在不安全的媒介上共享私密的信息。
加密算法，本章的内容，可以让用户加密一个东西而不需要提前共享密钥。
签名算法，在之后章节会讨论，用户可以使用私钥对一些信息进行签名，而其他人使用公钥可以对这些信息进行验证。

9.2 为什么不在所有的场景上都是用公钥加密

从表面来看，公钥加密好像可以淘汰之前提到的对称密钥算法。对于任何事情都可以使用公钥加密，也不需要对称密钥系统中的密钥交换过程。然而在实际的密码学系统中，可以看到到处都是混合的加密，公钥加密在其中起着重要作用，但是大部分的加解密以及认证工作还是基于对成密钥算法的。

目前来看最重要的原因是性能。与流密码（原生的流密码或者其他）算法相比，公钥加密机制实在是太慢了。RSA通常情况下需要2048位也就是256个字节。其加密需要0.29百万次循环，解密需要11.12百万次循环。而对称加密和解密只需要每字节约10次循环。这也意味着在对称密钥算法中，解密256位数据，只需要3000次循环，这个效率是非对称版本的4000次。而目前的密码系统使得对称加密更快了，在AES-GCM硬件加速或者Salsa20/ChaCha20只需要2或者4次每字节，更大程度上提高了性能。

实际的密码系统中还有更多其他的问题。例如对于RSA来说，它不能加密任何比它大的信息，通常情况是小于或者等于4096位，比大部分的需求要小的多。当然最重要的问题依然是上述的速度的问题。

9.3 RSA

加密和解密

本节简单描述RSA背后的数学问题。其本身并不能产生安全加密机制。之后会看到在其上构造的密码指导OAEP。

为了产生一个key，需要挑选两个大素数p和q，这些数需要随机私密的挑选。将两者相乘的到N，这个是公开的。然后选择一个加密指数e，这个也是公开的。通常这个数是3或者65537.因为这些数的二进制形式中仅有很少量的1。计算指数会更有效。（N，e）是公钥，任何人都可以用公钥来加密消息M，得到密文C。
$C=M^e(mod N)$
接下来的问题是解密，有一个解密指数d，可以将C转化会M。如果指导p和q，d很容易计算。可以使用d来解密消息：
$M=C^d(mod N)$
RSA的安全性依赖于对于不知道d的人来说解密操作是不可能的，并且在只知道（N，e）的情况下d的计算是非常难的。

打破RSA

类似于很多密码系统，RSA依赖于特定数学问题的难度。给定密文C，和公钥（N，e），反推出明文M。这被称为RSA难题。
$C=M^e(mod N)$
最直接的方法是将N分解为p*q。给定p和q，攻击者只需要重复密钥拥有者的过程来计算产生d即可。

幸运的是，没有一个算法可以在合理的时间内分解这么大的数。不幸的是，目前也无法证明该算法一定不存在。更加糟糕的是，有一个理论上的算法，被称为Shor's Algorithm，可以在量子计算机上在合理的时间内分解一个数。目前，量子计算机还离我们有些远，但是未来某天可能就会成为现实。到时候RSA就变得不再有效。

本节中仅仅提到了分解大数这个最直接的方式来攻击RSA。在接下来的部分可以看到一系列针对RSA的实际攻击，其主要依赖于一些具体的实现。

实施中的隐患

目前，没有已知的实际的攻破RSA的方法。但这不意味着使用RSA的系统没有被攻破过。和其他被攻破的系统一样，应用中有很多组成部分，一旦其中的某部分没有恰当的使用，就会使整个系统变得不可用。更多有关RSA实施的细节的，参考【Bon99】和【AV96】，本部分只提及一些有趣的部分。

Salt

Salt是一个用python写的供应系统。它有一个模块叫做cypto，它没有使用已有的密码学系统，而是实现了一个自己的，其中使用的RSA和AES由第三方库提供。

很长一段时间里，Salt使用的公钥指数e是1，这也就意味着P^e=P1=P(mod N)。这也就意味着结果的密文就是明文。目前该问题已经被修复，这里只是为了提醒大家，不要实现自己的加密系统。Salt现在支持了SSH作为传输蹭，但是先前提到的DIY的RSA/AES系统依然存在，并且还是默认的传输层。

OAEP（Optimal asymmetric encryption padding）最优非对称加密填充

OAEP是Optimal asymmetric encryption padding的简称，是RSA填充的一种。它的结构类似于下图（文档中这个图有问题，下面是正确的图）：

image.png

最终产生的需要被加密的数据是X||Y，是n位长，这个n是N的位数。它使用一个随机的块R它的长度是k，在这个标准中，k是一个定值。消息首先需要用0填充被扩充到n-k位。图中左边的长度为n-k位，右边的长度为k。随机块R和以0扩充的M，M||000...使用两个陷阱函数，G和H。陷阱函数都是从一个方向计算非常简单，但是逆转非常的难。世纪中通常为hash函数。

G的输入是k位，输出是n-k位，H的输入是n-k位，输出是k位。

然后结果的X和Y被连接在一起，然后由标准的RSA来进行加密产生密文。

解密的时候，要反过来操作。接收者收到X||Y，他们是指导k的，因为这个是协议里的定值。所以前n-k是X，后k位是Y。

想要得到M，M||000...,需要去计算
$M||000...=X⊕G(R)$

$G(R)=G(H(X)⊕Y)$

可以看出，对于一些H和G来说，需要所有的X和Y才能找到M。对于H和G有很多种基于Hash函数的选择。

9.4 椭圆曲线（书中暂未介绍）

9.5 遗留问题：未验证的加密

绝大多数的公钥加密只能一次加密一小块，一般都远小于要发送的信息。另外这些算法还很慢，比对称加密要慢的多。通常非对称加密用来连接密码系统。

有了公钥密码和密钥交换，是密码学里面两个非常重要的部分，因为人们总是需要与其他人交换私密的信息。有了这两个技术就可以安全地和其他人交流。

目前为止讨论的加密都没有任何形式的身份认证。这也就意味着对消息进行加密和解密，并不能验证得到的消息确实是发送者发送的原本的消息。

没有身份认证的加密可以提供隐私性，但是如之前章节所言，没有身份认证，尽管攻击者不知道任何原文的信息，他任然可以修改加密的信息。接收这些消息会泄漏一些私密的信息，这也就意味着私密性不在。例如之前第7章提到的CBC的填充攻击。

综上所言，出了加密私密的信息之外，还需要对其进行身份认证。通常身份认证都是对消息增加一些额外的可计算的信息。类似于加密，身份认证也分为对称类型的和非对称类型的。对称类型的通常被称为消息认证（message authentication），非对称类型的通常被称为数字签名。

下一章先介绍一下另一个密码学中的重点：hash函数。hash在产生签名和消息认证等过程中都需要用到。

[Bon99] Dan Boneh. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46:203–213, 1999. URL: http://crypto.stanford.edu/dabo/papers/RSA-survey.pdf.

[AV96] Ross Anderson and Serge Vaudenay. Minding your pʼs and qʼs. In In Advances in Cryptology - ASIACRYPT’96, LNCS 1163, 26–35. Springer� Verlag, 1996. URL: http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf.