지난 글에서는 RSA를 이해하기 위해 여러 수학 개념을 살펴봤습니다.
이제 아래와 같은 RSA의 구조가 어느 정도 이해가 될 것입니다. (아마도)

RSA 전체 과정이 이해가 안 되신다면, 먼저 아래 글을 읽어주세요.
RSA를 이해하기 위한 수학 개념

1. 큰 소수 p와 q를 생성
n = p x q
φ(n) = (p - 1)(q - 1)

2. 공개키 e를 생성
e는 φ(n)과 서로소 관계
d = e^-1 mod φ(n)
=> d는 e의 '모듈러 역원'

공개키: (e, n)
비밀키: (d, n)

암호화: c = m^e mod n
복호화: m = c^d mod n

그런데 여기서 문제가 하나 남았습니다.
우리는 분명 d는 e의 모듈러 역원이라고 배웠습니다.

그럼 그 모듈러 역원을 어떻게 구할까요?
아직 우리는 단순히 “역원이다”라고 말만했지 계산하는 방법을 모릅니다.

이번 글에서 이 모듈러 역원을 구하기 위해 반드시 필요한 알고리즘인
유클리드 알고리즘(Euclidean Algorithm)과
확장 유클리드 알고리즘(Extended Euclidean Algorithm)을 다뤄 보겠습니다.

❓ 왜 유클리드 알고리즘이 사용될까?

당장은 아래 내용이 이해가 안가도 괜찮습니다.

RSA의 개인키인 d는 아래의 조건을 만족해야 합니다.

e = 공개키 지수
φ(n) = 매우 큰 두 소수 p * q와 1사이의 서로소인 수의 개수

gcd(e, φ(n)) = 1
e * d = 1 mod (φ(n))

즉, 아래의 수식을 만족하는 d와 k가 존재한다는 뜻입니다.

e * d + φ(n) * k = 1

그리고 위 식을 일반화 하자면 아래와 같습니다.

e d + φ(n) k = gcd(e, φ(n))
a x + b y = gcd(a, b)

따라서,
두 수 a와 b의 최대공약수(gcd)를 구하는 과정에서
x와 y를 계산할 수 있다면, RSA 비밀키 지수인 d를 구할 수 있는 것입니다.

여기에서 필요한 것이 바로 유클리드 알고리즘과,
이를 응용한 확장 유클리드 알고리즘입니다.

🔎 유클리드 알고리즘이란?

유클리드 알고리즘은 사실 굉장히 간단합니다.

두 수 a, b의 최대공약수(gcd)는
a = bq + r 에서 r(나머지)와 b의 최대공약수와 같다.

즉 아래의 식이 성립한다는 의미입니다.

a > b
a = b * q + r
gcd(a, b) = gcd(b, r)

한번 예시를 들어보겠습니다. a를 32, b를 12라고 가정하겠습니다.
여기서 a를 b로 나눈 나머지를 구해보면 아래와 같습니다.

a = 32, b = 12
32 = 12 * 2 + 8

즉, 유클리드 알고리즘에 따르면,
8과 12의 gcd와 32와 12의 gcd는 같다는 결론에 이릅니다.

gcd(32, 12) = gcd(12, 8)

🤔 왜?

유클리드 알고리즘으로 gcd를 찾을 수 있다는 점은 알았습니다.
그런데 이게 왜 가능할까요?

공통의 약수를 가진 어떤 수 a와 b가 있고,
a는 b보다 크다고 가정하겠습니다.

a > b

그렇다면 a를 아래와 같이 나타낼 수 있습니다.

a = b * q(몫) + r(나머지)

또 하나의 식을 만들어 보면,
a와 b의 공약수가 d라고 했을 때,
아래와 같이 나타낼 수도 있습니다.

a = x * d(공약수)
b = y * d(공약수)

이 두 식을 이용해 변형하면
아래와 같아집니다.

a = b * q(몫) + r(나머지)
a = x * d(공약수)
b = y * d(공약수)

r = a - b * q
r = (x * d) - (y * d * q)
r = d * (x - yq)

즉 나머지인 r 역시 a와 b의 공약수인 d의 배수가 되는 셈입니다.
따라서 a와 b의 gcd는 b와 r의 gcd와 같습니다.

이번에도 예시를 한번 들어보겠습니다.

a = 30
b = 16

a가 30이고 b가 16이고,
a가 b보다 크다는 조건입니다.

a = b * q(몫) + r(나머지)

30 = 16 * 1 + 14

a를 b로 나눴을 때,
몫은 1이고, 나머지는 14가 됩니다.
이제 위에서 정의한 식을 따라가보겠습니다.

