* 대칭키의 문제점
- 대칭키를 약속하는 법 > 키 분배
- 대칭키가 많아지면(대화자가 많아지면) 키 관리가 힘들어진다. > 키 관리
* 공개키 암호화
- 대칭키 암호화의 문제점 해결을 위해서 만들어짐.
- 각 사용자는 자신의 공개키(Public key : K+)와 개인키(Private Key : K-)를 쌍으로 가지고 있다.
- 사용자는 개인키를 자신의 비밀상자에 보관하고, 공개키를 사람들에게 공개한다.
> 공개키로 인해 Key분배 문제가 해결된다. 자신의 키를 정의해서 공개키를 알려 주면된다.
> 여러명과 통신을 하더라도 하나의 키만 가지고 있으면 가능하다. > 키 관리 문제 해결
- 암호화 : 공개키를 이용하여 평문을 암호화 한다.
- 복호화 : 개인키를 이용하여 암호문을 해독한다.
- 대표적이면서 거의 유일한 공개키 알고리즘 : RSA
> RSA key 생성 알고리즘
1. 두 개의 큰 소수 p,q를 선택한다.
2. n = pq, z = (p-1)(q-1) 을 이용하여 n과 z를 생성한다.
3. n보다 작은 수 중에서 z와 서로 소 관계에 있는 e를 하나 선택한다.
(e는 무수히 많은 수중에서 하나이다.)
4. e*d % z = 1 의 관계를 성립시키는 d값을 선택한다.
(d값 또한 무수히 많은 수중에서 하나이다.)
5. 공개키(n,e)와 개인키(n,d)를 생성한다.
> 암호화 : m^e % n = c
> 복호화 : c^d % n = m
// m is 평문!
example) p = 5, q = 11. then n = 55, z = 40
e = 7 ( e는 z와 서로소 관계에 있는 수 중 하나 )
d = 23 ( d는 ed % z = 1을 만족하는 수 중 하나 )
data(bit pattern) = 0011
1. data를 십진수로 변경한다. 0011(2) = 3
2. 암호화 : 3^7 % 55 = 2187 % 55 = 42
3. 전송!!
4. 복호화 : 42^23 % 55 = ... = 3
5. 십진수를 2진수로 변경하여 데이터로 취급 3 = 0011(2)
// 암호화 전의 수와 복호화 된 수의 값이 같다!!
> RSA의 안전성
~ 공개키를 알 고 있더라도, d 값을 찾는 것은 매우 힘들다.
~ n값을 두 소수 p와 q로 나누는 과정을 얼마나 빠르게 하느냐에 따라 안전성이 달라진다.
~ 큰 소수 p, q로 n을 분해하는 과정은 매우 어렵다.
* 공개키암호화의 문제점 및 응용
- 문제점 : 암호화, 복호화 하는데 지수 연산이 필요하기 때문에 매우 많은 시간이 걸린다.
- 공개키를 사용하여 대칭키를 암호화하고, 대칭키를 이용하여 메세지를 암호화하여 전송한다.
- 디지털 서명, 인증등에서 사용한다.
