RSA 알고리즘 분석: 수학 배경부터 RSA-512 실습, 공격까지

한눈에 보기

• RSA는 키 쌍 하나로 암호화와 서명을 모두 하는 공개키 암호
  • 1977년 Rivest, Shamir, Adleman 발표
• 안전성의 근거는 소인수분해의 어려움
  • 큰 두 소수의 곱셈은 쉽고, 곱을 다시 두 소수로 나누기는 어려움
• 동작 원리는 정수론 세 가지면 충분
  • 나머지 연산, 오일러 정리, 중국인의 나머지 정리(CRT)
• 패딩 없는 RSA(흔히 “교과서 RSA”, textbook RSA)는 안전하지 않음
  • 같은 평문이 늘 같은 암호문이 됨
  • 암호문을 곱해 평문을 조작할 수 있음
  • 실제로는 무작위성과 검사용 구조를 더하는 OAEP(Optimal Asymmetric Encryption Padding)·PSS(Probabilistic Signature Scheme) 패딩과 함께 사용
• 지금 RSA의 주 용도는 서명
  • TLS(Transport Layer Security) 인증서, SSH(Secure Shell) 키, JWT(JSON Web Token), 코드 서명
  • 키교환은 TLS 1.3부터 RSA 키 전송 대신 ECDHE(Elliptic Curve Diffie–Hellman Ephemeral, 일회용 타원곡선 키교환)가 맡고, 지금은 ECDHE와 PQC(Post-Quantum Cryptography, 양자내성암호) 알고리즘 ML-KEM을 섞은 하이브리드로 전환 중
• RSA-512는 더 이상 안전하지 않음
  • 1999년 처음 분해, 지금은 클라우드에서 몇 시간이면 분해
  • 이 글의 RSA-512 예시는 원리 설명용

배경 지식

RSA 자체는 몇 줄짜리 식이지만, 제대로 이해하려면 세 가지 배경이 필요하다. 공개키 암호가 무엇을 풀려는 것인지, RSA 식이 왜 맞고 왜 깨기 어려운지 보여 주는 정수론, 그리고 수백 자리 수로 그 식을 실제로 계산하는 방법이다.

공개키 암호와 트랩도어 일방향 함수

대칭키 암호(예: AES, Advanced Encryption Standard)는 암호화와 복호화에 같은 키를 쓴다. 그래서 두 가지 문제가 남는다.

• 키 분배: 처음 만난 두 사람이 그 키를 어떻게 안전하게 나눠 갖는가.
• 전자서명: 같은 키를 가진 사람은 누구나 같은 값을 만들 수 있어서, “이 사람이 만들었다”를 제3자에게 증명할 수 없다.

1976년 Diffie와 Hellman은 “New Directions in Cryptography”에서 이 두 문제를 풀 방법으로 공개키 암호를 제안했다. 키를 둘로 나누는 것이다.

• 공개키: 누구에게나 알려 줘도 되는 키. 암호화와 서명 검증에 쓴다.
• 개인키: 주인만 갖는 키. 복호화와 서명 생성에 쓴다.

이게 가능하려면 트랩도어 일방향 함수(trapdoor one-way function)가 필요하다. 트랩도어 일방향 함수란 한 방향 계산은 쉽고, 거꾸로 계산하기는 어려운데, 비밀 정보(트랩도어)를 알면 거꾸로도 쉬워지는 함수를 뜻한다. Diffie와 Hellman은 이 조건을 제시했지만 암호화와 서명에 쓸 함수를 실제로 만들지는 못했고, 키를 나눠 갖는 방법(Diffie–Hellman 키교환)만 내놓았다.

이듬해인 1977년 Rivest, Shamir, Adleman이 소인수분해로 이 함수를 처음 구현했다. 그것이 RSA이고, 하나의 키 쌍으로 암호화와 서명을 모두 할 수 있다. RSA에서는 이렇게 대응된다.

사실 RSA와 거의 같은 방식은 영국 정보기관 GCHQ(Government Communications Headquarters)의 Clifford Cocks가 1973년에 먼저 고안했다. 다만 기밀로 분류되는 바람에 1997년에야 세상에 알려졌다.

나머지 연산(모듈러 산술)

시계를 생각하면 쉽다. 10시에서 5시간 뒤는 15시가 아니라 3시다. 12를 넘으면 다시 처음부터 세므로, 시계에서는 15시와 3시가 같은 자리다. 12로 나눈 나머지만 보는 셈이다.

이렇게 어떤 수 n으로 나눈 나머지만 따지는 계산을 나머지 연산이라고 한다. 쓰는 말은 세 가지다.

• a mod n: a를 n으로 나눈 나머지. 예를 들어 17 mod 5 = 2다.
• mod n의 n: 나누는 수. 시계에서는 12다. 수학 교과서에서는 이 수를 법(modulus)이라고 부르지만, 이 글에서는 mod n으로 쓴다.
• a ≡ b (mod n): a와 b를 n으로 나눈 나머지가 같다는 뜻이다. 이때 a와 b가 mod n에서 합동이라고 한다. 시계라면 15 ≡ 3 (mod 12)다.

17 ≡ 2 ≡ 7 ≡ -3 (mod 5)     5로 나누면 모두 나머지가 2

음수도 같다. -3 = 5 × (-1) + 2이므로 -3을 5로 나눈 나머지는 2다.

나머지 연산의 핵심 성질은 중간에 나머지를 취해도 결과가 같다는 것이다.

(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a × b) mod n = ((a mod n) × (b mod n)) mod n

이 성질 덕분에 65^17처럼 큰 거듭제곱도 매 단계 나머지를 취하면서 작은 수로 계산할 수 있다. 나눗셈은 그대로 되지 않는다. 대신 곱해서 1이 되는 수(모듈러 역원)를 곱한다.

최대공약수와 유클리드 호제법

두 수의 최대공약수(GCD, Greatest Common Divisor)가 1이면 두 수가 서로소라고 한다.

GCD는 유클리드 호제법으로 빠르게 구한다. gcd(a, b) = gcd(b, a mod b)를 나머지가 0이 될 때까지 반복하고, 그때 마지막으로 나눈 수가 최대공약수다. 아래 예제의 3120과 17은 키 생성 예시에서 φ(n)과 e로 다시 쓰이는 수다.

gcd(3120, 17)
  3120 = 183 × 17 + 9
    17 =   1 × 9  + 8
     9 =   1 × 8  + 1
     8 =   8 × 1  + 0   → gcd = 1 (서로소)

서로소가 아니면 마지막으로 나눈 수가 1보다 크다. e로 45를 골랐다고 해 보자.

gcd(3120, 45)
  3120 = 69 × 45 + 15
    45 =  3 × 15 + 0    → gcd = 15 (서로소 아님)

3120과 45는 둘 다 15(= 3 × 5)로 나누어떨어진다. 이런 e로는 개인키 d를 계산할 수 없어서, RSA는 키를 만들 때 e가 φ(n)과 서로소인지 먼저 확인한다. 같은 이유로 e = 3도 이 φ(n)에서는 쓸 수 없다(3120 = 3 × 1040).

반복 횟수는 자릿수에 비례하므로, 수백 자리 수에도 순식간에 끝난다.

확장 유클리드 호제법과 모듈러 역원

a × x ≡ 1 (mod n)을 만족하는 x를 a의 모듈러 역원이라 하고 a⁻¹ mod n으로 쓴다. 나머지 세계의 “나눗셈”이다. 역원은 gcd(a, n) = 1일 때만 존재한다.

역원은 확장 유클리드 호제법으로 구한다. 호제법을 돌리면서 a × s + b × t = gcd(a, b)를 만족하는 s, t를 함께 추적하는 방법이다. 위 예에서 17의 역원(mod 3120)을 구해 보자.

각 행은 r = 이전 r - 몫 × 직전 r이고, s, t도 같은 식으로 갱신한다. 나머지가 1인 행에서 3120 × 2 + 17 × (-367) = 1이 된다. 양변을 3120으로 나눈 나머지를 보면 17 × (-367) ≡ 1이므로 역원은 -367 mod 3120 = 2753이다.

17 × 2753 = 46801 = 15 × 3120 + 1  ✓

이 2753이 키 생성 예시에서 개인키 d가 된다.

소수와 소인수분해

1과 자기 자신으로만 나누어떨어지는 1보다 큰 수가 소수다. 모든 자연수는 소수들의 곱으로 한 가지 방법으로만 나타난다(산술의 기본 정리).

RSA의 안전성은 이 비대칭에 기반한다.

• 곱셈은 쉽다: 약 155자리 소수 두 개를 곱하는 건 컴퓨터로 마이크로초다.
• 소인수분해는 어렵다: 결과로 나온 약 309자리(1024비트) 수를 다시 쪼개는 데 알려진 가장 좋은 방법(GNFS, General Number Field Sieve)으로도 어마어마한 계산이 든다.

소수는 얼마나 많은가

