🔉 🥂 🤙🏻 停止使用RSA 👨🏼‍💼 🤰🏿 🏇

嗨％用户名％！

RSA是第一个被广泛使用的非对称密码算法，该算法在业界仍然很流行。乍一看它相对简单。 RSA加密和签名可以算在一张纸上，学生在实验室工作中通常会这样做。
但是，仅存在大量细微差别，没有这些细微差别，即使是孩子也可以破解您的RSA实现。

由于某些原因，人们仍然认为RSA是一种很好的算法。但是实际上，实施RSA时的一击范围非常巨大。如果不是不可能的话，很难验证弱参数。而且算法的性能差会鼓励开发人员使用冒险的方式进行改进。

更糟糕的是，超过20年前发明的填充oracle攻击今天仍然有用。
即使理论上可以正确实施RSA，实际上，这种“壮举”几乎是不可能实现的。几十年来不断出现的漏洞仅证实了这一点。

关于RSA算法的几句话

如果您知道RSA的工作原理，则可以跳过此部分。

RSA是具有两种用途的公共密钥密码系统。

第一种是加密，当爱丽丝发布她的公钥时，鲍勃知道这一点，就可以加密只有爱丽丝可以读的消息，并用她的私钥解密。

第二个是数字签名，该签名允许Alice使用她的私钥对消息签名，以便每个人都可以使用她的公钥验证此签名。

两种算法的细节都不同，因此我们将它们简称为RSA。

要开始使用RSA，Alice需要选择两个质数p和q ，它们一起形成一组以N = pq为模的数字。然后，爱丽丝需要选择一个开放指数e和一个秘密指数d ，使得

e d = 1 m o d （ p - 1 ） （ q - 1 ）

$ed = 1 \ mod（p-1）（q-1）$ 。本质上， e和d应该相互简单。

选择这些选项后，Bob可以向Alice发送消息M，

C = M^{e} （ m o d N ）

$C = M ^ e（mod \ N）$ 。然后，爱丽丝可以通过计算解密消息

M = C^{d} （ m o d N ）

$M = C ^ d（mod \ N）$ 。
数字签名正好相反。如果爱丽丝想对邮件签名，她将计算签名

S = M^{d} （ m o d N ）

$S = M ^ d（mod \ N）$ 鲍勃可以通过确认消息来检查

M = S^{e} （ m o d N ）

$M = S ^ e（mod \ N）$

就是这样，这就是主要思想。稍后我们将返回Padding oracles，但是现在让我们看看如果RSA参数选择不正确怎么办。

结束的开始

为了使RSA正常工作，您需要选择很多参数。不幸的是，他们选择的看似无害的方法可能会损害安全性。让我们逐一检查一下，看看有什么不愉快的惊喜在等着您。

黄金一代

RSA安全性基于这样一个事实，即很难实现N （这是两个质数p和q的乘积），很难将N分解为质数而不知道p和q 。开发人员负责选择组成RSA模块的素数。与其他加密协议的密钥生成相比，此过程非常慢，在其他密钥协议中，仅选择几个随机字节就足够了。因此，开发人员经常尝试创建特定形状的数字，而不是生成真正随机的质数。它几乎总是糟糕地结束。选择质数的方法有很多，因此分解N很简单。例如， p和q必须是全局唯一的。如果p或q曾在其他RSA模块中重复使用过，则可以使用GCD算法轻松计算两个因子。错误的随机数生成器很可能导致这种情况发生，研究表明，2012年大约1％的TLS流量受到了此类攻击。

而且， p和q必须彼此独立地选择。如果p和q共享其最高有效位的大约一半，则可以使用Fermat方法计算N。实际上，即使选择简单性测试算法也可能带来安全隐患。可能最广为人知的攻击是RSALib中的ROCA漏洞，该漏洞影响了许多智能卡，可信平台模块甚至Yubikey密钥。在这里，生成密钥时，仅使用某种形式的质数来加快计算速度。用数论中的棘手技术发现以这种方式产生的质数很容易。一旦识别出一个弱系统，素数的特殊代数性质使攻击者可以使用Coppersmith方法分解N。

应该记住，在所有这些情况下，以这种方式生成素数都不是导致系统完全故障的明显事实。这是因为质数的微不足道的数论性质对RSA安全性具有重大影响。普通开发人员会穿越这个数学雷区的期望严重破坏了安全性。

秘密参展商

由于使用较大的私钥会对解密和签名时间产生负面影响，因此开发人员有动力选择较小的d ，特别是在功耗较低的设备（例如智能卡）的情况下。但是，当d小于N的4度根时，攻击者可以恢复私钥。相反，开发人员应选择较大的d值，以便使用中文余数定理来加快解密速度。但是，此方法的复杂性增加了可能导致密钥恢复的微小实现错误的可能性。

您说通常在RSA初始化期间首先生成一个模块，使用固定的开放指数，然后选择一个秘密吗？
是的，如果您始终使用建议的开放指数e之一，则可以防止使用秘密指数小的攻击。
不幸的是，这也假设开发人员会真正做到这一点。在现实世界中，开发人员通常会做一些奇怪的事情，例如，首先选择d ，然后考虑e 。

公开参展商

与秘密参展商一样，开发人员希望使用小型公开参展商来节省加密和签名验证。通常，在这种情况下使用费马素数，特别是e = 3、17和65537。

