Skip to content
Beside the Wheel

정수론부터 RSA까지

공부
RSA
암호화
정수론

RSA는 대표적인 비대칭 암호화 방식 중 하나이다.

RSA의 기반이 되는 정수론 개념과 암호화 원리를 알아보자.

군

RSA를 이해하기 위해선 우선 군(group)이 무엇인지 알아야 한다.
오늘날 RSA를 비롯한 많은 암호화 방식이 군론을 기반으로 한다. 개념은 어렵지 않다.

군이란, 아래 규칙에 맞게 원소의 집합과 연산(덧셈, 곱셈)을 정의한 것이다.

  • 닫힘: 집합 안의 두 원소를 연산했을 때, 그 결과가 군 안에 속해야 한다.
  • 결합법칙: 여러 원소에 대한 연산을 임의의 순서로 수행할 수 있다. (e.g. (a+b)+c = a+(b+c))
  • 항등원: 특정 원소와 항등원을 연산한 결과가 그 원소 자신이 되어야 한다. (e.g. a+0=a, 이 경우 항등원 0이 군 내에 존재함)
  • 역원: 두 원소를 연산한 결과가 항등원이 되는 특정 원소가 군 내에 존재한다. 그 원소를 역원이라 부른다. (e.g. a+(-a)=0, 이 경우 역원인 -a가 군에 존재함)

RSA에서 사용하는 군은 1, 2, 3, …, n-1 중에서 n과 서로소인 수들로 구성된 곱셈 군이다.

여기서 n을 모듈러스(modulus)라고 부르고, 군에 속한 원소의 개수를 군의 크기 또는 위수(order)라고 부른다. 특히 n과 서로소인 수의 개수를 φ(n)으로 표기하며, 이를 오일러 피 함수라고 한다.

예를 들어 n=5일 때, 5와 서로소인 수는 {1, 2, 3, 4}로 4개다. 따라서 φ(5) = 4이다.

양의 정수끼리 그냥 연산한 결과는 n보다 큰 수가 될 수 있으니, 군의 성질을 만족시키기 위해 연산을 모듈러 n으로 정의한다. 덧셈은 (a+b)%n, 곱셈은 (a*b)%n로 계산한다. 여기서 %는 모듈러 연산자이고 n으로 나눈 나머지값을 결과로 한다.

모듈러 역원

이렇게 모듈러 정수군에서 덧셈, 뺄셈, 곱셈을 쉽게 할 수 있다. 하지만 나눗셈을 하기 위해선 생각이 필요하다.

실수에서는 ÷ 2는 × 1/2와 같다. 하지만 정수군에는 1/2가 없으므로, 2를 나누는 대신 모듈러 곱셈에서의 역원을 곱해줄 수 있다.

예를 들어 mod 10에서, 3의 곱셈 역원은 7이다. 따라서 mod 10에서 어떤 수를 3으로 나누는 것은 7을 곱하는 것과 같다. 모듈러 연산에서의 곱셈 역원이므로, 모듈러 역원으로도 부른다.

3 × 7 = 21
21 % 10 = 1이기 때문


3 × 7 ≡ 1 (mod 10)
모듈러 결과가 같으면, 두 값이 합동이라고도 한다. 기호는 ≡

모듈러 역원의 존재 조건 (베주 항등식)

그런데 이 역원이 항상 존재하는 건 아니다. 쉬운 예로 mod 10에서 5를 생각해보면, 5에 어떤 수를 곱해도 결과가 일의 자리수가 1이 되는 경우는 없으니까 말이다.

만약 a에 대한 역원 x가 존재한다고 가정하면

  • ax ≡ 1 (mod m)
  • ax = 1 + my (어떤 정수 y에 대해)

이므로 ax - my = 1 가 성립해야 한다.