소수는 무한히 많다. 유클리드의 증명이 간단하다. 소수가 유한하다고 가정하고 전부 곱한 뒤 1을 더하면, 그 수는 어떤 소수로 나눠도 1이 남는다. 그러면 그 수 자체가 소수이거나 목록에 없는 소수를 약수로 가지므로 모순이다.

수가 커질수록 소수는 드물어진다. 하지만 아주 천천히 드물어진다.

범위가 1,000배씩 커져도 비율은 4, 6, 13, 20, 27로 덧셈하듯 조금씩 줄어든다. 소수 정리가 이를 설명한다. x 근처에서 소수의 비율은 약 1 / ln x이고, ln x는 자릿수에 비례한다. 자릿수가 두 배가 되어야 소수 비율이 겨우 절반이 된다는 뜻이다.

RSA-512의 p, q 같은 256비트 수에 적용하면 이렇다.

• ln(2^256) ≈ 177이므로 이 근처 수는 약 177개 중 1개가 소수다. 홀수만 보면 89개 중 1개다.
• 2^256 이하의 수는 약 1.2 × 10⁷⁷개이고, 그중 소수는 약 6.5 × 10⁷⁴개다.

비율로는 1%도 안 되지만 모수가 우주의 원자 수(약 10⁸⁰개)와 비슷한 규모라 개수는 어마어마하다. RSA-2048의 1024비트 소수라면 710개 중 1개꼴이고, 개수는 약 2.5 × 10³⁰⁵개다.

소수가 이렇게 많아서 RSA에 두 가지가 보장된다.

• 키 생성이 빠르다: 무작위 256비트 홀수를 고르면 평균 89번 안에 소수를 만난다. 소수 판정 한 번은 밀리초 단위라 키 생성이 금방 끝난다.
• 같은 소수가 겹칠 일이 없다: 생일 문제로 계산해도 우연히 겹치려면 약 10³⁷개의 키를 만들어야 한다. 실제로 소수가 겹친 키가 발견된 적은 있지만, 소수가 모자라서가 아니라 난수 생성기가 고장 나서였다.

다 나눠 보면 되지 않나: 시행 나눗셈

n을 작은 소수부터 차례로 나눠 보면 언젠가는 p가 나온다. 이 방법을 시행 나눗셈(trial division)이라고 한다. 원리상 틀린 데가 없다. 확인할 범위도 n의 절반이 아니라 √n까지면 된다. 두 소인수 중 작은 쪽은 반드시 √n 이하이기 때문이다.

문제는 앞 절의 소수 개수다. 컴퓨터 10억 대가 각각 1초에 1조 번, 합쳐서 초당 10²¹번 나눗셈을 한다고 가정해 보자.

시행 나눗셈의 비용은 √n = 2^(비트 수 / 2)에 비례한다. 키가 1비트 늘 때마다 약 1.4배씩, 즉 키 길이에 대해 지수적으로 늘어난다.

그런데 RSA-512는 실제로 몇 시간이면 깨진다. 시행 나눗셈이 아니라 GNFS처럼 훨씬 영리한 알고리즘 덕분이다. GNFS의 시간 복잡도는 대략 exp(1.923 × (ln n)^(1/3) × (ln ln n)^(2/3))이다. 지수 시간보다는 훨씬 느리게 늘지만 다항 시간보다는 빠르게 늘어서, 비트 수를 늘리면 계산량이 여전히 크게 뛴다.

결국 RSA의 안전성은 “다 나눠 볼 수 없다”가 아니라 “알려진 가장 좋은 알고리즘으로도 시간이 너무 걸린다”에 기반한다. 그래서 RSA 키 길이는 GNFS를 기준으로 정한다.

시행 나눗셈이 쓸모없지는 않다. 소인수 하나가 작으면 바로 찾아낸다. 그래서 키 생성기는 소수 후보를 본격적인 소수 판정에 넘기기 전에 작은 소수로 나눠 보고, 나누어떨어지는 후보를 싸게 걸러 낸다.

오일러 피 함수

φ(n)(오일러 피 함수)은 1부터 n까지 중 n과 서로소인 수의 개수다.

• p가 소수면 φ(p) = p - 1이다(1부터 p-1까지 전부 서로소).
• p, q가 서로 다른 소수면 φ(p × q) = (p - 1)(q - 1)이다.

φ(10) = |{1, 3, 7, 9}| = 4 = (2 - 1)(5 - 1)

n = p × q에서 φ(n)을 구하려면 p, q를 알아야 한다. 즉 φ(n)을 아는 것은 소인수분해를 아는 것과 같다. 실제로 n과 φ(n)을 알면 p + q = n - φ(n) + 1이 나오고, 이차방정식을 풀어 p, q를 바로 얻는다.

오일러 정리와 페르마 소정리

RSA 복호화가 맞는 이유의 핵심이다.

오일러 정리:     gcd(a, n) = 1 이면  a^φ(n) ≡ 1 (mod n)
페르마 소정리:   p가 소수이고 p ∤ a 이면  a^(p-1) ≡ 1 (mod p)

페르마 소정리는 오일러 정리에서 n이 소수인 경우다. 예를 들어 7^φ(10) = 7^4 = 2401 ≡ 1 (mod 10)이다.

한마디로 지수는 φ(n) 주기로 돈다. a^k의 k에 φ(n)의 배수를 더해도 결과가 같다. 그래서 e × d ≡ 1 (mod φ(n))이 되게 d를 고르면 e제곱한 것을 d제곱했을 때 원래 수로 돌아온다.

중국인의 나머지 정리(CRT)

서로소인 두 수 p, q에 대해 “p로 나눈 나머지”와 “q로 나눈 나머지”를 알면, p × q로 나눈 나머지가 정확히 하나로 정해진다는 정리다(CRT, Chinese Remainder Theorem).

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)     →  x ≡ 8 (mod 15)

RSA에서는 두 군데에 쓰인다.

1. 증명: m이 n과 서로소가 아닐 때도 복호화가 맞다는 것을 p, q 각각에서 따로 보이고 합친다.
2. 속도: 개인키 연산을 n(512비트) 대신 p, q(각 256비트)에서 따로 하고 합치면 약 4배 빠르다.

빠른 거듭제곱(square-and-multiply)

m^d mod n을 m을 d번 곱해서 구하면, d가 2048비트일 때 우주의 나이로도 못 끝낸다. 대신 지수를 2진수로 보고 제곱과 곱하기를 반복한다. 왼쪽 비트부터 보면서 매번 제곱하고, 비트가 1이면 m을 한 번 더 곱한다.

65^17 mod 3233을 계산해 보자. 17 = 10001₂다.

곱셈 횟수가 지수 크기가 아니라 지수의 비트 수에 비례한다. 2048비트 지수도 약 2048번의 제곱과 그 절반 정도의 곱셈이면 끝난다.

이 방식은 비트가 1일 때만 곱셈을 더 하므로, 실행 시간이나 전력 소비를 재면 비밀 지수 d의 비트가 새어 나갈 수 있다. 실제 라이브러리는 비트와 상관없이 같은 연산을 하는 방식(Montgomery ladder 등)과 블라인딩을 쓴다.

컴퓨터는 큰 수를 어떻게 계산하나

CPU는 한 번에 64비트까지만 계산한다. 2048비트 수를 다루려면 64비트짜리 조각 여러 개로 쪼개야 한다. 방법은 초등학교에서 배운 세로셈과 같다.

조각으로 쪼개서 저장한다. 세로셈에서 한 자리가 0~9를 담듯, 64비트 단위(limb, 워드) 하나를 한 “자리”로 쓴다. 2⁶⁴진법인 셈이다.

2048비트 수 = 64비트 × 32칸
n = a₃₁·2^(64·31) + … + a₁·2^64 + a₀

이것을 다중 정밀도(multi-precision) 또는 빅넘(bignum) 연산이라고 한다. Python의 int가 처음부터 이렇게 구현돼 있어서, 뒤의 예시 코드에서 154자리 수를 그냥 쓸 수 있다(CPython은 30비트 단위). C에서는 OpenSSL의 BIGNUM이나 GMP(GNU Multiple Precision Arithmetic Library) 같은 라이브러리를 쓴다.

연산은 세로셈 그대로 한다.

• 덧셈: 칸끼리 더하고 넘친 자리올림(carry)을 다음 칸으로 넘긴다. x86-64에는 자리올림까지 더하는 명령(adc)이 있다.
• 곱셈: 32칸 × 32칸이면 64비트 곱셈 1,024번이다. mul 명령은 64비트 두 개를 곱해 128비트 결과를 한 번에 준다. 수가 더 크면 Karatsuba처럼 곱셈 횟수를 줄이는 알고리즘을 쓴다.

끝까지 거듭제곱하지 않는다. 가장 중요한 요령이다. m^d를 그대로 계산하면 어떤 컴퓨터로도 불가능하다.

• e = 65537만 해도, 2000비트 m의 65537제곱은 약 1억 3천만 비트(16MB)짜리 수다.
• 개인키 d는 2048비트라서, m^d는 비트 수 자체가 약 2²⁰⁴⁸이다. 저장할 공간이 우주에 없다.

