RSA 암호화 알고리즘 (1)
RSA는 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반한 공개키 방식의 암호 알고리즘이다. 이론을 체계화한 3인(Ron Rivest, Adi Shamir, Leonard Adleman)의 성 첫글자를 따서 명명되었다.
RSA 알고리즘 개요
RSA는 개략적으로 다음과 같은 순서의 과정으로 나누어 볼수 있다.
- 공개키와 개인키 생성
- 공개키를 사용한 암호화
- 개인키를 사용한 복호화
공개키와 개인키를 생성하기
공개키는 (n,e) 라는 두개의 수로 이루어지고, 개인키는 (n,d) 라는 두개의 수로 이루어진다. 결국 공개키와 개인키를 만드는 것은 3개의 숫자 n, e, d 를 구하는 과정이다.
n 값 구하기
먼저, 두 소수 p와 q를 임의로 정한다. (p ≠ q 이어야 한다.)
n을 다음과 같이 구한다.
n = p * q
Φ(n) 값 구하기
p와 q를 다음과 같이 다음식에 대입하여 Φ(n)를 구한다.
Φ(n) = (p - 1) * (q - 1)
e 값 구하기
e는 다음 두가지 조건을 모두 만족하는 값이다.
1 < e < Φ(n)
e는 Φ(n)와 서로소
서로소: 1 이외에 공약수를 갖지 않는 둘 이상의 양의 정수
d 값 구하기
아래 식을 만족하는 d를 구해야 한다. (mod는 나머지 연산자를 뜻한다.)
(e * d) mod Φ(n) = 1
풀어서 말하면, e * d 값을 Φ(n)로 나누었을때 나머지가 1인 d를 구하는 것이다.
여기까지 n, e, d를 모두 구하여, 공개키(n, e)와 개인키(n, d)가 완성된다.
공개키를 사용하여 평문을 암호화
공개키(n, e)를 사용하여 암호화 한다.
먼저, 암호화하기 전의 값을 평문 M이라 하고 암호화한 값을 암호문 C라고 하자.
암호문 C는 다음과 같이 구한다. (^는 제곱연산자를 뜻한다.)
C = (M ^ e) mod n
개인키를 사용하여 암호문을 복호화
개인키(n, d)를 사용하여 암호문 C를 평문 M으로 복호화 한다.
M = (C ^ d) mod n
예제
위에 설명한 알고리즘의 순서대로 실제값을 대입하여 계산해 보자.
<1단계> 임의 소수 p, q 정하기
p = 2, q = 7 로 정하자.
<2단계> n값 구하기
n = 2 * 7
n = 14
<3단계> Φ(n)
Φ(n) = (2 - 1) * (7 - 1)
Φ(n) = 6
<4단계> e값 구하기
1 < e < 6
e는 6와 서로소
5가 가능한 값이다. (2, 3, 4, 5 숫자 하나씩 조건에 맞는지 확인해 보았다.)
e = 5
<5단계> d값 구하기
(5 * d) mod 6 = 1
5 또는 11이 가능한 값이다. (1, 2, 3, …, 11 역시 하나씩 확인해 보았다.)
5는 e와 동일한 값이므로 11로 정하자.
d = 11
<6단계> 공개키 완성
공개키는 (14, 5)이며, 개인키는 (14, 11) 이다.
<7단계> 암호화
평문 M 을 3 이라고 하자.
암호문 C는 다음과 같이 계산된다.
C = (3 ^ 5) mod 14
계산기를 두드려 계산해보자.
C = 5
<8단계> 복호화
다시 암호문 5 를 통해 평문 M은 다음과 같이 계산된다.
M = (5 ^ 11) mod 14
상당히 큰 숫자이다. 역시 계산기를 두드려 계산해보자.
M = 3
지금까지 RSA의 전체 과정을 개략적으로 설명하였다. 하지만, 실제 적용을 위해서는 추가적으로 몇가지 알고리즘이 더 필요하다. 이어지는 포스트에서는 조금더 세부적인 설명을 해보겠다.
