椭圆曲线数字签名算法（ECDSA）中文版

密码学，数字签名，椭圆曲线算法

5星 · 超过95%的资源需积分: 50 185 浏览量 2011-11-02 12:24:34 上传评论 5 收藏 199KB DOC 举报

资源详情

资源评论

资源推荐

椭圆曲线数字签名算法（ECDSA）

原文 The Elliptic Curve Digital Signature

Algorithm (ECDSA)

 公司

（翻译部分内容有删节）

摘要

椭圆曲线数字签名算法（ ）是使用椭圆曲线对数字签名算法（ ）的模拟。

 于  年成为  标准，并于  年成为  和  标准。它在  年

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

问题（ !"#）和大数分解问题（$%&$

!'#）不同，椭圆曲线离散对数问题（  ()

!"#）没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高

于其他公钥体制。本文将详细论述 *+, 标准及其协议和实现方面的问题。

1、介绍

数字签名算法（）在联邦信息处理标准 '# 中有详细论述。它的安全性基于素域上

的离散对数问题。

椭圆曲线密码（）由 -!& 和 . 于 / 年发明。它可以看作是

椭圆曲线对先前基于离散对数问题（"#）的密码系统的模拟，只是群元素由素域中的数

换为有限域上的椭圆曲线上的点。椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题

（"#）的难解性。

椭圆曲线离散对数问题远难于离散对数问题，椭圆曲线密码系统的单位比特强度要远高于

传统的离散对数系统。因此在使用较短的密钥的情况下， 可以达到于 " 系统相同的

安全性。这带来的好处就是计算参数更小，密钥更短，运算速度更快，签名也更加短小。

因此椭圆曲线密码尤其适用于处理器速度、带宽及功耗受限的场合。

 是椭圆曲线对  的模拟。 首先由 .$$ 在  年为了响

应  对数字签名标准（）的要求而提出。 于  年作为  标准被采纳，

在  年作为  标准被采纳，并于  年成为  和 '# 标准。包含它的其他

一些标准亦在  的考虑之中。本文中我们将介绍 *+, 标准。也将介绍一些签名

的基础知识以及协议及实现方面的问题。

本文其他部分的安排如下：第二节中我们将回顾数字签名方案和 。第三节和第四节将

分别介绍有限域和椭圆曲线。第五节将讲述域参数的产生，第六节将讲述密钥对的产生。

第七节的内容是  的签名和验证过程。第八章论证  的安全性。第九节和第

十节讲述的是  协议和实现方面的问题。

2、数字签名方案

2.1 背景知识

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

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

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

能被发现。

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

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

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

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

01 和 ) 提出。更一般的讲就是攻击者获得用户  的摘要和签名，

但他无法用其他的摘要来伪造这样一个签名。

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

间人改变），数据源认证（确保数据的来源是可信的），不可否认性（确保用户不能对自

己的行为进行抵赖）。数字签名是密码学协议的基本组成部分，并且可以提供其他一些服

务如：身份认证（ '#, ， 2345 ），密钥传递前的认证（ 

*+,5，23345），经验证的密钥协商（23345）。

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

1、基于大整数分解（'）的方案，安全性基于大整数分解的难度。实例有  方案和

!$ 方案。

2、基于离散对数（"）的方案，安全性基于有限域上普通的离散对数问题。实例包括

