RSA 알고리즘

- 공개키 암호 시스템

- 메시지를 암호화 할 때 공개키를 사용하고, 복호화 할 때 개인키를 사용한다.

 

key 생성

p, q (둘 다 소수, p!=q)

n = p*q

Φ(n) = (p-1)*(q-1) (오일러 파이 함수 Φ(n) = 1~n-1까지의 양의 정수 중 n와 서로소 관계에 있는 정수 개수)

gcd(e, Φ(n)) = 1 인 e 구하기 (여러 값 중 하나 고르면 된다) => 개인키 e가 된다.

(e*d) mod Φ(n) = 1 이 되는 d를 고른다. => 공개키 d가 된다.

 

암호화

C: 암호문 M: 평서문

 

C = M^e (mod n)

 

복호화

M = C^d (mod n)