"Coding the Matrix" 문제 2.5.1 풀이
"코딩 더 매트릭스" 책에서, 오늘 우연히 60페이지에 있는 다음의 문제가 눈에 들어왔습니다.
Problem 2.5.1: 11-심볼 메시지를 다음과 같이 암호화하였다고 생각하자. 각 심볼은 0과 26
사이의 숫자에 의해 표현된다(A -> 0, B -> 1, ..., Z -> 25, space -> 26). 각 숫자는 5-비트 이진
시퀀스 (0 -> 00000, 1 -> 00001, ..., 26 -> 11010)에 의해 표현된다. 마지막으로, 55비트의 결과
시퀀스는 결함이 있는 일회성 패드를 사용하여 암호화된다. 키는 55개의 랜덤 비트가 아니라 5
개 랜덤 비트로 구성된 동일한 시퀀스를 11번 복사한 것이다. 암호문은 다음과 같다.
10101 00100 10101 01011 11001 00011 01011 10101 00100 11001 11010
평문을 찾아보자.
영문 판인 경우는 1.5.1 번 문제로 나옵니다.
Problem 1.5.1: An 11-symbol message has been encrypted as follows. Each symbol is represented
by a number between 0 and 26 (A → 0,B → 1, . . . ,Z → 25, space → 26). Each number
is represented by a five-bit binary sequence (0 → 00000, 1 → 00001, ..., 26 → 11010). Finally,
the resulting sequence of 55 bits is encrypted using a flawed version of the one-time pad: the
key is not 55 random bits but 11 copies of the same sequence of 5 random bits. The cyphertext
is
10101 00100 10101 01011 11001 00011 01011 10101 00100 11001 11010
Try to find the plaintext.
위의 문제를 풀려면 책을 읽어야만 알 수 있는 2가지 배경 설명이 필요합니다.
우선, one-time pad(일회성 패드)라고 불리는 암호 체계는 키의 각 비트가 평문의 각 비트를 암호화하는데 단 한 번만 사용된다는 것입니다. 가령, 다음과 같은 평문 비트 열이 있을 때,
00101001010010101001010101010010101
암호화를 위한 키가 평문 비트 열의 길이와 동일하게 다음과 같다면,
01001001010010100101001100100010100
이를 일회성 패드라고 하는 것입니다. 평문과 키가 이런 식이면 '완벽한 비밀 유지'가 가능하다고 하는데, 한 가지 (치명적인) 단점이라면 긴 메시지를 암호화했을 때 그만큼의 키 길이도 함께 필요하기 때문에 양측이 키를 동의했어야 할 시점에 많은 비트를 확보해야 한다는 점입니다. one-time pad라는 용어로 인해 문제가 다소 어려워진 듯한데, 결국 그 부분의 이야기는 다음과 같이 축약해서 정리할 수 있습니다.
55비트의 결과 시퀀스는 결함이 있는 일회성 패드를 사용하여 암호화된다.
키는 55개의 랜덤 비트가 아니라 5개 랜덤 비트로 구성된 동일한 시퀀스를 11번 복사한 것이다.
==> 즉, 암호화에 사용한 키의 길이가 5비트라는 의미
2번째로 알아야 할 사항은 암호화 방식인데, 책에서는 단순히 XOR 연산을 따르는 것으로 나옵니다.
자, 그럼 이제 문제가 풀릴 것입니다. 결국 암호화 알고리즘은 XOR 연산이며,
0 xor 0 = 0
1 xor 0 = 1
0 xor 1 = 1
1 xor 1 = 0
따라서 문제에서 제시한 암호문은 다음과 같은 연산으로 이뤄진 결과물입니다.
p == plain text bits
k == key bits
e == encrpyed bits
p1 xor k1 = e1 1
p2 xor k2 = e2 0
p3 xor k3 = e3 1
p4 xor k4 = e4 0
p5 xor k5 = e5 1
.
.
.
pi xor ki = ei
따라서, 복호화는 이런 방식으로 이뤄집니다.
1 xor k1 = p1
0 xor k2 = p2
1 xor k3 = p3
0 xor k4 = p4
1 xor k5 = p5
.
.
.
ei xor ki = pi
키 길이가 5비트라고 했으니 그럼 키의 후보군은 2의 5승으로 32개가 됩니다.
00000
00001
00010
00011
00100
...[생략]...
11100
11101
11110
11111
32개뿐이기 때문에 각각의 키로 암호문과의 xor 연산을 해보면 다음의 평문 후보군이 나오고,
VEVLZDLVEZ
WHWI AIWH Z
ZIZHVPHZIVW
YJYGUOGYJUX
L EWME LWV
EVE IS EVIL
HWHZLRZHWLI
GXGYKQYGXKJ
이 중에서 정상적인 영어 문장은 "EVE IS EVIL"입니다. (
첨부 파일은 이 글의 C# 예제 코드를 포함합니다.)
그렇다면 결함이 없는 일회성 패드였다면 어땠을까요? 그럼 55비트의 키 길이를 갖는다는 것이고 2의 55승(36,028,797,018,963,968)에 해당하는 키 후보군이 존재하게 됩니다. 물론, 이 정도라고 해도 근래의 컴퓨팅 성능으로는 풀어낼 수 있지만 복호화 된 텍스트가 정상적인 영어 문장인지도 판별해야 하기 때문에 일회성 패드로 암호화한 것만으로도 복호화를 위한 연산을 꽤나 증가시킬 수 있습니다.
참고로, 평문 후보군이 8개로 키의 후보군이 32개인 것에 비해 적게 나옵니다. 이유는 간단합니다. 이 문제에서 평문의 경우 정의역이 0 ~ 26, 공역과 치역은 5비트 범위를 갖는 0 ~ 31입니다. 하지만 key의 범위가 5비트이기 때문에 공역/치역이 5비트 범위를 갖게 되는 것일 뿐, 일단 key가 선택된 이후부터는 5비트 내의 일부만 공역/치역이 됩니다. 이로 인해 key가 확정되기 전의 공역/치역의 범위가 0 ~ 31이었던 것이, key가 선택되는 시점에 0 ~ 31 중의 일부로 공역과 치역이 바뀌기 때문에 그에 속하지 않는 숫자는 가역 조건이 맞지 않는 경우가 나오게 되고 그것이 평문 후보군을 걸러내게 됩니다.
말로 하니 좀 이상하게 설명이 되었는데, 예를 들어 보면 쉽습니다. 가령 키가 11100이고 암호화된 비트가 00011이면 이를 xor 연산했을 때 11111(31)이 나오지만 이는 26의 숫자만 가질 수 있는 정의역에 해당하지 않으므로 그런 사례가 나오면 11100이라는 키는 더 이상 복호화 연산에 적합하지 않으므로 평문 후보군도 줄어들게 되는 것입니다. 당연한 것 같으면서도, key가 선택되기 전과 선택된 후의 공역/치역이 달라진다는 것은 암호화 자체는 적합한 key에 대해서는 전단사 함수이지만 그 외의 key 후보군들에 대해서는 모든 값들에 대해 가역적이지는 않다는 재미있는 결과가 나옵니다.
게다가 XOR의 출력에 대한 균등 분포도 재미있습니다. 대표적으로 치환 암호(Substitution cipher)의 경우 단일 치환 방식은 출력이 균등하지 않아 단어의 빈도에 대한 분포를 이용해 해독이 (어느 정도는) 쉽다는 문제가 있는데, 단순히 비트 수준의 xor 연산에서부터 균등 분포를 제공해 준다는 것은 2진수를 기반으로 한 프로그래밍이 암호화에 꽤나 적합해지는 조건을 제시해 줍니다.
(수학을 그다지 잘 알지 못하는 제 수준에서) 암호화 방식의 관점으로 좀 더 이야기를 해보면, 대체적인 치환 암호화 방식은 정의역이 인코딩되는 형식이기 때문에 공역과 치역은 같지만 정의역과는 같지 않을 수 있습니다. 반면 전치 암호(Transposition cipher)화 방식의 경우에는 정의역/공역/치역이 같습니다. 그리고, 치환/전치 암호는 key의 선택 여부와 상관없이 공역과 치역이 같습니다. (맞나요? ^^ 잘 알지도 못하면서 느낀 바를 쓰려니 힘들군요.)
그러고 보니, "코딩 더 매트릭스" 덕분에 쓴 글이 벌써 5개가 되었군요.
OxyPlot 라이브러리로 복소수 표현
; https://www.sysnet.pe.kr/2/0/10974
행렬 연산으로 본 해밍코드
; https://www.sysnet.pe.kr/2/0/11026
C# - 오일러 공식을 이용한 복소수 값의 라디안 회전
; https://www.sysnet.pe.kr/2/0/10976
C# - Lights Out 퍼즐 풀기
; https://www.sysnet.pe.kr/2/0/10981
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]