In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.
As with elliptic-curve cryptography in general, the bit size of the private key believed to be needed for ECDSA is about twice the size of the security level, in bits. [1] 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.
Suppose Alice 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 multiplicative order of the point .
Parameter | |
---|---|
CURVE | the elliptic curve field and equation used |
G | elliptic curve base point, a point on the curve that generates a subgroup of large prime order n |
n | integer order of G, means that , where is the identity element. |
the private key (randomly selected) | |
the public key (calculated by elliptic curve) | |
m | the message to send |
The order of the base point must be prime. Indeed, we assume that every nonzero element of the ring is invertible, so that must be a field. It implies that must be prime (cf. Bézout's identity).
Alice creates a key pair, consisting of a private key integer , randomly selected in the interval ; and a public key curve point . We use to denote elliptic curve point multiplication by a scalar.
For Alice to sign a message , she follows these steps:
As the standard notes, it is not only required for to be secret, but it is also crucial to select different for different signatures. Otherwise, the equation in step 6 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 implementation failure was used, for example, to extract the signing key used for the PlayStation 3 gaming-console. [3]
Another way ECDSA signature may leak private keys is when is generated by a faulty random number generator. Such a failure in random number generation caused users of Android Bitcoin Wallet to lose their funds in August 2013. [4]
To ensure that is unique for each message, one may bypass random number generation completely and generate deterministic signatures by deriving from both the message and the private key. [5]
For Bob to authenticate Alice's signature, he must have a copy of her public-key curve point . Bob can verify is a valid curve point as follows:
After that, Bob follows these steps:
Note that an efficient implementation would compute inverse only once. Also, using Shamir's trick, a sum of two scalar multiplications can be calculated faster than two scalar multiplications done independently. [6]
It is not immediately obvious why verification even functions correctly. To see why, denote as C the curve point computed in step 5 of verification,
From the definition of the public key as ,
Because elliptic curve scalar multiplication distributes over addition,
Expanding the definition of and from verification step 4,
Collecting the common term ,
Expanding the definition of s from signature step 6,
Since the inverse of an inverse is the original element, and the product of an element's inverse and the element is the identity, we are left with
From the definition of r, this is verification step 6.
This shows only that a correctly signed message will verify correctly; other properties such as incorrectly signed messages failing to verify correctly and resistance to cryptanalytic attacks are required for a secure signature algorithm.
Given a message m and Alice's signature on that message, Bob can (potentially) recover Alice's public key: [7]
Note that an invalid signature, or a signature from a different message, will result in the recovery of an incorrect public key. The recovery algorithm can only be used to check validity of a signature if the signer's public key (or its hash) is known beforehand.
Start with the definition of from recovery step 6,
From the definition from signing step 4,
Because elliptic curve scalar multiplication distributes over addition,
Expanding the definition of and from recovery step 5,
Expanding the definition of s from signature step 6,
Since the product of an element's inverse and the element is the identity, we are left with
The first and second terms cancel each other out,
From the definition of , this is Alice's public key.
This shows that a correctly signed message will recover the correct public key, provided additional information was shared to uniquely calculate curve point from signature value r.
In December 2010, a group calling itself fail0verflow announced the recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. However, this attack only worked because Sony did not properly implement the algorithm, because was static instead of random. As pointed out in the Signature generation algorithm section above, this makes solvable, rendering the entire algorithm useless. [8]
On March 29, 2011, two researchers published an IACR paper [9] demonstrating that it is possible to retrieve a TLS private key of a server using OpenSSL that authenticates with Elliptic Curves DSA over a binary field via a timing attack. [10] The vulnerability was fixed in OpenSSL 1.0.0e. [11]
In August 2013, it was revealed that bugs in some implementations of the Java class SecureRandom sometimes generated collisions in the value. This allowed hackers to recover private keys giving them the same control over bitcoin transactions as legitimate keys' owners had, using the same exploit that was used to reveal the PS3 signing key on some Android app implementations, which use Java and rely on ECDSA to authenticate transactions. [12]
This issue can be prevented by deterministic generation of k, as described by RFC 6979.
Some concerns expressed about ECDSA:
Below is a list of cryptographic libraries that provide support for ECDSA:
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 compared to non-EC cryptography to provide equivalent security.
The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a variant of the Schnorr and ElGamal signature schemes.
The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.
In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity, among the first whose security is based on the intractability of certain discrete logarithm problems. It is efficient and generates short signatures. It was covered by U.S. Patent 4,995,082 which expired in February 2008.
The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.
The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.
KCDSA is a digital signature algorithm created by a team led by the Korea Internet & Security Agency (KISA). It is an ElGamal variant, similar to the Digital Signature Algorithm and GOST R 34.10-94. The standard algorithm is implemented over , but an elliptic curve variant (EC-KCDSA) is also specified.
In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in where is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.
The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985.
In cryptography, implicit certificates are a variant of public key certificate. A subject's public key is reconstructed from the data in an implicit certificate, and is then said to be "implicitly" verified. Tampering with the certificate will result in the reconstructed public key being invalid, in the sense that it is infeasible to find the matching private key value, as would be required to make use of the tampered certificate.
A BLS digital signature—also known as Boneh–Lynn–Shacham (BLS)—is a cryptographic signature scheme which allows a user to verify that a signer is authentic.
In cryptography, subliminal channels are covert channels that can be used to communicate secretly in normal looking communication over an insecure channel. Subliminal channels in digital signature crypto systems were found in 1984 by Gustavus Simmons.
In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.
Elliptic curve scalar multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography (ECC). The literature presents this operation as scalar multiplication, as written in Hessian form of an elliptic curve. A widespread name for this operation is also elliptic curve point multiplication, but this can convey the wrong impression of being a multiplication between two points.
In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.
Network coding has been shown to optimally use bandwidth in a network, maximizing information flow but the scheme is very inherently vulnerable to pollution attacks by malicious nodes in the network. A node injecting garbage can quickly affect many receivers. The pollution of network packets spreads quickly since the output of honest node is corrupted if at least one of the incoming packets is corrupted.
In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves. It is designed to be faster than existing digital signature schemes without sacrificing security. It was developed by a team including Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. The reference implementation is public-domain software.
The Sakai–Kasahara scheme, also known as the Sakai–Kasahara key encryption algorithm (SAKKE), is an identity-based encryption (IBE) system proposed by Ryuichi Sakai and Masao Kasahara in 2003. Alongside the Boneh–Franklin scheme, this is one of a small number of commercially implemented identity-based encryption schemes. It is an application of pairings over elliptic curves and finite fields. A security proof for the algorithm was produced in 2005 by Chen and Cheng. SAKKE is described in Internet Engineering Task Force (IETF) RFC 6508.
In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors key exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a quantum computer. This is important because some public key algorithms in use today will be easily broken by a quantum computer if such computers are implemented. RLWE-KEX is one of a set of post-quantum cryptographic algorithms which are based on the difficulty of solving certain mathematical problems involving lattices. Unlike older lattice based cryptographic algorithms, the RLWE-KEX is provably reducible to a known hard problem in lattices.
{{cite journal}}
: Cite journal requires |journal=
(help){{cite journal}}
: Cite journal requires |journal=
(help)