encryption - 破解维吉尼亚密码的复杂性

Question

所以我想知道解密由 bt Vigenère 加密的 n 个单词的文本的时间复杂度是多少。

Vigenère 只是对每个字母应用不同的凯撒位移。我知道对于凯撒密码来说它只是 O(n) 因为我们只是尝试所有不同的 25 班次。但是维热内尔呢？

Answer 1

打破凯撒的转变是O(1)，不是O(n)。字母的大小是恒定的。您只需要在给定密钥下解码一小段密文，就可以知道您是否在正确的轨道上。

对于 Vigenere 的密码，您有重复移位的序列。没有统计分析的暴力破解方法取决于密钥空间，即O(26^k)长度为 的密钥k。因为统计分析对 Vigenere 的密码非常有效，所以它的实际强度比这个时间限制所暗示的要低得多。