尽管密码学家建议使用65537，但开发人员经常选择e = 3，这会导致RSA密码系统中的许多漏洞。

（在这里，开发人员使用e = 1，这实际上根本不加密明文。）

当e = 3或类似大小时，可能会出错。较小的开放指数经常与其他常见错误结合在一起，使攻击者可以解密某些密文或因子N。

例如，富兰克林-路透社的攻击使攻击者可以解密以已知的固定距离连接的两条消息。换句话说，假设Alice仅向Bob发送“购买”或“出售”。这些消息将与一个已知值相关联，并将使攻击者无需解密消息即可确定其中的哪个表示“购买”，哪个“出售”。一些带有小e的攻击甚至可能导致密钥恢复。

如果开放指数很小（不仅是3），那么知道密钥的几位攻击者可以恢复剩余的位并破坏密码系统。尽管可以通过填充来修复许多此类e = 3 RSA攻击，但是自己实施RSA的开发人员通常会忘记使用它。

RSA签名也容易受到小型公共参展商的攻击。 2006年，Bleichenbacher发现了一种攻击，攻击者可以在许多RSA实现中伪造任意签名，包括Firefox和Chrome中使用的签名。这意味着任何来自易受攻击的实施的TLS证书都可以被篡改。这种攻击利用了以下事实：许多库在处理RSA签名时都使用小的公共指数，并且不执行简单的对齐检查。 Bleichenbacher对签名的攻击是如此简单，以至于它被包含在密码学课程的许多练习中。

选择选项是一项艰巨的任务

所有这些对参数的攻击的共同点是，参数的可能变体的总数比安全变体的总数大得多。

假定开发人员自己将管理这个复杂的选择过程，因为除开放指数外的所有内容都必须在初始化期间生成。
没有简单的方法来检查参数的可靠性 。相反，开发人员需要一个认真的数学基础，普通雇员不应期望这样的数学基础。尽管如果参数错误，将RSA与对齐方式结合使用可以节省您的时间，但许多人还是不愿意这样做。

填充Oracle攻击

如上文所述，仅使用现成的RSA并不可行。例如，如果对相同的明文进行了多次加密，则导言中概述的RSA方案将创建相同的密文。这是一个问题，因为它将使攻击者可以从上下文中学习消息的内容，而无需对其进行解密。这就是为什么我们需要将消息与几个随机字节对齐。不幸的是，最广泛使用的对齐方案PKCS＃1 v1.5通常容易受到所谓的填充预言攻击。

Daniel Bleikhanbacher于1998年发现了对PKCS＃1 v1.5的最初攻击。尽管她已经超过20岁，但今天她仍然与许多系统相关。这种攻击的现代版本通常包括一个额外的Oracle，它比Bleikhanbacher最初描述的要复杂一些，例如，服务器响应时间或TLS中任何协议降级的执行。一个特别令人震惊的例子是ROBOT攻击，它是如此可怕，以至于一组研究人员能够使用Facebook和PayPal秘密密钥对消息进行签名。有人可能会说这并不是RSA的错-基本的数学很好；几十年前人们只是弄乱了一个重要的标准。事实是，自1998年以来，我们已经有了带有严格安全证据的标准对准方案OAEP。但是几乎没有人使用它。即使发生这种情况，众所周知，OAEP难以实施，并且经常容易受到Manger攻击，这是可用于恢复明文的另一种Oracle攻击。

这里的根本问题是，在使用RSA时必须进行对齐，并且这种额外的复杂性为对密码系统的攻击打开了广阔的空间。一点信息（“消息是否正确对齐”）这一事实可能会对安全性产生巨大影响，从而使得实际上无法开发安全库。 TLS 1.3不再支持RSA，因此我们可以预期将来会有更少的此类攻击。

但是，尽管开发人员继续在自己的应用程序中使用RSA，但Padding Oracle攻击将继续发生。

怎么办

人们通常喜欢使用RSA，因为他们发现它在概念上比复杂的DSA协议或椭圆曲线密码术（ECC）更简单。但是，尽管RSA更直观，但它确实缺乏对傻瓜的保护。

首先，一个常见的误解是椭圆形是非常危险的，因为选择不良曲线会使所有内容无效。的确，曲线选择对安全性有很大影响，但是使用ECC的好处之一是可以公开进行参数选择。密码学家为您选择参数，因此开发人员只需要生成随机字节的数据即可用作密钥。从理论上讲，开发人员可以使用可怕的参数构建ECC实现，并且将无法检查诸如错误的曲线点之类的东西，但通常不会。可能的解释是，ECC背后的数学是如此复杂，以至于很少有人感到有足够的信心实施它。换句话说，这种恐惧迫使人们使用由了解自己知识的密码学家创建的库。另一方面，RSA非常简单，可以在一小时内（很差）实现。

其次，任何基于Diffie-Hellman的密钥匹配或签名方案（包括椭圆曲线选项）都不需要对齐，因此完全可以抵抗Padding Oracle攻击。鉴于RSA在避免此类漏洞的尝试方面拥有很长的记录，因此这是一次重大胜利。

我们建议使用Curve25519进行密钥交换，并使用ed25519进行数字签名。加密应使用ECIES协议执行，该协议将ECC密钥交换与对称加密算法结合在一起。 Curve25519旨在完全防止其他曲线可能发生的攻击类别，而且速度也非常快。此外，它在许多库中实现，例如libsodium，它配备了易于阅读的文档，并且支持大多数语言。