对称加密的安全性可以直接使用密钥长度判断，如 128 位、256 位，只要密码学家同意算法本身是安全的。相比之下，衡量公钥加密的安全性则比较复杂：我们选择目前最高效的算法（如大步小步、Pollard rho 等）来攻击手中的问题（如椭圆曲线离散对数问题），估算攻击所需的资源的数量级，然后与对称加密的攻击相比较，得出其安全性“等效于 n 位对称加密”的结论。例如 NIST 认为：256 位有限域上的椭圆曲线公钥加密拥有”等效于 128 位对称加密“的安全性，因此推荐与 AES-128 配合使用。

但问题真的有那么简单吗？知名密码学家（兼信息安全界知名喷子与段子手） Daniel J. Bernstein 有不同意见。在口水战泛滥的”256 位还是 128 位加密”问题上，他的观点也是我听说过最有趣的。

人们常说破解 128 位对称加密（如 AES-128）所需的运算量约为 2^128，但往往忽略了一个前提：这个等级的运算量，是破解一个密钥与一个密文所需的运算量。如果攻击者能获得使用不同密钥加密的相同明文，那么它可以对使用不同密钥的大量用户（或连接）同时进行无差别攻击，而且这是一个可以完美并行化的问题。例如同时攻击 2^40 个密钥，能破解一个是一个，那么至少破解一个密钥的所需的运算量就降低为 2^88。这已经接近人类能想象的数字（2^80）。而且攻击者还可以碰运气：降低搜索次数，成功率线性递减。例如只搜索 25%，将运算量降低为 2^86。

随后，作者还设想了一台大规模并行密码破解机。机器具有 2^32 个芯片，攻击者进行 2^32 次运算（虽然极大，但是人类可以想象的），那么破解至少一个密钥的可能性就是 2^-24。虽然 0.00000006% 的概率可以忽略不计，但纯理论上讲，如此之低的安全性是许多密码学家不能接受的。

相比之下，破解 256 位的椭圆曲线（如 Curve25519，虽然严格意义是 255 位），攻击者必须至少解决一个椭圆曲线离散对数问题，破解多个密钥的难度不比破解一个密钥容易。无论同时破解多少个密钥，运算量都至少为 2^128（攻击更多密钥则需要更高的运算量）。而且攻击者也不太可能碰运气：降低搜索次数，成功率二次方递减。

因此得到几个结论：

1. 同样被评估为“128 位安全”，对称加密和公钥加密的安全性却有极大的差别。虽然在实践中可能没有什么影响，但有明显的理论意义。DJB 说——Bottom line: 128-bit AES keys are not comparable in security to 255-bit elliptic-curve keys. Is 2^255 – 19 big enough? Yes. Is 128-bit AES safe? Unclear.
2. 在密码分析中，串行计算的性能和并行计算的性能不能盲目互换。如果条件合适，大规模并行攻击的成本可能比类似的串行攻击低上亿倍。
3. 在这种意义上，将 256 位对称加密和“128 位安全的公钥加密”搭配并非是不合理的。这也是主张使用 256 位加密而不是 128 位加密的一个有趣理由。Daniel J. Bernstein 设计的 ChaCha20 只使用 256 位加密，可能就是这个原因。此外，这个攻击之所以可行，是因为不同的密钥被用来加密相同的明文：AES_k1(x), AES_k2(x), … 但如果不同的密钥总是加密不同的明文：AES_k1(x1), AES_k2(x2), …，无差别攻击就不再可行。有研究者建议提高 nonce 大小，例如将 nonce 提高到 128 位，然后随机选取，但这个方案比加长密钥复杂，而且有许多缺点。

当然，上述讨论不适用于量子计算机。等大型量子计算机问世，所有现在使用的公钥加密和 128 位的对称加密均可被破解，只有 256 位对称加密还算安全。

延伸阅读

• Is 2^{255}-19 big enough? (PDF)
  竖版，强烈建议使用“幻灯片模式”或“全屏”阅读。

It is widely asserted that 128-bit AES and a strong 256-bit elliptic curve provide comparable security levels against known attacks. This assertion is false. Known attacks batch and scale much more effectively for 128-bit AES than they do for a strong 256-bit elliptic curve.

• Understanding Brute Force (PostScript)

There is a widespread myth that parallelizing a computation cannot improve its price-performance ratio. The reality is that a parallel computer is often several orders of magnitude faster than a comparably priced serial computer.