Gaon12: 시작

2026-01-12T05:38:50Z

시작

새 문서

== 개요 ==
'''RSA 암호'''(RSA cryptosystem)는 1977년 [[론 라이베스트]](Ron Rivest), [[아디 샤미르]](Adi Shamir), [[레너드 애들먼]](Leonard Adleman) 세 사람이 개발한 [[공개키 암호]] 시스템이다.<ref>세 사람의 성(姓)의 첫 글자를 따서 RSA라고 명명했다.</ref>

현대 인터넷 보안의 근간을 이루는 암호화 기술로, [[HTTPS]], [[SSL/TLS]], [[전자서명]], [[VPN]] 등 우리가 매일 사용하는 수많은 보안 시스템에서 활용되고 있다.<ref>당신이 지금 보고 있는 이 웹페이지도 RSA로 암호화되어 있을 가능성이 높다.</ref>

RSA의 가장 큰 특징은 '''암호화 키와 복호화 키가 서로 다르다'''는 것이다. 기존의 [[대칭키 암호]]와 달리, 공개키로 암호화한 데이터는 오직 대응하는 개인키로만 복호화할 수 있다. 이 혁신적인 아이디어 덕분에 사전에 비밀 키를 교환할 필요 없이 안전하게 통신할 수 있게 되었다.

== 역사 ==
=== 탄생 배경 ===
1976년, [[위트필드 디피]](Whitfield Diffie)와 [[마틴 헬먼]](Martin Hellman)이 혁명적인 논문 "New Directions in Cryptography"를 발표하면서 '''공개키 암호'''라는 개념을 처음 제시했다. 그러나 이들은 구체적인 구현 방법은 제시하지 못했다.<ref>개념만 던져놓고 "누가 만들어봐~"한 셈이다.</ref>

=== RSA의 탄생 ===
1977년, [[MIT]]의 세 교수가 이 문제를 해결했다. 론 라이베스트가 알고리즘을 고안했고, 아디 샤미르가 수학적 증명을 담당했으며, 레너드 애들먼은 보안성을 분석했다.<ref>사실 애들먼은 처음엔 "이거 안 될 거야"라고 회의적이었다고 한다.</ref>

재미있는 일화가 있다. 라이베스트는 1977년 [[유월절]] 전날 밤, 친구들과 와인을 마신 후 집에 돌아와 소파에 누워 있다가 갑자기 RSA 알고리즘을 떠올렸다고 한다. 그는 새벽까지 논문을 완성했고, 이것이 암호학 역사상 가장 중요한 논문 중 하나가 되었다.<ref>천재의 영감은 소파에서 나온다는 교훈...</ref>

=== 특허와 공개 ===
RSA 알고리즘은 1983년 미국에서 특허를 받았고(US 4,405,829), 2000년 9월 특허가 만료되었다. 특허 기간 동안 '''RSA Security'''라는 회사가 라이선스를 관리했으며, 상당한 수익을 올렸다.

한편 영국의 [[GCHQ]](정보통신본부)에서는 RSA보다 '''4년 먼저''' 같은 원리의 암호를 개발했다는 사실이 1997년에 공개되었다. [[제임스 엘리스]], [[클리퍼드 콕스]], [[말콤 윌리엄슨]]이 1973년에 이미 공개키 암호를 개발했지만, 군사 기밀로 분류되어 공개되지 못했다.<ref>역시 군대는 뭐든 먼저 만들고 숨긴다.</ref>

== 작동 원리 ==
RSA는 '''큰 소수의 곱셈은 쉽지만, 그 결과를 다시 소인수분해하는 것은 매우 어렵다'''는 수학적 난제를 기반으로 한다.

=== 기본 개념 ===
RSA는 다음과 같은 특징을 가진다:
* '''공개키'''(Public Key): 누구에게나 공개되며, 데이터를 암호화하는 데 사용
* '''개인키'''(Private Key): 자신만 가지고 있으며, 데이터를 복호화하는 데 사용
* 공개키로 암호화한 것은 대응하는 개인키로만 복호화 가능
* 개인키로 서명한 것은 대응하는 공개키로만 검증 가능

=== 키 생성 과정 ===
RSA 키를 생성하는 과정은 다음과 같다:

'''1단계: 두 개의 큰 소수 선택'''
* 서로 다른 두 개의 큰 소수 p와 q를 무작위로 선택한다.
* 예시: p = 61, q = 53<ref>실제로는 수백 자리의 소수를 사용한다. 61이나 53 같은 건 초등학생도 소인수분해할 수 있다.</ref>

