EFFICIENT IMPLEMENTATION OF PUBLIC KEY CRYPTOSYSTEMS

Abstract

Public key cryptosystems are widely used in computer and communication systems for their capability of digital signature and convenience in key management. The performance of public key cryptosystems is determined by two factors: one is the speed of operation, i.e. encryption and decryption, or signature and verification; another is the speed of system generation, which mainly involves the speed of key generation. Thus, it is of practical significance to improve the performance of public key cryptosystems. In this thesis, several issues about efficient implementation of public key cryptosystems are discussed. Among the existing public key cryptosystems, RSA [24] is one of the most popular systems used in practice. In this thesis, we firstly discuss the methods of improving the performance of RSA scheme, including its operation and key generation. There are two main approaches for improvement of operation speed: fast exponentiation and efficient modular reduction. We describe a fast exponentiation algorithm namely SS(l) [13] for fast RSA encryption/decryption operation. Additionally, we examine the efficiency of modular reduction. We discover that on many performance greatly or even degrades the performance when the bit length of the integers involved becomes large. We suggest that SS(l) algorithms alone be usually the best choice to be used in RSA encryption and decryption, or signature and verification when RSA is implemented with software. In RSA scheme its security relies on the choice of its public and private keys. We consider some types of factorization attacks on RSA which lead to the need of strong primes generation. We invent a fast method for strong prime generation based on the probabilistic Miller-Rabin primality test. In addition, we also design an approach to generate deterministic strong prime based on John Shawe-Taylor's technique [34] and we demonstrate that time complexity for generating strong primes by means of deterministic method is comparable to generating strong primes by means of probabilistic method. To look for possibility of substantially improving the speed of public key cryptosystems, we also consider the use of elliptic curves as mathematical basis for public key cryptosystems. Recently, elliptic carves have received great attention in the area of public key cryptography due to the shorter key length for equivalent security strength as the public key cryptosystems over field of GF(q). Currently, it is time-consuming to generate secure elliptic curves. In this thesis, we present an efficient elliptic curves generation scheme. Finally, we examine a novel public key cryptosystem based on a different mathematical structure. Finite Automata public key cryptosystem for implementation is discussed. FAPKC has an attractive feature of fast speed in operation and system generation: with our implementation, the speed of FAPKC is above ten times faster than that of RSA. We conclude that FAPKC has great potential value in practical use. However, it is still an evolving technique and needs to be extensively studied.