【本科课程项目分享】凯撒密码的统计法破解分析

Ray

本贴用于分享笔者的“计算机与问题求解”课程项目《凯撒密码的统计法破解分析》。

题目要求如下：
凯撒密码（Caesar cipher）是一种替换加密方式，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移形成密文，如当偏移量为3时，所有字母A被替换为D,B被替换为E,以此类推。然而，凯撒密码非常容易被破解，攻击者可以通过使用字母频率分析的方法，找到字母替换的规律从而破解密码。当密文长度足够大时，可以先分析密文中每个字母出现的频率，然后将这一频率与正常情况下的该语言字母表中所有字母的出现频率做比较。英文字母表中字母出现频率如下图所示。

本题提供文本加密、字母频率统计以及频率分析法破解精度计算的Python3程序，请使用该程序进行以下分析：
(1)分析不同错误容忍度（程序中tolerance超参数）对破解精度的影响。
(2)分析不同的加密文本长度对破解精度的影响
(3)分析不同类型的文本（学术、小说、新闻…）对破解精度的影响
(4)分析同一类型中不同主题的文本（如新闻文本包含科技、政治、体育等不同主题）对破解精度的影响。
需要提交：
（1）程序文档，文档结构包括：问题描述、主要算法或者模型、实验数据及分析、有关说明（如引用他人程序说明）；
（2）程序源代码，其中需要包含注释，以及程序运行环境的说明；
（3）提交方式略。


楼下施工正文。

Ray

一、问题描述

   凯撒密码（Caesar cipher）是一种替换加密方式，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移形成密文，如当偏移量为3时，所有字母A被替换为D,B被替换为E,以此类推。然而，凯撒密码非常容易被破解，攻击者可以通过使用字母频率分析的方法，找到字母替换的规律从而破解密码。当密文长度足够大时，可以先分析密文中每个字母出现的频率，然后将这一频率与正常情况下的该语言字母表中所有字母的出现频率做比较。本文档中将使用上述方法，对使用凯撒密码加密的文本进行破解。

   在实际破解过程中，破解精度受到多个因素的影响。首先，我们可以通过分析容忍度来理解破解结果的准确性。容忍度指的是允许破译字母与真实字母在标准频率表的位置偏差，代表了破解的精确度。其次，加密文本的长度对字母频率统计的稳定性有重要影响，较长的文本中不同字母的频率分布服从大数定律，意味其通常能提供更可靠的频率分布，使破解更加准确。此外，文本类型（如学术文本、小说、新闻等）与主题（如科技、政治、体育等新闻）也会因专业术语和常用词汇的不同而呈现出不同的语用习惯。这或许会导致其字母频率分布与标准表存在差异，进而影响破解效果。

   本文档旨在分析

      (1)不同错误容忍度

      (2)不同加密文本长度

      (3)不同文本类型

      (4)同一类型中不同文本主题

   对破解精度的影响。

Ray

二、算法阐释

   本实验代码基于凯撒密码加密原理与字母频率分析技术，实现了文本加密、频率统计、批处理、容忍度-正确率评估及权方正确率评估等功能。以下对核心算法模块进行详细阐释。

   Encrypt函数采用通过固定偏移量实现字符替换。该算法对大小写字母分别处理，保持原文非字母字符不变。通过模运算确保偏移后的字母仍在字母表范围内，形成循环替换。

   get_letter_frequency函数实现文本字母频率统计分析。该函数首先统计文本中总字母数，然后遍历文本累加各字母出现次数，最后通过归一化处理得到各字母的频率分布。

   针对传统容忍度算法的局限性，本实验提出权方正确率评估get_weighted_accuracy函数。该算法采用平方函数对排名偏差进行惩罚，偏差越大惩罚力度呈二次增长，各字母对总分的贡献度与其在文本中的出现频率成正比，从而避免传统容忍度算法的二分判断，提供更细腻的评估结果。

   为实现文本长度的精确控制，为read_file函数增加了截取参数truncate。该函数按字母数而非字符数进行截取，确保T1和T2的取值不受文本长度影响。

   程序采用模块化设计，支持多文件批量处理，设计了process_single_file函数，主程序通过遍历输入目录调用该函数，实现自动化批量处理，显著提升实验效率。

Ray

三、实验数据选择及分析

