정수론(Number theory)

RSA 암호(RSA cryptosystem)

누구나 잠글 수 있지만 두 소수⁠(prime number)⁠를 아는 사람만 열 수 있는 자물쇠. 오일러 정리⁠(Euler's theorem)⁠로 m^(ed) ≡ m이 되게 지수 e, d를 고른다.

c \equiv m^{e} \pmod n, \qquad m \equiv c^{d} \pmod n, \qquad ed \equiv 1 \pmod{\varphi(n)}

먼저 보면 좋은 개념오일러 피 함수와 페르마 소정리

두 소수 $p =$ , $q =$ 를 몰래 고르고, 곱 $n = pq$ 와 지수 $e =$ 를 세상에 공개합니다. 누구든 메시지 $m =$ 를 $c = m^e \bmod n$ ( $m^e$ 을 $n$ 으로 나눈 나머지⁠(remainder)⁠)으로 잠글 수 있습니다. 1977년 MIT의 로널드 리베스트, 아디 샤미르, 레너드 애들먼이 발표해 세 사람 성의 머리글자를 딴 이름입니다.

원 위의 n개 점에서 m → mᵉ mod n을 모두 이은 그림입니다. 노란 화살표가 지금의 m, 초록 점선이 복호화입니다.

$e$ 가 $\varphi(n)$ 과 서로소⁠(coprime)⁠이면 잠그기는 $0, 1, \dots, n-1$ 을 서로 겹치지 않게 자리만 바꾸는 순열⁠(permutation)⁠입니다. 되돌리는 열쇠가 $d$ 입니다. $ed = 1 + k\,\varphi(n)$ 이고 $m$ 이 $n$ 과 서로소이면, 오일러 정리 $m^{\varphi(n)} \equiv 1$ 덕분에 $(m^e)^d = m \cdot (m^{\varphi(n)})^k \equiv m$ 입니다. $m$ 이 $p$ 나 $q$ 의 배수여도 $p$ , $q$ 로 나눈 나머지를 따로 보면 같은 결론이 나옵니다(중국인의 나머지 정리⁠, Chinese remainder theorem⁠). $d$ 는 $\varphi(n)$ 을 법으로 한 $e$ 의 모듈러 역수⁠(inverse)⁠이고, 확장 유클리드 호제법⁠(Euclidean algorithm)⁠으로 순식간에 구합니다. $e$ 가 $\varphi(n)$ 과 서로소가 아니면 역수가 없고, 그림에서 여러 점이 한 점으로 몰려(회색 점) 순열이 깨집니다.

그런데 $d$ 를 구하는 자연스러운 길은 $\varphi(n) = (p-1)(q-1)$ 을 아는 것이고, $n$ 과 $\varphi(n)$ 을 알면 $p + q = n - \varphi(n) + 1$ 에서 $p, q$ 가 곧바로 나옵니다. 공개된 것은 $n$ 과 $e$ 뿐입니다. 이것만으로 $d$ 를 알아내는 일은 $n$ 을 소인수분해⁠(prime factorization)⁠하는 일만큼 어렵다는 것이 증명되어 있습니다. 다만 $d$ 없이 암호문⁠(ciphertext)⁠을 푸는 다른 지름길이 없다는 증명은 아직 없습니다. 수백 자리 수의 소인수분해는 지금 알려진 어떤 방법으로도 보통 컴퓨터에서 현실적인 시간 안에 끝나지 않습니다(충분히 큰 양자컴퓨터가 생기면 쇼어 알고리즘⁠(algorithm)⁠으로 빨리 풀립니다). 곱하기는 쉽고 되돌리기는 어렵다는 이 비대칭이 자물쇠입니다.

같은 자물쇠를 거꾸로 쓰면 전자서명⁠(digital signature)⁠이 됩니다. 보내는 사람이 메시지를 비밀 열쇠 $d$ 로 잠가 붙이면, 누구나 공개된 $e$ 로 풀어 보아 그 사람이 보냈음을 확인할 수 있습니다. 실제로는 긴 메시지를 해시 함수⁠(hash function)⁠로 짧은 고정 길이의 수로 줄인 뒤 그 수를 잠급니다. 서로 다른 메시지의 해시⁠(hash)⁠가 우연히 같아질 확률⁠(probability)⁠은 생일 문제⁠(birthday problem)⁠가 알려 줍니다.

만난 적 없는 두 사람이 공개된 통신망에서 비밀 열쇠를 맞추는 또 다른 방법은 디피–헬먼 키 교환⁠(Diffie–Hellman key exchange)⁠입니다.

큰 수를 소인수분해하기는 어렵지만, 큰 수가 소수인지 가리기는 쉽습니다(소수 판정⁠, primality test⁠). RSA는 이 두 일의 난이도 차이에 기대고 있습니다.

소인수분해가 정말로 어려운지는 아무도 증명하지 못했습니다. 두 소수를 받으면 곱해 보아 답인지 곧바로 확인할 수 있지만, 그 답을 찾기는 어려워 보입니다. 이처럼 답을 빨리 확인할 수 있는 문제가 모두 빨리 풀 수도 있는 문제인지 묻는 것이 P 대 NP 문제⁠(P versus NP problem)⁠입니다. 다만 P ≠ NP가 증명되더라도 소인수분해가 어렵다는 결론은 곧바로 나오지 않습니다. 소인수분해는 NP에서 가장 어려운 문제로 여겨지지 않기 때문입니다.

관련된 시대와 장소20세기 초 케임브리지 벨 연구소 블레츨리 파크

이 개념이 나오는 큰 생각무작위성

이 개념이 나오는 긴 글

소수 소수를 세는 사람들 소수는 제멋대로 흩어져 있는 것 같다. 그런데 멀리서 세어 보면 로그가 보인다. 정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 그래프 이론 일곱 다리의 도시 쾨니히스베르크의 일곱 다리를 한 번씩만 건너 산책할 수 있을까? 오일러는 지도를 지우고 점과 선만 남겼다. 계산 이론 기계가 풀 수 없는 문제 모든 수학 문제를 기계적으로 풀 수 있을까? 러셀의 역설에서 괴델과 튜링까지, 그 질문에 대한 답은 '아니오'였고, 그 증명이 컴퓨터를 낳았다.

이 개념을 언급하는 페이지

생일 문제
… 정해진 길이(예: 256비트)의 짧은 값으로 바꾸는 함수로, 문서의 '지문'처럼 쓰입니다. 전자 서명(RSA서명 등)은 문서 대신 이 지문에 서명하므로, 해시값이 같은 두 문서를 찾아내면 한 문서에 받은 서명을 …
단사·전사·전단사
… 서로소일 때만 곱셈을 되돌리는 "나눗셈", 곧 곱해서 1이 되는 수(역원)가 존재합니다. 이것이RSA 암호같은 암호의 바탕입니다. 선형대수에서도 똑같습니다. 행렬이 나타내는 변환이 전단사이려면 행렬이 …
소수와 에라토스테네스의 체
… 넣으면 바젤 문제와 이어집니다. 큰 두 소수를 곱하기는 쉽지만 그 곱을 거꾸로 쪼개기는 어렵다는 사실이RSA 암호의 바탕입니다. 차이가 2인 소수 쌍, 곧 쌍둥이 소수가 끝없이 있는지는 아직 아무도 모릅니다. 반면 …
최대공약수와 유클리드 호제법
… 5배를 넘지 않습니다(1844년 프랑스의 가브리엘 라메가 증명). 그래서 수백 자리 수에도 쓸 수 있고,RSA의 열쇠 계산에 쓰입니다. 각 단계의 정사각형 개수를 적어 두면 a/b 의 연분수가 됩니다. 마지막 …
모듈러 연산
… 증명도 없습니다). 이 비대칭이 디피–헬먼 키 교환과, 잠그는 열쇠는 공개하고 여는 열쇠만 숨기는공개키 암호의 바탕입니다. 18세기 프로이센의 도시 쾨니히스베르크에서는 일곱 다리를 한 번씩만 건너 산책할 수 …
오일러 피 함수와 페르마 소정리
… 의 공식은 소인수분해한 뒤 각 소인수의 배수를 포함배제 원리로 빼면 나옵니다. 이 정리 하나 위에RSA 암호가 서 있습니다.
중국인의 나머지 정리
… 를 만족하고, 15에 원시근이 없는 이유도 같은 쪼개기에서 나옵니다.RSA 암호는 복호화(잠긴 메시지 풀기)를 p 와 q 로 따로 한 뒤 이 정리로 합쳐 3~4배가량 빠르게 합니다. …
디피–헬먼 키 교환
… 이 방법은 열쇠를 미리 나누지 않고 공개된 정보만으로 암호를 쓰는 공개키 암호의 문을 열었고, 이듬해RSA 암호가 뒤따랐습니다. 가로축은 k, 세로축은 결과입니다. 노란 점(앨리스의 a)과 초록 점(밥의 b)을 가로로 …
소수 판정
… 두 인수 중 하나는 \sqrt n 이하이니 \sqrt n 까지의 소수로만 나눠 보면 됩니다. 하지만RSA에 쓰는 300자리 수라면 \sqrt n 이 150자리입니다. 150자리 이하의 소수만 해도 약 3 …
해밍 거리
… 망가진 부분에 강하고, CD는 여기에 자료의 순서를 흩어 기록하는 방법까지 더해 긁힌 자국을 견딥니다.RSA같은 암호가 엿듣는 사람을 막는다면, 오류 정정 부호는 잡음을 막습니다. 둘 다 보내는 내용을 약속된 …
처치–튜링 논제
… 1994년에 내놓은 알고리즘을 쓰면, 충분히 큰 양자 컴퓨터는 소인수분해를 다항식 걸음에 해낼 수 있어RSA를 위협합니다. 보통 컴퓨터로는 소인수분해의 다항 시간 방법이 알려져 있지 않습니다. 그런 방법이 정말 …
P 대 NP 문제
… 나눠 보면 되기 때문입니다. 그러나 NP 완전인지는 모르고, 다항 시간 방법이 알려져 있지 않다는 사실에RSA암호가 기대고 있습니다. 디피–헬먼 키 교환이 기대는 이산 로그 문제, 곧 g^x \equiv h …
무작위 알고리즘
… 확률은 1/4 이하입니다. 그러니 번 독립으로 검사하면 합성수를 소수라고 잘못 말할 확률은 이하입니다.RSA에 쓸 수백 자리 소수를 이렇게 찾습니다. '몬테카를로'라는 이름은 넓이를 무작위 점으로 어림하는 …
군
… p − 1의 약수이고, a^{p-1} 은 a^k = 1 을 (p − 1)/k번 곱한 것이어서 1입니다.RSA 암호는 이 정리를 두 소수의 곱으로 넓힌 오일러의 정리 위에서 작동합니다. 군이라는 생각은 방정식에서 …
정수론
… 못할 것 같다고 적었습니다. 그 예상은 빗나갔습니다. 1976년의 디피–헬먼 키 교환과 1977년의RSA는 큰 수의 거듭제곱을 어떤 수로 나눈 나머지는 빨리 계산되고 소수 판정도 빠르지만, 큰 수를 …

이 페이지가 가리키는 개념

소수와 에라토스테네스의 체 순열 중국인의 나머지 정리 모듈러 연산 최대공약수와 유클리드 호제법 소인수분해 해시 테이블 생일 문제 디피–헬먼 키 교환 소수 판정 P 대 NP 문제