정보보호 스터디

[공개 키 암호] RSA에 대한 공격

녕녕펀치 2024. 3. 7. 10:40

1.  공격

  • 암호 해독자가 알고 있는 것
    • 암호문 : 도청해서 얻은 것
    • 수 E와 N : 공개 키로서 공개되어 있으므로 암호 해독자는 E와 N을 알고 있음
  • 암호 해독자가 모르는 것
    • 평문: 지금부터 해독하려고 하는 내용
    • 수 D : 개인 키 중 적어도 D는 모르고 있음
    • 기타 : 암호 해독자는 키 쌍을 만들었을 때의 p, q, L을 모르고 있음

2. 암호문으로부터 평문 구하기

  • 암호문 = (평문)^E mod N (RSA에 의한 암호화)
  • mod N이 붙어 있으면 평문을 구하는 것은 이산 대수를 구한다는 매우 곤란한 문제가 됨

3. 전사 공격

  • 수 D를 알면 암호문을 복호화할 수 있음
  • RSA에 대한 공격 방법으로서, D의 후보가 되는 수를 순서대로 시도해서 복호화하는 전사 공격
  • 전사 공격은 D의 비트 수가 크면 클수록 어려워짐

4. E와 N으로부터 D 구하기

  • E로부터 D를 계산할 때는 p와 q를 사용. 하지만, 암호해독자는 p와 q를 전혀 모름
  • RSA : 소수 p와 q를 암호 해독자가 알게 해서는 안됨
  • ① N을 소인수 분해하는 공격
    • N = p x q
    • N은 공개되어 있음
    • 큰 수의 소인수 분해를 고속으로 할 수 있는 방법이 발견되면 RSA를 해독할 수 있음
    • 하지만, 현재 큰 수의 소인수 분해를 고속으로 행하는 방법은 아직 발견되지 않음
  • ② p와 q를 추측하는 공격
    • p와 q는 의사난수 생성기로 생성하는 것이기 때문에 의사난수 생성기의 품질이 나쁘면 p와 q를 암호 해독자가 추측해 버릴 우려가 있음
    • 생성하는 난수를 암호 해독자가 추측할 수 있어서는 안됨
    • 키 쌍을 작성할 때 p와 q를 파일의 어딘가에 기록하건 화면에 표시하거나 하면 안됨
  • ③ 기타 공격
    • N을 소인수 분해해서 p와 q를 구할 수 있으면 D를 구할 수 있음
    • D를 구하는 것이 N을 소인수 분해하는 것과 같은지 아닌지는 수학적으로 증명해야함
    • D를 구하는 것과 N을 소인수 분해하는 것이 결정적 다항식 시간으로 같다는 것을 2004년 알렉산더 메이가 증명함

5. 중간자 공격

  • RSA에 해독하는 것은 아니지만, 기밀성에 대한 매우 유효한 공격 방법
  • 적극적 공격자 맬로리가 송신자와 수신자 사이에 들어가서, 송신자에 대해서는 수신자처럼, 수신자에 대해서는 송신자처럼 행세하는 공격
  • 이 공격은 RSA뿐만 아니라 어떤 공개 키 암호에도 사용할 수 있음
  • 그렇다고 해서 공개 키 암호가 해독된 것은 아님. 모든 암호 알고리즘은 제대로 기능하고 있으며, 기밀성을 유지하고 있음. (단, 그 기밀성은 앨리스와 밥 사이의 것이 아닌, 앨리스와 맬로리 사이, 그리고 맬로리와 밥 사이의 기밀성임)
  • 공개 키 암호에 의한 암호화만으로는 이 중간자 공격을 막을 수 없음