[3장] 암호의 역사

1절 시저암호

시저암호: 평문으로 사용되는 알파벳을 일정한 문자 수 만큼 평행이동 시킴으로써 암호화 한다.

예를들어 abcde라는 암호가 존재하면 shift 2 연산을 진행하면 cdefg가 된다. (2문자 평행이동)

평문: kabsoonyee
암호문: NDEVRRQBHH 

대충 이렇다.

그러면 이때 키값은 무엇일까? 당연히 평행 이동한 문자수가 될것이다. 

 

복호화 과정도 동일하다. 키값을 다시 재사용한다. 이는 대칭암호이다.

 

1-4 전사 공격에 의한 해독

이러한 암호문은 전사 공격에 의해 해독되기 쉬운데, 영어 알파벳이 26문자 이므로 암호화 키는 0~25까지 26가지 일것으로 추정할 수 있다. 이때 키가 될 수 있는 모든 가능한 후보들을 시도해 보는게 전사공격 이다. 

브루트포스 어택이라고 한다.

 

 

2절 단일 치환 암호

단일 치환 암호란 평문을 구성하는 알파벳들을 다른 알파벳으로 변환하는 암호를 말한다. 시저 암호 역시 단일 치환 암호에 포함된다.

치환표 개념이 존재할 수 있다.

 

평문에 등장하는 문자의 빈도가 암호문으로 바뀐 뒤에도 암호문 내에서 동일한 빈도로 나타난다는 약점이 존재한다.

즉 aabbccdd가 DDFFSSUU로 변환되었을 때를 생각해보자. 

 

이렇게 치환표가 존재하는 단일 치환 암호의 경우 키값은 치환표가 될 것이다. 하지만 치환표에 따라 암호문이 달라질 수 있으므로 시저암호가 전사 공격에 약했지만 단일 치환 암호는 전사공격으로 해독이 어렵다.

 

키 공간과 전사공격 시간 계산

우리는 위의 두 암호화 기법을 살펴보면서 키 공간이 클수록 전사 공격이 어렵다는것을 알 수 있었다. 시저 암호의 경우 키공간이 고작 26 이지만 단일 치환 암호의 경우 치환표에 따라 알파벳이 랜덤으로 배치되기 때문에 26!의 경우의 수를 가진다.

이 값이 키 공간임임을 알 수 있고 이를 전사공격으로 조사했을 때 26!의 크기에 비례한다.

 

2-5 빈도 분석에 의한 해독

그래서 이런 브루트포스 공격보다는 빈도 분석에 의한 해독을 사용하는데, 평문에 나오는 문자의 빈도와 암호문의 문자의 빈도가 일치하는것을 이용한다.

aaaabbc 라는 평문과 DDDDFFB라는 암호문이 있을 때 우리는 빈도분석을 통해 a가 D임을 b가 F임을 c가 B임을 유추할 수 있다!

 

 

MeYLGVIWAMeYOPINYZGWYeGMZRUUYPZAIXILGVSIZZMPGKKD WOMePGROeIWGPCeIPAMDKKeYCIUYMGIFRWCeGLOPINYZHRZM PDNYWDWOGWITDWYSeDCeeIAFYYWMPIDWYAGTYPIKGLMXFPI WCeHRZMMeYMeDWOMGQRYWCeUXMeDPZMQRGMeeYAPISDWO FICJILYSNICYZeYMGGJIPRWIWAIHRUNIWAHRZMUDZZYAMeYFRW CeMRPWDWOPGRWAIOIDWSDMeIGWYMSGMePYYeYHRUNYARNF RMSDMeWGOPYIMYPZRCCYZZIOIDWIWAIOIDWeYMPDYAILMYPM eYMWUNMDWOUGPZYKFRMIMKIZMeIAMGODTYDMRNIWASIKJYAI SIXSDMeeDZWGZYDWMeYIDPZIXDWODIUZRPYMeYXIPYZGRPDM 

