打破Vigenère密码的复杂性 [英] Complexity of breaking Vigenère cipher

问题描述

所以我想知道什么是解密n个字的文本加密btVigenère的时间复杂度。

So I want to know what is the time complexity of deciphering a text of n words encrypted bt Vigenère.

Vigenère正在为每封信件套用不同的Caesar班次。
我知道对于凯撒密码，它只是O（n）因为我们只是尝试所有不同的25班。但是Vigenère呢？

Vigenère is just applying different Caesar shifts for each letter. I know that for a Caesar Cipher it is just O(n) Because we simply try all different 25 shifts. But what about Vigenère?

推荐答案

破解ceasar的移位 O（1），而不是 O（n）。字母表的大小是不变的。

Breaking Ceasar's shift is O(1), not O(n). The size of the alphabet is constant. You only need to decode a short stretch of the ciphertext under a given key to know if you are on track.

对于Vigenere的密码，你有一系列重复的移位。你只需要解密给定密钥下的一小段密文。在没有统计分析的情况下破坏它的强力方法取决于键长度 k的键 O（26 ^ k） 。因为统计分析对维根塞密码是非常有效的，所以其实际强度比这个时间界限所建议的低得多。

For Vigenere's cipher you have sequence of repeating shifts. The brute-force way to break it without statistical analysis depends on the key space, which is O(26^k) for a key of length k. Because statistical analysis is highly effective on Vigenere's cipher, its actual strength is much lower than would be suggested by this time bound.

这篇关于打破Vigenère密码的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！