为什么非对称加密比对称加密效率低?

信息安全 加密 不对称 算法 表现
2021-09-01 08:55:36

众所周知,非对称加密的计算成本通常比对称加密高得多,因此通常的做法是使用非对称加密来建立用于批量数据交换的对称密钥。不过,我没有找到任何关于到底慢了多少的信息。

所以,假设我有一些小数据 X(比如 256 位哈希值),并且我选择了合理的现代密码算法,那么计算的粗略相对成本是多少

  • X 在某个公钥下加密
  • X 在某个对称密钥下加密
  • H(X),H是一个密码散列函数
1个回答

这取决于算法。尤其是使用非对称加密,速度变化很大您可能想查看eBACS以获得更详细且与机器无关的各种加密原语的基准测试。与往常一样,您需要在自己的系统上执行自己的基准测试,以准确了解在所选条件下对生产系统的期望。

你永远不应该使用非对称密码来直接加密任何东西。如果您对密钥以外的任何内容进行加密,则可能会面临使密码分析成为可能的风险。例如,RSA 不喜欢加密非随机数据。这在加密密钥时很好(毕竟这是随机的),但在加密 ASCII 时就不行了。引用另一个答案(强调我的):

RSA 有一些操作限制。对于最常用的变体(称为 PKCS#1 v1.5),如果 RSA 密钥的大小是“1024 位”(意味着密钥对的中心数学组件是 1024 位整数),那么RSA 最多可以加密长度为 117 字节的消息,并生成长度为 128 字节的加密消息。有限的大小以及加密时大小的增加是 RSA 加密过程的数学结构不可避免的结果。由于这些限制,我们通常不直接使用 RSA 加密数据;相反,我们选择一个小的随机字节序列,我们称之为会话密钥。我们用 RSA 加密会话密钥;然后我们使用带有对称加密算法的会话密钥来处理整个消息。这称为混合加密。

使用对称密码加密少量数据不会让您从其更高的速度中受益。大多数对称密码都有一个称为密钥调度的一次性设置成本,其中密钥被处理并拆分为密码的每个组件的单独子密钥,或者分散在密码的内部状态中。这些子密钥通常被缓存,因此每次调用密码时都可以直接使用它们。每次使用新密钥时,都会运行密钥计划,并且必须完成之后才能加密任何内容。一些密码具有非常昂贵的密钥调度,例如Blowfish,其密钥调度相当于 521 次 Blowfish 加密,需要 4 KiB 的 RAM,并且是慢速bcrypt的基础功能。其他人有非常简单的密钥时间表,例如TEA,它只是将密钥拆分并将其与常量混合。当您使用单个密钥加密大量数据时,与单独加密小块数据相比,您可以从快速密码的速度中获益更多。


下面是中等负载下低端系统(奔腾 III,1 GHz)的快速基准测试。请注意,这些基准仅显示这些算法在这台特定机器上的速度。它可能精确到一个数量级之内,但是具有不同能力的更快的机器可能不仅更快,各个算法的相对速度也可能不同!但是想出个主意...

RSA,具有不同的大小:

OpenSSL> 速度 rsa
...
                  签名 验证 签名/s 验证/s *
rsa 512 位 0.001305s 0.000113s 766.2 8881.1
rsa 1024 位 0.007685s 0.000372s 130.1 2687.5
rsa 2048 位 0.050615s 0.001355s 19.8 738.1
rsa 4096 位 0.353636s 0.005201s 2.8 192.3

AES,具有不同的密钥大小和输入长度:

OpenSSL> 速度 aes
...
“数字”以每秒处理的 1000 字节为单位。
类型 16 字节 64 字节 256 字节 1024 字节 8192 字节
AES-128 CBC 21174.71k 23656.67k 24212.96k 39798.65k 40800.k
aes-192 cbc 18706.23k 20713.58k 21222.25k 34669.23k 35059.k
aes-256 cbc 16153.38k 17569.97k 18004.69k 30170.76k 30020.k

SHA-256,具有各种输入长度:

OpenSSL> 速度 sha256
...
“数字”以每秒处理的 1000 字节为单位。
类型 16 字节 64 字节 256 字节 1024 字节 8192 字节
sha256 6537.11k 14781.14k 26256.93k 32630.49k 34562.k

* 在教科书 RSA 中,签名验证等同于加密,签名等同于解密。验证涉及确定是否s e ≡ m (mod n),而加密正在运行c ≡ m e (mod n)在现实世界中,有一些重要的区别涉及防止 RSA 被轻易破坏所必需的特殊填充操作。


我想你想知道为什么会有这种性能差异。原因与这些加密原语的工作方式有关。下面是非对称密码、对称密码和散列函数的基本解释,以及影响它们性能的因素。

不对称密码涉及所谓的硬度问题这些是数学中的开放问题,它们利用了这样一个事实:一个操作很容易在一个方向上执行,但如果没有秘密值就很难反向操作。RSA 使用的事实是,将两个巨大的素数相乘很简单,但是在没有至少一个原始素数的情况下,将得到的合数分解回原始素数是非常困难的。对于教科书 RSA,加密消息m需要您计算c ≡ m e (mod n)要解密c,请计算m ≡ c d (mod n)这里,n是两个秘密素数pq的乘积,de的模逆(一个公共指数,通常被选为费马素数),通过计算d ≡ e -1 mod (p - 1)得到(q - 1)

非对称密码的速度差异很大,因为它们都涉及不同的数学概念。即使是使用相同概念的不同密码(例如 RSA 和Rabin 密码系统),速度也会有所不同。这些算法通常很慢,因为它们需要一次对非常大的数字进行操作,这对于我们只能有效处理 64 位数字的现代 CPU 来说是困难的(或者更多,最新的 CPU最高可达 512 位) ,当使用特殊优化时)。尤其是在 64 位处理器上涉及 64 位整数时,模块化算术是微不足道的,但在涉及大量 2048 位数字时效率非常低。

