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

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

5星 · 超过95%的资源需积分: 32 12 浏览量更新于2023-03-03 评论 1 收藏 602KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

The Elliptic Curve Digital

Signature Algorithm (ECDSA)

Don Johnson



and Alfred Menezes

 

and Scott Vanstone

 



Certicom Research, Canada



Dept. of Combinatorics & Optimization, University of Waterloo, Canada

Emails:



djohnson, amenezes, svanstone



@certicom.com

Abstract

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve

analogue of the Digital Signature Algorithm (DSA). It was accepted in 1999

as an ANSI standard, and was accepted in 2000 as IEEE and NIST

standards. It was also accepted in 1998 as an ISO standard, and is under

consideration for inclusion in some other ISO standards. Unlike the

ordinary discrete logarithm problem and the integer factorization problem,

no subexponential-time algorithm is known for the elliptic curve discrete

logarithm problem. For this reason, the strength-per-key-bit is substantially

greater in an algorithm that uses elliptic curves. This paper describes the

ANSI X9.62 ECDSA, and discusses related security, implementation, and

interoperability issues.

1 Introduction

The Digital Signature Algorithm (DSA) was speciﬁed in a U.S. Government Federal

Information Processing Standard (FIPS) called the Digital Signature Standard (DSS

[70]). Its security is based on the computational intractability of the discrete logarithm

problem (DLP) in prime-order subgroups of





Elliptic curve cryptosystems (ECC) were invented by Neal Koblitz [49] and Victor

Miller [67] in 1985. They can be viewed as elliptic curve analogues of the older

discrete logarithm (DL) cryptosystems in which the subgroup of







is replaced by

the group of points on an elliptic curve over a ﬁnite ﬁeld. The mathematical basis for

the security of elliptic curve cryptosystems is the computational intractability of the

elliptic curve discrete logarithm problem (ECDLP).

Since the ECDLP appears to be signiﬁcantly harder than the DLP, the strength-per-

key-bit is substantially greater in elliptic curve systems than in conventional discrete

logarithm systems. Thus, smaller parameters can be used in ECC than with DL sys-

tems but with equivalent levels of security. The advantages that can be gained from

smaller parameters include speed (faster computations) and smaller keys and certiﬁ-

cates. These advantages are especially important in environments where processing

power, storage space, bandwidth, or power consumption is constrained.

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue

of the DSA. ECDSA was ﬁrst proposed in 1992 by Scott Vanstone [108] in response

to NIST’s (National Institute of Standards and Technology) request for public com-

ments on their ﬁrst proposal for DSS. It was accepted in 1998 as an ISO (Inter-

national Standards Organization) standard (ISO 14888-3), accepted in 1999 as an

ANSI (American National Standards Institute) standard (ANSI X9.62), and accepted

in 2000 as an IEEE (Institute of Electrical and Electronics Engineers) standard (IEEE

1363-2000) and a FIPS standard (FIPS 186-2). It is also under consideration for in-

clusion in some other ISO standards. In this paper, we describe the ANSI X9.62

ECDSA, present rationale for some of the design decisions, and discuss related se-

curity, implementation, and interoperability issues.

The remainder of this paper is organized as follows. In



2, we review digital sig-

nature schemes and the DSA. A brief tutorial on ﬁnite ﬁelds and elliptic curves is

provided in



3 and



4, respectively. In



5, methods for domain parameter generation

and validation are considered, while



6 discusses methods for key pair generation

and public key validation. The ECDSA signature and veriﬁcation algorithms are pre-

sented in



7. The security of ECDSA is studied in



8. Finally, some implementation

and interoperability issues are considered in



9 and



10.



2 Digital Signature Schemes

2.1 Background

Digital signature schemes are designed to provide the digital counterpart to hand-

written signatures (and more). A digital signature is a number dependent on some

secret known only to the signer (the signer’s private key), and, additionally, on the

contents of the message being signed. Signatures must be veriﬁable — if a dispute

arises as to whether an entity signed a document, an unbiased third party should be

able to resolve the matter equitably, without requiring access to the signer’s private