여기서 a와 m이 서로소이면 x와 y가 항상 존재한다. 왜냐하면..

  1. 집합 S = {ax + by > 0 | x, y는 정수}를 생각해보자.

    • S는 공집합이 아니다.
      • y=0, x=1이면: a×1 + b×0 = a
      • a가 양수면 그대로, 음수면 |a| (x=-1로 조정)
      • 따라서 S는 최소한 하나의 원소를 가진다.
    • S에 있는 가장 작은 원소를 d라고 부르자.

  2. a를 d로 나누면 몫 q와 나머지 r로 표현할 수 있다. (나머지 정리)

    a = dq + r  (0≤r<d)

    여기서 만약 r이 0보다 크다면

    r = a - dq
    = a - (as + bt)q
    = a(1-sq) + b(-tq)

    이므로 r도 S의 원소라는 뜻인데, r < d이므로 d가 최소원소라는 것에 모순된다.
    따라서 r = 0이어야 한다. 즉, a는 d로 나누어 떨어진다.
    같은 방법으로 b도 d로 나누어 떨어지는 것을 알 수 있다.

  3. d는 a와 b의 공약수이면서, d = as + bt이다.

    만약 다른 공약수 c가 있다고 하면, c에 어떤 정수 l이나 k를 곱한 것이 a, b와 각각 같을 것이다.

    • a = c × l
    • b = c × k

    따라서 이렇게 표현할 수 있다.

    d = as + bt
    = c×l×s + c×k×t
    = c × (l*s + k*t)

    즉, c는 d의 약수이다.
    모든 공약수 c는 d의 약수여야하므로 d는 가장 큰 공약수, 다시 말해 최대공약수(gcd)이다.

  4. 집합 S = {ax + by > 0 | x, y는 정수}의 가장 작은 원소 d는 a, b의 최대공약수이다.
    따라서 ax + by = gcd(a, b)를 성립하는 x, y는 항상 존재한다.
    (이 식을 베주 항등식 Bézout’s Identity 이라 부른다.)

이런 이유 때문이다.

이제 다시 모듈러 역원으로 돌아가자. a에 대한 역원 x가 존재한다고 가정하면, ax - my = 1을 만족하는 어떤 정수 y가 있어야 한다. a와 m이 서로소이면 (최대공약수가 1이면) ax - my = gcd(a, m) = 1을 성립하는 x, y가 항상 존재하므로, 역원도 항상 존재한다.

특히 m이 소수이면, 0이 아닌 모든 원소 a에 대해 m과 항상 서로소이므로, 모든 수에 대해 모듈러 역원이 존재한다.

모듈러 역원 찾는 법 (확장 유클리드 호제법)

만약 26의 모듈러 11에서의 역원을 구하려면, 26×x ≡ 1 (mod 11)을 만족하는 x를 찾아야 한다.

즉 26×x + 11×y = 1을 만족하는 정수 x, y를 찾아야 한다. 베주 항등식이 말해주는 건 이런 x, y가 존재한다는 것뿐, 구체적인 값은 알려주지 않는다.

그럼 모듈러 역원은 실제로 어떻게 찾을 수 있을까? 여기서 확장 유클리드 호제법이 필요하다.

확장 유클리드 알고리즘(Extended Euclidean Algorithm)은 유클리드 호제법을 수행하면서 베주 항등식의 x, y 를 함께 계산하는 방법이다.

a·x + b·y = g

유클리드 호제법에서 베주 항등식 찾기

유클리드 호제법의 과정을 보며 생각해보자.

a를 b로 나누면 몫 q와 나머지 r로 표현할 수 있다. 여기서 유클리드 호제법에 따라, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. (gcd(a, b) = gcd(b, r₀))

따라서 원래 문제 gcd(a, b)를 더 작은 문제 gcd(b, r₀)로 바꿀 수 있다.

a = bq₀ + r₀   (0 ≤ r₀ < b)
-> b = r₀q₁ + r₁   (0 ≤ r₁ < r₀)


a = bq₀ + r₀에서, a 위치에 b를 b 위치에 r₀을 대입한 것.
q₁와 r₁는 새로운 몫과 나머지이다.

gcd(b, r₀) = gcd(r₀, r₁)이므로 또 반복한다.

r₀ = r₁q₂ + r₂   (0 ≤ r₂ < r₁)

이 과정을 나머지가 0이 될 때까지 계속한다. 전체 과정을 나열하면 다음과 같다.

a = bq₀ + r₀
b = r₀q₁ + r₁
r₀ = r₁q₂ + r₂
⋯
r₍ₖ₋₂₎ = r₍ₖ₋₁₎qₖ + rₖ
r₍ₖ₋₁₎ = rₖq₍ₖ₊₁₎ + 0

