Elliptic Curve Digital Signature Algorithm

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. 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 . 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: Calculate . (Here HASH is a cryptographic hash function, such as SHA-2, with the output converted to an integer.) Let be the leftmost bits of , where is the bit length of the group order . (Note that can be greater than but not longer.) Select a cryptographically secure random integer from . Calculate the curve point . Calculate . If , go back to step 3. Calculate . If , go back to step 3. The signature is the pair . (And is also a valid signature.) As the standard notes, it is not only required for to be secret, but it is also crucial to select different for different signatures.