RSA 공개 키 암호화 시스템

RSA?

RSA는 공개 키 암호화 방식의 한 종류로 전자서명이 가능한 최초의 알고리즘이다.
RSA는 무슨 뜻인가하니 Ron Rivest, Adi Shamir, Leonard Adleman의 앞 글자를 딴 것이다.

Example

1. 임의의 두 소수 p, q를 생각하자
   p = 7, q = 11
2. 공개 키 N = p * q = 77
3. pi(n) = (p-1) * (q-1) = 60
4. gcd(e, pi(n)) = 1 을 만족하는 e(단, 1 < e < pi(n))를 선택하자
   e = 13
5. (e * d) mod pi(n) = 1 을 만족하는 d를 찾자
   d = 37

---

암호화 C = (Message)^e mod n
복호화 (Message) = C^d mod n

if Message = 2
C = 2^13 mod 77 = 30

Decryption
30^37 mod 77 = 2

참고

wikipedia - RSA

​