Elegant Signatures with Elliptic Curve Cryptography

Elegance is the only beauty that never fades. This is a loving Audrey Hepburn quote. I struggle to adapt this thought into my all life. In this post, we will mention how to create much more elegant signatures with elliptic curves.

Vlog

High level explanation of ECDSA

---

🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

---

Python implementation from scratch

Why ECDSA

Digital signatures enable trustability to messages even sent through insecure channel. Today, the most common adoption for digital signatures is RSA. There are lots of reasons for this adoption. First of all, RSA announced first. Moreover, the math behind RSA is easy to understand. On the other hand, it requires to compute powers of very large integers. In other words, its computational cost is high and it is hard to run.

On the other hand, Elliptic Curve Cryptography (ECC) is an amazing alternative to RSA. First of all, its computational cost is not high and it requires linear computations. That’s why, it is easy to run it on a simple hardware. However, the math behind ECC is very complex. Because of this complexity, people might keep away from it.

So, ECC offers same strength for smaller key sizes (12 times smaller! 3072 bit RSA = 256 bit ECC). That’s the elegance that we would like to have.

Previously, we’ve focused on addition formulas and mentioned how to calculate a public key on an elliptic curve. These are all prerequisites to apply Elliptic Curve Digital Signature Algorithm (ECDSA).

Public Configuration

An elliptic curve in Weierstrass form satisfies the equation y² = x³ + ax + b. The variables a and b must be public. Furthermore, a point on the curve must be known publicly as base point.

Finally, finite field and order of group must be announced publicly. Finite fields state the modulo values whereas order of group state number of points on that curve. BTW, finite fields enable to produce integer results. Divisor terms can be expressed as multiplier by applying Extended Euclidean Algorithm in point addition formulas for Elliptic Curves. Counting points on an elliptic curve is important subject. We discard it for now.

Bitcoin protocol employs secp256k1 and its public configuration is shown below. We will work on these configuration, too.

---

---

#curve configuration
# y^2 = x^3 + a*x + b = y^2 = x^3 + 7
a = 0; b = 7

#base point
x0 = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y0 = 32670510020758816978083085130507043184471273380659243275938904335757337482424

#finite field
mod = pow(2, 256) - pow(2, 32) - pow(2, 9) - pow(2, 8) - pow(2, 7) - pow(2, 6) - pow(2, 4) - pow(2, 0)
order = 115792089237316195423570985008687907852837564279074904382605163141518161494337

Public Key Generation

You should select a private key length of 32-byte and keep it secret. Then, you need to calculate your public key

privateKey = 75263518707598184987916378021939673586055614731957507592904438851787542395619
# privateKey = random.genrandbits(256)
publicKeyX, publicKeyY = applyDoubleAndAddMethod(x0, y0, privateKey, a, b, mod)
print("public key: ",publicKeyX, ", ", publicKeyY)

Random Point Generation

ECDSA requires an additional random point. Random Point can be calculated as Random Key times base point.

import random
randomKey = random.getrandbits(128)
randomPointX, randomPointY = applyDoubleAndAddMethod(x0, y0, randomKey, a, b, mod)
print("random point: (", randomPointX,", ",randomPointY,")")

Hashing

Hash algorithms are one-way and non-invertible functions. Signing will be applied on hash value instead of message.

message = b"ECC beats RSA"

import hashlib
hashHex = hashlib.sha1(message).hexdigest()
hash = int(hashHex, 16)

print("message: ", message)
print("hash: ", hash)

Signing

Signature of the message is r and s pair. The following formulas will be used to calculate these pair.

r = (randomPoint)_x

s = (hash + r * privateKey) * [(randomKey)^-1 mod order] mod order

We can adapt these formula into python as illustrated below.

r = randomPointX % order

s = hash + (r * privateKey)
s = s * pow(randomKey, -1, order)
s = s % order

print("signature")
print("r: ", r)
print("s: ", s)

Verification

To verify the signature, we can calculate the following formulas

w = s^-1 mod order

u1 = (hash * w mod order) x base point

---

---

u2 = (r * w mod order) x public key

checkpoint = u1 + u2

So, we can adapt these formulas in python just like the following code snippet.

w = pow(s, -1, order)
u1 = applyDoubleAndAddMethod(x0, y0, (hash * w) % order, a, b, mod)
u2 = applyDoubleAndAddMethod(publicKeyX, publicKeyY, (r * w) % order, a, b, mod)

checkpoint = pointAddition(u1[0], u1[1], u2[0], u2[1], a, b, mod)

