encryption - Vigenère 暗号の解読の複雑さ

Question

だから、ヴィジェネールで暗号化されたn個の単語のテキストを解読するのにかかる時間の複雑さを知りたい.

Vigenère は、文字ごとに異なる Caesar シフトを適用しているだけです。Caesar Cipher の場合は O(n) であることがわかっています。これは、単純にすべての異なる 25 シフトを試すためです。しかし、ヴィジェネールはどうですか？

Answer 1

Breaking Cesar のシフトはO(1)で、 ではありませんO(n)。アルファベットのサイズは一定です。所定のキーの下で暗号文の短いストレッチをデコードするだけで、順調に進んでいるかどうかを知ることができます。

Vigenere の暗号では、一連の反復シフトがあります。統計分析なしでそれを破る力ずくの方法はO(26^k)、長さのキーのキースペースに依存しますk。Vigenere の暗号では統計分析が非常に効果的であるため、その実際の強度は、この制限時間によって示唆されるよりもはるかに低くなります。