DZYIZXMGAYZNDZYSeIMXGRCIWWGMOYM

 

라는 암호문을 보자

 

 

문자	개수	문자	개수	문자	개수	문자	개수	문자	개수
I	47개	G	27개	C	12개	F	7개	V	2개
Y	47개	Z	27개	S	11개	L	6개	B	0개
M	45개	P	26개	N	10개	H	5개
W	35개	R	22개	U	10개	J	3개
e	33개	A	17개	K	8개	T	3개
D	30개	O	16개	X	8개	Q	2개

1. 최빈도를 갖는 암호를 보자 Y와 I가 중 하나를 e라고 가정해보자 우선 Y를 e 라고 가정하고 치환해주자

MEeLGVIWAMEeOPINeZGWeEGMZRUUePZAIXILGVSIZZMPGKKDWO MEPGROEIWGPCEIPAMDKKEeCIUeMGIFRWCEGLOPINeZHRZMPDN eWDWOGWITDWeSEDCEEIAFeeWMPIDWeAGTePIKGLMXFPIWCEHR ZMMEeMEDWOMGQReWCEUXMEDPZMQRGMEEeAPISDWOFICJILeS NICeZEeMGGJIPRWIWAIHRUNIWAHRZMUDZZeAMEeFRWCEMRPWD WOPGRWAIOIDWSDMEIGWeMSGMEPeeEeHRUNeARNFRMSDMEWG OPeIMePZRCCeZZIOIDWIWAIOIDWEeMPDeAILMePMEeMWUNMDWO UGPZeKFRMIMKIZMEIAMGODTeDMRNIWASIKJeAISIXSDMEEDZWGZ eDWMEeIDPZIXDWODIUZRPeMEeXIPeZGRPDMDZeIZXMGAeZNDZe SEIMXGRCIWWGMOeM

 

2. 영어기준 the 라는 표현을 점검한다.

 

theLGVIWAtheOPINeZGWehGtZRUUePZAIXILGVSIZZtPGKKDWOthPG ROhIWGPChIPAtDKKheCIUetGIFRWChGLOPINeZHRZtPDNeWDWOG WITDWeShDChhIAFeeWtPIDWeAGTePIKGLtXFPIWChHRZtthethDWOt GQReWChUXthDPZtQRGthheAPISDWOFICJILeSNICeZhetGGJIPRWI WAIHRUNIWAHRZtUDZZeAtheFRWChtRPWDWOPGRWAIOIDWSDthIG WetSGthPeeheHRUNeARNFRtSDthWGOPeItePZRCCeZZIOIDWIWAIOI DWhetPDeAILtePthetWUNtDWOUGPZeKFRtItKIZthIAtGODTeDtRNIWA SIKJeAISIXSDthhDZWGZeDWtheIDPZIXDWODIUZRPetheXIPeZGRPDt DZeIZXtGAeZNDZeShItXGRCIWWGtOet

3. thPee를 보고 P를 r이라 추측해보자

theLGVIWAtheOrINeZGWehGtZRUUerZAIXILGVSIZZtrGKKDWOthrGR OhIWGrChIrAtDKKheCIUetGIFRWChGLOrINeZHRZtrDNeWDWOGWIT DWeShDChhIAFeeWtrIDWeAGTerIKGLtXFrIWChHRZtthethDWOtGQRe WChUXthDrZtQRGthheArISDWOFICJILeSNICeZhetGGJIrRWIWAIHRU NIWAHRZtUDZZeAtheFRWChtRrWDWOrGRWAIOIDWSDthIGWetSGthreeheHRUNeARNFRtSDthWGOreIterZRCCeZZIOIDWIWAIOIDWhetrDeA ILterthetWUNtDWOUGrZeKFRtItKIZthIAtGODTeDtRNIWASIKJeAISIXSD thhDZWGZeDWtheIDrZIXDWODIUZRretheXIreZGRrDtDZeIZXtGAeZND ZeShItXGRCIWWGtOet