3.1 错误容忍度与文本长度对破解精度的影响

   本节同时分析错误容忍度与文本长度对破解精度的影响。

   同时分析这两个因素的动机在于其补偿关系，即较长的文本可以在更低的容忍度下达到相同的破解精度，而较短的文本则需要更高的容忍度来补偿统计数据的不足。进行单因子变化分析无法捕捉到这一关系。同时分析这两个维度亦有助于理解下文提出权方正确率的动机。

   本节笔者截取了A Strong Appeal.doc第一章正文中的前250、500、1000、2000、4000与8000有效英语字母作为实验数据。加密后使用代码分析六段文本在容忍度为1~8的情况下的解密正确率。数据见下表，可视化见图1。

表1. 解密正确率—字母数/容忍度表

	T1	T2	T3	T4	T5	T6	T7	T8
250	0.558	0.869	0.892	0.892	0.920	0.920	1.000	1.000
500	0.639	0.807	0.920	0.944	1.000	1.000	1.000	1.000
1000	0.442	0.655	0.941	0.964	1.000	1.000	1.000	1.000
2000	0.715	0.814	0.973	0.973	1.000	1.000	1.000	1.000
4000	0.876	0.876	0.951	1.000	1.000	1.000	1.000	1.000
8000	0.902	0.952	1.000	1.000	1.000	1.000	1.000	1.000

图1. 解密正确率—字母数/容忍度三维柱状图

   表1与图1的数据显示，文本长度相同的前提下，错误容忍度越大，解密准确率越高。随着文本长度的增加，达到相同准确率所需的容忍度逐渐降低。例如，250字母文本需要容忍度7才能达到100%准确率，而8000字母文本仅需容忍度3即可实现完全破解。这一现象印证了两个因素的补偿关系，即较长的文本可以在更低的容忍度下达到相同的破解精度，而较短的文本则需要更高的容忍度来补偿统计数据的不足。

   值得注意的是，字母数为1000的文本相比字母数为250的文本，T1低了11%以上。为了分析这一现象，下表列出了字母数为250-1000-4000的不同加密文本切片中的字母频率。频率与标准字母频率相同的标为绿色，偏差为1的标为黄色，偏差为2及以上的标为红色。可以看到，字母数为1000的文本中红色较多，但最高频字母h（对应明文e）符合标准频率分布，而字母数为250的文本中红色较少，但h与标准频率有1位偏差。这在一定程度上体现了容忍度算法的局限性，因为1000字母数的文本相比250字母数的文本提供了更多信息，而这种信息的冗余并不会导致破译变难。

表2. 字母数为250、1000与4000的文本字母频率偏差表

	h	w	d	r	l	q	v	k	u
250	d	h	w	l	q	r	u	v	k
1000	h	r	q	d	w	v	u	l	g
4000	h	d	w	v	r	l	q	k	u

   笔者因此提出计算权方正确率：

   该算法中，25是26个字母的最大可能排名差（从第0位到第25位），作为归一化分母；取平方可对排名偏差进行非线性惩罚，对0-1的位次偏差给予的惩罚大于24-25的位次偏差给予的惩罚；最终将结果归一化到[0,1]区间，便于比较。

权方正确率可对字母数为1000的文本正确对e进行排名给予积极反应。事实上，字母数为250、1000和4000的文本，其权方正确率分别为0.447、0.447与0.434，这相比其在Tolerance1下的正确率，0.558、0.442和0.876更能代表文本的自身频率分布与标准分布的固有匹配程度。

   此外，经笔者验证，权方正确率较高的文本，在文本长度相同的情况下，其达到100%准确率所需的容忍度较低，但反之不适用。

综上，错误容忍度与文本长度仅能体现不同的错误容忍度达到100%准确率与文本长度的补偿关系，而无法客观代表文本的自身频率分布与标准分布的固有匹配程度。这一局限性源于该算法对所有在容忍度外的字母的赋予权重0，而对于容忍度内的字母赋予权重1，是一种离散而二分的评估方式。而笔者提出的权方正确率赋予所有字母非线性惩罚，代表文本内部的一种固有属性，与文本长度相关性低，是一种连续且加权的评估方式，可用于后续小节的进一步分析。

3.2 文本类型与主题对破解精度的影响

   本节基于前文提出的权方正确率、容忍度1和容忍度2三个指标，分析文本类型与主题对破解精度的影响。

实验数据包括文学作品、时事新闻与学术论文三种类型。文学作品主题包括小说、自传与政治经济评论各一；新闻主题包括UN可持续发展城市、CNN文学影视与CNN动物保护各一；学术论文主题包括法律伦理、游戏媒介理论与网络安全各一。每段文本截取前3000字母，从而排除文本长度对容忍度的影响。

