Twisting Edwards curves with isogenies.
Mike Hamburg · 2014
Edwards ’ elliptic curve form is popular in modern cryptographic implementations thanks to their fast, strongly unified addition formulas. Twisted Edwards curves with a = −1 are slightly faster, but their addition formulas are not complete over Fp where p ≡ 3 (mod 4). In this short note, we propose that designers specify Edwards curves, but implement scalar multiplications and the like using an isogenous twisted Edwards curve. 1 Edwards curves Edwards and Twisted Edwards elliptic curves [4, 3, 6] have the form Ed,a: y 2 + a · x 2 = 1 + d · x 2 · y 2 over some field F, with d, a ̸ = 0. Their identity is (0, 1), and they have a point of order 2 at (0, −1). For speed and simplicity, most authors choose a ∈ {±1}, so we will consider only those values of a. In this paper, we will call the curve “twisted ” when a = −1 and “untwisted ” when a = 1. When d is square in F, the curve Ed,a has a point of order 4 with y = ∞. Likewise, when d/a is square in F, it has a point of order 2 with x = ∞. When a is square in F, it has points of order 4 with y = 0, such as (±1, 0) when a = 1. The addition formula on Ed,a is (x1, y1) + (x2, y2) = x1y2 + y1x2 1 + dx1x2y1y2 y1y2 − ax1x2 1 − dx1x2y1y2 This formula is correct when neither the inputs nor outputs include points at infinity [6]. For a = 1, it may be computed with 9 full field multiplications, plus 1 multiplication by d (which might be small for efficiency) and 7 additions. When a = −1, it may be computed with 8