RSA 암호화 단계별 시뮬레이터

RSA 암호화란 무엇인가요?

RSA(Rivest-Shamir-Adleman)는 1977년 론 리베스트, 아디 샤미르, 레너드 애들먼에 의해 발표된 최초의 공개키 암호 시스템 중 하나입니다. 동일한 키로 암호화와 복호화를 수행하는 대칭 암호화와 달리, RSA는 키 쌍(key pair)을 사용합니다. 누구나 암호화에 사용할 수 있는 공개키와 소유자만이 복호화에 사용할 수 있는 개인키로 구성됩니다.

RSA의 수학적 보안은 정수 분해 문제에 기반합니다. 두 개의 큰 소수를 곱하는 것은 매우 쉽지만, 그 결과물을 다시 소인수분해하는 것은 숫자가 충분히 클 때 계산적으로 불가능에 가깝기 때문입니다.

RSA 키 생성 과정

RSA 키 생성 과정은 다음과 같은 5가지 기본 단계로 이루어집니다:

• 단계 1 – 소수 선택: 서로 다른 두 개의 큰 소수 p와 q를 선택합니다. 소수가 클수록 키가 더 안전해집니다.
• 단계 2 – 모듈러스 계산: n = p × q를 계산합니다. n의 비트 길이에 따라 키 크기(예: 2048비트)가 결정됩니다.
• 단계 3 – 오일러 피 함수: φ(n) = (p−1)(q−1)을 계산합니다. 이 값은 e를 선택하고 d를 계산하는 데 핵심적인 역할을 합니다.
• 단계 4 – 공개 지수: 1 < e < φ(n) 이고 gcd(e, φ(n)) = 1을 만족하는 e를 선택합니다. 표준적인 선택은 65537입니다.
• 단계 5 – 개인 지수: 확장 유클리드 알고리즘을 사용하여 d × e ≡ 1 (mod φ(n))을 만족하는 d를 계산합니다.

확장 유클리드 알고리즘

개인 지수 d를 구하려면 φ(n)에 대한 e의 모듈러 곱셈 역원을 찾아야 합니다. 확장 유클리드 알고리즘은 표준 GCD 알고리즘을 확장하여 a·x + b·y = gcd(a, b)를 만족하는 계수 x와 y를 함께 찾아냄으로써 이를 효율적으로 해결합니다.

gcd(e, φ(n)) = 1일 때, 이 알고리즘은 e·x ≡ 1 (mod φ(n))을 만족하는 x를 도출하며, 이때 d = x mod φ(n)이 됩니다.

RSA 보안 고려 사항

• 키 크기: 현대의 RSA는 2048 또는 4096비트 키를 사용합니다. 이 시뮬레이터에서 사용되는 작은 소수들은 교육용일 뿐이며 즉시 해독될 수 있습니다.
• 패딩 방식: 실제 환경의 RSA 구현은 원시 RSA에 대한 수학적 공격을 방지하기 위해 패딩(OAEP, PKCS#1)을 사용합니다.
• 성능: RSA는 대칭 암호화보다 훨씬 느립니다. 실제로는 RSA로 무작위 대칭키를 암호화하여 전달하고, 그 대칭키로 실제 데이터를 암호화하는 혼합 암호화(hybrid encryption) 방식을 사용합니다.
• 양자 위협: 충분히 강력한 양자 컴퓨터에서 쇼어(Shor) 알고리즘을 실행하면 큰 수를 효율적으로 소인수분해할 수 있어 RSA를 위협할 수 있습니다. 이에 대한 대응책으로 양자 내성 암호가 개발되고 있습니다.

RSA의 실질적 활용

• TLS/SSL (HTTPS): 웹 브라우징 시 대칭 세션 키를 안전하게 교환하기 위해 핸드셰이크 과정에서 RSA가 사용됩니다.
• 전자 서명: 개인키로 해시를 암호화하여 문서에 서명하고, 공개키로 이를 검증하여 무결성을 확인합니다.
• 이메일 암호화: PGP 및 S/MIME은 이메일 통신 암호화에 RSA를 활용합니다.
• SSH 인증: RSA 키 쌍은 원격 서버 접속을 위한 비밀번호 없는 인증을 제공합니다.
• 코드 서명: 소프트웨어 개발사는 RSA로 실행 파일을 서명하여 진위 여부와 변조되지 않았음을 증명합니다.

자주 묻는 질문 (FAQ)