컴퓨터공학 300 주제 시리즈의 012번째 글이다. 전체 지도는 여기.

한 줄 요약

a 의 법 n 에 대한 역원은 a·x ≡ 1 (mod n) 인 x 이며, gcd(a, n) = 1 일 때만 존재하고 확장 유클리드로 구한다. 페르마 소정리(소수 p 에 대해 aᵖ⁻¹ ≡ 1)와 그 일반화인 오일러 정리는 역원 계산, 소수 판정, RSA 의 정당성을 한꺼번에 설명한다.

왜 필요한가

지난 글에서 모듈러 산술은 덧셈·뺄셈·곱셈은 자유롭지만 나눗셈이 막힌다는 것을 봤다. 나눗셈이 필요한 순간은 많다. 큰 조합 수를 소수로 나눈 나머지를 구할 때, 암호에서 서명을 검증할 때, 오류 정정 부호에서 방정식을 풀 때다.

“역수를 곱하는 것” 이 나눗셈이라면, 나머지 세계의 역수가 모듈러 역원이다. 그리고 공개키 암호 RSA 는 “공개 지수 e 와 비밀 지수 d 가 서로 모듈러 역원” 이라는 한 줄로 요약된다. 이 글이 끝나면 그 한 줄이 왜 복호화를 보장하는지 증명할 수 있다.

핵심 개념

모듈러 역원

a·x ≡ 1 (mod n) 을 만족하는 x 를 a 의 법 n 에 대한 역원이라 하고 a⁻¹ 로 쓴다.

정리. a 의 법 n 역원이 존재할 필요충분조건은 gcd(a, n) = 1 이다. 존재하면 법 n 에 대해 유일하다.

증명. (⇐) gcd(a, n) = 1 이면 베주 항등식에 따라 ax + ny = 1 인 정수 x, y 가 있다. 양변을 법 n 으로 보면 ax ≡ 1 이다. (⇒) ax ≡ 1 이면 ax − 1 = ny 인 y 가 있으므로 ax − ny = 1 이다. gcd(a, n) 은 좌변을 나누므로 1 을 나누고, 따라서 1 이다. 유일성: x, x’ 이 모두 역원이면 x ≡ x(ax’) = (xa)x’ ≡ x’ 이다. ∎

예: 법 10 에서 3 의 역원은 7 이다(3·7 = 21 ≡ 1). 2 는 역원이 없다. 2x 는 항상 짝수라서 10 으로 나눈 나머지가 1 이 될 수 없다.

n 이 소수 p 면 1, 2, …, p−1 모두 p 와 서로소이므로 0 이 아닌 모든 원소가 역원을 갖는다. 이때 {0, 1, …, p−1} 은 사칙연산이 자유로운 유한체 ℤₚ 가 된다. 타원곡선 암호, 리드-솔로몬 부호 같은 기술이 유한체 위에서 이뤄진다.

역원이 있으면 나눗셈과 소거가 된다

gcd(a, n) = 1 이면 ab ≡ ac (mod n) 에서 양변에 a⁻¹ 을 곱해 b ≡ c 를 얻는다. 지난 글의 2·3 ≡ 2·8 (mod 10) 이 실패한 이유는 gcd(2, 10) = 2 이기 때문이다.

같은 이유로 gcd(a, n) = 1 이면 x ↦ ax mod n 은 {0, …, n−1} 위의 전단사다. 005번 글에서 x ↦ 7x mod 10 이 전단사로 나온 것이 이 정리의 예다.

페르마 소정리

정리. p 가 소수이고 p 가 a 를 나누지 않으면 aᵖ⁻¹ ≡ 1 (mod p) 이다.

증명. 위의 전단사 성질에 따라 a·1, a·2, …, a·(p−1) 을 법 p 로 보면 1, 2, …, p−1 을 순서만 바꾼 것이다. 두 목록을 각각 모두 곱하면 aᵖ⁻¹ · (p−1)! ≡ (p−1)! (mod p). (p−1)! 은 p 와 서로소이므로 역원을 곱해 소거하면 aᵖ⁻¹ ≡ 1 이다. ∎

따름정리(역원 공식). 법이 소수 p 면 a⁻¹ ≡ aᵖ⁻² (mod p). aᵖ⁻² · a = aᵖ⁻¹ ≡ 1 이기 때문이다. 빠른 거듭제곱으로 O(log p) 번 곱하면 된다.

오일러 정리

법이 소수가 아니면 지수 p−1 대신 오일러 피 함수 φ(n) 을 쓴다. φ(n) 은 1 부터 n 까지에서 n 과 서로소인 수의 개수다.

  • p 가 소수면 φ(p) = p − 1
  • 서로 다른 소수 p, q 에 대해 φ(pq) = (p−1)(q−1)

정리(오일러). gcd(a, n) = 1 이면 a^φ(n) ≡ 1 (mod n). 증명은 페르마 소정리와 같은 방식으로, 1…n−1 대신 n 과 서로소인 수들만 곱하면 된다.

RSA 가 동작하는 이유

교과서식 RSA 의 뼈대는 다음과 같다.

1. 큰 소수 p, q 를 고르고 n = pq, φ(n) = (p−1)(q−1)
2. gcd(e, φ(n)) = 1 인 공개 지수 e 를 고른다
3. 비밀 지수 d = e⁻¹ mod φ(n)          ← 확장 유클리드
4. 암호화 c = mᵉ mod n,  복호화 m = cᵈ mod n

