[과제] Substitution Cihper Decrypt

단순 치환 암호(Simple Substitution)은 가장 기본적인 방법으로 현재 문자를 n번째 앞에 있는 문자와 서로 치환해서 암호화하는 것이다.

 

암호문을 복호화 하는 방법 역시 단순하다. 암호문에 있는 문자와 평문에 있는 문자를 비교해서 치환하면 되는데, 암호화된 문자 각각을 알파벳 순서 상 n번째 뒤/앞에 위치한 문자로 치환하는 것이다.

 

Caesar's Cipher는 단순 치환 암호의 일종으로 알파벳 순서상 가능한 n번의 이동으로 암호화를 한다. (  n ∈ {0, 1, 2, … , 25} )

복호화 역시 단순 치환 암호의 복호화하는 방법과 똑같다. 알파벳의 개수는 정해져있기 때문에  26개의 키를 모두 사용하여 점검할 수 있다.

 

이렇게 무차별 대입으로 언젠가 올바른 키를 대입했을 시 평문을 찾는 암호 공격을 전수키 조사(exhaustive key search)라고 한다.

 

 

---

Cihper 암호 해독 문제

주어진 문자열은 다음과 같다.

APS ZU BMS THAAMT KB SOP CHAAPJ MQ LPUWHKX. K UHJ SM JMZ SMLHJ VJ QXKPBLU -- UM PCPB SOMZDO TP
QHEP SOP LKQQKEZASKPU MQ SMLHJ HBL SMVMXXMT, K USKAA OHCP H LXPHV. KS KU H LXPHV LPPWAJ XMMSPL
KB SOP HVPXKEHB LXPHV. K OHCP H LXPHV SOHS MBP LHJ SOKU BHSKMB TKAA XKUP ZW HBL AKCP MZS SOP SXZP
VPHBKBD MQ KSU EXPPL: "TP OMAL SOPUP SXZSOU SM IP UPAQ-PCKLPBS, SOHS HAA VPB HXP EXPHSPL PGZHA."
K OHCP H LXPHV SOHS MBP LHJ MB SOP XPL OKAAU MQ DPMXDKH SOP UMBU MQ QMXVPX UAHCPU HBL SOP UMBU
MQ QMXVPX UAHCP MTBPXU TKAA IP HIAP SM UKS LMTB SMDPSOPX HS SOP SHIAP MQ IXMSOPXOMML. K OHCP H
LXPHV SOHS MBP LHJ PCPB SOP USHSP MQ VKUUKUUKWWK, H USHSP UTPASPXKBD TKSO SOP OPHS MQ KBFZUSKEP,
UTPASPXKBD TKSO SOP OPHS MQ MWWXPUUKMB, TKAA IP SXHBUQMXVPL KBSM HB MHUKU MQ QXPPLMV HBL
FZUSKEP. K OHCP H LXPHV SOHS VJ QMZX AKSSAP EOKALXPB TKAA MBP LHJ AKCP KB H BHSKMB TOPXP SOPJ TKAA
BMS IP FZLDPL IJ SOP EMAMX MQ SOPKX URKB IZS IJ SOP EMBSPBS MQ SOPKX EOHXHESPX. K OHCP H LXPHV
SMLHJ. K OHCP H LXPHV SOHS MBP LHJ LMTB KB HAHIHVH, TKSO KSU CKEKMZU XHEKUSU, TKSO KSU DMCPXBMX
OHCKBD OKU AKWU LXKWWKBD TKSO SOP TMXLU MQ KBSPXWMUKSKMB HBL BZAAKQKEHSKMB -- MBP LHJ XKDOS
SOPXP KB HAHIHVH AKSSAP IAHER IMJU HBL IAHER DKXAU TKAA IP HIAP SM FMKB OHBLU TKSO AKSSAP TOKSP
IMJU HBL TOKSP DKXAU HU UKUSPXU HBL IXMSOPXU. K OHCP H LXPHV SMLHJ. K OHCP H LXPHV SOHS MBP LHJ
PCPXJ CHAAPJ UOHAA IP PNHASPL, HBL PCPXJ OKAA HBL VMZBSHKB UOHAA IP VHLP AMT, SOP XMZDO WAHEPU
TKAA IP VHLP WAHKB, HBL SOP EXMMRPL WAHEPU TKAA IP VHLP USXHKDOS, HBL SOP DAMXJ MQ SOP AMXL
UOHAA IP XPCPHAPL HBL HAA QAPUO UOHAA UPP KS SMDPSOPX.

 

 

알파벳 빈도수 테이블

다음과 같은 알파벳 빈도수 테이블을 이용하여 자주 사용되는 알파벳을 치환-대입하며 암호를 해독할 수 있다.

출처 : https://en.wikipedia.org/wiki/Letter_frequency

 

 