그래서 앞의 square-and-multiply 표처럼 제곱하거나 곱할 때마다 바로 mod n을 취한다. 중간값이 늘 n보다 작으므로, 2048비트 수끼리의 곱셈과 나머지 연산을 3,000번쯤 반복하면 끝난다. 나머지 연산 절에서 본 “중간에 나머지를 취해도 결과가 같다”는 성질이 실제 구현에서 결정적인 이유다.

나눗셈을 피한다: Montgomery 곱셈. mod n을 구하려면 원래 나눗셈이 필요한데, 큰 수 나눗셈은 곱셈보다 훨씬 느리다. 실제 라이브러리는 Montgomery 곱셈을 쓴다.

• 수를 특수한 형태(Montgomery 형태)로 바꿔 두면, mod n을 나눗셈 없이 곱셈과 64비트 단위 자리 이동만으로 구할 수 있다.
• 처음과 끝에 한 번씩 변환하는 비용이 들지만, 곱셈을 수천 번 하는 거듭제곱에서는 크게 이득이다.
• 비슷한 목적으로 Barrett 축약도 쓴다.

여기에 뒤의 CRT 최적화(절반 크기로 나눠 계산해 약 4배 이득)와 손으로 최적화한 어셈블리가 더해진다. 실험 환경(Intel Xeon 2.1GHz 클라우드 컨테이너, OpenSSL 3.0.13, Python 3.13)에서 2048비트로 재 보면 이렇다.

$ openssl speed -seconds 1 rsa2048
                  sign    verify    sign/s verify/s
rsa 2048 bits 0.000406s 0.000020s   2465.7  49240.4

공개키 연산이 개인키 연산보다 수십 배 빠른 것은 e = 65537이 17비트뿐이라 곱셈 횟수가 적기 때문이다. 그래서 RSA는 서명 검증과 암호화가 가볍고, 서명 생성과 복호화가 무겁다.

소수 판정: 밀러-라빈

RSA 키를 만들려면 수백 자리 소수를 찾아야 한다. 소인수분해로 확인할 수는 없으니 확률적 소수 판정을 쓴다.

가장 단순한 건 페르마 소정리를 거꾸로 쓰는 것이다. a^(n-1) mod n ≠ 1이면 n은 확실히 합성수다. 그러나 이 검사를 n과 서로소인 모든 a에 대해 통과하는 합성수(카마이클 수)가 있다. 561 = 3 × 11 × 17이 가장 작은 예다.

2^560 mod 561 = 1     ← 페르마 검사는 통과해 버린다

밀러-라빈 판정은 여기에 한 가지를 더 본다. 소수 p에 대해 mod p에서는 x² ≡ 1의 해가 ±1뿐이다. n - 1 = 2^s × d로 쓰고 a^d부터 제곱을 반복하면서, ±1이 아닌 수가 제곱해서 1이 되는 순간을 찾는다.

560 = 2^4 × 35
2^35 mod 561 = 263
263² mod 561 = 166
166² mod 561 = 67
 67² mod 561 = 1      ← 67은 ±1이 아닌데 제곱이 1 → 561은 합성수

합성수가 한 번의 검사를 통과할 확률은 최대 1/4이다. 서로 다른 무작위 a로 k번 반복하면 오판 확률은 4^(-k) 이하가 된다. 실제 라이브러리는 비트 수에 맞춰 반복 횟수를 정한다.

RSA 알고리즘

자~ 지금까지 공부한 내용을 바탕으로 이제 본격적으로 RSA 알고리즘에 대해 알아보자.

키 생성

1. 큰 소수 p, q를 무작위로 고른다. 크기는 비슷하게(각각 키 길이의 절반) 하되 너무 가깝지 않게 한다.
2. n = p × q를 계산한다. n의 비트 수가 “키 길이”다(RSA-2048이면 2048비트).
3. φ(n) = (p - 1)(q - 1)을 계산한다.
4. gcd(e, φ(n)) = 1인 공개 지수 e를 고른다. 거의 항상 65537(= 2¹⁶ + 1)을 쓴다.
5. d = e⁻¹ mod φ(n)을 확장 유클리드 호제법으로 구한다.

결과는 이렇다.

손으로 따라갈 수 있게 작은 수로 해 보면 이렇다. 이 키를 아래 절의 예시에서 계속 쓴다.

p = 61, q = 53
n = 61 × 53 = 3233
φ(n) = 60 × 52 = 3120
e = 17                     (gcd(17, 3120) = 1)
d = 17⁻¹ mod 3120 = 2753   (확장 유클리드 호제법 절의 표)

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

e = 65537이 표준이 된 이유는 2진수로 10000000000000001이라 square-and-multiply에서 제곱 16번, 곱셈 1번이면 되기 때문이다. 그러면서도 e = 3 같은 아주 작은 값의 위험은 피한다.

암호화와 복호화

메시지를 0 ≤ m < n인 정수 m으로 바꾼 뒤 이렇게 계산한다.

암호화:  c = m^e mod n     (공개키로 누구나)
복호화:  m = c^d mod n     (개인키를 가진 사람만)

작은 예의 키로 m = 65(문자 A의 ASCII 코드)를 암호화하고 다시 복호화하면 이렇다.

c = 65^17 mod 3233 = 2790        (빠른 거듭제곱 절의 표)
m = 2790^2753 mod 3233 = 65  ✓

여기서 m < n이 중요하다. RSA 계산의 결과는 항상 n으로 나눈 나머지라서, m이 n 이상이면 복호화해도 원래 m이 아니라 m mod n이 나온다. 65에 n을 더한 3298을 암호화해 보면 65와 같은 암호문이 나오고, 복호화하면 65가 돌아온다.

3298^17 mod 3233 = 2790        (3298 = 65 + 3233, 65의 암호문과 같다)
2790^2753 mod 3233 = 65        → 3298이 아니라 65가 나온다

그래서 n보다 큰 메시지는 한 번에 암호화할 수 없다. 키 길이가 한 번에 담을 수 있는 메시지 크기의 상한이 되는 셈이다.

실제로 암호화하는 대상은 숫자가 아니라 문자열이나 파일이다. RSA는 정수만 계산하므로, 먼저 메시지를 바이트로, 바이트를 하나의 큰 정수로 바꾼다. 8바이트 문자열 pwnblitz로 처음부터 끝까지 해 보자.

① 문자열 → 바이트: 각 글자를 ASCII 코드(16진수)로 바꾼다.

 p  w  n  b  l  i  t  z
70 77 6e 62 6c 69 74 7a

② 바이트 → 정수 m: 8바이트를 앞에서부터 이어 붙여 하나의 수로 읽는다(빅엔디언).

m = 0x70776e626c69747a = 8104067423481197690   (63비트)

③ 키 준비: 앞에서 본 대로 m < n이어야 하는데, 작은 예의 키(n = 3233, 12비트)는 2바이트도 담지 못한다. 그래서 이 예에서는 조금 더 큰 키를 쓴다.

p = 29000000009, q = 41000000021
n = 1189000000978000000189      (71비트)
e = 65537
d = 478959977172760425473

④ 암호화: c = m^e mod n

c = 8104067423481197690^65537 mod n = 513227893339762215819

⑤ 복호화: c^d mod n으로 정수를 되찾고, 그 정수를 다시 8바이트로 바꾸면 원래 문자열이 나온다.

c^d mod n = 8104067423481197690 = 0x70776e626c69747a → b'pwnblitz'  ✓

Python으로는 몇 줄이면 같은 과정을 해 볼 수 있다.

p, q, e = 29000000009, 41000000021, 65537
n = p * q
d = pow(e, -1, (p - 1) * (q - 1))

m = int.from_bytes(b"pwnblitz", "big")    # 문자열 → 정수
c = pow(m, e, n)                          # 암호화
m2 = pow(c, d, n)                         # 복호화
print(m2.to_bytes(8, "big"))              # 정수 → 문자열: b'pwnblitz'

이 방식은 원리만 보여 주는 패딩 없는 RSA다. 실제로는 메시지에 패딩을 씌운 뒤 정수로 바꾸고, 긴 데이터는 RSA로 직접 암호화하지 않는다.

왜 복호화가 되는가

c^d = (m^e)^d = m^(ed)이므로 m^(ed) ≡ m (mod n)을 보이면 된다. e × d ≡ 1 (mod φ(n))이므로 어떤 정수 k에 대해 ed = 1 + k × φ(n)이다.

경우 1: gcd(m, n) = 1 — 오일러 정리를 바로 쓴다.

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

경우 2: m이 p나 q의 배수 — 오일러 정리를 쓸 수 없지만 CRT로 p와 q에서 따로 보인다.

• mod p에서: m ≡ 0이면 양쪽 다 0이라 성립한다. 아니면 페르마 소정리로 m^(p-1) ≡ 1이고, φ(n)이 p - 1의 배수이므로 m^(ed) = m × (m^(p-1))^(k(q-1)) ≡ m이다.
• mod q에서도 같은 논리로 m^(ed) ≡ m이다.
• CRT에 따라 mod p와 mod q 양쪽에서 m과 합동이면 mod n에서도 합동이다.

