RSA(Rivest–Shamir–Adleman)는 대형 소수의 곱으로 구성된 정수를 기반으로 동작하는 비대칭형 공개키 암호화 알고리즘이다.

개요

• RSA는 1977년 미국 매사추세츠공과대학교(MIT)의 론 리베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레오나르드 애들먼(Leonard Adleman)에 의해 고안되었으며, 이들의 이름 머리글자를 따서 알고리즘 이름이 붙여졌다.
• 공개키 암호화 방식 중 가장 오래되고 널리 사용되는 알고리즘으로, 이메일 암호화, 디지털 서명, SSL/TLS 등 다양한 분야에서 활용된다.
• RSA는 암호화와 복호화 시 서로 다른 키를 사용하는 비대칭키 구조로, 하나의 키는 공개되고, 다른 하나는 비밀로 유지된다.
• 주요 보안 기반은 큰 수의 소인수분해가 계산적으로 매우 어렵다는 수학적 문제에 의존한다.

동작 원리

RSA 알고리즘은 다음과 같은 수학적 절차를 따른다.

1. 두 개의 큰 소수 p와 q를 선택한다.
2. n = p × q를 계산하고, 오일러 피 함수 값인 φ(n) = (p - 1) × (q - 1)을 구한다.
3. 1 < e < φ(n)이면서 φ(n)과 서로소인 정수 e를 선택하여 공개키로 사용한다.
4. e에 대한 φ(n)의 곱셈 역원 d를 계산하여 개인키로 사용한다.
5. 공개키는 (e, n), 개인키는 (d, n)이다.
6. 평문 m은 암호문 c = m^e mod n으로 암호화되며, 복호화는 m = c^d mod n으로 수행된다.

RSA의 특징

• 계산적으로 안전성이 높은 알고리즘으로 간주되며, 이론적으로는 양자컴퓨터 등장 이전까지 실용적인 공격이 어렵다.
• 키 길이가 길어질수록 보안성은 증가하지만, 암호화·복호화 속도는 느려진다.
• 일반적으로 데이터 전체를 암호화하기보다는 대칭키를 암호화하는 데 사용된다.
• 전자서명 알고리즘으로도 널리 사용되며, 인증서 기반 보안 시스템의 핵심을 이룬다.

RSA를 이용한 세션 키 공유

모든 통신을 공개키 암호를 이용해 암호화하기엔 부하가 너무 크므로, 키 교환용으로만 사용하기도 한다.

1. A와 B는 대칭키를 이용한 암호화 통신을 하려고 한다.
2. A는 세션키를 생성해 B의 공개키로 암호화하여 B에게 보낸다.
3. B는 암호화된 세션키를 본인의 개인키로 복호화 한다.
4. A와 B는 안전한 방법으로 세션키를 공유한다.

보안성과 취약점

• RSA의 보안은 소인수분해의 난이도에 의존하므로, 키 길이가 짧으면 브루트포스 공격이나 수학적 기법으로 분석될 수 있다.
• 키 관리가 부실할 경우 개인키 유출 시 전체 보안이 붕괴된다.
• 타이밍 공격, 전력 분석 등 물리적 측면의 사이드채널 공격에도 노출될 수 있다.
• 양자컴퓨터의 등장으로 인해 RSA의 보안성에 대한 우려가 커지고 있으며, 이에 대응하기 위한 후양자 암호(post-quantum cryptography)가 연구되고 있다.

RSA와 ECC

효율성이 훨씬 높은 타원곡선암호의 등장으로 점유율이 빼앗기고 있다.

• RSA와 ECC의 비교

실제 활용

• HTTPS와 SSL/TLS 프로토콜의 인증 및 암호화
• 디지털 인증서 발급 및 검증 (X.509 기반)
• 전자서명 및 전자정부 서비스 인증
• 암호화 메일(PGP/GPG) 통신

같이 보기

• 공개키 암호화
• 타원곡선암호
• 디피-헬만 키 교환
• 전자서명
• 해시 함수

참고 문헌

• Rivest, R. L., Shamir, A., & Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, 21(2), 120–126.
• Stallings, W. (2017). Cryptography and Network Security: Principles and Practice (7th ed.). Pearson.

각주