117. 확장 유클리드 알고리즘 (Extended Euclidean Algorithm)

⚠️ 이 문서는 두 수가 겹치지 않는다는 사실(GCD=1)을 확인하는 것을 넘어, 한 걸음 더 나아가 RSA 암호의 꽃인 '개인키($d$)'를 기적처럼 정확히 계산해서 뚝딱! 하고 뱉어내는 수학적 3D 프린터, 확장 유클리드 알고리즘을 다룹니다.

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

본질: 일반 유클리드 알고리즘이 두 수의 최대공약수(GCD)가 무엇인지만 알려준다면, **확장 유클리드 알고리즘(EEA)**은 계산 과정을 거꾸로 거슬러 올라가 **베주 항등식 ($ax + by = GCD(a, b)$)**의 해(x, y)까지 통째로 찾아내는 업그레이드 버전이다.

가치: 이 알고리즘이 없었다면 RSA에서 공개키 $e$를 가지고도 해독 열쇠인 개인키 $d$를 우주 끝까지 가도 찾지 못해 시스템이 성립할 수 없다. EEA는 수백 자리의 거대한 식 $e \times d \equiv 1 \pmod{\phi(N)}$ 에서 단 몇 밀리초 만에 개인키 $d$(모듈로 역수)를 완벽하게 찾아내 쥐여준다.

융합: 이 고대 그리스의 낡은 수학 연산법은 현대 암호학(RSA, ECC 타원곡선 서명)의 코어 C 라이브러리에 하드코딩 융합되어, 전 세계 수십억 대의 스마트폰이 와이파이를 켜고 인증서를 발급받는 순간마다 보이지 않게 작동하며 암호 체계의 심장 박동을 유지하고 있다.

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

우리는 116번 문서에서 "공개키 $e$와 오일러 함수 $\phi(N)$의 최대공약수(GCD)가 1이어야만 개인키 $d$가 존재한다"는 것을 확인했다. 좋다. 존재한다는 사실(Fact)은 알았다. 그런데 수백 자리의 십진수 바다에서 도대체 "어떻게 그 $d$ 값을 콕 집어서 찾아낼 것인가?"

일반 대수학: $3 \times x = 1$ 일 때, $x = 1/3$ 이다. 소수가 나온다.
모듈로 암호학: $3 \times d \equiv 1 \pmod{20}$. 여기서 $d$는 소수가 아니라 1부터 20 사이의 정수여야 한다. 작은 숫자면 $d$에 1부터 20까지 손으로 일일이 곱해보면 7 ($3 \times 7 = 21 \equiv 1$) 임을 안다.
현실의 RSA: $65537 \times d \equiv 1 \pmod{어마어마한 600자리 숫자}$. 이걸 1부터 600자리 끝까지 대입해 보려면 컴퓨터가 불타 없어진다.

이 절망적인 무차별 대입을 완벽히 소거하고, 덧셈과 나눗셈 몇 번의 릴레이만으로 정답 $d$를 단숨에 끄집어내는 수학적 마법 지팡이가 바로 **확장 유클리드 알고리즘(EEA)**이다.

📢 섹션 요약 비유: 미로 속에 금괴(개인키 d)가 있다는 사실은 드론으로 확인했습니다(일반 유클리드). 하지만 벽을 다 부수고 찾으려면 100년이 걸립니다. 확장 유클리드는 입구에서부터 빵 부스러기를 떨어뜨리며 미로를 들어간 뒤, 목적지를 찍고 그 부스러기를 주우면서 거꾸로 딱 돌아 나오면 정확히 내 손에 금괴가 쥐어져 있는 미친 네비게이션입니다.

