Microsoft MVP성태의 닷넷 이야기
Math: 21. "Coding the Matrix" 문제 2.5.1 풀이 [링크 복사], [링크+제목 복사]
조회: 2513
글쓴 사람
정성태 (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)
11757정성태10/19/201820개발 환경 구성: 416. Visual Studio 2017을 이용한 아두이노 프로그램 개발(및 디버깅)
11756정성태10/19/201810오류 유형: 500. Visual Studio Code의 아두이노 프로그램 개발 시 인텔리센스가 안 된다면?
11755정성태10/19/201812오류 유형: 499. Visual Studio Code extension for Arduino - #include errors detected.
11754정성태10/19/201814개발 환경 구성: 415. Visual Studio Code를 이용한 아두이노 프로그램 개발 - 새 프로젝트
11753정성태10/19/201844개발 환경 구성: 414. Visual Studio Code를 이용한 아두이노 프로그램 개발
11752정성태10/18/201826오류 유형: 498. SQL 서버 - Database source is not a supported version of SQL Server
11751정성태10/18/201831오류 유형: 497. Visual Studio 실행 시 그래픽이 투명해진다거나, 깨진다면?
11750정성태10/18/201826오류 유형: 496. 비주얼 스튜디오 - One or more projects in the solution were not loaded correctly.
11749정성태10/18/201873개발 환경 구성: 413. 비주얼 스튜디오에서 작성한 프로그램을 빌드하는 가장 쉬운 방법
11748정성태10/18/201822개발 환경 구성: 412. Arduino IDE를 Store App으로 설치한 경우 컴파일만 되고 배포가 안 되는 문제
11747정성태10/17/201890.NET Framework: 799. C# - DLL에도 EXE처럼 Main 메서드를 넣어 실행할 수 있도록 만드는 방법파일 다운로드1
11746정성태10/15/201852개발 환경 구성: 411. Bitvise SSH Client의 인증서 모드에서 자동 로그인 방법파일 다운로드1
11745정성태10/15/201866오류 유형: 495. TFS 파일/폴더 삭제 - The item [...] could not be found in your workspace, or you do not have permission to access it.
11744정성태10/15/201844개발 환경 구성: 410. msbuild로 .pubxml 설정에 따른 배포 파일을 만드는 방법
11743정성태10/15/201855웹: 37. Bootstrap의 dl/dt/dd 조합에서 문자열이 잘리지 않도록 CSS 설정
11742정성태10/15/201853스크립트: 13. 윈도우 배치(Batch) 스크립트에서 날짜/시간 문자열을 구하는 방법
11741정성태10/15/201847Phone: 13. Android - LinearLayout 간략 설명
11740정성태10/15/201878사물인터넷: 51. Synology NAS(DS216+II)를 이용한 원격 컴퓨터의 전원 스위치 제어
11739정성태10/15/201853Windows: 151. 윈도우 10의 전원 관리가 "균형 조정(Balanced)"으로 바뀌는 문제
11738정성태10/15/201844오류 유형: 494. docker - 윈도우에서 실행 시 "unknown shorthand flag" 오류
11737정성태10/13/201864오류 유형: 493. Azure Kudu - There are 395 items in this directory, but maxViewItems is set to 299
11736정성태10/12/201875오류 유형: 492. Visual Studio 로딩 시 오류 - The 'Scc Display Information' package did not load correctly.
11735정성태10/12/201891VS.NET IDE: 129. Visual Studio - 특정 문자(열)를 개행 문자로 바꾸는 방법
11734정성태10/10/2018173Linux: 4. Synology NAS(DS216+II)에 FTDI 장치 연결 후 C#(.NET Core)으로 DTR 제어파일 다운로드1
11733정성태10/11/2018178Linux: 3. Synology NAS(DS216+II)에서 FTDI 장치를 C/C++로 제어
[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...