用于高吞吐量的多线程/核心加密算法

Question

在某些情况下，单个连接(或文件)可能需要额外的可用吞吐量。虽然网络带宽和CPU核心是可用的，但它们不能被利用。(除了算法外部的方法外)

下面是一些例子：

• VPN --当加密只在内部封装多个流数据包的隧道连接上进行时。

通常，人们认为加密算法本身是一个序贯过程，它依赖于先前的块或比特(S)来实现有效的密码强度。这意味着算法不能是多线程的。

所有加密都是这样吗？这是否同样适用于现代通用算法(块和流)？

是否有一种方法可以使加密算法在多线程(核心)上工作？是否有任何现有的算法(可能不是普通的或学术的)可以跨多个核工作？

通常，这不是一个问题，因为机器可能使用多个连接(HTTPS)，但这意味着单个连接受到单个CPU核心的密码转换速度的限制。此外，当使用多路复用(如VPN)时，这可能是一个特别有限的问题。

Answer 1

通常，人们认为加密算法是一个顺序过程，它依赖于前一个块或比特(S)来实现有效的密码强度。这意味着算法不能是多线程的。

这只适用于“重手”操作，如CBC-MAC (及其变体)、HMAC和CBC。对于大多数实现的现代密码学来说，并行性都是高性能实现所必需的特性。

在跳到与您在这方面相关的方案之前，让我澄清为什么并行性实际上是必要的。你可能听说过AES-NI。这些指令每条指令执行一次AES循环。然而，在这种情况下，这些指令的延迟时间不是一个CPU周期，而是3-7个CPU周期，尽管它们的吞吐量至少为每个周期1条指令.延迟意味着如果指令B依赖于指令A的结果，则B必须等待A的全部延迟，因此，要优化使用硬件，需要做的是并行运行8个与数据无关的AES操作，这与请求级并行非常棘手。因此，取而代之的是，它们使用可并行的方案，一次不计算一个AES数据块，而是计算8或多个是实现的最佳选择。

但是，你一定会问自己，这是怎么做到的：

1. 如果您想要CPA安全加密，CTR-模式通过加密计数器将块密码转换为流密码。
2. 如果你想要一个基于现在的MAC，GMAC可以并行化 --通常被利用来减少要计算的裁减数。
3. 如果您想要一个完整的并行PRF，PMAC是一条可行的道路，尽管在实践中，由于HMAC或单块AES在需要时的突出地位，它并不常见。
4. 如果您想要并行散列算法，可以使用树散列。
5. 如果您需要经过身份验证的加密，那么AES-GCM可以并行化--因为它本质上是由GMAC和CTR组成的。
6. 如果您想要防止误用的身份验证加密，广义SIV变换和AES-GCM-SIV都需要两次传递，但每一次传递都可以并行化--至少对于加密，解密是本机并行的。

Answer 2

在公钥设置中，还有一些高度并行加密方案的简单示例。也就是说，基于错误学习的加密方案1通常归结为通过计算大量的矩阵运算(乘法/加法)来加密，这些运算具有高度的并行性。基于LWE的密码学目前是量子后密码学的领先候选之一，并且在未来几年内可能会在实践中得到更广泛的应用(假设它没有发生灾难性的事情)。

即使在私钥设置中，这也会导致仍然相当高效的可并行结构。最著名的例子之一是斯威夫特哈希函数，它的吞吐量比SHA256稍低(~15%，我的意思是，因为SWIFT是基于“公钥”硬度假设)。它的一个修改版被提交给了SHA3比赛，但没有通过第一轮(我不知道这个时期的历史，知道为什么会发生这种情况，也许是因为性能原因--如果有更多的人能发表评论，我会感兴趣的)。

1我认为这也适用于基于代码的密码学，但我不太熟悉这个领域。