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

摘要

基于SIMD指令和bitslice数据结构设计了GF(2m)上的ECC攻击算法,并对核心模块进行了优化。利用比特交换的方法提出了一个bitslice数据结构和非bitslice数据结构的快速转换算法,计算复杂度为O(nlogn),对算法简单调整后可适用于二元矩阵的快速转置；利用karatsuba-ofman算法和Montgomery并行求逆对椭圆曲线底层运算进行了优化,分析了计算复杂度,对ECC挑战中的ECC2-109和ECC2-131进行了测试,在单核Pentium IV3.0GHz平台上的迭代速度分别为133万次/秒和98万次/秒,攻击效率比Chris Monico的公开程序提高了1倍。