2020 암호경진대회 1번 문제 풀이

문제 출처 : cryptocontest.kr/

Home - SEC연구소 | 암호분석경진대회

1,2,3번은 일반부와 고등부 공통의 문제였습니다. 4,5번에 비해 상대적으로 쉽지만 참고 논문을 이해하는 것은 생각보다 쉽지 않은 문제입니다.

 

참고 논문 : eprint.iacr.org/2015/802.pdf

2015-802.pdf

0.36MB

 

1. 문제 접근 :

Hill cipher는 고전 암호로써, 행렬의 역연산이 쉽지 않음을 이용합니다.

예를 들어, 

임을 계산하기는 쉽지만, 아래와 같이 행렬식 만으로는 어떤 행렬의 곱으로 이루어졌는지 알수 없습니다.

(위와 같은 경우도 가능하기 때문에 K가 되는 2x2 행렬이 무엇인지 그리고 평문인 (1,2)를 구하는 것은 어렵다.)

 

이러한 hill cipher를 어떻게 하면 풀 수 있는지 살펴보겠습니다.

 

 

2. 문제 풀이 :

 

논문을 참고하여 문제를 풀었습니다. 논문의 핵심 내용만 살펴보도록 하겠습니다.

우선 IC 와 IML의 개념에 대해 이해하여야 합니다.

기존의 hill cipher는 KPA(Known Plaintext Attack)과 COA (Ciphertext Only Attack)에 대해 공격이 쉽지 않다고 알려져있습니다.

지금 문제에 주어진 상황은 평문이 뭔지를 모르므로 COA 를 적용해야하지만 막막합니다. 지금 알파벳으로만 이루어져 있으므로 정말 단순히 COA를 적용한다면 키 행렬의 사이즈 d값을 안다고 가정하여도, $O(26^{d^2})$ 임을 알 수 있습니다. 

 

논문에서 얘기하길, 분할정복 (divide and conquer attack)을 이용하면 $O(d26^d)$ , 중국인의 나머지 정리 (CRT) 를 추가적으로 활용하면 $O(d13^d)$ 로 해결할 수 있다고 설명합니다. 중국인의 나머지 정리를 활용하는 것은 추가적인 것이므로 핵심 내용인 분할정복을 어떻게 하였는지 살펴봅시다.

 

IC 정의

IML 정의

 

논문에서 설명하는 분할정복을 이해하기 위해서는 우선 IC와 IML에 대해 이해하여야합니다. ( IC의 상위 버전이 IML )

우선 둘 다 알파벳의 frequency를 이용합니다.

http://pi.math.cornell.edu/

알파벳의 frequency는 알다시피 E가 제일 높습니다. (한글은 'ㅇ'이 제일 많이 쓰인다고들 합니다.)

위의 IC와 IML에서의 $f_i$에 해당하는 것이 일반적인 frequency 이고 hat 값이 우리가 가진 text의 frequency가 됩니다.

 

충분한 길이의 어떤 text가 존재한다면, 그게 올바른 문장인지 판별하기 위하여 IML을 이용합니다.

(자세한 내용은 논문 참고)

간단히 설명하자면, 충분한 길이의 text는 일반적인 알파벳 frequency를 따라야하므로 이것이 올바른 문장에 가까울수록 $(f_i)(log_2f_i)$ 의 값이 크게 나온다는 것입니다. (IC도 동일한 원리)

결과적으로 위 구한 값의 합의 (-) 값을 구하므로 올바른 문장일 수록 IML값이 작다는 걸 알 수 있습니다.

 

이제 분할정복을 살펴보면, 다음의 과정을 거치면 됩니다.

 

1. 암호문의 알맞은 블럭 단위로 쪼갠다.

위 암호문의 글자를 모두 세어보면 1285자이고, 1285=5*257 이므로 hill cipher에 사용된 d=5 or 257임을 알 수 있습니다. 단순한 COA의 복잡도가 d=5일 때 $O(26^{25})$, divide and conquer attack을 d=257일 때를 이용하면 $O(257*26^{257})$이므로 d=5가 됨을 알 수 있습니다. 효율이 더 떨어지면 안 됩니다. 

암호문을 5글자씩 나누어 257개의 블럭처럼 생각합시다.

 

2. [0,0,0,0,0]~[25,25,25,25,25] 까지의 행렬에 대치된 값으로 각 블럭을 복호화합니다. 

