RSA 알아보기

 
 

들어가며

우리가 지난번에 알아본 DES는 암호화와 복호화를 같은 키 값으로 수행하는 대칭키 암호입니다. 실제 통신에서 대칭키 암호를 사용하려면 통신에 앞서 송신자와 수신자가 대칭키를 사전에 공유하는 과정이 필요합니다.
 
알다시피 대칭키는 외부에 노출되어선 안됩니다. 하나의 키를 통해 암호화와 복호화를 동시에 수행하기 때문에, 키가 노출된다면 누구라도 해당 통신을 탈취해서 내용을 확인할 수 있게 되어 해당 키를 사용한 암호화는 결국 무용지물이 됩니다.
 
처음에는 송신자와 수신자가 물리적으로 만나 사전에 키를 공유하는 방법을 취했습니다. 직접 교환한다면 중간자가 개입될 여지도 없고, 가장 확실하고 안전하게 키를 교환할 수 있는 방법이었습니다. 그러나 물리적인 교환이라는 방법은 그 자체로 단점이 명확한 방법이었습니다. 교환해야 하는 사람이 아주 먼 곳에 있는 사람이라면 어떨까요? 또는 교환해야하는 사람이 아주 많아진다면 하나하나 교환할 수 있을까요?
 
 
 

비밀 키 안전하게 교환하기

결국 이러한 해결 방법으로는 한계가 있었고, 사람들은 다른 방법을 생각하기 시작했습니다.
 
 

키 배포 센터

 
첫 번째는 키 배포 센터(Key Distribute Center)입니다. 키 배포 센터는 송신자와 수신자가 비밀키를 직접 교환하는 대신, 중간에서 키를 관리할 역할을 하는 서버를 만들어주는 개념입니다. 키를 발급받기 위해 하나의 키 배포 센터를 만들고, 사람들이 이 배포 센터에 접근하여 키를 받아 사용하게 된다면 아무리 멀리 떨어져있는 상대라도 손쉽게 키를 발급받아 사용할 수 있었습니다.
 
다만 이 방법의 경우 사람들이 많이 몰렸을때 키 배포 센터에 부하가 걸릴 위험이 있고, 해당 배포 서버가 마비되면 그 서버를 사용하던 모든 사용자의 연결에 영향을 줄 수 있다는 단점이 있었습니다. 연결을 사용하는 모두가 하나의 센터에 의존하고 있다보니, 공격자들도 개개인의 연결이 아닌 이 배포 서버 자체를 대상으로 공격을 시도하기 시작하여 이러한 약점이 존재한다는 것을 알게 되었습니다.
 
 

디피 - 헬먼 키 교환 방식

 
두 번째 방법은 디피-헬먼(Diffie-Hellman) 키 교환 방식입니다. 이 방법은 비밀 키를 직접 교환하는게 아닌, 비밀 키를 만들 수 있는 재료를 서로 교환하고, 각자 연산을 통해 비밀 키를 생성하는 방식입니다. 어떻게 비밀 키를 생성할 수 있는지 과정을 살펴보면 다음과 같습니다.
 

1. 통신을 진행할 두 사람 A, B가 소수 p와 p보다 작은 양수 g를 골라 사전에 공유합니다.
2. A와 B가 각각 정수를 하나씩 선택(각각 a, b)합니다.
3. 각자가 선택한 정수를 토대로 g^(a || b) mod p 를 계산합니다. (계산한 값을 각각 A', B')
4. 서로가 서로에게 계산한 값(A', B')을 전송합니다.
5. A는 B'^a mod p를, B는 A'^b mod p를 계산합니다. 이때 B'^a mod p와 A'^b mod p는 지수법칙에 의해 g^(ab) mod p 로 같은 값이 됩니다.
6. 계산 결과를 비밀 키로 사용합니다.

 
이렇게 나온 비밀 키는 처음에 고른 소수 p가 충분히 크다는 전제 하에, 사실상 역산이 불가능합니다. 중간에서 통신을 도청하는 것으로 얻을 수 있는 정보는 g^a와 g^b 인데, 이를 통해 g^(ab) 를 찾아내는 것은 현재 인류가 보유하고 있는 모든 기기로부터의 컴퓨팅 능력을 총동원해도 알아내기 어렵습니다.
 
이렇게 말로만 설명을 들으면 언뜻 쉽게 뚫릴것처럼 보이기도 합니다. 컴퓨터를 이용하면 막연히 연산이 가능하지 않을까 하는 의심이 들어서 실제로 충분히 큰 숫자를 가져와서 보겠습니다.
 