X coordinate of checkpoint must be equal to r in the signature if the signature is valid. That’s all to validate signature.

if(checkpoint[0] == r):
   print("signature is valid...")
else:
   print("invalid signature detected!!!")

Everything seems OK!

How It Works

Signing and verification calculations are not arbitrary calculations, of course. Please look at the checkpoint calculation formula.

checkpoint = u1 + u2

Put both u1 and u2 point calculation clearly in this statement

checkpoint = (hash * w) x base point + (r * w) x public key

Here, we can express public key as private key x base point

---

---

checkpoint = (hash * w) x base point + (r * w) * private key x base point

Now, both addition terms include base point and w as multiplier. Parenthesize it as base point multiplication.

checkpoint = (hash + r * private key) w x base point

What’s next? Remember how to calculate w and s pair.

w = s^-1 mod order

s = (hash + r * privateKey) * [(randomKey)^-1 mod order] mod order

Put s into the w calculation

w = ((hash + r * privateKey) * ((randomKey)^-1) mod order)^-1

w = (hash + r * privateKey )^-1 * (randomKey)

w = (hash + r * privateKey)^-1 * randomKey

---

---

Now put this in the checkpoint instead of w

checkpoint = (hash + r * private key) * (hash + r * privateKey)^-1 * randomKey x base point

As seen both parenthesized terms are inverse of each other. Their multiplication is equal to 1.

To sum up, you calculate the random key times base point as checkpoint. It is actually the random point.

checkpoint = randomKey x base point = random point

Now remember that we compare x coordinate of checkpoint to r value. Interestingly, r is the x coordinate of random point. That must be equal if message is valid. Because we proven that checkpoint is equal to random point.

Importance of random key

Random keys must be different for each signed message. Otherwise, it will cause your private key to be stolen similar to the hack of Sony PlayStation 3 in 2010.

Our signature pair was (r, s). Let’s remember how s was calculated.

s = (hash + r * privateKey) * [(randomKey)^-1 mod order] mod order

And r was the x coordinate of the randomKey x base point

---

---

What if two different messages (h1 and h2) are signed with same random key

s1 = (h1 + r * privateKey) * [(randomKey)^-1 mod order] mod order

s2 = (h2 + r * privateKey) * [(randomKey)^-1 mod order] mod order

An attacker can subtract s2 from s1 then

s1 – s2 = (h1 + r * privateKey) * [(randomKey)^-1 mod order] mod order – (h2+ r * privateKey) * [(randomKey)^-1 mod order] mod order

Then we can represent this subtraction with the common multiplicative inverse of random key.

s1 – s2 = [(randomKey)^-1 mod order] (h1 + r * privateKey – h2 – r * privateKey)

We can simplify the r times private key

s1 – s2 = [(randomKey)^-1 mod order] (h1 – h2)

Notice that s1 and s2 are known publicly because they are signatures. Also, h1 and h2 are known publicly because they are the hash of public messages. So, an attacker can find random key from this equation.

---

---

Thereafter, if the attacker knows random key, then he can find the private key from the 1st or 2nd signature calculation.

s1 = (h1 + r * privateKey) * [(randomKey)^-1 mod order] mod order

Here, s1 is publicly known. Also, the attacker just restore the random key. Finally, r was the x coordinate of random key times base point. So, the attacker can use double and add method to find the corresponding point and extract its x coordinate. In summary, the attacker will have the private key. Also, he does not have to solve the elliptic curve discrete logarithm problem!

Let’s implement the private key restoration from two signatures if they are signed with same random key.

# attacker restores private key

# h1 - h2: hash values of 1st and 2nd message
# s1 - s2: s parts of the 1st and 2nd signature

randomKeyPrime = ( ( (h1 - h2) % order ) * pow(s1 - s2, -1, order) ) % order
assert randomKey == randomKeyPrime

randomPointPrime = applyDoubleAndAddMethod(x0, y0, randomKeyPrime, a, b, mod)
rPrime = randomPointPrime[0]
assert rPrime == r

privateKeyPrime = ( (s1 * randomKeyPrime - h1) * pow(rPrime, -1, order) ) % order
assert privateKeyPrime == privateKey

ECDSA vs EdDSA

EdDSA is a variant of ECDSA. See similarities and differences of these algorithms.

Summary

So, we’ve mentioned how to consume ECC to create digital signatures. In this way, a message can be signed with a much smaller key and in faster way. ECDSA is highly adopted in IOT devices because of their low power consumption. Moreover, Bitcoin transactions are signed with ECDSA, too. Finally, I pushed this study to GitHub.

---

Support this blog if you do like!

    

---