key. Disputes may arise when a signer tries to repudiate a signature it did create, or

when a forger makes a fraudulent claim.

This paper is concerned with asymmetric digital signatures schemes with appendix.

“Asymmetric” means that each entity selects a key pair consisting of a private key

and a related public key. The entity maintains the secrecy of the private key which it

uses for signing messages, and makes authentic copies of its public key available to

other entities which use it to verify signatures. “Appendix” means that a cryptographic

hash function is used to create a message digest of the message, and the signing

transformation is applied to the message digest rather than to the message itself.

SECURITY. Ideally, a digital signature scheme should be existentially unforgeable un-

der chosen-message attack. This notion of security was introduced by Goldwasser,

Micali and Rivest [33]. Informally, it asserts that an adversary who is able to obtain

entity



’s signatures for any messages of its choice is unable to successfully forge



’s signature on a single other message.

APPLICATIONS. Digital signature schemes can be used to provide the following ba-

sic cryptographic services: data integrity (the assurance that data has not been al-

tered by unauthorized or unknown means), data origin authentication (the assur-

ance that the source of data is as claimed), and non-repudiation (the assurance that

an entity cannot deny previous actions or commitments). Digital signature schemes

are commonly used as primitives in cryptographic protocols that provide other ser-

vices including entity authentication (e.g., FIPS 196 [72], ISO/IEC 9798-3 [40], and

Blake-Wilson and Menezes [10]), authenticated key transport (e.g., Blake-Wilson

and Menezes [10], ANSI X9.63 [4], and ISO/IEC 11770-3 [41]), and authenticated

key agreement (e.g., ISO/IEC 11770-3 [41], Difﬁe, van Oorschot and Wiener [21],

and Bellare, Canetti and Krawczyk [8]).

CLASSIFICATION. The digital signature schemes in use today can be classiﬁed ac-

cording to the hard underlying mathematical problem which provides the basis for

their security:



1. Integer Factorization (IF) schemes, which base their security on the intractability

of the integer factorization problem. Examples of these include the RSA [85] and

Rabin [84] signature schemes.

2. Discrete Logarithm (DL) schemes, which base their security on the intractability

of the (ordinary) discrete logarithm problem in a ﬁnite ﬁeld. Examples of these

include the ElGamal [23], Schnorr [90], DSA [70], and Nyberg-Rueppel [78, 79]

signature schemes.

3. Elliptic Curve (EC) schemes, which base their security on the intractability of the

elliptic curve discrete logarithm problem.

2.2 The Digital Signature Algorithm (DSA)

The DSA was proposed in August 1991 by the U.S. National Institute of Standards

and Technology (NIST) and was speciﬁed in a U.S. Government Federal Information

Processing Standard (FIPS 186 [70]) called the Digital Signature Standard (DSS).

The DSA can be viewed as a variant of the ElGamal signature scheme [23]. Its

security is based on the intractability of the discrete logarithm problem in prime-order

subgroups of







DSA DOMAIN PARAMETER GENERATION. Domain parameters are generated for each

entity in a particular security domain. (See also the note below on secure generation

of parameters.)

1. Select a 160-bit prime



and a 1024-bit prime



with the property that



2. (Select a generator



of the unique cyclic group of order









Select an element







and compute

 

"!

$#&%('*)+-,



. (Repeat until

/.0

3. Domain parameters are





and



DSA KEY PAIR GENERATION. Each entity



in the domain with domain parameters

32452(-6

does the following:

1. Select a random or pseudorandom integer

such that

98:7;8:<:

2. Compute

=>@?

)+5,





’s public key is

;



’s private key is

DSA SIGNATURE GENERATION. To sign a message



does the following:

1. Select a random or pseudorandom integer

C8>BD8:<:

2. Compute

EF>5G

)+-,



and

H9IE

)+-,



. If

HJIK

then go to step 1.

3. Compute

L)+5,



4. Compute

MN

SHA-1

A;6

5. Compute

ONB





M*PQ7RH5

)+-,



. If

O<IK

