🛠 Franklin-Reiter Related Message Attack

🔑 개요

Franklin-Reiter Related Message Attack은 RSA 암호화에서 특정한 조건을 만족하는 두 개의 관련된 메시지가 암호화될 경우, 원본 메시지를 복원할 수 있는 공격 기법입니다.

이 공격은 동일한 RSA 모듈러스 ( N ) 와 같은 공개 지수 ( e ) 를 사용하여 관련된 두 개의 메시지를 암호화할 때 발생하는 취약점을 악용합니다.

---

🔥 공격 조건

• 같은 공개키 ( (N, e) ) 로 두 개의 관련된 메시지 ( m_1, m_2 ) 가 암호화됨

• 두 메시지가 특정한 선형 관계를 만족해야 함:
  [
  m_2 = f(m_1)
  ]
  예를 들어,
  [
  m_2 = m_1 + c
  ]
  같은 형태여야 함.

• 공격자는 두 개의 암호문을 알고 있음:
  [
  c_1 = m_1^e \mod N
  ]
  [
  c_2 = m_2^e \mod N
  ]

---

🔥 공격 과정

1. 다항식 설정
   두 개의 메시지가 선형 관계를 가진다는 점을 이용해 두 개의 다항식을 정의합니다.

   • ( f(x) = x + c ) 라고 하면, ( m_2 = f(m_1) ) 이므로:
     [
     P_1(x) = x^e - c_1
     ]
     [
     P_2(x) = (x + c)^e - c_2
     ]

2. 최대공약수 계산
   두 다항식 ( P_1(x) ) 와 ( P_2(x) ) 의 최대공약수 ( \gcd(P_1(x), P_2(x)) ) 를 계산하면,
   이 다항식의 해가 ( m_1 ) 이 됩니다.

3. m_1 복원 후 m_2 도 쉽게 계산 가능
   [
   m_2 = m_1 + c
   ]

이제 공격자는 평문 ( m_1 ) 과 ( m_2 ) 를 쉽게 구할 수 있습니다.

---

⚡ 예제

공격이 가능한 경우의 예제를 들어보면,

1. Alice가 Bob에게 두 개의 관련된 메시지를 암호화해 보냄:

   • ( m_1 = \text{"Hello"} )
   • ( m_2 = m_1 + 1 ) (ASCII 코드 기반)

2. 동일한 ( (N, e) ) 키를 사용하여 암호화:

   • ( c_1 = m_1^e \mod N )
   • ( c_2 = m_2^e \mod N )

3. 공격자는 ( \gcd(P_1(x), P_2(x)) ) 를 계산하여 ( m_1 ) 을 복원.

---

⛏ 방어 방법

1. Salt 적용

   • 각 메시지에 난수를 추가하여 암호화 (Padding 적용)
   • 예: OAEP (Optimal Asymmetric Encryption Padding) 사용

2. 무작위화(Randomization)

   • 메시지를 직접 암호화하지 않고, 변형된 값을 사용하여 암호화.

3. 동일한 키로 여러 개의 관련된 메시지를 암호화하지 않기

   • 특히 선형적인 관계를 가지는 메시지는 동일한 RSA 키로 암호화하면 안 됨.

---

🎯 결론

Franklin-Reiter 공격은 RSA를 사용할 때, 동일한 공개키로 선형 관계가 있는 두 메시지를 암호화하면 위험하다는 점을 보여줍니다.
따라서 OAEP 패딩을 사용하거나, 메시지의 랜덤화를 통해 방어하는 것이 중요합니다.

더 깊이 들어가려면 GCD를 활용한 다항식 공격을 직접 구현해보는 것도 추천합니다! 🚀