* 공개키 암호(Public key cryptography)
- 비대칭 암호라고도 한다.
* 공개키 암호에서의 키
- 트랩 도어의 단방향 함수에 기반을 둔다.
- 한 방향으로의 계산은 쉬우나 다른방향으로의 계산은 힘들다.
- 공개키와 개인키의 한 쌍을 만들어 낸다.
> 공개키 : 메세지를 암호화 하는데 사용하는 키 ( 모두에게 공개 되있다. )
> 개인키 : 메세지를 복호화 하는데 사용하는 키 ( 개개인 만이 알고 있다. )
- 특정사람의 공개키로 암호화된 암호는 그 사람의 개인키로만 복호화가 가능하다.
* Knapsack 암호체계
ⓐ Knapsack problem(= General Knapsack problem)
- N개의 가중치의 집합 {W0, W1, ... , Wn-1}과 특정값 S가 주어졌을때, 가중치 집합의 특정 원소를 뽑아내 합한 결과가
S가 되는 것(가중치들)을 찾는 문제이다.(일종의 subset sum문제)
- 일반적인 knapsack problem은 NP-complete문제로 가능한 경우를 모두 해봐야 값을 구할 수 있는 문제이다.
(문제 해결에 많은 시간이 걸린다.)
ⓑ super-increasing Knapsack(SIK) problem
- 이는 가중치를 나열했을 때, 특정 가중치는 이전 가중치의 총합보다 크다는 것을 만족하는 가중치 집합을 가지고 푼다.
ex) (2,3,7,14,31), S=19 // 가장 큰 값부터 더하기 시작하여 더한 값이 S보다 크면 그 앞에 것을 탐색한다.
1) 31 >= 19 Pass
2) 14 <= 19 Select 14
3) 14+7 = 21 >= 19 Pass
4) 14+3 = 17 <= 19 Select 3
5) 17+2 = 19 = 19 Select 2
Result : {14, 3, 2}
ⓒ Knapsack cryptography
- SIK(ⓑ)에 해당하는 것을 생성한다.
- SIK를 GK(ⓐ)의 문제로 변환시킨다.
> 이경우 GK를 공개키로 사용하며, SIK를 개인키로 사용한다.
- 서로 서로소관계에 있는 두 숫자(m과 n)를 추출하여 암호화에 사용한다.
예시)
- 단점/약점
> 단방향으로만 작동한다. 공개키로 암호화 된 것을 개인키로 풀기는 쉽지만, 개인키로 암호화된 것을 공개키로 풀기 힘들다.
> 1983년 제작된 컴퓨터 Apple II에 의해 이미 해독 가능한 수준이 되었다.
> SIK로 도출한 GK는 GK에 가깝지 않아서 풀기가 쉽다.
* 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
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)
// 암호화 전의 수와 복호화 된 수의 값이 같다!!
ⓑ 안전성
- n값(공개된 값)을 소인수 분해가 가능하면 쉽게 RSA를 깰 수 있다.
- 현재 위의 문제에서 n값 55는 5와 11로 소인수 분해가 가능하며 이는 p,q에 해당한다.
- 하지만, 큰 소수끼리의 곱은 이를 발견하기가 힘들다. 즉, 이를 얼마나 빨리 발견하느냐가 RSA의 안전성과 연관된다.
* Diffie-Hellman 알고리즘
- 비밀키를 각 종단에서 생성하여 같이 사용한다.
- 키 또는 비밀값을 만들어주는 알고리즘
- 서로 생성한 키 or 비밀값을 사용하여 둘 만 사용하는 대칭키를 생성하는 알고리즘이다.
- 중간자 공격의 여부가 존재한다.
- 키 생성 절차 > 공개된 값 : 큰 값의 소수 p, generator g(primitive root of p)
- 중간자 공격을 방지할 법이 없을가?
1) 교환하는 값을 대칭키로 암호화하여 보낸다. (모순! Diffie-hellman은 대칭키에 사용하는 키를 생성하는 알고리즘이다.)
2) 교환하는 값을 상대방의 공개키로 암호화하여 보낸다.
3) 교환하는 값을 자신의 개인키로 서명하여 보낸다.
* 공개키 암호의 적용
1. 메세지 암호화
- 상대방의 공개키로 암호화하여 메세지를 전송한다.
- 수신자는 자신의 개인키로 복호화하여 메세지를 추출한다.
2. 전자서명
- 메세지를 자신의 개인키로 암호화한다.
- 보안은 안되지만, 무결성과 인증, 부인봉쇄를 할수 있다.
3. 공개키의 한계
- 공개키만을 이용하여 기밀성과 부인 봉쇄를 동시에 만족시킬 수 없다.
* 공개키 인증
- 특정 사람의 공개키가 그 사람의 것인지를 확인하기 위해서 인증기관이 만들어 졌다.
- 인증기관(Certification Authority:CA) : 특정 개체의 공개키가 시실인 것을 증명해주는 곳
- 특정 사람은 자신의 공개키를 인증기관에 등록하여 사용한다.
- 인증기관은 특정 사람과 공개키를 결합하는 인증서를 만들고, CA의 개인키로 암호화한다.
> 다른 사람이 특정 사람의 공개키를 원한다면, 인증서를 보내준다.
> 인증서를 인증기관의 공개키로 복호화하여 서로 비교를 하여 공개키의 사실 여부를 확인한다.
? 인증기관의 개인키는 어떻게 믿을 수 있는가?
> 이로 인해 계층적으로 인증기관이 존재하며, 최상위 기관(Root certificate)은 충분히 신뢰 할 수 있다고 생각한다.
- 공개키 인증서의 표준으로 X.509를 사용한다.
※ 공개키 신뢰모델
- 완전 독점 모델
> 하나의 CA에서 모든 키를 관리한다. (CA가 손상되면 큰 문제가 발생하게 된다.)
- 소수 독점 모델
> 다수의 CA가 존재한다.
> 현재 브라우져에서 사용하는 방법이다.
> 사용자는 어떤 CA를 신뢰할 수 있을지에 대한 결정권을 가지고 있다.
- 완전 자유모델
> 공개키 사용자 모두가 CA로 존재한다.
> 무정부 상태라고 할 수 있다.
> 사용자는 어떤 사람을 신뢰할 것인지를 선택한다.
* 지금까지 정리한 것을 보면, 공개키를 안전하게 사용하기 위해서는
1. 키 생성과 관리법
2. 인증 기관
3. 인증서 관리
등이 전재로 이뤄져야 한다.
* 대칭키 VS 공개키
- 대칭키는 공개키에비해 속도가 빠르다.
- 공개키는 공유된 비밀키가 필요없으며 서명을 통해 부인 봉쇄도 가능하다.
- 공개키는 지수 연산을 하기 때문에 큰 메세지를 암호호화는데 비효율적이다.
- 따라서 현실세계에서는 혼합된 암호 체계, 대칭키로 데이터를 암호화하고 공개키로 대칭키의 키를 교환하는 방식을
체택하고 있다.