0，$， 和 6!4(  方案。

3、基于椭圆曲线（）的方案，安全性基于椭圆曲线离散对数问题。

2.2 数字签名算法

 于  年由  提出，并在 '#, 中得到确认。 可以看作是 0

签名方案的一个变形。其安全性建立在素域上的离散对数问题的困难性之上。

 参数的产生。每个用户的安全参数产生如下：

1、选择 , 比特的素数 7 和 8 比特的素数，满足 79 4。

2、在有限域 : ;中寻找 7 阶循环子群的生成元 ，具体方法是在 : ;选取元素  计算

<= 4>27 ，当 ? 时即找到满足要求的 。

3、域参数就是，7 和 。

 密钥对的产生。每个拥有域参数，7 和  进行如下操作：

1、选择伪随机数 @ 满足 A@A 4。

2、计算 6<@ 。

3、用户的私钥是 @，公钥是 6。

 签名过程：

1、选择伪随机数 B 满足 ABA 4。

2、计算 *<B ，<*7，若 < 则返回第一步。

3、计算 B47。

4、计算 <C4=>。

5、计算 <B4=D@>7，若 < 则返回第一步。

6、对消息  的签名就是=E>。

 签名的验证。为了验证=E>是对  的签名，需要使用签名者的域参数= E7E>和公钥

6 进行如下运算：

1、验证 ， 在区间FE74G中。

2、计算 <C4=>。

3、计算 H<47。

4、计算 (<H7 和 (<H7

5、计算 *<(6( 及 )<*7。

6、如果 )< 则认可此签名。

安全性分析。由于  和  均小于 7，故  签名长度小于 5 比特。 的安全性依赖

于两个方面，它们都基于离散对数问题的难解性，一个是 : ;上的离散对数问题，目前已

有数域筛算法去加以解决，这是一种亚指数级的算法。其平均运算时间为：

=@ ==D=>>=$ >25=$$ >25>>

其中  约为 +5，若是 8 比特的素数，则上式的计算量是无法接受的。因此目前

8 比特的  可以应付现有攻击。另一个是 7 阶子群上的离散对数问题，给定

，7， 和 6，6<@ ，要寻找 @，目前最好的算法是 #I 算法，大约要

做

7=J72>

步。若 7 是 , 比特的，则该算法在计算上不可行，因此  是很安全的。 的安全

性主要取决于和 7 的尺寸。增加其中一个的尺寸而不增加另一个的尺寸对安全性的提高

并无益处。此外，对两种离散对数问题解决算法的提高都会削弱 。

安全参数的产生。 的早期版本受到了一些批评，因此 '#, 推出了一种新模式以

产生素数以及“可证明的随机性”。它可以防止用户故意构造一个利于破译的素数（例如可

以由  来产生域参数并发送给用户）。 '# 指定了两个模式，分别使用 C4 和

，产生伪随机私钥 @。'#, 指定使用这两种模式以及其他经过 '# 认可的安全

模式。

3、有限域

我们将简要介绍有限域的知识。更多详细内容请参看其他书籍。有限域由一个有限集合 '

和 ' 上的两个二元运算组成，这两个运算满足某种运算规则，分别称为加法和乘法。有限

域的阶即域中元素的个数。当仅当 7 是素数时存在一个 7 阶有限域，这个有限域是唯一的，

记作 '7。有很多方法可以描述 '7 的元素，有些描述方式可以使域上的软件及硬件运算更

加高效。若 7< ，其中为素数， 为正整数，则称为 '7 的特征， 称为 '7 的度。

至于椭圆曲线密码，一般基于素域或是多项式域。在 5+ 和 5+ 中我们将分别介绍这两种

有限域上的元素和运算以及多项式域的两种表示方法：多项式表示方法和正规基表示方法。

3.1 有限域 Fp

# 为素数，有限域 ' 称为素域，由整数集KEELLE 4M和其上的符合下列规则的运算组

成：

4加法：E!N ，D!<， 为  与 ! 的和模所得的值。

4乘法：E!N ，;!<， 为  与 ! 的积模所得的值。

4求逆运算： 是 ' 中的非零元素， 的逆是唯一的，记作 4，有 ;4<

例 1 ．'5，全部元素为 KEELLEM ，其上三种运算： D<， ;<5，4

<5。

3.2 有限域 F2m

' 称之为特征为  的有限域，可以看做是 ' 上的  维向量空间。' 中存在  个不

同的元素 OEOLLEO4，任一个 ON' 均可写为以下形式：

O<PPDPODLLDP4O4PNKEM

集合KOEOLLEO4M称为 ' 在 ' 上的基。有这样一个基，域中所有元素就可以

用一个比特串=PEPELLP4>来表示。这样，加法就可以用向量的逐比特异或运算来

表示，乘法运算则依赖于基的选择。

基的选择方式是多种多样的。一些基可以使运算变得高效。*+, 给出了两种基，

分别是多项式基和正规基。

多项式基

%=@><@D%4@4DLL%@D%@D%（QNKEM）是 ' 上的  次本原多项式。

域元素。有限域 ' 由 ' 上的所有不多于  次的多项式组成。

'<K4@4DLLD@D9NKEMM

域元素 4@4DLLD@D 可以写为比特串

=4ELLE>

形式。

因此 ' 的元素可以写为长度为  的比特串。乘法单位元是=EELEE>，加法零元是

全零串=EELLE>。

域运算。

4 加法： <=  4ELLE> ， !<=!4ELLE!E!> ， D!<<=4E

LLEE>，<*!。

4 乘法： <=  4ELLE> ， !<=  !4ELLE!E!> ， ;!<<=4E

LLEE>，多项式 4@4DLLD@D 由=4@4DLLD@D>;=!4

@4DLLD!@D!>模 %=@>而来。

4求逆运算： 是 ' 中的非零元素，4 满足 4;<

例 2.有限域 '8E模多项式为 %=@><@8D@D，有限域中 , 个元素分别为：

=>=>@=>

@D=>@=>@D=>

@D@=>@D@D=>@5=>

@5D=>@5D@=>@5D@D=>

@5D@=>@5D@D=>@5D@D@=>

@5D@D@D=>

'R8 上的运算举例：

4=>D=><=>

4=>;=><=> =@5D@D>;=  @5D><@,D@/D@D

=@,D@/D@D>=@8D@D><@5D@D@D

4=>4<=>

@<=>是 '8 的生成元

@<=>@<=>@5<=>@8<=>

@/<=>@,<=>@3<=>@<=>

@<=>@<=>@<=>@<=>

@5<=>@8<=>@/<=>

模多项式的确定。*+, 的两条标准如下：

1.如果在 ' 上有  次三项本原多项式 @D@BD，则模多项式应在这些多项式中选取 B

最小的那个。

2.若不存在那样的多项式，则 %=@>应为  次 / 项本原多项式 @D@B5D@BD@BD。

这时有三条原则：=>B5 应尽量小。=>B5 确定时 B 应尽量小。=5>B5EB 确定时，B 应

尽量小。

正规基（略）

4、有限域上的椭圆曲线

本节我们将给出椭圆曲线的简要介绍，更详细的内容请参见其他书目。

4.1Fp 上的椭圆曲线

剩余26页未读，继续阅读

张盛锋

2023-07-25

阅读这份中文版文件，作者的用词简洁明了，不会让人感到晦涩难懂。

评论收藏

内容反馈

孤单旅行

粉丝: 20

椭圆曲线数字签名算法（ECDSA）中文版

评论5

最新资源

椭圆曲线数字签名算法（ECDSA）中文版

评论5

椭圆曲线数字签名算法ECDSA.pdf

椭圆曲线数字签名算法

椭圆曲线数字签名算法(ECDSA)

椭圆曲线数字签名算法（ECDSA）英文版

ECDSA签名【利用ECDSA签名算法实现密码加密】

ECDSA算法实现源码

ECDSA快速验签算法

ECC和ECDSA算法

RSA.计算工具计算工具

椭圆曲线数字签名认证程序

椭圆曲线算法

ECDSA.rar_ECDSA_数字签名_椭圆曲线签名

Go椭圆曲线数字签名、验证

The Elliptic Curve Digital Signature Algorithm (ECDSA).pdf

数字签名程序

数字签名工具

rsa数字签名

操作系统之安全算法：Digital Signatures：椭圆曲线数字签名算法ECDSA.docx

基于哈希证明系统的区块链两方椭圆曲线数字签名算法研究.docx

ECDSA椭圆曲线加密算法

椭圆曲线加密和签名算法.pptx

ecdsa.rar_ECDSA_java ecdsa_椭圆曲线_椭圆曲线签名

一种基于椭圆曲线的数字签名与盲签名方案 (2012年)

multi-party-ecdsa：{t，n}阈值ECDSA的Rust实现（椭圆曲线数字签名算法）

介绍ECDSA的入门级资料，通俗易懂

ecdsa-0.10.tar.gz

Assert工具(断言)的使用

Python标准库深度解析

最新资源