如何编写算法来破解Caesar Cipher？

Question

我正在尝试在编程书中进行练习,其中一个练习是解密密文,该密文使用凯撒密码进行未知移位.

这是密文:

HVWGWGHVSPSGHQCADIHSFSLSFQWGSWVOJSSJSFSLDSFWSBQSR

我不知道预期的输出,因为我还没有确定算法.

我已经编写了以下算法来尝试使用Caesar密码对其进行解密,但这是我已经得到的.如何在C#中解密？

string s = "HVWGWGHVSPSGHQCADIHSFSLSFQWGSWVOJSSJSFSLDSFWSBQSR";

int[] freq = new int[26];

for (int i = 0; i < s.Length; i++)
{
  // converting 
  string temp = s.Substring(i, 1); 

  // converting to an array
  int itemp = (int)temp.ToCharArray()[0];

  freq[itemp - 65]++;  
}

for (int i = 0; i < 26; i++)
{
  Console.WriteLine(i + " " + freq[i]);
}

Answer 1

由于这似乎是一项任务,我不打算在C#中给你答案.我将解释算法并在Python中提供解决方案.

Caeser Cipher通过移动字母"N"个空格来工作.如果您在数组中设置了字母:

array = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

这是操纵字母表以查看不同变化的简单方法.

接下来要做的是计算密码中每个字母的出现次数:

count = {}                                                                                                                                                                       
encrypted_string = "HVWGWGHVSPSGHQCADIHSFSLSFQWGSWVOJSSJSFSLDSFWSBQSR"        
for s in encrypted_string:                                                    
    if count.has_key(s):                                                      
        count[s]+=1                                                           
    else:                                                                     
        count[s] = 1                                                          

most_occured = 1                                                              
last_found = ""                                                               
for key in count:                                                             
    if count[key] > most_occured: 
        last_found = key                                                      
        most_occured = count[key] 

这很重要,因为Ceasar Cipher使用正常的字母移位,所得到的密文可以通过频率分析得出,就像普通字母一样.

在英语中,字母"E"最常出现.按理说,在你的密文中最常出现的字母很可能是一个与"E"相对应的移位字母.

因为S在你的密文中最常出现(总共13次),并且鉴于我们知道E最常出现在英语中,我们知道这S很可能E.

鉴于我们知道这是一个凯撒密码,我们可以假设其余的字母移位就像S移位一样.并且E是第5个字母,我们可以做以下数学:

密码文本中最常出现的字母的字母位置 - 字母表中最多出现的字母的位置=要将密文移位到解密的位置的数量

或者,更简洁:

"S"的位置 - "E"的位置= 14:

19 - 5 = 14

这意味着每个字母应该左移14个位置:

decrypted_string = ""                                                  

for s in encrypted_string:                                                
       decrypted_string += array[array.index(s)-14]                         

print decrypted_string   

这将输出以下解密文本:

THISISTHEBESTCOMPUTEREXERCISEIHAVEEVEREXPERIENCED

我故意留下一些东西,比如如何实际进行计算,我在第二个算法中硬编码"14".有些项目需要由执行任务的人员负责.还有一种更快更容易的方法可以做我做的一些事情; 我这样做是为了好玩.