[CryptoHack] RSA Starter 3

 

설명

---

RSA는 모듈러 N의 인수분해의 어려움에 의존한다.

소인수를 찾을 수 있으면, N의 Euler totient를 계산하여 암호문을 해독할 수 있다.

 

주어진 $N =  p * q$ 및 두 개의 소수:

p = 857504083339712752489993810777

q = 1029224947942998075080348647219

 

N의 totient는 무엇인가?

 

풀이

---

수론에서, Euler's totient function은 주어진 정수 n까지 서로소인 양의 정수 갯수를 말한다.

Euler's totinet function은 곱셈적 함수이다. 두 정수 m, n 이 서로소인 경우에 

$\phi (mn) = \phi (m) \phi (n)$이 성립한다.

 

또한 정의에 따라, 소수 p에 대해 $\phi (p) = p-1$ 이 성립한다.

역도 성립한다. $\phi (n) = n-1$이면 n은 소수이다.

 

$p^n$ 은 $p$만을 소인수로 가지므로

$\phi (p^n) = p^n - p^{n-1} = p^{n-1}( p - 1)$ 도 성립한다.

 

이러한 성질들을 가지고 쉽게 구할 수 있다.

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
N = p*q
phi = (p-1) * (q-1)

print(phi)