Ⅱ. 작동 원리: 베주 항등식 (Bézout's Identity)과 빵 부스러기

확장 유클리드 알고리즘의 심장에는 프랑스 수학자 에티엔 베주가 증명한 베주 항등식이 들어 있다. "두 숫자 $A$와 $B$의 최대공약수(GCD)는, 항상 어떤 정수 $x$와 $y$를 가져와서 $A \cdot x + B \cdot y = GCD$ 형태로 나타낼 수 있다."

우리의 RSA 세계에 이 마법의 공식을 대입해 보자.

$A$는 우리의 공개키 $e$
$B$는 우리의 오일러 함수 $\phi(N)$
$GCD(e, \phi(N)) = 1$ 이 되어야 안전하다.
공식을 대입하면 $\rightarrow$ $e \cdot x + \phi(N) \cdot y = 1$

여기서 양변을 $\pmod{\phi(N)}$ 이라는 쳇바퀴 상자에 집어넣어 버리면 기적이 일어난다! $\phi(N) \cdot y$ 부분은 $\phi(N)$으로 나누면 나머지가 무조건 0이 되어 허공으로 날아가 버린다. 결국 남는 식은 $e \cdot x \equiv 1 \pmod{\phi(N)}$ 이 된다. 오 마이 갓! 여기서 튀어나온 $x$ 가 바로 우리가 그렇게 애타게 찾던 모듈로 역수, 즉 개인키 $d$ 였던 것이다!

빵 부스러기 줍기 (역추적 과정)

그럼 저 $x$와 $y$를 어떻게 찾는가? 컴퓨터는 일단 일반 유클리드 호제법처럼 나눗셈을 하며 몫과 나머지를 주르륵 밑으로 적어 내려간다(빵 부스러기 흘리기). 나머지가 1이 나오면, 아래쪽 식부터 시작해 위의 식을 대입하면서 거꾸로 치고 올라간다(역대입). 제일 꼭대기에 도달하면 짠! 하고 $x$ 값(개인키 $d$)과 $y$ 값이 정수로 딱 떨어져 나온다.

┌───────────────────────────────────────────────────────────────────────────┐
│           확장 유클리드 알고리즘의 개인키 'd' 색출 작전 시각화            │
├───────────────────────────────────────────────────────────────────────────┤
│                                                                           │
│ [ 상황: e=3, Φ(N)=20 일 때, 개인키 d를 찾아라! ]                          │
│                                                                           │
│ 1. 빵 부스러기 흘리기 (아래로 전진 - 나눗셈)                              │
│    20 = 3 × 6 + 2  (나머지 2)   --- (식 A)                                │
│     3 = 2 × 1 + 1  (나머지 1)   --- (식 B) ◀ 빙고! GCD=1 발견!            │
│                                                                           │
│ 2. 빵 부스러기 줍기 (거꾸로 올라가며 식 정리)                             │
│    식 B를 바꿈:  1 = 3 - (2 × 1)                                          │
│    여기에 식 A의 "2 = 20 - 3 × 6" 을 쏙 대입함!                           │
│                 1 = 3 - [ (20 - 3 × 6) × 1 ]                              │
│                                                                           │
│ 3. 최종 식 정리 (베주 항등식 형태 완성)                                   │
│    1 = 3 - 20 + (3 × 6)                                                   │
│    1 = 3 × (7) + 20 × (-1)                                                │
│        ↑   ↑     ↑     ↑                                                  │
│        e   x(d)  Φ(N)   y                                                 │
│                                                                           │
│ ★ 기적의 판결: "찾았다! 3 옆에 곱해진 7이 바로 우리가 찾던 개인키 d 다!"  │
└───────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 컴퓨터 공학에서 이 거꾸로 치고 올라가는 과정은 반복문(While 루프)이나 재귀 함수(Recursive Call) 몇 줄의 코드로 우아하게 짤 수 있다. 600자리짜리 큰 수라도 이 반복문을 몇백 번만 쳇바퀴 돌리면 1초도 안 되어 600자리짜리 개인키 $d$를 뱉어낸다. 암호학에서 무차별 대입(Brute Force)을 수식 계산(Algebra)으로 박살 내버린 통쾌한 공학의 승리다.

📢 섹션 요약 비유: 복잡하게 꼬인 이어폰 줄(거대한 방정식)을 힘으로 당겨서(무차별 대입) 풀려면 끊어집니다. 확장 유클리드 알고리즘은 꼬였던 매듭의 순서를 영상으로 녹화해 두었다가, 정확히 반대 순서로 살살 되감기 재생(역추적)하여 단숨에 줄을 완벽하게 풀어내는 천재적인 팁입니다.

Ⅲ. 암호학 전반에 걸친 실무 장악력

확장 유클리드 알고리즘(EEA)은 RSA 키를 만들고 나면 쓸모가 없어지는 1회용 함수가 아니다. 비대칭키 암호학이 굴러가는 모든 바퀴에 윤활유처럼 발려 있다.

RSA 암호의 심장 창조
- 우리가 지금까지 본 것처럼, 웹 서버가 HTTPS 통신을 위해 1년에 한 번씩 자기만의 인증서 쌍(공개키/개인키)을 발급받을 때 무조건 한 번 호출되어 은밀한 $d$ 값을 서버 하드디스크 깊숙이 묻어준다.
타원곡선 암호 (ECC / ECDSA)의 절대 필수 부품
- 비트코인이나 모바일 뱅킹에서 서명할 때 쓰이는 최신 타원곡선 암호에서는, 타원 위에서 점들을 덧셈하고 나눗셈할 때마다 분모를 없애주기 위해 '모듈로 역수'가 수만 번씩 필요하다. 이 무수한 연산들을 모조리 뒤에서 처리해 주는 엔진이 바로 EEA다.
블록 암호 (AES)
- AES 내부에서 글자를 아예 다른 모양으로 꼬아버리는 믹서기 사전인 'S-Box'를 짤 때도, 이 갈루아 체(수학) 안에서의 역수 계산 공식(EEA)을 사용하여 빈틈없는 난수 표를 설계한다.

Ⅳ. 결론

"수천 년 전 그리스 철학자의 호기심이, 21세기 디지털 철갑 자물쇠의 열쇠구멍을 뚫었다." 확장 유클리드 알고리즘은 단순한 수학 공식을 넘어, 유한한 시계 산술(모듈로 상자) 안에 영원히 갇혀 버릴 뻔했던 숫자들의 감옥 문을 부수고, '역원(돌아가는 길)'이라는 비상구를 만들어준 구원자다. এই 알고리즘 덕분에 인류는 비밀키와 공개키라는 완벽하게 분리된 두 개의 톱니바퀴를 수학적으로 한 치의 오차 없이 맞물리게 조립하는 '비대칭키 암호화'라는 마법을 완성할 수 있었다.

📌 관련 개념 맵

전제 지식: 일반 유클리드 호제법 (최대공약수 GCD 도출)
수학적 목표: 베주 항등식(Bézout's Identity) 풀이, 모듈로 곱셈 역원 (Modular Multiplicative Inverse) 계산
적용 암호 알고리즘: RSA (개인키 d 생성), ECC 타원곡선 암호 (점 덧셈/곱셈 연산 내부 코어)
프로그래밍 구현: 재귀 함수 (Recursion) 및 반복문 (Iterative Method)

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

공개키(자물쇠)는 있는데 이걸 열어줄 개인키(열쇠)를 1억 개의 무더기 속에서 하나씩 찾으려면 천 년이 걸려요!
그래서 옛날 그리스의 똑똑한 할아버지(유클리드)가 남긴 비법서를 컴퓨터에 입력했죠. "나눴던 기록을 거꾸로 다시 계산해 봐!"
컴퓨터가 그 비법대로 계산을 거꾸로 슝슝슝 100번만 타고 올라가니까, 신기하게도 내 손에 나에게 딱 맞는 단 하나의 완벽한 열쇠(개인키 d)가 뚝 떨어졌답니다!