每日算法 — 使用java实现凯撒密码：仿射加密扩展与卡方统计频率破解

引言

凯撒密码（Caesar Cipher）是古罗马时期 Julius Caesar 用于军事通信的加密方法，其原理简单却影响深远——将明文中的每个字母按固定偏移量向后推移。尽管在现代密码学中它已被完全破解，但作为入门级的加密算法，凯撒密码完美展示了替换密码的核心思想，也是理解现代加密体系的绝佳起点。本文将用Java实现凯撒密码的完整系统，不仅包含基础的移位加密，还将扩展到仿射加密，并实现基于卡方统计学的自动破解算法。

凯撒密码原理

基础移位加密

设偏移量为 k（1 ≤ k ≤ 25），加密公式为：

C = (P + k) mod 26
P = (C - k) mod 26

其中 P 为明文字母对应的数字（A=0, B=1, …, Z=25），C 为密文。

public class CaesarCipher {

    private static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    /**
     * 加密：将每个字母按偏移量k后移
     */
    public static String encrypt(String plaintext, int shift) {
        StringBuilder sb = new StringBuilder();
        shift = ((shift % 26) + 26) % 26; // 规范化到0-25

        for (char c : plaintext.toUpperCase().toCharArray()) {
            if (Character.isLetter(c)) {
                int idx = ALPHABET.indexOf(c);
                int newIdx = (idx + shift) % 26;
                sb.append(ALPHABET.charAt(newIdx));
            } else {
                sb.append(c); // 非字母字符保持不变
            }
        }
        return sb.toString();
    }

    /**
     * 解密：将每个字母按偏移量k前移
     */
    public static String decrypt(String ciphertext, int shift) {
        return encrypt(ciphertext, 26 - shift); // 解密即反方向移位
    }

    public static void main(String[] args) {
        String text = "HELLO WORLD";
        int key = 3;
        String encrypted = encrypt(text, key);
        String decrypted = decrypt(encrypted, key);

        System.out.println("明文: " + text);
        System.out.println("密钥: " + key);
        System.out.println("密文: " + encrypted);
        System.out.println("解密: " + decrypted);
    }
}

仿射加密扩展

仿射加密是凯撒密码的广义形式，引入乘数密钥 a（需与26互质）：

C = (a × P + b) mod 26
P = a⁻¹ × (C - b) mod 26

其中 a⁻¹ 是 a 在模26下的乘法逆元。

public class AffineCipher {

    private static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    /**
     * 扩展欧几里得算法求乘法逆元
     */
    static int modInverse(int a, int m) {
        int m0 = m, t, q;
        int x0 = 0, x1 = 1;
        if (m == 1) return 0;
        while (a > 1) {
            q = a / m;
            t = m;
            m = a % m;
            a = t;
            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }
        if (x1 < 0) x1 += m0;
        return x1;
    }

