초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
로그인 요청의 비밀번호도, 쿠키의 번호표도 글자 그대로 여러 라우터를 거쳐 갑니다. 그중 한 곳만 들여다봐도 다 보입니다. 받는 쪽만 읽을 수 있게 메시지를 뒤섞어 보내 봅시다.
메시지를 정해진 규칙으로 뒤섞어 알아볼 수 없게 만드는 것을 암호화(encryption), 원래대로 되돌리는 것을 복호화(decryption)라 합니다. 뒤섞는 방법을 정하는 비밀 값은 키(key)입니다.
알파벳을 키만큼 뒤로 미는 방법이 있습니다. 키가 3이면 HELLO는 KHOOR가 되고,
받는 쪽은 3만큼 당겨 되찾습니다. 이처럼 잠글 때와 열 때 같은 키를 쓰는 방식을
대칭 키(symmetric key) 암호라 합니다. 실제 대칭 키 암호는 훨씬 복잡하게
뒤섞어 키 없이는 사실상 풀 수 없고, 계산도 빠릅니다.
문제는 키를 나누는 일입니다. 처음 접속한 쇼핑몰에 키를 보내면 키도 같은 라우터를 지나가니, 엿본 사람도 키를 갖게 됩니다.
열쇠 대신 자물쇠를 나눠 주면 어떨까요? 서버가 열린 자물쇠를 누구에게나 주고 열쇠는 혼자 가집니다. 브라우저는 비밀을 상자에 넣고 자물쇠를 철컥 잠가 보냅니다. 중간에서 다 봐도 열쇠가 없으니 열 수 없습니다.
잠그는 키와 여는 키를 따로 두는 이 방식을 공개 키 암호(public-key cryptography)라 합니다. 누구에게나 주는 자물쇠가 공개 키(public key), 주인만 가진 열쇠가 개인 키(private key)입니다. 한 방향으로는 계산하기 쉽고 거꾸로는 어려운 계산이 있으면 이런 자물쇠를 만들 수 있습니다. 대표적인 것이 RSA입니다. 이름은 만든 세 사람(Rivest, Shamir, Adleman)의 첫 글자입니다.
RSA는 소수와 나머지 연산으로 키를 만듭니다.
n과 e가 공개 키, d가 개인 키입니다. 메시지를 n보다 작은 수 m으로 바꿔 두면 잠그고 여는 것은 거듭제곱 한 번씩입니다.
c = m^e mod nm = c^d mod ne와 d를 이렇게 고르면 열었을 때 언제나 m이 돌아옵니다. 증명은 넘어가고 직접 계산해 봅시다.
n을 p와 q로 쪼개면 (p − 1)(q − 1)을 계산해 개인 키 d도 구할 수 있습니다. 그래서 RSA의 안전은 n을 쪼개기 어렵다는 데 달려 있습니다. p와 q를 곱하기는 쉽지만 n만 보고 p와 q를 찾기는 어렵습니다. 실제로 쓰는 n은 십진수로 600자리가 넘어, 알려진 방법으로는 오늘날의 컴퓨터로도 감당할 수 없을 만큼 오래 걸립니다. 대신 그만큼 큰 수를 거듭제곱해야 해서, 빠른 거듭제곱을 써도 공개 키 암호는 대칭 키 암호보다 훨씬 느립니다.
공개 키가 n = 187, e = 3입니다. 엿보는 사람이 잠긴 값 c = 125를 봤습니다. 원래 메시지 m(0 이상 187 미만)은 얼마일까요? 숫자로 답하세요.