In this thesis, we propose a modified ElGamal elliptic curve cryptosystem using a knapsack scheme. We will use an elliptic curve defined over $F_{p^n}$. And we will encrypt or decrypt a message using the knapsack scheme. To use the knapsack scheme, a sender must share a sequence with a receiver. We share the sequence with a similar method to ElGamal ECC. Also, we will consider possible attacks and the complexity for the ElGamal ECC and the proposed cryptosystem. Finally, we will compare the proposed cryptosystem with the ElGamal ECC in the terms of security and efficiency.
본 논문에서는 강력한 보안성을 확보하고 있다는 엘가말 타원곡선 암호시스템에 배낭암호기법을 적용하여 동일한 안전성을 가지고 같은 시간에 더 많은 메시지를 전달할 수 있는 암호시스템을 제안한다. 제안된 암호시스템은 엘가말 타원곡선 암호시스템의 키 교환을 이용한 [단계1]과 배낭암호기법을 이용하여 암호화와 복호화를 수행하는 [단계2]로 나눌 수 있다.
대략적인 내용을 살펴보면, 메시지를 주고받는 송신자와 수신자는 엘가말 타원곡선 암호시스템에서 사용한 키 교환 기법을 이용하여 동일한 수열을 교환한다. 물론 이 수열은 두 사람만이 알 수 있다. 그 다음, 해쉬함수를 이용하여 초증가 수열을 만들고 이 초증가 수열을 가지고 배낭암호기법을 사용하여 암호화와 복호화를 수행한다. 기존의 공격들(샤미르 공격과 저밀도 공격)은 공개된 수열이 있어야 가능하기 때문에 개선된 암호시스템에는 적용될 수 없다.
안전성 면에서 살펴보면, 제안된 타원곡선 암호시스템의 [단계1]에서는 엘가말 타원곡선 암호시스템의 안전성과 최소한 동일함을 알 수 있고 [단계2]에서는 기존의 공격방법이 적용되지 않으므로 안전하다는 사실을 알 수 있다. 결국 이 논문에서 제안한 암호시스템의 안전성은 기존의 엘가말 타원곡선 암호시스템의 안전성과 최소한 동일하다는 것을 알 수 있다.
효율성 면에서 살펴보면, 한 개의 메시지 블록을 전달할 때는 기존의 암호시스템의 complexity와 제안된 암호시스템의 complexity는 거의 차이가 없으나, 전달하고자 하는 메시지 블록의 양이 많을수록 제안된 암호시스템의 complexity가 크게 개선됨을 알 수 있다.
