cryptography - 用于公钥加密的 Big-O

Question

我已经搜索了几天，但我找不到使用公钥加密来加密、解密或尝试破解加密文件(蛮力)的大 O 符号算法。我正在尝试确定我开发的大量使用公钥加密的想法的大 O 符号。

这些与公钥加密相关的 Big-O 算法是什么:

A) 用长度为 L 的 key 加密由 N 个字符组成的文件

B)解密同一个文件

C) 一种典型的暴力破解算法，用于破解 N 个字符且最大 key 长度为 L 的加密文件

任何包含用于破解加密的更有效算法的 Big-O 符号将不胜感激。此外，请引用可以找到此 Material 的任何地方。

很抱歉问一个我真的应该能够自己找到的问题，但我还没有找到我要找的东西。

Answer 1

标准公钥/私钥算法几乎从不用于大输入，因为这些算法的安全属性通常不适合批量加密。最常见的配置是使用公钥/私钥算法来加密一个小的(恒定大小，通常为 128 - 256 位) key ，然后将该 key 用于对称加密算法。

话虽如此，我将使用 RSA 作为其余问题的测试用例:

A/B) 撇开 key 生成，RSA 在 O(n) 中加密和解密对于消息的大小。 (请注意，所有消息都必须是 key 的大小，因此填充较小的消息，必须分解较大的消息。)加密/解密的确切速度取决于您的 RSA 实现使用的算法，但它是 key 大小的多项式:

http://www.javamex.com/tutorials/cryptography/rsa_key_length.shtml

C) 给定一个公钥，可以通过分解公钥来破解 RSA，目前最好使用 GNFS 来完成。 (这是 O(exp((7.1 b)^1/3 (log b)^1/3)) )。我认为基于加密数据破解 RSA 的工作并不多，因为公钥是一个更有用的目标。