Edwards normal form

From Elliptic Curve Crypto


Caveat emptor: "Edwards curves" are quartic curves, i.e. curves of degree four, and moreover trivally reducible to a degree of two, because the variables appear only with even powers in the equation of the normal form. They are not very interesting for cryptographic use, because any cryptographic properties of Edwards curve public key schemes such as Ed448 or Ed25519 depend solely on the prime numbers specified as moduli.

Curve known as Ed448 “Goldilocks” in Edwards normal form with

A quartic curve is in Edwards normal form[1] if it can be described by the equation

The more general original Edwards form has another parameter c

but it is very simple to eliminate the scale parameter c and reduce this equation to its normal form for ease of performing algebraic group operations on rational points or finite fields.

The twist


This curve in a so-called twisted Edwards form is the one used in the Ed25519 digital signature scheme [2].

There is also a “twisted” Edwards form

And this brings us back to the ancient Greek word στραγγός with the idea of using something “twisted” for strong cryptography.

Point group arithmetic

The point group operation as defined here is plotted on the “untwisted” Ed448 curve (with d=-39081 and the twist parameter a=1.) When the points indicated with hollow circles are “added,” the result point is shown with a filled-in circle.

The point group operation on Edwards curves is defined in the primary sources [3] of the Ed25519 and Ed448 schemes (take or leave the twist parameter a) as

.


To the best of our knowledge, this resolves to a simple circle group over a conic section, and not to a proper quartic point group operation.

If then this can be rewritten as the conic section equation by setting and , and we have

.

Protestants find it offensive to refer to arithmetic or other operations as of some “law” or as works done through or under the “law” so to speak, (and not the natural laws of mathematics,) although that term does appear as such in the original literature. It is something vaguely felt to be grammatically repulsive, almost as if in Spanish to imply, “bajo la ley” and not “sobre la ley” or above-board.

The term “law” is normally reserved in mathematical contexts for a formal probability measure over an event space. The abuse of the term in the cryptologic literature (hint, hint, there’s an arbitrary “law” involved in a mathematical operation) cannot be a coincidence. The FBI under Christopher Wray has for many years, and under other directors as well, been demanding “lawful access” to break the aforementioned encryption at will, and as usual, it’s “for the children” [4][5].

Example program in R

The point group “sum” of any two points on the curve should be derivable from geometric considerations of lines intersecting the curve and reflecting across axes as in the case of the Weierstraß normal form, but the precise rules seem a little bit more complicated, exactly which reflections to take where with so many axes of symmetry.


The “sum” point as shown on this R plot appears at first glance to be the reflection through the origin of the point of intersection of the curve and the line segment (not shown) joining one of the two points which were “added” with the reflection across the x-axis of the other, but there are many other cases to consider. This R code picks two points on the Ed448 curve at random and “sums” them.

#! /usr/bin/R -f

f <- function(x){sqrt((1-x^2)/(1+39081*x^2))}
g <- function(x1,y1,x2,y2,d=-39081){
	(x1*y2 + y1*x2) / (1 + d*x1*x2*y1*y2)
}
h <- function(x1,y1,x2,y2,d=-39081,a=1){
	(y1*y2 - a*x1*x2) / (1 - d*x1*x2*y1*y2)
}

x <- seq(0,1,0.0001); x <- c(rev(x),-x)
y <- f(x)
x <- c(x,rev(x)); y <- c(y,rev(-y))

xp <- (rbinom(2,100,0.5)-50)/100
yp <- f(xp) * (-1)^sample.int(2,1)

plot(x,y,type="l")
points(xp,yp)

points(g(xp[1],yp[1],xp[2],yp[2]),h(xp[1],yp[1],xp[2],yp[2]),pch=19)

Group structure, identity and degree

The point (0,1) serves as an identity for the point group operation as defined by Bernstein et al. on curves in Edwards form, normal or twisted.

Much of the trouble here is that these “Edwards curves” are not really elliptic curves at all, because their degree as defined is four, and not three. Furthermore, they are readily simplified on geometric considerations: they become simple conic sections when is plotted against and the degree is reduced to two. Taking square roots then gives the point group operation as defined with a much simpler geometric interpretation which is missing for curves in the fourth degree. In effect, a circle group with the simplest possible cyclic structure is yielded with birational equivalences among the conic sections: hyperbolæ, parabolaæ, ellipses. We can’t really take the suggestions or recommendations of conic sections or the squares of coördinates of conic sections seriously for cryptography.

These simple conic section group operations of degree two are certainly more “efficient” to compute, and even more so when the coördinates are squared, than are the point group operations involving true elliptic curves of degree three in Weierstraß normal form or Montgomery normal form with an additional point at infinity which serves for those curves as the identity for a proper point group operation.

  1. Harold M. Edwards. “A normal form for elliptic curves.” Bulletin of the American Mathematical Society, vol. 44, no. 3, Jul 2007, pp. 393–422. https://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/
  2. Wikipedia: EdDSA https://en.wikipedia.org/wiki/EdDSA#Ed25519
  3. Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters. “Twisted Edwards Curves.” Cryptology ePrint Archive, vol. 2008, no. 013 https://eprint.iacr.org/2008/013.pdf
  4. Christopher Wray, Director Federal Bureau of Investigation. “Finding a Way Forward on Lawful Access: Bringing Child Predators out of the Shadows: Remarks as delivered.” Department of Justice Lawful Access Summit, Washington, D.C. October 4, 2019. https://www.fbi.gov/news/speeches/finding-a-way-forward-on-lawful-access
  5. Zack Whittaker. “US attorney general William Barr says Americans should accept security risks of encryption backdoors.” TechCrunch, July 23, 2019. https://techcrunch.com/2019/07/23/william-barr-consumers-security-risks-backdoors/