::: 삼성전자 소프트웨어멤버십 블로그 :::

RSA 알고리즘은 인수분해 문제를 응용한 알고리즘이다. RSA 알고리즘에서 활용하는 이론적인 정리부터 살펴보기로 한다.

1. 기본 정리

1600년대 프랑스의 수학자인 페르마(Pierre de Fermat)는, p가 소수이고 p와 서로소인 양의 정수인 m에 대하여 다음 정리를 발견하였다.

스위스에서 출생한 1700년대의 수학자 오일러(Leonhard Euler)도 위 페르마의 정리와 유사한 정리를 발견한다. p와 q가 소수이고, m < n 인 m과 n은 서로소이며, n=p×q이면, 다음 오일러의 정리가 만족된다.

2. 기본 정리의 응용

(식2)의 양변에 m을 곱하면, 아래의 식이 구해진다.

위 (식3)의 모듈러 연산식을 음미하면, m에 대하여 {(p-1)×(q-1)+1}회 지수승하면 원래 값 m으로 되돌아오는 것으로 해석할 수 있다.

여기서, φ = (p-1)×(q-1)로 두고, φ+1을 다음과 같이 두수 e와 d의 곱으로 나타내기도 한다. 그러면 (식3)은 다음의 (식4)와 같다.

φ(파이)기호는 오일러 φ 함수 (Euler's phi function)를 뜻한다. 1부터 n까지의 양의 정수 중에 n과 서로소인 것의 개수를 나타내는 함수이다. 양의 정수 n에 대하여 정의되며 함수로 φ(n)으로 표기한다.

(식4)로부터 가상의 값 c를 통해, 다음의 두 식을 표현해 낼 수 있다.

(식5)의 c값인 좌변항을 (식6)에 대입하고, (식4)의 e×d를 (p-1)×(q-1)+1로 치환하면, 원래의 (식3)이 구해진다.

그리고 (식2)와 (식3)으로부터, 다음의 관계식을 얻을 수 있다.

이제 (식7)을 고려하여 (식4)의 두 수 e와 d의 곱 e×d가 가질 수 있는 값을 일반화하면, e×d는 다음의 값을 가질 수 있다.

- φ+1을 확장한 iφ+1 또는

- x mod φ=1을 만족하는 x값

(식5)와 (식6)에서 m과 c를 각각 다음과 같이 두기로 하자.

- m : 암호화하기 전의 메시지(원문 또는 평문, plain text)

- c : 암호문(cipher text)

그러면, (식5)는 암호화 과정, (식6)은 복호화 과정으로 활용하여, 다음과 같이 원문 m에 대한 암호문 c와 암호문 c를 복호화한 m을 구할 수 있다.

RSA 알고리즘의 공개키 (n, e)로 생성된 암호문 c에 대하여, 개인키 (n, d)를 모르는 상황에서 복호화 하여 m을 알아내려면 다음의 과정을 거치게 될 것이다.

마지막 단계까지 가더라도, n이 큰 소수의 곱으로 이루어진 합성수라면, 인수분해 문제로 인해 소인수 분해를 효과적으로 계산할 수 없다. 따라서 현실적으로 n을 1024 bits이상 크기로 구성한다면, 복호화 키(key) 없이 p와 q의 값을 알아내어 암호문을 복호화하기가 현실적으로 불가능하다.