반응형
설명
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)
반응형
