Elliptic Curve DSA
Encyclopedia
The Elliptic Curve Digital Signature Algorithm (ECDSA) is a variant of the Digital Signature Algorithm
(DSA) which uses Elliptic curve cryptography
.
in general, the bit size of the public key believed to be needed for ECDSA is about twice the size of the security level, in bits. By comparison, at a security level of 80 bits, meaning an attacker requires the equivalent of about
signature generations to find the private key, the size of a DSA public key is at least 1024 bits, whereas the size of an ECDSA public key would be 160 bits. On the other hand, the signature size is the same for both DSA and ECDSA: 
bits, where 
is the security level measured in bits, that is, about 320 bits for a security level of 80 bits.
Suppose Alice
wants to send a signed message to Bob
. Initially, the curve parameters
must be agreed upon. 
is the field size; 
is an indication of the basis used; 
and 
are two field elements that define the equation of the curve; 
is an optional bit string that is present if the elliptic curve was randomly generated in a verifiable fashion;
is a base point of prime order on the curve (i.e., 
); 
is the order of the point 
; and 
is the cofactor (which is equal to the order of the curve divided by 
).
Also, Alice must have a key pair suitable for elliptic curve cryptography, consisting of a private key
(a randomly selected integer in the interval 
) and a public key 
(where 
). Let 
be the bit length of the group order 
.
For Alice to sign a message
, she follows these steps:
When computing
, the string 
resulting from 
shall be converted to an integer. Note that 
can be greater than 
but not longer.
It is crucial to select different
for different signatures, otherwise the equation in step 4 can be solved for 
, the private key: Given two signatures 
and 
, employing the same unknown 
for different known messages 
and 
, an attacker can calculate 
and 
, and since 
(all operations in this paragraph are done modulo 
) the attacker can find 
. Since 
, the attacker can now calculate the private key 
. This cryptographic failure was used, for example, to extract the signing key used in the PlayStation 3
gaming console.
. If he does not trust the source of 
, he needs to validate the key (
here indicates the identity element):
After that, Bob follows these steps:
Note that using Straus's algorithm (also known as Shamir's trick) a sum of two scalar multiplications
can be calculated faster than with two scalar multiplications.
paper demonstrating that it is possible to retrieve a TLS private key of a server using OpenSSL that authenticates with Elliptic Curves DSA and binary curves via a timing attack
.
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...
(DSA) which uses Elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
.
Key and signature size comparison to DSA
As with elliptic curve cryptographyElliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
in general, the bit size of the public key believed to be needed for ECDSA is about twice the size of the security level, in bits. By comparison, at a security level of 80 bits, meaning an attacker requires the equivalent of about
signature generations to find the private key, the size of a DSA public key is at least 1024 bits, whereas the size of an ECDSA public key would be 160 bits. On the other hand, the signature size is the same for both DSA and ECDSA: bits, where is the security level measured in bits, that is, about 320 bits for a security level of 80 bits.Signature generation algorithm
| Parameter | |
|---|---|
| q | field size |
| FR | the basis used |
| a, b | field elements defining the point of the curve |
| DPS | DomainParameterSeed, optional |
| G | base point |
| n | order of G |
| h | cofactor |
Suppose Alice
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
wants to send a signed message to Bob
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
. Initially, the curve parameters
must be agreed upon. is the field size; is an indication of the basis used; and are two field elements that define the equation of the curve; is an optional bit string that is present if the elliptic curve was randomly generated in a verifiable fashion; is a base point of prime order on the curve (i.e., ); is the order of the point ; and is the cofactor (which is equal to the order of the curve divided by ).Also, Alice must have a key pair suitable for elliptic curve cryptography, consisting of a private key
(a randomly selected integer in the interval ) and a public key (where ). Let be the bit length of the group order .For Alice to sign a message
, she follows these steps:- Calculate
, where HASH is a cryptographic hash functionCryptographic hash functionA cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
, such as SHA-1, and let
be the 
leftmost bits of 
. - Select a random integer
from 
. - Calculate
, where 
. If 
, go back to step 2. - Calculate
. If 
, go back to step 2. - The signature is the pair
.
When computing
, the string resulting from shall be converted to an integer. Note that can be greater than but not longer.It is crucial to select different
for different signatures, otherwise the equation in step 4 can be solved for , the private key: Given two signatures and , employing the same unknown for different known messages and , an attacker can calculate and , and since (all operations in this paragraph are done modulo ) the attacker can find . Since , the attacker can now calculate the private key . This cryptographic failure was used, for example, to extract the signing key used in the PlayStation 3PlayStation 3
The is the third home video game console produced by Sony Computer Entertainment and the successor to the PlayStation 2 as part of the PlayStation series. The PlayStation 3 competes with Microsoft's Xbox 360 and Nintendo's Wii as part of the seventh generation of video game consoles...
gaming console.
Signature verification algorithm
For Bob to authenticate Alice's signature, he must have a copy of her public key. If he does not trust the source of , he needs to validate the key ( here indicates the identity element):- Check that
is not equal to 
and its coordinates are otherwise valid - Check that
lies on the curve - Check that
After that, Bob follows these steps:
- Verify that
and 
are integers in 
. If not, the signature is invalid. - Calculate
, where HASH is the same function used in the signature generation. Let 
be the 
leftmost bits of 
. - Calculate
. - Calculate
and 
. - Calculate
. - The signature is valid if
, invalid otherwise.
Note that using Straus's algorithm (also known as Shamir's trick) a sum of two scalar multiplications
can be calculated faster than with two scalar multiplications.Security
On March 29th, 2011, two researchers published a IACRInternational Association for Cryptologic Research
The International Association for Cryptologic Research is a non-profit scientific organization whose purpose is to further research in cryptology and related fields...
paper demonstrating that it is possible to retrieve a TLS private key of a server using OpenSSL that authenticates with Elliptic Curves DSA and binary curves via a timing attack
Timing attack
In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms...
.