RSA 공개키 암호

핵심 정리

RSA는 공개키 기반 암호 방식이다. 공개키 암호 알고리즘은 트랩도어 단방향 함수에 기반한다. 누구나 공개된 키로 메시지를 암호화할 수 있지만, 그 암호문을 열람할 수 있는 사람은 짝이 되는 비밀 키를 가진 한 사람뿐이다. 이 점이 공개키 암호를 대칭키 암호와 구별하는 기본 틀이다.

RSA는 공개키로 암호화하고 개인키로 복호화하는 공개키 암호 알고리즘이다. RSA의 키 쌍에서 개인키는 개인키는 공개하지 않고 비밀로 유지한다. 공개키는 {e,n}이고 개인키는 {d,n}이며, 두 키는 같은 모듈러스 n을 공유한다. 송신자는 수신자의 공개키로 평문을 암호화하고, 수신자는 자신의 개인키로만 그 암호문을 복호화한다.

RSA는 큰 정수의 소인수분해 문제에 기반한 대표적인 공개키 암호 알고리즘이다. 소인수분해는 큰 수를 소수들의 곱으로 나누는 계산이다. 두 소수를 곱하는 것은 쉽지만 곱해진 결과에서 두 소수를 되찾는 것은 소인수분해의 어려움이다. 이 차이가 RSA 설계의 바탕이다.

RSA는 쇼어 알고리즘을 이용한 양자 컴퓨터 공격에 안전하지 않다. 따라서 RSA의 안전성은 현재의 계산 환경을 전제로 한 것이며, 영구적인 보장으로 받아들이면 안 된다. 이 한계는 인수분해가 어렵다는 전제가 깨지는 경우에 드러난다.

OAEP는 RSA 암호의 안전성을 높이기 위한 메시지 패딩 규격이다. RSA는 평문을 그대로 계산하지 않고 패딩을 붙인 뒤 암호화하는 구성으로 쓰인다. 키 길이와 관련해서는 키 길이가 길수록 안전성은 높아지지만 알고리즘 수행시간은 길어진다. 이 관계 때문에 키 길이를 고를 때는 안전성과 속도를 함께 고려해야 한다.

자세히

키 구조와 기밀성

RSA의 요건은 공개키와 개인키가 짝을 이룬다는 데서 출발한다. 공개키는 모두에게 알려져 있어도 되지만 개인키는 소유자 한 사람만 가져야 한다. 발신자는 공개키만 있으면 암호문을 만들 수 있으나, 그 암호문을 열어 보려면 개인키가 있어야 한다. 도청자가 암호문과 공개키를 모두 알고 있어도 개인키가 없으면 평문을 얻을 수 없다는 점이 기밀성 효과의 근거다.

효과에는 한계도 있다. 메시지와 공개키를 모두 알 수 있으면 변조된 메시지를 보낼 수 있으므로, 실제로는 수신측의 공개키만으로 암호화하는 경우는 드물다. 대신 송수신 양측의 키쌍을 함께 쓰는 방법이 쓰인다. 개인키를 가진 자만 복호화할 수 있다는 구조는 해독 가능한 사람을 단 한 사람으로 한정하는 효과가 있다.

소인수분해 난제와 트랩도어

RSA 안전성의 근거는 n을 소인수분해하는 일이 어렵다는 데 있다. 공개키 {e,n}에서 n을 소인수분해할 수 있으면 개인키 {d,n}의 d를 알아낼 수 있다. 따라서 n의 분해 난이도가 개인키 보호의 강도를 정한다.

트랩도어 단방향 함수는 정방향 계산은 쉽고 역방향 계산은 비밀 정보 없이는 어려운 함수다. 비밀 정보를 가진 소유자만 역연산을 쉽게 할 수 있다는 점이 공개키 알고리즘의 설계 원리가 된다. 소인수분해 난제에 기대는 것은 RSA와 Rabin 암호이고, 다른 공개키 알고리즘은 이산대수 난제에 기댄다.

다른 공개키 알고리즘과의 비교

RSA와 함께 묻는 공개키 알고리즘은 ElGamal이다. ElGamal은 디피헬만 키 교환을 확장한 방식으로, 암·복호화와 전자서명을 모두 지원한다. ElGamal은 이산대수 문제의 어려움에 기초를 둔 공개키 알고리즘이다. RSA와 ElGamal은 암호화와 복호화에 서로 다른 키를 쓰는 비대칭키 알고리즘이다.

Rabin 암호는 RSA와 같은 방식으로 암호화하며 2차 합동식에 근거한다. RSA와 Rabin은 같은 소인수분해 난제에 기대는 점에서 함께 비교된다. 안전성의 근거를 한눈에 보면 다음과 같다.