Digital Signatures, ECDSA and EdDSA

Digital signatures are a cryptographic tool to sign messages and verify message signatures in order to provide proof of authenticity for digital messages or electronic documents. Digital signatures provide:

• Message authentication - a proof that certain known sender (secret key owner) have created and signed the message.
• Мessage integrity - a proof that the message was not altered after the signing.
• Non-repudiation - the signer cannot deny the signing of the document after the signature is once created.

Digital signatures are widely used today in the business and in the financial industry, e.g. for authorizing bank payments (money transfer), for exchange of signed electronic documents, for signing transactions in the public blockchain systems (e.g. transfer of coins, tokens or other digital assets), for signing digital contracts and in many other scenarios.

Digital signatures cannot identify who is the person, created a certain signature. This can be solved in combination with a digital certificate, which binds a public key owner with identity (person, organization, web site or other). By design digital signatures bind messages to public keys, not to digital identities.

Sign Messages and Verify Signatures: How It Works?

Digital signature schemes typically use a public-key cryptosystem (such as RSA or ECC) and use a public / private key pairs. A message is signed by a private key and the signature is verified by the corresponding public key:

Messages are signed by the sender using a private key (signing key). Typically the input message is hashed and then the signature is calculated by the signing algorithm. Most signature algorithms perform some calculation with the message hash + the signing key in a way that the result cannot be calculated without the signing key. The result from message signing is the digital signature (one or more integers):

signMsg(msg, privKey) 🡒 signature

Message signatures are verified by the corresponding public key (verification key). Typically the signed message is hashed and some calculation is performed by the signature algorithm using the message hash + the public key. The result from signing is a boolean value (valid or invalid signature):

verifyMsgSignature(msg, signature, pubKey) 🡒 valid / invalid

A message signature mathematically guarantees that certain message was signed by certain (secret) private key, which corresponds to certain (non-secret) public key. After a message is signed, the message and the signature cannot be modified and thus message authentication and integrity is guaranteed. Anyone, who knows the public key of the message signer, can verify the signature. Аfter signing the signature author cannot reject the act of signing (this is known as non-repudiation).

Most signature schemes work like it is shown at the following diagram:
At signing, the input message is hashed (either alone, or together with the public key and other input parameters), then some computation (based on elliptic curves, discrete logarithms or other cryptographic primitive) calculates the digital signature. The produced signed message consists of the original message + the calculated signature.

At signature verification, the message for verification is hashed (either alone or together with the public key) and some computations are performed between the message hash, the digital signature and the public key, and finally a comparison decides whether the signature is valid or not.

Digital signatures are different from MAC (message authentication codes), because MACs are created and verified by the same secret key using a symmetric algorithm, while digital signatures are created by a signing key and are verified by a different verification key, corresponding to the signing key using an asymmetric algorithm. Both signatures and MAC codes provide message authentication and integrity.

Digital Signature Schemes and Algorithms

Most public-key cryptosystems like RSA and ECC provide secure digital signature schemes (signature algorithms). Examples of well known digital signature schemes are: DSA, ECDSA, EdDSA, RSA signatures, ElGamal signatures and Schnorr signatures.

The above mentioned signature schemes are based on the difficulty of the DLP (discrete logarithm problem) and ECDLP (elliptic-curve discrete logarithm problem) and are quantum-breakable (powerful enough quantum computers may calculate the signing key from the message signature). Quantum-safe signatures (like SPHINCS, BLISS and XMSS) are not massively used, because of long key length, long signatures and slower performance, compared to ECDSA and EdDSA.

The most popular digital signature schemes (as of Nov 2018) are: RSA signatures, ECDSA and EdDSA. Let's give some details about them, along with some live code examples.

RSA Signatures

The RSA public-key cryptosystem provides a cryptographically secure digital signature scheme (sign + verify), based on the math of the modular exponentiations and discrete logarithms and the difficulty of the integer factorization problem (IFP). The RSA sign / verify process works as follows:

