RSA 알고리즘이란?
RSA 알고리즘은 공개키(public key)와 개인키(private key)라는 서로 다른 두 개의 키를 사용하는 대표적인 비대칭(공개키) 암호화 방식입니다. 공개키는 누구에게나 공개되며, 개인키는 소유자만 안전하게 보관합니다. 공개키는 두 개의 숫자로 구성되는데, 그중 하나는 두 개의 매우 큰 소수를 곱한 값입니다.
소인수분해의 어려움에 기반한 보안
RSA 알고리즘의 보안은 매우 큰 수를 소인수분해하는 것이 사실상 불가능하다는 수학적 사실에 근거합니다. 현재까지 초대형 수를 효율적으로 인수분해할 만한 방법이 없기 때문에, RSA 키를 무단으로 추론하려면 막대한 시간과 연산 능력이 필요합니다.
공개키 암호화와 개인키 복호화
RSA 암호화에서 메시지는 숨길 필요가 없는 공개키로 암호화됩니다. 공개키로 암호화된 메시지는 RSA의 수학적 특성 덕분에 오직 짝이 되는 개인키로만 복호화할 수 있습니다. 따라서 이러한 메시지를 읽으려면 공개키와 개인키로 이루어진 한 쌍의 키가 반드시 필요합니다.
계산은 쉽고 역산은 어렵다
RSA의 보안성은 두 개의 큰 소수를 곱해 만든 거대한 정수를 인수분해하는 데서 나옵니다. 두 수를 곱하는 것은 아주 간단하지만, 그 결과값에서 원래의 소수들을 다시 찾아내는 것은 극도로 어렵습니다. 슈퍼컴퓨터를 사용하더라도 상당한 시간이 걸린다는 점이 RSA 알고리즘의 강점이자 단점입니다.
키 생성 과정: 라빈-밀러(Rabin-Miller) 소수 판별
RSA 암호화에서 가장 중요한 부분은 공개키와 개인키를 생성하는 알고리즘입니다. 키 생성 시에는 라빈-밀러(Rabin-Miller) 소수 판별법 등을 통해 두 개의 큰 소수 p와 q를 검증합니다. 이후 p와 q를 곱하여 모듈러스(modulus) n을 계산하는데, 이 n은 공개키와 개인키 양쪽 모두에 사용됩니다. 여기서 말하는 키 길이(key length)는 n의 비트(bit) 길이를 의미하며, 일반적으로 비트 단위로 정의됩니다.
디지털 서명 및 하이브리드 암호화 활용
RSA 암호화는 단독으로 사용되기보다는 다른 암호화 방식과 결합하거나, 메시지의 진위성(authenticity)과 무결성(integrity)을 검증하는 디지털 서명 용도로 널리 활용됩니다. 대칭키 암호화에 비해 효율이 낮고 자원 소모가 크기 때문에, 메시지 전체나 파일 전체를 암호화하는 용도로는 적합하지 않습니다.
무작위 소수가 만드는 복잡성
RSA 공개키의 복잡성은 두 개의 크고 무작위로 생성된 소수 인수에서 비롯됩니다. 이 숫자들은 무작위 방식으로 생성되며, RSA 알고리즘은 소인수분해를 일방향(one-way) 암호화 방식으로 사용하기 때문에 그 보안 전제 역시 여기에 완전히 의존합니다.
TLS, PGP, VPN 등 실제 활용 분야
RSA는 TLS(Transport Layer Security)와 함께 사용되어 두 당사자 간의 통신을 보호하는 데 활용되어 왔습니다. 또한 PGP(Pretty Good Privacy)와 같은 유명한 암호화 제품과 알고리즘에서도 현재든 과거든 RSA를 사용해 왔습니다. 그 외에도 VPN(가상사설망), 이메일 서비스, 웹 브라우저, 다양한 연결 채널에서 RSA가 폭넓게 사용되고 있습니다.