---

 

 

1. 알파벳 빈도수 구하는 코드 (JAVA)

class CountAlpha{
    private int[] alphabetCounts = new int[26];
		
		//알파벳 개수 구하기
    public void countAlphabets(String text) {
        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch >= 'A' && ch <= 'Z') {
                alphabetCounts[ch - 'A']++;
            }
        }
    }
		
		//알파벳 개수 출력
    public void printAlphabetCounts() {
        for (int i = 0; i < alphabetCounts.length; i++) {
            System.out.println((char) (i + 'A') + ": " + alphabetCounts[i]);
        }
    }
}
public class Decrypt {
    public static void main(String[] args) {
		    //암호화 문장 
        String cipher_text = " 암호문 작성 ";
        CountAlpha counter = new CountAlpha();

        counter.countAlphabets(cipher_text);
        counter.printAlphabetCounts();
    }
}

 

 

위와 같은 자바 코드를 이용해 암호문의 알파벳 빈도수를 구하고 정렬하니 다음과 같은 결과를 얻었다.

Frequency Count Table

 

 

2. 문장에서 반복되는 단어 찾기 및 치환

 

암호문 분석을 위해 많이 반복되는 단어로 OP, MQ, K OHCP H, SM, HBL를 발견하였고 K, I가 한 글자로 쓰이는 것을 볼 수 있었다.

 

알파벳 빈도를 이용해 암호문을 직접 해석하는 과정은 다음과 같이 진행하였.

 

1. P를 빈도가 가장 높은 E로 치환 → P=E

2. K와 H는 한글자로 많이 쓰이는 I,A로 치환 → K=I, H=A

3. S, M는 그 다음으로 빈도 높은 T, O로 치환 했을 시

→ S=T // SOP→ tOe = THE로 예상, O=H

→ M=O

4. 빈도가 가장 낮은 G,N,Y는 J/X, Q, Z로 치환 가능 → G=J/X, N=Q, Y=Z

5. theXe iB에서 X=R, B=S/N 예상, 그런데 문장 사이에 aBL가 있므로 S보단 N일 가능성이 크다고 생각
→ B=N

→ anL이므로 AND를 예상하여 L=D로 치환

6. Tith, Thite에서 T=W로 예상

7. todaJ를 보면 TODAY인 단어와 매칭 가능, J=Y

8. 문장의 시작에 Aet 단어는 LET으로 예상 → A=L

9. wordU, Utill, iU로 보았을 때 U는 S로 예상 → U=S

10. i haCe a dreaV이란 문장이 몇번 반복되어 나오는데, I HAVE DREAM으로 예상 → C=V, V=M

11. transQormed, oQ 란 단어를 보면 Q=F 라고 예상

12. trZe, trZths에서 Z=U라고 예상

13. toDether, Dirls에서 D=G라고 예상

14. Ioys, Irothers에서 I=B라고 예상

15. faEe the diffiEulties 문장에서 E=C 예상

16. deeWly, uW 에서 W=P 예상

17. eGual를 보면 남는 단어 중 K,J,X과 매칭이 되지 않고 오히려 EQUAL이란 단어를 연상 가능. 아까 위에서 N=Q로 두고 치환 했을 때 단어는 eqalted. 이 단어를 보면 N은 Q보단 X인 것 같음

→ G=Q, N=X

18. 치환되지 않은 단어 중 blacR, Foin를 보았을 때 R=K, F=J로 예상

 

 

복호화한 결과는 다음과 같다.

Key Table

 

 

암호문 해독 결과

위 과정을 통해 해석된 문장은 다음과 같다.

let us not wallow in the valley of despair. i say to you today my friends -- so even though we face the difficulties of today and tomorrow, 
i still have a dream. it is a dream deeply rooted in the american dream. i have a dream that one day this nation will rise up and live out the true meaning of its creed: "we hold these truths to be self-evident, that all men are created exual." 
i have a dream that one day on the red hills of georgia the sons of former slaves and the sons of former slave owners will be able to sit down together at the table of brotherhood. 
i have a dream that one day even the state of mississippi, a state sweltering with the heat of injustice, sweltering with the heat of oppression, will be transformed into an oasis of freedom and justice. 
i have a dream that my four little children will one day live in a nation where they will not be judged by the color of their skin but by the content of their character. i have a dream today. i have a dream that one day down in alabama, 
with its vicious racists, with its governor having his lips dripping with the words of interposition and nullification -- one day right there in alabama little black boys and black girls will be able to join hands with little white boys and white girls as sisters and brothers. i have a dream today. 
i have a dream that one day every valley shall be exalted, and every hill and mountain shall be made low, the rough places will be made plain, and the crooked places will be made straight, and the glory of the lord shall be revealed and all flesh shall see it together.