RSA

공개키 암호 알고리즘의 표준으로 인수분해 문제 해결이 어렵다는 사실에 기반하고 있다. 암호화와 전자서명 등에 사용된다.

키 생성¶

• N = pq
• p와 q는 서로 다른 소수
• Φ(N) = (p-1)(q-1)
• Φ(N) 보다 작고, Φ(N)과 서로소인 정수 e를 찾음
• de ≡ 1 (mod Φ(N))를 만족하는 정수 d
• 확장 유클리드 호제법 사용

암호화/복호화¶

통신 주체는 상대방의 공개키로 평문을 암호화하여 송신하고 수신자는 자신의 개인키로 암호문을 복호화하여 평문을 획득함

• 암호화
• C = M^e mod n
• e: 공개키
• 복호화
• M = C^d mod n
• d: 비밀키

취약점¶

• 소인수분해 공격
• 현실적인 시간 내에 효율적인 소인수분해는 아직 불가능
• 이러한 알고리즘이 개발된다면 안전하지 않음
• 중간자 공격
• 통신 주체사이에서 RSA를 하는 공격자의 위험성
• 공개키 인증서를 사용하여 방지
• 선택 암호문 공격(CCA, Chosen Ciphertext Attack)
• 임의의 데이터를 송신하면 그것을 암호문으로 간주하고 회신해주는 서비스를 공격자가 이용할 수 있다는 것을 가정한 공격
• 이러한 공격을 막기 위해 최적 비대칭 암호화 패딩(OAEP)으로 평문을 수정하는 것이 권장된다.

권장사항¶

공개키 N과 e로부터 비밀키 d를 구할 수 있다면 RSA는 해독이 가능하므로 아래 권장사항을 지켜야만 한다.

• 소수 p와 q는 최소 512bit, N은 최소 1024bit
• p와 q는 같지 않고 거의 비슷한 크기의 소수
• p-1과 q-1은 큰 소인수를 가져야 함
• p-1과 p-1 최대공약수는 작은 수