따라서 모든 0 ≤ m < n에 대해 복호화가 맞다. 다만 경우 2는 m으로 gcd(m, n)을 구하면 n이 소인수분해된다는 뜻이기도 하다. 무작위 메시지에서 일어날 확률은 대략 1/p + 1/q로, 사실상 0이다.

φ(n) 대신 λ(n)

증명을 다시 보면 실제로 필요한 건 “ed - 1이 p - 1과 q - 1 둘 다의 배수”라는 사실뿐이다. 그 최소 조건이 카마이클 함수 λ(n) = lcm(p - 1, q - 1)이다.

• d = e⁻¹ mod λ(n)으로 구하면 φ(n) 기준보다 작거나 같은 d가 나온다. p - 1, q - 1이 모두 짝수라 λ(n)은 항상 φ(n)의 절반 이하다.
• 두 d 모두 복호화는 똑같이 된다. 미국 연방 표준 FIPS(Federal Information Processing Standards) 186-5는 λ(n) 기준을 요구한다.
• 뒤의 RSA-512 실습에서 OpenSSL 3.0.13이 만든 키의 d는 φ(n) 기준이었다.

작은 예에서는 λ(n) = lcm(60, 52) = 780이고, 이 기준으로 구한 d는 413이다. 413으로도 똑같이 복호화된다.

CRT로 빠르게 복호화하기

개인키 연산은 d가 n만큼 커서 느리다. p, q를 알고 있으니 CRT로 쪼개서 계산한다. 이를 위해 개인키 파일에 세 값을 미리 저장해 둔다.

dP   = d mod (p - 1)
dQ   = d mod (q - 1)
qInv = q⁻¹ mod p

복호화는 이렇게 한다(표준 문서 RFC 8017 5.1.2절).

m1 = c^dP mod p
m2 = c^dQ mod q
h  = qInv × (m1 - m2) mod p
m  = m2 + h × q

작은 예의 암호문 2790을 CRT로 풀어 보면 이렇다.

dP = 2753 mod 60 = 53
dQ = 2753 mod 52 = 49
qInv = 53⁻¹ mod 61 = 38      (53 × 38 = 2014 = 33 × 61 + 1)

m1 = 2790^53 mod 61 = 4
m2 = 2790^49 mod 53 = 12
h  = 38 × (4 - 12) mod 61 = 1
m  = 12 + 1 × 53 = 65  ✓

절반 크기 수의 거듭제곱은 곱셈 하나가 약 1/4 비용이고 지수 길이도 절반이라, 각각이 약 1/8이다. 두 번 하므로 전체로는 약 4배 빠르다. 대신 이 최적화는 오류 주입 공격이라는 새 약점을 만든다.

전자서명

같은 식을 반대로 쓰면 서명이 된다.

서명:  s = H(M)^d mod n      (개인키로, 주인만)
검증:  H(M) == s^e mod n ?   (공개키로, 누구나)

H는 SHA-256 같은 해시 함수다. 메시지를 직접 서명하지 않고 해시를 서명하는 이유는 두 가지다. 메시지가 n보다 길 수 있고, 해시 없이 서명하면 s1 × s2가 m1 × m2의 서명이 되는 식으로 서명을 위조할 수 있기 때문이다. 실제로는 해시에 다시 패딩을 씌운 뒤 서명한다. RSA 표준인 PKCS#1(Public-Key Cryptography Standards #1)이 정한 v1.5 서명 방식이나 PSS가 그 패딩이다.

작은 예의 키로, 해시값이 123이라고 하면 이렇다.

s = 123^2753 mod 3233 = 2746
검증: 2746^17 mod 3233 = 123  ✓

“서명은 개인키로 암호화하는 것”이라는 설명이 흔하지만, 수식이 닮았을 뿐 패딩과 안전성 요구가 다르다. 암호화용 키와 서명용 키는 나눠 쓰는 것이 원칙이다.

실제 예시: RSA-512

이제 실제 도구로 512비트 키를 만들어 같은 과정을 따라간다.

실험 환경은 Ubuntu 24.04, OpenSSL 3.0.13, Python 3.13, cryptography 50.0.1이다.

키 만들기

$ openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:512 -out rsa512.pem
$ openssl pkey -in rsa512.pem -pubout -out pub.pem

-----BEGIN PRIVATE KEY-----
MIIBVAIBADANBgkqhkiG9w0BAQEFAASCAT4wggE6AgEAAkEAn/yFgkcD7crrcsFo
Xw+6BLRSLaDAZNzUc6CtuzgmWYQJxbrxMKS3UxTLDFbTTNEKgEdc9/KM4jLF8b8A
KtVYTwIDAQABAkEAiyiORKRawYLoy7d5fn5icmcat/+EefcvgKf5lcigaukzo/XK
/FXAD6dFKCR8aIngcOZBACt114vSqZw/H6gmyQIhAM7j2Aq1SFH40ogJa/2naczC
hJt3UdseCGTxxhG9LSPVAiEAxfZ4afWe3hGhrxFoBw3dASEk8H4dghLWZRbPBirW
MZMCIFH2C4F6fdMTmvwPl3uelhhrOzOH2qLOzA6JhalDY52dAiBpuAlwVMqlv3bA
HqSWd9HZw5CNmlw51cOHMtoWahP/XwIgImS23qeayNLEBghXEJc48HMF+qGKO4cZ
9XgH0OnvEGs=
-----END PRIVATE KEY-----

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAJ/8hYJHA+3K63LBaF8PugS0Ui2gwGTc
1HOgrbs4JlmECcW68TCkt1MUywxW00zRCoBHXPfyjOIyxfG/ACrVWE8CAwEAAQ==
-----END PUBLIC KEY-----

키 파일 안의 값

PEM(Privacy-Enhanced Mail) 형식은 ASN.1(Abstract Syntax Notation One) 구조를 DER(Distinguished Encoding Rules)로 인코딩한 바이너리를 Base64로 감싼 것이다. 개인키 파일 안에는 PKCS#1이 정한 순서대로 정수 아홉 개가 들어 있다.

$ openssl pkey -in rsa512.pem -text -noout
Private-Key: (512 bit, 2 primes)
modulus:
    00:9f:fc:85:82:47:03:ed:ca:eb:72:c1:68:5f:0f:
    ba:04:b4:52:2d:a0:c0:64:dc:d4:73:a0:ad:bb:38:
    26:59:84:09:c5:ba:f1:30:a4:b7:53:14:cb:0c:56:
    d3:4c:d1:0a:80:47:5c:f7:f2:8c:e2:32:c5:f1:bf:
    00:2a:d5:58:4f
publicExponent: 65537 (0x10001)
privateExponent:
    00:8b:28:8e:44:a4:5a:c1:82:e8:cb:b7:79:7e:7e:
    62:72:67:1a:b7:ff:84:79:f7:2f:80:a7:f9:95:c8:
    a0:6a:e9:33:a3:f5:ca:fc:55:c0:0f:a7:45:28:24:
    7c:68:89:e0:70:e6:41:00:2b:75:d7:8b:d2:a9:9c:
    3f:1f:a8:26:c9
prime1:
    00:ce:e3:d8:0a:b5:48:51:f8:d2:88:09:6b:fd:a7:
    69:cc:c2:84:9b:77:51:db:1e:08:64:f1:c6:11:bd:
    2d:23:d5
prime2:
    00:c5:f6:78:69:f5:9e:de:11:a1:af:11:68:07:0d:
    dd:01:21:24:f0:7e:1d:82:12:d6:65:16:cf:06:2a:
    d6:31:93
exponent1:
    51:f6:0b:81:7a:7d:d3:13:9a:fc:0f:97:7b:9e:96:
    18:6b:3b:33:87:da:a2:ce:cc:0e:89:85:a9:43:63:
    9d:9d
exponent2:
    69:b8:09:70:54:ca:a5:bf:76:c0:1e:a4:96:77:d1:
    d9:c3:90:8d:9a:5c:39:d5:c3:87:32:da:16:6a:13:
    ff:5f
coefficient:
    22:64:b6:de:a7:9a:c8:d2:c4:06:08:57:10:97:38:
    f0:73:05:fa:a1:8a:3b:87:19:f5:78:07:d0:e9:ef:
    10:6b

앞의 00은 DER 정수가 음수로 읽히지 않게 붙인 부호 바이트다. 이름을 앞 절의 기호와 맞춰 보면 이렇다.

공개키 파일에는 n과 e 두 개만 있다.

값 검증

10진수로 바꿔서 앞 절의 관계가 정말 성립하는지 확인한다.

import math
from cryptography.hazmat.primitives import serialization

key = serialization.load_pem_private_key(open("rsa512.pem", "rb").read(), None)
k = key.private_numbers()
n, e, d, p, q = k.public_numbers.n, k.public_numbers.e, k.d, k.p, k.q

phi = (p - 1) * (q - 1)
lam = math.lcm(p - 1, q - 1)