'''2단계: n 계산'''
* n = p × q를 계산한다.
* 예시: n = 61 × 53 = 3233
* 이 n이 '''RSA 모듈러스'''(RSA modulus)라고 불리며, 공개키와 개인키 모두에 포함된다.

'''3단계: 오일러 함수 φ(n) 계산'''
* φ(n) = (p-1) × (q-1)을 계산한다.
* 예시: φ(3233) = 60 × 52 = 3120
* φ(n)은 n보다 작으면서 n과 서로소인 양의 정수의 개수를 의미한다.<ref>[[오일러]]가 만든 함수다. 수학자들은 그리스 문자를 정말 좋아한다.</ref>

'''4단계: 공개 지수 e 선택'''
* 1 < e < φ(n)이면서 φ(n)과 서로소인 정수 e를 선택한다.
* 보통 e = 65537 (= 2^16 + 1)을 많이 사용한다.<ref>65537은 [[페르마 소수]]다. 계산이 빠르면서도 보안성이 좋아서 자주 쓰인다.</ref>
* 예시: e = 17

'''5단계: 개인 지수 d 계산'''
* d × e ≡ 1 (mod φ(n))을 만족하는 d를 구한다.
* 즉, d는 e의 모듈러 역원이다.
* [[확장 유클리드 호제법]]을 사용하여 계산한다.
* 예시: d = 2753<ref>왜냐하면 2753 × 17 = 46801 = 15 × 3120 + 1이기 때문</ref>

'''6단계: 키 생성 완료'''
* '''공개키''': (n, e) = (3233, 17)
* '''개인키''': (n, d) = (3233, 2753)
* p, q, φ(n)은 '''반드시 폐기'''해야 한다!<ref>이걸 남겨두면 보안이 뚫린다. 마치 금고를 만든 후 설계도를 버리지 않는 것과 같다.</ref>

=== 암호화 과정 ===
평문 메시지 M을 암호화하여 암호문 C를 만드는 과정:

'''수식:''' C ≡ M^e (mod n)

'''예시:'''
* 평문: M = 123
* 공개키: (n=3233, e=17)
* 암호화: C = 123^17 mod 3233 = 855

이제 누구든 공개키 (3233, 17)을 알면 메시지를 암호화할 수 있지만, 개인키 없이는 복호화할 수 없다!

'''실제 계산 과정:'''
123^17 mod 3233을 직접 계산하는 것은 비효율적이다. 대신 '''제곱-곱셈 알고리즘'''(Square-and-Multiply)을 사용한다:
* 17 = 2^4 + 2^0 = 16 + 1
* 123^17 = 123^16 × 123^1
* 123^2 mod 3233 = 15129 mod 3233 = 1926
* 123^4 mod 3233 = 1926^2 mod 3233 = 2830
* 123^8 mod 3233 = 2830^2 mod 3233 = 2746
* 123^16 mod 3233 = 2746^2 mod 3233 = 2728
* 123^17 mod 3233 = 2728 × 123 mod 3233 = 855

=== 복호화 과정 ===
암호문 C를 복호화하여 평문 M을 복원하는 과정:

'''수식:''' M ≡ C^d (mod n)

'''예시:'''
* 암호문: C = 855
* 개인키: (n=3233, d=2753)
* 복호화: M = 855^2753 mod 3233 = 123

원래 평문 123이 복원되었다!<ref>마법같지만 수학이다.</ref>

=== 왜 작동하는가? ===
RSA가 작동하는 이유는 [[페르마의 소정리]]와 [[오일러 정리]]에 기반한다.

'''수학적 증명:'''
* M^(ed) ≡ M (mod n)임을 증명해야 한다.
* d × e ≡ 1 (mod φ(n))이므로, d × e = 1 + k × φ(n) (k는 정수)
* 따라서 M^(ed) = M^(1 + k×φ(n)) = M × (M^φ(n))^k
* [[오일러 정리]]에 의해 M^φ(n) ≡ 1 (mod n) (M과 n이 서로소일 때)
* 따라서 M^(ed) ≡ M × 1^k ≡ M (mod n)

이 증명은 '''M과 n이 서로소'''일 때 성립한다. 만약 M이 p나 q의 배수라면? 그래도 [[중국인의 나머지 정리]]를 사용하면 증명할 수 있다.<ref>수학자들은 구멍을 남기지 않는다.</ref>

