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

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뿐만 아니라 어떤 공개 키 암호에도 사용할 수 있음
• 그렇다고 해서 공개 키 암호가 해독된 것은 아님. 모든 암호 알고리즘은 제대로 기능하고 있으며, 기밀성을 유지하고 있음. (단, 그 기밀성은 앨리스와 밥 사이의 것이 아닌, 앨리스와 맬로리 사이, 그리고 맬로리와 밥 사이의 기밀성임)
• 공개 키 암호에 의한 암호화만으로는 이 중간자 공격을 막을 수 없음