print("p * q == n        :", p * q == n)
print("d == e^-1 mod phi :", d == pow(e, -1, phi))
print("d == e^-1 mod lam :", d == pow(e, -1, lam))
print("dP == d mod (p-1) :", k.dmp1 == d % (p - 1))
print("dQ == d mod (q-1) :", k.dmq1 == d % (q - 1))
print("qInv == q^-1 mod p:", k.iqmp == pow(q, -1, p))

$ python3 verify.py
p * q == n        : True
d == e^-1 mod phi : True
d == e^-1 mod lam : False
dP == d mod (p-1) : True
dQ == d mod (q-1) : True
qInv == q^-1 mod p: True

값을 10진수로 펼치면 이렇다. n은 154자리다.

n = 8379168304550086449807344490128792431091039336737024727136590445576691409594283592049171404421956274269188660875702192181717808570503476395065181635696719
e = 65537
p = 93579012157759218278910331995509999177820501172642104749026624809483341997013
q = 89541106615061841712825751426199781693529612249735829847144856654367300137363

φ(n) = 8379168304550086449807344490128792431091039336737024727136590445576691409594100471930398583361964538185766951094830842068295430635907304913601330993562344
λ(n) = 4189584152275043224903672245064396215545519668368512363568295222788345704797050235965199291680982269092883475547415421034147715317953652456800665496781172

d (φ 기준, 파일에 저장된 값)
  = 7288317884567155623102486727494267551678360275732702054876197237439908659290350449400985263966138036517992051011807561409633962851517401110820511669561033
d (λ 기준)
  = 3098733732292112398198814482429871336132840607364189691307902014651562954493300213435785972285155767425108575464392140375486247533563748654019846172779861

dP   = 37072064523122855549923691191226728545001353005863969446251403938670003330461
dQ   = 47818014105322938158707119248143280276665744527953740769644976700889591185247
qInv = 15556583678902998972415315401002248179549414257827002632376710449105327820907

gcd(p - 1, q - 1) = 2라서 λ(n)이 정확히 φ(n)의 절반이다. 앞에서 말한 대로 이 키의 d는 φ(n) 기준이었다. 위의 두 d는 서로 다르지만 어느 쪽으로도 복호화가 된다.

패딩 없이 암호화·복호화

문자열을 바이트로, 바이트를 빅엔디언 정수로 바꿔서 식을 그대로 적용한다.

msg = b"Hello, RSA-512! from pwnblitz.net"   # 33바이트
m = int.from_bytes(msg, "big")
c = pow(m, e, n)                # 암호화
m2 = pow(c, d, n)               # 복호화
print(m2.to_bytes(len(msg), "big"))

m = 8382905590662478611826414001641596226714714265463421197424462108686583509968244
c = 1015202108328848712081590085179979061074146064724403823255612450058731865167486640875905462949813147093582279661959619519304369455439476178362634598714099
c^d mod n → b'Hello, RSA-512! from pwnblitz.net'

m은 263비트로 n(512비트)보다 작으므로 그대로 들어간다. 실제로는 RSA로 긴 데이터를 암호화하지 않고, 무작위 AES 키만 RSA로 감싸고 데이터는 AES로 암호화한다(하이브리드 암호).

CRT 복호화

같은 암호문을 CRT로 풀어 보자.

m1 = pow(c, k.dmp1, p)
m2 = pow(c, k.dmq1, q)
h = (k.iqmp * (m1 - m2)) % p
m = m2 + h * q

m1 = 54373508621908185003394454041206299888689661098273874761092500642566072234087
m2 = 55582675461727332533619119005016529216460326237989021639990439830424597193485
h  = 93
m  = m2 + 93 × q = 8382905590662478611826414001641596226714714265463421197424462108686583509968244  ✓

m1은 m mod p, m2는 m mod q다. m이 q의 약 93배라서 h가 93이 나왔다. 메시지가 p, q보다 작으면(예를 들어 8바이트 pwnblitz) m1 = m2 = m, h = 0이 되어 CRT의 동작이 잘 보이지 않는다. 그래서 일부러 긴 메시지를 골랐다.

패딩: PKCS#1 v1.5와 OAEP

실제 도구는 패딩 없는 RSA를 쓰지 않는다. OpenSSL로 pwnblitz(8바이트)를 암호화한 뒤, 개인키로 패딩을 벗기지 않고(rsa_padding_mode:none) 복호화하면 RSA 연산에 실제로 들어간 512비트 블록이 보인다.

$ printf 'pwnblitz' > msg.txt
$ openssl pkeyutl -encrypt -pubin -inkey pub.pem -in msg.txt -out c_pkcs1.bin
$ openssl pkeyutl -decrypt -inkey rsa512.pem -in c_pkcs1.bin -pkeyopt rsa_padding_mode:none | od -An -tx1
 00 02 b0 d3 e3 f9 d4 7d dc 1a ef d0 d7 38 67 22
 27 30 03 ad 78 62 06 a8 21 0b 97 a1 0e 4a b7 4e
 99 79 2f c6 28 16 4f e5 5b 89 2d 72 38 be 2f 6c
 83 a5 92 30 b5 f9 ce 00 70 77 6e 62 6c 69 74 7a

PKCS#1 v1.5 암호화 패딩의 구조는 00 02 | 0이 아닌 무작위 바이트(PS) | 00 | 메시지다. 마지막 8바이트 70 77 6e 62 6c 69 74 7a가 pwnblitz다. 무작위 바이트 덕분에 같은 메시지를 다시 암호화해도 매번 다른 암호문이 나온다.

$ openssl pkeyutl -encrypt -pubin -inkey pub.pem -in msg.txt | od -An -tx1 | head -1
 2f 5b 8c 28 81 7a b4 eb d2 91 e3 10 4d 91 5c 59
$ openssl pkeyutl -encrypt -pubin -inkey pub.pem -in msg.txt | od -An -tx1 | head -1
 7a 70 1e 49 7e 70 bf 9a df 04 d0 6d f4 e8 27 08

PKCS#1 v1.5는 1998년 Bleichenbacher가 보인 패딩 오라클 공격에 약하다. 새로 만드는 시스템은 OAEP를 쓴다. OAEP는 메시지와 무작위 시드를 해시 기반 마스크(MGF1, Mask Generation Function 1)로 섞어서, 블록 전체가 무작위처럼 보인다.

$ openssl pkeyutl -encrypt -pubin -inkey pub.pem -in msg.txt -out c_oaep.bin -pkeyopt rsa_padding_mode:oaep
$ openssl pkeyutl -decrypt -inkey rsa512.pem -in c_oaep.bin -pkeyopt rsa_padding_mode:none | od -An -tx1
 00 7c 5c 96 e7 ec 36 24 a2 3d 90 87 37 0f dd 6c
 1d b1 1f f5 76 89 6b d3 ad 4d e4 c9 0d fb e9 36
 5a aa 1a d3 0e a3 6f 26 bb 18 e5 9c b4 e4 7f 41
 c3 3c 3e 13 6d 3a 34 53 2e 28 fc 69 2d bb 09 1a

첫 바이트 00 말고는 메시지가 어디 있는지 보이지 않는다. 패딩에는 공간이 든다. k를 키 바이트 수(여기서는 64), hLen을 해시 길이라고 하면 한 번에 넣을 수 있는 메시지 길이는 이렇다.

$ openssl pkeyutl -encrypt -pubin -inkey pub.pem -in msg.txt -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256
...:rsa routines:ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex:data too large for key size:...

512비트 키는 SHA-256 OAEP로는 8바이트도 담지 못한다. 키가 너무 작다는 또 하나의 증거다.

서명

$ openssl dgst -sha256 -sign rsa512.pem -out sig.bin msg.txt
$ openssl dgst -sha256 -verify pub.pem -signature sig.bin msg.txt
Verified OK
$ openssl pkeyutl -verifyrecover -pubin -inkey pub.pem -in sig.bin -pkeyopt rsa_padding_mode:none | od -An -tx1
 00 01 ff ff ff ff ff ff ff ff ff ff 00 30 31 30
 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20
 92 12 33 99 40 a9 e0 4c 61 6c d3 0c e6 37 09 ca
 a0 bf c8 07 c0 04 b3 a7 12 98 e6 5b 5b ee 60 d4
$ openssl dgst -sha256 msg.txt
SHA2-256(msg.txt)= 9212339940a9e04c616cd30ce63709caa0bfc807c004b3a71298e65b5bee60d4

공개키로 s^e mod n을 계산하면 PKCS#1 v1.5 서명 패딩이 그대로 보인다. 구조는 00 01 | ff… | 00 | DigestInfo | 해시다.

• 30 31 … 04 20은 “이것은 SHA-256 해시이고 길이는 32바이트”라는 ASN.1 DigestInfo다. 60 86 48 01 65 03 04 02 01이 SHA-256의 OID(Object Identifier, 객체 식별자) 2.16.840.1.101.3.4.2.1이다.
• 마지막 32바이트가 msg.txt의 SHA-256 값과 정확히 같다.

서명 패딩은 무작위가 없어서 같은 메시지에는 항상 같은 서명이 나온다. 무작위 솔트를 넣고 안전성 증명이 있는 RSA-PSS가 더 권장되고, TLS 1.3 핸드셰이크 서명은 RSA를 쓸 때 PSS를 요구한다.

