点乘和离散对数问题是椭圆曲线密码学的基础问题。点乘的计算速度直接决定椭圆曲线密码的实现效率;椭圆曲线离散对数问题的求解复杂度直接决定椭圆曲线密码的安全性。本文围绕椭圆曲线加法群中负映射易于计算这一性质,研究负映射在提高点乘速度、降低离散对数问题求解复杂度中的应用。本文的主要工作如下:1.本文从负映射出发提出了点乘的另一计算途径,使点乘的标量具有双重选择。若新标量的计算代价小于原标量,则可以替换原标量来加速点乘。现有的点乘算法均未考虑替换标量,因此该方法可与现有算法相叠加进一步提高点乘效率。研究表明,替换标量对重复倍点法平均可减少5%的点加运算,对Shamir同时多点乘平均可减少4%的点加运算,对非相邻表示型平均可减少1.5次点加运算,且优化开销几乎为零。2.用Pollard-算法求解椭圆曲线离散对数问题的时间复杂度取决于迭代函数像空间的规模,该空间是点P生成的n阶循环群。负映射是椭圆曲线加法群上的自同构,诱导出由等价类组成的划分。若将迭代函数定义在等价类上,则像空间缩小一半。但是由此定义的迭代函数生成的随机序列容易陷入无效循环,使算法失效。本文运用一种基于栈结构的循环检测算法快速检测并跳出无效循环,保持序列的随机性,使Pollard-算法速度提高约倍。3.图形处理单元(Graphics Processing Unit,GPU)具有大规模数据并行处理能力,为并行Pollard-算法提供了新的实现平台。因为该并行Pollard-是目前求解椭圆曲线离散对数问题最有效的方法,所以研究它在GPU平台上的运行速度有助于衡量椭圆曲线密码的安全性。本文在GPU上设计实现了160位素域上的并行Pollard-算法,并采用负映射加速机制。为适应GPU平台单指令多线程的执行特点,用代码变换消除了循环检测栈的分支语句。实验数据表明,并行Pollard-算法在GPU上的每秒迭代次数大约比CPU高两个数量级。