4. 익숙한 단어를 보자 Oet는 뭘까? bet? ret? set? 등 추측해본다

5. thethDWg라는패턴이보인다.이것은thething일지도모른다 D→i, W→n ??

6. grINe라는패턴이보인다. 사전을 찾아보았더니 

grace, grade, grape, grate, grave, gripe, grofe, ...처럼 많은 후보가 있다. 이것으로는 결정을 할 수 없다.

– I→a를 가정해 보면 greater라는 패턴이 나오므로 I→a는 맞는 것 같다. 

– 하지만, N→c를 가정하면 tricening라는 패턴이 나왔다. 

이런 단어는 영어 단어에 없는 것 같다. 따라서 N→c는 잘못일지도 모른다

 

7. 다시 돌아가서 빈도가 높은 문자를 가정해본다. G -> o로 가정해보자

theLoVanAthegraNeZonehotZRUUerZAaXaLoVSaZZtroKKingthroRgha norCharAtiKKheCaUetoaFRnChoLgraNeZHRZtriNeningonaTineShiChh aAFeentraineAoTeraKoLtXFranChHRZtthethingtoQRenChUXthirZtQRo thheAraSingFaCJaLeSNaCeZhetooJarRnanAaHRUNanAHRZtUiZZeAt heFRnChtRrningroRnAagainSithaonetSothreeheHRUNeARNFRtSithno greaterZRCCeZZagainanAagainhetrieAaLterthetnUNtingUorZeKFRtat KaZthaAtogiTeitRNanASaKJeAaSaXSithhiZnoZeintheairZaXingiaUZRr etheXareZoRritiZeaZXtoAeZNiZeShatXoRCannotget

Cannot get 이라는 문자가 등장한다. 틀림없다. C -> c이다. C-> c이므로 N->c는 잘못이다.

 

8. Shich라는 패턴이 보인다. 이는 which일 것이다.

theLoVanAthegraNeZonehotZRUUerZAaXaLoVSaZZtro KKingthroRghanorcharAtiKKhecaUetoaFRnchoLgraNeZ HRZtriNeningonaTineShichhaAFeentraineAoTeraKoLtX FranchHRZtthethingtoQRenchUXthirZtQRothheAraSing FacJaLeSNaceZhetooJarRnanAaHRUNanAHRZtUiZZeA theFRnchtRrningroRnAagainSithaonetSothreeheHRUNe ARNFRtSithnogreaterZRcceZZagainanAagainhetrieAaLt erthetnUNtingUorZeKFRtatKaZthaAtogiTeitRNanASaKJ eAaSaXSithhiZnoZeintheairZaXingiaUZRretheXareZoRri tiZeaZXtoAeZNiZeShatXoRcannotget

9. thethingtoQRench라는 패턴이 찾아졌다. 이것은 분명히 the thing to QRench이다.

사전을 찾아보니 quench라는 단어가 있었다(Q→q, R→u)

- quench라는 것은 「갈증을 해소하다」라는 의미이다. 마시는 것에 관한 이야기가 아닐까?

 

10. hotZuUUer라는 패턴이 찾아졌다. 이것은 hot summer일 것이다(Z→s, U→m). 

U가 두 개 연속해 있다는 것이 큰 실마리였다. 「갈증을 해소하다」라는 문맥과도 일치한다.

 

theLoVanAthegraNesonehotsummersAaXaLoVwasstroKKingthrougha norcharAtiKKhecametoaFunchoLgraNesHustriNeningonaTinewhichha AFeentraineAoTeraKoLtXFranchHustthethingtoquenchmXthirstquothh eArawingFacJaLewNaceshetooJarunanAaHumNanAHustmisseAtheFu nchturningrounAagainwithaonetwothreeheHumNeAuNFutwithnogreat ersuccessagainanAagainhetrieAaLterthetnmNtingmorseKFutatKastha AtogiTeituNanAwaKJeAawaXwithhisnoseintheairsaXingiamsuretheXar esouritiseasXtoAesNisewhatXoucannotget