복호화가 맞는 이유: ed ≡ 1 (mod φ(n)) 이므로 ed = 1 + kφ(n) 이다. gcd(m, n) = 1 이면 오일러 정리로

cᵈ ≡ m^(ed) = m · (m^φ(n))ᵏ ≡ m · 1ᵏ = m   (mod n)

(gcd(m, n) ≠ 1 인 경우도 중국인의 나머지 정리를 쓰면 성립한다.) 실제 표준인 PKCS #1 은 φ(n) 대신 그 약수인 카마이클 함수 λ(n) = lcm(p−1, q−1) 을 쓰고, ed ≡ 1 (mod λ(n)) 을 요구한다(RFC 8017, 3.2절). 원리는 같다. 또 실제 RSA 는 패딩(OAEP, PSS) 없이 쓰면 안전하지 않다. 아래 예제는 원리 확인용이다.

페르마 판정법과 그 한계

페르마 소정리의 대우는 “어떤 a 에 대해 aⁿ⁻¹ ≢ 1 (mod n) 이면 n 은 합성수다” 다. 이것으로 큰 수가 합성수임을 빠르게 증명할 수 있다. 하지만 역은 성립하지 않는다. 561 = 3·11·17 은 561 과 서로소인 모든 a 에 대해 a⁵⁶⁰ ≡ 1 을 만족하는 합성수(카마이클 수)다. 그래서 실무에서는 페르마 판정을 강화한 밀러-라빈 판정법을 쓴다. NIST 의 디지털 서명 표준 FIPS 186-5 는 RSA 키 생성에 쓰는 밀러-라빈 판정 절차를 부록으로 규정한다(NIST FIPS 186-5).

직접 해 보기

역원을 세 가지 방법(확장 유클리드, 페르마, 파이썬 내장 pow(a, -1, n))으로 구해 비교하고, 작은 RSA 를 돌려 본다. 파이썬 3.8 부터 pow 의 지수에 음수를 주면 모듈러 역원을 계산한다고 공식 문서에 적혀 있다.

import math

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def inverse(a, n):
    g, x, _ = ext_gcd(a, n)
    if g != 1:
        raise ValueError(f"{a} 는 법 {n} 에서 역원이 없다 (gcd={g})")
    return x % n

p = 1_000_000_007
a = 123456789
print(inverse(a, p), pow(a, p - 2, p), pow(a, -1, p))
print(inverse(3, 10))
try:
    inverse(2, 10)
except ValueError as e:
    print(e)

# 장난감 RSA (원리 확인용, 실제로 쓰면 안 된다)
P, Q = 61, 53
n, phi = P * Q, (P - 1) * (Q - 1)
e = 17
d = pow(e, -1, phi)
m = 65
c = pow(m, e, n)
print(n, phi, d, c, pow(c, d, n))

# 페르마 판정법을 속이는 카마이클 수 561
fooled = all(pow(b, 560, 561) == 1 for b in range(2, 561) if math.gcd(b, 561) == 1)
print(561, "= 3*11*17, 페르마 판정 통과:", fooled)

실행 결과다.

18633540 18633540 18633540
7
2 는 법 10 에서 역원이 없다 (gcd=2)
3233 3120 2753 2790 65
561 = 3*11*17, 페르마 판정 통과: True

세 방법이 같은 역원을 낸다. 장난감 RSA 에서 65 를 암호화한 2790 을 복호화하면 65 가 돌아온다.

현업에서는

  • TLS 와 인증서. HTTPS 연결에서 RSA 서명을 검증할 때마다 이 글의 모듈러 거듭제곱이 실행된다. RSA 공개 지수는 흔히 65537 을 쓴다. 이진수로 1 이 두 개뿐이라 빠른 거듭제곱의 곱셈 횟수가 적기 때문이다.
  • 타원곡선과 디피-헬먼. X25519 같은 키 교환은 소수 2²⁵⁵ − 19 를 법으로 하는 유한체 위에서 계산하며, 마지막 나눗셈을 z^(p−2) 를 곱하는 페르마 방식 역원으로 계산하도록 의사코드에 적혀 있다(RFC 7748, Elliptic Curves for Security).
  • 경쟁 프로그래밍과 조합 계산. “답을 10⁹ + 7 로 나눈 나머지를 출력하라” 는 문제에서 C(n, r) = n! / (r!(n−r)!) 을 계산하려면 분모의 역원이 필요하다. 10⁹ + 7 이 소수이므로 페르마 역원을 쓴다.
  • 직접 구현하지 않는다. 실무 암호는 상수 시간 구현, 부채널 공격 방어, 패딩이 필요하다. 원리를 이해하는 것과 직접 구현해 배포하는 것은 다른 일이다. 검증된 라이브러리를 쓴다.

확인 문제

  1. 법 11 에서 4 의 역원을 구하라.
  2. 법 12 에서 역원이 존재하는 원소를 모두 나열하라. 몇 개인가?
  3. 3¹⁰⁰ mod 7 을 페르마 소정리로 구하라.
  4. 장난감 RSA 에서 p = 5, q = 11, e = 3 일 때 d 를 구하라.

풀이

  1. 4·3 = 12 ≡ 1 이므로 3.
  2. 1, 5, 7, 11 의 4 개. φ(12) = 4 와 일치한다.
  3. 3⁶ ≡ 1 (mod 7) 이고 100 = 6·16 + 4 이므로 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4.
  4. φ = 4·10 = 40, 3d ≡ 1 (mod 40) 에서 d = 27 (3·27 = 81 = 2·40 + 1).

더 읽을거리 (References)