    /**
     * 判断a是否与26互质
     */
    static boolean isValidA(int a) {
        return gcd(a, 26) == 1;
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static String encrypt(String plaintext, int a, int b) {
        if (!isValidA(a)) throw new IllegalArgumentException("a必须与26互质");
        StringBuilder sb = new StringBuilder();

        for (char c : plaintext.toUpperCase().toCharArray()) {
            if (Character.isLetter(c)) {
                int p = ALPHABET.indexOf(c);
                int cipher = (a * p + b) % 26;
                sb.append(ALPHABET.charAt(cipher));
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    public static String decrypt(String ciphertext, int a, int b) {
        if (!isValidA(a)) throw new IllegalArgumentException("a必须与26互质");
        int aInv = modInverse(a, 26);
        StringBuilder sb = new StringBuilder();

        for (char c : ciphertext.toUpperCase().toCharArray()) {
            if (Character.isLetter(c)) {
                int cipher = ALPHABET.indexOf(c);
                int plain = ((cipher - b) * aInv) % 26;
                if (plain < 0) plain += 26;
                sb.append(ALPHABET.charAt(plain));
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

基于频率分析的自动破解

凯撒密码的密钥空间仅有25种可能，暴力枚举即可破解。但对于稍长的密文，基于字母频率统计的方法更为优雅高效。

英语字母频率表

根据大规模英文文本统计，各字母出现频率如下：

static final double[] ENGLISH_FREQ = {
    8.167, 1.492, 2.782, 4.253, 12.702,  // A-E
    2.228, 2.015, 6.094, 6.966, 0.153,   // F-J
    0.772, 4.025, 2.406, 6.749, 7.507,   // K-O
    1.929, 0.095, 5.987, 6.327, 9.056,   // P-T
    2.758, 0.978, 2.360, 0.150, 1.974,   // U-Y
    0.074                                 // Z
};

卡方统计检验

卡方检验衡量观察频率与期望频率的偏离程度：

χ² = Σ (观察值 - 期望值)² / 期望值

public class CaesarCracker {

    private 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.327, 9.056,
        2.758, 0.978, 2.360, 0.150, 1.974, 0.074
    };

    /**
     * 计算文本中各字母的频率
     */
    static double[] calculateFreq(String text) {
        double[] freq = new double[26];
        int total = 0;
        for (char c : text.toUpperCase().toCharArray()) {
            if (Character.isLetter(c)) {
                freq[c - 'A']++;
                total++;
            }
        }
        if (total == 0) return freq;
        for (int i = 0; i < 26; i++) freq[i] = freq[i] * 100.0 / total;
        return freq;
    }

    /**
     * 计算卡方统计量（越小表示越接近英文分布）
     */
    static double chiSquare(double[] observed) {
        double chi = 0;
        for (int i = 0; i < 26; i++) {
            double expected = ENGLISH_FREQ[i];
            double diff = observed[i] - expected;
            chi += (diff * diff) / expected;
        }
        return chi;
    }

    /**
     * 自动破解凯撒密码：尝试所有25种偏移，选择卡方值最小的
     */
    public static int crack(String ciphertext) {
        double minChi = Double.MAX_VALUE;
        int bestShift = 0;

        for (int shift = 1; shift <= 25; shift++) {
            String decrypted = CaesarCipher.decrypt(ciphertext, shift);
            double[] freq = calculateFreq(decrypted);
            double chi = chiSquare(freq);

            if (chi < minChi) {
                minChi = chi;
                bestShift = shift;
            }
        }
        return bestShift;
    }

    /**
     * 带置信度评估的破解
     */
    public static CrackResult crackWithConfidence(String ciphertext) {
        int shift = crack(ciphertext);
        String plaintext = CaesarCipher.decrypt(ciphertext, shift);
        double[] freq = calculateFreq(plaintext);
        double chi = chiSquare(freq);

        // 计算置信度：与第二优解的差距
        double secondMinChi = Double.MAX_VALUE;
        for (int s = 1; s <= 25; s++) {
            if (s == shift) continue;
            double c = chiSquare(calculateFreq(CaesarCipher.decrypt(ciphertext, s)));
            if (c < secondMinChi) secondMinChi = c;
        }
        double confidence = secondMinChi / chi;

        return new CrackResult(shift, plaintext, chi, confidence);
    }

    static class CrackResult {
        int shift;
        String plaintext;
        double chiSquare;
        double confidence;

        CrackResult(int s, String p, double c, double conf) {
            shift = s; plaintext = p; chiSquare = c; confidence = conf;
        }

        @Override
        public String toString() {
            return String.format("密钥=%d, 置信度=%.2f, 明文=%s", shift, confidence, plaintext);
        }
    }
}

完整的密码系统测试

public class CryptoDemo {

    public static void main(String[] args) {
        String original = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG";

        System.out.println("=== 原始明文 ===");
        System.out.println(original);
        System.out.println();

        // 凯撒加密
        int caesarKey = 7;
        String caesarCipher = CaesarCipher.encrypt(original, caesarKey);
        System.out.println("=== 凯撒加密 (密钥=" + caesarKey + ") ===");
        System.out.println("密文: " + caesarCipher);

        // 自动破解
        int crackedKey = CaesarCracker.crack(caesarCipher);
        System.out.println("自动破解密钥: " + crackedKey);
        System.out.println("破解明文: " + CaesarCipher.decrypt(caesarCipher, crackedKey));
        System.out.println();

        // 仿射加密
        int a = 5, b = 8; // a必须与26互质
        String affineCipher = AffineCipher.encrypt(original, a, b);
        System.out.println("=== 仿射加密 (a=" + a + ", b=" + b + ") ===");
        System.out.println("密文: " + affineCipher);
        System.out.println("解密: " + AffineCipher.decrypt(affineCipher, a, b));
        System.out.println();

        // 暴力破解仿射密码
        System.out.println("=== 仿射密码暴力破解 ===");
        crackAffineBruteForce(affineCipher);
    }

    static void crackAffineBruteForce(String cipher) {
        int[] validA = {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}; // 与26互质的数
        double minChi = Double.MAX_VALUE;
        String bestPlain = "";
        int bestA = 0, bestB = 0;

        for (int a : validA) {
            for (int b = 0; b < 26; b++) {
                String plain = AffineCipher.decrypt(cipher, a, b);
                double chi = CaesarCracker.chiSquare(CaesarCracker.calculateFreq(plain));
                if (chi < minChi) {
                    minChi = chi;
                    bestPlain = plain;
                    bestA = a; bestB = b;
                }
            }
        }
        System.out.printf("最优密钥: a=%d, b=%d%n", bestA, bestB);
        System.out.println("破解明文: " + bestPlain);
    }
}

安全性分析

凯撒密码和仿射密码都属于古典密码，其致命弱点在于：单字母替换保持了明文的统计特征。现代密码学通过以下方式解决这一问题：
– 多表替换（如Vigenère密码）：不同位置使用不同替换表
– 扩散与混淆（如AES）：让每个密文字母依赖于多个明文字母

小结

本文通过Java实现了完整的凯撒密码系统：
– 基础移位加密与解密算法
– 仿射加密的扩展实现（引入乘数密钥与模逆元）
– 基于卡方统计学的自动频率分析破解
– 扩展欧几里得算法求模逆元的数学实现

尽管凯撒密码在现代已无实用安全性，但它承载的历史意义和教学价值不可忽视。从简单的位移运算到复杂的模逆元计算，从直观的频率分析到严谨的卡方检验，这一古老密码为我们打开了密码学世界的大门。