ECDSA - Sign and Verification

Last updated on Jul 13, 2023 7 min read

In this blog, I have explained the workings of ECDSA sign and verification. To understand this, we first require the knowledge about basic concept of cryptography. If you know the concept, then you can jump to ECDSA explanation.

Disclaimer: The information provided in this blog post about the working of ECDSA signing and verification is explained to the best of my knowledge and is the result of thorough research from various reliable sources.

What is Cryptography?

In simple term, it’s techniques to secure the data or to do secure communication. You may check the basics here

Let’s talk about various types of Cryptography:

Symmetric Key Cryptography

It is also known as the Single Key Cryptography. It refers to the encryption method where only a single key is used for both encryption and decryption. The sender and receiver share this key using any reasonably secure and reliable method before starting the communication.

Asymmetric Key Cryptography

It is also known as the Public-key Cryptography where there are 2 keys involved. The mathematical properties of the keys are such that the data encrypted with one key can ONLY BE decrypted by the other key.

Public Key:
- As the name indicates, this key is meant to be made public, often through Digital Certificates issued by an Issuer who is trusted by all parties in the context of its use.
Private Key:
- This key is intended to be managed securely by one entity. Often, the entity that owns this key also generates it, to ensure nobody else has ever had any access to it.

Asymmetric Keys are used for two types of operations:

Encryption and Decryption

A Sender will use the Receiver’s Public key to encrypt and securely send data to the receiver – so that ONLY the Receiver can decrypt it using their Private Key.

Signing and Verification

When any document (or data) is encrypted using a Private Key, anyone with the corresponding public key can decrypt data encrypted with this key, so this is used not to ensure secrecy. Usually, a hash of the data is first generated which is then encrypted and attached to the document. This process is called digitally signing the document.

The primary purpose is to assure the receiver(s) that

The document could only have originated from whoever has access to the Private Key. This property is often referred to as non-repudiation.
The document was not altered during the transmission thus assuring the integrity of content.
In this operation, the encryption and decryption processes are still in the picture, but the process is different.

Note: Now we understand the basics of cryptography and its types and the operation that is possible in types of cryptography. As the attack that we are discussed during this blog is based on signing and verification operation, let’s deep dive into this.

What is ECDSA?

The following are the commonly used algorithms used with the Public-Key Cryptography:
- RSA
- DSA
- ECDSA (modified version of DSA)
  - This is a combination of ECC + DSA.
  - Means, Digital Signature Algorithm (DSA) based on the Elliptic Curve Cryptography (ECC).
Comparison of RSA and Elliptic Curve Cryptography:
- To get the same level of protection, ECC requires a key with a smaller size than RSA, so it’s faster than RSA.
- ECC (256-bit key size) = RSA (3072-bit key size).
- ECC (384-bit key size) = RSA (7680-bit key size).
- ECC (512-bit key size) = RSA (15360-bit key size).

What is an Elliptic Curve?

Despite the similarity in the name, this curve is not the same as an ellipse.
Elliptic curves with real coefficients (i.e., points x and y that can be plotted on real axes) can be expressed as,
- y² = x³ + ax + b
- Where, a and b are constant values.
To understand the Elliptic Curve Cryptography, first we must understand how the Elliptic Curve is created and then we will see how we can use the cryptography in it.
To create the Elliptic Curve, first we need to define the following:
- Equation
- p (finite field which can be any number)
Based on the equation, it will identify the multiple (x, y) points on the curve which satisfied equation and by joining all the points the elliptic curve is created
- Equation example,
  - y² = x³ + ax + b mod p
  - a = 0
  - b = 7
  - Where, a and b are constants which have values 0 and 7 respectively. For better understanding, let me replace a = 0 and b = 7
- Finite field, p = 17
- Now, let’s check the co-ordinate (15, 13) lie on a curve or not
  - (15, 13) so x=15 and y = 13
  - y² mod p = x³ +0x + 7 mod p
  - (13x13) mod p = ((15x15x15) + 0x15 + 7) mod p
  - 169 % 17 = (3375 + 0 + 7) % 17
  - 169 % 17 = 3382 % 17
  - 16 = 16, that means yes (15, 13) is on the selected curve
- This is how for the different values of x and y, it will identify multiple points which lies on curve and by joining all the points, it will draw a curve which satisfies the equation, as shown in figure:
  - References: https://www.desmos.com/calculator/ialhd71we3

Following are some popular Elliptic Curves which used in real world
- Bitcoin curve: https://neuromancer.sk/std/secg
- https://neuromancer.sk/std/nist

Now, once the Elliptic curve was created on the graph and when we perform signing and verification based on this, then this is called as an Elliptic Curve Cryptography. So, let’s first understand the terminologies and variable naming convention used in it and then we will deep dive into the cryptography part.

Variables Naming Convention in ECC

Equation: y² = x³ + ax + b mod p
a and b are constant values
- which remain constant, irrespective of values of x and y supplied to the equation
p = finite field (can choose any number)
G = Base point (X, Y), from where we start identifying other point on the curve
n = integer order of G, more details
k = Nonce (Random Number)
Private Key = (Long Integer Value)
Public Key = (Private Key * G) (Results will be some point (X, Y) on elliptic curve)
r = x co-ordinate of the point (k * G)
R = k * G, where R is temporary variable to store intermediate equation output
r = R.x (It’s x co-ordinate of R)
M = Message to sign
- It’s plaintext value for which we want to generate the signature
H(M) = Hash of the Message,
- Ex. SHA256 Hash of the plaintext value
- SHA256(Plaintext) = H(M)

Indentify “n” = integer order of G

Let us understand this by using y² = x³ + ax + b mod p, where,
- a = 0, b = 7
- p = 17
- G = (15,13)
G = Base point (X, Y). We have chosen that as (15, 13)
- The selected base point needs to lie on the curve, means it must satisfy the equation.
  - y² = x³ + ax + b mod p

from tinyec.ec import SubGroup, Curve 

field = SubGroup(p=17, g=(15, 13), n=18, h=1) 
curve = Curve(a=0, b=7, field=field, name='NonceReuseDemo') 
print('curve:', curve) 

for index in range(0, 25): 
    p = index * curve.g 
    print(f"{index} * G = ({p.x}, {p.y})")

n = integer order of G
- For the equation and p value that we have selected, the points get repeated after 18 occurrences in above snapshot,
- So, we can say that n=18 for the equation y2 = x3 + 0x + 7 mod p, where p=17

Signing in ECDSA

In ECDSA, signature = (r, s)
- So, it consists of 2 part, r and s
- Where, r = R.x (x co-ordinates of R), please check Variables Naming Convention in ECC for more details
- And to calculate the “s” part, the following mathematical equation is used
- s = k^-1 * (H(M) + r * PrivateKey) (mod n)

Signature verification in ECDSA

To perform the verification, It will first extract the “r” and “s” from signature
- As a user we have following information
  - Plaintext data
  - Signature generated for plaintext data which is a combination of “r” and “s”
Again, to verify also it perform following mathematical operation
- s1 = s^-1 (mod n)
- R = (H(M) * s1) * G + (r*s1) * Public key
  - Where, R is temporary variable to store the intermediate output
- r’ = R.x (x co-ordinates of R)
- IF r’ == r
  - Signature is valid
- ELSE
  - Signature is invalid