RSA는 겉보기에는 공식이 많고 복잡해 보이지만,
막상 몇 가지의 수학적 개념을 공부하면 전체 구조가 이해가 가게 됩니다.

이번 글에서 제가 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

처음에 저 수식을 보고 든 생각은 "저게 대체 뭐지? "였습니다.
막상 내용을 이해하고 보면 쉽지는 않아도, 이해는 가능하니 걱정하지 마세요

아래는 위 수식에서 나온 수학 용어들의 설명이지만
굳이 안봐도 뒤에서 설명할 예정입니다.

φ(n): 1부터 n까지의 자연수 중에서, n과 서로소인 수의 개수
ex)
n = 10
1~10 중 10과 서로소: 1, 3, 7, 9
φ(10) = 4

x^y: x의 y제곱
ex) 2^3 = 8

x mod y: x를 y로 나눈 나머지
ex) 10 mod 3 = 1

모듈러 역원: a에 어떤 수 x를 곱해서 m으로 나눈 나머지가 1이 되게 하는 x
ex)
a * x ≡ 1 (mod n)
x는 a의 역원

서로소: 최대공약수가 1인 관계
ex) 3과 4은 서로소 관계

소수: 1과 자기자신 외의 나누어떨어지는 수가 없는 수
ex) 1, 3, 5, 7, 11 ...

❓ 의문점

여기서 부터는 제가 처음 RSA 수식을 보면서
느꼈던 의문들과 제가 찾은 답입니다.

🙄p와 q는 왜 소수여야 하나요?

저는 처음에 이렇게 생각했습니다.

그냥 아무 두 수를 곱해서 n으로 만들어 쓰면 안되는건가요?

하지만 실제로는 소수 두 개의 곱이기에 아래 공식이 성립합니다.

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

이 공식이 RSA의 핵심이며,
RSA는 이 공식이 성립해야 정상적으로 동작합니다.

✏️ φ(n)이 뭐에요?

φ(n)은 다음을 의미합니다.

1부터 n-1 사이에서 n과 서로소인 정수의 개수

여기서 서로소란 최대공약수가 1뿐인 관계라는 뜻입니다.
예를들어 2와 3, 4와 7 등 1 외에는 같은 약수가 없는 관계를 의미하죠.

자 소수는 1과 자기자신외에는 약수가 없다고 했습니다.
그렇다면 소수에서 1을빼면 그 숫자가 바로
1과 소수 사이의 서로소 관계인 숫자의 개수가 됩니다.

즉 φ(p) = (p - 1)이 되고, φ(q) = (q - 1)이 됩니다.

n이 서로 다른 소수인 p와 q의 곱이기에
φ(p * q) = (p - 1) * (q - 1)이 성립하게 되는거죠

ex)
p = 3
q = 7
n = 21

φ(n) = 2 * 6 = 12

p의 서로소 (3 - 1)
1, 2

q의 서로소 (7 - 1)
1, 2, 3, 4, 5, 6

n의 서로소 ((3 - 1) * (7 - 1))
1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20

😵‍💫 알듯 말듯 헷갈려요...

네 제가 그랬습니다. p와 q가 소수라서 서로소가 -1한 값인건 알겠어요.
근데 φ(p * q) = (p - 1) * (q - 1)가 왜 성립하는지 이해가 안갔습니다.

수식으로 한번 써보겠습니다.

p = 3
q = 7
n = 21
φ(n) = 2 * 6 = 12

n은 서로 다른 소수인 p와 q의 곱셈입니다.
그렇다면 n의 약수는 p의 배수 혹은 q의 배수라고 생각할 수 있습니다.

그렇다면 n - 1에서 p의 배수와 q의 배수의 개수를 각각 구한 뒤,
n - 1에서 빼주면 n과 서로소 관계인 수의 개수가 나오지 않을까요?

20 / 3 = 6
20 / 7 = 2
20 - 6 - 2 = 12

이걸 수식으로 표현해 보면
n - 1에서 p와 q의 배수는 아래와 같습니다.

(p * q - 1) / p = q - (1 / p)
(p * q - 1) / q = p - (1 / q)

여기서 한가지 생각해야 할 점은
우리는 서로소인 "정수"의 개수를 세는것입니다.
따라서 6.99나 6이나 서로소인 정수의 개수는 같다는 점을 이용해
아래와 같이 수식을 간략화 할 수 있습니다.

q - (1 / p) ≈ q - 1
p - (1 / q) ≈ p - 1

※
≈는 근삿값을 의미하며
대충 비슷한 값이라는 뜻입니다.

🔑 공개키 e와 비밀키 d는 어떻게 생성되나요?

RSA의 또 하나의 핵심 조건은 이것입니다.

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