RSA-512는 왜 안전하지 않은가

이 글의 n도 CADO-NFS 같은 공개 도구로 분해할 수 있다. 위 논문 기준으로 클라우드에서 몇 시간이면 된다.

RSA가 실제로 쓰이는 곳

RSA는 1977년에 나온 알고리즘이지만 지금도 인터넷 곳곳에 있다. 다만 쓰임새는 크게 바뀌었다. 예전에는 비밀값을 감싸 보내는 암호화에 많이 썼지만, 지금은 대부분 “이 사람이 맞다”를 보증하는 서명에 쓴다.

TLS: 키교환에서 물러나 서명만 맡다

HTTPS에서 RSA의 역할은 TLS 1.3을 기점으로 바뀌었다.

TLS 1.2의 RSA 키 전송은 클라이언트가 만든 비밀값(premaster secret)을 서버의 RSA 공개키로 암호화해 보내는 방식이다. 단순하지만 두 가지 문제가 있다.

• 전방 기밀성이 없다. 세션키가 서버 개인키 하나에 달려 있다. 오늘 통신을 녹화해 두었다가 몇 년 뒤 개인키를 손에 넣으면, 녹화한 통신이 전부 풀린다. PQC 글의 HNDL(Harvest Now, Decrypt Later: 지금 저장, 나중에 해독) 공격과 같은 구조다.
• 패딩 오라클에 노출된다. PKCS#1 v1.5 암호화 패딩을 쓰기 때문에, Bleichenbacher 공격이 20년 넘게 구현마다 되풀이됐다.

그래서 TLS 1.3(RFC 8446, 2018)은 RSA 키 전송을 아예 없앴다. 세션키는 매번 새로 만드는 일회용 키로 ECDHE 키교환을 해서 얻고, RSA는 두 곳에서 서명만 한다.

• 인증서: 인증기관(CA)이 서버 인증서에 서명한다. 보통 PKCS#1 v1.5 서명(sha256WithRSAEncryption)이다.
• 핸드셰이크: 서버가 지금까지 주고받은 핸드셰이크 내용에 자기 개인키로 서명한다(CertificateVerify). TLS 1.3은 여기에 RSA-PSS를 요구한다.

로컬에 RSA-2048 인증서로 TLS 서버를 띄우고 두 방식으로 접속해 보면 차이가 그대로 보인다.

$ openssl req -x509 -newkey rsa:2048 -keyout server.key -out server.crt -days 30 -nodes -subj "/CN=localhost"
$ openssl s_server -accept 8443 -cert server.crt -key server.key -www

$ openssl s_client -connect localhost:8443 </dev/null 2>/dev/null | grep -E "PKEY|Peer sig|Temp Key|Cipher is"
   a:PKEY: rsaEncryption, 2048 (bit); sigalg: RSA-SHA256
Peer signing digest: SHA256
Peer signature type: RSA-PSS
Server Temp Key: X25519, 253 bits
New, TLSv1.3, Cipher is TLS_AES_256_GCM_SHA384

• a:PKEY ... sigalg: RSA-SHA256: 인증서의 공개키가 RSA-2048이고, 인증서 자체도 RSA로 서명돼 있다.
• Peer signature type: RSA-PSS: 서버가 핸드셰이크에 RSA-PSS로 서명했다.
• Server Temp Key: X25519: 세션키는 RSA가 아니라 일회용 X25519 키교환에서 나왔다.

서버를 TLS 1.2와 RSA 키 전송 암호군(AES128-GCM-SHA256, 정식 이름 TLS_RSA_WITH_AES_128_GCM_SHA256)만 받도록 띄우면 이렇게 바뀐다.

$ openssl s_server -accept 8443 -cert server.crt -key server.key -www -tls1_2 -cipher AES128-GCM-SHA256
$ openssl s_client -connect localhost:8443 -tls1_2 -cipher AES128-GCM-SHA256 </dev/null 2>/dev/null | grep -E "Peer sig|Temp Key|Cipher is"
New, TLSv1.2, Cipher is AES128-GCM-SHA256

일회용 키(Server Temp Key)도, 서버의 서명(Peer signature type)도 없다. 서버는 서명으로 자신을 증명하지 않고, 비밀값을 복호화할 수 있다는 사실만으로 개인키를 가졌음을 보인다. 세션 전체가 서버 개인키 하나에 달려 있다는 뜻이다.

실제 사이트에 openssl s_client -connect <도메인>:443으로 접속해 보면, RSA 인증서를 쓰는 곳과 ECDSA(Elliptic Curve Digital Signature Algorithm) 인증서를 쓰는 곳이 섞여 있다. 어느 쪽이든 TLS 1.3이면 키교환은 ECDHE(최근에는 PQC 하이브리드)다.

SSH 키

ssh-keygen -t rsa로 만드는 SSH 키도 RSA 키 쌍이다. 공개키 파일은 길어 보이지만 안에 든 건 e와 n 두 개뿐이다. 이 글의 RSA-512 공개키를 OpenSSH 형식으로 바꿔 보자.

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAAAQQCf/IWCRwPtyutywWhfD7oEtFItoMBk3NRzoK27OCZZhAnFuvEwpLdTFMsMVtNM0QqAR1z38oziMsXxvwAq1VhP demo

가운데 Base64를 풀면 “4바이트 길이 + 값”이 세 번 반복된다.

import base64, struct, sys

blob = base64.b64decode(open(sys.argv[1]).read().split()[1])
fields = []
while blob:
    (length,) = struct.unpack(">I", blob[:4])
    fields.append(blob[4:4 + length])
    blob = blob[4 + length:]

name, e, n = fields
print("type :", name.decode())
print("e    :", int.from_bytes(e, "big"))
print("n    :", int.from_bytes(n, "big").bit_length(), "bits")

$ python3 sshpub.py id_rsa512.pub
type : ssh-rsa
e    : 65537
n    : 512 bits

00 00 00 07 73 73 68 2d 72 73 61   길이 7, "ssh-rsa"
00 00 00 03 01 00 01               길이 3, e = 0x010001 = 65537
00 00 00 41 00 9f fc 85 …          길이 65, n (앞의 00은 부호 바이트)

모든 RSA SSH 공개키가 AAAAB3NzaC1yc2E로 시작하는 이유가 이것이다. 00 00 00 07 ssh-rsa를 Base64로 바꾼 값이다.

키 형식 이름(ssh-rsa)과 서명 알고리즘 이름은 구분해야 한다. 예전 서명 알고리즘 ssh-rsa는 SHA-1을 써서 OpenSSH 8.8(2021)부터 기본으로 꺼졌다. RSA 키 자체는 그대로 쓸 수 있고, 서명만 rsa-sha2-256/rsa-sha2-512로 한다. 새로 만드는 키라면 짧고 빠른 Ed25519가 기본 추천이다.

JWT: RS256과 JWKS

로그인 토큰으로 쓰는 JWT도 RSA로 서명하는 경우가 많다. 알고리즘 이름이 곧 패딩 방식이다.

토큰을 발급하는 서버는 검증용 공개키를 JWKS(JSON Web Key Set)로 공개한다. 이 글의 RSA-512 공개키를 JWK로 바꾸면 이렇다.

{
  "kty": "RSA",
  "alg": "RS256",
  "n": "n_yFgkcD7crrcsFoXw-6BLRSLaDAZNzUc6CtuzgmWYQJxbrxMKS3UxTLDFbTTNEKgEdc9_KM4jLF8b8AKtVYTw",
  "e": "AQAB"
}

여기에도 n과 e뿐이다. e의 AQAB는 01 00 01을 Base64url로 쓴 것, 즉 65537이다. JWKS를 열어 보면 거의 모든 키에서 AQAB를 보게 된다.

JWT에는 RSA와 관련된 유명한 구현 실수가 있다. 검증 코드가 토큰 헤더의 alg를 그대로 믿으면, 공격자가 alg를 HS256(HMAC, Hash-based Message Authentication Code)으로 바꾸고 누구나 받을 수 있는 RSA 공개키를 HMAC 비밀키로 써서 토큰을 만들 수 있다. 서버는 같은 공개키로 HMAC을 검증하므로 위조 토큰이 통과한다(알고리즘 혼동 공격). 검증하는 쪽에서 허용할 알고리즘을 고정해 두면 막힌다.

파일을 주고받을 때

파일을 안전하게 보내는 방법은 두 갈래다. RSA가 하는 일도 서로 다르다.

통로를 암호화하는 방식에서는 앞의 TLS·SSH와 똑같다. RSA는 “접속한 서버가 진짜인지”만 보증하고, 데이터는 ECDHE로 만든 세션키와 AES·ChaCha20으로 암호화된다. 파일은 받는 서버에 도착하면 평문이다.

