662. RSA 알고리즘 - 소인수분해 기반 가장 보편적인 공개키 암호

핵심 인사이트: 당신이 인터넷 쇼핑몰(HTTPS)에서 카드 번호를 칠 때, 그 번호가 해커에게 털리지 않는 이유는 1970년대에 세 명의 천재 수학자(Rivest, Shamir, Adleman)가 만든 RSA 알고리즘 덕분이다. 이들은 우주 나이보다 긴 시간이 걸리는 '거대 소수의 소인수분해'를 이용해, 인터넷을 떠다니는 공개키와 내 컴퓨터에 숨겨진 개인키의 완벽한 암호화 한 쌍을 창조해 냈다.

Ⅰ. RSA의 개념과 역사

1977년 MIT의 세 학자(Ron Rivest, Adi Shamir, Leonard Adleman)의 이름 앞 글자를 따서 명명된 인류 역사상 가장 유명하고 전 세계적으로 가장 널리 쓰이는 비대칭키(공개키) 암호화 알고리즘입니다.
인터넷 전자 상거래, 공인인증서(전자서명), SSL/TLS(HTTPS) 통신의 키 교환 등 모든 현대 보안의 근간이 되는 수학적 발명품입니다.

Ⅱ. RSA의 수학적 메커니즘 (어떻게 키를 만들까?) 🌟

RSA는 앞선 661번 문서에서 배운 **소인수분해 문제(Integer Factorization)**의 무지막지한 난해함을 이용합니다.

키 생성 (Key Generation)
- 두 개의 엄청나게 큰 소수(보통 수백 자리의 숫자) $p$와 $q$를 무작위로 고릅니다.
- 두 수를 곱해 $N$을 만듭니다 ($N = p \times q$).
- 복잡한 오일러 파이 함수와 모듈러 연산을 거쳐 두 개의 마법의 열쇠 $e$와 $d$를 뽑아냅니다.
- 결과물: ($N, e$)를 묶어서 인터넷에 널리 뿌리는 **'공개키(Public Key)'**로 삼고, $d$는 나만 몰래 간직하는 **'개인키(Private Key)'**로 숨깁니다.
기밀성 암호화 (앨리스가 나에게 편지를 보낼 때)
- 앨리스는 내 블로그에서 내 '공개키($N, e$)'를 다운받습니다.
- 평문(메시지)을 공개키 $e$승으로 곱하고 $N$으로 나눈 나머지(Mod)를 구하면 쓰레기 값(암호문)이 됩니다.
- 해커가 중간에 암호문과 내 공개키($N, e$)를 다 훔쳐봐도, $N$을 $p$와 $q$로 소인수분해 할 수 없어서 절대 풀지 못합니다. 오직 내 방에 숨겨둔 **개인키 $d$**로만 수학적으로 풀립니다.
전자 서명 (내가 진짜 작성자임을 증명할 때)
- 반대로 내가 공지사항을 내 **개인키 $d$**로 암호화(도장)해서 올리면, 전 세계 누구나 내 '공개키($N, e$)'를 곱해보고 평문이 툭 튀어나오는 것을 보고 "아! 진짜 본인 개인키로 쓴 글 맞네!"라고 증명할 수 있습니다.

Ⅲ. 현대 보안에서의 키 길이와 권고안 🌟

컴퓨터 CPU 속도가 기하급수적으로 빨라지면서 $N$을 소인수분해 해버리는 해커들의 연산 속도도 무서워졌습니다.
과거: 1024비트 길이의 키를 썼으나, 이제는 슈퍼컴퓨터에 뚫릴 위험이 생겼습니다.
현재 표준: NIST 등 글로벌 보안 기관들은 반드시 최소 2048비트(2048-bit) 길이 이상의 키를 사용할 것을 강력히 권고하고 있습니다. 2048비트는 숫자가 약 600자리에 달하는 크기라 현존 기술로는 해독이 불가능합니다.
은행이나 군사 등급의 극비 시스템은 3072비트 또는 4096비트를 씁니다.

Ⅳ. RSA의 한계점

치명적인 단점은 키의 길이가 너무너무 길고(2048비트), 이를 곱하고 나누는 지수 연산 과정이 CPU에 엄청난 부하를 준다는 것입니다. 일반 대칭키(AES)보다 연산 속도가 수천 배 느려, 대용량 파일 암호화에는 절대 쓰지 못하고 오직 짧은 '열쇠(대칭키)를 몰래 배달할 때'만 제한적으로 사용합니다.

📢 섹션 요약 비유: RSA의 방어력은 엄청나게 큰 두 숫자의 곱하기(소인수분해)에 숨어 있습니다. 해커에게 "15라는 숫자는 어떤 두 소수를 곱한 걸까?"라고 물으면 "3과 5요!"라고 1초 만에 풀 수 있지만, RSA가 만든 "600자리짜리 무작위 숫자가 어떤 두 소수의 곱일까?"라는 퀴즈는 전 세계 슈퍼컴퓨터를 수백만 년 돌려도 답을 찾을 수 없는 통곡의 벽입니다.