Microsoft MVP성태의 닷넷 이야기
Math: 21. "Coding the Matrix" 문제 2.5.1 풀이 [링크 복사], [링크+제목 복사]
조회: 2120
글쓴 사람
정성태 (kevin13@chol.net)
홈페이지
첨부 파일

"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 라이브러리로 복소수 표현
; http://www.sysnet.pe.kr/2/0/10974

행렬 연산으로 본 해밍코드
; http://www.sysnet.pe.kr/2/0/11026

C# - 오일러 공식을 이용한 복소수 값의 라디안 회전
; http://www.sysnet.pe.kr/2/0/10976

C# - Lights Out 퍼즐 풀기
; http://www.sysnet.pe.kr/2/0/10981




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]





[최초 등록일: ]
[최종 수정일: 7/17/2017 ]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:kevin13@chol.com

비밀번호

댓글 쓴 사람
 



2018-06-11 12시49분
정성태

[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
11658정성태8/18/20185사물인터넷: 31. 커패시터와 RC 회로파일 다운로드3
11657정성태8/18/201810사물인터넷: 30. 릴레이(Relay) 제어파일 다운로드3
11656정성태8/18/201831사물인터넷: 29. 트랜지스터와 병렬로 연결한 LED파일 다운로드1
11655정성태8/18/201826사물인터넷: 28. 저항과 병렬로 연결한 LED파일 다운로드1
11654정성태8/18/201844사물인터넷: 27. 병렬 회로의 저항, 전압 및 전류파일 다운로드1
11653정성태8/18/201828사물인터넷: 26. 입력 전압에 따른 LED의 전압/저항 변화파일 다운로드1
11652정성태8/18/201834사물인터넷: 25. 컬렉터 9V, 베이스에 5V와 3.3V 전압으로 테스트하는 C1815 트랜지스터파일 다운로드1
11651정성태8/18/201846사물인터넷: 24. 9V 전압에서 테스트하는 C1815 트랜지스터파일 다운로드2
11650정성태8/18/201842사물인터넷: 23. 가변저항으로 분압파일 다운로드1
11649정성태8/14/201869사물인터넷: 22. 저항에 따른 전류 테스트파일 다운로드1
11648정성태8/14/201878사물인터넷: 21. 퓨즈를 이용한 회로 보호파일 다운로드3
11647정성태8/8/2018145오류 유형: 476. 음수의 음수는 여전히 음수가 되는 수(절대값이 음수인 수)
11646정성태8/8/201877오류 유형: 475. gacutil.exe 실행 시 "Failure initializing gacutil" 오류 발생
11645정성태8/8/201887오류 유형: 474. 닷넷 COM+ - Failed to load the runtime.
11644정성태8/8/2018171디버깅 기술: 119. windbg - 닷넷 개발자를 위한 MEX Debugging Extension 소개
11643정성태8/12/2018172사물인터넷: 20. 아두이노 레오나르도 R3 호환 보드의 3.3v 핀의 LED 전압/전류 테스트 [1]파일 다운로드1
11642정성태8/3/201899Graphics: 19. Unity - LightMode의 ForwardBase에 따른 _WorldSpaceLightPos0 값 변화
11641정성태8/3/2018135Graphics: 18. Unity로 실습하는 Shader (10) - 빌보드 구현파일 다운로드1
11640정성태8/3/2018117Graphics: 17. Unity - World matrix(unity_ObjectToWorld)로부터 Position, Rotation, Scale 값을 복원하는 방법파일 다운로드1
11639정성태8/2/2018135디버깅 기술: 118. windbg - 덤프 파일로부터 추출한 DLL을 참조하는 방법
11638정성태8/2/2018202오류 유형: 473. windbg - 덤프 파일로부터 추출한 DLL 참조 시 "Resolved file has a bad image, no metadata, or is otherwise inaccessible." 빌드 오류
11637정성태8/1/2018113Graphics: 16. Unity - World matrix(unity_ObjectToWorld)로부터 TRS(이동/회전/크기) 행렬로 복원하는 방법파일 다운로드1
11636정성태8/1/2018114Graphics: 15. 3D 공간에서 두 점이 이루는 각도 구하기파일 다운로드1
11635정성태8/1/2018101오류 유형: 472. C# 컴파일 오류 - Your project is not referencing the ".NETFramework,Version=v3.5" framework.
11634정성태8/1/2018140.NET Framework: 790. .NET Thread 상태가 Cooperative일 때 GC hang 현상 재현 방법파일 다운로드1
[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...