Research

Schnorr and ECDSA

The properties and mathematics of elliptic curves are heavily used in both the Schnorr and ECDSA signatures. To create and verify digital signatures in both the Schnorr and ECDSA signature schemes, a public key and a private key are used.

Education Blog 02: Schnorr and ECDSA

Overview

The properties and mathematics of elliptic curves are heavily used in both the Schnorr and ECDSA signatures. As a result, we recommend that the reader first learn the fundamentals of elliptic curves before proceeding.

Elliptic curves digital signatures

To create and verify digital signatures in both the Schnorr and ECDSA signature schemes, a public key and a private key are used.

The private key is a secret value that is known only to the signer. It is used to generate the signature by performing mathematical operations on the message and a random value called the nonce.

The private key is a secret value that only the signer knows. It generates the signature by performing mathematical operations (elliptic curves) on the message and a random one-time use value known as the nonce.
The public key, on the other hand, is a value that anyone can see. It's derived from the private key and used to validate the signature.

When the signer wants to create a signature, they first choose a random nonce and then use it along with their private key to compute an elliptic curve point. The signature is represented by this point. The message and signature are then delivered to the intended recipient. The recipient, or verifier, then computes a second point on the elliptic curve using the signature, the message, and the signer's public key. If this point matches the signer's point, it means the signature is valid and the message has not been tampered with.

It is critical to remember that the private key must be kept secret, as anyone with access to it can use it to generate valid signatures on any message. The public key, on the other hand, is free to distribute because it can only be used to verify signatures, not create them.

Schnorr and ECDSA

Schnorr signatures and ECDSA(Elliptic Curve Digital Signature Algorithm) are two different digital signature schemes that are based on elliptic curve mathematics and are both considered secure. ECDSA is widely used and accepted in the industry, whereas Schnorr signatures are known for their efficiency and versatility.

ECDSA is more widely used and accepted in the industry than Schnorr signatures for a few reasons:

Standardization: ECDSA was proposed by the National Institute of Standards and Technology (NIST) in the early 1990s, and it has been widely adopted as a standard by various organizations and industries. Schnorr signatures, on the other hand, were first proposed in 1991 and have not been widely adopted as a standard.
Compatibility: ECDSA is based on the same mathematical principles as the widely used RSA algorithm, which makes it easy to integrate into existing systems that are based on RSA. Schnorr signatures, on the other hand, use a different mathematical structure, which makes it harder to integrate into existing systems.
Implementation and Support: ECDSA has been around for longer and has been widely used, this resulted in more libraries, tools, and experts that have experience with ECDSA.
Security: While Schnorr signatures are more efficient and versatile than ECDSA, it is widely accepted that ECDSA is secure enough for most use cases.

However, Schnorr signatures are getting more attention in recent years and new standards are being proposed by some organizations like BLS, Taproot, and Tapscript and some new cryptographic schemes like threshold signatures and multisignatures can be implemented more efficiently using Schnorr signatures.

In both Schnorr and ECDSA, the process of generating a public key from a private key involves using a mathematical operation on a point on an elliptic curve, known as the generator point. The private key is used as an input to the operation, and the resulting output is the corresponding public key.

The same method is used in both Schnorr and ECDSA to generate a public key, which is the scalar multiplication of the private key $s$ and the generator point $G$. As a result, $Y = sG$ is the public key.

Schnorr Signature Scheme

Signing(Signature generation):

Given a curve $E = \{(x,y) \in Z_q^2 : y^2 \equiv x^3 + ax + b \mod{q}, 4a^3 + 27b^2 \neq 0 \} \cup \{0\} \;$and a message $m$, a Schnorr signature is generated using secret key $s \in Z_q$ and public key $Y = sG \in E$ as follows:

Compute the challenge $c = H(R, Y, m)$, where $H$ is a cryptographic hash function, such as Sha3, Keccak, etc.
Using the secret key $s$, compute the response $z = k + sc \in Z_q$
Define the signature over $m$ to be $σ = (R, z)$.

Sample a random nonce $k \in Z_q$; compute the commitment $R = kG$

Please keep in mind that the one-time use nonce $k$ must be kept private and known only to the signer.

Validating:

The following steps are taken to validate the integrity of $m$ by an identified signer using the public key $Y$ and the signature $σ = (R, z)$:

Parse $σ = (R, z)$ and then derive $c = H(R, Y, m)$.
Validating success if $R' = R$ otherwise fail.

Compute $R' = zG + (-c)Y$.

If the signature was correctly generated, the validation should succeed as shown by the following steps. $R' = zG + (-c)Y \\ R' = (k+sc)G + (-c)(sG) \\ R' = kG + (sc)G - (sc)G \\ R' = kG \\ R' = R$

ECDSA Signature Scheme

Signing(Signature generation): The ECDSA, for the most part, looks like Schnorr in the signature generation or signing process, except for the calculation of $z$ and the absence of challenge $c$.

Using the secret key $s$, compute the response $z = (k^{-1})(r_x + sH(m)) \in Z_q$, where $H$ is a cryptographic hash function, such as Sha3, Keccak, etc.
Define the signature over $m$ to be $σ = (R, z)$.

Sample a random nonce $k \in Z_q$; compute the commitment $(r_x, r_y) = R = kG$

Please keep in mind that the one-time use nonce $k$ must be kept private and known only to the signer.

Validating:

The following steps are taken to validate the integrity of $m$ by an identified signer using the public key $Y$ and the signature $σ = (R, z)$:

Parse $σ = (R, z)$.
Validating success if $R' = R$ otherwise fail.

Compute $R' = (z^{-1})(r_xG + H(m)Y)$.

If the signature was correctly generated, the validation should succeed as shown by the following steps. $R' = (z^{-1})(r_xG + H(m)Y) \\ R' = ((k^{-1})(r_x + sH(m)))^{-1}(r_xG + H(m)(sG)) \\ R' = (k^{-1})^{-1}(r_x + sH(m))^{-1}(r_x + sH(m))G \\ R' = kG \\ R' = R$

Difference between Schnorr and ECDSA

The main difference, as we can see, is how $z$ is calculated during the signature generation process.

ECDSA calculates $z$ as $z = (k^{-1})(r_x + sH(m))$ , which can be seen or made an analogy as $c = ab$, where $a = k^{-1}$ and $b = r_x + sH(m)$, implying that the difficulty behind the ECDSA signature is determining the unknown values $a$ and $b$ from a known value $c$.

On the other hand, the value $z$ of the Schnorr signature scheme is calculated as $z = k + sc$ where $c = H(R,Y,m)$, which can be seen as $c = a+b$ where $a = k$ and $b = sc$. The difficulty behind Schnorr's signature is also determining the unknown values $a$ and $b$ from a known value $c$. So, in summary, the ECDSA conceals all private information by using multiplication to obfuscate both the nonce $k$ and the private key $s$, whereas Schnorr conceals all private information by using addition to obfuscate them.