Sca Resistant Algorithms Of Scalar Multiplication Of Elliptic Curve Cryptography

At present, elliptic curve scalar multiplication is one of the important practical problems. Elliptic curve scalar multiplication is the main operation of elliptic curve cryptography (ECC) based protocols, such as ECIES, ECDSA, and ECDH. Computation speed of elliptic curve scalar multiplication will directly case affect implementation efficiency of ECC based cyptosystem, which is more considerable for smart card or cell phone, where the computing power, storage spaces, width of network is limited.Side-channel analysis (SCA) or information leakage analysis (ILA) refers to a new and emerging type of cryptanalysis that uses leaked side-channel information frome a cryptographic device to determine the secret key. It is a great threat to original elliptic curve scalar multiplication. Today, more and more attention has been driven to take countermeasure to defend SCA attack.Many mothds can be applied to enhance computing efficiency of elliptic curve scalar multiplication, such as signed binary presentation, non-adjacant form (NAF), mixed coordinates strategy, precomputation, addition chain and so on. Some special kind of elliptic curv, such as Koblitz curve, hyperelliptic curve, Montgomery-form elliptic curve, who possesses some special features, have more efficient scalar multiplication. There are three kinds of countermeasures to defend side channel analysis, unified addition formulae, regular point multiplication algorithm, and randomization techniques. Each such method will reduce the computation efficiency of elliptic curve scalar multiplication. A reasonable scalar multiplication should balance the computing speed and computing efficiency of cryptosystem. An ideal elliptic curve cryptosystem can be obtained only by integrateing and optimizing different methods to inhance computing efficiency and computing speed. This paper deeply analizes different kinds of implementation algorithm of elliptic curve scalar multiplication and countermeasurs to defend side channel analysis, and proposed some side channel analysis resistant elliptic curve scalar multiplication algorithms.The main contributions and accomplishments of this dissertation are as follows:1. Proposing an bintree addition chain based elliptic curve scalar multiplication.The concept of bintree was proposed, which enrich addition chain theory. A new scalar multiplication algorithm was proposed basing bintree addition chain. The algorithm adoppted a new mixed coordinate strategy and got the most fast point addition formulae , which enhances computing efficiency. Special structure of bintree addition chain maks it can defend side channel analysis naturally.2. Proposing a improved algorithms for securing elliptic scalar multiplication against side channel attacks.Considering the general binary method is not secure, the paper proposd a simple signed binary encoding scheme, wich is applied to binary window based scalar multiplication. The algorithm can resist side channel analysis and make up some secure flaw. In the end, An efficient randomization technique, using some random variables within the point addition operation, has also been proposed as a possible countermeasure against a DPA-style attack on the window-family algorithm.3. Proposing a improved Montgomery ladder based algorithm.The algorithm inherits secure feature of resisting side channel analysis from basis of Montgomery ladder algorithm. Meanwhile the secure level is further improved. The algorithm, which is to get high computing speed, is particularly applicable to multi-processor cyptophic devices. A y -coordinate recovery method is also apllied to improve computation speed further.4. Proposing a new SCA resistant scalar multiplication of Montgomery-form curve.The concep of Fabonacci-form series was proposed. Special structure of Fabonacci-form series takes full advantages of high computing speed of Montgomery-form curve. Addition chain method is also applied to resist simple side channle analysis. The length of addition chain was optimized by golden ratio addition chain, which improved computing efficiency deeply.5. Proposing a new scalar multiplication algorithm based on randomized projective coordinate expression.Randomized projective coordinate expression is one of the main measures to SCA attack. In the algorithm, base point P is randomized, and the its computational cost is the same as the computational cost of an operation of points without randomized expression. In the case of a Montgomeryform elliptic curve, we compute addition of two points in randomized projective coordinates using these difference points in unrandomized projective coordinates, namely, the Z-coordinate of the point to be 1, the resultant point is in randomized projective coordinates, and no extra field operations are required. The scalar multiplication method with randomized projective coordinates on a Montgomery-form elliptic curve is applicable to other types of elliptic curve, such as the Weierstrass form, and other coordinate systems, such as Jacobian coordinate. The scalar multiplication method on a Montgomery-form elliptic curve is effective against the simple power analysis (SPA) attack and is much faster than other scalar multiplication methods which prevent SPA.6. Proposing a new scalar multiplication algorithm based on randomized projective coordinate expression.The algorithm provides a differently randomized signed-scalar representation at every multiplication execution so that it makes DPA infeasible. In addition it uses an addition-subtraction multiplication algorithm to resist SPA. It also seems to be able to defeat timing attacks because every execution time of a scalar multiplication changes according to every differently randomized signed-scalar representation. The result shows that it needs no additional computation load compared to the ordinary binary scalar multiplication.