C++ 程序对单表替换密码进行字母频率攻击

引言

单字母替换密码多年来一直被用于隐藏和编码消息。在这些密码中，明文中的每个字母都被密文中的一个固定字母替换。尽管这些密码易于理解和应用，但它们也很容易受到字母频率攻击等攻击。

问题陈述

字母频率攻击的主要目标是破解单字母替换密码，而无需知道密钥。它通过比较密文中字母的频率与该语言（例如，英语）中字母出现的假定分布来实现。通过发现相似的模式并运用统计学，可以对密钥进行一些逻辑猜测，从而解密消息。

方法

为了对任何密文进行字母频率攻击，我们应该采取以下步骤

1. 首先，找出每个字母在此文本中出现的频率。
2. 接下来，通过与该书面语言（例如，英语）的标准频率进行比较，衡量每个字符出现的频率。
3. 通过频率分析尝试初步猜测可能用作密钥的内容。
4. 使用此假设代码或猜测的密钥进行解密并检查结果。
5. 细化此结果，直到获得可读的明文。

代码实现

让我们在 C++ 中实现一个简单的字母频率攻击来解密单字母替换密码。我们将假设输入的密文是大写的，并且只包含字母（没有空格或标点符号）。

输出

Decrypted plaintext: IAT JNFCY LOEZV MES GNBKX EQTO IAT PDRH UEW

说明

1. 计算字母频率（calculateFrequency 函数）
   
   • 在此示例中，用于计算字母频率的函数是 calculateFrequency。
   • 此函数接受一个名为 text 的字符串（在本例中，它恰好是密文）。
   • 执行此操作后，它会遍历文本中的所有字符。
   • 如果它是字母，它会转换为大写并增加其在 freq 映射中的频率计数。
   • 它返回一个包含输入文本中每个字母频率的 freq 映射。
2. 执行字母频率攻击（letterFrequencyAttack 函数）
   
   • 它将密文作为输入。
   • 使用 calculateFrequency 函数计算密文中每个字母的频率。
   • 创建一个字符串 englishFreq，它表示标准的英语字母频率（从最多到最少）。

根据频率分析猜测密钥

• 对于标准英语频率字符串中的每个字母，找出密文中出现最多的字符并将其分配为可能的替换。
• 猜测的密钥存储在密钥映射中。

使用猜测的密钥解密密文

• 遍历密文中的每个字符。
• 如果它是字母，则将其转换为大写并用密钥中的相应元素替换。如果不是字母，则不做任何操作。
• 它返回解密的明文。

3. 主函数 (main)

• 它创建带有加密消息的字符串密文。
• 调用 letterFrequencyAttack 并使用密文并将其存储在明文中。
• 将解密的明文打印到控制台。

时间复杂度和空间复杂度

1. 时间复杂度

计算字母频率（calculateFrequency 函数）

• 时间复杂度：O(n)，其中 n 是输入文本（密文）的长度。这是因为我们遍历文本中的每个字符一次。

执行字母频率攻击（letterFrequencyAttack 函数）

• 对于英语频率字符串中的每个字母，找出密文中出现频率最高的字母：O (26 * n)，其中 n 是输入文本（密文）的长度。在这里，对于英语频率字符串中的每个字母，我们遍历密文中的所有字符以找出出现频率最高的字符。
• 使用猜测的密钥解密密文：O(n)，其中 n 是输入文本（密文）的长度。这是因为我们遍历密文中的每个字符一次以解密它。
• 总体时间复杂度：O(n)，其中 n 是输入文本（密文）的长度。解密步骤占主导地位。

2. 空间复杂度

• 计算空间复杂度可以通过使用方程 (n) 最好地解释。
• 存储密文中每个字母的频率（函数 calculateFrequency）：O(26) = O(1)，因为字母表中的字母数量是固定的。
• 存储猜测的密钥（key 映射）：O(26) = O(1)，因为字母表中的字母数量是固定的。
• 存储解密的明文：O(n)，其中 n 是输入文本（密文）的长度，因为明文的大小等于密文的大小。
• 总体空间复杂度：O(n)，其中 n 是输入文本（密文）的长度。

C 语言中单字母替换密码的优点

1. 简单性：字母频率攻击背后的概念简单明了。它依赖于对任何给定编码消息中发现的字母频率进行基本统计分析。
2. 效率：在许多情况下，通过应用字母频率攻击，可以相对快速地破解单字母替换密码。这使得它适用于解密简单密码，而无需大量的计算资源。
3. 无需先验知识：在这些攻击期间，不需要有关加密过程或所用密钥的先验知识。它们只依赖于明文所用给定语言中单个字母的出现频率。
4. 适用性：字母频率攻击对任何语言的单字母替换密码都有效。这使其成为一种用于解密使用此类密码加密的消息的多功能技术。
5. 教育价值：实施和理解字母频率攻击可以作为学习密码学、统计分析和编程的教育练习。它提供了对简单加密技术的漏洞和更强加密方法重要性的深入了解。
6. 进一步分析的基础：虽然字母频率攻击可能并非总是能完全解密密文，但它可以为更高级的密码分析技术提供一个起点。密码分析师可以通过识别常见模式并对密钥进行有根据的猜测来完善他们的方法并进一步解密消息。

结论

总之，字母频率攻击是解密单字母替换密码的强大工具，但它依赖于明文语言的已知性。它对较长的消息或增加复杂性的密码也效果不佳。因此，对于更安全的加密方案，通常会使用更高级的技术，例如二元组或三元组的频率分析。