public-key - 为什么公钥算法很慢？

Question

我正在为测试而学习，但我仍然不明白为什么公钥算法比对称算法慢得多。

Answer 1

公钥加密是非对称加密的一种形式，不同之处在于使用了额外的加密密钥。

对称算法使用“共享秘密”，其中两个系统各自使用单个加密密钥来加密和解密通信。

公钥密码术不使用单个共享密钥，而是使用数学密钥对：公钥和私钥。在该系统中，通信使用公钥加密并使用私钥解密。这是来自维基百科的更好解释：

公钥密码学中使用的区分技术是使用非对称密钥算法，其中用于加密消息的密钥与用于解密消息的密钥不同。每个用户都有一对加密密钥——一个公共加密密钥和一个私有解密密钥。公开可用的加密密钥被广泛分发，而私有解密密钥只有接收者知道。消息使用收件人的公钥加密，只能使用相应的私钥解密。密钥在数学上是相关的，但私钥不能从公钥中导出（即在实际或预计的实践中）。

那么计算开销就非常明显了：公钥可用于它所暴露的任何系统（互联网上的公钥系统，例如将公钥暴露给整个互联网）。作为补偿，公钥和私钥都必须非常大，以确保更高级别的加密。然而，结果是更高级别的加密，因为私有解密密钥（到目前为止）不能从公共加密密钥进行逆向工程。

还有更多可能会影响公钥基础设施(PKI) 的“速度”。由于该系统的问题之一是信任，因此大多数实现都涉及证书颁发机构(CA)，这是受信任的实体，可以委托密钥对并验证密钥的“身份”。

总结一下：更大的加密密钥大小，两个加密密钥而不是一个，并且引入了证书颁发机构：额外的 DNS 查找和服务器响应时间。

正是由于这种额外的开销，大多数实现都受益于混合算法，其中公钥和私钥用于生成会话密钥（很像对称算法中的共享密钥）以获得两全其美的效果。

Answer 2

Public key algorithms rely on "trapdoor" calculations, ones that are computationally expensive to encrypt and computationally intractable to decrypt with the secret key. If the first step is too easy (which correlates with speed), the second step becomes less hard (more breakable). Consequently, public key algorithms tend to be resource intensive.

Private key algorithms already have the secret during the encryption phase, so they don't have to do as much work as an algorithm with a public secret.

The above is an over-generalization but should give you a feel for the reasons behind the relative speed differences. That being said, a private key algorithm can be slow and a public key algorithm may have an efficient implementation. The devil is in the details :-)

Answer 3

加密和密钥方法是一个非常深刻和复杂的话题，只有世界上最聪明的数学头脑才能完全理解，但也有大多数人可以理解的顶级观点。

主要区别在于，对称算法需要比非对称 (PKI) 方法小得多的密钥。因为对称算法适用于abcd1234在可信通信方法中传输的“共享秘密”（例如只要他们依赖其他安全方法（即我相信你不会告诉任何人）。

PK 基础设施涉及通过互联网、不可信空间发送该“密钥”，并涉及使用大量素数和大量密钥（例如 1024 位或 2048 位而不是 128 或 256 位）。

一般的经验法则是 PKI 方法比对称密钥慢大约 1,000 倍。