이건 뭘까요?
공개키인 e와 비밀키인 d를 곱한 다음,
φ(n)으로 나눈 나머지가 1이 되어야 한다는 것입니다.

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

e * d = 1 + kφ(n)
k: 어떤 정수

이것을 d가 e의 모듈러 역원이다라고 합니다.

아까 처음에 RSA의 전체 구조를 살펴볼 때
아래와 같은 수식이 있었습니다.

m^e mod n = c
c^d mod n = m

m: 암호화할 메시지
c: 암호화된 메시지

즉 m이라는 메시지를 e만큼 제곱한다음 mod n을 했을때의 값이 바로
RSA에서 암호화된 메시지라는 의미입니다.

이 암호화된 메시지를 d만큼 제곱하고 mod n을 하면
다시 m이라는 암호화 이전의 메시지가 복구됩니다.
이런 수식이 성립하기 위한 조건이 바로 e와 d가 모듈러 역원이여야 한다는 점입니다.

📐 오일러 정의란

n과 m이 서로소일 때 n과 서로소인 숫자들을 모두 곱한 값은,
그 숫자들 각각에 m을 곱해서 (mod n) 후 다시 곱한 값과 같다.

이번엔 오일러 정의를 한번 살펴보겠습니다.
말로하면 너무 어려우니 예시를 들어볼게요

n = 10
m = 3

φ(10) = 4
1, 3, 7, 9

자 n과 m은 서로소 관계이고,
m이 n보다 작다는 조건을 만족합니다.

P = 1 * 3 * 7 * 9 = 189
P ≡ 9 (mod 10)

P에 mod 10을 한 결과는 9가 되네요
자 이제 m을 곱해보겠습니다.

1 * 3 = 3
3 * 3 = 9
7 * 3 = 21 mod 10 = 1
9 * 3 = 27 mod 10 = 7

신기하게도 mod 10을 한 결과는 {3, 9, 1, 7} 입니다.
위의 계산식과 순서만 달라졌을뿐 집합이 유지되는게 확인됩니다.

그렇다면 수식으로 이렇게도 됩니다.

Q = (1 * 3)(3 * 3)(7 * 3)(9 * 3)
Q = (1 * 3 * 7 * 9) * 3^4

그리고 여기서 mod 10을 하면 결과는 Q ≡ P가 됩니다.

P = 189 mod 10 = 9
Q = (189 * 81) mod 10 = 9 * 1 = 9
Q ≡ P (mod 10)
189 * 3^4 ≡ 189 (mod 10)

여기서 3^4는 위에서 정의한 m^φ(n)이고,
mod 10은 mod n입니다. 그렇다면 아래와 같은 수식을 얻을 수 있습니다.

189 * m^φ(n) ≡ 189 (mod n)
P * m^φ(n) ≡ P (mod n)

여기서 양쪽에 있는 P를 없애기 위해, P의 모듈러 역원을 곱해줍니다.
아까전에 역원을 곱하면 p*d ≡ 1 (mod n)이 된다고 했었죠?
P ≡ 9 (mod 10) 이고, 9 * 9 = 81 ≡ 1 (mod 10)이므로
P의 모듈러 역원은 9입니다.

따라서 양변에 9를 곱해줍니다.

P * m^φ(n) ≡ P (mod 10)

((189 * 9) * m^φ(n)) ≡ (189 * 9) (mod 10)

여기서 189 * 9 ≡ 1 (mod 10)이므로

(1 * m^φ(n)) ≡ 1 (mod 10)

m^φ(n) ≡ 1 (mod 10)

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

✅ 암호화와 복호화가 어떻게 되나요?

자 지금까지 위에서 수식들을 알아봤습니다.
이제 마지막으로 이 부분을 볼까요

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

지금까지 모듈러 역원도 배웠고, 오일러 정의도 배웠습니다.
그렇다면 이제 암호화와 복호화는 어떻게 하는걸까요

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

p = 5 (소수)
q = 11 (소수)
n = 55 (p * q)
e = 3 (공개키 지수)
d = 27 (비밀키 지수)
m = 13 (평문 메시지)

위에서 공부했던 조건들을 만족하는지 확인해보겠습니다.

p랑 q는 소수

n = p * q

φ(n) = (p-1)(q - 1) = 40

공개키 지수 e:
1 < e < φ(n)
1 < 3 < 40
e와 φ(n)가 서로소여야 함
gcd(3, 40) = 1

개인키 지수 d:
d는 e의 mod φ(n)에 대한 역원이여야 함
3 * 27 = 81 mod 40 = 1

메시지 m:
0 < m < n
0 < 13 < 55
m과 n은 서로소여야 함
gcd(13, 55) = 1

조건이 많기도하네요 모든 조건에 부합하는 숫자들로 설정했으니,
예시를 들어보겠습니다.