각 단계는 단순히 나눗셈 정리를 적용한 것이고, 각 줄의 왼쪽 두 수가 다음 줄의 오른쪽 두 수가 되는 구조다. 마지막에 나온 나머지 rₖ 가 바로 gcd(a, b) = g 이다.

각 단계의 r을 기준으로 정리하면 as + bt 같이 정수 계수가 있는 a, b 두 항으로 나타낼 수 있는 식, 즉 선형 결합의 형태로 나타낼 수 있음을 알 수 있다.

r₀ = a - b·q₀


r₁ = b - r₀·q₁
   = b - (a - b·q₀)·q₁
   = b - a·q₁ + b·q₀·q₁
   = -q₁·a + (1 + q₀·q₁)·b


# r₀과 r₁이 a, b의 선형 결합이므로 이후 식도 선형 결합일 것
r₂ = r₀ - r₁·q₂
   ...
   = (1 + q₁·q₂)·a - (q₀ + q₂ + q₀·q₁·q₂)·b

따라서 모든 나머지 rᵢ는 항상 다음과 같이 쓸 수 있다:

rᵢ = sᵢ·a + tᵢ·b

마지막 단계의 나머지 rₖ가 gcd(a, b)이므로, 그때의 계수 sₖ와 tₖ가 바로 베주 항등식 a×x + b×y = gcd(a,b)의 해가 된다.

a×c ≡ 1 (mod n)을 만족하는 c를 찾는 것은 a×c - n×k = 1을 만족하는 정수 c, k를 찾는 것과 같다.

이는 베주 항등식 a×c + n×(-k) = 1과 똑같은 형태다. 따라서 a와 n이 서로소이면 확장 유클리드 호제법으로 이 식을 만족하는 c를 구할 수 있고, 이 c가 바로 a의 모듈러 n에서의 역원이다.

암호화의 아이디어

이제 우리는 모듈러 역원을 구할 수 있다. 이 도구를 어떻게 암호화에 활용할 수 있을까? 암호화에서 기본적으로 필요한 건, 메시지를 어떤 방법으로 변환하고 다시 역변환으로 돌릴 수 있어야 한다는 것이다.

여기서 모듈러 연산의 재밌는 성질 하나를 알아보자. mod 5에서 2를 계속 거듭제곱해보면:

2¹ mod 5 = 2
2² mod 5 = 4
2³ mod 5 = 3
2⁴ mod 5 = 1  ← 다시 1로
2⁵ mod 5 = 2  ← 처음부터 반복
2⁶ mod 5 = 4
... (반복)

신기하게도 2⁴ ≡ 1이 되고, 그 이후로는 같은 패턴이 반복된다.

왜 하필 4번일까? mod 5에서 곱셈 군은 {1, 2, 3, 4}로 이루어져 있다. 5와 서로소인 수가 4개다. 이 4를 군의 크기라 한다. 어떤 원소든 군의 크기만큼 거듭제곱하면 1로 돌아온다.

이 성질을 암호화에 활용해보자. 메시지 m을 거듭제곱해서 암호문을 만든다고 하면:

c = m^e mod n

이 암호문 c를 다시 원래 메시지 m으로 되돌리려면 어떻게 해야 할까? 다른 지수 d로 거듭제곱해서

c^d = (m^e)^d = m^(e·d) ≡ m (mod n)

가 되게 하면 된다.

위의 예시에서 보았듯이, 4번 거듭제곱하면 1이 된다. 따라서 e·d가 4k + 1 형태(k는 정수)라면

m^(e·d) = m^(4k+1) = (m^4)^k × m ≡ 1^k × m ≡ m

원래 메시지로 돌아온다!

정리하면, e·d ≡ 1 (mod 군의크기)가 되도록 d를 선택하면 암호화/복호화가 작동한다.
(왜 정확히 이게 작동하는지는 오일러 정리에서 다시 살펴보자.)

e·d ≡ 1 (mod 군의크기)를 만족하는 d는 e의 모듈러 역원이다. 앞에서 배운 확장 유클리드 호제법으로 구할 수 있다. 즉, 공개 지수 e와 군의 크기를 알면, 누구나 비밀 지수 d를 계산할 수 있다.

