암호학 - Public Key Cipher :: RSA와 안전성

RSA가 소인수분해의 어려움에 기반한 암호 알고리즘이라는 사실은 이미 지난 포스트에서 설명을 했습니다.
(관련 포스트 : http://reinliebe.tistory.com/79)

게다가 해독 사례도 이미 언급을 하였습니다 (관련 포스트 : http://reinliebe.tistory.com/83)

일단 앞서 언급한 내용과 더불어

오늘은 RSA 암호의 안전성에 대하여 알아 보겠습니다.

우선 RSA 암호를 공격한다는 의미는 공개키를 이용하여 암호문으로 부터 원 메시지를 복원 한다는 의미와 같은데, 아직까지는 소인수분해를 이용하여  φ(n) 과 d 를 계산하는 방법 말고 특별히 이렇다 할 효율적인 알고리즘이 알려져 있지 않다지요 ...

물론 소인수분해 외의 방법이 존재 할 지도 모르고요 ...

아무튼 이어서... RSA 암호의 공격 방법에 대하여 알아보아요 ...

▶ Protocol 공격

  - 작은 e를 사용하는 경우

  - 작은 d를 사용하는 경우

  - Multiplicative 특성을 이용한 공격

  - 여러 암호문을 보낼 때 공통의 modulus를 사용하는 경우

  - 순환 공격

  - 부분 키 노출 공격

  - Timing 공격

 

▶ 소인수분해 공격

  - Trial Division

  - Pollard rho 공격

  - Pollard p-1 공격

  - 타원곡선을 이용한 공격

  - Dixon's random square 공격

  - Quadratic sieve 공격

  - Number field sieve 공격

 

물론 이 밖에도 다양한 알고리즘과 공격 방법이 존재 할 수 있습니다.
(일단 참고한 자료들이 조금 오래된 자료기 때문에 지금은 더 효율적인 알고리즘들이 나왔을 것으로 추정됩니다만)

 

아무튼 이런 공격들로부터 안전한 RSA를 구현하기 위해
매우 큰 소수(1024bit 이나 2048bit 정도)를 사용하도록 권장하며,
소수를 선택함에 있어 아래와 같은 규칙을 갖게 됩니다.

▶ 소수 선택의 조건

  - 두 소수 p, q의 크기가 거의 같아야 함

  - p-q가 너무 작으면 안됨

  - p-1이 큰 수를 인수로 가져야 함

  - p+1이 큰 수를 인수를 가져야 함

출처 - http://reinliebe.tistory.com/