RSA 성능 해부: 왜 'Verification'은 매우 빠르고 'Signing'은 극도로 느린가?
Source: Dev.to
위의 링크에 있는 전체 텍스트를 제공해 주시면, 해당 내용을 한국어로 번역해 드리겠습니다. (코드 블록, URL 및 기술 용어는 그대로 유지됩니다.)
누가 숫자를 결정하나요?
키‑페어 생성자(키 페어의 소유자)가 숫자를 결정합니다.
아래는 세 가지 일반적인 질문에 답하는 자세한 순서입니다:
| 질문 | 답변 | 방법 |
|---|---|---|
| How is (d) determined? | Calculated via the Extended Euclidean Algorithm. | →→→ |
| How are keys distributed? | Written in an X.509 certificate and sent. | →→→ |
| How is the message turned into a number? | Pad the message, then convert it into a huge integer. | →→→ |
역할
| 행위자 | 지수 | 일반적인 크기 | 속도 |
|---|---|---|---|
| You (Client) | (e = 65537) (또는 다른 작은 공개 지수) | Small | Fast |
| Server | (d) (거대한 개인 지수) | Large | Slow |
Source:
기술 보충
1. (d) (개인키)는 어떻게 계산되나요?
(d)는 무작위 숫자가 아닙니다. 다음을 만족하는 유일한 정수입니다.
[ e \cdot d \equiv 1 \pmod{(p-1)(q-1)} ]
즉, ((p-1)(q-1)) 모듈로의 모듈러 곱셈 역원입니다.
소수인 (p)와 (q)를 알고 있는 서버만이 확장 유클리드 알고리즘을 사용해 이 방정식을 풀 수 있습니다.
2. 공개키 ((e,n))는 어떻게 배포되나요?
디지털 인증서 (X.509) 를 통해 배포됩니다. 인증서 안에는 다음과 유사한 구조가 포함됩니다.
Certificate:
Data:
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public-Key: (2048 bit)
Modulus: 00:C3:A7:1F:...:4D:RSA에 사용되는 이진 지수 승법(제곱‑곱) 알고리즘은 다음과 같습니다.
// If the current least‑significant bit is 1, multiply
if exponent % 2 == 1 {
result = (result * base) % modulus
}
// Square the base for the next bit
base = (base * base) % modulus
// Shift right to process the next bit
exponent /= 2
return resultRSA 워크플로우 요약
| 당사자 | 사용된 지수 | 일반적인 비용 |
|---|---|---|
| 서버 (서명자) | 개인 (d) (거대) | 느림 (무거운 모듈러 지수 연산) |
| 클라이언트 (검증자 / 암호화자) | 공개 (e) (작음) | 빠름 (가벼운 모듈러 지수 연산) |
무거운 연산은 서버(서명)에서 수행되고, 클라이언트의 검증은 비용이 적게 듭니다. 이러한 비대칭 때문에 RSA 기반 서명은 트래픽이 많은 서버에서 병목 현상이 될 수 있어, 검증은 동일하게 저렴하지만 서명도 CPU 부담이 훨씬 적은 ECDSA로 전환이 촉진됩니다.
Source: …
RSA 검증 vs. 서명 생성
검증
[ \text{Verification} \equiv s^{e}\pmod n ]
- 공개 지수 (e)는 (보안 요구 사항을 만족한다면) 임의로 선택할 수 있다.
- 값 65537이 관례적으로 사용되는 이유는 이진 거듭제곱 방법의 비용을 최소화하기 때문이다.
65537의 이진 표현
[ 65537_{10}=10000000000000001_{2} ]
- 비트 길이: 17비트
- 해밍 무게(1의 개수): 2 (선행 비트와 마지막 비트)
이진 거듭제곱 (Square‑and‑Multiply)
| 단계 | 연산 | 이유 |
|---|---|---|
| 시작 | (s) | – |
| 0 (15번 반복) | 제곱하고 (n)으로 나눔 | 중간 값을 작게 유지 |
| 1 (마지막) | 제곱, (s)와 곱한 뒤 (n)으로 나눔 | 거듭제곱을 완료 |
≈ 17개의 모듈러 곱셈만 필요하므로 RSA 검증(및 공개키 암호화)이 엄청나게 빠르다.
왜 65537이 “기적”인가
| 속성 | 이유 |
|---|---|
| 이진 방법에서 빠름 | 1비트가 매우 적음(1…0…1 패턴) |
| 소수 | 페르마 소수 (F_{4}=2^{2^{4}}+1) |
| 충분히 큼 | 작은 모듈러에 대한 공격을 방지 |
서명 생성 (비밀키 복호화)
[ \text{Signature} \equiv m^{d}\pmod n ]
- 비밀 지수 (d)는 임의로 선택되지 않는다.
- 다음을 만족해야 한다
[ e,d \equiv 1 \pmod{\phi(n)} ]
여기서 (\phi(n))은 오일러의 토션트 함수이다.
- 2048‑비트 모듈러의 경우, (d)는 대략 같은 크기(≈ 2048비트)이며 무작위처럼 보인다.
예시 (설명용)
[ d \approx 1101011\ldots00110_{2} ]
- 비트 길이: ≈ 2048비트 (RSA‑2048)
- 해밍 무게: ≈ 1024 (전체 비트의 절반 정도)
서명을 위한 이진 거듭제곱
| 연산 | 대략적인 횟수 |
|---|---|
| 제곱 | 2048 (비트당 한 번) |
| 곱 | 1024 (1비트당 한 번) |
| 전체 모듈러 곱셈 | > 3000 |
따라서 서명은 검증보다 수백 배 느리다.
“(d)를 작게 만든다면?”
작은 가중치의 (d)를 선택하면 (예: (e=65537) 만큼 계산하기 쉽게 만드는 경우) Wiener’s attack 또는 Boneh–Durfee attack와 같은 공격이 가능해지며, 이들은 ((e,n))으로부터 (d)를 복구할 수 있습니다.
RSA의 보안은 (d)가 크고 겉보기에 무작위인 정수일 때 유지됩니다; 그렇지 않으면 (n)을 소인수분해하지 않고도 개인 키를 유도할 수 있습니다.
TLS(SSL)에서의 비대칭 성능
| Party | Operation | Speed |
|---|---|---|
| Client | 공개키로 암호화 ((m^{e})) | 엄청 빠름 |
| Server | 개인키로 복호화 ((c^{d})) | 극히 느림 |
| Server | 서명 생성 ((m^{d})) | 극히 느림 |
| Client | 서명 검증 ((s^{e})) | 엄청 빠름 |
서버가 비용이 많이 드는 개인키 연산을 수행해야 하기 때문에, 많은 현대 시스템에서는 ECDSA(타원곡선 디지털 서명 알고리즘) 를 선호합니다. ECDSA는 서버 부하가 훨씬 가볍고(서명 생성이 빠름), 검증은 RSA보다 약간 느리지만 여전히 충분히 허용 가능한 수준입니다.
요약: 누가 무엇을 가지고 무엇을 계산하는가
증명자 (예: 서버) – “나는 주체이다”
| 값 | 설명 |
|---|---|
| (m) | 메시지의 해시 |
| (d) | 비밀 지수 (크고 비밀) |
| (n) | 모듈러스 (공개) |
| 계산 | (s = m^{d}\pmod n) (서명) |
| 특징 | 이진 방법이 여러 번 반복 → 높은 연산 비용 |
검증자 (예: 클라이언트) – “서명이 진짜인가?”
| 값 | 설명 |
|---|---|
| (s) | 받은 서명 |
| (m) | 로컬에서 계산된 메시지 해시 |
| (e) | 공개 지수 (보통 65537) |
| (n) | 모듈러스 (인증서에서) |
| 계산 | (\text{Check} = s^{e}\pmod n) |
| 판단 | (\text{Check}=m)이면 서명이 유효 |
| 특징 | (e)에 1비트가 적음 → 연산이 즉시 완료 |
RSA의 비대칭 비용(빠른 검증, 느린 서명)은 프로토콜 선택에 영향을 미치는 기본 설계 특성으로, 타원곡선 기반 대안 채택을 촉진합니다.