Elliptic Curve Digital Signature Algorithm - thuật toán chữ ký số đường cong elliptic

A Brief Introduction to ECDSA

It is impossible to overstate how modern cryptography redefines trust for all our digital interactions - from securing bank account logins with encryption to verifying the authenticity of your favorite apps through digital certificates.

Public key cryptography is a key concept empowering these interactions. It consists of two key pairs:

Public key: Widely distributed and used by anyone to verify an entity's identity. Private key: Confidential and known only to the owner, used for encryption and signing messages.

Elliptic curve cryptography (ECC) is a specific type of public key cryptography that uses mathematics of elliptic curves to create smaller, and more efficient keys. This is especially beneficial in resource-constrained environments like Ethereum. Within Ethereum, the Elliptic Curve Digital Signature Algorithm (ECDSA) helps verify the legitimacy of submitted transactions.

Let's consider a real-world scenario to understand how ECDSA works in action.

Alice, a diligent businesswoman, has been abducted and held captive on a remote island. Her captors demand a hefty ransom of $1 million for her release. With limited options for communication, they provide a single postcard for her to instruct her associate, Bob, to transfer the funds.

Alice considers writing the ransom amount and signing the postcard like a check. However, this method poses a significant risk: the kidnappers could easily forge the postcard, inflate the amount, and deceive Bob into sending them more money.

Alice needs a robust approach that allows:

Bob to verify that the transfer has be authorized by her, and
ensure that postcard's message has not been tampered with.

The goal of this exercise is device a method for Alice to create a secret key 🔑 known only to her. This key will be crucial for her to prove her identity and ensure the message's authenticity to Bob.

Mathematics, as always, comes to the rescue. Through ingenious use of Elliptic Curves, let's explore how Alice can generate the secret key 🔑.

Elliptic curves

An elliptic curve is a curve described by the equation:

y^2 = x^3 + ax+b

Such that $4a^3 + 27b^2 \ne 0$ to ensure the curve is non-singular. The equation above is what is called the Weierstrass normal form of the long equation:

y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6

Examples:

Observe that elliptic curves are symmetric about the x-axis.

Ethereum uses a standard curve known as secp256k1 with parameters $a=0$ , and $b=7$ ; which is the curve: $y^2=x^3+7$

Groups and Fields

Group

In mathematics, a GROUP is a set $G$ , containing at least two elements, which is closed under a binary operation usually referred to as addition ( $+$ ). A set is closed under an operation when the result of the operation is also a member of the set.

The set of real numbers $\mathbb{R}$ is a familiar example of a group, since arithmetic addition of two real numbers is closed.

3 \in \mathbb{R}, 5 \in \mathbb{R} \\ 3 + 5 = 8 \in \mathbb{R}

Field

Similarly, a FIELD is a set $F$ , containing at least two elements, which is closed under two binary operations usually referred to as addition ( $+$ ), and multiplication( $\times$ ).

In other words, A FIELD is a GROUP under both addition and multiplication.

Elliptic curves are interesting because the points on the curve form a group, i.e the result of "addition" of two points remains on the curve. This geometric addition, distinct from arithmetic counterparts, involves drawing a line through chosen points (P and Q) and reflecting the resulting curve intersection(R') across the x-axis to yield their sum (R).

A point (P) can also be added to itself ( $P+P$ ), in which case the straight line becomes a tangent to P that reflects the sum (2P).

Repeated point-addition is known as scalar multiplication:

nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}

Discrete logarithm problem

Let's leverage scalar multiplication to generate the secret key 🔑. This key, denoted by $K$ , represents the number of times a base point $G$ is added to itself, yielding the resulting public point $P$ :

P = K*G

Given $P$ and $G$ it is possible derive the secret key $K$ by effectively reversing the multiplication, similar to the logarithm problem.

We need to ensure that scalar multiplication does not leak our secret key 🔑. In other words, scalar multiplication should be "easy" one way and "untraceable" the other way around.

The analogy of a clock helps illustrate the desired one-way nature. Imagine a task starting at 12 noon and ending at 3. Knowing only the final time (3) makes it impossible to determine the exact duration without additional information. This is because modular arithmetic introduces a "wrap-around" effect. The task could have taken 3 hours, 15 hours, or even 27 hours, all resulting in the same final time modulo 12.

Over a prime modulus, this is especially hard and is known as discrete logarithm problem.

Elliptic curves over finite field

So far, we have implicitly assumed elliptic curves over the rational field ( $\mathbb{R}$ ). Ensuring secret key 🔑 security through the discrete logarithm problem requires a transition to elliptic curves over finite fields defined by a prime modulus. This essentially restricts the points on the curve to a finite set by performing modular reduction with a specific prime number.

For the sake of this discussion, we will consider the secp256k1 curve defined over an arbitrary finite field with prime modulus 997:

y^2 = x^3 + 7 \pmod {997}

While the geometric representation of the curve in the finite field may appear abstract compared to a continuous curve, its symmetry remains intact. Additionally, scalar multiplication remains closed, although the "tangent" now "wraps around" given the modulus nature.

