🛒 "결제하기" 버튼을 누른 0.3초 동안 벌어지는 일

자, 상상해보자. 너 지금 새벽 2시에 침대에 누워서 쇼핑앱 켜놓고 있어.
장바구니에 담아둔 거 결제하려고 카드번호 입력하고 "결제하기" 딱 눌렀지.

그 순간, 네 폰이랑 쇼핑몰 서버 사이에는 수십 개의 공유기, 기지국, 해저 케이블이 끼어 있어.
네 카드번호는 그 길을 그대로 통과해야 해.
중간에 누가 몰래 엿듣고 있어도 이상하지 않은 구조야.

그런데도 우리는 아무렇지 않게 결제를 하지. 왜?
중간에 다 들여다봐도 무슨 소린지 알 수 없게 만드는 수학이 깔려 있기 때문이야.

재밌는 건, 이 두 정리는 암호를 만들려고 발명된 게 아니라는 것.
페르마는 1640년대 사람이고, 오일러는 1700년대 사람이야.
인터넷은커녕 전기도 없던 시절이지.

순수하게 "숫자가 신기하네?" 하는 호기심으로 만든 정리가
330년 뒤에 전 세계 전자상거래를 떠받치는 기둥이 된 거야.
이게 수학의 무서운 점이자 매력이지.

🧮 먼저 준비운동: '나머지 세계'에 오신 걸 환영합니다

RSA를 이해하려면 딱 하나의 감각만 장착하면 돼.
바로 모듈러 연산(modular arithmetic), 쉽게 말해 "나머지만 보는 세계"야.

⏰ 시계는 이미 모듈러 계산기다

지금 9시인데 5시간 뒤는 몇 시일까? 14시가 아니라 2시지.
왜냐면 시계는 12를 넘어가면 다시 0으로 돌아오니까.

이걸 수학 기호로 쓰면 이래:

여기서 ≡ 기호는 등호가 아니라 합동 기호야.
"완전히 같다"가 아니라 "나눈 나머지가 같다"는 뜻이지.

요일도 마찬가지야. 오늘이 월요일이면 100일 뒤는?
100 ÷ 7 = 14 나머지 2니까, 월요일에서 2칸 뒤인 수요일.
우리는 이미 일상에서 mod 7, mod 12, mod 24를 쓰고 있었던 거야.

🔑 모듈러 연산의 마법 같은 성질

모듈러 세계가 암호에 쓰이는 결정적 이유가 있어.
곱셈과 거듭제곱이 "나머지끼리" 계산해도 결과가 똑같다는 거야.

예시) 17 × 23 을 mod 5 로 계산하기

방법 A (정직하게): 17 × 23 = 391 → 391 mod 5 = 1
방법 B (나머지 먼저): 17 mod 5 = 2, 23 mod 5 = 3
                      2 × 3 = 6 → 6 mod 5 = 1

결과 동일! ✔

이게 왜 중요하냐고?
RSA에서는 수백 자리 숫자를 수백 자리 횟수만큼 거듭제곱해야 하는데,
만약 진짜 다 곱했다간 우주의 원자 수보다 큰 숫자가 나와.

하지만 매 단계마다 나머지만 남기면 숫자는 절대 커지지 않아.
컴퓨터가 감당할 수 있는 크기 안에서 계산이 끝나는 거지.

🎩 페르마의 소정리: 소수가 부리는 이상한 마술

피에르 드 페르마(Pierre de Fermat, 1601–1665)는 사실 직업 법률가였어.
툴루즈 지방의회 법관이었고, 수학은 어디까지나 취미였지.

그런데 이 아저씨가 취미로 남긴 것들이
확률론, 해석기하학, 정수론의 기초를 통째로 만들어버렸어.
(그리고 그 유명한 "여백이 좁아서 증명을 못 쓰겠다"는 페르마의 마지막 정리도 이 사람.)

📜 정리의 내용

말이 어렵지? 숫자로 때려보면 바로 납득돼.

🔢 직접 계산해보자 (p = 7)

소름 돋지 않아?
아무 숫자나 집어넣어도 6제곱 하면 무조건 나머지가 1이야.
729를 7로 나누면 104 나머지 1, 46656을 7로 나누면 6665 나머지 1.
우연이 아니라 법칙인 거지.

🧠 왜 이런 일이 벌어질까? (직관적 증명)

증명이 생각보다 예뻐. 같이 따라와 봐. p = 7, a = 3으로 해볼게.

1단계. 1부터 6까지의 수에 각각 3을 곱하고 mod 7 해보자.

3×1 = 3  → 3
3×2 = 6  → 6
3×3 = 9  → 2
3×4 = 12 → 5
3×5 = 15 → 1
3×6 = 18 → 4

결과 집합: {3, 6, 2, 5, 1, 4}
원래 집합: {1, 2, 3, 4, 5, 6}

