Research On Some Elliptic Curve Cryptographic Algorithms

Elliptic curve public key cryptography is based on elliptic curve discrete log-arithm problem. Since there are no general-purpose sub-exponential algorithms known for the elliptic curve discrete logarithm problem, the key of elliptic curve cryptography systems is shorter than that of other public key cryptography sys-tems such as RSA. The international elliptic curve cryptography standards has been proposed such as FIPS186-2, ANSI X9.62, and IEEE P1363. In order to meet the demand for electronic authentication service system applications, Chi-nese also proposed SM2elliptic curve public key cryptography standard. Elliptic curve cryptography has been more and more widely used, which is mainly used in constrained environments, such as smart cards, chips and so on.In the use of elliptic curve cryptography, scalar multiplication is the most time-consuming. We mainly focus on speeding up scalar multiplication algorithms with no precomputations by reducing their Hamming weights. In this aspect, the main achievements are as follows.1. We proposed a fast double base conversion algorithm by searching near a straight line, to improve the efficiency of greedy algorithm for calculating double-base chain. And we improved the efficiency of greedy algorithm for calculating triple-base chain by searching near a plane.2. We proposed a new algorithm, called add/sub algorithm, to calculate s-calar multiplication. The density of triple-base chains gained by this algorithm with base{2,3,5} is1/5.61426, which is the lowest among the existing algorithm-s. The speed of calculating scalar multiplication using the chain gained by this algorithm is fastest. Recoding is very easy and efficient, and together with the add/sub algorithm are very suitable for software implementation.3. We gave the upper bound of the length of the canonic triple-base repre- sentation of integer x with base{2,3,5}, which is and showed that there are infinitely many integers x whose shortest triple-base representations with base{2,3,5} have length greater than where c is a positive con-stant. Then the presented upper bound on the length of the canonic triple-base representation is meaningful.The encryption process can be detected in some environments, where scalar multiplication should be resistant to simple power analysis The Montgomery al-gorithm is resistant to simple power analysis for computing scalar multiplication on elliptic curves. The main achievements in this aspect are as follows.1. We presented new formulae to compute point addition and point doubling on an elliptic curve over a prime field to improve the Montgomery algorithm. Moreover, this is the first efficient method that can resist simple power analysis for calculating scalar multiplication on the SM2.2. We presented new formulae to compute point addition and point doubling on an elliptic curve over a finite filed of character three to speed up the scalar multiplication of the Montgomery algorithm.Multi-scalar multiplications are needed in the signature verification of the elliptic curve digital signature algorithm. We introduced the concept of a join-t triple-base chain. Our algorithm, named the joint binary-ternary-quintuple method, is able to find a shorter joint triple-base chain for the sparseness of joint triple-base number systems. This algorithm has the lowest Hamming weight when using same number of pre-computed points. And the cost of calculating multi-scalar multiplications using joint triple-base chain gained by this algorithm is less than that of existing algorithms.Identity-based encryption schemes require to hash messages into an elliptic curve. The main achievements in this aspect are as follows.1. We construct a deterministic hash function from a prime field into twisted Edwards form elliptic curves.2. We propose four deterministic encoding algorithms to hash messages into Montgomery-form elliptic curves. Moreover, we provide new functions indifferen- tiable from a random oracle based on our deterministic encodings.3. Moreover, we provided new functions indifferentiable from a random oracle based on our deterministic encodings. We construct a hash function from the plaintext space to C34curves. Based on our deterministic encoding, we provided a new function indifferentiable from a random oracle.The upper three works laid the groundwork for identity-based encryption on elliptic curves and C34curves.