[암호학] RSA 계산 과정 딱 4개만 외워보자!

1. RSA란?
2. RSA 계산 과정 
3. RSA 계산 과정 (예제 풀이)

 

 

1. RSA란?

 

두 개의 소수가 곱해진 합성수가 있을 때,

곱하는 소수의 크기가 클수록 합성수를 소인수분해 하는 것은 어렵다.

 

예를 들어 19,939이 두 소수 127, 157의 곱으로 이루어져 있다는 것을 구하는 것만 해도 꽤 많은 시간이 걸린다.

RSA 암호화 방식은 이처럼 매우 큰 소수들의 곱으로 생성된 수는 소인수분해 하기 어렵다는 것을 이용한 공개키 암호화 방식이다.

 

(물론, 컴퓨터가 계산하는 것이므로 127,157보다 더 큰 소수의 곱을 이용한다.)

 

2.  RSA 계산 과정

 

 ① p, q 선택

소수 두 가지를 정한다. (p,q) 

 

② n, $ \phi (n)$ 연산

지금 고른 두 소수의 곱을 n이라고 하고 n의 $ \phi (n)$를 구해준다. ($ \phi (n)$=(p-1)(q-1)) 

 

③ Ke 선택

$ \phi (n)$ 와 서로소인 Ke를 선택해준다.  

 

(e의 값에 따라 구해지는 공개키와 개인키 값은 달라질 수 있다.)

 

④ Kd 연산 (이 때, 유클리드 호제법을 쓰면 쉽게 구할 수 있다.)

Ke ×Kd ≡ 1 mod $ \phi (n)$ 에서 kd를 구해준다.  

 

이 과정을 거치면 공개키는 (Ke, n) 개인키는 (Kd, n)이 된다.

 

평문 M의 암호화 식과 암호문 C의 복호화 식은 각각 다음과 같다.

 

[암호화 과정 ] $C \equiv M^{Ke}$ (mod n)

   

[복호화 과정] $M \equiv C^{Kd}$ (mod n)

 

공개키를 이용해 암호화, 개인키를 이용해 복호화하는 것을 볼 수 있다.

여기서 공개키인 (Ke, n)이 공개되는 값들이고 Kd, p, q,  $ \phi (n)$ 는 비밀로 해야하는 값들이다. 

 

3. RSA 계산 과정 (예제 문제)

 

과정을 알면서도 가끔 문제를 풀라고 하면 어려워하는 경우가 많다. 

다음 문제 풀이 과정을 따라와보자.

 

(e의 값에 따라 구해지는 공개키와 개인키 값은 달라질 수 있다.)

 

p = 7, q = 13 일 때 공개키와 개인키를 구하시오.

 

 ① p, q 선택

소수 두 가지를 정한다. (p,q) 

 

-> p, q값이 주어져 있다. p = 7 , q = 13

 

② n, $ \phi (n)$ 연산

지금 고른 두 소수의 곱을 n이라고 하고 n의 $ \phi (n)$를 구해준다. ($ \phi (n)$=(p-1)(q-1)) 

 

-> n = 7 * 13 = 91 , $ \phi (91)$ = (7-1) * (13-1) = 6 * 12 = 72

 

③ Ke 선택

$ \phi (n)$ 와 서로소인 Ke를 선택해준다.  

 

-> 72와 서로소인 Ke = 5 선택 

 

(5말고도 72와 서로소인 수는 많기 때문에 다른 수를 Ke로 선택해도 된다.

단, 여기서 선택되는 값에 따라 공개키와 개인키가 달라질 수 있다.)

 

④ Kd 연산 (이 때, 유클리드 호제법을 쓰면 쉽게 구할 수 있다.)

Ke ×Kd ≡ 1 mod $ \phi (n)$ 에서 kd를 구해준다.  

 

-> 5 * Kd  ≡ 1 mod 72

-> Kd = 29

 

유클리드 호제법을 이용한 풀이

 5 * Kd  ≡ 1 mod 72 식을 잘 살펴보자

 

5의 Kd 배수를 mod 72 했더니 1이 나온다고 한다.

 

mod 72를 했을 때 결과가 1이 나오기 위해서는, 

 

72와 서로소인 수를 mod 72 해주어야 한다. 

 

 

그리고 이건 두 수의 최대 공약수가 1이 되어야 한다는 뜻이다. 

 

그렇다면 이제 유클리드 호제법을 이용할 수 있다.

 

아래는 확장 유클리드 호제법을 이용해 Kd = 29임을 구한 것이다.