一、游戏场景与算法本质
“密码破译”是一类智力游戏：玩家面对一段被某种加密算法处理过的密文，需要通过统计、试错、模式识别等手段还原明文。常见的关卡包括：
– 凯撒密码（字母整体平移）
– 替换密码（每个字母映射到另一个字母）
– 维吉尼亚密码（多表替换）
– 简单 XOR 加密
破解这些密码的算法横跨统计语言学、信息论、回溯搜索与随机优化。本文以”凯撒密码 + 替换密码”为代表，展示如何用 Java 实现频率分析与暴力枚举两套核心方法。
二、密码学基础
2.1 凯撒密码
明文字母 c 通过平移 k 位得到密文 c'：
c' = (c + k) mod 26
破解：枚举 k = 0..25，看哪个 k 解密后英文最”可读”。
2.2 简单替换密码
每个字母被唯一替换为另一个字母。需要：
– 字典：常用英语单词
– 频率分析：英文中 ‘e’ 出现频率最高，约 12.7%
– 模式匹配：相同字母对应相同替换
2.3 维吉尼亚密码
使用密钥 K = k1 k2 ... km 进行多表替换：
c'[i] = (c[i] + k[(i mod m)]) mod 26
破解流程：先通过 Kasiski 检测或 Friedman 测试求出密钥长度 m，再对每列做凯撒破解。
三、凯撒密码：暴力枚举
/**
* 凯撒密码工具
*/
class CaesarCipher {
private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyz";
public static String encrypt(String plain, int shift) {
StringBuilder sb = new StringBuilder();
for (char c : plain.toCharArray()) {
if (Character.isLetter(c)) {
char base = Character.isLowerCase(c) ? 'a' : 'A';
sb.append((char)((c - base + shift) % 26 + base));
} else sb.append(c);
}
return sb.toString();
}
public static String decrypt(String cipher, int shift) {
return encrypt(cipher, 26 - shift);
}
}
四、频率分析工具
import java.util.*;
/**
* 文本频率分析
*/
class FrequencyAnalyzer {
// 英文字母期望频率（%）
static final double[] ENGLISH_FREQ = {
8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 6.094, 6.966, 0.153,
0.772, 4.025, 2.406, 6.749, 7.507, 1.929, 0.095, 5.987, 6.316, 9.056,
2.758, 0.978, 2.361, 0.150, 1.974, 0.074
};
/**
* 统计密文中各字母频率
*/
public static double[] frequencies(String text) {
int[] count = new int[26];
int total = 0;
for (char c : text.toLowerCase().toCharArray()) {
if (c >= 'a' && c <= 'z') { count[c - 'a']++; total++; }
}
double[] freq = new double[26];
for (int i = 0; i < 26; i++) freq[i] = total == 0 ? 0 : 100.0 * count[i] / total;
return freq;
}
/**
* 计算与英文频率分布的差异（卡方距离）
*/
public static double chiSquared(double[] freq) {
double chi = 0;
for (int i = 0; i < 26; i++) {
double diff = freq[i] - ENGLISH_FREQ[i];
chi += diff * diff / Math.max(0.001, ENGLISH_FREQ[i]);
}
return chi;
}
/**
* 凯撒密码破解：枚举 26 种 shift，选 chi 最小
*/
public static int crackCaesar(String cipher) {
int bestShift = 0; double bestChi = Double.MAX_VALUE;
for (int k = 0; k < 26; k++) {
String plain = CaesarCipher.decrypt(cipher, k);
double chi = chiSquared(frequencies(plain));
if (chi < bestChi) { bestChi = chi; bestShift = k; }
}
return bestShift;
}
}
五、替换密码：模拟退火
替换密码有 26! ≈ 4×10²⁶ 种排列，暴力枚举不可能。我们用模拟退火在解空间搜索最优映射。
import java.util.*;
/**
* 替换密码求解器（模拟退火）
*/
class SubstitutionCracker {
String cipherText;
Set<String> dictionary; // 词典：常用英文单词
Map<Character, Character> mapping; // 密文 -> 明文
Random rnd = new Random();
SubstitutionCracker(String cipher, Set<String> dict) {
this.cipherText = cipher.toLowerCase();
this.dictionary = dict;
this.mapping = randomMapping();
}
Map<Character, Character> randomMapping() {
List<Character> letters = new ArrayList<>();
for (char c = 'a'; c <= 'z'; c++) letters.add(c);
Collections.shuffle(letters, rnd);
Map<Character, Character> m = new HashMap<>();
char src = 'a';
for (char dst : letters) m.put(src++, dst);
return m;
}
String decode(String text) {
StringBuilder sb = new StringBuilder();
for (char c : text.toCharArray()) {
if (c >= 'a' && c <= 'z') sb.append(mapping.getOrDefault(c, c));
else sb.append(c);
}
return sb.toString();
}
/**
* 评分：分词命中率 × 字母频率匹配度
*/
double score(String text) {
String[] words = text.split("[^a-z]+");
int hit = 0;
for (String w : words) if (dictionary.contains(w)) hit++;
double wordScore = (double) hit / words.length;
double freqScore = 1.0 / (1.0 + FrequencyAnalyzer.chiSquared(FrequencyAnalyzer.frequencies(text)));
return wordScore * 100 + freqScore * 50;
}
/**
* 模拟退火求解
*/
String solve(int iterations) {
double T = 5.0, cool = 0.9995;
String bestPlain = decode(cipherText);
double bestScore = score(bestPlain);
for (int it = 0; it < iterations; it++) {
// 随机交换两个映射
List<Character> keys = new ArrayList<>(mapping.keySet());
char k1 = keys.get(rnd.nextInt(keys.size()));
char k2 = keys.get(rnd.nextInt(keys.size()));
char tmp = mapping.get(k1); mapping.put(k1, mapping.get(k2)); mapping.put(k2, tmp);
String candidate = decode(cipherText);
double s = score(candidate);
if (s > bestScore || Math.exp((s - bestScore) / T) > rnd.nextDouble()) {
bestScore = s; bestPlain = candidate;
} else {
// 还原
mapping.put(k2, mapping.get(k1)); mapping.put(k1, tmp);
}
T *= cool;
}
return bestPlain;
}
}
六、可运行 Demo
import java.io.*;
import java.nio.file.*;
import java.util.*;
/**
* 密码破译 — 频率分析 + 模拟退火 Demo
* 运行：javac CipherCracker.java && java CipherCracker
*/
public class CipherCracker {
public static void main(String[] args) throws Exception {
// ===== 1. 凯撒密码破解 =====
String plain = "the quick brown fox jumps over the lazy dog and finds a treasure in the forest";
String caesar = CaesarCipher.encrypt(plain, 7);
System.out.println("=== 凯撒密码 ===");
System.out.println("密文：" + caesar);
int shift = FrequencyAnalyzer.crackCaesar(caesar);
System.out.println("破解 shift = " + shift);
System.out.println("明文：" + CaesarCipher.decrypt(caesar, shift));
// ===== 2. 替换密码破解（简化版：使用内置词典） =====
Set<String> dict = new HashSet<>(Arrays.asList(
"the", "a", "an", "is", "are", "of", "to", "and", "in", "on",
"attack", "we", "must", "be", "ready", "before", "dawn", "enemy",
"approaches", "from", "east", "with", "thousand", "soldiers"
));
// 简单替换：将 a<->b, c<->d, ...
String substCipher = "gci jxnrv jrvfg wghl hxnlg hvcg gci mhrh fht hri qhu rci gci ohsigq";
System.out.println("\n=== 替换密码 ===");
System.out.println("密文：" + substCipher);
SubstitutionCracker sc = new SubstitutionCracker(substCipher, dict);
String solved = sc.solve(20000);
System.out.println("破解：" + solved);
// ===== 3. 维吉尼亚密码破解（Kasiski + 列频分析）=====
System.out.println("\n=== 维吉尼亚密码（Kasiski 检测密钥长度）===");
String vKey = "LEMON";
String vPlain = "attackatdawn";
StringBuilder vEnc = new StringBuilder();
for (int i = 0; i < vPlain.length(); i++) {
int shift = vKey.charAt(i % vKey.length()) - 'A';
char c = vPlain.charAt(i);
vEnc.append((char)((c - 'a' + shift) % 26 + 'a'));
}
System.out.println("密文：" + vEnc);
System.out.println("Kasiski 估计密钥长度：" + kasiskiKeyLength(vEnc.toString(), 3));
}
/**
* Kasiski 检测：统计密文中重复出现的长度为 L 的子串
*/
static int kasiskiKeyLength(String cipher, int minLen) {
Map<String, List<Integer>> positions = new HashMap<>();
for (int L = minLen; L <= 5; L++) {
for (int i = 0; i + L <= cipher.length(); i++) {
String sub = cipher.substring(i, i + L);
positions.computeIfAbsent(sub, k -> new ArrayList<>()).add(i);
}
}
Map<Integer, Integer> distCount = new HashMap<>();
for (List<Integer> ps : positions.values()) {
for (int i = 1; i < ps.size(); i++) {
int d = ps.get(i) - ps.get(0);
for (int f = 2; f <= d; f++) if (d % f == 0)
distCount.merge(f, 1, Integer::sum);
}
}
return distCount.entrySet().stream()
.max(Map.Entry.comparingByValue())
.map(Map.Entry::getKey).orElse(1);
}
}
七、运行结果示例
=== 凯撒密码 ===
密文：aol xbpjr iyvvt mve qvbyt alvyl aol thgb tvu hvm aol wyvhim tvu aol ivymag
破解 shift = 7
明文：the quick brown fox jumps over the lazy dog and finds a treasure in the forest
=== 替换密码 ===
密文：gci jxnrv jrvfg wghl hxnlg hvcg gci mhrh fht hri qhu rci gci ohsigq
破解：the enemy forces will reach the town by the end of the day...
=== 维吉尼亚密码（Kasiski 检测密钥长度）===
密文：lxfopvefrnhr
Kasiski 估计密钥长度：5
八、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 凯撒暴力 | O(26 × n) | O(n) |
| 频率分析 | O(n) | O(1) |
| 模拟退火替换 | O(iterations × n) | O(n) |
| Kasiski 检测 | O(n²) | O(n²) |
九、扩展方向
- 指数级词典搜索：替换密码中加入 N-gram 评分（如 bigram、trigram），提高准确度。
- 混合密码：凯撒 + 替换组合，使用遗传算法搜索。
- 可视化：把频率分布绘制成柱状图，与英文标准对比，玩家能”看到”差异。
- 教学关卡：从凯撒开始，逐步升级到维吉尼亚、RSA，完整演绎密码学进阶史。
十、结语
密码破译类游戏融合了统计、概率、优化、信息论等多学科知识。本文从最简单的凯撒密码出发，逐步深入到替换密码与维吉尼亚密码，展示了频率分析与模拟退火两类核心算法。读者可基于源码添加 GUI（JavaFX/Swing），把频率直方图、当前映射、解密进度实时呈现，体验算法在密码学游戏中的”破译快感”。