r = a - b * q
r = (x * d) - (y * d * q)
r = d * (x - yq)

14 = 30 - 16 * 1
14 = (x * d) - (y * d * 1)
14 = xd - yd
14 = d(x - y)

자 a와 b의 공약수인 d는 2입니다.
이걸 수식에 포함시켜 보겠습니다.

a = 30
b = 16

a = x * 2
b = y * 2
x = 15
y = 8

x와 y를 구했으니 식에 대입해 보겠습니다.

14 = d(x - y)

14 = d(15 - 8)
14 = d * 7
d = 2

단편적인 예시지만,
이걸 통해서 알 수 있는 점은
r(나머지) 역시 d(공약수)의 배수이므로,
공약수 d는 그대로 유지된다는 것입니다.

따라서 a와 b의 gcd는 b와 r의 gcd와 같습니다.

즉,
gcd를 구하는 과정에서 r을 계속 계산하며 나머지를 줄여가다 보면,
결국 r이 0이 되었을 때 그 직전 r의 값이 바로 gcd가 됩니다.

✅ 유클리드 알고리즘의 사용

이론적인 내용을 알았으니
조금 큰 수를 이용해 한번 gcd를 찾아 보겠습니다.
그 전에,
위에서 정의한 유클리드 알고리즘의 식을 조금 일반화 해보겠습니다.

a > b

a = b * q1 + r1
b = r1 * q2 + r2
r1 = r2 * q3 + r3
r2 = r3 * q4 + r4
...
rn-1 = rn * q(n+1) + 0

복잡해 보이지만 사실 간단합니다.
큰 수를 작은 수로 나누고,
그 나머지를 다시 반복해서 나누는 과정을 나타낸 것입니다.

첫 번째 줄은 가장 큰 수 a를 두 번째 수 b로 나눈 것입니다.

a = b * q1 + r1

두 번째 줄은, 이전 단계의 나머지 r1으로 앞의 b를 다시 나누는 과정입니다.

b = r1 * q2 + r2

이런 방식으로 나머지가 0이 될 때까지 계속 반복합니다.
나머지가 0이 되었을 때 직전의 나머지 값이 바로 최대공약수입니다.

r1 = r2 * q3 + r3
r2 = r3 * q4 + r4
...
rn-1 = rn * q(n+1) + 0

gcd(a, b) = rn-1

자 그럼 이제 한번 유클리드 알고리즘을 사용해 보겠습니다.
a는 391, b는 299로 예시를 들어 보겠습니다.

a = 391
b = 299

391 = 299 * 1 + 92
299 = 92 * 3 + 23
92 = 23 * 4 + 0

gcd(391, 299) = 23

생각보다 간단하게 나옵니다.
자 이제 여기서 확장 유클리드 알고리즘으로 나아가 보겠습니다,
확장 유클리드 알고리즘을 이용하면,
391x + 299y = 23 형태의 x, y 를 구할 수 있고,
그 점을 이용해 RSA의 비밀키 지수인 d를 만들어낼 수 있습니다.

🏗️ 확장 유클리드 알고리즘이란?

여기까지는 최대공약수를 구하는 과정이었습니다.
하지만 RSA에서는 gcd(e, φ(n)) = 1인 경우,
즉 아래 방정식을 만족하는 d를 찾아야 합니다.

e * d + φ(n) * k = 1

사실 이 문제는 곧 ax + by = gcd(a, b) 문제와 동일하며,
유클리드 알고리즘을 거꾸로 추적하면 x와 y를 구할 수 있습니다.

이 과정이 바로 확장 유클리드 알고리즘입니다.

🔥 확장 유클리드 알고리즘의 원리

확장 유클리드 알고리즘은
앞서 나온 나머지 관계를 거꾸로 대입해 올라가면서,
각 단계별로 a와 b의 형태로 식을 변환합니다.

예시로 gcd(99, 78)를 이용해 보겠습니다.
99와 78의 최대공약수를 찾는 식은 다음과 같습니다.

99 = 78 * 1 + 21
78 = 21 * 3 + 15
21 = 15 * 1 + 6
15 = 6 * 2 + 3
6  = 3 * 2 + 0

gcd(99, 78) = 3

자 여기서 우리의 목표는
99의 78에 대한 모듈러 역원입니다.

마지막 두 개의 식을 이용해보겠습니다.

6 = 21 - 15 * 1
3 = 15 - 6  * 2

여기서 6에 대한 식을 대입하면 아래와 같아집니다.

