RSA 알고리즘이란 무엇인가?
RSA는 개발자 세 명의 이름인 리베스트(Rivest), 샤미르(Shamir), 애들먼(Adleman)의 머리글자를 딴 것으로, 이들은 공개키 암호화 기술의 기반을 마련한 인물들입니다. RSA는 안전한 정보 전송을 위한 공개키 암호 시스템으로, 특히 인터넷을 통해 데이터를 주고받을 때 민감한 정보를 보호하는 표준 암호화 방식으로 자리 잡았습니다.
비대칭 암호화 방식의 대표주자
RSA(Rivest-Shamir-Adleman) 암호화 알고리즘은 다양한 제품과 서비스에서 폭넓게 활용되는 비대칭 암호화 알고리즘입니다. 이 방식에서는 개인키와 공개키 한 쌍이 생성되며, 공개키는 누구나 접근할 수 있지만 개인키는 키 쌍을 생성한 사람만이 알고 있습니다.
RSA에서는 개인키 또는 공개키 어느 쪽으로든 정보를 암호화할 수 있으며, 복호화에는 반대쪽 키가 사용됩니다. 이러한 유연성이 RSA가 가장 널리 쓰이는 비대칭 암호화 알고리즘 중 하나로 자리매김한 이유이기도 합니다.
소수와 RSA의 수학적 원리
소수(prime number)란 1과 자기 자신으로만 나누어 떨어지는 수를 말합니다. 예를 들어 3은 1과 3으로만 나눌 수 있으므로 소수지만, 4는 1과 4 외에도 2로 나누어지므로 소수가 아닙니다. 마찬가지로 5, 7, 11, 13, 17 등은 소수이며, 6, 8, 9, 10, 12는 소수가 아닙니다.
RSA 알고리즘은 "큰 소수를 찾아 서로 곱하는 것은 쉽지만, 그 곱(합성수)을 다시 두 소수로 인수분해하는 것은 극도로 어렵다"는 수학적 사실에 기반합니다. 덕분에 RSA는 공개키로 암호화하고 개인키로 복호화하는 기밀성(confidentiality)과 디지털 서명 기능을 모두 동등한 수준의 보안성으로 지원합니다.
RSA 기술의 역사와 활용 분야
RSA Information Security는 웹에서 데이터와 문서를 안전하게 연결·전송할 수 있게 하는 기술을 개척하고 상용화했으며, 가상 거래 상대방의 신원을 생성하고 인증하는 기능을 통해 디지털 상거래의 대중화에 결정적인 역할을 했습니다.
또한 이 기술은 도청자가 모바일 통화나 기타 디지털 통신을 엿듣는 것을 방지하는 데에도 활용됩니다. RSA의 기술은 흔히 공개키 암호(public-key encryption)라고 불리며, 컴퓨터와 컴퓨터 네트워크, 컴퓨터 정보를 변조 불가능하게 만드는 기존 방식보다 월등히 앞선 발전으로 평가받습니다.
RSA의 대수적 구조: 환과 군
RSA는 두 개의 지수 e와 d를 사용하며, e는 공개되고 d는 비공개로 유지됩니다. 평문을 P, 암호문을 C라고 할 때, RSA는 환(ring)과 군(group)이라는 두 가지 대수 구조를 활용합니다.
암호화/복호화 환(Encryption/Decryption Ring) — RSA는 덧셈과 곱셈이라는 두 가지 산술 연산을 포함하는 환 R = < Zn, +, × >를 필요로 합니다. RSA에서 이 환은 모듈러스 n이 공개되어 있기 때문에 공개된 상태이며, 누구나 이 환을 이용해 메시지를 암호화하여 전송할 수 있습니다.
키 생성 군(Key Generation Group) — RSA는 공개키와 개인키 생성에 필요한 곱셈과 나눗셈만을 제공하는 곱셈군 G = < Zφ(n), *, × >를 필요로 합니다. 이 군의 모듈러스인 φ(n)은 외부에 공개되지 않으므로, 해당 군 역시 비공개로 유지됩니다.