파일 자체를 암호화하면 메일 첨부든 USB든 클라우드든 상관없이, 받는 사람의 개인키가 있어야만 열린다. 여기서 RSA가 암호화 용도로 쓰인다. 구조는 앞에서 본 하이브리드 암호 그대로다. GPG로 받는 사람의 RSA-3072 키에 1MB 파일을 암호화하고, 결과 파일 안의 패킷을 열어 보자.

$ gpg -r demo@example.invalid --encrypt -o report.bin.gpg report.bin
$ ls -l report.bin report.bin.gpg | awk '{print $5, $9}'
1048576 report.bin
1049890 report.bin.gpg
$ gpg --list-packets report.bin.gpg
gpg: encrypted with rsa3072 key, ID 99CCABB56DE5415F, created 2026-11-08
      "Demo Receiver <demo@example.invalid>"
# off=0 ctb=85 tag=1 hlen=3 plen=396
:pubkey enc packet: version 3, algo 1, keyid 99CCABB56DE5415F
	data: [3071 bits]
# off=399 ctb=d4 tag=20 hlen=2 plen=0 partial new-ctb
:aead encrypted packet: cipher=9 aead=2 cb=16
	length: unknown
# off=420 ctb=a3 tag=8 hlen=1 plen=0 indeterminate
:compressed packet: algo=2
# off=422 ctb=ae tag=11 hlen=5 plen=1048592
:literal data packet:

• pubkey enc packet ... algo 1: 무작위 세션키를 받는 사람의 RSA 공개키(algo 1 = RSA)로 암호화한 RSA-3072 블록 하나다. 400바이트가 안 된다.
• aead encrypted packet: cipher=9: 파일 내용은 그 세션키로 AES-256(cipher=9)으로 암호화돼 있다.
• 1MB 파일이 약 1.3KB만 커졌다. RSA 연산은 파일 크기와 상관없이 세션키에 한 번뿐이다.

받는 사람이 여러 명이면 세션키를 각자의 공개키로 한 번씩 감싸서 pubkey enc packet이 사람 수만큼 생긴다. 파일 본문은 한 번만 암호화된다.

이 방식에서 주의할 점이 두 가지 있다.

• 전방 기밀성이 없다. 받는 사람의 개인키가 나중에 새면, 그 키로 받은 과거 파일이 전부 열린다. TLS 1.2 RSA 키 전송과 같은 약점이다.
• 암호화만으로는 보낸 사람을 알 수 없다. 공개키는 누구나 가지므로 누구나 암호화할 수 있다. gpg --sign --encrypt처럼 보낸 사람의 서명을 함께 붙여야 한다.

최근 도구인 age는 기본으로 X25519를 쓰지만, 받는 사람의 SSH RSA 공개키(ssh-rsa ...)로도 파일을 암호화할 수 있다. 이때는 RSA-OAEP로 파일 키를 감싼다.

코드 서명과 부팅

• 소프트웨어 배포: Windows 실행 파일의 Authenticode 서명, Android 앱 서명, Debian·Ubuntu 패키지 저장소의 GPG 서명에 RSA가 많이 쓰인다. 사용자는 공개키로 “배포자가 만든 그대로인지”를 확인한다.
• Secure Boot: PC를 켤 때 UEFI 펌웨어가 부트로더의 서명을 확인한 뒤 실행한다. 이 체인의 키가 대부분 RSA-2048이다. 펌웨어에 박혀 있어 쉽게 바꿀 수 없다는 점에서, PQC 전환이 가장 어려운 곳 중 하나다.

랜섬웨어는 RSA를 어떻게 쓰나

랜섬웨어도 같은 하이브리드 구조를 쓴다. 공격자 입장에서 공개키 암호가 딱 맞는 도구이기 때문이다.

• 개인키가 피해자 PC에 없다. 악성코드에는 공개키만 들어 있다. 샘플을 아무리 분석해도 복호화 키는 나오지 않는다.
• 서버와 통신하지 않아도 된다. 공개키만 있으면 암호화할 수 있어서, 네트워크가 막힌 환경에서도 동작한다.
• 파일은 빠르게 암호화한다. 파일 내용은 AES나 ChaCha20 같은 대칭키로 암호화하고, RSA는 그 키만 감싼다.

많은 계열이 키를 한 단계 더 쌓는다.

1. 파일마다 새 대칭키를 만들어 파일 내용을 암호화한다.
2. 그 대칭키를 피해자별 RSA 공개키로 암호화해 파일 끝에 붙인다. 이 키 쌍은 감염 때 피해자 PC에서 새로 만든다.
3. 피해자 RSA 개인키는 악성코드에 내장된 공격자 마스터 공개키로 암호화해 남기고, 원본은 지운다.

피해자별 키 쌍을 따로 두는 이유는, 몸값을 낸 피해자에게 건넨 복호화 키가 다른 피해자에게 통하지 않게 하기 위해서다. 마스터 개인키는 끝까지 공격자 서버에만 있다. 최근에는 RSA 대신 Curve25519 같은 타원곡선을 쓰는 계열도 많지만 구조는 같다.

복구가 가능했던 경우는 거의 다 구현 실수나 수사 덕분이었다. RSA 수학 자체가 깨진 사례는 없다.

• WannaCry(2017): 피해자 RSA 키 쌍을 Windows 암호 API로 만들었는데, 일부 Windows XP·7 환경에서는 키 생성에 쓴 소수가 메모리에서 지워지지 않고 남아 있었다. 재부팅 전이라면 wanakiwi 같은 도구가 메모리에서 p를 찾아냈다. p를 알면 q = n / p, 이어서 d가 나온다. 이 글 앞부분의 키 생성 과정 그대로다.
• CryptoLocker(2013~2014): 국제 공조 수사로 공격자 서버의 데이터베이스를 확보하면서 피해자 개인키가 공개되고 복구 서비스가 열렸다.
• 그 밖에 예측 가능한 난수로 대칭키를 만들었거나, 모든 피해자에게 같은 키를 쓴 변종들이 있다. 이런 계열의 복호화 도구는 No More Ransom 프로젝트에 모여 있다.

그래서 랜섬웨어에 대비할 때는 암호를 풀 수 있다는 가정을 버리고, 감염 전후에 할 일을 미리 정해 둬야 한다.

• 제대로 구현된 랜섬웨어는 RSA를 깨서 복구할 수 없다. 네트워크에서 분리된 백업, 지울 수 없는(immutable) 백업, 실제 복구 연습이 확실한 대책이다.
• 감염을 발견하면 네트워크부터 분리하고, 섣불리 재부팅하지 않는다. WannaCry처럼 키가 메모리에 남아 있을 수 있어서, 메모리를 먼저 확보하면 복구 단서가 될 수 있다.
• 암호화보다 그 앞의 행동을 잡는다. 짧은 시간에 파일을 대량으로 읽고 다시 쓰거나 이름을 바꾸는 패턴, 볼륨 섀도 복사본 삭제 같은 행위가 탐지 지점이다.
• 최근 랜섬웨어는 암호화 전에 데이터를 빼돌려 공개하겠다고 협박하기도 한다(이중 갈취). 백업으로는 유출까지 막을 수 없다.

직접 쓸 때의 원칙

RSA를 직접 쓸 일이 생기면 이 글에서 본 pow(m, e, n)을 그대로 쓰지 않는다. 검증된 라이브러리의 고수준 API를 쓰고, 아래를 지킨다.

• 암호화는 OAEP, 서명은 PSS를 쓴다. 호환성 때문에 PKCS#1 v1.5 서명을 쓰는 건 아직 괜찮지만, PKCS#1 v1.5 암호화는 새로 쓰지 않는다.
• RSA로는 키만 감싼다. 데이터는 AES-GCM 같은 대칭키 암호로 암호화한다.
• 키는 2048비트 이상, 새로 만들면 3072비트 이상으로 한다. 개인키는 가능하면 HSM(Hardware Security Module, 하드웨어 보안 모듈)이나 클라우드 KMS 안에 둔다.
• 새로 설계하는 시스템이면 ECC(Elliptic Curve Cryptography, 타원곡선 암호)인 Ed25519, X25519를 먼저 검토하고, 장기적으로는 PQC 전환을 염두에 둔다.

RSA-OAEP로 AES 키를 감싸고 데이터는 AES-GCM으로 암호화하는 하이브리드 암호의 최소 예시다.

import os
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.ciphers.aead import AESGCM

# 받는 사람의 키 쌍 (실제로는 미리 만들어 두고 공개키만 배포한다)
priv = rsa.generate_private_key(public_exponent=65537, key_size=3072)
pub = priv.public_key()
oaep = padding.OAEP(mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(), label=None)

# 보내는 쪽: 데이터는 AES-GCM으로, AES 키만 RSA-OAEP로 감싼다
data = b"RSA wraps the key, AES encrypts the data." * 100
aes_key = AESGCM.generate_key(bit_length=256)
nonce = os.urandom(12)
ct = AESGCM(aes_key).encrypt(nonce, data, None)
wrapped_key = pub.encrypt(aes_key, oaep)

# 받는 쪽: 개인키로 AES 키를 풀고, 그 키로 데이터를 복호화한다
key2 = priv.decrypt(wrapped_key, oaep)
assert AESGCM(key2).decrypt(nonce, ct, None) == data