→ 순서만 섞였을 뿐, 똑같은 집합! 🎲

2단계. 이게 우연이 아닌 이유는?
만약 3×i ≡ 3×j (mod 7)이면, 양변에서 3을 "약분"할 수 있어.
7이 소수라서 3과 7은 서로소이고, 따라서 i ≡ j가 돼.
즉 서로 다른 입력은 반드시 서로 다른 출력을 낸다는 뜻.
6개 자리에 6개 값을 겹치지 않게 배치하면 → 결국 전체를 섞어놓은 것뿐이야.

3단계. 이제 양쪽을 다 곱해버리자.

(3×1)(3×2)(3×3)(3×4)(3×5)(3×6) ≡ 1×2×3×4×5×6 (mod 7)

좌변 정리: 3⁶ × 6!  ≡  6! (mod 7)

6! = 720은 7과 서로소 → 양변에서 약분 가능

∴ 3⁶ ≡ 1 (mod 7)  ✔

끝! 증명이 세 줄이야.
"곱하기는 순열을 만든다" → "다 곱해서 약분한다". 이게 전부지.

🌍 오일러 정리: 소수가 아니어도 되게 만든 업그레이드

페르마의 정리는 훌륭하지만 치명적인 제약이 있어.
"p가 소수일 때"만 쓸 수 있다는 것.

그런데 RSA에서 쓰는 모듈러스 n은 소수가 아니라 두 소수의 곱이야.
n = p × q. 즉 합성수지. 페르마 정리를 그대로 못 써.

여기서 등장하는 사람이 레온하르트 오일러(Leonhard Euler, 1707–1783).
역사상 논문을 가장 많이 쓴 수학자, 말년에 실명하고도 암산으로 논문을 구술한 괴물.

φ(n), 오일러 파이 함수

오일러는 먼저 새로운 함수를 하나 정의해.

예를 들어 φ(10)을 구해보자.
1~10 중 10과 서로소인 수: 1, 3, 7, 9 → 총 4개.
따라서 φ(10) = 4.

여기서 엄청나게 중요한 두 가지 성질이 나와.

②번 검증: φ(15) = φ(3)×φ(5) = 2×4 = 8. 위 표와 일치! ✔

📜 오일러 정리

봐봐. n이 소수 p라면 φ(p) = p−1이니까
a^p−1 ≡ 1 (mod p) — 정확히 페르마의 소정리야.

즉 페르마의 소정리는 오일러 정리의 특수한 경우인 거지.
"소수 전용"이었던 법칙을 "모든 수"로 확장한 게 오일러의 공로.

🧪 숫자로 확인 (n = 10, a = 3)

φ(10) = 4
3⁴ = 81
81 mod 10 = 1  ✔

계속 돌려보면:
3¹ = 3  → 3
3² = 9  → 9
3³ = 27 → 7
3⁴ = 81 → 1   ← 여기서 한 바퀴!
3⁵      → 3   ← 다시 처음으로 반복

주기가 정확히 4 (= φ(10))

🔐 RSA: 세 사람의 이름을 딴 자물쇠

1977년, MIT의 세 연구자
Ron Rivest, Adi Shamir, Leonard Adleman이 논문을 발표해.
세 사람 성의 첫 글자를 따서 RSA.

이들이 해결한 문제는 이거였어.

기존 암호는 전부 대칭키였어. 자물쇠와 열쇠가 같은 방식.
그럼 열쇠를 어떻게 상대에게 전달하지? 그 전달 과정이 뚫리면 끝이잖아.
이게 수천 년간 암호학의 난제였던 키 분배 문제야.

💡 발상의 전환: 자물쇠와 열쇠를 분리하자

RSA의 아이디어는 이래.

쇼핑몰이 자기 자물쇠(공개키)를 전 세계에 뿌려.
너는 그 자물쇠로 카드번호를 잠가서 보내.
중간에 누가 가로채도? 자물쇠는 있는데 열쇠가 없어.
오직 쇼핑몰만 자기 개인키로 열 수 있지.

⚙️ RSA 키 생성 5단계

[1] 거대한 소수 두 개를 고른다 → p, q
    (실제로는 각각 1024비트, 약 308자리)

[2] n = p × q          ← 이게 모듈러스, 공개됨

[3] φ(n) = (p−1)(q−1)  ← 이건 비밀! 핵심 재료

[4] φ(n)과 서로소인 e를 고른다  ← 공개 지수
    (보통 e = 65537 사용)

[5] e × d ≡ 1 (mod φ(n)) 을 만족하는 d를 찾는다
    ← 개인 지수, 절대 비밀

공개키 = (n, e)     |     개인키 = (n, d)
p, q, φ(n) 은 계산 후 파기

🔄 암호화와 복호화

