Research on ECC Attacking Algorithm Based on SIMD Instructions

ECC is one of the most important public key cryptosystems which has higher security strength per bit compared with RSA and ElGamal. The break of ECC needs a great amount of computational resources. With the help of SIMD instructions, a bitsliced version of parallelized Pollard rho algorithm is proposed for the break of ECC over binary finite fields and some key operations are optimized. Based on the idea of bit swap, an efficient algorithm of converting data format between bitslice and non-bitslice is proposed, which can be implemented with basic logic instructions in CPU and avoid conditional branch. The computational complexity of the algorithm is O(n log n) and the slightly modified version can be used for the quick transposition of 0-1 matrix. The involved elliptic curve algorithm is improved with the help of Karatsuba-Ofman algorithm for multiplication and Montgomery trick for parallel inversion. The improved Pollard rho algorithm based on SIMD instructions is applied to the ECC2-109 and ECC2-131 of Certicom' ECC challenges, and the experimental results show that the iteration speed on the platform of one core Pentium 4 30GHz CPU reach 133 million and 098 million per second respectively, which is about one time faster than the program of Chris Monico, who is the winner of the challenge ECC2-109.