RSA

핵심 개념은 $x^{ed}≡x \pmod{pq}$이다.

($x$는 평문, $x^{e}(\mbox{mod } pq)$는 암호문, $e$: Encrytion exponent, $d$: Decryption exponent)

x를 e로 암호화하고 d로 복호화 하면 다시 평문x가 나오며, 반대로 d로 암호화, e로 복호화 해도 평문 x가 나온다.(전자서명에서 사용)

 p와 q는 매우 큰 소수이다. 키사이즈 N비트는 pq를 말한다.

$\varphi(pq) = (p-1)(q-1)$

$x^{\varphi(pq)} ≡ 1 (\mbox{mod }pq)$

오일러 정리

 

$x^{\varphi(pq)+1} ≡ x (\mbox{mod }pq)$, $x^{ed}≡x (\mbox{mod }pq)$

$ed≡ 1 (\mbox{mod } \varphi(pq))$

$gcd(e,\varphi(pq)) = 1$ 이면 $법\varphi(pq)$에서 e의 곱셈역원 d가 존재하므로,

만족하는 e를 먼저 구하고, 확장 유클리드 알고리즘으로 d를 구함. 

 

 

여기서 공개키엔 n(=pq)와 e를 

개인키엔 {n,d} 혹은 {p, q, dP, dQ, qInv, (r_i, d_i, t_i)}를 담고 생성된 나머지 값은 파기한다.

rsa의 키사이즈는 n의 사이즈를 의미한다.

 

추가 의문

평문 x가 pq와 서로소가 아니여도 작동하는가?

-> 작동한다.

참고 : https://crypto.stackexchange.com/questions/1004/does-rsa-work-for-any-message-m

Does RSA work for any message M?

유저 user996522의 글을 보면 쉽게 이해 할 수 있다.

RSA에서 평문 x의 최대 크기는  x<pq 이고 (이때 x는 패딩까지 포함.)  p와 q는 소수 이므로, x가 pq와 서로소이기 위해선 x가 "p의 배수, q와 서로소" 혹은 "q의 배수, p와 서로소" 여야 한다.

x가 p와 배수 q와 서로소인 경우 아래와 같다.(반대도 문자만 서로 바꾸면 동일)

$x ≡ 0  \pmod{p}$ 이고  모든 정수 k에 대해 $x^k≡ x^{ed} ≡x ≡ 0 \pmod{p}$ 이다 .

\begin{align} x^{ed} &≡x^{1+z\varphi(pq)}\\
&≡ x^{1+z\varphi(p)\varphi(q)} \\
&≡ x\cdot (x^{\varphi(q)})^{\varphi(q)}\\
&≡ x \pmod{q} \end{align}

중국인의 나머지 정리에 따라

연립합동식

$$x^{ed} ≡x \pmod{p}$$

$$x^{ed} ≡x \pmod{q}$$

에서 $x^{ed}$는 법 pq에서 유일한 해 이므로 x로 복원 가능하다. 

중국인의 나머지 정리