총 257개의 블럭으로 구성된 암호문을 각 행렬 값과 계산하여 IML을 계산합니다. 여기서 key의 역행렬이 존재하여야 암호화, 복호화 모두 가능하므로 행렬의 원소가 mod2, mod13으로 모두 0인 값은 제외합니다. 

이렇게 계산한 총 257개의 값에 대해 IML을 계산하여 그 값을 오름차순으로 정렬하면 끝입니다.

 

추가적으로 계산량을 줄이기 위하여 논문에 나와있는 $d_{i,t}$ 값을 활용하여도 되고, 중국인의 나머지 정리를 이용하여도 됩니다. 

 

수도코드

 

이제 위 과정을 이용해 key의 후보가 되는 행렬 5가지를 조합하여 120가지의 암호문 (5!=120) 을 비교하면 올바른 평문을 얻을 수 있습니다.

 

3. 결과

 

평문 :

정답 평문

 

(띄어쓰기 했을 때)

CRYPTANALYSIS IS THE STUDY OF ANALYXING INFORMATION SYSTEMS IN THE STUDY OF ANALYZING INFORMATION SYSTEMS IN ORDER TO STUDY THE HIDDEN ASPECTS OF THE SYSTEMS CRYPTANALYSIS ISUSED TO BREACH CRYPTOGRAPHIC SECURITY SYSTEMS  AND GAIN ACCESS TO THE CONTENTS OF ENCRYPTED MESSAGES EVEN IF THE CRYPTOGRAPHIC KEY IS UNKNOWN IN ADDITION TO MATHEMATICALANALYSIS OF  CRYPTOGRAPHIC ALGORITHMS CRYPTANALYSIS INCLUDES THE STUDY OF  SIDE CHANNEL ATTACKS THAT DO NOT TARGET WEAKNESSES IN THE CRYPTOGRAPHIC ALGORITHMS THEMSELVES BUT INSTEAD EXPLOIT WEAKNESSES IN THEIR WEAK IMPLEMENTATION EVEN THOUGH THE GOAL HAS BEEN THE SAME THE METHODS AND TECHNIQUES OF  CRYPTANALYSIS HAVE CHANGED DRASTICALLY THROUGH THE HISTORY OF  CRYPTOGRAPHY ADAPTING TO INCREASING CRYPTOGRAPHIC COMPLEXITY RANGING FROM THE PENAND PAPER METHODS OF THE PAST THROUGH  MACHINES LIKE THE BRITISH BOMBES AND BOLOSSUS COMPUTERS AT BLETCHLEY PARK 
IN WORLD WAR TWO TO THE MATHEMATICALLY ADVANCED COMPUTERIZED SCHEMES OF THE PRESENT 
METHODS FOR BREAKING MODERN CRYPTO SYSTEMS OFTEN IN VOLVE  SOLVING CAREFULLYC ON STRUCTED PROBLEMS IN PURE MATHEMATICS THE BEST  KNOWN BEING INTEGER FACTORIZATION GIVEN SOME ENCRYPTED DATA THE GOAL OF  THE CRYPTANALYSTIS TO GAIN AS MUCH INFORMATION AS POSSIBLE ABOUT  THE ORIGINAL UNENCRYPTED DATA TISUSEFUL TO CONSIDER TWO ASPECTS OF  ACHIEVING THIS THE FIRST IS BREAKING THE SYSTEM THAT IS DISCOVERING HOW  THE ENCIPHERMENT PROCESS WORKS THE SECOND IS SOLVING THE KEY 
THAT IS UNIQUE FOR A PARTICULAR ENCRYPTED MESSAGE OR GROUP OF MESSAGE

 

복호화 키 :

논문의 수도코드를 보면 좀 더 복잡한 느낌을 받을 수도 있지만 IML의 값만 활용한다는 것을 이해하면 쉽게 풀 수 있는 문제였습니다. (처음에 잘못 이해해서 IML이 큰 값으로 잡았다가 계속 이상한 게 나와서 당황했었다.)

프로그래밍 능력보다는 수학적 이해가 더 필요한 문제였습니다. (물론 암호학은 수학입니다.)

 

코드는 변수 이름을 너무 막 써놔서 시간이 된다면 정리 후 깃헙에 올리겠습니다.

 

감사합니다.