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 y2 = x3 + 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!
Hey, I don’t find the code in the github link you provided. Plz give me the code
Code is available here: https://github.com/serengil/crypto/blob/master/python/EccApp.py
Find the section – applyDigitalSignature