[RSA 이해를 위한 몸부림 - 3] RSA 암호화 간단히 이해

RSA 암호화

RSA는 공개키 암호화 방식중 하나이다.

우선, 암호화 하는데에 KEY가 필요하겠다.

키는 총 두 가지의 KEY가 관여하는데 하나는 공개키, 하나는 개인키(비밀키)이다.

먼저 이 KEY들이 어떻게 만들어지는지 보자.

1. KEY

우선 공개키.

임의의 서로소인 수 p, q를 정하자.
그리고

n = p * q
Φ(n) = (p-1) * (q-1)

이라 하자. (Φ는 "파이" 라고 읽으면 된다)

그리고 1 < e < Φ(n) 이면서 Φ(n)과 서로소인 e를 정한다.

여기까지 잘했다면 공개키는 두 수 n과 e의 조합인 <n, e> 로 정할 수 있다.

다음은 개인키.

여기서 이전에 설명했던 모듈러 연산 및 역원이 쓰이는데

공개키 e와 곱해져서서 Φ(n)으로 나눴을 때 나머지가 1이 되는 d가 개인키에 이용된다.

식으로 나타내면..

e*d mod Φ(n) = 1

이 되어야한다.

그렇게해서 d를 구했다면, 개인키는 두 수 n과 d의 조합인 <n, d> 이다.

2. 원하는 평문 암호화

우선 RSA의 개략적인 과정을 살펴보자.

두 사람 A, B 가 서로 데이터를 주고받는다고 가정해보자.

위 사진은 일단 A가 B에게 일방적으로 데이터를 보내는 순간 이다.

목적지가 B이므로 B의 공개키를 서로 나눠갖고, B의 공개키로 데이터를 암호화해서 보내야한다.

데이터를 B가 무사히 받았다면, B는 B의 개인키로 데이터를 복호화하여 열어보면된다.

반대로, 만약 B가 A에게 보낸다고 하면 A의 공개키를 서로 나눠갖고 B가 그 공개키로 암호화하면 된다.

암호화 하는 식이다.

M은 평문이고 개인키 <n, e> 로 암호화 한 결과가 C이다. 간단하다.

3. RSA 암호문 평문으로 복호화

평문으로 복호화는 개인키 짝 <n, d> 이 이용된다.

이 또한 간단하다.

4. 예제

한 번 위 과정들을 수동으로 직접해보자.

[1] KEY 만들기

p = 5 , q =11 로 하자. 두 수는 서로소가 확실하다.

n = 55, Φ(n) = 40 으로 정할 수 있다.

e = 13 이라 하자.

그러면, 공개키는 < 55, 13 >

13 * d (mod 40) = 1 에서 d를 구해야 한다.

대충 40에 대한 모듈러 범위에서 추측해도 되지만 확장된 유클리드 알고리즘으로 풀어보자.

1 = 13 * d + 40 * t

위 식은 모듈러 연산 과 유클리드 알고리즘 에서 성립함을 알 수 있다.

q	r1	r2	r	d1	d2	d	t1	t2	t
0	13	40	13	1	0	1	0	1	0
3	40	13	1	0	1	-3	1	0	1
13	13	1	0	1	-3	40	0	1	-13

위 표를 통해 d = -3 임을 알 수 있다. 하지만, d는 양수여야 한다.

고로 d = (-3 + 40) mod 40 = 37 로 정할 수 있다.

암호화 시킬 데이터는 숫자 30 으로 하자.

이렇게 암호문 C가 만들어질 것이다.

위 처럼 30의 13제곱은 매우 크기에 파이썬같은 유용한 도구를 이용하자.

암호문은 정수 50이 되었다. 그러면, 이를 개인키로 복호화 해보자.

위와 같이 복호화 하면 평문으로 30이 나와야할 것이다.

아주 잘나온다.

5. 보안성 ???

위에서 설명한 통신과정에서 보면 공개키는 공공연히 공개되는 글자 그대로 공개키이다.

공개키로 암호화 하는 것을 보면 왠지 공개키가 유출되면 위험한게 아닌가 싶었다.

복호화 하려면, d 값을 알아야한다. d값을 알려면, Φ(n)도 알아야한다.

하지만, 공개키가 유출되었다고 가정하면 해커가 아는 것은 n값과 e값 뿐이다.

예제에서는 55라는 작은 숫자가 이용되었지만, 실제상황에서는 몇 억, 몇 조의 수가 n값이 되어버릴 수도 있다. 이렇게 되면 소인수분해를 며칠을 해야 p, q가 구해질까 말까한 상황이 된다.

고로, 일단 Φ(n)를 구하는 과정부터 고난의 길인 것이다.
(물론 양자컴퓨터가 나와서 이 연산을 몇 시간만에 해치우는 날이 오면 의미없는 일이 되어버리겠지만)

혹여나 만약 Φ(n)를 알게되어도 모듈러의 합동성질 때문에 d 값을 한 번에 특정짓는 것은 상당히 오랜시간이 걸릴 것이다.

위에서 예제를 다시 가져오자면, 어쨌든 e*d를 40으로 나눠서 1이 나와야하는 것이라면, d가 37이 아니라 77이 될 수도 있다는 것이다.

한마디로 보안성에서는 현시점으로는 시간과 노력을 무수히 쏟아야 뚫어낼 수 있을만한 암호화방식이라는 것이다.

.
.
.
.
.
contact : a42873410@gmail.com