PART II — 구조
정수론은 한때 "가장 순수한 수학"이라고 불렸어요. 응용이 전혀 없다는 게 자랑이었죠. 그런데 이제는 사정이 완전히 달라졌습니다. 여러분이 카페 와이파이로 인터넷 뱅킹을 켜는 순간, 그 거래는 RSA라는 공개키 암호 위에서 굴러가고 RSA의 안전성은 통째로 정수론에 기대고 있어요. 이 챕터에서는 가분성과 소수, 모듈러 산술을 거쳐 RSA가 왜 작동하고 왜 어려운지까지 한 번에 따라가 봅니다.
정수의 세계에서 가장 먼저 익혀야 할 동사는 "나눈다"입니다. 다만 우리가 보통 쓰는 "나누기"와 달리, 정수론에서는 결과가 정수로 딱 맞아떨어지는 경우만 의미가 있어요. 예를 들어 \( 6 = 2 \cdot 3 \)이니 \( 2 \)는 \( 6 \)을 나누지만, \( 7 \)은 \( 6 \)을 나누지 못합니다.
정의 9.1.1 (가분성)
정수 \( a, b \)에 대해, 어떤 정수 \( k \)가 존재해 \( b = a \cdot k \)이면 "\( a \)가 \( b \)를 나눈다"고 하고 \( a \mid b \)로 씁니다. 이때 \( a \)는 \( b \)의 약수, \( b \)는 \( a \)의 배수예요.
몇 가지 즉시 따라오는 성질이 있습니다. \( a \mid b \)이고 \( a \mid c \)이면 어떤 정수 \( s, t \)에 대해서도 \( a \mid (sb + tc) \)예요. 즉 약수는 정수계수 선형결합 안에서도 살아남습니다. 또 \( 0 \)은 모든 정수를 약수로 가지지만 자기 자신만 \( 0 \)을 나눌 수 있는 특수한 값이고, \( 1 \)과 \( -1 \)은 모든 정수의 약수예요.
정리 9.1.2 (나눗셈 정리, Division Theorem)
임의의 정수 \( a \)와 양의 정수 \( n \)에 대해, \( a = qn + r \)이고 \( 0 \le r < n \)을 만족시키는 정수 \( q, r \)가 유일하게 존재합니다. \( q \)는 몫, \( r \)는 나머지(remainder)예요.
이 정리는 너무 당연해 보여서 처음에는 "이걸 왜 정리라고 부르지?" 싶지만, 사실 \( \gcd \)부터 모듈러 산술, 다항식 나눗셈까지 정수론의 거의 모든 알고리즘이 이 한 문장 위에 서 있어요. 나머지를 \( r = a \bmod n \)으로 표기합니다.
예제 9.1.3
\( a = 47, n = 5 \)면 \( 47 = 9 \cdot 5 + 2 \)이므로 \( q = 9, r = 2 \). \( a = -7, n = 3 \)이면 \( -7 = (-3) \cdot 3 + 2 \)이므로 나머지는 \( -1 \)이 아니라 \( 2 \)입니다. 음수일 때 \( r \ge 0 \)이라는 조건을 빠뜨리기 쉬워요.
두 정수의 공통된 약수 중 가장 큰 것을 최대공약수라 부르고 \( \gcd(a,b) \)로 씁니다. 초등학교에서는 약수를 모조리 나열해서 비교했지만, 큰 수에서는 이 방법이 끔찍하게 비효율적이에요. 다행히 기원전 300년경에 유클리드가 너무나 우아한 알고리즘을 남겼습니다.
정리 9.2.1 (유클리드 알고리즘의 핵심)
모든 정수 \( a, b \) (단 \( b \neq 0 \))에 대해 \[ \gcd(a, b) = \gcd(b,\ a \bmod b). \] 즉 큰 수를 작은 수로 나눈 나머지로 바꿔 가며 반복하면 결국 한쪽이 \( 0 \)이 되고, 그때 다른 쪽이 정답입니다.
예제 9.2.2 (\( \gcd(252, 198) \))
\( 252 = 1 \cdot 198 + 54 \), \( 198 = 3 \cdot 54 + 36 \), \( 54 = 1 \cdot 36 + 18 \), \( 36 = 2 \cdot 18 + 0 \). 따라서 \( \gcd(252, 198) = 18 \). 단 네 줄로 끝났어요.
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
그런데 유클리드 알고리즘은 단지 값만 알려주는 게 아니라, 거꾸로 따라가면 \( \gcd \)를 \( a \)와 \( b \)의 정수계수 결합으로 쓰는 방법까지 줍니다. 이게 베주의 정리예요.
정리 9.2.3 (베주 항등식, Bézout)
임의의 정수 \( a, b \)에 대해 \( \gcd(a,b) = ax + by \)를 만족하는 정수 \( x, y \)가 존재합니다.
예제로 위의 \( \gcd(252, 198) = 18 \)을 거꾸로 풀면 \( 18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 \), 다시 \( 54 = 252 - 198 \)이므로 \( 18 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198 \). 즉 \( x = 4, y = -5 \)입니다. 이 \( x, y \)는 9.9에서 곱셈 역원을 만들 때 결정적으로 쓰이니 잘 기억해 두세요.
1보다 큰 정수 \( p \)가 \( 1 \)과 자기 자신 외의 양의 약수를 갖지 않으면 소수(prime)라고 부릅니다. 그렇지 않은 정수는 합성수(composite)예요. 사람들은 2300년 넘게 소수를 들여다봤는데도 여전히 풀지 못한 문제가 산처럼 쌓여 있습니다.
정리 9.3.1 (유클리드)
소수는 무한히 많습니다.
증명 (스케치)
유한히 많다고 가정하고 그 전부를 \( p_1, p_2, \dots, p_k \)라 합시다. 이제 \( N = p_1 p_2 \cdots p_k + 1 \)을 보세요. \( N \)은 어떤 \( p_i \)로 나누어도 나머지가 \( 1 \)이라 \( p_i \)의 배수가 아닙니다. 그런데 \( N > 1 \)이므로 어떤 소수의 배수여야 해요(이건 9.4에서 보장됩니다). 따라서 우리 목록에 없는 소수가 있다는 뜻이고, 이는 모순입니다.
∎
"그럼 소수가 얼마나 자주 나오나?"가 다음 질문이에요. \( \pi(n) \)을 \( n \) 이하의 소수 개수라고 하면, 가우스가 십대 시절에 추측하고 1896년에 증명된 결과가 다음과 같습니다.
정리 9.3.2 (소수 정리, Prime Number Theorem)
\[ \pi(n) \sim \frac{n}{\ln n}. \] 즉 \( n \) 근처에서 무작위로 정수를 뽑았을 때 소수일 확률이 대략 \( 1/\ln n \).
한편 풀리지 않은 거대 추측들도 있어요. 쌍둥이 소수 추측은 \( p \)와 \( p+2 \)가 동시에 소수인 쌍이 무한히 많다고 주장합니다. 골드바흐 추측은 \( 4 \) 이상의 짝수는 모두 두 소수의 합으로 쓸 수 있다는 250년 묵은 문제예요. 컴퓨터로 \( 4 \cdot 10^{18} \)까지는 확인됐지만, 증명은 아직 없습니다.
노트
소수 정리가 RSA에 왜 중요할까요? 1024비트 소수 두 개가 필요할 때, "소수일 확률이 \( 1/\ln(2^{1024}) \approx 1/710 \)"이라는 사실이 있어야 안심하고 무작위 후보를 뽑을 수 있어요. 이 확률이 0에 가까웠다면 RSA 키 생성은 실용적이지 않았을 거예요.
"모든 정수는 소수의 곱"이라는 사실은 너무 익숙해서 정리라는 자각조차 못하기 쉬워요. 그런데 정말 따져 보면, 이 분해가 항상 가능하다는 것과 게다가 유일하다는 것은 그 자체로 묵직한 정리입니다.
정리 9.4.1 (산술 기본정리)
\( 1 \)보다 큰 모든 정수 \( n \)은 \[ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \] 의 꼴로 쓸 수 있고, 소수 \( p_1 < p_2 < \cdots < p_k \)와 양의 지수 \( e_i \)는 유일하게 결정됩니다.
증명 스케치
존재성은 강한 귀납법으로 쉽게 보입니다. \( n \)이 소수면 끝, 합성수면 \( n = ab \) (\( 1 < a, b < n \))이고 귀납가설로 \( a, b \)가 각각 소인수분해를 가지니 결합하면 됩니다. 유일성이 진짜 핵심이에요. 핵심 보조정리는 유클리드의 보조정리: 소수 \( p \)가 \( ab \)를 나누면 \( p \mid a \)이거나 \( p \mid b \). 이걸 쓰면 두 분해가 다르다고 가정해도 결국 같은 소수들의 같은 지수 모음으로 강제되어 모순이 나옵니다.
∎
겉보기엔 당연하지만, 이 유일성은 사실 일반적인 수 체계에서 깨질 수 있어요. 예를 들어 \( \mathbb{Z}[\sqrt{-5}] \)에서는 \( 6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}) \)처럼 분해가 두 가지 나옵니다. 이걸 다루려고 19세기 수학자들이 "이데알(ideal)" 개념을 발명했죠. 정수에서 유일성이 성립한다는 건 결코 공짜가 아니에요.
예제 9.4.2
\( 360 = 2^3 \cdot 3^2 \cdot 5 \). 이 분해를 알면 약수의 개수는 \( (3+1)(2+1)(1+1) = 24 \)개라고 즉시 셀 수 있어요. 모든 약수 \( d \)는 \( 2^a 3^b 5^c \) (\( 0 \le a \le 3, 0 \le b \le 2, 0 \le c \le 1 \))의 꼴이니까요.
앨런 튜링(Alan Turing, 1912-1954)은 24살에 "계산 가능 함수"의 보편 모델인 튜링 기계를 정의해 컴퓨터 과학의 토대를 놓은 사람이에요. 제2차 세계대전 동안 영국 블레츨리 파크에서 독일군의 에니그마(Enigma) 암호를 깨뜨리는 데 결정적 기여를 했고, 그 덕에 전쟁이 수년 앞당겨 끝났다고 평가됩니다. 전후에는 동성애를 이유로 영국 정부에 의해 화학적 거세형을 받았고 1954년 청산가리 묻은 사과를 베어 문 채 발견됐어요(자살로 추정). 2009년 영국 총리, 2013년 여왕의 공식 사면이 있었지만 너무 늦었죠. 이 챕터에서 우리가 보게 될 모듈러 산술과 RSA는 모두 튜링이 평생 매달렸던 "암호 깨기"의 직계 후손입니다.
노트
튜링상(Turing Award)은 컴퓨터 과학의 노벨상이라 불려요. 매년 한 명에게 주어지고, 상금은 100만 달러. 이 상의 이름이 왜 튜링이어야 했는지는 9.8과 9.11을 보면 자연히 이해됩니다.
시계는 \( 12 \)를 넘으면 다시 \( 1 \)로 돌아갑니다. 13시는 1시와 "같은 자리"예요. 이 직관을 정수 전체에 적용한 게 모듈러 산술입니다.
정의 9.6.1 (합동, congruence)
양의 정수 \( n \)과 정수 \( a, b \)에 대해, \( n \mid (a - b) \)이면 \( a \)와 \( b \)는 \( n \)을 법으로 합동이라 하고 \[ a \equiv b \pmod{n} \] 으로 씁니다.
같은 말로, \( a \)와 \( b \)를 \( n \)으로 나눈 나머지가 같다는 뜻이에요. 이 관계는 정수 위의 동치관계입니다. 반사성·대칭성·추이성을 모두 만족하니까요. 동치관계가 있으면 동치류로 분할이 따라옵니다. \( n = 5 \)일 때 정수는 다섯 개의 동치류로 쪼개져요: \( [0], [1], [2], [3], [4] \). 각 동치류는 \( \{ \dots, -5, 0, 5, 10, \dots \} \) 같은 무한집합이에요.
모듈러 산술이 강력한 진짜 이유는 합과 곱이 동치류 위에서 잘 정의된다는 점입니다.
정리 9.6.2 (합·곱의 잘 정의됨)
\( a \equiv a' \pmod{n} \)이고 \( b \equiv b' \pmod{n} \)이면 \[ a + b \equiv a' + b' \pmod{n}, \quad a \cdot b \equiv a' \cdot b' \pmod{n}. \]
증명은 간단합니다. \( a - a' \)와 \( b - b' \)가 \( n \)의 배수이면 \( (a+b) - (a'+b') \)와 \( ab - a'b' = a(b-b') + b'(a-a') \)도 모두 \( n \)의 배수예요. 그래서 우리는 큰 수를 다룰 때 거추장스럽게 끌고 다닐 필요 없이, 매 단계마다 \( \bmod n \)으로 나머지를 취해도 결과가 같다는 자유를 얻습니다.
예제 9.6.3
\( 7^{100} \bmod 4 \)는 얼마? \( 7 \equiv 3 \equiv -1 \pmod{4} \)이므로 \( 7^{100} \equiv (-1)^{100} = 1 \pmod{4} \). 큰 수를 직접 계산할 필요가 전혀 없어요.
합동을 동치관계로 보고 동치류 자체를 원소로 삼는 새 집합을 만들 수 있어요. 이 집합을 \[ \mathbb{Z}_n = \{0, 1, 2, \dots, n-1\} \] 라고 쓰고, 각 원소를 "그 동치류의 대표 나머지"로 봅니다.
\( \mathbb{Z}_n \)에서의 덧셈과 곱셈은 정수의 덧셈·곱셈을 한 뒤 \( n \)으로 나머지를 취하는 것으로 정의해요. 9.6에서 이게 잘 정의된다는 걸 봤습니다. 결과적으로 \( \mathbb{Z}_n \)은 가환환(commutative ring)이 됩니다. 곧, 결합법칙·교환법칙·분배법칙이 모두 성립하고, \( 0 \)과 \( 1 \)이라는 항등원을 갖습니다.
예제 9.7.1 (\( \mathbb{Z}_5 \)의 곱셈표 일부)
\( 3 \cdot 4 = 12 = 2 \cdot 5 + 2 \)이므로 \( \mathbb{Z}_5 \)에서 \( 3 \cdot 4 = 2 \). \( 2 \cdot 3 = 6 = 1 \), \( 4 \cdot 4 = 16 = 1 \). 잘 보면 \( \mathbb{Z}_5 \)에서 0이 아닌 모든 원소가 곱셈 역원을 가져요. 이건 \( 5 \)가 소수라서 그렇습니다.
한편 \( \mathbb{Z}_6 \)에서는 사정이 다릅니다. \( 2 \cdot 3 = 6 = 0 \)이거든요. 두 0이 아닌 원소를 곱했는데 0이 나오는 일이 벌어집니다. 이런 \( \mathbb{Z}_n \)을 "영인자(zero divisor)가 있다"고 말해요. \( n \)이 합성수일 때 일어나는 현상이고, 이게 9.9에서 나올 곱셈 역원의 존재 조건과 직결됩니다.
노트
해시 함수, 체크섬, 의사난수 생성기, 빠른 멱승 등 컴퓨터에서 정수 연산을 다룰 때 \( \mathbb{Z}_n \)은 거의 항상 등장합니다. 32비트 부호 없는 정수의 산술이 곧 \( \mathbb{Z}_{2^{32}} \) 위의 산술이에요.
아주 단순한 암호 시나리오를 그려 봅시다. 앨리스가 밥에게 메시지 \( m \)(어떤 \( \mathbb{Z}_p \) 안의 수, \( p \)는 큰 소수)을 보내려고 합니다. 둘은 사전에 비밀키 \( k \)를 공유했고, 앨리스는 \[ c = m \cdot k \pmod{p} \] 로 암호화해서 \( c \)를 보냅니다. 밥은 \( k \)의 곱셈 역원 \( k^{-1} \)을 알고 있으니 \[ m = c \cdot k^{-1} \pmod{p} \] 로 복호화하면 끝이에요. 깔끔해 보이죠?
그런데 이 방식엔 치명적 약점이 있습니다. 공격자 이브가 메시지 두 개 \( c_1 = m_1 k \), \( c_2 = m_2 k \)를 가로챘다고 합시다. 이브는 \( c_1 \cdot c_2^{-1} = m_1 \cdot m_2^{-1} \pmod{p} \)를 계산할 수 있어요. 키 \( k \)가 깨끗이 사라집니다. 이브가 만약 메시지 한 개의 평문을 우연히 알게 된다면 — 가령 인사말 "안녕"이 거의 매번 들어간다면 — 다른 모든 메시지의 평문도 같이 무너져요.
노트 (왜 알아야 하나)
이 약점을 보면 "단일 키로 곱하기만 하는" 식의 암호로는 안전을 보장할 수 없다는 게 분명해집니다. 9.11의 RSA는 이 문제를 두 개의 다른 키, 그리고 곱셈이 아닌 멱승 연산으로 해결해요. 그 멱승의 안전성을 떠받치는 게 다음에 나오는 오일러 정리입니다.
\( \mathbb{Z}_n \)에서 \( a \)의 곱셈 역원이란 \( a \cdot a^{-1} \equiv 1 \pmod{n} \)을 만족하는 원소입니다. 어떤 \( a \)는 역원을 가지고 어떤 건 못 가져요. 그 기준이 정확히 무엇일까요?
정리 9.9.1 (역원 존재 조건)
\( a \in \mathbb{Z}_n \)이 곱셈 역원을 가질 필요충분조건은 \( \gcd(a, n) = 1 \)입니다.
증명
(⇐) \( \gcd(a, n) = 1 \)이면 베주의 정리(9.2.3)에 의해 \( ax + ny = 1 \)인 정수 \( x, y \)가 있어요. 양변을 \( \bmod n \)으로 보면 \( ax \equiv 1 \pmod n \)이라 \( x \)가 곧 \( a^{-1} \). (⇒) \( a a^{-1} \equiv 1 \pmod n \)이면 어떤 정수 \( y \)에 대해 \( a a^{-1} - 1 = ny \), 곧 \( a a^{-1} + n(-y) = 1 \). \( a, n \)의 임의의 공약수는 \( 1 \)도 나누어야 하니 \( \gcd(a, n) = 1 \).
∎
특히 \( n = p \)가 소수면 \( 1, 2, \dots, p-1 \) 모두가 \( p \)와 서로소이므로 모두 역원을 가져요. 그래서 \( \mathbb{Z}_p \)는 단지 환을 넘어 체(field)가 됩니다.
역원의 존재는 곧 "소거(cancellation)"의 가능 여부를 결정합니다. \( ab \equiv ac \pmod n \)에서 \( a \)를 양쪽에서 지우려면 \( a^{-1} \)을 곱해야 하는데, 그러려면 \( \gcd(a, n) = 1 \)이 필수예요. 이 조건이 없으면 일반적으로 소거가 안 됩니다. 예를 들어 \( \mathbb{Z}_6 \)에서 \( 2 \cdot 1 \equiv 2 \cdot 4 \pmod 6 \)이지만 \( 1 \not\equiv 4 \).
예제 9.9.2 (\( \mathbb{Z}_{11} \)에서 \( 7^{-1} \))
\( \gcd(7, 11) = 1 \). 확장 유클리드: \( 11 = 1 \cdot 7 + 4 \), \( 7 = 1 \cdot 4 + 3 \), \( 4 = 1 \cdot 3 + 1 \). 거꾸로 \( 1 = 4 - 3 = 4 - (7 - 4) = 2 \cdot 4 - 7 = 2(11 - 7) - 7 = 2 \cdot 11 - 3 \cdot 7 \). 따라서 \( -3 \cdot 7 \equiv 1 \pmod{11} \)이고 \( 7^{-1} \equiv -3 \equiv 8 \pmod{11} \). 검산: \( 7 \cdot 8 = 56 = 5 \cdot 11 + 1 \).
\( \mathbb{Z}_n \)에서 역원을 가지는 원소의 개수를 세는 함수가 오일러의 토션트(totient) \( \varphi(n) \)입니다.
정의 9.10.1 (오일러의 \( \varphi \) 함수)
\( \varphi(n) = |\{ a \in \{1, 2, \dots, n\} : \gcd(a, n) = 1 \}| \). 즉 \( n \)과 서로소인 \( n \) 이하 양의 정수의 개수.
몇 가지 사실. \( p \)가 소수면 \( 1, 2, \dots, p-1 \)이 모두 \( p \)와 서로소이므로 \( \varphi(p) = p - 1 \). \( p, q \)가 서로 다른 소수면 곱셈성을 이용해 \[ \varphi(pq) = (p-1)(q-1). \] 이 한 줄이 RSA의 심장이에요.
정리 9.10.2 (오일러)
\( \gcd(a, n) = 1 \)이면 \[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]
증명 스케치
\( \mathbb{Z}_n \) 안에서 \( n \)과 서로소인 원소들의 집합을 \( S = \{r_1, r_2, \dots, r_{\varphi(n)}\} \)이라 합시다. \( a \)도 \( n \)과 서로소이므로, \( aS = \{a r_1, a r_2, \dots\} \)는 \( S \)의 순열입니다(소거 가능하니까). 따라서 \[ \prod_i (a r_i) \equiv \prod_i r_i \pmod n. \] \( a \)를 모아 \( a^{\varphi(n)} \prod r_i \equiv \prod r_i \), \( \prod r_i \)는 가역이므로 양변에서 지우면 \( a^{\varphi(n)} \equiv 1 \).
∎
특수한 경우로 \( n = p \)(소수)면 \( \varphi(p) = p-1 \)이라 다음이 즉시 따라와요.
따름정리 9.10.3 (페르마의 소정리)
\( p \)가 소수이고 \( p \nmid a \)이면 \( a^{p-1} \equiv 1 \pmod{p} \).
예제 9.10.4
\( 3^{100} \bmod 7 \)은? \( \gcd(3,7)=1 \)이고 \( 3^6 \equiv 1 \pmod 7 \). \( 100 = 6 \cdot 16 + 4 \). 따라서 \( 3^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7 \).
이제 모든 재료가 모였어요. RSA(Rivest-Shamir-Adleman, 1977)는 인류 역사상 가장 널리 쓰인 공개키 암호이자, 정수론이 일상에 직접 들어온 사건입니다. 핵심은 "인수분해는 어렵고, 멱승은 쉽다"는 비대칭성이에요.
정의 9.11.1 (RSA 키 생성)
① 큰 서로 다른 소수 \( p, q \)를 비밀리에 고르고 \( n = pq \)로 둡니다. ② \( \varphi(n) = (p-1)(q-1) \)을 계산. ③ \( \gcd(e, \varphi(n)) = 1 \)인 정수 \( e \)를 고름(공개 지수). ④ 확장 유클리드로 \( d = e^{-1} \pmod{\varphi(n)} \)를 계산(비밀 지수). ⑤ 공개키는 \( (n, e) \), 비밀키는 \( d \). \( p, q, \varphi(n) \)은 폐기 또는 비밀 보관.
암호화·복호화는 단순한 멱승이에요. 평문 \( m \in \mathbb{Z}_n \)에 대해 \[ \text{암호화: } c = m^e \bmod n, \quad \text{복호화: } m = c^d \bmod n. \]
정리 9.11.2 (RSA의 정확성)
\( \gcd(m, n) = 1 \)이면 \( (m^e)^d \equiv m \pmod{n} \). (\( \gcd(m,n) \neq 1 \)인 경우도 중국인의 나머지 정리로 확장 가능.)
증명
키 생성에서 \( ed \equiv 1 \pmod{\varphi(n)} \)이므로 어떤 정수 \( k \)에 대해 \( ed = 1 + k\varphi(n) \). 따라서 \[ m^{ed} = m^{1 + k\varphi(n)} = m \cdot \big(m^{\varphi(n)}\big)^k. \] 오일러 정리(9.10.2)에 의해 \( m^{\varphi(n)} \equiv 1 \pmod n \), 그러므로 \( m^{ed} \equiv m \cdot 1^k = m \pmod n \).
∎
예제 9.11.3 (작은 RSA)
\( p = 5, q = 11 \), \( n = 55 \), \( \varphi(n) = 4 \cdot 10 = 40 \). \( e = 3 \) (\( \gcd(3, 40) = 1 \)). \( d \)는 \( 3d \equiv 1 \pmod{40} \)에서 \( d = 27 \) (\( 3 \cdot 27 = 81 = 2 \cdot 40 + 1 \)). 평문 \( m = 8 \)을 암호화하면 \( c = 8^3 \bmod 55 = 512 \bmod 55 = 17 \). 복호화: \( c^{27} \bmod 55 \)는 멱승 반복 제곱법으로 계산하면 정확히 \( 8 \)이 나옵니다(직접 해 보세요).
왜 안전할까요? 이브가 공개키 \( (n, e) \)와 \( c \)를 봐도 \( m \)을 복원하려면 \( d \)가 필요하고, \( d \)를 알려면 \( \varphi(n) \)이 필요한데, \( \varphi(n) \)을 알려면 \( n \)을 \( pq \)로 인수분해해야 합니다. 그런데 1024비트, 2048비트짜리 \( n \)을 인수분해하는 알려진 알고리즘은 모두 너무 느려요. 슈퍼컴퓨터로도 수십억 년이 걸린다고 추정됩니다.
RSA의 안전은 "큰 정수의 인수분해가 어렵다"는 가정 위에 있어요. 그런데 진짜로 어렵다는 게 증명됐을까요? 슬프게도 답은 "아직 모름"입니다. 인수분해 문제 FACTOR는 NP에 속해요. 검증은 쉬우니까요. 어떤 \( n \)과 후보 \( (p, q) \)를 받으면 곱셈 한 번으로 \( pq = n \)인지 확인 가능합니다.
여기서 4장의 SAT가 등장합니다. SAT(논리식 충족 가능성)은 NP-완전 문제예요. 만약 \( P = NP \)가 증명된다면, SAT를 다항시간에 풀 수 있고, 그러면 NP에 있는 모든 문제(인수분해 포함)도 다항시간에 풀려서 RSA가 무너집니다. 반대로 \( P \neq NP \)가 증명되어도, 그것만으로는 인수분해가 어렵다는 결론이 자동으로 따라오진 않아요. 인수분해는 NP-완전성이 알려져 있지 않은 "중간 난이도" 문제로 분류되거든요.
노트 (양자 컴퓨팅)
1994년 피터 쇼어(Peter Shor)는 양자 컴퓨터에서 인수분해를 다항시간에 푸는 알고리즘을 발견했습니다. 충분히 큰 결함 허용 양자 컴퓨터가 등장하면 RSA는 한순간에 깨져요. 그래서 NIST는 격자(lattice) 기반 같은 "포스트 양자 암호"를 표준화하고 있습니다. 정수론이 일선에서 물러나는 게 아니라, 더 깊은 정수·대수 구조로 무대가 옮겨 가는 셈이에요.
요약하면, 우리가 매일 누리는 인터넷의 보안은 "인수분해는 어렵고 멱승은 쉽다"는 한 줄의 비대칭성에 걸려 있고, 그 비대칭성의 정확한 이유는 컴퓨터 과학에서 가장 큰 미해결 문제인 \( P \) vs \( NP \)와 깊이 얽혀 있습니다. 가장 순수하다던 정수론이 가장 실용적인 분야로 변신한 이야기, 이것이 이 챕터의 진짜 결말이에요.