아래 수는 충분히 크다고 알려진 300자리에 가까운 348자리의 소수로 추정되는 숫자입니다. 이 정도의 사이즈라면 현재 컴퓨팅 능력으로는 역연산이 어려운 수로 보기에 충분합니다.
 

// 가독성을 위해 줄바꿈을 시행하였습니다.
p = 2563498771487337883760923236
51653778850951735325988433950193
17514231629751122866556311015474
56520516892741686362097229245056
58182408737146935042320063086160
93102079996295643404492052697942
28188630270202780169375871963966
47247656019579539786390333149201
07655499032370765549128572151127
05650254526416741394475812709174
96327454682310135809427945111001

 
 
한 눈에 봐도 연산하기 굉장히 어려울만큼 충분히 큰 수인 것처럼 보이네요.
 
물론 이런 디피-헬먼 키 교환 방식에도 약점은 있습니다. 송수신자 사이에서 비밀 정보를 교환할 수는 있지만, 직접 주고받는게 아닌 중간에서 "송신자와 중간자", "중간자와 수신자" 두 개의 연결을 만들어 마치 둘 사이에만 통신을 하는 것처럼 위장하는 중간자 공격이 가능하여 실제 상대방과 통신중이라는 것을 보장할 수 없다는 문제가 있습니다.
 

디피-헬먼 키 교환 방식 외에도 키 배포 센터의 문제를 해결하기 위해 등장한 또 다른 알고리즘이 있는데, 그 중 하나가 바로 오늘의 주제 RSA 입니다.
 
 

RSA

RSA 암호는 암호화 키와 복호화 키가 동일한 대칭 암호와 달리, 암호화 키와 복호화 키가 다른 비대칭 암호이자 공개 키 암호입니다. 로널드 라이베스트(Ronald L. Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman) 세 명의 컴퓨터 과학자가 체계화시킨 방법으로 이들의 이름 앞글자를 따서 RSA 암호로 불리게 되었습니다.
 
공개키 암호는 암호화 키를 가진 누구나 암호화가 가능하며, 암호화에 사용되는 키는 공개되어 있습니다. 송신자는 공개된 암호화 키를 이용해 정보를 암호화하여 수신자에게 전송하고, 수신자는 공개되지 않은 복호화 키를 통해 해당 정보를 복호화합니다. 여기서 암호화 키를 공개 키(Public key), 복호화 키를 개인키(Private key)라고 부릅니다.
 
이렇기 때문에 공개키와 개인키는 밀접한 연관이 있으며, 각각 따로 생성하거나 사용할 수 없습니다. 하나의 공개키에는 하나의 개인키가 짝으로서 존재하기 때문에 한 쪽만 변경 할 수 없다는 의미입니다.
 
RSA의 암호화와 복호화는 수식으로 간단히 표현됩니다. 
 

암호문 = (평문)^E mod N
평문 = (암호문)^D mod N

 
첫 번째 수식을 RSA의 암호화 과정, 두 번째 수식을 RSA의 복호화 과정이라고 표현합니다. 따라서 (E, N) 을 공개키, (D, N) 을 개인 키라고 말 할 수 있겠습니다. 위에서 언급한 것처럼, ( E, D, N ) 세 가지 키 모두 면밀한 계산을 통해 생성되며 그 중 E와 D는 밀접하게 연결되어 있습니다.
 
그럼 이제부터 RSA를 어떻게 적용할 수 있는지 살펴보겠습니다.
 
 

RSA가 일어나는 과정

 
 

키 생성

암/복호화를 적용하기 위해서는 먼저 키 쌍을 생성해야합니다. 가장 먼저 할 일은 N을 구하는 과정입니다.
 
1. N 구하기
먼저 충분히 큰 소수 p와 q를 준비합니다.
N은 이 p와 q의 곱으로 나타낼 수 있습니다.

N = p * q

 
 
2. L 구하기
L이 갑자기 튀어나와서 놀라셨을텐데, 실제 암호화나 복호화 과정에서 사용되는 값은 아니고 키 쌍을 만들때만 임시로 사용하는 값입니다.
L은 p-1와 q-1의 최소공배수 연산을 통해 구할 수 있습니다.

L = lcm(p - 1, q - 1)

 
 
3. E 구하기
다음은 공개 키에 사용되는 E를 구하는 방법입니다.
E의 경우 아래 두 조건을 동시에 만족하는 숫자 중 하나를 골라줍니다.

