sa数字签名算法c语言,椭圆曲线数字签名算法(ECDSA).pdf

摘要

椭圆曲线数字签名算法(ECDSA)是使用椭圆曲线对数字签名算法(DSA)的模拟。

ECDSA 于 1999 年成为 ANSI 标准，并于 2000 年成为 IEEE 和 NIST 标准。它在 1998年既

已为 ISO 所接受，并且包含它的其他一些标准亦在 ISO 的考虑之中。与普通的离散对数问

题(discrete logarithm problem DLP )和大数分解问题(integer factorization problem IFP)

不同，椭圆曲线离散对数问题(elliptic curve discrete logarithm problem ECDLP )没有亚

指数时间的解决方法。

因此椭圆曲线密码的单位比特强度要高于其他公钥体制。

本文将详细论述 ANSIX9.62 标准及其协议,安全，实现，互操作性方面的问题。

1、介绍

数字签名算法(DSA)在联邦信息处理标准 FIPS 中有详细论述，称为数字签名标准。它的

安全性基于素域上的离散对数问题。椭圆曲线密码(ECC)由 Neal Koblitz 和 Victor Miller

于 1985 年发明。它可以看作是椭圆曲线对先前基于离散对数问题(DLP)的密码系统的模

拟，只是群元素由素域中的元素数换为有限域上的椭圆曲线上的点。椭圆曲线密码体制的安

全性基于椭圆曲线离散对数问题(ECDLP)的难解性。椭圆曲线离散对数问题远难于离散

对数问题，椭圆曲线密码系统的单位比特强度要远高于传统的离散对数系统。因此在使用较

短的密钥的情况下，ECC 可以达到于 DL 系统相同的安全级别。这带来的好处就是计算参

数更小，密钥更短，运算速度更快，签名也更加短小。因此椭圆曲线密码尤其适用于处理能

力、存储空间、带宽及功耗受限的场合。

ECDSA 是椭圆曲线对 DSA 的模拟。ECDSA 首先由 Scott 和 Vanstone 在 1992 年为了响应

NIST 对数字签名标准(DSS)的要求而提出。ECDSA 于 1998年作为 ISO 标准被采纳，在

1999 年作为ANSI 标准被采纳，并于 2000 年成为 IEEE 和 FIPS 标准。包含它的其他一些

标准亦在 ISO 的考虑之中。本文中我们将介绍ANSI X9.62 标准。也将介绍一些签名的基础

知识以及协议、安全性、实现、互操作性方面的问题。

本文其他部分的安排如下：

第二节中我们将回顾数字签名方案和 DSA，

第三节和第四节将分别介绍有限域和椭圆曲线，

第五节将讲述域参数的产生和参数有效性的验证，

第六节将讲述密钥对的产生和公钥有效性的验证，

第七节的内容是 ECDSA 的签名和验证过程。第八章论证 ECDSA 的安全性，

第九节和第十节讲述的是 ECDSA 协议和实现方面的问题。

2、数字签名方案

2.1 背景知识

数字签名的目的是提供一个手写签名的数字化副本。签名是一个依赖于签名者私钥和被签名

一段消息的比特串。签名必须是可验证的，即如果对签名的真实性存在疑问，必须由一个中

立的第三方作出公正的裁决，并且无需知道签名者的私钥。对签名的抵赖以及伪造签名应该

能被发现。

本文论述的是非对称摘要数字签名。“非对称”即用户的密钥对各不相同。用户的私钥用于

签名，其他用户用他的公钥来检验签名的真实性。摘要是指对一段消息先用哈希函数进行摘

要计算，尔后再对消息摘要进行签名，而不是消息。

安全性：

从理论上讲，在选择消息攻击下，数字签名应该是不可伪造的。这一概念由 Goldwasser，

Micali 和 Rivest 提出。更一般的讲就是攻击者获得用户 A 的摘要和签名，但他无法用其他

的摘要来伪造这样一个签名。

应用：

数字签名方案用于以下一些用途：数据完整性(确保数据没有被未知或未授权的中间人改

变)，数据源认证(确保数据的来源是可信的)，不可否认性(确保用户不能对自己的行为

进行抵赖)。数字签名是密码学协议的基本组成部分，并且可以提供其他一些服务如：身份

认证(FIPS 196，ISO/IEC 9798-3)，密钥传递前的认证(ANSI X9.63 ，ISO/IEC 11770-3)，

经验证的密钥协商(ISO/IEC 11770-3)。

分类：

数字签名方案可以根据所基于的数学难题进行分类：

1、基于大整数分解(IF)的方案，安全性基于大整数分解的难度。实例有 RSA 方案和 Rabin

方案。

2、基于离散对数 (DL)的方案，安全性基于有限域上普通的离散对数问题。实例包 El