已知明文密文，如何暴力破解仿射密码f(p)=(a·p+b)的密钥a、b？求优化方案

Great question! Brute force is a foundational approach for affine cipher key recovery, but your current code has a few critical issues (like incorrect a/b iteration logic and ignoring affine cipher's mathematical constraints) — plus there are more efficient, cleaner ways to implement this. Let's walk through better alternatives:

First, Let's Fix & Optimize Your Brute Force Approach #

Your original code has bugs (e.g., a = a + x causes a to accumulate instead of testing distinct values, and you only check a single character pair instead of all of them). Affine cipher rules state a must be coprime with 26 (since we need an inverse for decryption), so we can narrow down valid a values to just 12 options instead of wasting time on invalid ones. Here's the optimized version:

public static int[] findKeysOptimizedBruteForce(String plaintext, String ciphertext) {
    // Valid a values (coprime with 26 — required for affine cipher invertibility)
    int[] validA = {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25};
    int[] keys = new int[]{-1, -1}; // Default to invalid if no match found

    // Iterate only valid a values
    for (int a : validA) {
        // Iterate all possible b values (0-25)
        for (int b = 0; b < 26; b++) {
            boolean matchesAllPairs = true;
            // Verify this (a,b) works for every character pair
            for (int i = 0; i < plaintext.length(); i++) {
                int plainNum = plaintext.charAt(i) - 'A'; // Convert to 0-25
                int expectedCipherNum = (a * plainNum + b) % 26;
                int actualCipherNum = ciphertext.charAt(i) - 'A';
                
                if (expectedCipherNum != actualCipherNum) {
                    matchesAllPairs = false;
                    break; // No need to check further
                }
            }
            if (matchesAllPairs) {
                keys[0] = a;
                keys[1] = b;
                return keys; // Return immediately once valid key is found
            }
        }
    }
    return keys;
}

2. Mathematical Approach (Solve Linear Equations) #

Instead of brute-forcing, we can use the linear nature of affine cipher to calculate a and b directly with just two distinct plaintext-ciphertext pairs. This is more efficient, especially for longer plaintexts. Here's the breakdown:

1. Given two pairs (p1, c1) and (p2, c2) where p1 ≠ p2, subtract the affine equations: c1 - c2 ≡ a*(p1 - p2) mod 26
2. Solve for a by multiplying both sides by the modular inverse of (p1 - p2) modulo 26
3. Plug a back into either equation to find b
4. Verify the key works for all pairs (to avoid edge cases)

Here's the Java implementation:

// Helper: Find modular inverse using Extended Euclidean Algorithm
private static int modInverse(int num, int mod) {
    num = num % mod;
    for (int x = 1; x < mod; x++) {
        if ((num * x) % mod == 1) {
            return x;
        }
    }
    return -1; // No inverse exists (invalid affine cipher scenario)
}

// Helper: Calculate greatest common divisor
private static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

public static int[] findKeysMathematical(String plaintext, String ciphertext) {
    int[] keys = new int[]{-1, -1};
    int p1 = plaintext.charAt(0) - 'A';
    int c1 = ciphertext.charAt(0) - 'A';
    
    // Find a second distinct plaintext-ciphertext pair (in case first two chars are identical)
    int p2 = -1, c2 = -1;
    for (int i = 1; i < plaintext.length(); i++) {
        p2 = plaintext.charAt(i) - 'A';
        c2 = ciphertext.charAt(i) - 'A';
        if (p2 != p1) {
            break;
        }
    }
    
    if (p2 == -1) return keys; // All plaintext chars are same — can't determine unique a
    
    // Calculate delta values and ensure they're positive modulo 26
    int deltaP = (p1 - p2) % 26;
    deltaP = deltaP < 0 ? deltaP + 26 : deltaP;
    int deltaC = (c1 - c2) % 26;
    deltaC = deltaC < 0 ? deltaC + 26 : deltaC;
    
    int invDeltaP = modInverse(deltaP, 26);
    if (invDeltaP == -1) return keys; // No inverse (invalid cipher)
    
    int a = (deltaC * invDeltaP) % 26;
    // Sanity check: a must be positive and coprime with 26
    if (a <= 0 || gcd(a, 26) != 1) return keys;
    
    int b = (c1 - a * p1) % 26;
    b = b < 0 ? b + 26 : b; // Ensure b is non-negative
    
    // Verify the key works for all character pairs
    boolean isValid = true;
    for (int i = 0; i < plaintext.length(); i++) {
        int plainNum = plaintext.charAt(i) - 'A';
        int expectedCipherNum = (a * plainNum + b) % 26;
        int actualCipherNum = ciphertext.charAt(i) - 'A';
        if (expectedCipherNum != actualCipherNum) {
            isValid = false;
            break;
        }
    }
    
    if (isValid) {
        keys[0] = a;
        keys[1] = b;
    }
    return keys;
}

Which Approach to Choose? #

• Optimized Brute Force: Perfect for beginners, simple to understand, and fast enough for most practical use cases (since the valid a list is tiny).
• Mathematical Method: More efficient (O(n) time vs. O(1226n) for brute force) and leverages the cryptography behind affine cipher — great for longer plaintexts or if you want a more elegant solution.

内容的提问来源于stack exchange，提问作者Shoug