RSA

RSA 알고리즘의 키 생성 과정은 공개 키와 비밀 키라는 한 쌍의 키를 만드는 절차이다. 이 과정은 안전한 통신의 기초가 되며, 몇 가지 수학적 연산을 통해 이루어진다.

먼저, 두 개의 충분히 큰 소수 p와 q를 선택한다. 이 소수들은 비밀에 부쳐지며, 이들의 크기가 전체 시스템의 안전성에 직접적인 영향을 미친다. p와 q를 곱하여 합성수 n을 계산한다. 이 n은 모듈러 산술의 모듈러스로 사용되며, 공개 키와 비밀 키 모두에 포함되는 공개된 값이다. 다음으로 오일러 피 함수 φ(n)을 계산하는데, 이는 (p-1)과 (q-1)을 곱한 값, 즉 φ(n) = (p-1)(q-1)과 같다.

그 후, φ(n)과 서로소인 정수 e를 선택한다. 일반적으로 65537(2^16 + 1)과 같은 작은 홀수가 널리 사용되며, 이 e가 공개 키의 일부가 된다. 마지막으로, 확장 유클리드 알고리즘을 사용하여 모듈러 φ(n)에 대한 e의 모듈러 역원 d를 계산한다. 이는 e * d ≡ 1 (mod φ(n))을 만족하는 수로, 비밀 키의 핵심 구성 요소이다. 최종적으로 공개 키는 (n, e) 쌍으로, 비밀 키는 (n, d) 쌍으로 구성된다. 키 생성 후에는 민감한 소수 p, q 및 φ(n)을 안전하게 폐기해야 한다.

RSA 암호화와 복호화 과정은 공개 키와 개인 키라는 두 개의 다른 키를 사용하는 비대칭키 암호 방식의 핵심 원리를 보여준다. 송신자는 수신자의 공개 키를 사용하여 평문을 암호문으로 변환한다. 이 공개 키는 누구나 알 수 있는 정보이며, 두 개의 큰 소수의 곱인 모듈러스 n과 공개 지수 e로 구성된다. 암호화는 평문 메시지 m을 공개 키 (n, e)를 이용해 수식 c ≡ m^e (mod n)에 따라 계산하여 암호문 c를 생성하는 방식으로 이루어진다.

반대로, 복호화는 암호문을 원래의 평문으로 되돌리는 과정으로, 오직 수신자만이 소유한 개인 키를 필요로 한다. 이 개인 키는 공개 지수 e와 서로소인 카마이클 함수 값 λ(n)에 대한 모듈러 역수인 개인 지수 d로 구성된다. 수신자는 자신의 개인 키 (n, d)를 사용하여 수식 m ≡ c^d (mod n)을 계산함으로써 암호문 c로부터 원본 메시지 m을 복원한다. 이때 암호화에 사용된 공개 키와 복호화에 사용된 개인 키는 수학적으로 연결되어 있지만, 공개 키로부터 개인 키를 추론하는 것은 현실적으로 불가능하다.

이러한 비대칭적 특성은 키 배포 문제를 해결한다. 기존의 대칭키 암호 방식에서는 암호화와 복호화에 같은 키를 사용하기 때문에, 안전하게 키를 교환해야 하는 어려움이 있었다. 반면 RSA를 비롯한 공개 키 암호 방식에서는 암호화 키(공개 키)를 공개해도 복호화 키(개인 키)는 비밀로 유지되므로, 사전에 비밀 채널을 통해 키를 공유할 필요 없이 안전한 통신을 시작할 수 있다. 이는 디지털 서명이나 안전한 키 교환과 같은 다양한 정보 보안 응용의 기초가 된다.

암호화와 복호화 연산은 모듈러 지수 연산이라는 수학적 연산에 기반한다. 이 연산은 컴퓨팅 관점에서 비교적 비용이 많이 드는 작업이지만, 암호화 과정에서는 공개 지수 e를 작은 값(예: 65537)으로 선택하여 계산 효율성을 높일 수 있다. 복호화 과정은 개인 지수 d가 일반적으로 매우 크기 때문에 더 많은 계산 자원을 필요로 하지만, 중국인의 나머지 정리[5]를 활용하면 연산 속도를 크게 향상시킬 수 있다.

