정수계획법에 기반한 공개키 암호 알고리즘의 설계 = Design of Public-Key Cryptographic Algorithm based on Integer Programming

국문 초록 (Abstract)

공개키 암호 알고리즘은 암호화에 사용되는 공개키와 복호화에 사용되는 비밀키가 서로 다르며, 공개키는 공개되고 비밀키는 비밀로 유지되어 소유자만이 알고 있다. 이러한 알고리즘의 암호화 함수는 한 방향으로의 계산은 매우 쉬우나, 특별한 정보 없이 반대 방향으로 계산하는 것은 매우 어려운 성질이 있도록 하기 위하여 계산상 풀기 어려운 문제에 기반하여 연구되고 있다.
본 논문에서는 정수계획법에 기반한 계산상 풀기 어려운 문제를 이용하여 새로운 공개키 암호 알고리즘을 제안한다. 먼저 정수 계획법에 대하여 소개하고 비밀키와 공개키의 생성 과정을 보인다. 공개키로 이용되는 행렬을 평문에 곱하여 암호문을 만들고 공개키와 비밀키를 이용한 복호화 행렬을 이용하여 평문을 복원한다. 이 알고리즘의 키 생성 방식은 기존의 배낭꾸리기 암호 시스템의 방식과 유사하지만 배낭꾸리기 시스템의 비밀키에서 나타나는 취약점을 보완하였다.

다국어 초록 (Multilingual Abstract)

The public-key cryptosystem uses two different keys for encryption and decryption. Since the encryption function of a public-key cryptosystem has to have properties of trapdoor and one-wayness, it is based on computationally intractable problems.
We propose a new public-key cryptographic algorithm based on integer programming. We introduce the integer programming problem, and then show the scheme of encryption and decryption using integer programming problem. Our algorithm efficiently encrypts and decrypts in polynomial time. Although the proposed algorithm is similar to knapsack public-key cryptosystem, it is more secure on attacks because it complements the weakness of private key of the knapsack cryptosystem.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련연구
• 3. 알고리즘
• 4. 결과 및 분석
• 5. 결론
• 참고문헌
• 저자소개