끝이야. 진짜 이게 다야.
거듭제곱 두 번으로 세계 경제가 돌아가고 있어.

🤔 왜 원래대로 돌아올까? — 오일러 정리 등판

복호화 과정을 풀어보자.

C^d = (M^e)^d = M^(ed)

그런데 우리는 ed ≡ 1 (mod φ(n)) 이 되도록 d를 골랐지.
즉, 어떤 정수 k에 대해  ed = 1 + k·φ(n)

따라서
M^(ed) = M^(1 + k·φ(n))
       = M · (M^φ(n))^k

여기서 오일러 정리! M^φ(n) ≡ 1 (mod n)

       ≡ M · 1^k
       ≡ M  (mod n)   🎉

봤지? 오일러 정리가 "1"을 만들어주는 순간,
지저분한 거듭제곱이 싹 사라지고 원래 메시지 M만 남아.

이게 RSA가 작동하는 수학적 이유의 전부야.
정말 아름답지 않아? 300년 전 정리 한 줄이 암호를 완성시킨 거야.

✏️ 손으로 따라 하는 미니 RSA

말로만 하면 감이 안 오지? 진짜 작은 숫자로 처음부터 끝까지 해보자.
계산기 없이도 따라올 수 있어.

Step 1. 소수 고르기

p = 11,  q = 13

Step 2. n 계산

n = 11 × 13 = 143

Step 3. φ(n) 계산

φ(143) = (11−1) × (13−1) = 10 × 12 = 120

Step 4. e 고르기

120과 서로소인 수 중 하나 선택 → e = 7
(120 = 2³×3×5 이고 7은 여기 안 들어감. OK ✔)

Step 5. d 찾기

7 × d ≡ 1 (mod 120) 을 만족하는 d는?

7 × 103 = 721
721 ÷ 120 = 6 나머지 1  ✔

→ d = 103

Step 6. 암호화 (M = 9를 보내자)

C = 9^7 mod 143

똑똑하게 계산하기 (제곱 반복법):
9¹ ≡ 9
9² = 81
9⁴ = 81² = 6561 → 6561 mod 143 = 6561 − 143×45 = 6561 − 6435 = 126

9⁷ = 9⁴ × 9² × 9¹
   ≡ 126 × 81 × 9 (mod 143)

126 × 81 = 10206 → 10206 mod 143 
         = 10206 − 143×71 = 10206 − 10153 = 53
53 × 9 = 477 → 477 mod 143 = 477 − 429 = 48

∴ C = 48

원래 메시지 9가 48이라는 엉뚱한 숫자로 바뀌었어.
누가 48을 가로채도 9라는 걸 알 방법이 없지.

Step 7. 복호화 (48을 다시 9로)

M = 48^103 mod 143

103 = 64 + 32 + 4 + 2 + 1 (이진수 1100111)

48¹  ≡ 48
48²  = 2304 → 2304 mod 143 = 2304 − 2288 = 16
48⁴  = 16² = 256 → 256 − 143 = 113
48⁸  = 113² = 12769 → 12769 mod 143 = 12769 − 12727 = 42
48¹⁶ = 42² = 1764 → 1764 − 1716 = 48
48³² = 48² ≡ 16
48⁶⁴ = 16² ≡ 113

48¹⁰³ = 48⁶⁴ × 48³² × 48⁴ × 48² × 48¹
      ≡ 113 × 16 × 113 × 16 × 48 (mod 143)

113 × 16 = 1808 → 1808 − 1716 = 92
92 × 113 = 10396 → 10396 − 10296 = 100
100 × 16 = 1600 → 1600 − 1573 = 27
27 × 48 = 1296 → 1296 − 1287 = 9

∴ M = 9  🎉 완벽 복원!

실제 RSA는 이 숫자들이 617자리(2048비트)일 뿐,
원리는 방금 우리가 손으로 한 것과 완전히 동일해.

🛡️ 그래서 왜 안 뚫리는데? — 소인수분해라는 벽

여기서 당연한 의문이 들지.

맞아. 이론적으로는 완벽하게 맞는 말이야.
RSA는 수학적으로 이미 "풀려 있는" 문제야.

문제는 시간이지.

⏳ 곱하기는 쉽고, 쪼개기는 지옥이다

이걸 일방향 함수(one-way function)의 비대칭성이라고 해.

자릿수가 커지면 이 격차가 기하급수적으로 벌어져.

우주 나이가 약 138억 년인데, 그만큼 걸린다는 얘기야.
"이론상 가능하지만 현실적으로 불가능" — 이게 현대 암호의 기본 철학이지.

🕵️ 공격자가 알아야 하는 것

공격자가 아는 것:  n, e, C
공격자가 원하는 것: M