== 구체적인 예제 ==
=== 작은 숫자로 이해하기 ===
실제 상황에서는 수백 자리 숫자를 사용하지만, 원리를 이해하기 위해 작은 숫자로 예를 들어보자.

'''앨리스와 밥의 통신:'''

'''1. 밥의 키 생성'''
* 밥이 두 소수 선택: p = 3, q = 11
* n = 3 × 11 = 33
* φ(n) = 2 × 10 = 20
* 공개 지수 선택: e = 3 (20과 서로소)
* 개인 지수 계산: d = 7 (3 × 7 = 21 = 1 + 1×20)
* 밥의 공개키: (33, 3)
* 밥의 개인키: (33, 7)

'''2. 앨리스의 암호화'''
* 앨리스가 보낼 메시지: M = 4
* 밥의 공개키 (33, 3)으로 암호화
* C = 4^3 mod 33 = 64 mod 33 = 31

'''3. 밥의 복호화'''
* 받은 암호문: C = 31
* 밥의 개인키 (33, 7)로 복호화
* M = 31^7 mod 33 = ?

31^7을 계산해보자:
* 31^2 = 961 mod 33 = 4
* 31^4 = 4^2 = 16 mod 33 = 16
* 31^7 = 31^4 × 31^2 × 31 = 16 × 4 × 31 mod 33 = 1984 mod 33 = 4

원래 메시지 4가 복원되었다!

=== 텍스트 암호화하기 ===
실제로 문자를 암호화하려면 어떻게 할까?

'''방법:'''
* 각 문자를 숫자로 변환 (예: A=01, B=02, ..., Z=26)
* 메시지 "HI"를 암호화한다면:
** H = 08, I = 09 → 메시지 = 0809 또는 따로따로 암호화

'''예시 (키: n=3233, e=17, d=2753):'''
* 평문: "HI" = 08, 09
* 암호화:
** 08^17 mod 3233 = 2082
** 09^17 mod 3233 = 2489
* 암호문: [2082, 2489]
* 복호화:
** 2082^2753 mod 3233 = 08
** 2489^2753 mod 3233 = 09
* 평문: "HI" 복원!

