[컴퓨터 보안] Attack against RSA(RSA 공격하기)

RSA 공격

• Brute force
  • 다 해보기 -> 경우의 수가 너무 많아서 거의 불가능
• Mathematical attacks
  • factor n (n!) 해보기
  • 정수를 소인수 분해만 쉽게 하면 RSA는 깨질 수 있다. -> factoring, discrete log를 빨리 수행할 수 있다면
• Chosen ciphertext attack
• Implementation attacks
  • 값마다 알고리즘의 연산량이 다름을 이용 -> 시간 차이, 전략 사용량 차이 등 

 

 

 

Mathematical attacks: Factoring Problem

• RSA를 수학적으로 공격하기 위한 접근법 3가지
  1. RSA에서 ø(n) = (p-1)*(q-1) 연산하는 부분이 있다. -> 소인수 분해
     • 이 부분을 효율적으로, 빨리 하기 -> 아직 방법이 발견되지 않음. 불가능한지 가능한지 모름
     • 이 부분이 이뤄지면, d = $e^{-1}$ (mod ø(n))을 결정할 수 있다.
  2. 소인수 분해 하지 않고 바로 ø(n) 구하기 -> 불가능
  3. ø(n) 구하지 않고 바로 d 구하기 -> 불가능
• Factoring을 쉽게 하면 RSA는 깨짐. 즉 Factoring이 RSA의 안전성이라고 생각할 수 있다.

 

 

 

Chosen Ciphertext Attack(CCA)

• 공격 성공 조건:
  1. 공격자가 ciphertext를 선택한다.
  2. 선택한 ciphertext에 대해서 private key를 가진 사람한테 decryption 요청
     • 예: 사용자가 핸드폰 잠시 두고 간 사이에 공격자가 몰래 Decryption 시도해보기
  3. 그 결과 공격자는 {Ciphertext, Plaintext} 쌍을 얻게 됨.
  4. 공격자가 이전에 선택한 Ciphertext 이외의 것을 한 개라도 복원하면 공격자 승리

 

 

Implementation Attack: Side Channel Attacks

• 알고리즘이 작동되면서 생성되는 부수적인 정보들을 이용해 공격하는 방법이다.
• Timing attack
  • private key에 따라 연산 시간이 달라지는 점을 활용.
  • 정수 값에 따라 알고리즘을 돌렸을 때, 걸리는 시간이 다른데, 이런 부분을 이용
• Power analysis, Electromagnetic analysis, Cache 등
  • 값에 따라 연산을 수행할 때 사용되는 전력 양 등이 다름을 이용

 

 

 

 

Fault-Based Attack

• 지금까지는 관찰해서 분석&공격했지만, Fault-Based attack은 좀 더 적극적인 공격이다.
• 연산이 수행되는 와중에 갑자기 강력한 전압을 걸거나 해서 의도적으로 에러를 유도함. 
• 즉, 정상 결과와 비정상 결과를 모두 얻은 후, 이를 조합해서 추가적인 정보를 얻어낸다.

 

 

 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]