[정보보안] 공개키 암호화인 RSA에 대해서

RSA

- 공개키 암호시스템, 암호화 뿐 아니라 전자서명이 가능한 최초의 알고리즘

- 소인수 분해의 난해함에 기반하여, 공개키만을 가지고는 개인키를 의미론적으로 아전한 암호화 시스템을 보장하도록 디자인됨. 

- 공인인증서 비밀번호 : 개인키를 푸는 암호화키

---

1. Key-pair generation (키 생성법) 

1) p, q : 굉장히 큰 소수 (p != Q), 
2) N = P X Q ,  N 을 modulus
3) (p-1)(q-1)과 서로소에 있는 정수 e를 찾는다.
4) e X d = 1 mod (p-1)(q-1) , e의 곱셈상의 역원인 d를 계산 

N,e 를 공개키로 사용
d를 개인키로 사용한다.

예제)

1) 굉장히 큰소수 p, q를 정한다. p = 11, q = 3
2) N을 계산  , N = pq = 33  (p-1)(q-1) = 20
3) 20과 서로소인 관계인거를 찾는다. e = 3, 7, 9 ... 이중에서 하나 선택,  e = 3 
4) ed = 1 mod 20,  d = 7

---

2. 암호화(Encryption)

1) message M 을 암호화 하기 위해
C = M^e mod N

2) C를 복호화
M = C^d mod N

예제)

공개키 : (N,e) =(33,3)
개인키 : d = 7
M = 9

Ciphertet C 
C = M^e mod N = 8^3 = 512 = 17 mod 33
M = C ^ d mod N = 17 ^ 7 = 410338673 = 12434505 * 33 + 8 = 8 mod 33  (d가 굉장히 큰 숫자)

- d가  2048 bit 라 복호화가 오래걸린다. 
- 공인인증서 비밀번호 치면 d가 나온다. 

 

 

---

 

RSA Encrypt / Decrypt - Examples - Practical Cryptography for Developers