表3. 不同文本类型与主题的权方正确率与容忍度表

	小说	自传	政治经济评论	UN可持续发展城市	CNN文学影视	CNN动物保护	法律伦理	游戏媒介理论	网络安全
WAcc	0.433	0.429	0.438	0.454	0.437	0.442	0.452	0.446	0.451
T1	0.806	0.780	0.803	0.802	0.951	0.789	0.768	0.795	0.470
T2	0.950	1.000	0.984	0.960	0.999	0.962	0.952	0.885	0.538

   观察数据显示，联合国可持续发展城市新闻与三篇论文正确率最高，因为此类学术与官方文献通常采用规范严谨的书面语，用词准确且符合标准英语的统计特征。相比之下，CNN新闻报道中包含较多口语化表达与访谈内容，语言风格相对灵活，致使其权方正确率相较UN的新闻略有降低。而自传文本作者为伍迪·艾伦，其语言风格极具个人特色，用词多元且常出现生僻词汇，因而权方正确率为所选文本中最低。

总体而言，不同文本的权方正确率呈现出一定规律：官方文献高于个人访谈，学术性内容高于个性化书写。这一分布趋势与选取文本时的预期基本一致，反映出文本类型与语言规范性对字母频率分布的影响。

   容忍度为1的情况下要求字母的实测频率排名与标准排名差不超过1，该标准过于严格，导致其评估结果易受文本特异性内容的干扰，代表性有限。可以看到，CNN的文学影视新闻的T1值高达0.951，而网络安全论文的T1值仅为0.470，其余均落在0.787±0.019的区间内。前二者巨大差异不符合文本选择的预期，且其余值没有区分度。采用该指标无法进行有效区分。

   容忍度为2的情况允许字母排名在标准排名的前后共5个位置内浮动，此宽松条件导致该指标在多数文本在字母数达到3000时即可迅速达到极高的准确率，从而丧失了有效的区分能力。在九类不同文本中，有六类文本的T2值均超过0.95。这表明T2指标对于中等长度的大多数文本类型而言，其评估已趋于饱和，无法进一步揭示不同文本在频率分布上存在的细小差异。

   综上，通过对三类评估指标的对比分析可见：权方正确率能够稳定反映不同文本类型与主题在字母频率分布上的内在差异，其评估结果与文本的语言规范性程度高度吻合，呈现官方文献高于个人访谈，学术性内容高于个性化书写的特征，证明了该指标在衡量文本固有统计特性方面的有效性与区分度。

相比之下，容忍度指标在评估中则显现出明显局限：T1因标准过于严苛，区分度与稳定性均有限；T2则因标准过于宽松，在中等长度文本上即出现评估饱和，丧失了区分不同文本类型的能力。

因此，在分析文本类型与主题对频率分析法破解精度的影响时，权方正确率相比传统容忍度指标更具参考价值。

Ray

四、其他说明与心得

   本报告中的代码主要部分由课程组提供，额外功能由笔者借由大语言模型初步完成，后续调试与改正由笔者手动完成。千问大模型在代码书写任务上的速度快于DeepSeek，但是二者准确率均一般，经常写出形式上正确而内核上错误的代码。

权方准确率指标由笔者提出，动机在于：

   1. 直觉觉得容忍度指标是一种二分指标，对噪声抗性差，扰动程度大，不具有代表性，需要进行多层化或梯度化处理，笔者选择了后者；

   2. 发现字母数增加后，同一容忍度下的正确率反而降低了（见3.1）；

   3. 自由文体应当比官方文体破译难度更大，但容忍度无法反馈这一特点。

一个设计良好的评估指标应能稳定地反映研究对象的内在属性，而非被偶然因素或指标自身的设计缺陷所干扰。从容忍度指标向权方正确率指标的转变，意味着从关注“绝对正确的字母数量”转向关注“整体分布的相似度”，这更加符合破译密码的概率本质。

Ray

以上是正文。

可以看出，课程对于项目中使用AI和一定程度上的建构有包容性。该项目作为面向全校（而非面对计算机学院）的计算机课程的第一个大作业而言难度适中，并且课程组已提供大部分代码，仅需调参即可。但是课程组同样鼓励进一步调试代码。代码如下，供参考：

• import os
• 
  
• OFFSET = 3  
• NUMBER_OF_LETTERS = 26  
• LETTER_FREQUENCY_TABLE = ['e','t','a','o','i','n','s','h','r','d','l','c','u','m','w',
• 'f','g','y','p','b','v','k','j','x','q','z']
• 
  
