用Grover算法攻击AES-128

Question

Grover的算法在尝试发现一个秘密AES密钥时需要多少个纯文本/密码文本对？

我试图确定是否有一个设备限制了它从纯文本生成密码文本的速度，是否有助于防止这种攻击。

Answer 1

格罗弗算法是一种在非结构化数据上渐近最优的、复杂度为\mathcal{O}(\sqrt{N})的强力量子算法.\mathcal{O}(\sqrt[3]{N})中也有奥伦森的“量子计算和隐藏变量”。

保证解

的唯一性

需要欧洲央行模式；

让n表示块大小。

设r是不同明文密文对的数目。

让r表示在两个秘密密钥( k_1 \neq k_2 )下同时加密的明文-密文对的数目。

然后，如果r明文不同，则产生不同结果的预期结果；

1- \frac{1}{2^{rn}}

给出了r的一个很好的估计；

r > \lceil 2^k/n \rceil

For AES-128

n=128, k=128 \Rightarrow r=3

For AES-192

n=128, k=192 \Rightarrow r=4

用于AES-256

n=128, k=256 \Rightarrow r=5

有关详细信息，请参阅“将Grover的算法应用于AES:量子资源估计”在#3.1

Answer 2

Grover的算法对于AES 128具有搜索复杂性\sqrt{2^{128}}。在普通的欧洲央行模式下，一个明文/密文对就足够了，因为密码映射是一个置换。

有趣的是，最近Grover算法和Simon算法的结合被用于：

将经典的高级幻灯片攻击(由Biryukov和Wagner引入)转换为量子攻击，从而提高时间复杂度的指数速度。

引文纸的作者包括王晓云，他对MD5和早期版本的SHA提出了最好的攻击。

具体来说，他们将量子幻灯片攻击扩展到Feistel密码。

编辑：

对于具有n位键的n比特分组密码，原始的幻灯片攻击具有O(2^{n/2})复杂性，并且需要尽可能多的明文/密文对。

上面引用的题名/责任者: L.需要O(n)复杂度，但是根据上面引用的文件，需要对Feistel密码进行修改。