Research And Implementation Of Multiple Point Multiplication Algorithms Of Elliptic Curve Cryptography

The security of elliptic curve cryptography (ECC) rests on the difficulty of solving the discrete logarithm problem over points on an elliptic curve. Currently the best algorithm known for solving the underlying mathematical problem in ECC takes fully exponential time, in contrast to the subexponential-time algorithm known for the integer factorization problem and the discrete logarithm problem. This means that significantly smaller parameters can be used in ECC than in other public key systems such as RSA and DSA, but with equivalent security level. The shorter key size generally leads to improved computational efficiencies and smaller storage and bandwidth requirements. Hence the elliptic curve cryptography seems to be the future standard of public key cryptography.The main focus of the thesis is the multiple point multiplication algorithm of elliptic curve cryptography. It consists of six chapters. In chapter one, some introductive materials are presented, including the motivations and the developments of the elliptic curve cryptosystems, the intentions of the research work, the main contents of the paper. In chapter two, some necessary and basic materials of the elliptic curves theory are introduced. In chapter three, the elliptic curve cryptography is studied. The key algorithms including point multiplication algorithms and multiple point multiplication algorithms of ECC are further investigated in chapter four. In 4.4 and 4.5, two multiple point multiplication algorithms are designed on the basis of analysis and research of known algorithms. The recoding of the scalar can be performed from the most significant bit (i.e. from left to right).Hence recoding and evaluation stage can be merged. These two algorithms are preferable on memory-constraint and limited-processing-power devices such as smartcard. In chapter five, the new multiple point multiplication algorithm is implemented using Visual C++. At last chapter six summarizes the whole paper and previews the further developments of the work.