public class VigenereBreak {

    // Standard frequency of English letters a-z
    public static double[] ENGFREQ = {.082, .015, .028, .043, .127, .022, .020, .061, .070, .002,
                                       .008, .040, .024, .067, .075, .019, .001, .060, .063, .091,
                                       .028, .010, .023, .001, .020, .001};

    public static void main(String[] args) {
        String cipher =
            "jbqfbwlzidnmseyivshvsdpgammzdygybxwjeyegovqsabbxkfsgmwoxkwpwn" +
            "wllargbymkwsflsqgynkmgzyhoghjgmvbamirxnvbmxzwvbtlbfjnprhjxagr" +
            "gcmmulqaaiuajlhcseqhlnmxzawqhwrldxgbnjsuirtatjeoevepkwinumafj" +
            "cnhezawabnbawqlorpmfvsjtvdtdswhkwaylgeqnpjienkhkllruwteegzvzl" +
            "lqshpqlwiymnymjwikmqnrkcauxvaxcbnwppdnprwsgjxbbbaytfqsmxzwhro" +
            "qspkhlrkrwsxubbidqhmaoidgtrpqtsoicemvwsxuheyzkyvwhcygsqeccv";

        System.out.println("Cipher length: " + cipher.length());

      
        // Step 1: for the chosen n, run MIC analysis per bin to guess each key letter
        int n = 14;
        int[][] myFreq = getFreq(cipher, n);
        StringBuilder guessedKey = new StringBuilder();
        System.out.println("\n--- MIC-based key letter guesses ---");
        for (int i = 0; i < n; i++)
            guessedKey.append(printMIC(myFreq[i]));
        System.out.println("\nGuessed key: " + guessedKey);

        // Step 2: decrypt using the key
        String key = guessedKey.toString(); 
        System.out.println("\n--- Decrypted message ---");
        decrypt(cipher, key);
    }

    // Compute Index of Coincidence for a single string
    public static double ic(int[] freq, int total) {
        if (total < 2) return 0;
        long sum = 0;
        for (int f : freq) sum += (long) f * (f - 1);
        return sum / (double) ((long) total * (total - 1));
    }

    // Average IC across all n bins for a candidate key length
    public static double averageIC(String cipher, int n) {
        int[][] freq = getFreq(cipher, n);
        double total = 0;
        for (int b = 0; b < n; b++) {
            int binTotal = 0;
            for (int f : freq[b]) binTotal += f;
            total += ic(freq[b], binTotal);
        }
        return total / n;
    }

    // Split ciphertext into n frequency bins
    public static int[][] getFreq(String cipher, int n) {
        int[][] freq = new int[n][26];
        int cipherLen = cipher.length();
        for (int i = 0; i < cipherLen; i++)
            freq[i % n][cipher.charAt(i) - 'a']++;
        return freq;
    }

    // MIC for a particular shift (0-25)
    public static double MICEnglish(int[] freq, int shift) {
        int total = 0;
        for (int f : freq) total += f;

        double mic = 0;
        for (int i = 0; i < 26; i++)
            mic += ENGFREQ[i] * freq[(i + shift) % 26];

        return mic / total;
    }

    // Find and print the best shift/letter for one bin; return the guessed letter
    public static char printMIC(int[] freq) {
        double max = -1;
        int shiftLet = 0;

        for (int i = 0; i < 26; i++) {
            double tempMIC = MICEnglish(freq, i);
            if (tempMIC > max) {
                max = tempMIC;
                shiftLet = i;
            }
        }

        char letter = (char) ('a' + shiftLet);
        System.out.printf("The highest found: %.4f letter: %c%n", max, letter);
        return letter;
    }

    // Decrypt cipher text with the given key
    public static void decrypt(String cipher, String key) {
        int keyLen = key.length();
        StringBuilder plain = new StringBuilder();
        for (int i = 0; i < cipher.length(); i++) {
            int letterToAdd = cipher.charAt(i) - key.charAt(i % keyLen);
            if (letterToAdd < 0)
                letterToAdd += 26;
            plain.append((char) (letterToAdd + 'a'));
        }
        System.out.println(plain.toString());
    }
}