RSA는 암호화에 쓰는 키를 공개해도 복호화 키를 곧바로 알아내기 어렵게 만든 공개키 방식입니다. 1978년 로널드 리베스트, 아디 샤미르, 레너드 애들먼이 발표했습니다. 핵심 계산은 큰 두 소수의 곱과 모듈러 거듭제곱입니다. 교과서의 작은 숫자 예제는 구조를 보여 주지만 실제 보안에는 안전한 키 생성, 패딩, 난수, 구현 방어가 함께 필요합니다.
공개키는 (n,e), 개인키는 d이며, 교과서식 암호화와 복호화는 c=mᵉ mod n, m=cᵈ mod n으로 적습니다.
두 소수로 키를 만드는 순서
서로 다른 큰 소수 p와 q를 비밀로 고르고 n=pq를 계산합니다. 공개 지수 e는 λ(n)=lcm(p−1,q−1)과 서로소가 되도록 고릅니다. 그런 다음 ed≡1 (mod λ(n))을 만족하는 d, 즉 e의 모듈러 곱셈 역원을 구합니다. (n,e)는 공개하고 d와 소수 p,q는 보호합니다. 교재에서는 λ(n) 대신 오일러 피 함수 φ(n)=(p−1)(q−1)을 자주 쓰며, 그 조건으로도 RSA의 기본 관계를 설명할 수 있습니다.
e와 λ(n)이 서로소이면 확장 유클리드 알고리즘으로 d를 계산할 수 있습니다. n만 공개된 상태에서 λ(n)을 얻으려면 일반적으로 p와 q를 알아야 합니다. 충분히 크고 적절히 생성된 n을 소인수분해하는 문제가 고전 컴퓨터에서 어렵다는 사실이 RSA 보안 설계의 중요한 기반입니다.
작은 숫자로 확인하는 RSA
원리를 보기 위해 p=61, q=53을 고르면 n=3233이고 φ(n)=60×52=3120입니다. e=17은 3120과 서로소입니다. 17d≡1 (mod 3120)을 만족하는 d는 2753입니다. 메시지를 정수 m=65로 놓으면 암호문은 c=65¹⁷ mod 3233=2790이고, 2790²⁷⁵³ mod 3233을 계산하면 65로 돌아옵니다.
| 항목 | 예제 값 | 공개 여부 |
|---|---|---|
| p, q | 61, 53 | 비밀 |
| n | 3233 | 공개 |
| e | 17 | 공개 |
| d | 2753 | 비밀 |
| m→c | 65→2790 | 연산 예 |
실제 구현은 지수를 그대로 곱하지 않고 제곱-곱 방식으로 모듈러 거듭제곱을 효율적으로 계산합니다. 지수의 비트 수에 비례하는 횟수의 제곱과 곱으로 줄일 수 있습니다. 개인키 연산에서는 중국인의 나머지 정리를 이용해 p와 q 각각에 대해 계산한 뒤 합쳐 속도를 높이기도 합니다. 이때 중간값과 실행 시간이 비밀 정보를 새지 않도록 방어가 필요합니다.
복호화하면 원문으로 돌아오는 이유
키 생성에서 ed=1+kλ(n)인 정수 k가 존재하도록 d를 정합니다. 카마이클 함수 λ(n)의 정의에 따라 적절한 m에 대해 m^λ(n)≡1이 되고, 따라서 m^(ed)=m^(1+kλ(n))≡m (mod n)이 됩니다. p나 q와 서로소가 아닌 메시지까지 포함한 일반적인 경우도 p와 q에 대한 합동식을 각각 보인 뒤 중국인의 나머지 정리로 결론을 얻을 수 있습니다.
소인수분해와 RSA 역산은 같은 문제일까
n을 소인수분해해 p와 q를 얻으면 λ(n)을 계산하고 개인 지수 d를 찾을 수 있으므로 RSA를 풀 수 있습니다. 그러나 임의의 RSA 암호문을 복호화하는 모든 방법이 곧바로 n의 소인수분해 방법이 된다는 동치성은 일반적으로 증명되어 있지 않습니다. 따라서 ‘RSA를 깨는 문제는 소인수분해와 완전히 동일하다’고 단정하기보다, 소인수분해의 어려움이 핵심 기반이며 알려진 공격과 구현 조건을 함께 고려한다고 설명하는 것이 정확합니다.
교과서 RSA를 그대로 쓰면 안 되는 이유
c=mᵉ mod n만 쓰는 교과서 RSA는 같은 키와 같은 메시지에서 언제나 같은 암호문이 나오는 결정적 연산입니다. 공격자는 예상 메시지를 직접 암호화해 대조할 수 있고, 모듈러 곱셈 구조 때문에 암호문을 변형했을 때 평문에도 예측 가능한 관계가 생깁니다. 메시지 공간이 작거나 형식이 알려졌다면 특히 위험합니다.
실제 암호화에는 RSA-OAEP처럼 검증된 확률적 인코딩을 사용합니다. 디지털 서명에는 RSA-PSS 같은 서명 인코딩이 권고됩니다. 암호화 패딩과 서명 패딩은 목적이 다르며 서로 바꿔 쓰지 않습니다. 임의로 만든 패딩이나 오래된 취약한 사용 방식을 새 시스템에 적용해서도 안 됩니다.
긴 문서를 RSA로 직접 암호화하지 않는다
RSA가 처리할 수 있는 메시지 길이는 모듈러스와 패딩 규격에 제한됩니다. 실제 시스템은 빠른 대칭키를 무작위로 만들고, 본문은 인증된 대칭키 암호로 처리하며, RSA는 그 짧은 키 자료를 보호하는 하이브리드 구조를 사용합니다. 이렇게 하면 큰 자료를 효율적으로 암호화하면서 공개키 방식의 키 전달 장점을 얻습니다.
서명은 개인키로 암호화하는 것과 같을까
RSA 서명과 복호화는 모두 개인 지수를 사용하는 모듈러 연산이라는 공통점이 있습니다. 하지만 실제 서명은 메시지의 해시를 규격에 맞게 인코딩하고 RSA-PSS 같은 검증된 방식으로 처리합니다. ‘개인키로 메시지를 암호화한 것’이라는 표현은 해시, 인코딩, 검증 규칙과 보안 목적을 감추므로 실제 프로토콜 설명으로는 부족합니다.
키 생성과 구현에서 생기는 위험
p와 q는 암호학적으로 안전한 난수원으로 생성하고 소수성 검사를 거쳐야 합니다. 여러 장치가 난수 부족으로 같은 소인수를 공유하면 공개된 모듈러스들의 최대공약수만 계산해도 인수분해될 수 있습니다. 개인키 연산 시간, 전력 소비, 오류 출력도 비밀키에 관한 정보를 흘릴 수 있어 일정 시간 연산, 블라인딩, 오류 검증 같은 대책을 사용합니다.
공개키를 받았다고 그 키의 소유자가 자동으로 확인되는 것도 아닙니다. 인증서와 신뢰 체계, 미리 공유한 지문 등으로 공개키와 신원을 연결해야 중간자 공격을 막을 수 있습니다. 암호 알고리즘의 수학적 강도와 키 배포의 신뢰성은 별개의 보안 문제입니다.
양자 계산과 현재의 전환
충분히 큰 오류보정 양자컴퓨터에서 쇼어 알고리즘은 정수 소인수분해를 효율적으로 수행할 수 있어 RSA를 위협합니다. 이것은 현재의 일반 컴퓨터에서 큰 RSA 모듈러스가 이미 즉시 분해된다는 뜻은 아닙니다. 장기간 비밀을 지켜야 하는 시스템은 표준기관의 전환 지침과 양자내성 암호 표준을 따라 계획적으로 교체해야 합니다.
디피-헬만과의 차이
디피-헬만 키 교환의 이산로그 계산은 양쪽이 공개 채널에서 공동 비밀을 만드는 방식입니다. RSA는 정수 인수분해와 연결된 공개키 연산으로 암호화·서명 계열을 구성합니다. 둘 다 공개키 암호에 속하지만 문제 가정과 프로토콜 목적이 같지 않으며, 어느 쪽이든 인증과 안전한 인코딩 또는 키 유도 절차가 필요합니다.
정확하게 이해하기 위한 점검표
- RSA는 큰 소수 자체가 아니라 두 큰 소수의 곱 n을 공개합니다.
- φ(n) 또는 λ(n)과 서로소인 e를 고르고 그 모듈러 역원 d를 구합니다.
- 교과서식 RSA를 실제 데이터에 직접 사용하지 않고 OAEP 또는 PSS 같은 규격을 적용합니다.
- RSA 역산과 인수분해가 완전히 동치라고 증명되었다고 말하지 않습니다.
- 난수, 공개키 인증, 부채널 방어와 키 관리까지 보안 범위에 포함합니다.
키 크기는 임의로 정하지 않는다
RSA의 안전성은 모듈러스의 비트 수만으로 결정되지 않습니다. 소수 생성 방식, 패딩, 해시 함수, 키의 사용 기간과 보호할 정보의 수명을 함께 봐야 합니다. 필요한 키 크기와 허용 용도는 시간이 지나며 바뀔 수 있으므로 과거 예제의 숫자를 기준으로 삼지 않고 적용 시점의 NIST 등 관련 표준과 조직 보안정책을 확인해야 합니다. 오래된 키를 새 규격으로 옮길 때는 인증서, 서명 검증 기간, 보관된 암호문까지 포함한 전환 계획이 필요합니다.