Elliptic curve cryptosystem is one of the most important, cryptosystems, which is obtained by substituting finite group of elliptic curve on finite field for finite group of cryptosystem based on discrete logarithm problem. Strictly speaking, it is not a new cryptosystem, but is a renovation of elliptic curve type of known cryptosystem. Because of its many special advantages, it has attracted more attention and been researched as an independent part. It is generally considered that the elliptic curve cryptosystem will become the most important public-key cryptosystem in the 21th century.Up to now, some typical elliptic curve cryptosystems have been implemented by software or hardware in a few laboratories. However, in most case, the speed of encryption/decryption is not satisfied, especially, the software implementation. Aiming at this problem, a software package is developed in this dissertation. The package is mostly applicable to microcomputers and can be implemented by most elliptic curve cryptosystems. The procedure of this dissertation divides into two hierarchies. First, the finite field GF(pm) and arithmetic among field elements are concerned in chapter 3 and chapter 4. Second, elliptic curve finite group E(GF(pm)) and arithmetic among point elements are concerned in chapter 5 and chapter 6. In addition, some mathematical concepts and theories used in this dissertation are reviewed in chapter 2, and the common elliptic curve cryptosystems are introduced in chapter 7.The main contributions of the dissertation are summarized as follows.(1) Elliptic curve cryptosystems in Optimal Extension Fields (OEF) , including ElGamal encryption algorithm, Diffie-Hellman key agreement scheme and elliptic curve digital signature algorithm (ECDSA), are implemented, and a software package, which is applicable to microcomputers, is developed.(2) Research on elliptic curve cryptosystems has mainly been focused on two types of finite fields GF(pm) in which p=2, m is positive integer or p is an adequately big prime, m=1. However, elliptic curve cryptosystems, based on both of the finite fields mentioned above, havecomputational difficulties. In this dissertation, we consider the character p = 232-s, and p is a prime of close to 32bit. In this field, the software implementation with fast arithmetic is obtained on 32bit microcomputers.(3)For the first hierarchy mentioned above, the multiplication and inversion in GF(pm) are two key operations. In order to improve their speed, "fast polynomial multiplication algorithm" and "fast algorithm of r-circulant matrix inversion" are proposed, which offer obviously computational advantages.(4)For the second hierarchy mentioned above, the key operation is the scalar multiplication, especially, the pairs of scalar multiplication used in certain practical elliptic curve cryptosystems. In the dissertation, a "fast Shamir algorithm represented by Five-element joint sparse form" is presented. And it is demonstrated that comparing with other similar algorithms, the total numbers of the computation of our algorithm can be saved about 10%, in the case of 192bit key.(5) In the implementation of elliptic curve cryptosystem, one of the key steps is to design and implement the base-point choice algorithm of elliptic curve finite group. Generally, this problem is reduced to quadratic residue problem of modulo a big prime number. But this reduction is not applicable to Optimal Extension Fields (OEF) . In order to solve this difficult problem, a "quadratic residue algorithm of Double- modulep,p(x)" is presented.(6)Security of cryptosystem is an important problem for implementation of elliptic curve cryptosystem. Therefore, enough secure elliptic curves are needed. Although the computation of order E(GF(pm)) for elliptic curve finite field is a very difficult problem, the case in Optimal Extension Fields(OEF)is relatively easy. In this dissertation, by using certain function of MIRACL systems, we got enough secure elliptic curves and a system parameter table for the impleme... |