RSA과제

키생성

두 소수 p,q에 n = p*q, φ(n) = (p-1) * (q-1)
공개 지수 e와 개인지수 d를 사용해서 e * d ≡ 1 (mod φ(n))가 되도록 한다. 공개키는 암호문을 복호화하고, 개인키는 암호문을 만든다. 공개키 구성 = {e, n}, 개인 키 구성 = {d, n}

e = {e | 1<e<ϕ(n) and ϕ(n)과 서로소}
{d|e*d mod n=1}, c = m^e mod n, m' = c^d mod n.

간소화

φ(p^n * q^m)를 간소화하면 다음과 같다.

φ(p^n*q^m) = (p^n * q^m) * (1-1/p) * (1-1/q)
φ(p^n*q^m) = (p^n * q^m) * (1 - 1/p - 1/q + 1/(pq))
φ(p^n*q^m) = (p^n * q^m) * ((pq-p-q+1)/(pq))
φ(p^n*q^m) = p^(n-1) * q^(m-1) * (pq-p-q+1)
φ(p^n*q^m) = p^(n-1) * q^(m-1) * (p*q-p-q+1)
φ(p^n*q^m) = p^(n-1) * q^(m-1) * (pq-p-q+1)