对称密码有两种类型:流密码和分组密码*流密码使用密钥生成无穷无尽的确定性伪随机字节流(密钥流)。该流与明文结合形成密文。解密涉及相同的操作,将密钥流与密文结合以获得明文。另一方面,块密码采用密钥并使用它来置换固定块的输入,输出相同大小的密文块。可以使用相同的密钥反向运行分组密码来解密密文。分组密码必须在某种操作模式下运行使用密钥安全地加密多个数据块。一些模式允许并行实现。其他的必须串行化,而其他的仍然可以并行化以进行加密但不能解密,反之亦然。

对称密码的速度非常快,因为它们只涉及混淆(输出不提供有关输入或密钥的提示)和扩散(输入或密钥的微小变化会导致输出发生剧烈变化)的概念。与通常作用于大量数字的非对称密码不同,对称密码涉及大量重复多次的非常简单的密钥相关操作。每个操作都足够小,可以由 CPU 有效计算。特别是,使用ARX 方案的密码(例如 Salsa20)只需要对非常小的字大小数据块进行加法、旋转和 XOR 操作,这可以在处理器上非常有效地实现。对笨重的数字没有算术运算。

散列函数与对称密码非常相似,它们涉及相同的混淆和扩散概念。事实上,哈希函数有时用于创建密码,反之亦然这可以通过 Salsa20(一种在其核心使用散列的流密码)和 Whirlpool(使用 AES 的修改版本的散列函数)看出。哈希函数接受一个有效无限大小的输入并输出一个固定大小的摘要。像密码一样,混淆会阻止攻击者从输出中了解有关输入的任何信息,而扩散会放大输入的微小变化。

哈希通常比对称密码慢,因为它们有更严格的要求。特别是,散列不仅必须防止攻击者反转操作(原像攻击)和修改输入而不改变散列(第二原像攻击),它还必须难以生成创建相同的输入对哈希(碰撞攻击)。抗碰撞是困难的,并且往往需要一个相当缓慢和复杂的哈希。换个角度来看,攻击者可以比调用该函数两次所花费的精力更少地碰撞严重损坏的 MD4 哈希。即便如此,对它的最佳原像攻击仍然是纯理论的。

* 流密码加密为C = P ⊕ E K,解密为P = C ⊕ E K,其中P为明文,C为密文,E K为使用密钥K生成的密钥流。对于分组密码,加密是C = E K (P),解密是P = D K (C) ,对于PC的单个块在给定单个K情况下,需要一种操作模式来处理多个PC。

当使用散列函数构造密码时,反之亦然,散列所要求的安全属性是不同的。例如,Salsa20 是一种安全的流密码,尽管它是由缺乏抗碰撞性的散列函数构建的同样,由密码构建的散列要求密码对相关密钥攻击是安全的,而安全密码本身并不一定需要这一点。