우선 암호화 입니다. 메시지 m을 암호화 해보겠습니다.

m^e mod n
13^3 mod 55
2197 mod 55 = 52

13이라는 숫자 메시지를 공개키로 암호화하니 52가 나왔습니다.
이제 개인키를 가지고 복호화를 해볼까요?

c^d mod n
52^27 mod 55
2.1482769967144679013436706816572e+46 mod 55
= 13

네... 13이 나옵니다.
근데 중간에 엄청 큰 수가 나오죠?
저는 계산기로 했지만 실제 컴퓨터는 빠른 거듭제곱 알고리즘을 사용합니다.

빠른 거듭제곱 알고리즘은 뒤에서 알아보고,
일단 복호화에 성공한걸 확인했습니다.

이제 RSA 알고리즘이 조금 감이 잡혔습니다.
하지만 아직 몇가지 궁금증이 남았습니다.

🤔 공개키 안전할까?

처음부터 궁금한게 있었습니다.

e와 n이 공개되어 있는데, 왜 d를 구할 수 없는 거지?

사실 제 생각보다 답은 간단했습니다.

• d를 구하려면 φ(n)이 필요합니다.
• φ(n)을 구하려면 p와 q를 알아야합니다.
• p와 q는 n을 소인수분해하면 얻을 수 있습니다.

뭐야? 그러면 p와 q를 소인수분해하면 공개키를 알 수 있다는 거네요? 네 그렇습니다. 이론적으로는 가능합니다.

하지만 문제는 p와 q의 조건이 매우 큰 서로 다른 소수라는 점입니다.
두 소수를 곱해 만들어진 n을 소인수분해하는 것은
현재의 기술로는 사실상 불가능한 일입니다.

예를 들어 2048비트 RSA 기준으로,
이를 소인수분해하려면
우주의 모든 컴퓨터를 동원해도 수십억 년 이상이 걸립니다.

결론은 RSA는 안전하다는 것이었습니다.

🔥 RSA는 매우 느리다던데요

RSA가 느리다는 말은 과장이 아닙니다.
비대칭키 암호는 기본적으로 큰 정수에 대한 거듭제곱을 반복하기 때문에,
연산 비용이 대칭키 암호(AES 등)에 비해 매우 큽니다.

그래서 RSA 같은 비대칭키는
서명 확인이나 대칭키 같은 작은 데이터를 암호화하는 용도로만 사용됩니다.
대량의 데이터를 그대로 RSA로 암호화하는 것은 비효율적입니다.
(데이터가 커질수록 n 값도 커져야 하기때문에 말도 안 되게 느려집니다.)

그럼에도 여전히 RSA를 사용하는 이유가 있습니다.
RSA는 공개키를 외부에 공개해도 안전하며,
상대방의 비밀키 없이 복호화할 방법이 없습니다.

즉, 통신을 시작할 때
신뢰할 수 있는 통신으로 대칭키를 교환하는 데 최적화되어 있기 때문에
초기 연결(handshake) 단계에서 여전히 RSA가 사용되고 있습니다.

💻 컴퓨터의 제곱 연산 방법

이 부분은 약간 외전(?)입니다.
RSA랑 연관이 있긴 하지만 수식보다는
빠르게 계산하는 방법에 속합니다.

RSA 계산의 핵심은 다음 형태의 연산입니다.

m^e mod n
c^d mod n

문제는 e가 매우 큰 수라는 것입니다.
예를 들어 e가 65537 정도만 되어도, 단순히 m * m * m ... 을 반복하는 방식은 전혀 현실적이지 않습니다.

그래서 RSA에서는 빠른 제곱(Fast Exponentiation) 또는
제곱 곱 알고리즘(Square-and-Multiply) 을 사용합니다.

이 알고리즘은 지수를 이진수로 보고, LSB부터 하나씩 처리하는 방식으로 계산량을 극적으로 줄입니다.

🧮 지수를 이진수로 보는 이유

예를 들어 7이라는 지수가 있다면:

7 = 0b0111

이진수 0111은 다음 수식과 같은 의미입니다.

7 = 1*2^0 + 1*2^1 + 1*2^2

지수의 이진 표현을 이용하면 m^7 을 이렇게 해석할 수 있습니다.

m^7 = m^(1 + 2 + 4)
m^7 = m^1 * m^2 * m^4

지수법칙을 적용해 지수를 이진수로 표현하면,
필요한 제곱들(m^1, m^2, m^4, m^8 ...)만 만들어서 곱하면 됩니다.

🔎 빠른 제곱 알고리즘 전체 흐름 살펴보기

알고리즘의 핵심은 두 가지 연산만 반복하는 것입니다.

