Fp上抵抗SPA攻击的椭圆曲线快速标量乘算法的研究

摘要

椭圆曲线密码体制具有以下独特的优点:密钥短、计算速度快、安全性高等，适合在带宽、存储空间、处理能力和功耗等受限的环境使用，它经过30年的发展历程，已经从理论研究阶段走向了实际应用阶段，成为了一种最有应用前景的公钥密码体制，越来越受密码学者的重视。本文围绕素域（Fp）上椭圆曲线密码体制的快速实现展开，主要在点的加法运算、标量表示和标量乘本身、预计算等几个方面进行了深入的研究。
　　Longa等人[14]提出了一种替换技巧:2ab=(a+b)2-a2-b2，如果a2，b2是已知条件或者本来就需要在其它式子中计算，那么我们就只需要计算(a+b)2，也就是用时间开销低的平方运算(S)替换时间开销高的乘法运算(M)，从而节约一定的时间开销。文献[14]把这种方法用到了Jacobian坐标系下点之间的运算，使得点加和倍点的运算量减少。我们可以把这种方法应用到几乎所有的坐标系下的点加和倍点公式中，特别是Modified雅克比坐标系下的点加和倍点公式中，从而在很大程度上减少标量乘法的计算时间。另一方面，Cohen等人在文献[4]给出了混合坐标系的概念及部分混合坐标系下点的加法运算的时间开销，但并没有给出具体的计算方法，本文给出了一种混合坐标系下的点加和倍点公式的计算方法，且该方法中有三个公式的计算比文献[4]中计算的速度快。
　　在标量表示及标量乘法方面，Okeya等人[23]对窗口宽度为w的标量k的非相邻表示形式NAFw（k）做了研究，得出了一种能够抵抗简单能量攻击(SPA)的标量乘法算法。由于快速标量乘法基本都涉及到预计算，Meloni[16]和Longa[15]分别提出了雅克比坐标系下co-Z加法算法和相应的预计算方法，根据点之间的数值关系，只使用一次求逆运算就能求出仿射坐标系下的所有预计算点，节约了大量的时间开销;本文根据该雅克比坐标系下的预计算方法，推出了Chudnovsky雅克比坐标系下预计算点的计算方法。
　　根据Cohen等人[4]提出的坐标系选择的方法，研究了在能够抵抗SPA攻击的标量乘法算法下如何选择坐标系才能使得运算速度较快，分析了预计算点在仿射坐标系和Chudnovsky雅克比坐标系两种坐标系下整个标量乘法的时间开销，并给出了点加、倍点和预计算方法改进后标量乘运算速度提升的百分比。

目录

声明

摘要

第一章 绪论

§1．1 研究背景与意义

§1．2 素域及椭圆曲线

1．2．1 素域

1．2．2 素域上的椭圆曲线

§1．3 椭圆曲线密码算法在不同坐标系下点的加法运算

1．3．1 仿射坐标系

1．3．2 射影坐标系

1．3．3 雅克比坐标系

1．3．4 Chudnovsky雅克比坐标系

1．3．5 Modified雅克比坐标系

1．3．6 混合坐标系

§1．4 椭圆曲线标量乘算法

§1．5 雅克比坐标系下的co-Z加法算法及其预计算方法

1．5．1 雅克比坐标系下的co-Z加法算法

1．5．2 利用雅克比坐标系下的co-Z加法算法进行预计算

第二章 快速及安全算法的研究

§2．1 快速点加和倍点运算

§2．2 抵抗简单能量攻击的标量乘算法

§2．3 Chudnovsky雅克比坐标系下的预计算

第三章 标量乘运算中坐标系的选择及相应的时间开销

§3．1 预计算点选择仿射坐标系表示时的时间开销

§3．2 预计算点选择Chudovsky雅克比坐标系表示时的时间开销

§3．3 本章小结

第四章 总结

参考文献

致谢