mod n에서 곱셈 군의 크기는 “n과 서로소인 수의 개수”이다. 예를 들어 n = 15일 때, 15와 서로소인 수는 {1, 2, 4, 7, 8, 11, 13, 14}로 8개다. 즉 군의 크기는 8이다.

RSA는 두 개의 큰 소수 p, q를 선택하고, 그 곱 n = p × q를 모듈러스로 사용한다. 이렇게 하면 n을 공개해도 안전하다. n을 알아도 p와 q를 찾는 것, 즉 소인수분해하는 것이 매우 어렵기 때문이다. p, q를 모르면 군의 크기를 계산할 수 없고, 따라서 d도 계산할 수 없다.

하지만 우리는 암호화 키를 만들려면 군의 크기를 알아야 한다. p, q를 알고 있는 사람만이 군의 크기를 계산할 수 있어야 하니까. 그렇다면 n = p × q일 때 군의 크기는 어떻게 계산할까?

군의 크기: 오일러 피 함수

앞 절에서 우리는 합성수 p × q를 사용하기로 했다. 이제 p와 q를 알 때 군의 크기를 계산하는 방법을 알아보자.

우선 곱셈 군이 무엇으로 이루어져 있는지 다시 생각해보자. mod n에서의 곱셈 군은 1부터 n-1까지의 수 중에서 n과 서로소인 수들의 집합이다. 곱셈 역원이 존재하려면 n과 서로소여야 하기 때문이다.

따라서 군의 크기는 n과 서로소인 수의 개수와 같다. 이 개수를 φ(n)이라 쓰고, 오일러 피 함수라 부른다.

예를 들어 n = 10일 때를 보자. 1부터 10까지 중 10과 서로소인 수는 1, 3, 7, 9이다. 따라서 φ(10) = 4이다.

n = 10일 때:
10과 서로소: {1, 3, 7, 9}
φ(10) = 4

n이 소수 p일 때는 간단하다. 1부터 p-1까지 모든 수가 p와 서로소이므로 φ(p) = p - 1이다. 이미 우리가 알고 있던 사실이다.

하지만 n이 합성수일 때는 어떨까? 특히 RSA에서 사용하는 n = p × q 형태일 때는?

직관적으로 생각해보자. n = p × q일 때, 1부터 n까지 중 n과 서로소가 아닌 수는 p의 배수이거나 q의 배수인 수들이다.

  • p의 배수: p, 2p, 3p, …, (q-1)p → q-1개 (pq는 제외)
  • q의 배수: q, 2q, 3q, …, (p-1)q → p-1개 (pq는 제외)
  • p와 q의 공배수: pq = n → 1개

p의 배수와 q의 배수는 겹치지 않는다 (p, q가 서로 다른 소수이므로). 따라서 n과 서로소가 아닌 수는 (q-1) + (p-1) + 1 = p + q - 1개이다. n과 서로소인 수는

φ(n) = n - (p + q - 1)
     = pq - p - q + 1
     = (p - 1)(q - 1)

이다. 깔끔하다!

더 엄밀하게 증명하면 이렇다.

우선 k가 mn과 서로소일 필요충분조건은 k가 m과도 서로소이고 n과도 서로소인 것이다. (공약수가 있다면 그 약수가 m이나 n의 약수이기도 할 것이므로)

여기서 중국인의 나머지 정리를 사용한다. 이 정리는 m과 n이 서로소일 때, 0 ≤ k < mn인 모든 정수 k가 순서쌍 (k mod m, k mod n)과 일대일 대응된다는 것이다.

왜 일대일 대응일까?

  • 유일성: 만약 k₁ ≡ k₂ (mod m)이고 k₁ ≡ k₂ (mod n)이면, k₁ - k₂는 m의 배수이면서 n의 배수다. m과 n이 서로소이므로 k₁ - k₂는 mn의 배수다. 따라서 0 ≤ k₁, k₂ < mn이면 k₁ = k₂다.

  • 존재성: 임의의 순서쌍 (a, b)에 대해 k ≡ a (mod m)이고 k ≡ b (mod n)을 만족하는 k가 항상 존재한다.