RSA의 안전성은 큰 정수의 소인수분해 문제가 어렵다는 사실에 기반한다. RSA에서 공개키는 두 개의 큰 소수 p와 q의 곱인 합성수 n과 공개 지수 e로 구성된다. 비밀키는 n의 소인수 p, q와 비밀 지수 d로 구성된다. 암호문을 복호화하거나 디지털 서명을 생성하는 데 필요한 비밀키 d는 p와 q를 알지 못하면 효율적으로 계산할 수 없다. 따라서 공격자가 공개키 n을 소인수분해하여 p와 q를 찾아낼 수 있다면, 비밀키 d를 복구하여 전체 시스템을 무너뜨릴 수 있다.

이러한 소인수분해 문제는 수학과 컴퓨터 과학에서 오랜 기간 연구된 난제이다. 현재까지 알려진 가장 효율적인 고전적 소인수분해 알고리즘은 일반 수체 체(GNFS)와 같은 방법이지만, 매우 큰 수(예: 2048비트 이상의 n)에 대해서는 현실적인 시간 내에 계산을 완료하는 것이 불가능한 것으로 여겨진다. 이 계산적 난이도가 RSA 암호의 핵심 보안 가정이다.

그러나 양자 컴퓨터의 발전은 이 가정에 위협이 될 수 있다. 쇼어 알고리즘은 양자 컴퓨터를 이용하여 소인수분해 문제를 다항 시간 내에 해결할 수 있는 알고리즘으로 알려져 있다. 만약 충분히 규모가 큰 양자 컴퓨터가 실현된다면, 현재 널리 사용되는 RSA 키 길이를 가진 시스템은 안전하지 않게 될 수 있다. 이에 대비하여 양자 내성 암호학 연구가 활발히 진행되고 있다.

따라서 RSA의 안전성은 키 길이에 크게 의존한다. 컴퓨팅 파워의 증가와 알고리즘의 발전에 대응하기 위해, 시간이 지남에 따라 권장되는 최소 키 길이는 점차 증가해왔다. 현재는 2048비트 길이의 키가 일반적으로 사용되며, 더 높은 보안 수준을 요구하는 경우에는 3072비트 또는 4096비트 키를 사용하기도 한다. 키 길이를 증가시키면 소인수분해에 필요한 계산량이 기하급수적으로 늘어나 공격을 현실적으로 불가능하게 만든다.

RSA 암호 체계의 안전성은 큰 수의 소인수분해가 어렵다는 문제에 기반한다. 따라서 RSA에 대한 주요 공격 방법은 이 수학적 문제를 우회하거나 효율적으로 해결하려는 시도들로 구성된다.

가장 직접적인 공격은 공개키인 모듈러스 n을 소인수분해하여 비밀키를 복구하는 것이다. 충분히 큰 n에 대해서는 양자 컴퓨터를 이용한 쇼어 알고리즘을 제외하고는 알려진 고전적 알고리즘으로 다항 시간 내에 해결하기 어렵다. 그러나 키의 크기가 충분히 크지 않거나, 생성 과정에서 난수 품질이 낮아 예측 가능한 소수가 사용된 경우, 공격자는 n을 효율적으로 인수분해할 수 있다. 이를 방지하기 위해 현대적 구현에서는 2048비트 이상의 큰 모듈러스를 사용한다.

