116. GCD (Greatest Common Divisor, 최대공약수)

⚠️ 이 문서는 초등학교 수학 시간에 배운 단순한 개념인 최대공약수(GCD)가 암호학으로 넘어와, RSA의 핵심 자물쇠인 '공개키($e$)'를 선택할 때 서로 겹치는 약수가 없음을 증명(서로소, Coprime)하여 암호가 풀리는 기적을 가능케 하는 결정적 나침반 역할을 어떻게 수행하는지 다룹니다.

핵심 인사이트 (3줄 요약)

본질: GCD(최대공약수)는 두 개 이상의 정수가 공통으로 가지는 약수 중 가장 큰 값을 의미하며, 특히 **$GCD(A, B) = 1$일 때 두 수는 '서로소(Coprime)'**라는 수학적 특권을 가진다.

가치: RSA 암호에서 공개키 지수 $e$를 뽑을 때, $e$는 반드시 오일러 파이 함수 $\phi(N)$과 서로소($GCD(e, \phi(N)) = 1$)여야만 한다. 만약 1이 아니라 겹치는 약수가 있다면, 영원히 닫힌 자물쇠를 다시 열 수 있는 **해독 열쇠(개인키 $d$)가 수학적으로 아예 존재하지 않게 되는 파국(에러)**이 발생한다.

융합: 거대한 수백 자리 숫자의 GCD를 구하기 위해 기원전에 발명된 인류 최초의 알고리즘인 **유클리드 호제법(Euclidean Algorithm)**이 컴퓨터 칩에 융합되어, 암호키를 찍어내는 0.001초의 찰나에 겹치는 약수가 있는지를 초스피드로 걸러낸다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

우리는 초등학교 때 12와 18의 최대공약수를 찾기 위해 소인수분해 트리를 그렸다 ($GCD(12, 18) = 6$). 하지만 RSA 암호학에서 소인수분해 트리를 그리는 짓은 자살 행위다. 숫자가 600자리가 넘기 때문이다.

다행히 암호학자들은 2,300년 전 그리스의 천재 유클리드가 만들어 놓은 '유클리드 호제법(나눗셈의 나머지를 꼬리에 꼬리를 물고 이어가는 공식)'을 컴퓨터 코드로 짜넣어, 수백 자리의 괴물 숫자 두 개의 최대공약수(GCD)를 단 몇 밀리초(ms) 만에 뽑아낸다.

그렇다면 왜 암호학은 이렇게 핏대를 세우며 GCD를 구하려 할까? **"수학적 톱니바퀴가 완벽하게 맞물려 돌아가기 위해서"**다. 두 숫자의 $GCD$가 1(서로소)이 아니라면, 비밀번호를 넣어 상자를 잠갔을 때, 우주를 다 뒤져도 그 상자를 다시 열 수 있는 역산(Inverse)의 열쇠가 뚝 끊어지고 아예 생성되지 않는 치명적 에러가 발생하기 때문이다.

📢 섹션 요약 비유: 톱니바퀴 두 개(자물쇠와 열쇠)를 맞물려 돌릴 때, 두 톱니바퀴의 톱니 개수가 완벽하게 어긋나야(GCD=1) 한 바퀴를 돌아 제자리로 기분 좋게 찰칵! 하고 떨어집니다. 만약 톱니 개수가 공통된 배수를 가지면(GCD가 1이 아니면) 중간에 톱니가 꽉 걸려서 금고 문이 영원히 열리지 않는 고철 덩어리가 됩니다.

Ⅱ. RSA 키 생성에서의 절대 법칙: $GCD(e, \phi(N)) = 1$

RSA 키 생성 5단계를 다시 떠올려보자. (111번 문서 참조) 우리는 거대 소수 $p, q$를 곱해 모듈러스 $N$을 만들고, 오일러 함수 $\phi(N) = (p-1)(q-1)$을 계산했다. 그다음 대문짝만하게 홈페이지에 걸어둘 **공개키(e)**를 골라야 하는데 아무 숫자나 고를 수 없다. 절대 조건이 하나 붙는다.

"오일러 함수 $\phi(N)$과 완벽한 서로소(GCD가 1)인 숫자 $e$를 골라야 한다!"

왜 하필 GCD가 1이어야 할까? (모듈러 역원의 존재 조건)

공개키 $e$를 정하면, 짝꿍이 되는 개인키 $d$를 컴퓨터가 계산해서 뱉어내야 한다. 개인키 $d$를 구하는 공식은 $e \times d \equiv 1 \pmod{\phi(N)}$ 이다. (즉, $e$의 역수를 구하는 것)

수학(정수론)의 절대 진리 중 하나는 이렇다: "어떤 수 $e$가 $\pmod{\phi(N)}$ 세상에서 역수(곱해서 1이 되는 짝꿍 $d$)를 가지려면, 두 수 $e$와 $\phi(N)$의 최대공약수(GCD)가 반드시 1이어야만 한다."

실패 사례 (GCD $\neq$ 1): 만약 $\phi(N) = 20$ 인데 내가 바보같이 짝수 $e = 4$ 를 골랐다 치자. $GCD(4, 20) = 4$ 다. (1이 아님). 4에다가 세상 무슨 숫자 $d$를 곱해서 20으로 나누더라도 무조건 나머지는 짝수(0, 4, 8, 12, 16)만 나오지, 절대 나머지 1이 나올 수 없다. 즉 개인키 $d$가 아예 생성되지 않아 암호 시스템이 고장 난다.
성공 사례 (GCD $=$ 1): $e = 3$ 을 고른다. $GCD(3, 20) = 1$ 이다 (서로소). $3 \times 7 = 21$ 이고 20으로 나누면 나머지 1이 딱 떨어진다! 개인키 $d=7$ 이 기적처럼 탄생한다.

