Digital Signatures

**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.

Sign Messages and Verify Signatures: How It Works?

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 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.

`Sha256RSA`

for its digital certificate. Nevertheless, the trend in the last decade is to move from RSA and DSA to 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).

`secp256k1`

), 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**.

`Sha256ECDSA`

signature scheme.EdDSA (Edwards-curve Digital Signature Algorithm)

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:

Text

EdDSA-Ed25519

ECDSA-secp256k1

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**.

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.

Last modified 8d ago