1 < E < L 를 만족하면서,
gcd(E, L) = 1 (즉, E와 L은 서로소 관계)

 
 
4. D 구하기
마지막으로 개인 키에 사용될 D를 구하는 방법입니다.
E와 마찬가지로 아래 두 조건을 동시에 만족하는 숫자 D를 구해주면 됩니다.

1 < D < L 를 만족하면서,
E * D mod L = 1

 
 
이렇게 생성된 키 쌍을 통해 암호화를 진행하면, 개인 키를 알고있지 않은 이상 현재의 기술력으론 해독하는 것이 현실적으로 불가능합니다. 우리가 위의 디피-헬먼 방법에서 보았듯이 키 쌍 생성 과정에서 충분히 큰 수를 이용하게 되면 역으로 계산하여 D 값을 알아내는 것이 무척이나 복잡하고 어려운 계산이 되어 사실상 원형을 알 수 없게 된다는 의미입니다.
 
위에서 적었던 평문을 만드는 수식을 다시 한 번 보겠습니다.

평문 = (암호문)^D mod N

공격자의 입장에서 알고있는 정보는 암호문과 공개키를 통해 얻어내는 N입니다. 그러나 이러한 상황에서 지수에 들어가는 D 값을 찾는건 아무리 좋은 컴퓨팅 파워를 갖고 있다고 해도 어려운 일입니다. 이를 이산 대수 문제(Discrete Logarithm Problem)라고 하며, 직접적인 방법으로 찾아내는건 거의 불가능하다는 것을 알 수 있습니다.
 
공개키를 통해 N 값을 알고 있으니, 역연산을 통해 p와 q를 구하고 이를 통해 D 값을 구할 수도 있을거라고 생각할수도 있지만, 이 또한 소인수분해의 난해함으로 인해 거의 불가능합니다. 두 수의 값을 알때 그 곱을 구하는 것은 몇 번의 반복적인 작업을 통해 가능하지만, 한 번 합쳐진 상태에서 다시 두 수로 쪼개는건 정말 어려운 작업입니다. 하물며 위에서 찾아봤던 "충분히 큰" 두 소수의 합이라면 역시 현재의 연산력으로는 불가능합니다.
 
아직까지는 소인수분해를 빠르게 할 수 있는 방법이 발견되지 않아 RSA는 안전하다고 할 수 있는데, 반대로 말하면 이러한 방법이 발견되면 RSA는 보안성을 잃게 된다는 의미와도 같습니다. 이후에 일반 컴퓨터보다 훨씬 큰 연산력을 가진 양자 컴퓨터가 발달한다면 소인수분해를 비교적 쉽게 해결할 수 있는 쇼어 알고리즘(Shor Algorithm)을 이용해 RSA 암호가 뚫리는 날이 올 수도 있습니다.
 
쇼어 알고리즘을 간단히 살펴보면, 양자 컴퓨터의 병렬 연산을 이용해 N을 소인수분해 할 때 필요한 주기 r을 찾습니다. 이렇게 찾은 r이 홀수라면 다른 주기를 찾고, 짝수라면 최대공약수 연산을 통해 소인수를 찾습니다. 이렇게 찾은 소인수와 서로소가 되는 값을 찾고, 만약 서로소가 되지 않는다면 주기를 찾는 과정을 반복합니다...
 
이런 방법으로 소인수분해를 수행하면 다항식의 시간 복잡도를 갖게 됩니다. 지수 함수의 시간 복잡도를 갖는 기존의 방법에 비해 훨씬 빠른 방법이라고 할 수 있겠으나, 아직까진 그만한 양자 컴퓨팅 파워를 사용할 수 없기 때문에 RSA는 현실적으로는 안전하다고 볼 수 있겠습니다.
 
 
 
 

마치며 

오늘은 대칭키 암호의 문제를 해결할 수 있는 비대칭키 암호 시스템인 RSA의 등장 배경과, 그 동작 방식에 대해서 알아보았습니다. 이전에 살펴본 DES와 달리, 이 글을 쓰는 현재에도 주력으로 사용되는 알고리즘인 만큼 복잡하면서도 재밌는 내용이었네요. 과연 언제쯤 양자 컴퓨터가 충분히 개발되고 상용화되어 RSA가 뚫리게 되는 날이 올지 궁금해집니다.
 
틀린 내용에 대한 지적은 댓글로 부탁드립니다.
읽어주셔서 감사합니다.



* 잘못된 내용을 지적해주신 문지연님께 감사드립니다.