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

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

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

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

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

RSA 암호화공식 : Eke(m) = m^e Mod n = c
RSA 복호화공식 : Dke(c) = ((m^e)^d) Mod n = c^d Mod n = m

[예제 첫번째]
n = p
q = 711 = 77
φn = (p-1)
(q-1) = 6*10 = 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번 문제를 풀어 보겠습니다. 문제는 아래와 같습니다.
[code]6번 문제

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

—- BEGIN HD PUBLIC KEY —-
 public=149
 mod=247         
—- END HD PUBLIC KEY —-
[/code]
1391877951.bin
그리고 위에 첨부한 암호화 된 문자열이 적힌 파일이 하나 주어집니다. 우선 주어진 값에서 mod 값이 우리가 알고 있는 N 값이며 public 값은 E 값으로 보입니다. 이제 주어진 값으로 Private Key를 구해 보도록 하겠습니다.

n = p q
247 = 13
19

φn = (p-1) (q-1)
φn = (13-1)
(19-1) = 1218 = 216

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

d = 29

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

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

이제 Python으로 복호화 하는 코드를 작성해 보도록 하겠습니다. 우선 주어진 암호화 파일을 Hex 값으로 변환을 합니다.
변환한 코드는 아래와 같습니다.
[code]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[/code]

이제 위 값을 hex.txt로 저장하고 복호화를 진행합니다. 코드는 아래와 같습니다.
[code]#!/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()
[/code]

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

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

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다