In 2007, Harold Edwards introduced a new form for elliptic curves. Thereafter, people interestingly named this form as Edwards Curves. Nowadays, elliptic curves in Edwards form are drawn much attention in crypto community. Because this kind of elliptic curves come with a faster, simple and elegant addition law.
Edwards curves are very similar to unit circle.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Unit circle
Edwards curves show similarity with the unit circle. The unit circle satisfies the following equation.
x2 + y2 = 1
Suppose that (x1, y1) and (x2, y2) are points on the unit circle. The angle between y-axis and (x1, y1) is α and angle between y-axis and (x2, y2) is β.
We can express (x1, y1) as (sinα, cosα) and (x2, y2) as (sinβ, cosβ).
Now, I can add these two points by adding their corresponding angles. Angle sum identities will help me to formulate.
x3= sin(α+β) = sinα.cosβ + cosα.sinβ
y3 = cos(α+β) = cosα.cosβ – sinα.sinβ
We know that (x3, y3) will satisfy the unit circle equation. This is satisfactory but not elliptic!
Edwards Curves
Edwards curves satisfy the form x2 + y2 = a2 + a2x2y2. This is the form Harold Edwards studied in the original paper. Additionally, Bernstein and Lange contributed the study and transformed edward curves to a simpler form x2 + y2 = 1+ dx2y2.
Setting the variable d to 0 create unit circle. The curve looks like a Starfish when the variable d increases in negative direction.
I will mention the form that Harold Edwards mentioned in the following parts of this post. You can find the proof of simpler form x2 + y2 = 1+ dx2y2 here.
Addition law
Elliptic curves are based on constructing new points from existing points. Traditional forms such as Weierstrass or Koblitz use chords and tangents to construct a new point.
Edwards Curves use neither chords nor tangents. They have a their own characteristic construction method similar to unit circle’s addition law.
Edwards addition law says that if (x1, y1) and (x2, y2) are points on the edwards curve, the following (x3, y3) point derived from known points must be on the same curve.
x3 = (x1y2 + x2y1)/(a.(1+x1y1x2y2))
y3 = (y1y2 – x1x2)/(a.(1 – x1y1x2y2))
Previous studies
Euler and Gauss have worked on this kind of elliptic equations and discovered addition formulas in late 1700s.
This is Euler’s very first study that appears in Observations on the comparison of arcs of unrectifiable curves (Observationes de Comparatione Arcuum Curvarum Irrectificabilium) published in 1761 (pp. 83 to 103).
Then, Gauss was interested in same integrals and documented it in his Werke published in 1799 (pp. 404). He worked on the form x2 + y2 = 1+ dx2y2 where d = -1.
The following illustration demonstrates the difference between unit circle and elliptic form worked by Gauss.
We can say that Harold Edwards revealed already discovered theorems.
Proof of Edwards Addition law
It is not fully clear that how Euler and Gauss found this addition formula. They might just observe. However, we can still apply mathematical induction to validate the formula. Exact values of the new point (x3, y3) derived from the known points x1, y1, x2, y2 must satisfy the equation x2 + y2 = a2 + a2x2y2 if the addition formula is valid. This is how exactly Harold Edwards proves the addition law in the original paper.
x32 + y32 = a2 + a2x32y32
x3 = (x1y2 + x2y1)/(a.(1+x1y1x2y2)) , y3 = (y1y2 – x1x2)/(a.(1 – x1y1x2y2))
Put the exact values into the Edwards form.
(x1y2 + x2y1)2/a2.(1+x1y1x2y2)2 + (y1y2 – x1x2)2/a2.(1 – x1y1x2y2)2 = a2 + a2.(x1y2 + x2y1)2(y1y2 – x1x2)2/a2.(1+x1y1x2y2)2.a2.(1 – x1y1x2y2)2
The identity will become very complex. That’s why, say P to x1y1x2y2. We will restore it later.
(x1y2 + x2y1)2/a2.(1+P)2 + (y1y2 – x1x2)2/a2.(1 – P)2 = a2 + a2.(x1y2 + x2y1)2(y1y2 – x1x2)2/a2.(1+P)2.a2.(1 – P)2
Denominators must be equal to apply addition
(x1y2 + x2y1)2.(1 – P)2/a2.(1+P)2.(1 – P)2 + (y1y2 – x1x2)2.(1+P)2/a2.(1 – P)2.(1+P)2 = a2.a2.(1+P)2.(1 – P)2/1.a2.(1+P)2.(1 – P)2 + a2.(x1y2 + x2y1)2(y1y2 – x1x2)2/a2.(1+P)2.a2.(1 – P)2
The second term on the right side has a2 multiplier in both dividend and denominator. We can simplify the expression.
(x1y2 + x2y1)2.(1 – P)2/a2.(1+P)2.(1 – P)2 + (y1y2 – x1x2)2.(1+P)2/a2.(1 – P)2.(1+P)2 = a2.a2.(1+P)2.(1 – P)2/1.a2.(1+P)2.(1 – P)2 + (x1y2 + x2y1)2(y1y2 – x1x2)2/a2.(1+P)2.(1 – P)2
Now, all denominators are same. We can simplify the denominators.
(x1y2 + x2y1)2.(1 – P)2 + (y1y2 – x1x2)2.(1+P)2 = a4.(1+P)2.(1 – P)2 + (x1y2 + x2y1)2(y1y2 – x1x2)2
Note that simplified denominator must not be equal to 0.
a2.(1+x1y1x2y2)2.(1 – x1y1x2y2)2 ≠ 0
Please focus on the term (1+P)2.(1 – P)2. We can rewrite it as [(1+P)(1-P)]2 = (1 – P2)2
(x1y2 + x2y1)2.(1 – P)2 + (y1y2 – x1x2)2.(1+P)2 = a4.(1 – P2)2 + (x1y2 + x2y1)2(y1y2 – x1x2)2
Focus on the left side of the equation. Evaluate the powers.
(x12y22 + x22y12 + 2P)(1 + P2 – 2P) + (y12y22 + x12x22 – 2P)(1 + P2 + 2P)
Combine the parts that contain 1 + P2 and 2P respectively.
(1 + P2)(x12y22 + x22y12 + 2P + y12y22 + x12x22 – 2P) + (2P)(- x12y22 – x22y12 – 2P + y12y22 + x12x22 – 2P)
(1 + P2)(x12y22 + x22y12 + y12y22 + x12x22) + (2P)(- x12y22 – x22y12 + y12y22 + x12x22 – 4P)
(1 + P2)(x12 + y12)(x22 + y22) + (2P)[(x12 – y12)(x22 – y22) – 4P]
(1 + P2)(x12 + y12)(x22 + y22) + 2P.(x12 – y12)(x22 – y22) – 8P2
Now, focus on the right side of the equation
(x1y2 + x2y1)2(y1y2 – x1x2)2 = (x12y22 + x22y12 + 2P)(y12y22 + x12x22 – 2P)
Put the term 2P to the outside.
(x12y22 + x22y12)(y12y22 + x12x22) + 2P(y12y22 + x12x22 – x12y22 – x22y12) – 4P2
(x12y12y24 + x14x22y22 + x22y14y22 + x12x24y12) + 2P(x12 – y12)(x22 – y22) – 4P2
Put left and right side together again
(1 + P2)(x12 + y12)(x22 + y22) + 2P.(x12 – y12)(x22 – y22) – 8P2 = a4.(1 – P2)2 + (x12y12y24 + x14x22y22 + x22y14y22 + x12x24y12) + 2P(x12 – y12)(x22 – y22) – 4P2
The both left and right side have the term 2P.(x12 – y12)(x22 – y22). We can simplify the equation. Also, we can add the term +8P2 on both side.
(1 + P2)(x12 + y12)(x22 + y22) = a4.(1 – P2)2 + (x12y12y24 + x14x22y22 + x22y14y22 + x12x24y12) + 4P2
Here, we can manipulate the term (1 – P2)2. The left side has the term (1 + P2), we should assimilate (1 – P2)2 to (1 + P2).
(1 – P2)2 = (1 + P2)2 – 4P2 = (1 + P2)(1 + P2) – 4P2
Put the real value instead of P
(1 + P2)(1 + x12y12x22y22) – 4P2
Adding and subtracting same values would not change the value
(1 + P2)(1 + x12y12x22y22 + x12y12 + x22y22 – x12y12 – x22y22) – 4P2
We can seperate the second parentheses
(1 + P2)(1 + x12y12x22y22 + x12y12 + x22y22) – (1 + P2)(x12y12 + x22y22) – 4P2
The second parentheses can be expressed as multiplication of two terms
(1 + P2)(1 + x12y12)(1 + x22y22) – (1 + P2)(x12y12 + x22y22) – 4P2
Reflect the minus sign into the parentheses
(1 + P2)(1 + x12y12)(1 + x22y22) + (- 1 – P2)(x12y12 + x22y22) – 4P2
Multiply two parentheses on the second term
(1 + P2)(1 + x12y12)(1 + x22y22) – x12y12 – x22y22 – P2x12y12 – P2x22y22 – 4P2
(1 + P2)(1 + x12y12)(1 + x22y22) – x12y12 – x22y22 – x22y22(x14y14)- x12y12(x24y24) – 2x12y12x22y22 – 2x12y12x22y22
(1 + P2)(1 + x12y12)(1 + x22y22) – x12y12(1 + x24y24 + 2x22y22) – x22y22(1 + x14y14 + 2x12y12)
(1 + P2)(1 + x12y12)(1 + x22y22) – x12y12(1 + x22y22)2 – x22y22(1 + x12y12)2
So, the term (1 – P2)2 can be expressed as (1 + P2)(1 + x12y12)(1 + x22y22) – x12y12(1 + x22y22)2 – x22y22(1 + x12y12)2
Turn back to the main equation
(1 + P2)(x12 + y12)(x22 + y22) = a4.(1 – P2)2 + (x12y12y24 + x14x22y22 + x22y14y22 + x12x24y12) + 4P2
Restore the 4P2
(1 + P2)(x12 + y12)(x22 + y22) = a4.(1 – P2)2 + (x12y12y24 + x14x22y22 + x22y14y22 + x12x24y12) + 2x12y12x22y22 + 2x12y12x22y22
Combine the parts that contain x12y12 and x22y22
(1 + P2)(x12 + y12)(x22 + y22) = a4.(1 – P2)2 + x12y12(x24 + y24 + 2x22y22) + x22y22(x14 + y14 + 2x12y12)
(1 + P2)(x12 + y12)(x22 + y22) = a4.(1 – P2)2 + x12y12(x22 + y22)2 + x22y22(x12 + y12)2
Now, set (1 – P2)2 to its manipulated value
(1 + P2)(x12 + y12)(x22 + y22) = a4.[(1 + P2)(1 + x12y12)(1 + x22y22) – x12y12(1 + x22y22)2 – x22y22(1 + x12y12)2] + x12y12(x22 + y22)2 + x22y22(x12 + y12)2
(1 + P2)(x12 + y12)(x22 + y22) = a4(1 + P2)(1 + x12y12)(1 + x22y22) – a4.x12y12(1 + x22y22)2 – a4.x22y22(1 + x12y12)2 + x12y12(x22 + y22)2 + x22y22(x12 + y12)2
Combine the parts that contain (1 + P2)
(1 + P2).[(x12 + y12)(x22 + y22) – a4(1 + x12y12)(1 + x22y22)] + a4.x12y12(1 + x22y22)2 + a4.x22y22(1 + x12y12)2 – x12y12(x22 + y22)2 – x22y22(x12 + y12)2 = 0
Reflect a multipliers into the parentheses
(1 + P2).[(x12 + y12)(x22 + y22) – (a2 + a2x12y12)(a2 + a2x22y22)] + (a2)2.x12y12(1 + x22y22)2 + (a2)2.x22y22(1 + x12y12)2 – x12y12(x22 + y22)2 – x22y22(x12 + y12)2 = 0
(1 + P2).[(x12 + y12)(x22 + y22) – (a2 + a2x12y12)(a2 + a2x22y22)] + x12y12(a2 + a2x22y22)2 + x22y22(a2 + a2x12y12)2 – x12y12(x22 + y22)2 – x22y22(x12 + y12)2 = 0
(1 + P2).[(x12 + y12)(x22 + y22) – (a2 + a2x12y12)(a2 + a2x22y22)] + (x12y12)[(a2 + a2x22y22)2 – (x22 + y22)2] + (x22y22)[(a2 + a2x12y12)2 – (x12 + y12)2] = 0
Remember the main equation for Edwards form x2 + y2 = a2 + a2x2y2 . We’ve already known that points (x1, y1) and (x2, y2) satisfy this equation.
x12 + y12 = a2 + a2x12y12
x22 + y22 = a2 + a2x22y22
Multiply these two equations
(x12 + y12).(x22 + y22) = (a2 + a2x12y12)(a2 + a2x22y22)
Move the terms on the right side to the left side
(x12 + y12)(x22 + y22) – (a2 + a2x12y12)(a2 + a2x22y22) = 0
Also, we can apply same approach to individual equation
x12 + y12 – (a2 + a2x12y12) = 0
x22 + y22 – (a2 + a2x22y22) = 0
As seen, these all appear in the final form of the equation
(1 + P2).[(x12 + y12)(x22 + y22) – (a2 + a2x12y12)(a2 + a2x22y22)] + (x12y12)[(a2 + a2x22y22)2 – (x22 + y22)2] + (x22y22)[(a2 + a2x12y12)2 – (x12 + y12)2] = 0
(1 + P2).[0] + (x12y12)[0] + (x22y22)[0] = 0
Finally, the equation becomes 0 = 0. This proves the addition law as claimed!
Doubling
Addition law can also be applied for doubling a point. Replacing (x2, y2) pair with (x1, y1) in the addition formula gives the doubling formula.
(x1, y1) + (x1, y1) = (x3, y3)
x3 = (x1y1 + x1y1)/(a.(1+x1y1x1y1)) = (x1y1 + x1y1)/(a.(1+x12y12))
y3 = (y1y1 – x1x1)/(a.(1 – x1y1x1y1)) = (y12 – x12)/(a.(1 – x12y12))
So, we have all the necessary stuff to find the coordinates of a point. Point addition and doubling enable to calculate a target point fast with double and add method.
Conclusion
So, we’ve mentioned elliptic curves in Edwards form. Even though addition law was discovered more than 2 centuries ago by math geniuses, adapting into the cryptography occurs in last decade. Proof of Edwards addition law may seem much harder than Weierstrass or Koblitz curves, but calculations would be handled much easier. This makes Edwards curves so popular today.
Bonus
Bernstein shows Weierstrass as a turtle (bird’s-eye view) and Edwards as a starfish in his slides. This metaphor supports the speed of elliptic curve forms. Weierstrass is old and slow whereas Edwards is new and fast. This is really funny!
Special thanks to
Publications of Christiane Peters, in particular her PhD thesis has been driver for me to enjoy and understand Edwards Curves. Besides, I got much help from studies of Tanja Lange and Daniel J. Bernstein.
Support this blog if you do like!