따라서 {0, 1, …, mn-1}의 원소들은 {0, 1, …, m-1} × {0, 1, …, n-1}의 순서쌍들과 정확히 일대일 대응된다.

이제 mn과 서로소인 k를 세어보자. k가 mn과 서로소 ↔ k가 m과 서로소이면서 n과도 서로소 ↔ (k mod m, k mod n)에서 양쪽 성분 모두 서로소

따라서 mn과 서로소인 k의 개수 = m과 서로소인 나머지 개수 × n과 서로소인 나머지 개수 = φ(m) × φ(n)

즉, φ(mn) = φ(m) × φ(n)이다.

이 곱셈적 성질로부터 바로 우리가 원하는 결과가 나온다.

φ(pq) = φ(p) × φ(q)
      = (p - 1) × (q - 1)

예를 들어 p = 61, q = 53이면

n = 61 × 53 = 3233
φ(n) = 60 × 52 = 3120

이다.

이 φ(n)이 바로 RSA의 핵심이다. n은 공개되지만, φ(n)은 비밀이다. φ(n)을 계산하려면 n을 p와 q로 소인수분해해야 하는데, 이게 매우 어렵기 때문이다.

오일러 정리

이제 아까 미뤄뒀던 질문으로 돌아가자. 왜 e·d ≡ 1 (mod φ(n))이면 m^(e·d) ≡ m이 될까?

18세기 수학자 오일러가 바로 이 질문에 답을 주었다. 그는 n과 서로소인 임의의 수 a에 대해

a^φ(n) ≡ 1 (mod n)

을 발견했다.

생각해보면 이것은 우리가 이미 본 패턴의 일반화다. mod 5에서 φ(5) = 4일 때 2⁴ ≡ 1 (mod 5)였던 것처럼, mod n에서 군의 크기가 φ(n)일 때는 a^φ(n) ≡ 1 (mod n)이 되는 것이다.

증명은 간단하다. n과 서로소인 모든 수 {a₁, a₂, …, a_φ(n)}을 생각하자. 이들에 각각 a를 곱하면 {a×a₁, a×a₂, …, a×a_φ(n)}이 되는데, 이것도 여전히 n과 서로소인 수들이고, 모두 서로 다르다. 따라서 두 집합은 같다. 순서만 다를 뿐이다.

양쪽을 모두 곱하면

a₁ × a₂ × ... × a_φ(n) ≡ a^φ(n) × (a₁ × a₂ × ... × a_φ(n)) (mod n)

좌변은 n과 서로소이므로 약분할 수 있고, a^φ(n) ≡ 1 (mod n)을 얻는다.

이 정리가 왜 중요할까?

a^φ(n) ≡ 1 이므로, 어떤 정수 k에 대해서도

a^(k·φ(n) + 1) ≡ a (mod n)

이 성립한다.

a^(k·φ(n) + 1) = (a^φ(n))^k × a ≡ 1^k × a ≡ a (mod n)

자, 이제 암호화로 돌아가자. 우리는 m^e로 암호화하고, c^d로 복호화하고 싶다. 그러려면

(m^e)^d = m^(e·d) ≡ m (mod n)

이어야 한다. 위의 오일러 정리를 쓰면, e·d = k·φ(n) + 1이 되게만 하면 된다!

다시 말해

e·d ≡ 1 (mod φ(n))

이면 된다. d는 e의 모듈러 φ(n)에서의 역원이다.

예를 들어 p = 61, q = 53이면 n = 3233이고 φ(n) = 3120이다. 공개 지수로 e = 17을 선택했다면, 비밀 지수 d는

17 · d ≡ 1 (mod 3120)

을 만족해야 한다. 확장 유클리드 호제법으로 계산하면 d = 2753이다.

검증해보자.

17 × 2753 = 46801 = 15 × 3120 + 1

따라서 임의의 메시지 m에 대해

(m^17)^2753 = m^(17×2753)
            = m^(15×3120 + 1)
            = (m^3120)^15 × m
            ≡ 1^15 × m
            ≡ m (mod 3233)

완벽하다!

이제 우리는

  • 공개 키: (e, n) = (17, 3233)
  • 개인 키: (d, n) = (2753, 3233)

