The security problem on sensitive information carried over computer telecommunication networks is one of major issues in an information oriented society. To make information transmitted over networks to be secure, it is inevitable to use the information processing techniques, cryptosystems. Currently the need for cryptographic protection for communication networks becomes widely recognized.
In 1976, Merkle and Hellman introduced the idea of public key cryptosystems, in which encryption key and decryption key are different from each other from the computational complexity point of view. Since then, many kinds of public key cryptosystems have been developed. Public key cryptosystems are, generally, based on hard number theoretic problems such as discrete logarithm or factoring large numbers. From the wide application areas and the obvious relations to complexity theory, public key cryptosystem is one of the major research areas in cryptography. Among cryptosystems, knapsack public key cryptosystems are characterized by the efficiency in encryption and decryption process. They are constructed by imposing a trapdoor on a knapsack problem which falls into the category of NP-complete problem.
To convince the security of cryptosystems and guide a more secure construction of cryptosystems, it is essential to develop methods for breaking cryptosystems. There does not exist a methodology to convince the security of cryptosystems completely. Their security can be assured only by showing that they are secure against all possible attacks known yet.
There are many attacks on knapsack public key cryptosystems, but most attacks use the lattice basis reduction techniques as the basic tool. However, the knapsack problems on which knapsack public key cryptosystems are constructed, are 0-1 integer problems in nature. Therefore it may be possible to attack on knapsack public key cryptosystems using the mathematical programming techniques.
In this paper, we develop two cryptanalytic methods for general public key cryptosystems. They are constructed on the basis of mathematical programming. For attacks, the knapsack problems are transformed into 0-1 quadratic integer problems. One attack is to solve them through the branch and bound method by exploiting the properties of IP dual programming. The other method is to obtain a partial solution from the persistency property of linear relaxations. For the former attack, the method to construct group problems for IP dual programming is proposed and results of computational tests are given. This method could be an alternative for cryptanalysis on knapsack cryptosystems from the computational experiences.
For the latter attack, the theoretical method is given for finding a partial solution of knapsack problems. It is revealed that the effectiveness of the method is restricted. But the computational expenditures for this are much less than those of the other methods and it could be used to complement the existing cryptanalyses on knapsack cryptosystems.
The cryptosystems are, naturally, to secure the information transmitted. In an electronic information oriented society, however, specific activities must be taken to assure that the communicant is really the person with whom I want to communicate, electronic messages are communicated authentically, and they cannot be repudiated. Identification and digital signature schemes may be used to provide assurances in distributed and networked computer environments. Many identification and digital signature schemes have been developed last twenty years or so. In most of them, it is possible to make identification or digital signature based on user's identity.
There are, however, many situations in which a user wants to verify his membership in certain groups without revealing his identity. Also, in some cases, the user must prove simultaneously his identity and membership in certain groups. Therefore, the scheme is needed in which a user can prove his identity, his membership in certain groups, or both his identity and membership in certain groups. And it is more desirable that it provide the ways to sign on a message digitally based on his identity, membership, or both selectively.
Many schemes for membership proof are presented, but they can provide only simple functions or there is a problem of efficiency for real world applications. In this thesis, we propose a membership proof system which is suitable for applications. In this scheme, identity and membership proofs are based on the discrete logarithms, which are efficient in both respect of computation and communication. This scheme can provide various types of identifications and digital signatures selectively.
현재의 정보화시대에서 전산통신망으로 통신되고 있는 중요한 정보를 어떻게 보호할 것인가 하는 것은 아주 중요한 문제이다. 현실적으로 통신정보를 보호하기 위해서는 암호법이라고하는 정보처리기법을 사용할 수 밖에는 없으며 이의 당위성은 널리 인식되고 있다.
암호화키와 복호화키가 서로 계산적으로 분리되어 있는 공개키암호법의 개념이 소개된 이후로 많은 종류의 공개키암호법이 개발되어 왔다. 이러한 공개키암호법은 대개 이산로그나 소인수분해와 같이 아주 어려운 정수론적 문제에 근거하고 있다. 이러한 공개키암호법은 그 응용분야가 넓고, 계산복잡성에 근거하여 그 안전성을 증명할 수 있다는 특성을 지니고 있으므로 암호학에서는 집중적인 연구의 대상이 되고 있는 실정이다. 공개키암호법들 중에서 배낭공개키암호법은 NP-Complete인 배낭문제를 기반으로하여 만들어지기 때문에 특히 그 암호화 및 복호화가 상당히 효율적으로 이루어 질 수 있다는 장점을 지니고 있다.
현재 어떠한 암호법이라도 그의 안전성을 절대적으로 증명할 수 있는 방법은 존재하지 않는다. 암호법의 안전성은 모든 가능한 암호공격방안에 대하여 그 암호법이 얼마나 안전한가에 의하여 평가될 수 있을 뿐이다. 따라서 암호공격방안을 제시하는 것은 암호법의 안전성에 대한 신뢰를 제고하기 위해 또한 보다 안전한 암호법을 만들기 위해 아주 중요한 일이다.
기존에 제시된 대부분의 배낭암호법에 대한 공격방안은 거의 모두가 정수격자의 기저축약을 그 기본적인 분석도구로 사용하고 있다. 그러나 배낭암호법이 기반으로 하는 배낭문제는 결국 0-1 정수 문제이다. 따라서 수리계획적인 접근방법에 의한 배낭암호법 분석이 가능하다.
본 논문에서는 일반적인 배낭암호법을 그 대상으로 하고 수리계획적 접근방법을 사용하는 두 가지의 배낭암호법 분석방안을 제시하고 있다. 이들 방안은 우선 배낭문제를 0-1 2차 정수계획법 문제로 변환하여 이의 해를 구하는 방법을 사용하고 있다. 첫 번째 방안은 정수계획법 쌍대문제의 특성을 이용하는 분단탐색법을 사용하여 배낭문제의 해를 구하고자 하는 방법이고, 다른 하나의 방안은 선형이완에서의 지속효과를 이용하여 배낭문제의 해의 일부를 구하는 방법이다. 논문에서 제시된 계산적 실험결과에 의하여, 첫 번째 방법은 일반적인 배낭암호법에 대한 상당히 유효한 암호공격방안이 될 수 있음이 증명되었다. 두 번째 공격방안에 대한 계산적 실험결과는 별로 성공적이지 못하다. 그러나 이 방안에서 요구되는 계산량이 다른 공격방안들에 비하여 상당히 적으므로 개발된 배낭암호법의 안전성을 확인하기 위한 선행적 안전성 실험방법으로 사용될 수 있을 것이다.
한편 현재의 통신환경에서는 통신되는 정보의 비밀성을 보장하는 이외에도 많은 보호대책이 필요하다. 즉 통신하고 있는 상대방이 정당한 상대인지를 확인할 수 있어야 하며, 통신하고 있는 정보가 변경 또는 조작되고 있지 않으며, 사후에 분쟁이 생길 경우에 이를 객관적으로 확인할 수 있어야 한다. 이를 위한 암호학적 방법이 식별과 디지탈 서명체계이다. 현재 많은 연구자들이 이러한 체계를 연구하고 있으며 지금까지 많은 식별체계와 디지탈 서명체계가 개발되어 있다. 이들은 대부분 사용자의 신분에 근거하여 사용자를 식별하며 또한 디지탈 서명을 하는 방식이다. 그러나 이러한 체계의 응용분야가 확대됨에 따라 보다 다양한 식별 및 디지탈 서명체계가 요구되고 있다. 일반적으로 사용자들은 여러 그룹에 소속되게 되는데 이때 어떤 그룹에 소속되어 있다는 사실만을 상대방에게 증명하거나 또는 그룹소속에 근거하여 디지탈 서명을 할 수 있는 방안이 필요하게 되었다.
본 논문에서는 하나의 체계 안에서 다양한 종류의 사용자식별과 디지탈 서명을 가능게하는 그룹소속증명/디지탈 서명체계를 개발하였다. 이 체계에서는 하나의 정보를 가지고 사용자가 자신의 신분을 증명할 수 있고, 신분을 밝히지 않고 일정한 그룹에 소속되어 있음을 증명할 수 있으며, 또한 신분과 그룹소속을 동시에 증명할 수 있다. 또한 신분이나 일정한 그룹소속에 근거하여 디지탈 서명을 할 수도 있다. 기존에 제시된 그룹소속 증명방식들은 그 기능이 단편적이거나 현실적으로 실현하기에 요구되는 계산량이나 통신량에서 문제가 있다. 그러나 논문에서 제시된 체계는 다양한 기능을 제공할 수 있으며 계산량이나 통신량의 측면에서 현실적으로 사용가능하다.
