Hunan University of Arts and Science, Changde, 415000, Hunan, Mainland of P.R.China

---

Abstract—On purpose to elevate the efficiency of elliptic curve scalar multiplication in the device with weak computation power and to improve computational security, in this paper we pioneer a novel algorithm named Improved- m-ary, which is based on the depth first addition chain scheme and the improved m-ary mechanism compatible with a flexible width window. At first, we research and analyze the advantages of addition-chain-method, m-ary and other algorithms respectively in terms of speeding computation by comparison. It is discovered that the proportion of atomic operation and window width are 2 key factors which keep the speed of scalar multiplication and its computation cost in a leash. Then, an innovative scalar-point-multiplication algorithm is designed by the project crew on the basis of findings of project research. At last, the results of theoretical analysis and experimentation statistics demonstrate that by this algorithm the average of hamming weight of the scalar as a multiplicator could be undercut and the computation cost of point-scalar-multiplication could be lowered to an amazing extent. In addition, because of its built-in scheme whereby the window width is randomized constantly it presents a favorable strong immunity against most attack methods hinged on power analysis . As a whole, it is potential that Improved-m-ary be a practical and promising fast scalar multiplication method alternative.

Index Terms—Addition Chain; Scalar Multiplication; Flexible Window Width; ECC; Information Security.

[PDF]

Cite: WenXue Tan, YiYan Fan , XiPing Wang and XiaoPing Lou, "An Innovative Scalar Multiplication Method Based on Improved m-ary," Journal of Software vol. 7, no. 11, pp. 2470-2477, 2012.