systemslibrarian/crypto-lab-grover

# crypto-lab-grover ## 它是什么 Grover 算法（Lov Grover，1996）是一种量子搜索算法，它使用 O(√N) 次查询在包含 N 个项目的非结构化搜索空间中找到特定项目——相比经典的暴力破解实现了二次加速。本演示通过精确的数学公式对完整的振幅放大过程进行经典模拟：Oracle 相位反转、关于均值反转的扩散，以及包括超过最优迭代次数时的过冲在内的概率振荡。其安全模型是对称密码学——Grover 是针对 AES、SHA 和 HMAC 的量子威胁，而 Shor 算法对此并无影响。Grover 的加速已被证明是最优的（BBBV 下界）；没有任何量子算法能以快于 O(√N) 的速度进行搜索。 ## 何时使用 - **理解为什么 AES-256 保持了强大的后量子安全裕度而 AES-128 被削弱** —— 在理想化的 Grover 假设下，有效密钥长度会减半：AES-128 降至约 2^64 次有效操作（潜在可行），而 AES-256 降至约 2^128（依然强健）。在实践中，电路深度使得实际成本远高于这些标题数字。 - **将 Grover 的过程可视化为旋转** —— Grover 算法的每一步*就是*两次反射（Oracle + 扩散），它们在由 |target⟩ 和错误答案张成的平面中组合成 2θ 的旋转。演示展示了状态向量在单位圆上的旋转，因此振幅的集中和过冲变成了直观的几何事实，而非抽象公式。 - **分别查看 Oracle 和扩散过程** —— “显示 Oracle + 扩散子步骤”开关将一次迭代拆分为两次截然不同的反射：Oracle 将目标振幅翻转为*负值*（可见为向下的柱状图），然后扩散过程将每个振幅关于均值（带符号柱状图上的金色均值线）进行反转。这种分解是精确的——它与闭式解 sin((2k+1)θ) 在浮点精度下完全一致。 - **讲解过冲现象** —— 概率曲线和旋转视图共同展示了为什么在超过 k* = π/4·√N 后运行更多的 Grover 迭代实际上会降低成功概率：状态向量旋转*越过了*目标轴。 - **将 Grover 和 Shor 作为互补的量子威胁进行比较** —— 并排比较表澄清了它们各自破解了哪些算法以及相应的缓解措施是什么。 - **不要将其用于公钥密码学威胁** —— Grover 不影响 RSA、ECC 或 Diffie-Hellman；那是 Shor 算法的领域。 ## 在线演示 **[systemslibrarian.github.io/crypto-lab-grover](https://systemslibrarian.github.io/crypto-lab-grover/)** 调整量子比特数量（n = 2–20）以调整搜索空间大小，逐步执行 Grover 迭代或自动运行，并观察状态向量向目标旋转，同时带符号的振幅柱状图逐渐集中。启用“显示 Oracle + 扩散子步骤”可将每次迭代作为两次反射来演示。演示还包含了带有交互式密钥大小选择器的 AES-128/192/256 量子影响分析、哈希函数安全表（从 MD5 到 SHA3-512），以及经典与量子搜索竞速动画。 你可以使用查询参数深层链接到特定状态——例如，`?steps=3` 会直接跳转到最优迭代，而 `?sub=1&steps=1` 会在 Oracle 子步骤处打开。 ## 可能出现的问题 - **将密钥减半字面理解为实际可行性** —— “AES-128 → 2^64”是一个理想化的查询次数；每次迭代的 Oracle 都是一个完整的 AES 电路，且 Grover 本质上是串行的，因此实际成本要高得多，AES-128 在现实中并不会被它破解。 - **假设 Grover 可以通过并行化消除深度** —— 它最多只提供二次加速，并且将其拆分到多台机器上也会分摊掉 √N 的收益；你无法像经典搜索并行化那样，通过暴力破解来降低电路深度。 - **运行过多迭代** —— 超过 k* = π/4·√N 后，状态会旋转越过目标，导致成功概率下降（过冲）；迭代次数越多并不一定越好。 - **将其应用于错误的密码原型** —— Grover 威胁的是对称密钥和哈希原像，而不是 RSA/ECC/DH（那是 Shor 算法）。将两者混淆会误述风险。 - **认为 O(√N) 是可以被超越的** —— BBBV 界证明了没有量子搜索能做得更好；假设未来会出现更快的通用搜索算法是毫无根据的。 ## 实际应用场景 - **后量子对称密码选型** —— NIST CNSA 2.0 推荐 AES-256（以及更大的哈希输出），这样即使有效强度减半，依然能越过安全门槛。 - **哈希安全裕度** —— Grover 使原像抗性减半，因此 SHA-256 在抵御量子攻击者时仍能提供约 128 位原像安全性；哈希输出大小的选择正是考虑到了这一点。 - **量子资源估算** —— Grassl 等人及其后续研究估算了在 AES 上运行 Grover 所需的量子比特和电路深度，为标准制定决策提供了依据。 - **迁移规划** —— 对称密码原型大多只需要更大的参数，而不需要替换，这与公钥密码学不同，Shor 算法迫使公钥密码学完全转向后量子方案。 ## 如何在本地运行 ``` git clone https://github.com/systemslibrarian/crypto-lab-grover cd crypto-lab-grover npm install npm run dev ``` ## 相关演示 - [crypto-lab-shor](https://systemslibrarian.github.io/crypto-lab-shor/) —— 互补的量子威胁：Shor 破解公钥（RSA/ECC），而 Grover 只对对称密码造成冲击。 - [crypto-lab-harvest-vault](https://systemslibrarian.github.io/crypto-lab-harvest-vault/) —— 现在收集，以后解密以及由这种加速促成的 Q-Day（量子日）时间线。 - [crypto-lab-aes-modes](https://systemslibrarian.github.io/crypto-lab-aes-modes/) —— 受到 Grover 密钥大小压力影响的 AES 模式。 - [crypto-lab-hash-zoo](https://systemslibrarian.github.io/crypto-lab-hash-zoo/) —— 原像抗性被 Grover 减半的哈希函数。 - [crypto-lab-bb84](https://systemslibrarian.github.io/crypto-lab-bb84/) —— 量子密钥分发，故事中量子防御的一面。 ## 学习工具 除了自由探索之外，该演示旨在进行主动教学： - **引导式课程** —— 一条分为 5 个阶段的路径（搜索设置 → Oracle + 扩散 → 旋转模型 → 过冲 → 密码学影响），可逐步引导模拟器。 - **预测模式** —— 在每次“步进”揭示答案之前，提交一个猜测（概率会上升、下降还是保持不变？）。 - **动态纠错面板** —— 在你可能产生错误认知的时刻浮现正确的纠正（Oracle ≠ “检查所有密钥”、过冲、k* ≠ 确定性、Grover ≠ Shor）。 - **比较心智模型** —— 在代数、几何和振幅视图中切换查看*相同*的过冲事实。 - **测量模拟器** —— “测量 ×100”对当前状态进行采样，让“概率 ≠ 确定性”变得具体可感。 - **数学层** —— 实时方程（θ、sin²((2k+1)θ)、k*）并代入当前数值。 - **Oracle 成本预算** —— 将标题上的 2^(n/2) 次*迭代*与每次 Oracle 调用的成本（完整的 AES 电路）区分开来，并提供逻辑量子比特和深度的具体数值。 - **挑战模式** —— 简短的问题，并提供即时的解释性反馈。 - **假设与来源表**，以及区分易混淆术语（振幅与概率、原像与碰撞、对称与公钥）的本地**词汇表**。 如需课堂教学，请参阅[教学指南](docs/TEACHING.md) —— 包含教案（15 分钟和 45 分钟）、讨论问题、可打印的练习题，以及挑战模式的答案。 ## 来源 1. **Grover, L. K.** (1996). "A fast quantum mechanical algorithm for database search." *Proceedings of the 28th Annual ACM Symposium on Theory of Computing*, pp. 212–219. 2. **Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U.** (1997). "Strengths and weaknesses of quantum computing." *SIAM Journal on Computing*, 26(5), pp. 1510–1523.（BBBV 下界 —— 证明 Grover 的 O(√N) 是最优的。） 3. **Grassl, M., Langenberg, B., Roetteler, M., & Steinwandt, R.** (2016). "Applying Grover's algorithm to AES: Quantum resource estimates." *Post-Quantum Cryptography (PQCrypto 2016)*, LNCS 9606, pp. 29–43.（AES 电路深度和量子比特成本估算的来源。） 4. **NIST** (2024). CNSA 2.0 和后量子密码学过渡指南。推荐在后量子对称安全中使用 AES-256。 5. **Nielsen, M. A. & Chuang, I. L.** (2010). *Quantum Computation and Quantum Information*. Cambridge University Press.（振幅放大的标准参考书。） *这是 [Crypto Lab](https://crypto-lab.systemslibrarian.dev/) 套件中 120 多个浏览器演示之一。* *“所以，你们或吃或喝，或做什么事，都要为神的荣耀而行。” —— 哥林多前书 10:31*

标签：后量子安全, 密码学, 手动系统调用, 教育工具, 数据可视化, 暗色界面, 格罗弗算法, 自动化攻击, 量子计算