┌────────────────────────────────────────────────────────────────────────┐
│           유클리드 호제법을 통한 초고속 GCD 도출과 열쇠의 탄생 시각화  │
├────────────────────────────────────────────────────────────────────────┤
│                                                                        │
│ [ 상황: 거대한 두 숫자가 서로소인지 0.001초 만에 확인해야 함 ]         │
│  - 오일러 파이 Φ(N) = 3120  (엄청 큰 수라 치자)                        │
│  - 내가 고른 공개키 e = 17                                             │
│                                                                        │
│ [ 유클리드 호제법 (나머지 꼬리물기 릴레이) 발동! ]                     │
│   3120 ÷ 17 = 몫 183, ★나머지 9★                                       │
│     17 ÷ 9  = 몫 1,  ★나머지 8★                                        │
│      9 ÷ 8  = 몫 1,  ★나머지 1★   ◀───── 빙고! 끝!                     │
│      8 ÷ 1  = 몫 8,  ★나머지 0★                                        │
│                                                                        │
│ ★ 컴퓨터의 판결: "마지막으로 나눈 수가 1이네! 즉 GCD(3120, 17) = 1!"   │
│   "이 두 숫자는 완벽한 서로소(Coprime)입니다. 짝꿍 열쇠 d를 찍어낼 수  │
│   있는 100% 안전한 공개키 e 로 합격 도장을 찍어 줍니다!"               │
└────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 단순한 나눗셈 릴레이(유클리드 알고리즘) 덕분에 우리는 600자리가 넘는 괴물 숫자들을 굳이 인수분해 트리를 그리지 않고도, 단 몇 번의 나누기 연산만으로 최대공약수가 1인지 아닌지 번개처럼 확인해 낼 수 있다. (실무에서는 $e$ 값을 고정으로 보통 65537 을 써서 이 GCD가 항상 1이 나오도록 안전하게 세팅해 둔다.)

📢 섹션 요약 비유: 혈액형 검사와 똑같습니다. 수혈(개인키 생성)을 해주려면 주는 피($e$)와 받는 피($\phi(N)$)가 거부반응 없이 완벽히 맞아야 살 수 있습니다. 두 숫자의 최대공약수(GCD)가 1인지 확인하는 것은 피가 응고되지 않고 안전하게 수혈될 수 있는지 피 한 방울 떨어뜨려 검사하는 '생존 필수 확인 절차'입니다.

Ⅲ. 실무적 활용: 공개키 e = 65537의 대통합

실제 프로그래머가 Java나 Python으로 RSA 키를 찍어낼 때, 코드는 굳이 매번 1부터 $e$를 고르며 "이게 GCD가 1일까?" 하고 헤매지 않는다.

실무의 마법 숫자 65537 ($2^{16} + 1$): 현재 전 세계 거의 모든 SSL/TLS 인증서는 공개키 $e$ 값으로 65537 이라는 숫자를 박아놓고 쓴다.
왜 65537일까?:
1. 65537은 '소수(Prime)'다. 소수는 자기 자신 말고는 약수가 없으므로, 어떤 거대한 $\phi(N)$을 데려와도 웬만해선 겹치는 약수가 없어 $GCD = 1$ 을 가볍게 달성하고 에러를 내지 않는다. (개인키 $d$ 생성 보장)
2. 2진수로 바꾸면 10000000000000001 이다. 양 끝에만 1이 있고 중간은 다 0이다. 아까 배운 '고속 거듭제곱'을 할 때 1이 적으면 연산(덧셈)을 덜 해도 되므로 CPU가 암호화를 눈 깜짝할 새 끝낼 수 있다. (퍼포먼스의 극대화)

Ⅳ. 결론

"정수론의 가장 낡고 소박한 도구가, 21세기 디지털 철갑의 심장을 조립하는 볼트가 되었다." GCD(최대공약수)는 단지 두 숫자를 나누는 소박한 수학 기호가 아니다. 두 개의 괴물 같은 숫자가 공통된 유전자(약수)를 가지지 않는다는 완벽한 타인(서로소)임을 증명함으로써, 잠긴 자물쇠를 풀 수 있는 단 하나의 마법의 열쇠(역원)가 우주 어딘가에 존재할 수 있도록 문을 열어주는 수학적 개국공신(Founding Contributor)이다. 유클리드의 이 2,300년 된 지혜가 없었다면 우리는 아직도 인터넷으로 신용카드를 긁지 못했을 것이다.

📌 관련 개념 맵

상위 개념: RSA 키 생성 알고리즘
필수 짝꿍 (검증 공식): 유클리드 호제법 (Euclidean Algorithm)
목표 달성: 모듈로 역원 (Modular Multiplicative Inverse) 존재의 수학적 증명
핵심 조건 상태: 서로소 (Coprime), $GCD = 1$

👶 어린이를 위한 3줄 비유 설명

비밀번호 자물쇠(공개키)를 만들려면, 두 개의 엄청나게 큰 숫자가 절대 겹치는 약속 기호(약수)를 가지지 않아야 짝꿍 열쇠(개인키)가 뚝딱! 하고 만들어져요.
겹치는 기호가 하나라도 있으면 자물쇠가 엉켜서 평생 열리지 않는 불량품이 돼버리거든요.
그래서 컴퓨터는 자물쇠를 굽기 전에 0.001초 만에 "두 숫자의 최대공약수(GCD)가 1이다(겹치는 게 하나도 없다)!"라고 검사 도장을 먼저 쾅 찍어준답니다.