基于SIMD指令的ECC攻击算法研究  

Research on ECC Attacking Algorithm Based on SIMD Instructions

作　　者：赵龙[1] 韩文报[1] 杨宏志[1] 

机构地区：[1]解放军信息工程大学信息工程学院信息研究系,郑州450002

出　　处：《计算机研究与发展》2012年第7期1553-1559,共7页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2009AA01Z417);国家"九七三"重点基础研究计划基金项目(2007CB807902);全国优秀博士学位论文作者专项基金项目(FANEDD-2007B74)

摘　　要：ECC是目前比特安全强度最高的公钥密码体制,对它的攻击需要大量的计算资源.基于SIMD指令和bitslice数据结构设计了GF(2m)上的ECC攻击算法,并对核心模块进行了优化.利用比特交换的方法提出了一个bitslice数据结构和非bitslice数据结构的快速转换算法,计算复杂度为O(nlogn),对算法简单调整后可适用于二元矩阵的快速转置;利用Karatsuba-Ofman算法和Montgomery并行求逆对椭圆曲线底层运算进行了优化,分析了计算复杂度.对ECC挑战中的ECC2-109和ECC2-131进行了测试,在单核Pentium 4 3.0GHz平台上的迭代速度分别为1 330 000次/s和980 000次/s,攻击效率比Chris Monico的公开程序提高了1倍.ECC is one of the most important public strength per bit compared with RSA and ElGamal. key cryptosystems which has higher security The break of ECC needs a great amount of computational resources. With thc 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（nlogn） 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.0 GHz 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.

关 键 词：椭圆曲线密码体制 椭圆曲线离散对数问题 ECC挑战 Pollard rho算法 SIMD指令 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]