3 = 15 - (21 - 15 * 1) * 2
3 = 15 * 3 - 21 * 2

여기서 우리의 목표는 3 = ax + by 형식으로 변경하는 것입니다.
우선 3을 15와 6으로만 표현해 봅시다.

3 = 15 - 6 * 2

여기서 6에 위 식 6 = 21 - 15 * 1으로 대입합니다.

3 = 15 - (21 - 15 * 1) * 2
3 = 15 - 2*21 + 2*15
3 = 3*15 - 2*21

자 이제 3을 15와 21로 표현하는 것에 성공했습니다.
한단계 더 올라가서 21과 78로 나타내기 위해
15를 21과 78로 표현해 봅시다.

78 = 21 * 3 + 15
15 = 78 - 21 * 3

3 = 3*15 - 2*21

3 = 3*(78 - 21*3) - 2*21
3 = 3*78 - 9*21 - 2*21
3 = 3*78 - 11*21

같은 방식으로 최종적으로 대입을 하면,
99와 78의 계수를 알 수 있습니다.

3 = 99 * (-11) + 78 * (14)

자 이제 모듈러 역원은 어떻게 얻을까요?

3 = 99 * (-11) + 78 * 14

우리가 얻은 식을 mod 78로 보면
78 * 14는 78의 배수이기 때문에 0이 됩니다.

3 ≡ 99 * (-11)  (mod 78)

그런데 모듈러 역원은 mod 연산을 했을 때
1이 나와야 한다고 했었습니다.

지금은 mod 연산을 했을때의 값이 3이기 때문에
이 값들은 모듈러 역원이 없다고 할 수 있습니다.

• gcd(99,78) = 3 이므로 mod 78에서 99는 역원은 존재하지 않는다.
• 모듈러 역원이 존재하려면 반드시 gcd = 1이어야 한다.

99 * -11 ≡ 3 (mod 78)

여기서 중요한 것을 알 수 있습니다.
바로 RSA 공개키의 조건의 이유입니다.

지난 글에서 RSA 공개키를 이야기할때,
e와 φ(n)가 서로소 관계여야만 한다고 했습니다.

즉,
e와 φ(n)의 gcd(최대공약수)가 1이어야만
RSA가 정상적으로 작동합니다.

RSA 비밀키를 만들기 위해서는 e*d + φ(n)*k = 1 수식이 성립해야만 하고,
그래야만 e*d ≡ 1 (mod φ(n))이 공식이 성립하고,
그래야만 공개키 e에 대한 모듈러 역원인 d를 구할 수 있습니다.

RSA에 대한 설명이 이해가 안가신다면 아래 글을 읽어주세요
RSA를 이해하기 위한 수학 개념

✅ 작은 수로 보는 모듈러 역원

위에서 본 예시는 gcd(99, 78) = 3이라
모듈러 역원이 존재하지 않는 경우였습니다.

이번에는 실제 gcd = 1인 경우를 예로 들어,
확장 유클리드 알고리즘으로 진짜 모듈러 역원을 구해보겠습니다.

예를 들어 아래와 같은 상황을 생각해 봅시다.

• φ(n) = 40
• e(공개키 지수) = 7
• d(개인키 지수) = 7⁻¹ mod 40

우리가 원하는 것은 아래의 식입니다.
즉 e(공개키)의 모듈러 역원인 d(개인키)를 구하는 것입니다.

7 * d ≡ 1 (mod 40)

위 식을 정수형식으로 바꿔보면 아래와 같이 표현할 수 있습니다.

7 * d + 40 * k(아무 정수) = 1

먼저 위에서 배운 유클리드 알고리즘으로 gcd(40, 7)을 구해보겠습니다.

40 = 7 * 5 + 5
7  = 5 * 1 + 2
5  = 2 * 2 + 1
2  = 1 * 2 + 0

gcd(7, 40) = 1

gcd가 1이니 이 예시는 모듈러 역원이 존재한다는 것을 알 수 있습니다.
이제부터 이 식을 거꾸로 올라가며,
1을 7과 40의 조합으로 표현해 보겠습니다.

나머지가 0인 식을 제외하고,
제일 마지막 식부터 시작합니다.

5 = 2 * 2 + 1
1 = 5 - 2 * 2

2를 한 단계 위의 식에서 가져옵니다.

7 = 5 * 1 + 2
2 = 7 - 5 * 1

1을 5와 2로 나타낸 식에,
위에서 구한 2를 7과 5로 나타낸 식을 대입합니다.

