많은사람들이 알겠지만 섬머워즈에서 켄지가 열심히 풀어댔던 암호는 RSA암호라는 겁니다.

RSA암호란 리베스트(Rivest), 샤미어(Shamir), 아델만(Adelman)인데 사람 이름들입니다.

이것이 섬머워즈에 나왔던 OZ보안암호이지요.

그럼 RSA가 뭔지부터 알아보죠

RSA암호란 소수 2개를 가지고 만드는 암호입니다.

원래 암호를 풀기위해선 열쇠가 필요합니다.

암호화 열쇠랑 복호열쇠이죠. RSA암호 전의 암호는 거의다 암호화열쇠와 복호열쇠가 같았습니다.(방법은 좀 다를지라도)

단순치환 사이퍼, 비즈네르 암호, 애그니마까지 암호화열쇠만 있으면 복호열쇠도 가지고 있는것이나 마찬가지였습니다.

하지만 이는 아주 불편한 점이 있죠.

무엇이냐면 암호화열쇠를 다른 타인이 가지게 된다면 타인이 그 암호를 가로채서 해독 할 수 있다는것과 받는 사람에게 사전에 암호화열쇠를 넘겨주어야 받는 사람이 그 암호를 해독할수 있다는 것이지요.

이런 방식은 암호의 보안성을 깰 요소가 매우 많아집니다.

그렇기 때문에 새로운 암호화방법이 필요했습니다.

그래서 탄생한것이 RSA암호입니다.

RSA암호는 현재로도 매우 보안성 높은 암호로 현재 인터넷에서도 쓰이고 있습니다.

두 소수를 이용해 암호화하는 방법으로 이는 소수의 곱을 인수분해를 하기 어렵다는점을 이용한 것입니다.

두 소수의 곱을 공개해서 그것으로 암호화 하게 합니다.

그리고 암호를 푸는 복호열쇠는 비밀로 해둡니다. 복호열쇠는 두 소수입니다.

공개열쇠로 암호를 해독하기 위해선 인수분해를 해 두소수를 알아내야만 하는데 이는 매우 어렵습니다.

예를 들어 6같은 경우 2와 3으로 쉽게 인수분해 되지만 437같은 경우는 인수분해 할경우 좀 생각을 해봐야 합니다.

자릿수가 더 늘어나면 컴퓨터로도 힘들어지죠.

켄지가 풀었던 문장을 좀 보죠.

the magic words are squeamish ossifrage.(후략)

마법의 주문들은 까다로운 수염수리이다.

이 문장은 RSA-129입니다.

RSA가 처음 나왔을때 암호의 안정성이 궁금해지자 사람들에게 풀어보라고 내놓은 문제입니다.

129자리의 숫자를 2개의 소수로 분리해내야 하죠.

114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541

이것을 2개의 소수로 분리한다음 해독해야 하는것이지요

참고로 두 소수는

3490529510847650949147849619903898133417764638493387843990820577

32769132993266709549961988190834461413177642967992942539798288533

입니다.

자 그럼 해독하는 법을 배워 볼까요?

(먼저 해독하는 법먼저 적고 암호화하는 법은 나중에 적겠습니다.)

M=C^d mod n

입니다.

여기서 M은 평문(암호가 풀린 것)이고 C는 암호문 d는 e를곱해 두 소수에서 각각 1을 뺀수의 최소 공배수로 나누면 1이 되는 수입니다.

여기서 e는 원래 공개되어 있는 숫자입니다.(자연로그할때 e가 아닙니다)

그리고 n도 공개되어 있는 숫자 입니다. 위에서 말한 129자리 숫자가 n입니다.

쉽게 예를 들어보죠.

암호문C가 141이고

공개열쇠 n=437, e=119라고 합시다.

먼저 n을 인수분해 해야 됩니다.

인수분해 하면 19와 23 두 소수가 나오게 됩니다.

이제 d를 구해야 합니다. e를 곱해서 (19-1)과 (23-1)의 최소공배수로 나누면 나머지가 1이되는 수를 구해야 되는 거죠.

18과 22의 최소공배수는 198입니다. d*119=198*k+1 (k는 자연수) 이 되는 숫자이죠.

구하게 되면 d는 5가 나옵니다. 5*119=198*3+1 이니까요. (595=594+1)

이제 암호를 풀면 됩니다. 141을 5제곱해서 437로 나눈 나머지가 평문M이 되는 것입니다.

답은 335이죠.

여기서 나오는 숫자들은 아스키코드를 써서 변환하면 글자들이 나오는 것이죠.(아스키 코드는 쉽습니다. 그냥 단순치환 사이퍼같은 겁니다.)

이런 식으로 푸는 암호입니다.

암호화 하는 방법은 이것을 반대로 하면 되는겁니다.

식은

C=M^e mod n이죠.

M을 e제곱하고 n으로 나눈 나머지 입니다.

현재 인터넷은 약 300자리의 숫자를 공개열쇠로 하고 있습니다.

이를 현재 컴퓨터로 풀려면 몇만년동안 풀어도 못푸는 정도이지요.

참고로 RSA말고 보안성 높은 몇몇 암호들이 있습니다. 소인수분해같이 "반대쪽으로 가기 힘든"함수들을 이용한건데요