• The RSA sign algorithm computes a message hash, then encrypts the hash with the private key exponent to obtain the signature. The obtained signature is an integer number (the RSA encrypted message hash).
• The RSA verify algorithm first computes the message hash, then decrypts the message signature with the public key exponent and compares the obtained decrypted hash with the hash of the signed message to ensure the signature is valid.

RSA signatures are deterministic (the same message + same private key produce the same signature). A non-deterministic variant of RSA-signatures is easy to be designed by padding the input message with some random bytes before signing.

RSA signatures are widely used in modern cryptography, e.g. for signing digital certificates to protect Web sites. For example (as of Nov 2018) the Microsoft's official Web site uses Sha256RSA for its digital certificate. Nevertheless, the trend in the last decade is to move from RSA and DSA to elliptic curve-based signatures (like ECDSA and EdDSA). Modern cryptographers and developers prefer ECC signatures for their shorter key length, shorter signature, higher security (for the same key length) and better performance.

DSA (Digital Signature Algorithm)

The DSA (Digital Signature Algorithm) is a cryptographically secure standard for digital signatures (signing messages and signature verification), based on the math of the modular exponentiations and discrete logarithms and the difficulty of the discrete logarithm problem (DLP). It is alternative of RSA and is used instead of RSA, because of patents limitations with RSA (until Sept 2000). DSA is variant of the ElGamal signature scheme. The DSA sign / verify process works as follows:

• The DSA signing algorithm computes a message hash, then generates a random integer k and computes the signature (а pair of integers {r, s}), where r is computed from k and s is computed using the message hash + the private key exponent + the random number k. Due to randomness, the signature is non-deterministic.
• The DSA signature verification algorithm involves computations, based on the message hash + the public key exponent + the signature {r, s}.

The random value k (generated when the signature is computed) opens a potential vulnerability: if two different messages are signed using the same value of k and the same private key, then an attacker can compute the signer's private key directly (see https://github.com/tintinweb/ecdsa-private-key-recovery).

A deterministic-DSA variant is defined in RFC 6979, which calculates the random number k as HMAC from the private key, the message hash and few other parameters. The deterministic DSA is considered more secure.

In the modern cryptography, the elliptic-curve-based signatures (liike ECDSA and EdDSA) are prefered to DSA, because of shorter key lengths, shorter signature lengths, higher security levels (for the same key length) and better performance.

ECDSA (Elliptic Curve Digital Signature Algorithm)

The ECDSA (Elliptic Curve Digital Signature Algorithm) is a cryptographically secure digital signature scheme, based on the elliptic-curve cryptography (ECC). ECDSA relies on the math of the cyclic groups of elliptic curves over finite fields and on the difficulty of the ECDLP problem (elliptic-curve discrete logarithm problem).

ECDSA is adaptation of the classical DSA algorithm, which is derived from the ElGamal signature scheme. More precisely, the ECDSA algorithm is a variant of the ElGamal signature, with some changes and optimizations to handle the representation of the group elements (the points of the elliptic curve). Like any other elliptic curve crypto algorithm, ECDSA uses an elliptic curve (like the secp256k1), private key (random integer within the curve key length - for signing messages) and public key (EC point, calculated from the private key by multiplying it to the curve generator point - for verifying signatures). The ECDSA sign / verify process works as follows:

• The ECDSA signing algorithm computes a message hash, then generates a random integer k and computes the signature (a pair of integers {r, s}), where r is computed from k and s is computed using the message hash + the private key + the random number k. Due to the randomness, the signature is non-deterministic.
• The ECDSA signature verification algorithm involves computations, based on the message hash + the public key + the signature {r, s}.

The random value k (generated when the signature is computed) opens a potential vulnerability: if two different messages are signed using the same value of k and the same private key, then an attacker can compute the signer's private key directly (see https://github.com/tintinweb/ecdsa-private-key-recovery).

A deterministic-ECDSA variant is defined in RFC 6979, which calculates the random number k as HMAC from the private key + the message hash + few other parameters. The deterministic ECDSA is considered more secure.