1 = 5 - 2(여기에 대입) * 2
1 = 5 - (7 - 5 * 1) * 2
1 = 5 - 2 * 7 + 2 * 5
1 = 3 * 5 - 2 * 7

1을 5와 7로 나타내는 것에 성공했습니다.
이제 한 단계 위의 식에서 5를 가져올 차례입니다.

40 = 7 * 5 + 5
5 = 40 - 7 * 5

이번에도 5를 대입해 보겠습니다.

1 = 3 * 5(여기에 대입) - 2 * 7
1 = 3 * (40 - 7 * 5) - 2 * 7
1 = 3 * 40 - 15 * 7 - 2 * 7
1 = 3 * 40 - 17 * 7

자 1을 40과 7을 이용해서 표현한 식이 완성되었습니다.

1 = 3 * 40 - 17 * 7

즉,
X = -17이고,
Y = 3 입니다.

7 * -17 + 40 * 3 = 1

위의 식을 만족하기 때문에
우리가 원한 식인 7 * d ≡ 1 (mod 40)을 구할 수 있습니다.

7 * (-17) + 40 * 3 = 1
7 * -17 ≡ 1 (mod 40)

즉 7의 mod 40에 대한 모듈러 역원은 -17이며,
이건 다시말해 23으로도 말 할 수있습니다.

7 * 23 = 161
161 mod 40 = 1

7의 40에 대한 모듈러 역원은 23이다.
7^-1 mod 40 = 23

mod 40의 세계에서는 사실상 같은 값
d ≡ -17 mod (40)
d ≡ 23 mod (40) << 표현이 가장 간단하고 직관적이라 쓰입니다.
d ≡ 63 mod (40)

정리하자면,
확장 유클리드 알고리즘으로 1 = 7x + 40y 꼴을 만들고
그때의 x가 곧 7^-1 mod 40이 됩니다.
이 d = 23이 바로, e = 7, φ(n) = 40인 RSA에서의 비밀키 지수 d 역할을 하게 됩니다.

👓 (확장) 유클리드 알고리즘 with Python

지금까지는 식만 가지고 손으로 계산해 봤습니다.
실제로 구현 단계에서는 유클리드 + 확장 유클리드를 다음처럼 정리해서 기억하면 됩니다.

1. 유클리드 알고리즘으로 gcd(a, b)를 구한다.
2. 재귀(혹은 반복문)를 이용해 각 단계마다 x, y를 함께 갱신한다.
3. 최종적으로 a * x + b * y = gcd(a, b)를 만족하는 (x, y, gcd)를 얻는다.
4. 만약 gcd(a, n) = 1이라면, x가 바로 a^-1 mod n이 된다.

def extended_euclidean(a, b):
    # 확장 유클리드 알고리즘
    # a * x + b * y = gcd(a, b)를 만족하는 (x, y, gcd)를 반환한다.

    if b == 0:
        # b == 0이면, 최대공약수는 찾은 상태
        return 1, 0, a

    x1, y1, g = extended_euclidean(b, a % b)
    # a = b * q + r  =>  r = a - b * q
    # (g = b * x1 + (a % b) * y1)를
    # (g = a * x + b * y) 형태로 바꾸는 과정
    x = y1
    y = x1 - (a // b) * y1

    return x, y, g

def modinv(a, n):
    # a의 n에 대한 모듈러 역원 a^-1 mod n을 구하는 함수
    x, y, g = extended_euclidean(a, n)

    # gcd(a, n) != 1 이면 역원이 존재하지 않음
    if g != 1:
        raise ValueError("역원이 존재하지 않습니다: gcd(a, n) != 1")
    # x가 음수일 수도 있으니,
    # mod n을 통해 항상 `0 <= d < n` 범위로 맞춰준다.
    return x % n

def main():
    e = 7
    phi_n = 40

    d = modinv(e, phi_n)
    print(f"{e}의 {phi_n}에 대한 모듈러 역원은 {d}입니다.")


if __name__ == "__main__":
    main()

😑 마치며

이 글을 쓰는 데 생각보다 많은 시간이 들어서 조금 당황했습니다.
머리로는 이해했다고 생각했던 내용도, 막상 글로 정리하려고 하니
부족한 부분이 계속 드러나더군요.

그래도 이번 글을 쓰면서 RSA의 핵심 개념인
비밀키 d를 어떻게 구하는가를 확실히 정리할 수 있었습니다.

다음 편에서는 드디어 이 수학들을 실제 코드로 옮겨
RSA를 직접 구현해보겠습니다.

읽다가 틀린 부분이나 잘못된 내용이 있다면
댓글로 지적해 주시면 감사하겠습니다.