Research on Some Elliptic Curve Cryptographic Algorithms 

Author  YuWei 
Tutor  LiBao; HuHongGang 
School  University of Science and Technology of China 
Course  Information Security 
Keywords  Elliptic Curve Public Key Cryptography Hamming Weight ScalarMultiplication Resistant to Simple Power Analysis MultiScalar Multiplication Hash Function 
CLC  TN918.1 
Type  PhD thesis 
Year  2013 
Downloads  85 
Quotes  0 
Elliptic curve public key cryptography is based on elliptic curve discrete logarithm problem. Since there are no generalpurpose subexponential 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 systems such as RSA. The international elliptic curve cryptography standards has been proposed such as FIPS1862, ANSI X9.62, and IEEE P1363. In order to meet the demand for electronic authentication service system applications, Chinese 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 timeconsuming. 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 doublebase chain. And we improved the efficiency of greedy algorithm for calculating triplebase chain by searching near a plane.2. We proposed a new algorithm, called add/sub algorithm, to calculate scalar multiplication. The density of triplebase chains gained by this algorithm with base{2,3,5} is1/5.61426, which is the lowest among the existing algorithms. 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 triplebase repre sentation of integer x with base{2,3,5}, which is and showed that there are infinitely many integers x whose shortest triplebase representations with base{2,3,5} have length greater than where c is a positive constant. Then the presented upper bound on the length of the canonic triplebase representation is meaningful.The encryption process can be detected in some environments, where scalar multiplication should be resistant to simple power analysis The Montgomery algorithm 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.Multiscalar multiplications are needed in the signature verification of the elliptic curve digital signature algorithm. We introduced the concept of a joint triplebase chain. Our algorithm, named the joint binaryternaryquintuple method, is able to find a shorter joint triplebase chain for the sparseness of joint triplebase number systems. This algorithm has the lowest Hamming weight when using same number of precomputed points. And the cost of calculating multiscalar multiplications using joint triplebase chain gained by this algorithm is less than that of existing algorithms.Identitybased 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 Montgomeryform 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 identitybased encryption on elliptic curves and C34curves.