• 오일러 정리/페르마 소정리를 모르면 바보로 느껴질 수 있습니다.

RSA는 대표적인 비대칭 암호화 알고리즘이다.

관찰

p하고 q는 소수, x, e, d는 정수, x하고 $N=pq$가 서로소, $ed = 1 \mod \phi(n)$이면

$$x^{ed}=x \mod N$$

이다

증명

$ed = k\phi(n) + 1$ for some k. then $x^{ed} = x^{k\phi(n)}x = x \mod N$ by 오일러 정리

이제 위의 e는 공개키, d는 비밀키가 될 것이다(encryption, decryption).

근데 $ed = 1 \mod \phi(n)$이려면 적어도 e와 $\phi(n)$이 서로소여야한다. 그리고 d는 유클리드 알고리즘을 이용해 $ed+\phi(n)y = 1$이 되도록 구한다.

이제 p와 q는 잊어버려도 된다.

포인트는 p와 q를 모르면 $\phi(n)=(p-1)(q-1)$을 알 수 없다는 것이다. 그래서 d와 N을 알고 있어도 e를 구할 수 없다.

RSA

이제 B가 A에게 비밀을 말하고 싶다고 해 보자. A는 아주 큰 두 소수 p, q를 고르고 N=pq를 계산한다. 이제 $\phi(n) = (p-1)(q-1)$과 서로소인 e를 고른다음에 d를 계산한다. (이제 p와 q는 잊어버려도 된다.) 이제 <N, e> 쌍은 공개하고 <N, d> 쌍은 혼자 가지고 있자.

B가 A한테 평문 x를 암호화해서 보내고 싶으면 x대신 $y = x^e \mod N$을 보낸다. 이제 A는 $x' = y^{d} \mod N$을 계산해서 복호화하면 된다.

Q&A

큰 지수승을 어떻게 계산하나요

암호화/복호화를 할 때 지수승을 계산한다. 이 계산이 오래걸리면 불편할 것이다.

만약 $x^{35409}$를 계산한다고 생각해보자. $35409=2^{15}2^{11}+2^9+2^6+2^4+1$이다.

이제 $(x^2)^2 = x^4 = x^{2^2}$, $(x^4)^2 = x^8 = x^{2^3}$, ... 를 15번 계산하면 $x^{x^{15}}$까지 계산할 수 있다. 이제 $x^{35409} = x^{2^{15}}x^{2^{11}}x^{2^9}x^{2^6}x^{2^4}x$이므로 곱셈 5번을 더 하면 된다.

e가 $2^{4096}$ 정도라고 해도 현대 컴퓨터에게 무리는 아니다.

Reference

• 이인석, 대수학