[Java] Cryptanalysis - Coincidence Counting

[Deque]

Coincidence Counting

This is another method to determine the length of a key used in Vigenère cipher.
Actually it is a modified Kasiski examination but easier to implement. Just take your message and make a second message that is the same but shifted one character. Lay the messages one upon the other and count each position where the characters are the same. Shift the message again and repeat this several times.

The result will show peaks when the message is shifted by a multiple of the key length. That is why you need Friedman Test in addition. The result is not precise, but gives you a hint to the real key length. Both methods work well together.

I used JFreeChart to show you a sample result. The peaks are marked blue. The given message was encoded with a key that is five characters long.

Code: (Java) [Select]

import javax.swing.JFrame;
import org.jfree.chart.ChartFactory;
import org.jfree.chart.ChartPanel;
import org.jfree.chart.JFreeChart;
import org.jfree.chart.plot.PlotOrientation;
import org.jfree.data.category.DefaultCategoryDataset;

public class CoincidenceCount implements Analysis {

    private int maxShift;

    @Override
    public String analyse(String code) {
        maxShift = code.length() - 1;
        int[] count = new int[maxShift + 1];

        for (int i = 1; i <= maxShift; i++) {
            String shifted = shiftText(code, i);
            count[i] = coincidenceCount(shifted, code);
        }
        createBarChart(count);
        return countString(count);
    }

    private String shiftText(String code, int shift) {
        StringBuilder b = new StringBuilder();
        b.append(code.substring(shift));
        b.append(code.substring(0, shift));
        return b.toString();
    }

    private String countString(int[] count) {
        StringBuilder b = new StringBuilder();
        b.append("shift\tcoincidences\n");
        for (int key = 1; key <= maxShift; key++) {
            b.append(key + "\t" + count[key] + "\n");
        }
        return b.toString();
    }

    private int coincidenceCount(String shifted, String code) {
        char[] shift = shifted.toCharArray();
        char[] plain = code.toCharArray();
        int count = 0;
        for (int i = 0; i < shift.length; i++) {
            if (shift[i] == plain[i]) {
                count++;
            }
        }
        return count;
    }

    private void createBarChart(int[] count) {
        DefaultCategoryDataset data = new DefaultCategoryDataset();
        int maxValues = 30 > maxShift ? maxShift : 30;
       
        for (Integer i = 1; i <= maxValues; i++) {
            Integer category = 0;
            if (isPeak(count, maxValues, i)) {
                category = 1;
            }
            data.addValue(count[i], category, i);
        }
       
        JFreeChart chart = ChartFactory.createBarChart("Coincidence Count",
                "Shift", "Coincidences", data, PlotOrientation.VERTICAL, false,
                false, false);
       
        JFrame frame = new JFrame();
        frame.setVisible(true);
        frame.setSize(800, 600);
        frame.setLocationRelativeTo(null);
        frame.add(new ChartPanel(chart));
    }

    private boolean isPeak(int[] count, int maxValues, Integer i) {
        return i > 1 && (i + 1) <= maxValues && count[i - 1] < count[i]
                && count[i + 1] < count[i];
    }
}
Deque