ECDSA signatures are the most widely used signing algorithm, used by millions every day (as of Nov 2018). For example, the digital certificates in Amazon Web sites are signed by the Sha256ECDSA signature scheme.

EdDSA (Edwards-curve Digital Signature Algorithm)

EdDSA (Edwards-curve Digital Signature Algorithm) is a fast digital signature algorithm, using elliptic curves in Edwards form (like Ed25519 and Ed448-Goldilocks), a deterministic variant of the Schnorr's signature scheme, designed by a team of the well-known cryptographer Daniel Bernstein.

EdDSA is more simple than ECDSA, more secure than ECDSA and is designed to be faster than ECDSA (for curves with comparables key length). Like ECDSA, the EdDSA signature scheme relies on the difficulty of the ECDLP problem (elliptic-curve discrete logarithm problem) for its security strength.

The EdDSA signature algorithm is works with Edwards elliptic curves like Curve25519 and Curve448, which are highly optimized for performance and security. It is shown that Ed25519 signatures are typically faster than traditional ECDSA signatures over curves with comparable key length. Still, the performance competition is disputable. The EdDSA sign / verify process works as follows:

• The EdDSA signing algorithm generates a deterministic (not random) integer r (computed by hashing the message and the hash of the private key), then computes the signature {Rs, s}, where Rs is computed from r and s is computed from the hash of (the message + the public key derived from the private + the number r) + the private key. The signature is deterministic (the same message signed by the same key always gives the same signature).
• The EdDSA signature verification algorithm involves elliptic-curve computations, based on the message (hashed together with the public key and the EC point Rs from the signature) + the public key + the number s from the signature {Rs, s}.

By design EdDSA signatures are deterministic (which improves their security). A non-deterministic variant of EdDSA-signatures is easy to be designed by padding the input message with some random bytes before signing.

A short comparison between Ed25519 EdDSA signatures and secp256k ECDSA signatures is given below:

Modern developers often use Ed25519 signatures instead of 256-bit curve ECDSA signatures, because EdDSA-Ed25519 signature scheme uses keys, which fit in 32 bytes (64 hex digits), signatures fit in 64 bytes (128 hex digits), signing and verification is faster and the security is considered better.

Public blockchains (like Bitcoin and Ethereum) often use secp2561-based ECDSA signatures, because the signer's public key (and its blockchain address) can be easily recovered from the signature (together with the signed message) by adding just 1 additional bit to the signature.

In the general case, it is considered that EdDSA signatures are recommended to ECDSA, but this is highly disputable and depends on the use case, on the curves involved and many other parameters.

Other Signature Schemes and Algorithms

Most signature algorithms are derived from generic signature schemes like ElGamal signatures and Schnorr signatures.

• RSA signature is derived from the RSA encryption scheme.
• DSA and ECDSA are derived from ElGamal signature scheme.
• EdDSA is derived from the Schnorr signature scheme.

Other signature schemes include:

• ECGDSA: an elliptic-curve digital signature scheme (based on the difficulty of the ECDLP problem), a slightly simplified variant of ECDSA, known as the German version of ECDSA.
• ECKDSA: an elliptic-curve digital signature scheme (based on the difficulty of the ECDLP problem), a complicated variant of ECDSA, known as the Korean version of ECDSA. The ECKDSA signs given message by given EC private key, along with the signer's digital certificate hash. This add identity to the digital signature, in addition to message authentication, integrity and non-repudiation.
• SM2 signature: an elliptic-curve digital signature scheme (based on the difficulty of the ECDLP problem), known as the Chinese digital signature algorithm, developed by the Chinese Academy of Science.
• GOST R 34.10-2001: an elliptic-curve digital signature scheme (based on the difficulty of the ECDLP problem), known as the Russian digital signature algorithm, one of the Russian cryptographic standard algorithms (called GOST algorithms).

After the short review of the most popular digital signature algorithms, let's get into technical details about the RSA sign, ECDSA and EdDSA signature algorithms, with code examples.