In
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the
Digital Signature Algorithm
The Digital Signature Algorithm (DSA) is a Public-key cryptography, public-key cryptosystem and Federal Information Processing Standards, Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular e ...
(DSA) which uses
elliptic-curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys to provide equivalent security, compared to cryptosystems based on modula ...
.
Key and signature sizes
As with elliptic-curve cryptography in general, the bit
size
Size in general is the Magnitude (mathematics), magnitude or dimensions of a thing. More specifically, ''geometrical size'' (or ''spatial size'') can refer to three geometrical measures: length, area, or volume. Length can be generalized ...
of the
private key believed to be needed for ECDSA is about twice the size of the
security level
In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of " bits of security" (also security strength ...
, in bits. For example, at a security level of 80 bits—meaning an attacker requires a maximum of about
operations to find the private key—the size of an ECDSA private key would be 160 bits. On the other hand, the signature size is the same for both DSA and ECDSA: approximately
bits, where
is the exponent in the formula
, that is, about 320 bits for a security level of 80 bits, which is equivalent to
operations.
Signature generation algorithm
Suppose
Alice
Alice may refer to:
* Alice (name), most often a feminine given name, but also used as a surname
Literature
* Alice (''Alice's Adventures in Wonderland''), a character in books by Lewis Carroll
* ''Alice'' series, children's and teen books by ...
wants to send a signed message to
Bob. Initially, they must agree on the curve parameters
. In addition to the
field and equation of the curve, we need
, a base point of prime order on the curve;
is the additive order of the point
.
The order
of the base point
must be prime. Indeed, we assume that every nonzero element of the
ring
(The) Ring(s) may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
Arts, entertainment, and media Film and TV
* ''The Ring'' (franchise), a ...
is invertible, so that
must be a
field. It implies that
must be prime (cf.
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout who proved it for polynomials, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called B� ...
).
Alice creates a key pair, consisting of a private key integer
, randomly selected in the interval