Так что я хочу знать, что такое временная сложность расшифровки текста из n слов, зашифрованных bt Vigenère.Сложность разрыва шифрования Vigenère
Vigenère просто применяет различные цезарные сдвиги для каждой буквы. Я знаю, что для Цезарного шифра это просто O (n), потому что мы просто попробуем все разные 25 смен. Но как насчет Вигеньера?
Нарушение сдвига Цезаря O(1), а не O(n). Размер алфавита постоянный. Вам нужно только декодировать короткий фрагмент зашифрованного текста под заданным ключом, чтобы узнать, находитесь ли вы в пути.
Для шифрования Vigenere у вас есть последовательность повторяющихся сдвигов. Метод грубой силы, чтобы разбить его без статистического анализа, зависит от ключевого пространства, которое составляет O(26^k) для ключа длиной k. Поскольку статистический анализ очень эффективен на шифре Вигенаре, его фактическая сила намного ниже, чем предполагалось на этот раз.