• def read_file(path, truncate=None):
•     """Read file function
•     Args:
•         path (str): The path of the file to read.
•         truncate (int, optional): Only read first N letters from the file.
•    
•     Returns:
•         text (str): The text content of the file.
•     """
•     with open(path,"r", encoding='UTF-8') as f:
•         text = f.read()
•         if truncate is not None:
•             truncated_text = ''
•             letter_count = 0
•             for char in text:
•                 if letter_count >= truncate:
•                     break
•                 truncated_text += char
•                 if (char >= 'A' and char <= 'Z') or (char >= 'a' and char <= 'z'):
•                     letter_count += 1
•             text = truncated_text
•         return text
• 
  
• def encrypt(text):
•     """Replacement encryption function
• 
  
•     Replace letters with the Caesar method: ASCII + OFFSET
• 
  
•     Args:
•         text (str): The text content of the original file.
•    
•     Returns:
•         encrypted_text (str): The encrypted text.
•     """
•     encrypted_text = ''
•     for c in text:
•         if c >= 'A' and c <= 'Z':
•             encrypted_text += chr(ord('A') + (ord(c)-ord('A') + OFFSET) % NUMBER_OF_LETTERS)
•         elif c >= 'a' and c <= 'z':
•             encrypted_text += chr(ord('a') + (ord(c)-ord('a') + OFFSET) % NUMBER_OF_LETTERS)
•         else:
•             encrypted_text += c
•     return encrypted_text
• 
  
• def save_to_file(text, path):
•     """Save the result to a file
• 
  
•     Args:
•         text (str): The text content of the file to save.
•         path (str): The path of the file to save.
•    
•     Returns:
•         (None)
•     """
•     with open(path, "w", encoding='UTF-8') as f:
•         f.write(text)
• 
  
• def get_letter_count(text):
•     """Count letters in the text
• 
  
•     Args:
•         text (str): The text to count letters.
•    
•     Returns:
•         letter_count (int): The number of letters in the text.
• 
  
•     """
•     letter_count = 0
•     for c in text:
•         if(c >= 'A' and c <= 'Z' ) or (c >= 'a' and c <= 'z'):
•             letter_count += 1
•     return letter_count
• 
  
• def get_letter_frequency(text):
•     """Letter frequency statistics on text
•    
•     Args:
•         text (str): The text to calculate letter frequency.
• 
  
•     Returns:
•         letter_frequency (dict): An unordered dictionary of the letter frequency,
•         i.e., {Key (char): letter, Value (float): frequency of the letter}
•     """
•     letter_count = get_letter_count(text)
•     letter_frequency = {}
• 
  
•     for c in text:
•         if(c >= 'A' and c <= 'Z' ) or (c >= 'a' and c <= 'z'):
•             if c.lower() in letter_frequency.keys():
•                 letter_frequency[c.lower()] += 1
•             else:
•                 letter_frequency[c.lower()] = 1
• 
  
•     for key, value in letter_frequency.items():
•         letter_frequency[key] = value / letter_count
•         
•     return letter_frequency
• 
  
• def get_weighted_accuracy(letter_frequency):
•     """Calculate weighted accuracy using squared penalty
• 
  
•    
•     Args:
•         letter_frequency (dict): A dictionary of the letter frequency
•         
•     Returns:
•         weighted_accuracy (float): Weighted accuracy score [0,1]
•     """
•     sorted_freq = sorted(letter_frequency.items(), key=lambda x:x[1], reverse=True)
•     frequency_table = [i[0] for i in sorted_freq]
•    
•     weighted_accuracy = 0
•     max_rank_diff = 25
•    
•     for letter, freq in letter_frequency.items():
•         actual_rank = frequency_table.index(letter)
•         standard_rank = LETTER_FREQUENCY_TABLE.index(letter) if letter in LETTER_FREQUENCY_TABLE else max_rank_diff
•         rank_diff = abs(actual_rank - standard_rank)
•         letter_score = ((max_rank_diff - rank_diff) ** 2) / (max_rank_diff ** 2)
•         weighted_accuracy += freq * letter_score
•    
•     return weighted_accuracy
• 
  
