A Gentle Introduction to Edwards-curve Digital Signature Algorithm (EdDSA)

Elliptic curves are the most challenging topic in crypto field whereas Edwards curves are the hottest topic among elliptic curves. Elliptic curve digital signature algorithm can sign messages faster than the existing signature algorithms such as RSA, DSA or ElGamal. Herein, Edwards-curve digital signature algorithm or shortly EdDSA offers slightly faster signatures than ECDSA. This post covers a step by step explanation of the algorithm and python implementation from scratch.

Vlog

High Level Explanation of Edwards Curve Digital Signature Algorithm

---

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

---

You can either continue to read this tutorial or watch the following video. They both cover the Edwards Curve Digital Signature Algorithm in Python From Scratch.

The curve

The original paper recommends to use twisted Edwards curve. This curve looks like a bird’s-eye roundabout intersection of a road.

ax² + y² = 1 + dx²y²

This has a similar addition formula to regular Edwards curves. I mention the difference boldly. It exists in the numerator of the y coordinate of the new point.

(x₁, y₁) + (x₂, y₂) = (x₃, y₃)

x₃ = (x₁y₂ + y₁x₂)/(1 + dx₁x₂y₁y₂)

y₃ = (y₁y₂ – ax₁x₂)/(1 – dx₁x₂y₁y₂)

Ed25519 is a special form of this curve where a = -1, d = -121665/121666. It handles over prime fields where p = 2²⁵⁵ – 19. The final form of the ed25519 is illustrated below.

---

---

-x² + y² = 1 – (121665/121666) x²y² (mod 2²⁵⁵ – 19)

The base point of the curve is y = (u-1)/(u+1) where u = 9. The integer equivalent is demonstrated below.

p = pow(2, 255) - 19

base = 15112221349535400772501151409588531511454012693041857206046113283949847762202
, 46316835694926478169428394003475163141307993866256225615783033603165251855960

Moreover, the variable d is a double value. We can convert it to integer by moving its denominator to numerator by switching its multiplicative inverse value.

#ax^2 + y^2  = 1 + dx^2y^2
a = -1; d = findPositiveModulus(-121665 * findModInverse(121666, p), p) #ed25519

Point addition and doubling

Regular elliptic curves in weierstrass form have different formulas for addition and doubling. In contrast, the both operation will be handled by same addition formula in edwards curves. Working on finite fields requires to move denominators into the numerator by replacing its multiplicative inverse.

def pointAddition(P, Q, a, d, mod):
   x1 = P[0]; y1 = P[1]; x2 = Q[0]; y2 = Q[1]

   x3 = (((x1*y2 + y1*x2) % mod) * findModInverse(1+d*x1*x2*y1*y2, mod)) % mod
   y3 = (((y1*y2 - a*x1*x2) % mod) * findModInverse(1- d*x1*x2*y1*y2, mod)) % mod

   return x3, y3

Key generation

Alice needs to generate a 32-byte private key. Then, she need to calculate private key times base point. This would be her public key.

import random
privateKey = random.getrandbits(256) #32 byte secret key
publicKey = applyDoubleAndAddMethod(base, privateKey, a, d, p)

She can use double-and-add method to find her public key fast.

def applyDoubleAndAddMethod(P, k, a, d, mod):
   additionPoint = (P[0], P[1])

   kAsBinary = bin(k) #0b1111111001
   kAsBinary = kAsBinary[2:len(kAsBinary)] #1111111001
   #print(kAsBinary)

   for i in range(1, len(kAsBinary)):
      currentBit = kAsBinary[i: i+1]
      #always apply doubling
      additionPoint = pointAddition(additionPoint, additionPoint, a, d, mod)

      if currentBit == '1':
         #add base point
         additionPoint = pointAddition(additionPoint, P, a, d, mod)

   return additionPoint

Signing

Firstly, Alice needs to convert the message to the numeric value.

def textToInt(text):
   encoded_text = text.encode('utf-8')
   hex_text = encoded_text.hex()
   int_text = int(hex_text, 16)
   return int_text

message = textToInt("Hello, world!")

Remember that a random key was involved in elliptic curve digital signature algorithm (ECDSA). This must be different for each signing. Otherwise, it causes an important security issue. This security disaster appears in Sony PlayStation game console in 2010. In EdDSA, this is handled by generating random key based on the hash of the message. In this way, every message has a different random key.

def hashing(message):
   import hashlib
   return int(hashlib.sha512(str(message).encode("utf-8")).hexdigest(), 16)

r = hashing(hashing(message) + message) % p

Random key times base point will be random point R and it is a type of curve point. Extracting secret random key r from known random point R is a really hard problem (ECDLP). Besides, combination of the random point, public key and the message will be stored in the variable h after hashing. This can be calculated by receiver party, too. Then, s variable stores (r + h x private key) which is a type of integer. Signature of the message consists of (R, s) pair.

R = applyDoubleAndAddMethod(base, r, a, d, p)

h = hashing(R[0] + publicKey[0] + message) % p
s = (r + h * privateKey)

Verification

Bob receives the message and its signature (R, s). Also, he knows Alice’s public key, and public curve configuration (base point, a, d, p). He needs to find the folowing P1 and P2 pair.

---

---

h = hashing(R[0] + publicKey[0] + message) % p
P1 = applyDoubleAndAddMethod(base, s, a, d, p)
P2 = pointAddition(R
, applyDoubleAndAddMethod(publicKey, h, a, d, p)
, a, d, p)

P1 is signature’s s value times base point. P2 is the addition of signature’s R value and h times public key. Remember that h can be calculated by Bob, too. Herein, P1 and P2 pair must be equal if the signature if valid.

Background of EdDSA

You might wonder how this works. Focus on the calculation of P1.

P1 = s x basePoint

Signature’s s value is retrieved by (r + h x privateKey). Bob knows exact value of s also he knows h and r values but he does not know the private key of Alice. Replace s in P1 calculation.

P1 = (r + h x privateKey) x basePoint

Transfer base point multiplication into the parenthesis.

P1 = r x basePoint + h x privateKey x basePoint

In the equation above includes private key times base point. This is exactly equal to public key of Alice. Moreover, random key r times base point is equal to random point R.

P1 = R+ h x publicKey

Now, P1 is exactly equal to P2. Expectation of equality of these two points is obviously normal.

---

---

EdDSA vs ECDSA

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

Conclusion

So, we have mentioned the EdDSA and covered simply python implementation. This scheme is designed to be faster than any existing digital signature scheme. Also, signing two different messages with same random key causes secret key to be disclosed in ECDSA. This issue is handled in EdDSA. Finally, the code project of this post is pushed into the GitHub.

---

Support this blog if you do like!

    

---