有限域上椭圆曲线基本算法快速实现的研究

摘要

本文旨在提高有限域上椭圆曲线算术运算的效率，主要研究了二进制扩域上的平方运算、有限域上的求逆运算以及椭圆曲线上的标量乘运算，并针对三种不同的运算分别提出了一种快速计算的算法。取得的主要研究成果如下：
　　提出了一种快速计算二进制扩域上平方运算的算法。该算法通过构建一张二维表，然后使用查表的方式来计算二进制扩域上元素的平方，从而加快二进制扩域上平方运算的速度。因二进制扩域中元素的特殊性，使得查询表不需要更新，且可固定在内存中或直接写进硬件设备中。因此，本算法中将该二维查询表直接写入了内存中，且将所要查询的内容作为索引下标以提升查找效率。此外，因所要计算的元素的每个字节之间无任何关联性，该算法更加适用于并行计算，并能进一步提高二进制扩域上平方运算的效率。
　　提出了有限域上求逆运算的两个安全外包计算算法，并给出了安全外包的形式化定义和安全模型。在给出定义的基础上，提出了一个具体的单元素安全求逆外包计算算法。为了降低云服务器的开销，本文结合联合求逆算法，进一步提出了一个可用于多元素求逆的安全外包算法。最后，给出了外包计算算法的安全性证明和算法的效率分析与比较。
　　研究了椭圆曲线上的标量乘运算，提出了窗口查表算法。该算法根据窗口的大小预先计算一些简单的标量乘运算，并将预先计算的结果存储起来构造出一张二维查询表。后续计算中，在遇到相同计算任务时，该算法通过用查表来代替真正计算的方式来提高标量乘运算的效率。该算法在所要计算的标量的bit长度比较大时更加适用。