then go to step 1.



’s signature for the message

HS2TO"6

DSA SIGNATURE VERIFICATION To verify



’s signature

HV2TOV6

obtains authen-

tic copies of



’s domain parameters

32452(-6

and public key

and does the following:

1. Verify that

and

are integers in the interval

XY"249:Z

2. Compute

MN

SHA-1

A;6

3. Compute

[O



)+-,



4. Compute



M][

)+-,



and



^H"[

)+-,



5. Compute

EF>@_a`=@_Sb

)+-,



and

c^E

)+-,



6. Accept the signature if and only if

c^H

SECURITY ANALYSIS. Since

and

are each integers less than



, DSA signatures

are 320 bits in size. The security of the DSA relies on two distinct but related discrete

logarithm problems. One is the discrete logarithm problem in





where the number

ﬁeld sieve algorithm (see Gordon [35] and Schirokauer [89]) applies; this algorithm

has a subexponential running time. More precisely, the expected running time of the

algorithm is

dfehgji-kle

1nm

Ppo

q66

1nrts

u6

$%(v

1nrtswrts

 6

4%(vhxux

q6

where

mzy

"{}|a~a

, and

r&s*

denotes the natural logarithm function. If



is a 1024-

bit prime, then the expression (1) represents an infeasible amount of computation;

thus the DSA using a 1024-bit prime



is currently not vulnerable to this attack. The

second discrete logarithm problem works to the base



in the subgroup of order









: given







, and

, ﬁnd

such that

=>@?

)+5,

 6

. For large



(e.g., 1024-bits),

the best algorithm known for this problem is Pollard’s rho method [83], and takes

about

 

"~

~6

steps. If





, then the expression (2) represents an infeasible amount of compu-

tation; thus the DSA is not vulnerable to this attack. However, note that there are two

primary security parameters for DSA, the size of



and the size of



. Increasing one

without a corresponding increase in the other will not result in an effective increase

in security. Furthermore, an advance in algorithms for either one of the two discrete

logarithm problems could weaken DSA.

SECURE GENERATION OF PARAMETERS. In response to some criticisms received

on the ﬁrst draft (see Rueppel et al. [86] and Smid and Branstad [99]), FIPS 186

speciﬁed a method for generating primes



and



“veriﬁably at random”. This fea-

ture prevents an entity (e.g., a central authority generating domain parameters to be

shared by a network of entities) from intentionally constructing “weak” primes



and



for which the discrete logarithm problem is relatively easy. For further discussion

of this issue, see Gordon [34]. FIPS 186 also speciﬁes two methods, based on DES



剩余55页未读，继续阅读

albert1905

2012-08-23

网上找了很多资料（包括wikipedia）都只是范范而谈，这个包含非常详细的数学细节~~ 三位作者中的两位是《应用密码学手册》(handbook of Applied Cryptography)的作者~~

孤单旅行

粉丝: 20
资源: 7

会员权益专享

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

评论1

会员权益专享

最新资源

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

评论1

ECDSA椭圆曲线加密算法

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

secp256k1-native:secp256k1的本机绑定

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

椭圆曲线数字签名算法：ECDSA

椭圆曲线数字签名算法

椭圆曲线加密算法ECDSA原理解析

VECDSigL：使用椭圆曲线数字签名链接的视频完整性验证

数字签名中的椭圆曲线密码学（ECC）算法解析

椭圆曲线数字签名算法(ECDSA)的 java实现公钥签名私钥验签

基于椭圆曲线的密码算法有哪些

椭圆曲线加密与签名算法在区块链中的应用

全世界公认的某个椭圆曲线算法的基点

RSA签名算法与ECDSA签名算法性能对比

C语言实现ECDSA，其中椭圆曲线使用ED25519

ECDSA签名算法 代码实现 matlab

ECDSA算法是国米算法吗

基于椭圆曲线加密算法的门限签名协议是什么

c++ 简单的实现椭圆曲线加密算法

bouncycastle ecdsa-secp256r1

会员权益专享

最新资源

ECDSA签名算法代码实现 matlab