论文部分内容阅读
本文主要介绍椭圆曲线上同态(同源)映射在椭圆曲线密码学方面的应用，如利用椭圆曲线上有效可计算的自同态加速点乘，配对，离散对数问题的计算，以及椭圆曲线上的困难问题归约等。特别的，针对Galbraith，Lin和Scott在09年欧密会上提出利用二次扭映射得到二次扩域上的椭圆曲线(简称为GLS曲线)，研究了利用其上存在的有效可计算自同态加速点乘计算的技术，并分析其离散对数问题的安全性。 首先，椭圆曲线上的同态映射，是本文关注的焦点。研究椭圆曲线上有效可计算同态映射的密码学应用，是本文的主要内容。 (1).Gallant，Lambert和Vanstone在2001年提出一种用椭圆曲线上有效可计算自同态加速点乘计算的方法(简称GLV方法)。本文总结了之前关于GLV方法的结果，并进一步研究了在一些特殊曲线(如GLS型曲线)上将GLV方法推广到高维情形的可行性。 (2).类比GLV方法，分析和总结了用椭圆曲线上有效可计算自同态加速双线性配对计算。该方法显著减少了计算配对过程中Miller迭代的次数。 (3).椭圆曲线上的扭曲映射是一类特殊的同态映射，它可将Tate配对和Weil配对等改造成对称的双线性配对。已知的扭曲映射只在超奇异的椭圆曲线上才存在并可有效构造。而对于通常椭圆曲线，扭曲映射只对嵌入次数为1的情况才存在。本文构造了两类特殊的嵌入次数为1的通常椭圆曲线，并给出相应的扭曲映射。同时，将反映超奇异椭圆曲线上配对求逆问题难度的Verheu1定理推广到这两类曲线上。 (4).总结了用椭圆曲线上自同态加速Pollard’sRho算法计算离散对数的方法。对存在m阶自同态的椭圆曲线，利用该同态映射可将其有理点分为若干等价类，从而使得PollardsRho算法加速因子√m。 其次，如何加快椭圆曲线上点乘的计算，是椭圆曲线密码学走向实际应用的主要问题。 本文重点考察了二次扩域上的GLS型椭圆曲线的快速点乘计算技术，并针对特征为2，3以及大素数p的情况分别讨论了该类曲线。对定义在大素数特征p的有限域上j-不变量为0，1728的GLS曲线给出了理想4维GLV分解，并利用其特殊的复乘结构使得标量分解的分量界为O(r1/4)，这样点乘计算迭代中二倍点次数可减少为原来的1/4。本文还推广了Brown等人关于“紧曲线”的分解方法，对j-不变量为0的通常椭圆曲线给出了最优的2维GLV分解。特别的，本文针对定义在Fp2上且j-不变量为0的GLS曲线，在x86-64平台上实现了其上的点乘运算。对于128bit安全级别的实例，本文的4维GLV方法运行时间大致是相同曲线上2维GLV方法的0.78，是Fp’上曲线2维GLV方法的0.78-0.87，与之前最快的X86-64平台上实现的点乘运算相比，该方法的时钟周期最快提高了27％。 最后，具有良好密码学性质的椭圆曲线的选取及其离散对数问题的计算，是椭圆曲线密码理论研究的两个核心问题。本文分析和总结了GLS曲线上DLP及相关问题的复杂性，并探讨了GLS曲线用于密码的可行性。