공개키 (Public Key)

1. 대칭키의 문제점

1) 키 분배 문제

2) 서로 모르는 사이의 경우 보안 커뮤니케이션이 불가능하다.

3) 키 관리 문제점

2. 공개키 암호 시스템

 - x는 개인키이고 y는 공개키이다.

 - 누군가가 모두 공개키를 알 수 있도록 등록을 해놓는다.

 - 이것을 관리하는 방법은 이 카테고리 마지막 게시글에서 설명한다.

 - A 는 B와 모르는 사이라고 가정한다.

 - A는 B의 공개키를 가지고 암호화 해서 B에게 보낸다.

 - A는 B에게 안전하게 메시지를 보낼 수 있고

 - B는 본인만 그 내용을 확인할 수 있다.

3. 일방향 함수

 - 해쉬 함수와 같이 

 - x --> f(x) 는 쉽지만 

 - f(x) --> x 는 어려워야 한다.

 - 단 private key를 가지고 있을 경우 쉽게 f(x) --> x 가 가능해진다.

 - 이때의 어려운 문제는 polynomial 시간 내에 풀 수 없는 문제를 말한다.

     - factorization problems (n = p x q 일 때 두 소수 p와 q를 알아내야함)

- discrete logarithm problems (a^x = b 에서 x를 알아내야함)

- shortest vector problems

4. RSA

 - 오일러의법칙에 따르면  

 - n과 a의 최대 공약수가 1이라고 할 때 a ^ phi(n) == 1 (mod n) 이 성립한다.

 - 그리고 이전에 올렸던 기본 공식에 대해 복습하도록 한다.

 - 오일러 법칙을 이용한다면 최대 공약수가 성립함을 증명할 수 도 있다.

 - 키 생성 방법

 - 위 그림을 보면 이해할 수 있겠지만

 - 어떤 수 n을 정한다 이때 n = p x q 가 성립해야하고 p 와 q는 어느정도 큰 소수여야 한다.

 - 0보단 크거나 같고 n보다는 작은 수 중에 소수의 개수 phi(n) 를 구한다.

 - 1보단 크거나 같고 phi(n)-1 보단 작거나 같은 수 중에 하나의 수 e를 선택한다. 

 - 이 때 e는 phi(n)과 최대공약수가 1이어야 한다.

 - e의 곱셈의 역원 d를 구한다.

 - 위의 구한 값을 이용하면 공개키는 (n, e) 이고 개인키는 d가 된다.

1) RSA Sign

2) RSA verify

 - 하지만 이런 방식은 쉽게 깨지므로 RSA의 변형이 필요하다.