RSA란?

대표적인 공개키 암호화 알고리즘이다. Rivest-Shamir-Adleman의 앞글자를 따서 RSA라고 부른다.
RSA의 핵심 안전성 가정은 큰 수 N을 소인수분해하는 문제가 매우 어렵다는 점에 기반한다.
일반적으로 AES같은 대칭키를 이용해 메시지를 암호화하고 대칭키를 RSA같은 공개키로 암호화하여 이용한다.

키생성

RSA는 Private Key(d,N)과 Public key(e,N)으로 구성되어 있다.

1. 서로 다른 큰 소수 p,q 선정(1024 bit 이상)
   1024 bit 이하인 소수를 사용하면 예측하기 쉽다
2. N = p x q
   N은 공개키와 개인키의 일부로 modulo 연산의 divisor로 사용된다.
   공개키 값의 일부로 N값은 공개된다. -> 소인수분해하면 p와 q를 얻을 수 있다. 그러나 소인수 분해 문제 다항 시간 내에 값을 구하기 힘들다.
   RSA의 키 크기를 의미하기도 한다.
3. 𝜑(𝑁)=(𝑝−1)(𝑞−1) 또는 l=lcm(p−1,q−1)
4. gcd(𝜑(𝑁),l)=1(1<e<l) 또는 gcd(e,l)=1(1<e<l)
   𝜑(𝑁) 또는 l 과 서로소인 공개 지수 e를 선택한다(보통 65537 이용)
5. d≡e^-1(modφ(N)) 또는 d≡e^-1(mod l)이 되도록 d를 계산

Private Key(d,N)과 Public key(e,N)으로 구성된다는 것을 기억하자.

암호화

Alice는 M이란 메시지를 Bob에게 보내고 싶다고 가정하자. Alice는 M을 public key(e,N)를 이용해 C를 계산하고 Bob에게 보내게 된다.

복호화

암호문 C가 Bob에게 전달되고 Bob은 Private Key(d,N)를 이용해 암호문을 평문으로 만든다.

Franklin–Reiter Related Message Attack

이걸 설명하기 위해 RSA에 대해 간략히 설명했다. Franklin–Reiter Related Message Attack은 RSA에서 서로 선형 관계를 가진 두 평문을 같은 공개키로 암호화했을 때 평문을 복구할 수 있다는 공격 방법이다.

일 때

두 평문이 선형 관계를 가진다면


이고

이므로 두 다항식은 같은 공통인수를 공유한다.
그래서 공격자는 다항식 연산에서

를 계산해서 M1 값을 찾을 수 있다.

암호학 관련 ctf에서 자주 등장하니 알아두자... 최근에 암호학 문제 풀때 해당 방법을 몰라서 다른 요상한 방법으로 풀었었는데 이 방법으로 푸는거였다.

해당 방법 말고도 다양한 RSA 관련 공격 방법이 있다. Duplicate Prime, Small Prime Diference, Low Private Exponent, Hastad’s Broadcast Attack, Coppersmith Attack, ROCA 등등...