Edwards curves are pivotal ones in crypto field. The normal form Harold Edwards studied was x2 + y2 = c2 + c2x2y2. Previously, we have proven the addition formula of this form. Bernstein and Lange firstly transform the equation to simpler form x2 + y2 = 1 + dx2y2 . Thereafter, they modified regular Edwards curves and introduced twisted Edwards curves ax2 + y2 = 1 + dx2y2.
Twisted Edward curves look like a bird’s-eye roundabout intersection of a road.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Regular Edwards curves are special form of twisted Edwards curves where a = 1. We can prove the addition formula of twisted ones similarly. Besides, proof of twisted Edwards curves will also prove the regular Edwards forms Bernstein and Tanja simplified.
Lemma
Suppose that (x1, y1) and (x2, y2) are points on the curve ax2 + y2 = 1 + dx2y2. In this case, (x3, y3) derived from the following formula will be on the same curve.
x3 = (x1y2 + y1x2)/(1 + dx1x2y1y2)
y3 = (y1y2 – ax1x2)/(1 – dx1x2y1y2)
Proof
We can validate the addition formula by putting (x3, y3) values to the twisted edwards curve equation.
ax32 + y32 = 1 + dx32y32
a(x1y2 + y1x2)2/(1 + dx1x2y1y2)2 + (y1y2 – ax1x2)2/(1 – dx1x2y1y2)2 = 1 + d(x1y2 + y1x2)2(y1y2 – ax1x2)2/(1 + dx1x2y1y2)2(1 – dx1x2y1y2)2
Make denominators same
a(x1y2 + y1x2)2(1 – dx1x2y1y2)2/(1 + dx1x2y1y2)2(1 – dx1x2y1y2)2 + (y1y2 – ax1x2)2(1 + dx1x2y1y2)2/(1 – dx1x2y1y2)2(1 + dx1x2y1y2)2 = (1 – dx1x2y1y2)2(1 + dx1x2y1y2)2/(1 – dx1x2y1y2)2(1 + dx1x2y1y2)2 + d(x1y2 + y1x2)2(y1y2 – ax1x2)2/(1 + dx1x2y1y2)2(1 – dx1x2y1y2)2
Now, all denominators are same, we can simplify them. Note that (1 + dx1x2y1y2)2(1 – dx1x2y1y2)2 cannot be 0.
a(x1y2 + y1x2)2(1 – dx1x2y1y2)2 + (y1y2 – ax1x2)2(1 + dx1x2y1y2)2 = (1 – dx1x2y1y2)2(1 + dx1x2y1y2)2 + d(x1y2 + y1x2)2(y1y2 – ax1x2)2
Set P to x1x2y1y2 to express this complex equation simpler.
a(x1y2 + y1x2)2(1 – dP)2 + (y1y2 – ax1x2)2(1 + dP)2 = (1 – dP)2(1 + dP)2 + d(x1y2 + y1x2)2(y1y2 – ax1x2)2
The term (1 – dP)2(1 + dP)2 can also be written as [(1 – dP)(1 + dP)]2 = (1 – d2P2)2
a(x1y2 + y1x2)2(1 – dP)2 + (y1y2 – ax1x2)2(1 + dP)2 = (1 – d2P2)2 + d(x1y2 + y1x2)2(y1y2 – ax1x2)2
Evaluate the powers except (1 – d2P2)2
a(x12y22 + y12x22 + 2P)(1 + d2P2 – 2dP) + (y12y22 + a2x12x22 – 2aP)(1 + d2P2 + 2dP) = (1 – d2P2)2 + d(x12y22 + y12x22 + 2P)(y12y22 + a2x12x22 – 2aP)
Focus on the left side. We can separate 1 + d2P2 and 2dP multipliers.
(1 + d2P2)(a(x12y22 + y12x22 + 2P) + y12y22 + a2x12x22 – 2aP) + (2dP)(a(- x12y22 – y12x22 – 2P) + y12y22 + a2x12x22 – 2aP)
Move a multiplier into the paranthesis
(1 + d2P2)(ax12y22 + ay12x22 + 2aP + y12y22 + a2x12x22 – 2aP) + (2dP)(- ax12y22 – ay12x22 – 2aP + y12y22 + a2x12x22 – 2aP)
Plus and minus 2aP terms exist in the first paranthesis. We can remove them.
(1 + d2P2)(ax12y22 + ay12x22 + y12y22 + a2x12x22) + (2dP)(- ax12y22 – ay12x22 – 2aP + y12y22 + a2x12x22 – 2aP)
We can rewrite the term (ax12y22 + ay12x22 + y12y22 + a2x12x22) as (ax12 + y12)(ax22 + y22). Similarly, the term (- ax12y22 – ay12x22 – 2aP + y12y22 + a2x12x22 – 2aP) can be rewritten as ((ax12 – y12)(ax22 – y22) – 4aP).
(1 + d2P2)(ax12 + y12)(ax22 + y22) + (2dP)[(ax12 – y12)(ax22 – y22) – 4aP].
Move 2dP into the paranthesis
(1 + d2P2)(ax12 + y12)(ax22 + y22) + (2dP)(ax12 – y12)(ax22 – y22) – 8adP2
Now, focus on the right side.
(1 – d2P2)2 + d(x12y22 + y12x22 + 2P)(y12y22 + a2x12x22 – 2aP)
Move 2P term to the outside of the paranthesis
(1 – d2P2)2 + d[(x12y22 + y12x22)(y12y22 + a2x12x22) + 2P(y12y22 + a2x12x22 – ax12y22 + ay12x22) – 4aP2]
The term (y12y22 + a2x12x22 – ax12y22 + ay12x22) can be rewritten as (ax12 – y12)(ax22 – y22)
(1 – d2P2)2 + d[(x12y22 + y12x22)(y12y22 + a2x12x22) + 2P(ax12 – y12)(ax22 – y22)- 4aP2]
Also, (x12y22 + y12x22)(y12y22 + a2x12x22) can be rewritten as (x12y12y24 + a2x14x22y22 + x22y14y22 + a2x12x24y12)
(1 – d2P2)2 + d[(x12y12y24 + a2x14x22y22 + x22y14y22 + a2x12x24y12) + 2P(ax12 – y12)(ax22 – y22)- 4aP2]
The left side of the equation has (1 + d2P2). We can refactor the term (1 – d2P2)2 on the right side.
(1 – d2P2)2 = (1 + d2P2)2 – 4d2P2 = (1 + d2P2)(1 + d2P2) – 4d2P2
We got the term (1 + d2P2). Now, replace P value with original one in the multiplier.
(1 + d2P2)(1 + d2x12x22y12y22) – 4d2P2
Adding and substracting dx12y12 and dx22y22 values would not change the content.
(1 + d2P2)(1 + d2x12x22y12y22 + dx12y12 + dx22y22 – dx12y12 – dx22y22) – 4d2P2
Separate plus and minus sign terms in same side.
(1 + d2P2)(1 + d2x12x22y12y22 + dx12y12 + dx22y22) +(1 + d2P2)( – dx12y12 – dx22y22) – 4d2P2
We can rewrite the term (1 + d2x12x22y12y22 + dx12y12 + dx22y22) as (1 + dx12y12)(1 + dx22y22)
(1 + d2P2)(1 + dx12y12)(1 + dx22y22) + (1 + d2P2)( – dx12y12 – dx22y22) – 4d2P2
Rewrite (1 + d2P2)( – dx12y12 – dx22y22)
(1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12 – dx22y22 – d3x22y22(x14y14) – d3x12y12(x24y24) – 2d2x12y12x22y22 – 2d2x12y12x22y22
Combine the parts that containing dx12y12 and dx22y22
(1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + d2x24y24 + 2dx22y22) – dx22y22(1 + d2x14y14 + 2dx12y12)
The second and third terms can be expressed as power of an addition.
(1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + dx22y22)2 – dx22y22(1 + dx12y12)2
Combine left and right sides
(1 + d2P2)(ax12 + y12)(ax22 + y22) + (2dP)(ax12 – y12)(ax22 – y22) – 8adP2 = d[(x12y12y24 + a2x14x22y22 + x22y14y22 + a2x12x24y12) + 2P(ax12 – y12)(ax22 – y22)- 4aP2] + (1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + dx22y22)2 – dx22y22(1 + dx12y12)2
Move d multiplier into the paranthesis
(1 + d2P2)(ax12 + y12)(ax22 + y22) + (2dP)(ax12 – y12)(ax22 – y22) – 8adP2 = dx12y12y24 + da2x14x22y22 + dx22y14y22 + da2x12x24y12 + 2dP(ax12 – y12)(ax22 – y22)- 4adP2 + (1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + dx22y22)2 – dx22y22(1 + dx12y12)2
The both left and right side have (2dP)(ax12 – y12)(ax22 – y22). We can remove these terms.
(1 + d2P2)(ax12 + y12)(ax22 + y22) – 8adP2 = dx12y12y24 + da2x14x22y22 + dx22y14y22 + da2x12x24y12 – 4adP2 + (1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + dx22y22)2 – dx22y22(1 + dx12y12)2
Move – 8adP2 to the right side.
(1 + d2P2)(ax12 + y12)(ax22 + y22) = dx12y12y24 + da2x14x22y22 + dx22y14y22 + da2x12x24y12 + 4adP2 + (1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + dx22y22)2 – dx22y22(1 + dx12y12)2
Put the real value of P in 4adP2
(1 + d2P2)(ax12 + y12)(ax22 + y22) = dx12y12y24 + da2x14x22y22 + dx22y14y22 + da2x12x24y12 + 2adx12x22y12y22 + 2adx12x22y12y22 + (1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + dx22y22)2 – dx22y22(1 + dx12y12)2
Combine terms that containing x12y12 and x22y22
(1 + d2P2)(ax12 + y12)(ax22 + y22) = dx12y12(y24 + ax24 + 2ax22y22) + dx22y22(y14 + ax14 + 2ax12y12) + (1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + dx22y22)2 – dx22y22(1 + dx12y12)2
We can rewrite the term (y24 + ax24 + 2ax22y22) as (ax22 + y22)2 and (y14 + ax14 + 2ax12y12) as (ax12 + y12)2
(1 + d2P2)(ax12 + y12)(ax22 + y22) = dx12y12(ax22 + y22)2 + dx22y22(ax12 + y12)2+ (1 + d2P2)(1 + dx12y12)(1 + dx22y22) – dx12y12(1 + dx22y22)2 – dx22y22(1 + dx12y12)2
Combine the terms that containing (1 + d2P2)
(1 + d2P2)[(ax12 + y12)(ax22 + y22) – (1 + dx12y12)(1 + dx22y22) ] = dx12y12(ax22 + y22)2 – dx12y12(1 + dx22y22)2 + dx22y22(ax12 + y12)2 – dx22y22(1 + dx12y12)2
Still, we can combine terms containing dx12y12 and dx22y22
(1 + d2P2)[(ax12 + y12)(ax22 + y22) – (1 + dx12y12)(1 + dx22y22) ] = dx12y12[(ax22 + y22)2 – (1 + dx22y22)2]+ dx22y22[(ax12 + y12)2 – (1 + dx12y12)2]
All terms in brackets must be equal to zero based on the twisted Edwards curve equation. This proves the theorem as claimed.
Regular Edwards curves (simplified version)
We have already proven the addition formula for regular Edward curves Bernstein and Tanja introduced by setting variable a to 1.
x2 + y2 = 1 + dx2y2
x3 = (x1y2 + y1x2)/(1 + dx1x2y1y2)
y3 = (y1y2 – ax1x2)/(1 – dx1x2y1y2) = (y1y2 – x1x2)/(1 – dx1x2y1y2)
So, we haven proven addition formula for both twisted and regular Edwards curves. In particular, twisted ones are backbones of edwards curve based digital signatures. This signatures offer either high speed and high security. Every security specialist must put Edwards curves in their toolbox.
Support this blog if you do like!
Thank you for this beautiful article.