곱하기는 쉽고 나누기는 어렵다
곱하기는 쉽지만 되돌리기는 어렵습니다
두 소수 37과 73을 종이에 곱해 보세요. 2701이라는 답을 1분이면 쉽게 찾아낼 수 있습니다.
이제 친구에게 2701만 보여주고 원래 어떤 두 소수를 곱했는지 찾아보라고 해 보세요. 왜 거꾸로 되돌리는 길은 까마득히 멀어질까요?
이야기
Ronald L. Rivest
CC BY-SA 4.0 · 위키미디어 공용
1977년 4월, MIT. 유월절 저녁 모임에서 돌아온 론 리베스트가 두통에 시달리며 소파에 누워 있다가 이 방법을 떠올렸습니다. 그날 밤 안에 초안을 다 썼다고 합니다. 아디 샤미르, 레너드 애들먼과 함께 낸 이 방법의 이름이 세 사람 성의 첫 글자를 딴 RSA입니다.
그런데 정작 이것을 먼저 찾은 사람은 따로 있었습니다. 영국 정보기관의 클리퍼드 콕스가 1973년에 사실상 같은 것을 만들어 놓았습니다. 다만 기밀로 묶여 있어 1997년에야 공개되었습니다. 이십사 년 동안 아무도 몰랐던 것입니다.
왜 한쪽으로만 쉬울까요. 두 수를 곱하는 데 드는 품은 자릿수에 비례해서 늘어납니다. 백 자리 곱셈은 열 자리 곱셈보다 백 배쯤 오래 걸릴 뿐입니다.
그런데 되돌리는 데 드는 품은 자릿수가 늘 때마다 곱절로 뜁니다. 자릿수를 두 배로 하면 시간이 두 배가 아니라 어마어마하게 커집니다. 이 차이가 벌어지는 속도가 다르기 때문에 어느 지점부터는 사람이 만들기는 쉽고 남이 풀기는 불가능해집니다.
🚩 그러니 이 암호는 「풀 수 없다」가 아니라 「푸는 데 너무 오래 걸린다」에 기대고 있습니다. 더 빠른 방법이 나오면 무너집니다.
지금 여러분이 보는 이 화면이 안전한 까닭입니다. 주소창의 자물쇠, 은행 앱, 메시지 앱이 모두 「곱하기는 쉽고 되돌리기는 어렵다」에 기대고 있습니다.
큰 수를 소인수분해하는 빠른 방법이 발견되면 그날로 인터넷 암호가 무너집니다.
계단 넷 — 같은 사실을 네 깊이로
두 소수를 곱하고 친구에게 되돌려 보라 하기
두 자리 소수 둘을 골라 곱셈표로 곱해 봅니다. 17과 19를 곱하면 323이라는 숫자가 금방 계산됩니다.
하지만 반대로 323만 주고 어떤 수 둘을 곱했는지 찾으려면 2부터 3, 5, 7, 11, 13, 17까지 하나하나 나누어 보아야 합니다. 가는 길은 빠르지만 돌아오는 길은 엄청나게 힘든 비밀이 여기에 숨어 있습니다.
곱하기는 쉽고 나누기는 어렵습니다
이 비대칭 하나에 오늘의 모든 은행이 걸려 있습니다.
소인수분해의 어려움
숫자가 몇백 자리로 커지면 현대의 슈퍼컴퓨터로도 소인수분해를 마치는 데 수만 년이 걸립니다. 이를 단방향 함수라고 부릅니다.
인터넷 뱅킹과 비밀번호 암호화는 모두 이 성질을 이용합니다. 비밀 열쇠를 가진 사람만 쉽게 문을 열고 들어갈 수 있고, 열쇠가 없는 공격자는 모든 경우를 일일이 대입하다 포기하게 만듭니다.
열쇠 두 개를 만들어 보세요
d 가 나오지 않으면 e 와 φ 가 서로소가 아닌 것입니다 — e 를 바꿔 보세요.
모듈러 거듭제곱
RSA 암호는 오일러의 정리 에 기초합니다. 두 큰 소수 의 곱 에 대해 입니다.
공개키 로 메시지 을 으로 암호화하면, 비밀키 를 아는 사람만이 으로 복호화할 수 있습니다.
암호로 만들고 다시 풀어 보세요
오일러 정리 m^φ(N) ≡ 1 때문입니다 — 나머지 셈이 열쇠를 만듭니다.
RSA
RSA의 안전성은 소인수분해 문제(Integer Factorization)의 계산 복잡도에 의존합니다. 고전 컴퓨터 알고리즘으로는 일반 수체 체(GNFS)가 준지수 시간에 머뭅니다.
그러나 양자컴퓨터에서는 쇼어 알고리즘(Shor's algorithm)에 의해 다항 시간 내에 소인수분해가 가능하므로, 오늘날 암호학은 격자 기반의 양자내성 암호(PQC)로 확장되고 있습니다.
얼마나 안전한가
그러나 쇼어 알고리즘을 쓰면 양자컴퓨터가 몇 시간에 풉니다.
풀어 보기
두 소수의 곱과 암호 원리. 두 소수 을 택하여 RSA 암호 체계를 구성하려 한다.
(1) 와 오일러 파이 함수 값 을 각각 구하시오.
(2) 공개키를 이라 할 때, 을 만족하는 최소의 양의 정수 비밀키 를 구하시오.
(3) 평문 를 암호화한 암호문 의 값을 구하시오.
(2) 에서 이므로 입니다.
답과 풀이 보기
(1) ,
(2) 을 만족하는 가장 작은 양의 정수를 찾습니다.
이므로 입니다.
(3) 이므로 입니다.
되돌려 보면 — 평문이 그대로 돌아옵니다. 이것이 RSA 가 도는 까닭입니다.
더 멀리
「쉬운 방향과 어려운 방향이 다르다」는 것이 암호의 뿌리입니다.
- 인터넷 결제·은행 — 자물쇠 모양이 뜨는 그 순간에 쓰입니다
- 전자 서명 — 내가 보낸 것이 맞다는 증명에도 같은 원리가 쓰입니다
- 양자 컴퓨터 — 만약 아주 빨리 소인수분해를 할 수 있게 되면 이 암호는 바뀌어야 합니다. 지금 그 준비가 진행 중입니다
이어지는 장
곱셈을 거꾸로 되돌리기 어려운 성질을 실제 작동하는 암호로 바꾸는 수학적 열쇠는 300년 전 페르마가 발견한 소수의 성질입니다 — 제134장에서 암호 해독의 심장을 들여다보세요.
영감을 받은 곳
론 리베스트, 아디 샤미르, 레너드 에이들먼이 1977년 MIT에서 고안하고 1978년 발표한 논문 「디지털 서명과 공개키 암호 시스템을 위한 방법」에서 제안되었습니다.