비대칭키 암호: 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 최대공약수는 작은 수