공개키 암호 시스템

배 경
▮ 메시지를 통신채널을 통해 암호화하여 보낼 때, 키 전송을 위한 안전한 채널이 필요.
--> 현실적으로 안전한 채널을 구성하는 방법 : 사람이 직접 전달
▮ 키 분배시 n명이 서로 암호화하여 메시지를 교환하려면 n(n-1)/2 개의 키가 필요
▮ 1978년 Merkle, Hellman 공개키 암호 시스템 발표
공개키와 비밀키
▮ 공개키 : 다른 사람들에게 알려지는 키. 이 키를 이용하여 메시지 암호화(복호화는 불가)
▮ 비밀키 : 개인만이 알고 있는 키. 공개키로 암호화된 메시지를 복호화
▮ n 명이 서로 암호화된 메시지 교환시 2n(공개키+비밀키)개의 키만 필요.
트랩도어 함수 모델
▮ 공개키로 암호화하는 함수는 계산하기 쉬어야하고, 반대로 비밀키를 가진 수신자 이외에게는 복호화하기는 어려워야 한다.
▮ 공개키 암호 시스템 구축 단계

단계 1) 계산적으로 불가능한 문제 P를 찾는다. 이 문제는 다항식 시간 내에 풀 수 없어야 한다.

단계 2) P의 부분문제 Peasy를 선택한다. Peasy는 다항식 문제가 되어야 한다.

단계 3) Peasy를 바꿔서 Pshuttle로 변환한다. 이때 Peasy와는 전혀 달라야하고 P와는 비슷하게 보여야 한다.

단계 4) Pshuttle을 공개하고 그것이 공개 암호 키로 어떻게 쓰이는가를 설명한다. Pshuttle이 Peasy로 어떻게 변환되는가는 trapdoor 비밀이다.

단계 5) 자세한 암호 시스템을 완성하고 적법한 해독자와 불법한 해독자가 전혀 다른 복호화 과정을 갖도록 한다.