Research On Several Problems Of Elliptic Curves Related To Cryptography

Elliptic curves have a history of more than one hundred years being studied as a pure mathematic object. As the development of cryptography, and especially after the advent of public key cryptography, elliptic curves began to have many practical applications. By far, the most important applications are elliptic curve cryptography (ECC) and elliptic curve method (ECM).ECC has the highest cryptographic strength per bit, and the advantages of shorter secret key and higher speed make it become the standard public key primitive for mobile devices and high security applications. ECM is the best method for detecting prime factors of middle size and plays an important role in the cofactorizaton step of GNFS for RSA. The reseach of ECC and ECM has caught great attention of the cryptographic society. On the one hand, the optimum implementations of relevant algorithims can be used to improve the efficiency of breaking ECC and RSA, which would give us a better appreciation for thier security level. On the other hand, the process of implementation contains many interesting theoretical problems. For example, the research of isomorphism classes and distribution of rational points can help to select better elliptic curves, and the study of pseudorandom sequences from elliptic curves can be used to generate random numbers and seek potential weekness for ECC in new aspects.This thesis mainly focuses on several problems related to ECC and ECM, including the isomorphism classes and distribution of rational points, the pseudorandom property of elliptic curve linear congruential generators (EC-LCG), the attack of ECC using SIMD instructions, the optimized implementation of ECM on the GPU platform. The main results are as follows:1. Two groups of representations are constructed. As to the minimum coefficient in each isomorphism class, the theoretical upper bound is derived using exponential sums and the actual value is analyzed through probability. The expectation and variance of the number of rational points is evaluated when one coefficient is fixed and the other coefficient runs through Fq or the quadratic residue of Fq. The expectation is evaluated when the two coefficients equals and run through Fq or the quadratic residue of Fq. The necessary and sufficient condition when the number of rational points divisible by some prime is proposed with division polynomials. The possibility of the number of the rational points divisible by 2 and 3 is discussed in detail when one coefficient is fixed and the other coefficient runs through Fq or the subgroup of Fq.2. The distribution of a segment of consecutive bits in EC-LCG over prime field is studied systemically. For the prime p of general form, the segment located in the lower half is proved to have well distribution. For the prime p=2n?c, where c is a very small constant, the segment located in the upper half or in the middle part is also proved to have well distribution. As to EC-LCG over binary field, well-ditribution measure and correlation measures of order k are evaluated for the coordinate binary sequences, so are the balance and linear complexity for the multidimensional case. Two families of pseudorandom binary sequences are constructed from coordinate sequences. Several methods of attacking EC-LCG are proposed. If enough x-coordinates are given, the EC-LCG will be recovered completely or partially even with the parameters unknown.3. Three algorithms of Montgomery multiplication using SIMD instructions are devised. Based on the best one, the implementation scheme and experimental results of attacking ECC over prime field are provided. Binary polynomial multiplications using SIMD instructions are studied in non-bitsliced and bitsliced data format separately and an efficient algorithm of transforming between the two data format is proposed based on the idea of bit swap. After that, the implementation scheme and experimental results of attacking ECC over binary field are provided using mixed data format. The expectation and variance of computational complexity for solving multiple ECDLP simultaneously are evaluated with the knowledge of probability, which shows that the stability of total computational complexity is growing and the average running time for one instance is descending as the increase of the number of discrete logarithm instances.4. An algorithmic performance evaluation model for the GPU platform is proposed. Based on the analysis of the prime facets of GPU architecture like device instructions, memory hierarchy, memory access mode and thread scheduling, an explicit time-consuming evaluation formula was established, which provides theoretical guidelines for choosing the best implementation scheme. Three algorithms of Montgomery multiplication based on floating-point operation and integer operation in GPU are proposed. Their efficiency is analyzed and compared with the above performance evaluation model. Finally, the implementation scheme and experimental results of ECM are provided based on the best algorithm of Montgomery multiplication.