소인수분해 외에도 다양한 수학적 공격이 존재한다. 공개 지수 e의 값이 너무 작을 경우(예: e=3), 특정 조건에서 공격이 성공할 수 있어, 일반적으로 e=65537과 같은 안전한 값이 권장된다. 또한, 동일한 메시지를 서로 다른 여러 수신자에게 암호화했을 때 발생할 수 있는 공통 모듈러스 공격이나, 비밀키 d의 일부 비트가 노출되었을 때 전체 키를 복원할 수 있는 부분 키 노출 공격 등이 연구되었다. 구현상의 결함을 이용한 부채널 공격도 위협이다. 이는 암호화 연산 중 발생하는 전력 소비나 전자기파 방출, 연산 시간 차이 등을 분석하여 비밀 정보를 유추하는 방식이다.

RSA는 공개 키 암호 방식의 대표적인 알고리즘으로, 데이터의 암호화와 복호화뿐만 아니라 디지털 서명을 생성하고 검증하는 데에도 핵심적으로 사용된다. 디지털 서명은 전자 문서의 무결성과 발신자의 신원을 보장하는 전자적 인증 수단이다. RSA를 이용한 디지털 서명은 서명자가 자신의 비밀키로 메시지 요약(해시) 값을 암호화하여 서명을 생성하고, 수신자는 서명자의 공개키로 이를 복호화하여 원본 해시 값과 비교함으로써 서명의 진위를 확인한다.

이 과정에서 서명 생성에 사용되는 키와 검증에 사용되는 키가 서로 다르기 때문에, 공개키를 아는 누구나 서명을 검증할 수 있지만 오직 비밀키를 가진 서명자만이 유효한 서명을 생성할 수 있다. 이는 종이 문서에 직접 서명하는 것과 유사한 효과를 디지털 세계에서 구현하며, 문서가 전송 중에 변조되지 않았음을 보장하고 부인 방지(부인 봉쇄)를 제공한다.

RSA 디지털 서명은 전자 상거래, 소프트웨어 배포, 전자 문서 관리 시스템 등 다양한 분야에서 널리 적용된다. 예를 들어, 소프트웨어 개발자는 배포 파일에 RSA 서명을 첨부하여 사용자가 파일의 출처와 무결성을 확인할 수 있게 한다. 또한, 많은 공개 키 인증서 표준과 전자 서명 법률의 기반 기술로 채택되어 있다.

RSA 서명의 안전성은 근본적으로 인수분해 문제의 난해함에 기반한다. 공격자가 서명을 위조하려면 서명자의 공개키로부터 비밀키를 유추해야 하는데, 이는 매우 큰 합성수를 소인수분해하는 문제와 동등하다. 따라서 충분히 큰 키 길이를 사용할 때 실질적으로 공격이 불가능한 것으로 간주된다.

RSA는 키 교환 과정에서도 중요한 역할을 한다. 키 교환은 통신 당사자들이 이후 대칭키 암호화에 사용할 공통의 비밀 키를 안전하게 공유하는 절차이다. RSA를 이용한 키 교환은 상대방의 공개 키로 세션 키를 암호화하여 전송하는 방식으로 이루어진다. 이렇게 암호화된 세션 키는 오직 해당 개인 키를 가진 수신자만 복호화할 수 있으므로, 제3자가 중간에서 키를 탈취하는 것을 방지한다.

이 방식은 SSL/TLS와 같은 보안 프로토콜의 초기 버전에서 널리 사용되었다. 예를 들어, 클라이언트는 서버의 RSA 공개 키로 자신이 생성한 대칭 키를 암호화하여 전송하고, 서버는 자신의 개인 키로 이를 복호화하여 동일한 대칭 키를 획득한다. 이후의 실제 데이터 통신은 이 공유된 대칭 키를 사용하여 더 빠르게 암호화 및 복호화한다.

그러나 RSA 기반 키 교환은 전달 공격에 취약할 수 있다는 점과 계산량이 많은 단점이 있다. 이러한 이유로 현대의 TLS 1.3과 같은 프로토콜에서는 보다 안전하고 효율적인 디피-헬먼 키 교환과 그 타원곡선 변형인 ECDH를 선호하며, RSA는 주로 서버의 신원을 인증하는 디지털 서명 용도로 사용되는 추세이다.