摘 要

数字签名是近年来研究的热点，多年来密码学者提出了很多关于离散对数问题和关于椭圆曲线的方案，然而时代在不断发展，人们在网络和计算机方面不断地取得进步，普通的基于离散对数的数字签名方案已经逐渐追不上时代的步伐，在安全方面可能会出现很大的漏洞，同时也有可能导致设计出的方案步骤比较繁多。

本文首先介绍了几类离散对数问题及解决这些问题的算法，分析了解决有限域上离散对数问题的困难性，并对数字签名方案的基本理论作了一些介绍。

然后本文基于离散对数问题，提出了三个新的数字签名----基于椭圆曲线离散对数问题的数字签名、基于离散对数的链式验证签名及将两者结合得到的基于椭圆曲线离散对数的链式验证签名。

接下来本文对三种方案的安全性作了简要分析，并且列举了可能出现的几类攻击，分析了这些攻击对提出的方案是否存在威胁，最终证明了这三个方案的安全性比普通的数字签名方案更高。

关键词：数字签名；离散对数；椭圆曲线；链式验证；公钥密码

Abstract

Digital signature is the hotspot of research in recent years, years cipher scholars put forward many on the discrete logarithm problem and on the elliptic curve encryption and digital signature scheme based on the system, but along with the development in computer network and people, ordinary discrete logarithm digital signature scheme based on has gradually can not catch up with the times the pace, in terms of security may there will be a big loophole and may lead to design the solution procedure is different.

In this paper, we first introduce several kinds of discrete logarithm problems and solve them, analyze the difficulty of solving the discrete logarithm problem in finite fields, and introduce the basic theory of digital signature schemes.

Then the discrete logarithm problem based on the proposed three new digital signature scheme - based on digital signature scheme based on the elliptic curve discrete logarithm problem, based on discrete logarithm chain verification signature scheme and elliptic curve discrete logarithm chain verification signature scheme based on a combination of both.

At the end of this paper, three schemes of safety made brief analysis, and lists the possible several classes of attacks, analysis of these attacks on the proposed scheme the existence of a threat, the ultimate proof of the security of the scheme is higher than the ordinary digital signature scheme.

key words：digital signature; discrete logarithm; elliptic curve; chain verification; public key cryptography

目录

摘要 I

Abstract II

第1章 绪论 1

1.1数字签名方案的发展概述 1

1.2数字签名的基本概念 2

1.3数字签名的分类 2

1.4数字签名方案的安全性及其攻击模型 3

1.5本文所做主要工作 4

第2章 预备知识 7

2.1单向函数 7

2.2哈希(Hash)函数 7

2.3离散对数问题 7

2.4计算复杂性 9

第3章 新的基于离散对数问题的数字签名方案 11

3.1 基于椭圆曲线离散对数问题的数字签名 11

3.1.1 基于椭圆曲线离散对数问题的数字签名方案的实现 11

3.1.2 基于椭圆曲线离散对数问题的数字签名方案安全性分析 12

3.2 基于离散对数的链式验证签名方案 13

3.2.1基于离散对数的链式验证签名方案的实现 13

3.2.2 基于离散对数的链式验证签名方案的安全性分析 14

3.3 基于椭圆曲线离散对数的链式验证签名方案 15

3.3.1基于椭圆曲线离散对数的链式验证签名方案的实现 15

3.3.2 基于椭圆曲线离散对数的链式验证签名方案的安全性分析 16

第4章 总结与展望 19

参考文献 21

致谢 23

第1章 绪论

数字签名是现代发展的重要产物，它既可以用作消息认证，也可以用作身份认证，是现代密码学领域的一个重要分支。数字签名的主要内容就是通过一个单向函数来处理一个需要传送的消息，最终得到一个唯一的数字串，而这个数字串被用来确定消息的来源，并最终核实消息是否在传送过程中发生了改变。一般情况下，发送者用自己的私钥来对数据进行加密，然后把它向接收者传递，当接收者收到后，接收者再用公钥对数据进行解密，从而确定消息的来源。

自密码学问世多年来，密码学者提出了很多关于椭圆曲线加密体制和离散对数问题的数字签名，然而时代在不断发展，人们在网络和计算机方面不断地取得进步，基于离散对数问题的普通的数字签名方案已经逐渐追不上时代的步伐，在安全方面可能会出现很大的漏洞，同时也有可能导致设计出的方案步骤比较繁多。

本文主要的研究目的是基于离散对数问题的难计算的特性设计出一个摆脱普通方案缺点的方案，降低数字签名系统对计算能力的需求，同时也相对降低公钥传输对带宽等资源的要求，最终得到一个既安全又有着不错的传输效率的方案。

1.1数字签名方案的发展概述

数字签名方案主要是基于公钥密码体制，而实现公钥密码体制思想主要是基于一些数学难题：大素数因子分解难题、二次剩余难题、离散对数难题。

1978年，基于大整数的分解问题被Adleman所提出。具体问题为对于一个给定的大整数n，要求出使得的两个大素数p和q。根据这个得到了第一个具体的签名算法，即RSA签名算法。