11. sucessagainanAagain라는패턴이있다. 이것은successagain and again일 것이다(A→d).

triedaLter라는 패턴이 보인다. 이것은 틀림없이 tried after이다(L→f).

whatXoucannotget라는 패턴이 보 인다. 이것은 what you cannot get일 것이다(X→y).

thefoxandthegrapesonehotsummersdayafoxwasstroKKingthroughano rchardtiKKhecametoaFunchofgrapesHustripeningonaTinewhichhadFe entrainedoTeraKoftyFranchHustthethingtoquenchmythirstquothhedra wingFacJafewpaceshetooJarunandaHumpandHustmissedtheFunchtu rningroundagainwithaonetwothreeheHumpedupFutwithnogreatersucc essagainandagainhetriedafterthetnmptingmorseKFutatKasthadtogiTei tupandwaKJedawaywithhisnoseintheairsayingiamsuretheyaresouritise asytodespisewhatyoucannotget

 

12. 이제 나머지를 전부 해독해주자.

-> foxwasstroKKing – fox was strolling – (K → l)

-> hetooJarunandaHumpandHustmissed - hetookarunandajumpandjustmissed – (H → j) – (J → k)

-> hejumpedupFutwithnogreatersuccess - hejumpedupbutwithnogreatersuccess – (F → b) 

-> butatlasthadtogiTeitup - butatlasthadtogiveitup – (T → v) 

이암호문에나오지않은마지막1문자 – (B → z)

 

13. 치환표를 만들어주자.

 

이렇게 해독할 수 있다. 

 

해독작업의 특징

1. 빈도가 높은 문자뿐 아니라 낮은 문자도 단서가 된다.

2. 처음과 끝을 아는것은 단서가 된다. 단어의 단락을 유추하자

3. 암호문이 길면 길수록 해독이 쉬워진다.

4. 같은 문자가 연속으로 나타나는 것을 살펴보자

5. 해독의 속도가 점점 빨라진다.

 

 

3절 다중 치환 암호

단일 치환 암호의 약점은 평문과 암호문간의 단순 대응을 사용하기 때문에 평문의 단일 문자에 대한 빈도가 그대로 암호문에 반영된다.

최초 해독시에 문자의 빈도로 접근했기 때문에 문자의 빈도를 균등하게 하는 암호를 만드는게 바람직하다.

 

이때 다중치환을 통해 문자의 발생빈도를 균일화 할 수 있다.

 

다중 치환 암호: 평문에 등장하는 문자의 빈도와 암호문에 등장하는 문자의 빈도를 다르게 만드는 암호 알고리즘

 

3-1절 Hill암호 기법

각 문자에 정수 값을 부여하고 m개의 문자를 한번에 치환하는 방법

M=3일 때

C1 = (k11 p1 + k12 p2 + k13 p3)mod26 

C2 = (k21 p1 + k22 p2 + k23 p3 ) mod 26

C3 = (k31 p1 + k32 p2 + k33 p3 ) mod 26

 

 이런식으로 하면 빈도수를 조절할 수 있다. 여기서 C는 암호문, P는 평문 k는 키 이다.

 

PAYMOREMONEY라는 평문이 있다고 가정하자.

1. 우선 평문을 숫자로 변환해준다. A = 0, P = 15, Y = 24 ...

2. 키를 가져온다. 키는 아래와 같다.

 

 3. 행렬 곱셈으로 변경해준다.

(키 x 평문을 숫자로 바꾼 행렬) mod 26

 4. 계산한다.

17 x 15 + 17 x 0 + 5 x 24 = 375 mod 26 = 11  => C1

21 x 15 + 18 x 0 + 21 x 24 = 819 mod 26 = 13 => C2

2 x 15 + 2 x 0 + 19 x 24 = 486 mod 26 = 18 => C3

 

11 13 18 ... 의 암호문이 나온다.

 

 

복호문 계산

