Grover 算法
Grover 算法 是什么?
Grover 算法一种量子搜索算法,可在 N 条记录的无结构数据中以约 sqrt(N) 步找到目标项,对对称密码与哈希函数提供平方级加速。
Grover 算法由 Lov Grover 于 1996 年提出,可在 O(sqrt(N)) 次查询内找到黑盒函数的目标输入,而经典算法需要 O(N) 次。应用于密码学时,它将对称原语与哈希函数的有效安全等级减半:AES-128 的安全强度降至约 64 比特,SHA-256 的原像抗性降至约 128 比特。常见的应对方法是将密钥和摘要长度加倍,例如改用 AES-256 与 SHA-384 或 SHA-512,即便面对 Grover 类攻击也能保留充分的安全余量。与 Shor 算法不同,Grover 本身并不会直接攻破公钥密码体系。
● 示例
- 01
NIST 在评估 AES-128 与 AES-256 的后量子安全性时以其作为参考。
- 02
用于说明为何应将 HMAC 与 KDF 的输出提升到 256 位以上。
● 常见问题
Grover 算法 是什么?
一种量子搜索算法,可在 N 条记录的无结构数据中以约 sqrt(N) 步找到目标项,对对称密码与哈希函数提供平方级加速。 它属于网络安全的 密码学 分类。
Grover 算法 是什么意思?
一种量子搜索算法,可在 N 条记录的无结构数据中以约 sqrt(N) 步找到目标项,对对称密码与哈希函数提供平方级加速。
Grover 算法 是如何工作的?
Grover 算法由 Lov Grover 于 1996 年提出,可在 O(sqrt(N)) 次查询内找到黑盒函数的目标输入,而经典算法需要 O(N) 次。应用于密码学时,它将对称原语与哈希函数的有效安全等级减半:AES-128 的安全强度降至约 64 比特,SHA-256 的原像抗性降至约 128 比特。常见的应对方法是将密钥和摘要长度加倍,例如改用 AES-256 与 SHA-384 或 SHA-512,即便面对 Grover 类攻击也能保留充分的安全余量。与 Shor 算法不同,Grover 本身并不会直接攻破公钥密码体系。
如何防御 Grover 算法?
针对 Grover 算法 的防御通常结合技术控制与运营实践,详见上方完整定义。
Grover 算法 还有哪些其他名称?
常见的别称包括: Grover 搜索算法。
● 相关术语
- cryptography№ 846
后量子密码学
面向经典计算机与大规模量子计算机均能保持安全的经典密码算法体系。
- cryptography№ 020
AES(高级加密标准)
由 NIST 标准化的 128 位分组密码,密钥长度可为 128、192 或 256 位,由 Daemen 与 Rijmen 设计,是全球占主导地位的对称加密算法。
- cryptography№ 247
密码学哈希函数
将任意长度输入映射为固定长度摘要的确定性单向函数,具备抗碰撞、抗原像和抗第二原像三大安全性质。
- cryptography№ 1036
Shor 算法
一种量子算法,可在多项式时间内完成大整数分解和离散对数计算,在足够规模的量子计算机上能够攻破 RSA、Diffie-Hellman 和椭圆曲线密码。
- cryptography№ 1121
对称加密
加密和解密使用同一个秘密密钥的加密方案,在密钥安全分发的前提下提供高速度和强机密性。
- cryptography№ 890
量子密码学
利用量子力学性质(通常是光子的性质)来获得仅靠经典通信无法实现的安全保证的密码学。