[정보보안기사 07] 비대칭키 암호: RSA

비대칭키 암호: RSA(Rivest-Shamir-Adleman)

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

키 생성

• 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 최대공약수는 작은 수