암호 공부하자 - 05 RSA 암호화

key word : 암호, Crypto, Cryptography, RSA 암호화, 공개키 암호화 알고리즘

"SSL/TLS에 가장 많이 사용되는 암호화 기법"

드디어 '암호 공부하자!'의 꽃이라 불릴 수 있는 주제에 왔습니다. 

전 세계의 대부분의 인터넷 뱅킹, 인터넷 시스템들이 RSA-2048 암호화를 사용합니다. 

즉 이번 글을 통해서 여러분의 개인정보가, 은행 계좌가 어떻게 보호되고 있는지 단편적으로나마 알 수 있다는 말이죠.

"암호 공부하자! - 01 Prologue"에서 공개키 암호에 대해서 짧게 다뤘었습니다. 

그 때는 '비대칭형 키'라는 말을 썼었는데요. 기억나시나요? 

서로 다른 공개키와 비밀키가 한 쌍을 이루며, 공개키로 암호화 한 내용은 쌍을 이루는 비밀키로만 복호화가 가능하다고 말했었습니다. 

공개키 암호화 알고리즘, 비대칭형 키 알고리즘의 대표적인 예인 RSA는 매우 큰 수의 소인수분해가 힘들다는 점을 이용한 것입니다. 

그렇다면 암호를 만드는 과정이 어떠한지, 복호화 과정이 어떠한지 원리와 함께 공부를 해 봅시다. 

1. 키, 암호화, 복호화 과정

RSA 방식으로 암호화를 하기 위해 먼저 키를 만들어야 합니다. 

1. 두 소수 p, q를 준비한다.  2. p-1, q-1과 각각 서로소인 정수 e를 준비한다.  3. ed를 (p-1)(q-1)으로 나눈 나머지가 1이 되도록 하는 d를 찾는다.  4. N = pq를 계산한 후, N과 e를 공개하고 d는 숨겨둔다. (공개키 : N, e, 비밀키 : d) 5. p, q (p-1), (q-1)은 파기한다.

위 방법으로 만들어진 공개키(N, e)와 비밀키(N, d)로 암호화와 복호화를 진행합니다. 

먼저 공개키로 RSA 방식으로 암호화를 하는 과정은 다음과 같습니다. 

보내려는 평서문 a를  으로 암호화 합니다. (단 a<N을 만족해야 합니다.)

다음으로 RSA 방식으로 복호화를 하는 과정은 다음과 같습니다. 

받은 암호문x를  으로 복호화 합니다.

갑자기 수식이 튀어나와서 놀라셨을 것 같은데요^^

어떻게 문자를 수식으로 암호화를 시킬 수 있는지, mod라는 건 어떤 물건인지에 대해 궁금해 하실 것 같아서 짧게나마 설명해드리겠습니다. 

컴퓨터가 0과 1로만 정보를 표현하다는 것은 잘 알고계실 겁니다. 

즉 지금 보고 있는 글자들도 컴퓨터에게는 단지 0과 1로 이루어진 데이터일 뿐이죠. 

"0100011101001010..." 0과 1로 이어진 하나의 데이터, 하나의 수열, 

위 수식에 대입이 가능할 것 같지 않나요? 

다음으로 mod연산에 대해 이야기 해보도록 합시다. 

mod연산은 나머지를 계산하고 싶을 때 사용하는 연산, 함수입니다. 

예를 들어서 7을 3으로 나눈 나머지를 알고 싶다!

7mod3 = 1 처럼 쓰게 되는 것이죠. 

아무래도 나머지를 계산하는 특이한 연산이다 보니 독특한 성질도 가지고 있습니다. 

위 두 가지 성질을 잘 이용한다면 큰 수의 계산도 빠르게 할 수 있게 되는데요. 

x의 23승을 N으로 나눈 나머지를 계산해 봅시다.

여기에서 이라고 한다면 위 식은 다음과 같이 정리됩니다. 

프로그래밍을 조금 공부하셨다면 눈치 채셨을 수도 있겠지만 수식에서 패턴, 반복이 들어가게 되면 이를 구현하는 것이 매우 편해집니다. 

즉 RSA는 프로그램으로 구현하기에도 효율적인 방법이라는것이죠. 

2. 암호화결과, 복호화결과

암호화가 정확한지를 알아보기 위해서는 평문 a와 이를 암호화한 a를 복호화시킨 결과가 같아야 되겠죠? 

우리가 알고 있는 식은 다음과 같습니다. 

페르마의 소정리

4번 식의 경우에는 페르마의 소정리로 이런 성질이 있다는 것만 알아두셔도 될 것 같습니다. 

은 오일러phi 함수로, 1부터 N까지 수들 중 N과 서로소인 수들의 개수입니다. 

그렇다면 이제 암호문 a'를 복호화 시켜보도록 할까요. 

암호문을 복호화 한 내용이 평문과 일치하네요. 

이상으로 RSA암호화의 자세한 내용을 공부해 보았습니다. 

소수를 사용하여 계산하고, 키를 만드는 과정에서 매우 큰 수가 등장하기 때문에 외부인이 이 암호를 뚫기 위해서는 아주 큰 수의 소인수 분해에 성공해야 되는데요. 

실제로 RSA-1024, RSA-2048과 같은 암호체계에서 사용하는 수는 소인수분해를 성공하는 것에 상금이 걸려있습니다. 

여러분도 한 번 도전해 보시거나, 새로운 암호체계를 생각해보시길 바라면서 이만 글을 마치겠습니다.