실제 시스템에서는 텍스트를 바이너리로 변환하고, 패딩을 추가하며, 여러 블록으로 나누어 암호화한다.<ref>[[PKCS#1]] 같은 표준이 이런 세부사항을 정의한다.</ref>

== 수학적 배경 ==
=== 소인수분해의 어려움 ===
RSA의 보안성은 '''큰 수의 소인수분해가 어렵다'''는 데 기반한다.

예를 들어:
* 61 × 53 = 3233은 계산하기 쉽다. (1초도 안 걸림)
* 하지만 3233 = ? × ?를 알아내는 것은 상대적으로 어렵다.

만약 n이 수백 자리의 수라면?
* 곱셈: 매우 빠름 (다항 시간)
* 소인수분해: 매우 느림 (지수 시간)<ref>현재까지 알려진 가장 빠른 알고리즘은 [[일반 수체 체 알고리즘]](GNFS)이다.</ref>

'''예시:'''
* RSA-2048 (617자리 수)를 소인수분해하려면 현대 슈퍼컴퓨터로도 수천 년이 걸린다고 추정된다.<ref>물론 [[양자 컴퓨터]]가 나오면 얘기가 달라지지만...</ref>

=== 모듈러 산술 ===
RSA는 '''모듈러 연산'''(modular arithmetic)에 크게 의존한다.

'''기본 개념:'''
* a ≡ b (mod n): a를 n으로 나눈 나머지가 b를 n으로 나눈 나머지와 같다
* 예: 17 ≡ 5 (mod 12) (시계 산술과 같다)

'''중요한 성질:'''
* (a + b) mod n = ((a mod n) + (b mod n)) mod n
* (a × b) mod n = ((a mod n) × (b mod n)) mod n
* (a^k) mod n을 효율적으로 계산할 수 있다

=== 오일러 정리 ===
'''오일러 정리:''' a와 n이 서로소이면, a^φ(n) ≡ 1 (mod n)

이것이 RSA가 작동하는 핵심 이유다!

'''특별한 경우 - 페르마의 소정리:'''
* n이 소수 p일 때, φ(p) = p-1
* 따라서 a^(p-1) ≡ 1 (mod p)
* [[페르마]]가 발견한 아름다운 정리다.<ref>페르마는 증명을 "여백이 부족해서"라는 말과 함께 남기지 않았다. RSA는 그의 정리를 실용화한 셈이다.</ref>

=== 중국인의 나머지 정리 ===
RSA 복호화를 빠르게 하기 위해 '''[[중국인의 나머지 정리]]'''(Chinese Remainder Theorem, CRT)를 사용한다.

'''기본 아이디어:'''
* M^d mod n을 직접 계산하는 대신
* M^d mod p와 M^d mod q를 각각 계산하고
* 결과를 결합한다

이렇게 하면 '''4배 정도 빠르다'''!<ref>실제 구현에서는 거의 항상 CRT를 사용한다.</ref>

== 보안성 ==
=== 안전한 키 길이 ===
RSA의 보안성은 키의 길이에 크게 의존한다.

{| class="wikitable"
! 키 길이 !! 보안 수준 !! 상태
|-
| 512비트 || 매우 약함 || 1999년 RSA-155 (512비트) 인수분해됨
|-
| 768비트 || 약함 || 2009년 RSA-768 인수분해됨
|-
| 1024비트 || 위험 || 2030년까지 안전하지 않을 것으로 예상
|-
| 2048비트 || 안전 || 현재 권장 최소 길이
|-
| 3072비트 || 매우 안전 || 2030년 이후 권장
|-
| 4096비트 || 극도로 안전 || 장기 보안이 필요한 경우
|}

'''NIST 권장사항 (2024년 기준):'''
* 2048비트: 2030년까지 사용 가능
* 3072비트: 2030년 이후 권장
* 4096비트: 최상위 보안이 필요한 경우<ref>하지만 키가 길어질수록 연산 속도는 느려진다.</ref>

=== 알려진 공격 방법 ===
==== 1. 작은 소수 공격 ====
p나 q가 너무 작으면 쉽게 소인수분해된다.

'''방어:''' p와 q는 충분히 큰 소수를 사용해야 한다. (최소 1024비트)

==== 2. 공통 모듈러스 공격 ====
같은 n을 여러 사용자가 공유하면 위험하다.

'''공격 시나리오:'''
* 앨리스와 밥이 같은 n을 사용하지만 다른 e, d를 사용
* 공격자가 두 공개키를 알면 개인키를 계산할 수 있다!

'''방어:''' 각 사용자는 자신만의 n을 생성해야 한다.

==== 3. 작은 지수 공격 ====
공개 지수 e가 너무 작고 평문이 작으면 취약하다.

'''예시:'''
* e = 3이고 M^3 < n이면
* C = M^3이 되고, 단순히 세제곱근을 구하면 M을 알 수 있다!

'''방어:''' [[패딩]] 스킴(OAEP 등)을 사용해야 한다.

==== 4. 타이밍 공격 ====
복호화 시간을 측정하여 개인키를 추정하는 공격.

'''원리:'''
* 개인키의 비트에 따라 연산 시간이 달라진다
* 여러 번 측정하면 패턴을 찾을 수 있다

'''방어:'''
* [[블라인딩]](Blinding) 기법 사용
* 상수 시간 알고리즘 구현

==== 5. 부채널 공격 ====
전력 소비, 전자기파 방출 등을 분석하여 키를 추정.

'''방어:''' 하드웨어 수준의 보안 조치 필요.

==== 6. 소인수분해 알고리즘의 발전 ====
현재까지 알려진 최선의 소인수분해 알고리즘:
* [[일반 수체 체 알고리즘]](General Number Field Sieve, GNFS)
* [[타원 곡선 인수분해]](Elliptic Curve Factorization)

'''기록:'''
* 2020년 2월: RSA-250 (829비트) 인수분해 성공<ref>2700 코어-년의 계산이 필요했다.</ref>

=== 양자 컴퓨터의 위협 ===
'''[[쇼어 알고리즘]]'''(Shor's Algorithm)은 양자 컴퓨터로 소인수분해를 '''다항 시간'''에 해결할 수 있다는 것을 보였다.

'''현재 상황:'''
* 2019년: [[IBM]]이 53큐비트 양자 컴퓨터 개발
* 2023년: [[IBM]]이 1121큐비트 Condor 프로세서 발표
* RSA-2048을 깨려면 수천~수만 큐비트가 필요할 것으로 추정

'''대응:'''
* [[양자내성암호]](Post-Quantum Cryptography, PQC) 개발 중
* [[NIST]]가 표준화 진행 중<ref>격자 기반 암호, 코드 기반 암호 등이 후보다.</ref>
* RSA를 대체할 새로운 암호 시스템 준비 중

== 장점과 단점 ==
=== 장점 ===
* '''키 배송 문제 해결''': 사전에 비밀 키를 공유할 필요가 없다
* '''전자서명 가능''': 개인키로 서명하고 공개키로 검증
* '''널리 사용됨''': 표준화되어 있고 검증된 기술
* '''수학적으로 증명됨''': 안전성이 수학적으로 근거가 있다

=== 단점 ===
* '''느린 속도''': 대칭키 암호(AES 등)보다 100~1000배 느리다
* '''키 크기''': 같은 보안 수준을 위해 대칭키보다 훨씬 긴 키 필요
** AES-128 = RSA-3072 수준
* '''양자 컴퓨터에 취약''': 쇼어 알고리즘으로 깨질 수 있다
* '''구현 복잡도''': 올바르게 구현하기 어렵다<ref>패딩, 타이밍 공격 방어 등 신경 쓸 게 많다.</ref>

=== 하이브리드 암호화 ===
RSA의 단점을 극복하기 위해 '''하이브리드 암호화'''를 사용한다.

'''방법:'''
# 세션 키(대칭키)를 무작위로 생성
# 세션 키로 데이터를 AES 등으로 암호화 (빠름!)
# 세션 키를 RSA로 암호화 (작은 데이터만)
# 암호화된 데이터와 암호화된 세션 키를 전송

이렇게 하면 '''RSA의 보안성 + 대칭키의 속도'''를 모두 얻을 수 있다!<ref>[[SSL/TLS]]가 정확히 이 방식을 사용한다.</ref>

== 활용 사례 ==
=== HTTPS / SSL/TLS ===
웹사이트에 접속할 때 주소창에 자물쇠 아이콘이 보이는가? 그것이 바로 RSA가 작동하는 증거다.

'''과정:'''
# 브라우저가 서버의 '''공개키'''를 받는다 (인증서에 포함)
# 브라우저가 '''세션 키'''를 생성
# 세션 키를 서버의 공개키로 암호화하여 전송
# 서버가 개인키로 세션 키를 복호화
# 이후 세션 키로 대칭키 암호화 통신

=== 전자서명 ===
RSA는 암호화뿐만 아니라 '''전자서명'''에도 사용된다.

'''원리:'''
* 암호화와 반대로, 개인키로 "암호화"하고 공개키로 "복호화"
* 개인키를 가진 사람만 서명할 수 있다
* 누구나 공개키로 서명을 검증할 수 있다

'''실제 과정:'''
# 문서의 해시(예: [[SHA-256]])를 계산
# 해시를 개인키로 "암호화" (서명)
# 문서와 서명을 함께 전송
# 수신자가 서명을 공개키로 "복호화"
# 문서의 해시를 계산하여 비교

'''용도:'''
* 소프트웨어 배포 (코드 서명)
* 이메일 서명 ([[PGP]], [[S/MIME]])
* 문서 인증
* 블록체인 ([[비트코인]]은 RSA 대신 [[ECDSA]]를 사용하지만)<ref>타원곡선 암호가 더 효율적이기 때문</ref>

=== SSH ===
리눅스/Unix 서버에 원격 접속할 때 사용하는 [[SSH]]도 RSA를 사용한다.

'''과정:'''
# 서버의 공개키를 클라이언트에 등록 (또는 반대로)
# RSA를 사용하여 세션 키 교환
# 이후 대칭키 암호화로 통신

=== VPN ===
[[VPN]] 연결 시 RSA로 안전한 터널을 구축한다.

=== 암호화폐 ===
일부 암호화폐는 RSA를 사용하지만, 대부분은 더 효율적인 [[타원곡선 암호]](ECC)를 선호한다.

=== 전자상거래 ===
신용카드 정보 전송, 전자결제 시스템에서 RSA가 사용된다.

== 구현 ==
=== 프로그래밍 언어별 구현 ===
'''Python:'''
<syntaxhighlight lang="python">
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# 키 생성
key = RSA.generate(2048)
public_key = key.publickey()

# 암호화
cipher = PKCS1_OAEP.new(public_key)
ciphertext = cipher.encrypt(b"Hello RSA!")

# 복호화
decipher = PKCS1_OAEP.new(key)
plaintext = decipher.decrypt(ciphertext)
</syntaxhighlight>

'''Java:'''
<syntaxhighlight lang="java">
import java.security.*;
import javax.crypto.Cipher;

KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
keyGen.initialize(2048);
KeyPair pair = keyGen.generateKeyPair();

Cipher cipher = Cipher.getInstance("RSA");
cipher.init(Cipher.ENCRYPT_MODE, pair.getPublic());
byte[] encrypted = cipher.doFinal("Hello RSA!".getBytes());

cipher.init(Cipher.DECRYPT_MODE, pair.getPrivate());
byte[] decrypted = cipher.doFinal(encrypted);
</syntaxhighlight>

'''JavaScript (Node.js):'''
<syntaxhighlight lang="javascript">
const crypto = require('crypto');

// 키 생성
const { publicKey, privateKey } = crypto.generateKeyPairSync('rsa', {
modulusLength: 2048,
});

// 암호화
const encrypted = crypto.publicEncrypt(
publicKey,
Buffer.from('Hello RSA!')
);

// 복호화
const decrypted = crypto.privateDecrypt(privateKey, encrypted);
</syntaxhighlight>

=== 주의사항 ===
'''절대 직접 구현하지 마라!'''<ref>심각하다. 정말로 하지 마라.</ref>
* 타이밍 공격, 부채널 공격 등 고려할 게 너무 많다
* 패딩, 난수 생성 등을 잘못하면 보안이 무너진다
* '''검증된 라이브러리를 사용'''하라
** [[OpenSSL]]
** [[PyCryptodome]]
** [[Bouncy Castle]]
** [[libsodium]]<ref>사실 libsodium은 RSA 대신 더 현대적인 암호를 권장한다.</ref>

== 변형과 개선 ==
=== RSA-OAEP ===
'''[[OAEP]]'''(Optimal Asymmetric Encryption Padding)는 RSA의 보안성을 강화하는 패딩 방식이다.

'''특징:'''
* 작은 지수 공격 방어
* 결정론적 암호화 방지<ref>같은 평문이 매번 다른 암호문으로 나온다.</ref>
* [[무작위 오라클]] 모델에서 증명됨

'''표준:''' [[PKCS#1]] v2.0 이상에서 권장

=== RSA-PSS ===
'''[[PSS]]'''(Probabilistic Signature Scheme)는 RSA 서명을 위한 안전한 방식이다.

'''장점:'''
* 선택 메시지 공격에 안전
* 보안성 증명 가능

=== Multi-Prime RSA ===
2개가 아닌 3개 이상의 소수를 사용하는 변형.

'''장점:'''
* CRT를 사용하면 더 빠른 복호화
* 같은 보안 수준에서 더 작은 개인키

'''단점:'''
* 보안성 분석이 덜 됨
* 표준화되지 않음

== 관련 암호 ==
=== 타원곡선 암호 (ECC) ===
[[타원곡선 암호]](Elliptic Curve Cryptography)는 RSA의 대안이다.

'''비교:'''
* '''키 길이''': ECC-256 ≈ RSA-3072
* '''속도''': ECC가 더 빠름
* '''성숙도''': RSA가 더 오래되고 검증됨
* '''양자 컴퓨터''': 둘 다 취약<ref>쇼어 알고리즘은 타원곡선에도 적용된다.</ref>

=== ElGamal ===
[[ElGamal 암호]]는 RSA와 비슷한 시기에 개발된 공개키 암호다.

'''차이점:'''
* [[이산대수 문제]]에 기반 (소인수분해가 아님)
* 암호문 크기가 평문의 2배
* 특허 없음<ref>RSA는 특허가 있었지만 ElGamal은 처음부터 자유로웠다.</ref>

=== Rabin 암호 ===
[[Rabin 암호]]는 RSA와 매우 유사하지만 e=2를 사용한다.

'''특징:'''
* 소인수분해와 직접 동치<ref>즉, Rabin을 깨는 것 = 소인수분해. RSA는 이론적으로 소인수분해 없이도 깰 수도 있다.</ref>
* 복호화 시 4개의 평문 후보가 나옴
* 실용적이지 않아서 잘 안 쓰임

== RSA 챌린지 ==
[[RSA Laboratories]]는 1991년부터 2007년까지 '''RSA Factoring Challenge'''를 운영했다.

'''목적:'''
* 소인수분해의 난이도 측정
* 암호학 연구 촉진
* 상금 제공<ref>처음에는 $10,000부터 시작</ref>

'''주요 결과:'''
{| class="wikitable"
! 번호 !! 비트 수 !! 인수분해 연도 !! 상금
|-
| RSA-100 || 330 || 1991 || 없음
|-
| RSA-129 || 426 || 1994 || $100
|-
| RSA-140 || 463 || 1999 || $7,500
|-
| RSA-155 || 512 || 1999 || $10,000
|-
| RSA-160 || 530 || 2003 || 없음
|-
| RSA-200 || 663 || 2005 || 없음
|-
| RSA-768 || 768 || 2009 || 챌린지 종료 후
|-
| RSA-250 || 829 || 2020 || 챌린지 종료 후
|}

'''미해결 숫자들:'''
* RSA-617 (617비트)
* RSA-704 (704비트)
* RSA-896 (896비트)
* RSA-1024 (1024비트)
* RSA-1536 (1536비트)
* RSA-2048 (2048비트)<ref>이건 인류가 깰 수 있을지 의문이다.</ref>

== 흥미로운 사실 ==
* RSA-129는 원래 '''4천조 년'''이 걸릴 것으로 예상되었으나, 분산 컴퓨팅으로 '''8개월'''만에 깨졌다.<ref>기술의 발전 속도를 보여주는 사례</ref>

* RSA 알고리즘은 '''무기'''로 분류되어 미국 수출 규제 대상이었다. 1990년대까지 암호 기술을 인쇄된 책으로만 수출할 수 있었다.<ref>그래서 RSA 소스 코드를 책으로 인쇄해서 수출한 사례도 있다.</ref>

* 2015년, 연구자들이 타이완의 '''국민신분증 카드'''에 사용된 RSA-1024 키를 생성할 때 약한 난수 생성기를 사용했다는 것을 발견했다. 이론상 모든 키를 깰 수 있었다!<ref>암호는 구현이 전부다.</ref>

* RSA의 세 발명자는 2002년 [[튜링상]]을 수상했다. 컴퓨터 과학계의 노벨상이라 불리는 상이다.

* 처음 RSA 논문이 제출되었을 때, 한 심사위원이 "이건 너무 간단해서 누군가 이미 발명했을 것"이라고 말했다고 한다.<ref>결과적으로 영국 정보기관이 먼저 발명하긴 했지만...</ref>

* 일부 국가에서는 강력한 암호 사용을 '''불법'''으로 규정한다. 중국, 러시아 등에서는 정부가 복호화할 수 있는 암호만 허용한다.<ref>프라이버시 vs 국가안보의 영원한 논쟁<s>이라 하고 검열이라 읽는다</s></ref>

* RSA-2048을 [https://zenodo.org/records/18205268 깼다고 주장]하는 사람이 나왔다. <s>근데 p랑 q가 [[소수(Prime Number)|소수]]가 아니라 RSA가 아닌게 함정</s> 당연히 거짓 논문이다. 자세한 내용은 [[Roughness of Area 엔진]] 문서를 참고하자.

== 같이 보기 ==
* [[공개키 암호]]
* [[대칭키 암호]]
* [[AES]]
* [[디피-헬먼 키 교환]]
* [[타원곡선 암호]]
* [[전자서명]]
* [[SSL/TLS]]
* [[양자내성암호]]
* [[소인수분해]]
* [[오일러 정리]]
* [[페르마의 소정리]]
* [[중국인의 나머지 정리]]

== 참고 문헌 ==
* R. L. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," ''Communications of the ACM'', vol. 21, no. 2, pp. 120–126, 1978.
* Dan Boneh, "Twenty Years of Attacks on the RSA Cryptosystem," ''Notices of the American Mathematical Society'', vol. 46, no. 2, pp. 203–213, 1999.
* Victor Shoup, "OAEP Reconsidered," ''Journal of Cryptology'', vol. 15, no. 4, pp. 223–249, 2002.

== 외부 링크 ==
* [http://www.rsa.com RSA Security 공식 웹사이트]
* [https://www.openssl.org/ OpenSSL 프로젝트]
* [https://csrc.nist.gov/projects/post-quantum-cryptography NIST 양자내성암호 프로젝트]

== 각주 ==
<references />

[[분류:암호학]]
[[분류:정보보안]]
[[분류:공개키 암호]]
[[분류:수학]]

RSA 암호 - 편집 역사

Gaon12: 시작