암호화와 복호화에 앞서 거쳐야 할 기본적인 과정임~
1) 적당히 비슷하고 큰 소수 p, q를 구함
2) 공개키 n을 생성 (n=pq)
3) φ를 구함 φ = (p-1)(q-1)
4) gcd(s,φ)=1을 만족하는 즉 서로 소인 또다른 공개키 s를 생성합니다. 1< s < φ
5) 유클리드 알고리듬을 이용하여 비밀키 d를 만듦 d = s^-1 (mod φ) (sd≡1 (mod φ) 를 구하는 것. 무엇을 선택하든 상관없음) 를 구하는 것 1< d < φ
※ 확장된 유클리드 알고리듬으로 정수 d를 구하는 법
t_0 = 0
t_1 = 1
t_j = t_(j-2)-q_(j-1)t_(j-1) mod r_0 (단, j≥2)
위 방법을 이용하여 d를 구한다.
암호화) n보다 작은 수로 메세지 M을 정한 다음,암호문 c = M^s (mod n) 을 계산하여 암호문 c를 보낸다.
복호화) M = c^d (mod n)을 사용해 복호한다.
예를 들어..
1) 소수 5와 7을 골랐다면..
2) 공개키 n=35를 만들게 됨.
3) φ=24를 구함.
4) 24와 서로소인 11=s를 구함.
5) 현재 공개키 (n,s) = (35,11)을 구함.
6) 비밀키 d를 구함.
d = 11^-1 (mod 24)
확장된 유클리드 알고리듬의 적용.
11^-1 (mod 24) --- 주어진 식
24 = 2*11+2(=r1)
--- 24(=n)를 앞의 11(=s)로 나누어 몫과 나머지 형태로 나타낸 것. n = q(=몫)*s+r1(=나머지1)
(t_2)0-2*1 (mod 24) = -2 (mod 24) = 22(=r2) (mod 24)
--- t_(2-2)=0이므로 0-2(=q)*1(t_(2-1)=1) (mod 24) = -2 (mod 24) = 24-2 (mod 24) = 22 (mod 24)
11 = 5(=q2)*2(r1)+1(r3)
---s를 앞에서 나온 나머지 r1으로 나눈 것입니다. 검산식 형태. (현재 여기서는 나머지가 1이 나왔기 때문에 유클리드 알고리듬은 끝이 난 것입니다.)
(t_3)1-22*5 (mod 24) = -109 (mod 24) = 11 (mod 24)
--- 1(=t_(3-2)) - 22(r2)*5(q2) (mod 24) = -109 (mod 24) = 24*5-109 (mod 24)=11(mod 24)
따라서 d = 11.
암호화) 메세지 3을 암호화 해본다. 암호문 c = 3^11 (mod 35) = 12
복호화) 암호문 12를 복호화 해본다. 메세지 M = 12^11 (mod 35) = 3.
복호화가 제대로 되었다.
중요 포인트는 확장된 유클리드 알고리듬을 적용할 때, 나머지가 1이 나올 때까지 계속 반복해야 한다는 점이다.
(여기서 φ는 φ(n)을 뜻하는 오일러 함수 값)
RSA는 공개키라고 해서 서버가 암호를 가지고 있다가 클라이언트가 접속을 하면 그 암호를 보내줌.
그럼 서버와 클라이언트가 그 암호를 이용해 서로서로 확인을 함.
공개키와 수신자의 개인키가 암호화/복호화 과정에서 이러한 공식을 사용하기 때문에 클라이언트 단에서 End User가 알기는 힘듦.
수신자가 암호화 알고리즘을 알 필요도 없고 알수도 없고, 수신자의 개인키가 복호화를 하기 때문..