(A) study on the analysis of cryptosystems for telecommunication

Abstract

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...