椭圆曲线上标量乘算法研究与改进

摘要

1985年,N.Koblitz和V.Miller提出椭圆曲线密码体制,使得密码体制在椭圆曲线上得到应用。与传统的公钥密码体制(例如RSA密码体制)相比,椭圆曲线密码体制使用相对比较短的密钥就可以达到相同的安全程度。因此,更短的密钥使得椭圆曲线密码体制的应用范围更加广泛,现在的微型设备很多都使用椭圆曲线密码体制来进行加密与解密。
　　计算速度是我们研究与应用椭圆曲线密码体制中最关心的一个问题。椭圆曲线密码体制的算法中,最耗时的运算就是标量乘运算,其占据了椭圆曲线算法总计算量的80％。研究者们通过各种各样的改进来提高标量乘的计算效率,研究成果颇丰。我们发现,大多数的改进都集中在标量的表示形式上,有单基数表示,双基数表示、多基数表示等等。我们在文中介绍并比较了一些常用的单基数表示的标量乘方法,并提出了新的标量乘方法。
　　二进制表示转换成一补数减法形式简单、快速,但是在减少二进制表示的汉明权的效果上并不是对所有的标量都有效。我们提出的新的标量表示方法基于二进制表示转换成一补数减法形式简单和快速的特点,但不是对标量的整个二进制表示进行一补数减法形式转换,而是选取二进制表示中满足转换条件的部分进行一补数减法形式转换。我们称新的标量表示方法为部分使用一补数减法形式(Partlyuse1’sComplementSubtractionform),简称PCS形式。非相邻表示型(NAF)表示作为一种被广泛使用的标量表示形式,其对减少标量乘的计算量有显著的效果。本文最后将PCS形式与NAF表示作对比,提出PCS形式的优越之处。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题背景及研究的目的和意义

1.2 国内外研究现状及分析

1.3 本文的主要研究内容

第2章 预备知识

2.1 椭圆曲线的概念

2.2 椭圆曲线上的点加运算和点乘运算

2.3 椭圆曲线离散对数问题

2.4 椭圆曲线密码

第3章 标量乘算法研究与分析

3.1 二进制方法

3.2 非相邻表示型方法

3.3 窗口方法

3.4 滑动窗口方法

3.5 标量乘算法对比分析

3.6 本章小结

第4章 基于一补数减法形式的改进算法

4.1 一补数减法形式方法

4.2 部分使用一补数减法形式方法

4.3 PCS方法与NAF方法比较与分析

4.4 本章小结

结 论

参考文献

声明

致谢