Research On The Application Of Negation Map In Elliptic Curve Cryptosystem

Point multiplication and elliptic curve discrete logarithm problem (ECDLP) are basic problems of elliptic curve (EC) cryptography. The efficiency of EC cryptosystem is dominated by the speed of point multiplication; the security of EC cryptosystem is determined by the computational complexity to solve ECDLP. This thesis investigates how negation map, an efficiently computable mapping in EC additive group, can be applied to accelerate point multiplication and reduce the complexity of solving ECDLP. It focuses on the following issues:1. Negation map provides an alternative way to compute point multiplication in the additive group using a different scalar. If the computational cost introduced by the new scalar is less than that of the original scalar, then the alternative scalar can be applied to accelerate point multiplication. Because this method has never been considered in previous researches, it can be combined with current algorithms to accelerate point multiplication by a further step. Research demonstrates that alternative scalar can reduce the number of point additions by 5% on average in repeated doubling algorithm. For non-adjacent form, alternative scalar can save 1.5 point additions on average. The speed-up is obtained at virtually no cost.2. In solving ECDLP, Pollard's method has time complexity , where n is the image space size of the iteration function, i.e., the cyclic group generated by point P. As automorphism of the elliptic curve additive group, negation map induces a partition comprised of equivalence classes . The image space n will shrink to half if the iteration function is defined over the above equivalent classes rather than EC points. However, point sequence generated by such iteration function suffers from fruitless cycles, which eliminates randomness of the sequence and renders Pollard's method ineffective. In this thesis, a stack-based cyclic detection algorithm[46] is adopted to quickly detect and escape from fruitless cycles. As a result, the sequence remains random; the speed of Pollard's method increases roughly by a factor of .3. Graphics Processing Unit (GPU) is empowered by massive data-parallelism, which provides new platform for parallelized Pollard's method. Since parallelized Pollard's is the state-of-the-art algorithm for solving ECDLP, research on its speed on GPU helps evaluate the security of EC cryptography. In this thesis, parallelized Pollard's with negation map is designed and implemented for 160-bit prime field curve on GPU. To make the code suitable for single-instruction, multiple-thread execution (SIMT), transformation is carried out on the code of the cycle-detection stack to eliminate branches; branchless multi-precision arithmetic is adopted to avoid branches. Experimental results show that total number of Pollard's iterations per second on GPU is two magnitudes higher than that on CPU.