힐 암호(Hill cipher)

힐 암호(Hill cipher)

• 행렬을 이용한 치환 암호이다.
• 1929년 레스터 힐이라는 미국 수학자에 의해 발명되었다.
• 둘 이상의 알파벳을 함께 다른 문자로 치환하기때문에 빈도분석에 쉽게 깨지지않는다.

힐 암호문 복호화하기

• 키는 N*N행렬을 사용했다.
• 평문은 문장으로서 의미를 갖고있다.
• 영어 알파벳 a~z로 이루어져있다.

위에 조건과 함께 아래의 다음과 같은 암호문이 주어졌다고 가정한다.
HSVEUEELEEKOCELTNOAYAASPRNWZSTFZMGHQZDQDMTLTOWAAXHWJPXHLSJSRRVJNNBVAXLXWRTJDITBVISFACQGOEREGQVAPLBSTYCJRMDVTRTJFWFURCFQPKZUTSBITAIRQDITLFOLZFZFLLCTFSBFQCLYRDDDFQPNOHZIHXWZSHT

암호문의 길이는 174자이다. 이 문자열은 2,3,6..으로 나누어떨어지므로 복호화에 사용될 키행렬은 2x2, 3x3 6x6을 가지고 있다고 예상할 수 있다. 3x3 키행렬로 암호화가 되었다고 가정하고 복호화를 진행한다.

 [A, B, C]
 [D, E, F] x [HSV...3글자씩]
 [G, H, I]

= [H*`A`+S*`B`+V*`C`, H*`D`+S*`E`+V*`F`, H*`G`+S*`H`+V*`I`]

하나의 행의 계산 결과는 한글자를 의미하는 것을 알 수있다. 하나의 행에 각 원소는 26개의 알파벳을 가질 수있으므로 경우의 수는 26*26*26=17576의 경우를 계산한다. 각각의 경우의 수에서 알파벳의 각 분포도를 기반으로 카이 제곱근을 통해 행의 스코어를 매긴다. 스코어가 높을수록 복호화된 키일 가능성이 높다. 가능성있는 키 후보군을 뽑아 가능한 모든 조합의 평문을 출력하여 올바른 문장을 찾을 수 있다.

JAVA 코드

static final String TEXT = "HSVEUEELEEKOCELTNOAYAASPRNWZSTFZMGHQZDQDMTLTOWAAXHWJPXHLSJSRRVJNNBVAXLXWRTJDITBVISFACQGOEREGQVAPLBSTYCJRMDVTRTJFWFURCFQPKZUTSBITAIRQDITLFOLZFZFLLCTFSBFQCLYRDDDFQPNOHZIHXWZSHT";
static double[] frequency = {8.17, 1.49, 2.78, 4.25, 12.70, 2.23, 2.02, 6.09
,7.00, 0.15, 0.77, 4.03, 2.41, 6.75, 7.51, 1.93
,0.10, 5.99, 6.33, 9.06, 2.76, 0.98, 2.36, 0.15
,1.97, 0.07};
static int MOD = 26;
public static void main(String[] args){
    // 17576 경우의 모든 키값 조회
    for (int x=0; x<26; x++){
        for (int y=0; y<26; y++){
            for (int z=0; z<26; z++){
                processChiSquaredStatistic(x,y,z);
            }
        }
    }

    Collections.sort(list);
    for (int i=0; i<3; i++){
        Node n =list.get(i);
        System.out.println(n.x+" "+n.y+" "+n.z);
    }
}

public static void processChiSquaredStatistic(int x, int y, int z){
    int[] observedCount = new int[26];
    int length = TEXT.length();
    // 암호문 3글자씩 처리하기 
    for (int i=0; i<length-3; i+=3){
        int a = TEXT.charAt(i+0)-'A';
        int b = TEXT.charAt(i+1)-'A';
        int c = TEXT.charAt(i+2)-'A';
        observedCount[(a*x+b*y+c*z)%MOD]++;
    }

    double size = (double)(length/3); //428
    double total = 0;
    for (int i=0; i<observedCount.length; i++){
        double expectedCount = frequency[i]/100*size;
        double residual = (double)observedCount[i] - expectedCount;
        double cal = residual * residual / expectedCount;
        // System.out.println(expectedCount+" "+(double)observedCount[i]+" "+residual+" "+cal);
        total += cal;
    }
    list.add(new Node(x,y,z,total));
}

public static class Node implements Comparable<Node>{
    int x;
    int y;
    int z;
    double total;
    
    public Node(int x, int y, int z, double total){
        this.x=x;
        this.y=y;
        this.z=z;
        this.total=total;
    }
    
    public int compareTo(Node n){
        return Double.compare(this.total, n.total);
    }
    
    public String toString(){
        return x+" "+y+" "+z+" "+total;
    }
}