• def get_accuracy(origin_text, encrypted_text, letter_frequency, tol=1):
•     """Calculate the decryption accuracy of the letter frequency method
• 
  
•     Args:
•         origin_text (str): The text content of the original file, i.e., the ground-truth.
•         encrypted_text (str): The encrypted text obtained by the Caesar method.
•         letter_frequency (dict): A dictionary of the letter frequency obtained by the `get_letter_frequency()` function.
•         tol (int, default=1): A hyperparameter to adjust the error tolerance.
• 
  
•     Returns:
•         accuracy (float): The decryption accuracy of the letter frequency method
•     """
•     letter_frequency = sorted(letter_frequency.items(), key=lambda x:x[1], reverse=True)
•     frequency_table = [i[0] for i in letter_frequency]
•     letter_count = get_letter_count(origin_text)
• 
  
•     count = 0
•     for i, c in enumerate(encrypted_text):
•         if(c >= 'A' and c <= 'Z' ) or (c >= 'a' and c <= 'z'):
•             idx = frequency_table.index(c.lower())
•             candidates = LETTER_FREQUENCY_TABLE[max(idx-tol, 0) : min(idx+tol+1, NUMBER_OF_LETTERS)]
•             if(origin_text.lower() in candidates):
•                 count += 1
•    
•     accuracy = count / letter_count
•     return accuracy
• 
  
• def print_letter_frequency(letter_frequency):
•     """Print the letter frequency
• 
  
•     Print the letter frequency with the format: "letter : frequency of the letter"
• 
  
•     Args:
•         letter_frequency (dict): A dictionary of the letter frequency obtained by the `get_letter_frequency()` function.
• 
  
•     Returns:
•         (None)
•     """
•     letter_frequency = sorted(letter_frequency.items(), key=lambda x:x[1], reverse=True)
•     for c, f in letter_frequency:
•         print("%c : %f"%(c, f))
• 
  
• def process_single_file(input_path, output_dir, truncate=None):
•     """Process a single file and generate report
•    
•     Args:
•         input_path (str): Path to the input file
•         output_dir (str): Directory to save output reports
•         truncate (int, optional): Only process first N letters from the file.
•    
•     Returns:
•         (None)
•     """
•     filename = os.path.basename(input_path)
•     output_filename = f"re_{filename}"
•     output_path = os.path.join(output_dir, output_filename)
•    
•     text = read_file(input_path, truncate=truncate)
•     en_text = encrypt(text)
•    
•     en_letter_frequency = get_letter_frequency(en_text)
•     letter_count = get_letter_count(text)
•    
•     report_content = []
•     if truncate:
•         report_content.append(f"Processing file: {filename} (first {truncate} letters)")
•     else:
•         report_content.append(f"Processing file: {filename}")
•     report_content.append("")
•     report_content.append("The letter frequency of the encrypted text:")
•    
•     sorted_freq = sorted(en_letter_frequency.items(), key=lambda x:x[1], reverse=True)
•     for c, f in sorted_freq:
•         report_content.append("%c : %f"%(c, f))
•     report_content.append("")
•     report_content.append("-" * 50)
•     report_content.append("")
•    
•     weighted_acc = get_weighted_accuracy(en_letter_frequency)
•     report_content.append(f"Weighted accuracy: {weighted_acc:.6f}")
•     report_content.append("")
•    
•     report_content.append("Accuracy for different tolerance values:")
•     for tol in range(1, 9):
•         accuracy = get_accuracy(text, en_text, en_letter_frequency, tol=tol)
•         report_content.append(f"Tolerance {tol}: {accuracy:.6f}")
•     report_content.append("")
•     report_content.append("-" * 50)
•     report_content.append("")
•     report_content.append(f"The total number of letters in the origin text is {letter_count}.")
•    
•     final_report = "\n".join(report_content)
•     print("=" * 50)
•     print(final_report)
•    
•     save_to_file(final_report, output_path)
•     print()
•     print("-" * 50)
•     print()
•     print(f"Report saved to: {output_path}")
•     print()
•     print("=" * 50)
•     print()
•     print()
• 
  
• if __name__ == '__main__':
•     input_dir = "./input"
•     output_dir = "./output"
•    
•     if not os.path.exists(output_dir):
•         os.makedirs(output_dir)
•    
•     if os.path.exists(input_dir):
•         txt_files = [f for f in os.listdir(input_dir) if f.endswith('.txt')]
•         
•         if not txt_files:
•             print(f"No .txt files found in {input_dir}")
•         else:
•             print(f"Found {len(txt_files)} .txt files to process")
•             print("=" * 40)
•             
•             for filename in txt_files:
•                 input_path = os.path.join(input_dir, filename)
•                 process_single_file(input_path, output_dir, truncate = 3000)
•                
•     else:
•         print(f"Input directory {input_dir} does not exist")
  

至此施工完毕。