2009년 해킹방어대회 예선 6번, RSA 알고리즘

[알고리즘]
1). 두 개의 큰 소수 p와 q를 선정한 다음에 법n 과 φn 을 계산합니다.
법n = pq
φn = (p-1) (q-1)

2). 공개키 e는 φn과 서로 소(素)의 관계가 되게 임의로 선정합니다.

3). e*d Mod φn = 1 의 관계에 있는 개인키 d를 유클리드 알고리즘을 통해 구합니다.

4). {e, n}을 공개키로 공개하고, {d} 는 개인키로 자신이 안전하게 보관합니다.
m = 평문, e,n = 공개키, d = 개인키, c = 암호문

RSA 암호화공식 : Ｅke(m) = m^e Mod n = c
RSA 복호화공식 : Ｄke(c) = ((m^e)^d) Mod n = c^d Mod n = m

[예제 첫번째]
n = pq = 711 = 77
φn = (p-1) (q-1) = 610 = 60
공개키e 는 φn과 서로소의 관계에 있는 임의의 정수 7로 선정합니다.
e = 7
따라서, 개인키는 유클리드 알고리즘을 이용하면 개인키 d = 43 이 됩니다.
평문 m 을 8로 하고 RSA 암호화 공식을 통해 암호문을 구해보면

c = 8^7 Mod 77
= 2097152 Mod 77
= 57

이제 평문m(=8)이 암호문c(=57)로 암호화 되었습니다.
그렇다면 이제 개인키d(=43)을 사용하여 다시 암호문 c(=57)를 복호화해보면

m = 57^43 Mod 77
= 3181403788572786716059998378326698266679069780899509454959934125355133265193 Mod 77
= 8

m = 8로 다시 복호화 됩니다.

[예제 두번째]
마지막으로 2009년도 해킹방어대회 예선 6번 문제를 풀어 보겠습니다. 문제는 아래와 같습니다.

6번 문제

세계적인 암호학 박사가 꿈인 팔준표씨는 친구인 김현증씨에게 메일을 보냈다.
그런데 중간에 자칭 해커인 김밤씨가 메일을 가로챘다. 그러나, 메일은 암호화 되어 있었다.
여러분은 이 메일을 해독할 수 있는가?

---- BEGIN HD PUBLIC KEY ----
 public=149
 mod=247         
---- END HD PUBLIC KEY ----

파일 : 2.bin

그리고 위에 첨부한 암호화 된 문자열이 적힌 파일이 하나 주어집니다. 우선 주어진 값에서 mod 값이 우리가 알고 있는 N 값이며 public 값은 E 값으로 보입니다. 이제 주어진 값으로 Private Key를 구해 보도록 하겠습니다.

n = p q
247 = 13 19

φn = (p-1) (q-1)
φn = (13-1) (19-1) = 12*18 = 216

ed Mod φn = 1
(149 d) mod 216 = 1

d = 29

이제 Private Key(d) 값을 구했으므로 평문으로 변환을 해보도록 하겠습니다. RSA 알고리즘을 보면 암호문을 평문으로 바꾸는 공식은 다음과 같습니다.

평문 = (암호문 ^ Private Key) Mod N

이제 Python으로 복호화 하는 코드를 작성해 보도록 하겠습니다. 우선 주어진 암호화 파일을 Hex 값으로 변환을 합니다.
변환한 코드는 아래와 같습니다.

be ae 45 ba b0 df 9d 66 8a 47 b0 34 d4 48 f6 8a 41 df 48 29 9e a5 48 a2 6c 89 df 9e 7f 30 f6 6c f4 df bc 35 3e 91 df 39 af 5a 28 ac bb df 45 d5 b4 bb df 47 47 9b ba df be 19 ae 66 df f4 48 1b 89 8a 18 1b b9 6c 1d df 25 f4 f4 e6 48 a2 6c 1d be a2 32 34 d4 48 29 9e a5 df 7e d0 25 c0 ac f6 9b e5 6f cf df 15 71 3e ef dd 72 c8 e8 ed 72 4d ce 14 91 72 a7 4f 43 32 de 6e db 15 df 6c 1d be a2 32 34 d4 8a 18 1b 5d 47 8e df 9d 66 8a 47 b4 bb df 6c cd 1b cf f4 d1 df 7e 56 30 94 6c d5 df be 19 ae 66 30 94 6c 47 1b 89 df 30 6b 44 84 df 48 6b df b4 c9 be a2 32 34 d4 34 d4 be e7 1a d5 b4 cd df be 19 ae 66 ae 7f f4 19 6f cf df 48 f6 df be f2 be 7e 45 d5 9e 7f df 6f 6b 6c 25 df be 19 ae 66 30 94 6c d5 df f4 94 be e7 c0 48 db df 8a 18 1b 45 df 6f 6b 6c 25 df 1b 30 c0 3b 1b 89 df b4 b9 df 9e f6 df 6c 1c be e7 32 34 d4 be 19 ae 66 30 94 d2 df 70 ed a3 5a b8 b8 ed af 8f 28 5a 39 79 39 8b 70 2b a3 2b 5a ed 39 b8 28 b8 ed a7 4b a7 b8 28 8b 8b 39 2b a3 28 03 a7 28 2b 2b a3 8f 39 b8 8f b8 39 ed 39 b8 b8 2e a7 28 8f ed a3 a3 a7 b8 28 03 70 28 2b 5a b8 79

이제 위 값을 hex.txt로 저장하고 복호화를 진행합니다. 코드는 아래와 같습니다.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

'''
---- BEGIN HD PUBLIC KEY ----
 public=149
 mod=247         
 ---- END HD PUBLIC KEY ----
'''
# d = 29

f = open('hex.txt', 'r')
data = f.read()
f.close()

data = data.split(' ')
print data

final = ''
for x in data:
    # 평문 = (암호문 ^ Private Key) mod N
    final += chr(pow(int(x, 16), 29) % 247)

f = open('output.txt', 'w')
f.write(final)
f.close()

정상적으로 복호화가 진행된 것을 확인할 수 있습니다.

참고 : http://blog.naver.com/shu777/120005550944