를 가지게 되었다.

RSA

지금까지 우리가 배운 것을 되돌아보자.

군론으로 시작해서, 모듈러 역원과 베주 항등식으로 역원의 존재를 증명했다. 확장 유클리드 호제법으로 역원을 실제로 계산하는 법을 배웠다. 암호화의 기본 아이디어를 살펴보고, 소수 대신 합성수를 써야 하는 이유를 알았다. 오일러 피 함수로 합성수의 군 차수를 계산했고, 오일러 정리로 암호화와 복호화가 왜 작동하는지 증명했다.

음. 이제 모든 준비가 끝났다. RSA 암호화 시스템의 전체 과정을 정리해보자.

키 생성

앨리스가 키를 생성한다고 하자.

  1. 두 개의 큰 소수 p, q를 선택한다. (예: p = 61, q = 53)
  2. n = p × q를 계산한다. (n = 3233)
  3. φ(n) = (p-1) × (q-1)을 계산한다. (φ(n) = 3120)
  4. 1 < e < φ(n)이고 φ(n)과 서로소인 e를 선택한다. (e = 17)
  5. 확장 유클리드 호제법으로 e·d ≡ 1 (mod φ(n))인 d를 계산한다. (d = 2753)

이제 앨리스는

  • 공개 키: (e, n) = (17, 3233)
  • 개인 키: (d, n) = (2753, 3233)

를 가지게 된다. 공개 키는 모두에게 알려주고, 개인 키는 비밀로 보관한다. p, q, φ(n)은 안전하게 폐기한다.

암호화

밥이 앨리스에게 메시지 m = 42를 보내고 싶다면, 앨리스의 공개 키 (e, n)을 사용하여

c = m^e mod n
  = 42^17 mod 3233
  = 2557

을 계산하고, 이 암호문 c = 2557을 앨리스에게 전송한다.

복호화

앨리스는 자신의 개인 키 (d, n)을 사용하여

m = c^d mod n
  = 2557^2753 mod 3233
  = 42

를 계산하고, 원래 메시지 42를 복원한다.

위에서 증명했듯이

c^d = (m^e)^d = m^(e·d) = m^(k·φ(n)+1) ≡ m (mod n)

이기 때문에 성립한다.

보안의 원리

RSA의 보안은 소인수분해의 어려움에 기반한다. RSA에서 공개 키 (e, n)는 모두가 알고 있다. 개인 키 d를 계산하려면 φ(n)이 필요하고, φ(n) = (p-1)(q-1)을 계산하려면 n을 p와 q로 소인수분해해야 한다.

하지만 n이 충분히 크면 소인수분해는 사실상 불가능하다. 위의 예시에서 n = 3233은 작은 수라 쉽게 분해할 수 있지만, 실제 RSA에서는 n이 2048비트 이상이다. 이는 약 600자리 십진수이고, 현재 컴퓨터로는 연산에 수십 년이 걸린다.

반대로 p와 q를 알고 있으면 φ(n)을 즉시 계산할 수 있고, 확장 유클리드 호제법으로 d도 빠르게 구할 수 있다. 이것이 바로 RSA의 비대칭성이다.

실제 사용

실제로 RSA를 사용할 때는 몇 가지 주의사항이 있다.

키 크기는 최소 2048비트 이상이어야 한다. 보안이 중요한 경우 3072비트나 4096비트를 사용한다. 공개 지수 e는 보통 65537 = 2^16 + 1을 사용한다. 이진수로 10000000000000001이므로 분할 정복 거듭제곱이 효율적이다.

실제로는 평문을 직접 암호화하지 않고 OAEP같은 패딩을 사용한다. 이렇게 하면 같은 평문도 매번 다른 암호문으로 암호화된다.

RSA는 암호화 외에도 디지털 서명에도 사용된다. 개인 키로 서명을 만들고, 누구나 공개 키로 검증할 수 있다.

참고 자료

관련글
공부eBPF로 서버 성능 Profiling하는 법: Pyroscope의 구현 살펴보기공부Spot 인스턴스에서 서버 가용성 개선하기embeddingembedding and chunkingembedding임베딩llmCTMllmCurcuit Tracing