Generating key pair

Alice can finally generate a key pair using elliptic curve over finite field.

Let's define the elliptic curve over the finite field of prime modulus 997 in Sage.

sage: E = EllipticCurve(GF(997),[0,7])
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 997

Define the generator point $G$ by selecting an arbitrary point on the curve.

sage: G = E.random_point()
(174 : 487 : 1)

Scalar multiplication over an elliptic curve defines a cyclic subgroup of order $n$ . This means that repeatedly adding any point in the subgroup $n$ times results in the point at infinity ( $O$ ), which acts as the identity element.

nP = O

sage: n = E.order()
1057
# Illustrating that n*G (or any point) equals O, represented by (0 : 1 : 0).
sage: n*G
(0 : 1 : 0)

A key pair consists of:

Secret key 🔑( $K$ ): A random integer chosen from the order of the subgroup $n$ . Ensures only Alice can produce valid signatures.

Alice randomly chooses 42 as the secret key 🔑.

sage: K = 42

Public key ( $P$ ): A point on the curve, the result of scalar multiplication of secret key 🔑( $K$ ) and generator point ( $G$ ). Allows anyone to verify Alice's signature.

sage: P = K*G
(858 : 832 : 1)

We have established that Alice's key pair $=[P, K] = [(858, 832), 42]$ .

ECDSA in action

ECDSA is a variant of the Digital Signature Algorithm (DSA). It creates a signature based on a "fingerprint" of the message using a cryptographic hash.

For ECDSA to work, Alice and Bob must establish a common set of domain parameters. Domain parameters for this example are:

Parameter	Value
The elliptic curve equation.	$y^2 = x^3 + 7$
The prime modulo of the finite field.	997
The generator point, $G$ .	(174, 487)
The order of the subgroup, $n$ .	1057

Importantly, Bob is confident that the public key $P = (858, 832)$ actually belongs to Alice.

Signing

Alice intends to sign the message "Send $1 million", by following the steps:

Compute the cryptographic hash $m$ .

sage: m = hash("Send $1 million")
-7930066429007744594

For every signature, a random ephemeral key pair [ $eK$ , $eP$ ] is generated to mitigate an attack exposing her secret key 🔑.

# Randomly selected ephemeral secret key.
sage: eK = 10
# Ephemeral public key.
sage: eP = eK*G
(215 : 295 : 1)

Ephemeral key pair $=[eK, eP] = [10, (215, 295)]$ .

Compute signature component $s$ :

$s = k^{−1} (e + rK ) \pmod n$

Where $r$ is the x-coordinate of the ephemeral public key (eP), i.e 215. Notice the signature uses both Alice's secret key 🔑 ( $K$ ) and the ephemeral key pair [ $eK$ , $eP$ ].

# x-coordinate of the ephemeral public key.
sage: r = int(eP[0])
215
# Signature component, s.
sage: s = mod(eK**-1 * (m + r*K), n)
160

The tuple $(r,s) = (215, 160)$ is the signature pair.

Alice then writes the message and signature to the postcard.

Verification

Bob verifies the signature by independently calculating the exact same ephemeral public key from the signature pair $(r,s)$ , message, and Alice's public key $P$ :

Compute the cryptographic hash $m$ .

sage: m = hash("Send $1 million")
-7930066429007744594

Compute the ephemeral public key $R$ , and compare it with $r$ :

$R = (es^{−1} \pmod n)*G + (rs^{−1} \pmod n)*P$

sage: R = int(mod(m*s^-1,n)) * G  + int(mod(r*s^-1,n)) * P
(215 : 295 : 1)
# Compare the x-coordinate of the ephemeral public key.
sage: R[0] == r
True # Signature is valid ✅

If Alice's captors were to modify the message, it would alter the cryptographic hash, leading to verification failure due to the mismatch with the original signature.

sage: m = hash("Send $5 million")
7183426991750327432 # Hash is different!
sage: R = int(mod(m*s^-1,n)) * G  + int(mod(r*s^-1,n)) * P
(892 : 284 : 1)
# Compare the x-coordinate of the ephemeral public key.
sage: R[0] == r
False # Signature is invalid ❌

Verification of the signature assures Bob of the message's authenticity, enabling him to transfer the funds and rescue Alice. Elliptic curves saves the day!

Wrapping up

Just like Alice, every account on the Ethereum uses ECDSA to sign transactions. However, ECC in Ethereum involves additional security considerations. While the core principles remain the same, we use secure hash functions like keccak256 and much larger prime field, boasting 78 digits: $2^{256}-2^{32}-977$ .

This discussion is a preliminary treatment of Elliptic Curve Cryptography. For a nuanced understanding, consider the resources below.

And finally: never roll your own crypto! Use trusted libraries and protocols to protect your data and transactions.

ℹ️ Note
ECDSA faces potential obsolescence from quantum computers – learn about how Post-Quantum Cryptography tackles this challenge.

Credits

Thanks to Michael Driscoll for his work on animated elliptic curves.

ECDSA