s프레쏘

RSA

핵심 개념은 $x^{ed}\equiv x(\mathrm{mod}pq)$이다. ($x$는 평문, $x^e(\text{mod }pq)$는 암호문, $e$: Encrytion exponent, $d$: Decryption exponent) x를 e로 암호화하고 d로 복호화 하면 다시 평문x가 나오며, 반대로 d로 암호화, e로 복호화 해도 평문 x가 나온다.(전자서명에서 사용) p와 q는 매우 큰 소수이다. 키사이즈 N비트는 pq를 말한다. $\phi (pq)=(p-1)(q-1)$ $x^{\phi (pq)}\equiv 1(\text{mod }pq)$ 오일러 정리 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$ if $gcd(a,n)=1$ ($a$와 $n$이 서로소) $\phi (n)$: $n$과 서로소인..