정수론 #6 :: RSA

RSA 암호화 방법

1. 엄청 큰 잘 알려지지 않은 소수 p, q의 곱 m을 구한다. (m = p*q)

2. Φ(m) = (p-1)(q-1)

3. Φ(m)과 서로소인 k를 구한다.

4. 다음을 만족하는 l을 구한다.

 

$\begin{gather*}kl≡ 1 \mod \phi(m) \\ \Rightarrow kl-\phi(m)y=1 \end{gather*}$

 

• public : m, k
  공개해도 됨.
• Secret key : l
  공개해선 안됨.
• Bank’s Secret : p, q, Φ(m)
  공개해선 안됨.

 

---

 

암호화

1. 평문을 표를 보고 숫자의 조합 M으로 바꾼다.

2. M을 쪼개서 a_i로 만든다. 이때 a_i는 m보다 작아야한다.

3. 다음을 푼다.

 

$\begin{gather*}b_i≡ a_i^k \mod m \end{gather*}$

 

4. 얻은 b_i가 암호.

 

---

 

복호화

1. 다음을 푼다.

 

$\begin{gather*}a_i≡ b_i^l \mod m \end{gather*}$

 

2. 얻은 a_i를 표를 보고 평문으로 바꾼다.

 

RSA는 '암호학'에서 더 자세하게 배울 수 있어요!