• Square: 제곱하기 (base = base² mod n)
• Multiply: 필요할 때 result에 곱하기

초기값:
result = 1 (결과 합산)
base = m (메시지)
exp = e (지수를 2진수로)

순서:
1) exp의 LSB 확인 (LSB는 가장 작은 비트)
2) LSB == 1
=> result = (result * base) mod n
3) base = (base * base) mod n (항상 수행)
4) exp를 오른쪽으로 한 비트 이동
=> 비트 연산을 통해 LSB(가장 오른쪽 비트)를 버리고 한 칸씩 당김
ex) (0b1101 >> 1) = 0b110

이렇게만 보면 이해가 잘 안가니 예시를 들어보겠습니다.
4^7을 한번 계산해보겠습니다.

4^7
7 = 0b0111

계산을 시작하기 전 초기값은 이렇습니다.

result = 1
base = 4
exp = 0b0111

자 첫번째 계산을 합니다.
exp의 LSB가 1이네요 그럼 result에 base를 곱합니다.

result = 1 * 4 = 4
base = 4 * 4 = 16
exp = 0b0111 => 0b0011

두번재 계산을 해보겠습니다.
exp의 LSB가 이번에도 1이니 result에 base를 다시 곱합니다.

result = 4 * 16 = 64
base = 16 * 16 = 256
exp = 0b011 => 0b0001

자 세번재 계산을 합니다.
이번에도 LSB가 1이니 result에 base를 곱합니다.

result = 64 * 256 = 16384
base = 256 * 256 = 65536
exp = 0b0000

exp가 0이 되었으니 연산을 종료합니다.
최종적으로 결과가 16384가 나왔습니다.

❓ 이게 왜 빠르지?

제가 너무 작은수를 예시로 들어서 차이가 안보이지만
큰수를 계산할때는 비교도 안되게 빨라집니다.

4^7 (작은 수)
단순계산:
4 * 4 * 4... 6번

빠른 제곱 알고리즘:
3step
base 3번
result 3번
총 6번
---------------------------
4^1024 (큰 수)
단순계산:
4 * 4 * 4 ... 1023번

빠른 제곱 알고리즘:
base 11번
result 1번 (bit=1일 때만)
총 12번

즉, 단순 계산이 O(n) (지수의 크기만큼 반복) 이라면,
빠른 제곱 알고리즘은 O(log n) 시간에 계산할 수 있습니다.

또한 실제 RSA에서는 mod n을 매 단계 적용합니다.

base = (base * base) mod n
result = (result * base) mod n

이렇게 즉시 mod n을 적용하면 수가 너무 커지는 것을 방지할 수 있습니다.
특히 RSA에서는 2048비트 이상의 매우 큰 지수를 사용하기 때문에,
빠른 거듭제곱 알고리즘이 없다면 실제 암호화는 사실상 불가능했을 것입니다.

아래는 제가 파이썬으로 만든 빠른 제곱 알고리즘 예시 코드입니다.
스텝별로 어떤 연산이 일어나는지 로그를 출력하도록 구성했기 때문에
이 알고리즘이 실제로 어떻게 작동하는지 직관적으로 확인할 수 있습니다.

# 컴퓨터가 제곱을 하는 방식을 디버깅하기 위한 예제

def computer_pow(base, exp):
result = 1
step = 0

    while exp > 0:
        print(f"\n[STEP {step}] ----------------")
        print(f"exp (binary): {bin(exp)}")
        print(f"result: {result}")
        print(f"base:   {base}")

        # LSB가 1이면 실행
        if exp & 1:
            print(f"=> LSB = 1, result = {result} * {base}")
            result = result * base

        # base를 제곱
        print(f"=> base = {base} * {base}")
        base = base * base

        # exp의 비트를 오른쪽으로 이동
        exp >>= 1
        step += 1

    return result

def main():
num = input("형식) 3^7\n계산 식을 입력해주세요: ")
base = int(num.split('^')[0])
exp = int(num.split('^')[1])

    result = computer_pow(base, exp)
    print(f"{base}^{exp}의 결과는 {result}입니다.")

if __name__ == "__main__":
main()

🍷 정리하며

자료를 찾아보고 최대한 이해한 내용을 정리해보려 했지만,
쓰다 보니 생각보다 두서없이 흘러간 부분도 있었던 것 같습니다.
그래도 이번 글을 통해 RSA의 수학적 원리와 구조를 스스로 정리해볼 수 있었고,
이 과정에서 많은 개념들을 명확하게 정리할 수 있었습니다.

다음 글에서는 실제로 RSA를 구현해보며
오늘 다룬 개념들이 코드에서 어떻게 적용되는지 확인해보겠습니다.
이 글이 RSA를 이해하는 데 작게나마 도움이 되었기를 바랍니다.