RSA란 무엇인가?
RSA는 공개키 암호 방식(public-key encryption)을 위한 암호 시스템으로, 인터넷처럼 보안이 취약한 네트워크를 통해 전송되는 민감한 정보를 보호하는 데 널리 사용됩니다.
RSA 암호화에서는 공개키와 개인키 어느 쪽으로도 메시지를 암호화할 수 있으며, 복호화에는 암호화에 사용된 키와 짝을 이루는 반대쪽 키가 사용됩니다. 이러한 특성 덕분에 RSA는 가장 폭넓게 활용되는 비대칭 암호 알고리즘이 되었습니다. RSA는 디지털 통신과 데이터 저장에 있어 기밀성(confidentiality), 무결성(integrity), 인증성(authenticity), 부인 방지(non-repudiation)를 보장하는 방법을 제공합니다.
키 생성의 기반: 곱셈군
RSA의 키 생성에는 곱셈군(multiplicative group) G = < Zφ(n), *, X >가 필요합니다. 이 군은 공개키와 개인키 생성에 필요한 곱셈과 나눗셈 연산만을 제공합니다. 이 군의 모듈러스인 φ(n)은 외부에 공개되지 않기 때문에, 군 자체도 외부에 비밀로 유지됩니다.
키 생성 절차의 핵심 요소
공개키와 개인키를 생성하는 알고리즘은 RSA 암호학에서 가장 까다로운 부분입니다. 먼저 라빈-밀러(Rabin-Miller) 소수 판별 알고리즘을 사용해 두 개의 매우 큰 소수 p와 q를 생성합니다.
그다음 p와 q를 곱하여 모듈러스(modulus) n을 계산합니다. 이 값은 공개키와 개인키 양쪽에서 모두 사용되며, 두 키 사이를 연결하는 고리 역할을 합니다. n의 길이(일반적으로 비트 단위로 표현)를 키 길이라고 부릅니다.
공개키는 모듈러스 n과 공개 지수(public exponent) e로 구성됩니다. e는 보통 65537로 설정되는데, 이는 너무 크지 않은 소수이기 때문입니다. 공개키는 누구에게나 공유되므로, e가 비밀리에 선택된 소수일 필요는 없습니다.
개인키는 모듈러스 n과 개인 지수(private exponent) d로 구성됩니다. d는 확장 유클리드 호제법(Extended Euclidean Algorithm)을 사용하여, n의 오일러 피함수(totient)에 대한 e의 곱셈 역원을 구하는 방식으로 계산됩니다.
주요 기호의 정의
모듈러 n에 대한 연산에서 e는 n의 오일러 피함수 φ(n)과 서로소(co-prime)인 정수입니다. 또한 d는 e의 φ(n) 모듈로 곱셈 역원입니다. 편의를 위해 각 기호의 정의를 정리하면 다음과 같습니다.
- n : 모듈러 연산에 사용되는 모듈러스
- φ(n) : n의 오일러 피함수(totient)
- e : φ(n)과 서로소인 정수 — 이 조건은 e가 φ(n) 모듈로에서 곱셈 역원을 가짐을 보장합니다
- d : e의 φ(n) 모듈로 곱셈 역원인 정수
키 생성 계산 단계
- 서로 다른 두 소수 p와 q를 생성합니다.
- 모듈러스 n = p × q 를 계산합니다.
- 오일러 피함수 φ(n) = (p − 1) × (q − 1) 을 계산합니다.
- 1 < e < φ(n) 이고 gcd(φ(n), e) = 1 을 만족하는 정수 e를 공개 지수로 선택합니다.
- d = e⁻¹ mod φ(n) 을 만족하는 값을 개인 지수 d로 계산합니다.
- 공개키(Public Key) = [e, n]
- 개인키(Private Key) = [d, n]
이렇게 생성된 개인키 d는 철저히 비밀로 유지해야 하며, 공개키 [e, n]은 자유롭게 배포할 수 있습니다. RSA의 안전성은 매우 큰 합성수 n을 다시 두 소수 p와 q로 분해하는 것이 현실적으로 불가능하다는 '큰 수의 소인수분해 난이도'에 근거합니다. 따라서 충분히 긴 키 길이(일반적으로 2048비트 이상)를 사용하는 것이 안전한 RSA 운용의 필수 조건입니다.