抗量子密码学
量子计算机是……
- 待办
- 待办
参见此页面：https://ianix.com/pqcrypto/pqcrypto-deployment.html
- 待办
量子计算是一种基于量子物理学的计算模型，其工作方式不同于经典计算机，并且能够完成经典计算机无法完成的事情，例如\ 高效破解 RSA 和 ECC。量子计算机并不是“速度更快的计算机”，它们也并非无所不能，无法更快地完成所有计算任务。量子计算机在解决某些问题时非常高效，在另一些问题上却相当薄弱。
计算机科学界普遍知道，量子计算机会破解某些密码学算法，尤其是依赖 IFP（整数分解问题）、DLP（离散对数问题）和 ECDLP（椭圆曲线离散对数问题）的 RSA、ECC 和 ECDSA 等公钥密码系统。量子算法并不意味着密码学的终结，因为：
- 只有部分密码系统不具备抗量子能力（如 RSA、DHKE、ECC、ECDSA 和 ECDH）。
- 某些密码系统具备抗量子能力，只会受到轻微影响（如密码学哈希、MAC 算法和对称密钥密码）。
下面详细讨论这些问题。
抗量子与可被量子破解的密码算法
大多数密码学哈希（如 SHA2、SHA3、BLAKE2）、MAC 算法（如 HMAC 和 CMAC）和密钥派生函数（bcrypt、Scrypt、Argon2）基本上都具备抗量子能力（只受量子计算轻微影响）。
- 使用 384 位或更长的长度以抵抗量子攻击（256 位在很长一段时间内应该也足够）
对称密码（如 AES-256、Twofish-256）具备抗量子能力。
- 使用 256 位或更长的密钥（不要使用 128 位 AES）
大多数流行的公钥密码系统（如 RSA、DSA、ECDSA、EdDSA、DHKE、ECDH、ElGamal）都可被量子计算破解！
- 大多数数字签名算法（如 RSA、ECDSA、EdDSA）都可被量子计算破解！
- 抗量子签名算法和公钥密码系统已经问世（如基于格或基于哈希的签名），但由于其密钥和签名比 ECC 更长，尚未得到大规模应用。
参见 https://en.wikipedia.org/wiki/Post-quantum_cryptography
...
抗量子密码算法
...
ECC 密码学和大多数数字签名都可被量子计算破解！
...
使用具有 5k+1 个量子比特的量子计算机（采用 Shor 算法），可以在 O(k^3) 阶时间内分解一个 k 位数字。
使用 1281 个量子比特和 72*256^3 次量子运算，可以分解 256 位数字（如比特币公钥）。
- 约 12 亿次运算，即在性能良好的机器上不到 1 秒
ECDSA、DSA、RSA、ElGamal、DHKE、ECDH 密码系统均可被量子计算破解
结论：公开已签名交易（如以太坊的做法）并不具备抗量子能力 -> 应避免泄露 ECC 公钥
哈希具备抗量子能力
密码学哈希（如 SHA2、SHA3、BLAKE2）被认为具备抗量子能力：
- 在传统计算机上，寻找 256 位哈希碰撞需要 √2^256 步（使用生日攻击）-> SHA256 具有 2^128 的密码强度
- 量子计算机可能通过 ∛2^256 次运算找到哈希碰撞（参见 BHT 算法），但这一点存在争议（参见 Bernstein 2009）。
- 理论上，找到 SHA256 / SHA3-256 碰撞可能需要 2^85 次量子运算，但实际成本可能高得多。
结论：SHA256 / SHA3-256 很可能具备抗量子能力
- SHA384、SHA512、SHA3-384 和 SHA3-512 具备抗量子能力
...
对称密码具备抗量子能力
...
大多数对称密码（如 AES 和 ChaCha20）都具备抗量子能力：
- Grover 算法使用 √𝑁 次量子运算找到 AES 密钥。
- 量子时代会使对称密码的密钥长度翻倍，参见 http://cr.yp.to/codes/grovercode-20100303.pdf。
后量子时代的 AES-256 相当于此前的 AES-128
- 128 位或更短的对称密码可受到量子攻击
结论：256 位对称密码通常具备抗量子能力
- AES-256、ChaCha20-256、Twofish-256、Camellia-256 被认为具备抗量子能力
后量子密码学
...
抗量子密钥协商：https://en.wikipedia.org/wiki/CECPQ1
https://ianix.com/pqcrypto/pqcrypto-deployment.html
后量子签名方案 XMSS：
- https://tools.ietf.org/html/rfc8391
- JS XMSS - https://www.npmjs.com/package/xmss
- 后量子密钥协商方案 McEliece 和 NewHope
后量子签名和密钥协商（XMSS、McEliece、NewHope）：\ https://github.com/randombit/botan
QC-MDPC 和 libPQC 可被量子计算破解：https://eprint.iacr.org/2016/858.pdf
基于哈希的公钥密码学
...
基于编码的公钥密码学
...
基于格的公钥密码学
...
GLYPH 签名（基于格的 Ring-LWE 格、Ring-LWE、环上带误差学习）
BLISS - http://bliss.di.ens.fr
NewHope
- Go 实现：https://github.com/Yawning/newhope
- Python 实现：https://github.com/scottwn/PyNewHope
- Python 实现：https://github.com/anupsv/NewHope-Key-Exchange
XMSS
NTRU：NTRUEncrypt 和 NTRUSign
基于零知识证明
PICNIC - https://github.com/Microsoft/Picnic
基于多元二次方程的公钥密码学
Rainbow: https://github.com/bcgit/bc-java/tree/master/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow
...
抗量子密码学库
抗量子密码学仍处于发展初期，尚不成熟，也未得到大多数密码学库和 Web 浏览器、OpenSSL、OpenSSH 等工具的广泛支持。以下是一些发展较为完善的抗量子密码算法库：
- liboqs（Open Quantum Safe）- https://github.com/open-quantum-safe/liboqs
- Bouncy Castle PQC - https://github.com/bcgit/bc-java/tree/master/core/src/main/java/org/bouncycastle/pqc/crypto
Python 中的 SPHINCS+ 签名
https://github.com/sphincs/pyspx
https://pypi.org/project/PySPX