다중 치환 암호의 암호문 C = Ek(P) = KP였다. 키 행렬과 평문 숫자 행렬을 곱셈연산한 값이었다.

이때 복호문을 계산하기 위해서는 P = K^-1 x C의 연산을 따라야 한다.

K^-1은 역행렬이다.

 

 

 

다중 단일 문자 치환 암호 기법 

- 단일 문자 치환 규칙들의 집합을 사용합니다.

- 근데 주어진 변환에서 사용될 특정 규칙은 키에 의해 결정됩니다.

대표적으로 Vigenere 암호 방식이 존재합니다.

 

Vigenere 암호 방식

• –  키 : deceptive
• –  평문 : we are discovered save yourself 

일 때

이런식으로 암호문이 나오게 됩니다. 그 이유는 아래의 표를 따릅니다.

 

 

4절 에니그마

20세기 초에 발명한 암호화/복호화 이며 독일어로 수수께끼를 의미한다.

이는 회전하는 원반과 전기회로를 써서 강력한 암호를 만들고자 시도했다. 

 

에니그만 다중 치환 암호를 전기적인 기계로 구현해낸 것이다.

 

애니그마의 구성

1. 송 수신자가 동시에 애니그마가 필요함

2. 코드북이 존재한다.  코드북에는 날짜 별 키값이 들어있다.

 

애니그마의 구조

1. 알파벳 26문자를 암호화 복호화 하는것이 아닌, 알파벳의 수롤 4개의 문자로 가정하고 암호화한다.

 

암호통신 흐름

1. 평문 -> 에니그마에서 코드북 날짜별 지침에 따라 설정 -> 암호문 

2. 무선 통신으로 전송

3. 암호문 -> 코드북의 날자별 지침에 따라 에니그마 설정 -> 평문

 

 로터

1. 로터는 앞뒤 단자가 뭐 연결되있는 아무튼 원반모양의 부품, 로터를 회전시켜 암호화를 진행

2. 하나의 문자를 입력하면 로터1이 1/4 회전한다.(알파벳의 수를 4개의 문자로 했을 경우)

3. 로터 1이 1회전하면 로터2가 1/4회전하고 로터 2가 1회전하면 로터 3이 1/4회전한다.

 

암호화 방법

1. 메시지를 통신키로 암호화 한다. 그럼 암호문 메시지가 새로 출력된다.

2. 통신키를 다시 날짜별 키로 암호화 한다. 그럼 통신키 암호문이 출력된다.

3. 두 암호문을 붙힌다. 최종 암호문이 탄생한다.

4. 이때 통신키는 2회 반복한다. 당시 무선기술의 한계 때문이다.

 

복호화 방법

1. 역순이다, 우선 최종 암호문에서 통신키 암호문과 메시지 암호문을 분리한다.

2. 통신키를 암호문을 날짜별 지침에 따라 복호화 한다.

3. 복호화 된 통신키를 받아서 메시지 암호문을 복호화 한다. 이후 기록한다.

 

에니그마의 약점

1. 통신키를 두번 반복한것을 암호화 한다.

2. 통신키는 사람이 선택한다.

3. 코드북이 필요하다.

 

 

5절 전치암호와 치환암호

전치암호란 평문에서 사용하는 문자의 집합과 암호문에서 사용하는 문자의 집합이 동일한것을 의미한다

예) 알파벳 -> 알파벳, 단순히 문자의 집합에서 자리를 바꾸는 규칙이 존재한다.

 

치환암호란 평문에서 사용하는 문자의집합과 암호문에서 사용하는 집합이 다를 수 있음을 의미한다.

예) 알파벳 -> 이진수, 꼭 일대일 대응일 필요는 없음.

전치암호는 치환암호에 종속된다.

 

6절 암호알고리즘과 키

암호알고리즘과 키는 반드시 분리되어야한다. 알고리즘내에 변경 가능한 부분은 항상 키이기 때문이다. 키는 매번 바꾸는것이 좋으며, 키를 재사용하면 해독 가능성이 증가한다.