RSA 암호 편집하기 (부분)

== 보안성 ==
=== 안전한 키 길이 ===
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를 대체할 새로운 암호 시스템 준비 중