경로 A: C^d mod n 계산 → d를 모름 ❌
경로 B: d 구하려면 φ(n) 필요 → φ(n) 모름 ❌
경로 C: φ(n) 구하려면 p, q 필요 → n 인수분해 필요 ❌
경로 D: 무차별 대입 → 2^2048 가지 ❌

모든 길이 막힘 = RSA의 안전성

✍️ 보너스: 전자서명은 자물쇠를 거꾸로 쓴다

RSA에는 재밌는 특성이 하나 더 있어.
e와 d를 바꿔 써도 작동한다는 것.

암호화:  C = M^e mod n  →  복호화: M = C^d mod n
서  명:  S = M^d mod n  →  검  증: M = S^e mod n

개인키로 먼저 잠그면 어떻게 될까?
누구나 공개키로 열 수 있어. 비밀은 전혀 안 되지.

대신 이런 의미가 생겨.

은행 앱의 공동인증서, 소프트웨어 코드 서명,
웹사이트 SSL 인증서가 전부 이 원리로 돌아가.
"이 사이트는 진짜 네이버가 맞습니다"를 수학적으로 증명하는 거지.

왜 RSA로 끝까지 안 하냐고?
느려서. RSA는 AES보다 수천 배 느려.
그래서 "느리지만 키 교환이 가능한 RSA" + "빠른 AES" 조합을 쓰는 거야.
이걸 하이브리드 암호 시스템이라고 해.

🧩 보너스 2: 페르마의 소정리는 소수 판별에도 쓰인다

RSA를 만들려면 거대한 소수 두 개가 필요하다고 했지?
그런데 308자리 숫자가 소수인지 어떻게 확인해?
1부터 나눠보는 건 당연히 불가능하고.

여기서 또 페르마가 등장해. 정리를 뒤집어서 쓰는 거야.

n = 15 가 소수일까? a = 2로 테스트

2^14 mod 15 = 16384 mod 15 = 4

4 ≠ 1  →  15는 합성수 확정! ✔
(실제로 15 = 3 × 5)

인수를 하나도 몰라도 "합성수다"라는 사실만은 순식간에 알아낼 수 있어.
이거 진짜 신기하지 않아? 범인이 누군지 몰라도 범죄가 있었다는 건 아는 격.

😈 하지만 함정이 있다: 카마이클 수

역은 성립하지 않아. 테스트를 통과해도 소수라는 보장이 없어.
모든 a에 대해 테스트를 통과하는 합성수가 존재하거든.

그래서 실무에서는 페르마 테스트를 강화한
밀러-라빈 소수판별법(Miller-Rabin)을 써.
이건 카마이클 수도 잡아내고, 테스트를 k번 반복하면
오판 확률이 4^−k 이하로 떨어져.

k=40이면 오판 확률이 약 10⁻²⁴.
컴퓨터 하드웨어가 고장 날 확률보다 낮지. 실질적으로 완벽해.

OpenSSL이 RSA 키를 만들 때도 정확히 이 과정을 거쳐.
난수를 하나 뽑고 → 밀러-라빈 돌리고 → 떨어지면 버리고 → 다시 뽑고.
소수 정리에 따르면 308자리 근처에서 소수 밀도는 약 1/709이라,
평균 수백 번 시도하면 하나 건진다는 계산이 나와.

⚠️ 수학은 완벽한데 구현이 뚫린다

재밌는 사실. RSA가 뚫린 사례는 거의 전부 수학이 아니라 구현 문제였어.

그래서 보안 업계의 제1계명이 이거야.

수학은 300년 검증됐지만, 구현은 사람이 하는 일이거든.
이런 실전 감각은 책만 봐서는 안 잡혀서,
재능넷 같은 재능 공유 플랫폼에서 현업 보안 개발자에게 직접 코드 리뷰를 받거나
정수론·암호학 과외를 받는 사람들도 꽤 많아졌어.
이론과 실무 사이의 간극을 메우는 데는 역시 사람이 최고지.

🌱 정리: 쓸모없는 수학은 없다

오늘 여정을 한 장으로 압축해보자.

영국 수학자 G.H. 하디는 1940년 저서 어느 수학자의 변명에서
정수론이 "전쟁에도 실용에도 쓸모없는, 그래서 아름다운 학문"이라고 자랑스럽게 썼어.

그로부터 37년 뒤, 그 "쓸모없는" 정수론은
전 세계 금융 거래의 토대가 되어버렸지.
하디가 지금 살아 있다면 어떤 표정일지 궁금하다. 😄

다음에 결제 버튼 누를 때,
그 0.3초 안에서 1640년의 페르마와 1763년의 오일러가
네 카드번호를 지키려고 열심히 일하고 있다는 걸 떠올려봐.

수학은 생각보다 훨씬 가까이, 그리고 훨씬 오래 우리 곁에 있었어. 🔐✨