RSA 알고리즘

RSA 알고리즘

1977년 Rivest, Shamir, Adleman이 발명한 공개키 암호 알고리즘으로 큰 두 소수의 곱을 인수분해하기 어렵다는 수학적 문제에 기반하며 암호화·전자서명·키교환 모두 가능한 범용 비대칭키 암호

특징: 인수분해 난제, 범용성, 키 길이 큼

키 생성 과정

• •① 두 개의 큰 소수 p, q를 선택 (각 1024비트 이상, RSA-2048 기준)
• •② 모듈러스 n = p × q 계산 (n이 공개키와 개인키 공통 요소)
• •③ 오일러 토시언트 φ(n) = (p-1)(q-1) 계산
• •④ 공개 지수 e 선택: 1 < e < φ(n), gcd(e, φ(n)) = 1 (일반적으로 e = 65537 = 2^16 + 1)
• •⑤ 개인 지수 d 계산: e × d ≡ 1 (mod φ(n)), 즉 d = e^(-1) mod φ(n) (확장 유클리드 알고리즘)
• •⑥ 공개키 = (n, e), 개인키 = (n, d), p와 q는 안전하게 폐기

암호화/복호화 과정

• •암호화: C = M^e mod n (평문 M을 수신자의 공개키 e로 암호화)
• •복호화: M = C^d mod n (암호문 C를 수신자의 개인키 d로 복호화)
• •수학적 근거: 오일러 정리에 의해 M^(e×d) ≡ M (mod n) 성립

전자서명 과정

• •서명 생성: S = H(M)^d mod n (메시지 해시값을 송신자 개인키로 서명)
• •서명 검증: H(M) = S^e mod n (서명을 송신자 공개키로 검증, 해시값 비교)

보안 강도: p, q를 알면 d 계산 가능 → n의 인수분해가 곧 키 해독, RSA-2048: 현재 안전(2030년까지 권장), RSA-3072: 2030년 이후 권장

구성요소: 소수 p/q, 모듈러스 n=p×q, 공개키(n,e), 개인키(n,d), 오일러 토시언트 φ(n)

기술요소: RSA-2048(표준), RSA-3072(장기), RSA-4096(최고), OAEP(암호화 패딩), PSS(서명 패딩)

키길이: 2048비트(현재 표준), 3072비트(장기 보안), 4096비트(최고 보안)

패딩: PKCS#1 v1.5(레거시/패딩 오라클 공격에 취약), OAEP(Optimal Asymmetric Encryption Padding/암호화 권장), PSS(Probabilistic Signature Scheme/서명 권장)

취약점: 작은 지수 공격(e가 작고 패딩 없을 때), 타이밍 공격(처리 시간 분석), 패딩 오라클(PKCS#1 v1.5), 양자 컴퓨터(Shor 알고리즘으로 다항시간 인수분해 가능)

적용사례: TLS 인증서, 코드 서명, S/MIME, SSH, 전자서명

비교: RSA(키3072/인수분해/범용/느림) vs ECC(키256/이산로그/효율/빠름), RSA-2048(표준) vs RSA-4096(기밀/연산부담)

연관: 비대칭키, ECC, PKI, 전자서명, 양자내성암호