print("data         :", len(data), "bytes")
print("wrapped key  :", len(wrapped_key), "bytes (RSA-3072 블록 하나)")
print("ciphertext   :", len(ct), "bytes (데이터 + 16바이트 태그)")

$ python3 hybrid.py
data         : 4100 bytes
wrapped key  : 384 bytes (RSA-3072 블록 하나)
ciphertext   : 4116 bytes (데이터 + 16바이트 태그)

데이터가 4KB든 4GB든 RSA 연산은 32바이트 AES 키에 한 번만 한다. 실제 프로토콜도 대부분 이 구조다.

공격과 구현 실수

RSA의 수학은 수십 년째 버티고 있지만, 실제로 깨지는 건 대부분 잘못 쓴 RSA다.

패딩 없는 RSA의 한계

• 결정적이다: 같은 평문은 항상 같은 암호문이 된다. 평문 후보가 적으면(예: “yes”/“no”) 공개키로 하나씩 암호화해 비교하면 끝이다.

• 가단성이 있다: 암호문에 2^e를 곱해 복호화하면 평문이 2배가 된다. 공격자가 평문을 모른 채로 의미 있게 바꿀 수 있다. 키 생성의 작은 예로 m = 65의 암호문 2790에 해 보면 이렇다.

  text 복사

  c' = 2790 × 2^17 mod 3233 = 3017
  c'^2753 mod 3233 = 130 = 2 × 65

• 작은 e와 짧은 메시지: e = 3이고 m³ < n이면 mod n이 아무 일도 하지 않는다. 암호문의 정수 세제곱근이 곧 평문이다.

m = int.from_bytes(b"pwnblitz", "big")
c = pow(m, 3, n)          # e = 3, 패딩 없음
assert c == m ** 3        # mod n이 작동하지 않았다

def icbrt(x):             # 정수 세제곱근 (이분 탐색)
    lo, hi = 0, 1 << (x.bit_length() // 3 + 2)
    while lo < hi:
        mid = (lo + hi) // 2
        if mid ** 3 < x: lo = mid + 1
        else: hi = mid
    return lo

print(icbrt(c).to_bytes(8, "big"))   # b'pwnblitz'

같은 메시지를 e = 3인 서로 다른 세 사람에게 보내면, 메시지가 길어도 CRT로 m³을 복원해 같은 방법으로 푼다(Håstad 브로드캐스트 공격). 패딩이 이 문제들을 막는다.

작은 개인 지수: Wiener 공격

복호화를 빠르게 하려고 d를 작게 고르면 위험하다. d < n^(1/4) / 3이면 e / n의 연분수 전개에서 d가 바로 나온다(Wiener, 1990). 이후 Boneh–Durfee가 경계를 d < n^0.292까지 넓혔다. 표준 방식대로 e = 65537로 정하고 d를 계산하면 d는 n과 비슷한 크기가 되어 이 문제가 생기지 않는다.

너무 가까운 p, q: 페르마 분해

p와 q가 가까우면 n은 ((p+q)/2)² - ((q-p)/2)²이고 (p+q)/2는 √n 바로 위에 있다. a = ⌈√n⌉부터 올라가며 a² - n이 제곱수가 되는 곳을 찾으면 된다.

import math

def fermat(n):
    a = math.isqrt(n)
    if a * a < n:
        a += 1
    while True:
        b2 = a * a - n
        b = math.isqrt(b2)
        if b * b == b2:
            return a - b, a + b
        a += 1

일부러 q를 p 바로 다음 소수로 고른 512비트 키를 만들어 돌려 보면, 반복 없이 첫 시도에 0.0001초 만에 분해된다.

n bits  = 512
q - p   = 126
found   = True, steps = 0, 0.0001s

위 RSA-512 키의 p - q는 252비트 크기라 이 방법은 통하지 않는다. FIPS 186-5는 |p - q|가 2^(nlen/2 - 100)보다 클 것을 요구한다. 2022년에는 Canon·Fujifilm 프린터 등에 쓰인 Rambus SafeZone 라이브러리가 이렇게 가까운 소수를 만든다는 것이 발견됐다(CVE-2022-26320).

소수를 공유한 키: 배치 GCD

두 키가 소수 하나를 공유하면 gcd(n1, n2)만으로 둘 다 분해된다. 따로 보면 멀쩡한 키라도 함께 보면 깨진다. 2012년 Heninger 등은 인터넷에서 모은 TLS·SSH 공개키에 배치 GCD를 돌려, TLS 호스트의 약 0.5%에 해당하는 키를 분해했다. 대부분 엔트로피가 부족한 임베디드 장비에서 만든 키였다(Mining Your Ps and Qs). 부팅 직후 난수 풀이 비어 있는 상태에서 키를 만든 것이 원인이었다.

패딩 오라클: Bleichenbacher

PKCS#1 v1.5 복호화 후 “패딩이 올바른지”를 서버가 응답 내용이나 시간 차이로 알려 주면, 공격자는 암호문에 s^e를 곱해 가며 수만~수백만 번 질의해서 평문을 복원할 수 있다(Bleichenbacher, 1998). 가단성과 패딩 검사가 합쳐진 공격이다. 2017년 ROBOT 연구는 이 20년 된 공격이 여전히 여러 TLS 구현에 통한다는 것을 보였다. TLS 1.3이 RSA 키 전송 방식을 아예 없앤 이유 중 하나다.

사이드채널과 오류 주입

• 타이밍·전력 분석: square-and-multiply는 d의 비트에 따라 연산이 달라진다. Kocher(1996)가 실행 시간만으로 비밀 지수를 복원할 수 있음을 보였다. 라이브러리는 상수 시간 구현과 블라인딩(임의의 r에 대해 c × r^e를 복호화하고 나중에 r로 나눔)으로 막는다.
• CRT 오류 주입(Bellcore 공격): CRT 서명 중 p 쪽 계산에 오류가 하나라도 나면, 잘못된 서명 s' 하나로 gcd(s'^e - H(M), n) = q가 나온다. 전압이나 클럭을 흔들어 오류를 일으키는 스마트카드 공격, 메모리 비트 플립 등이 원인이 된다. 위 RSA-512 키로 p 쪽 결과(s1)의 비트 하나를 뒤집어 확인해 보면 실제로 q가 나온다. 그래서 라이브러리는 서명을 내보내기 전에 공개키로 한 번 검증한다.

import hashlib, math

H = int.from_bytes(hashlib.sha256(b"pwnblitz").digest(), "big")
s1 = pow(H, k.dmp1, p) ^ 1          # p 쪽 계산에 비트 하나 오류
s2 = pow(H, k.dmq1, q)
s_bad = s2 + (k.iqmp * (s1 - s2) % p) * q

print(math.gcd(pow(s_bad, e, n) - H, n) == q)   # True

그 밖에

• 공통 모듈러스: 여러 사용자에게 같은 n과 서로 다른 e, d를 나눠 주면, 한 사람이 자기 (e, d)로 n을 분해할 수 있다. 같은 평문을 두 e로 암호화하면 외부인도 확장 유클리드로 평문을 복원한다.
• ROCA(CVE-2017-15361): Infineon 칩의 키 생성 라이브러리가 특수한 구조의 소수를 만들어서, 공개키만 보고 분해할 수 있었다. 에스토니아 전자 신분증 인증서와 TPM(Trusted Platform Module) 키가 대량으로 재발급됐다.

키 길이와 지금의 위치

미국 NIST(National Institute of Standards and Technology)의 SP 800-57 Part 1은 RSA 키 길이와 대칭키 보안 강도를 이렇게 대응시킨다.

키를 두 배로 늘려도 보안 강도는 그만큼 늘지 않는다. GNFS 때문이다. 그래서 같은 강도에서 키가 훨씬 작은 ECC가 많이 대체했다.

더 근본적인 문제는 양자컴퓨터다. Shor 알고리즘은 소인수분해를 다항 시간에 푼다. 키를 늘리는 걸로는 막을 수 없어서, NIST는 2026년 10월 확정한 IR 8547에서 RSA를 포함한 기존 공개키 암호를 키 길이와 관계없이 2030년 이후 비권장(deprecated), 2035년 이후 사용 금지(disallowed)로 정했다. 다만 기존 방식과 PQC를 섞은 하이브리드 키교환은 PQC 쪽이 승인된 방식이면 계속 쓸 수 있다.

참고

• W. Diffie, M. Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory, 1976
• R. Rivest, A. Shamir, L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, 1978
• RFC 8017: PKCS #1 v2.2 RSA Cryptography Specifications
• FIPS 186-5: Digital Signature Standard
• D. Boneh, “Twenty Years of Attacks on the RSA Cryptosystem”, Notices of the AMS, 1999
• L. Valenta 외, “Factoring as a Service”, FC 2016
• N. Heninger 외, “Mining Your Ps and Qs”, USENIX Security 2012
• H. Böck, J. Somorovsky, C. Young, “Return Of Bleichenbacher’s Oracle Threat (ROBOT)”, USENIX Security 2018