RSA (공개키 암호 알고리즘)

RSA

무슨 말이냐면 소수 11 과 13이 있을 때 n=pq --> 143=11*13 라고 하면
p와q를 이용하여 n을 구하는 것은 쉽지만, n의 값만 보고
p, q를 유추하기 어려움(소인수 분해의 어려움)을 이용.

-> 공식 암호화 : c = me mod n 공개키로 암호화
(m=평문, e=공개키, n=pq(공개키), c= 암호문)

-> 공식 복호화 : m = cd mod n 개인키로 복호화
(m=평문, e=공개키, n=pq(공개키), c= 암호문)

ex) p=5, q=7로 선택
*** n,e=공개키
*** n,d=개인키
*** 참고로 p, q도 비밀로 해야함

*** 서로소란 두 수의 최대 공약수가 1인 두 자연수

1. 임의의 소수 p,q 를 생성

2. p와q를 곱하여 n을 구한다( n= 35 = 공개키)

3. (P-1)(q-1)을 계산한다. (5-1)(7-1)=24

4. 3번에서 구한 24와 서로소인 임의의 자연수 e를 구한다
--> e=7로 선택하였음 (e= 공개키)

4.1 e의 값은 1 < e < n 중에서 24와 서로소인 값을 구하는 것.

5. e*d mod [(p-1)(q-1)] = 1 인 d를 구한다.
--> 즉, 7*d mod 24 = 1 인 값을 구하는 것