A DEVICE, METHOD AND A COMPUTER PROGRAM PRODUCT FOR CALCULATING ADDITIONS OF POINTS ON ELLIPTIC CURVES IN EDWARDS FORM

摘要

A device (100) for calculations on elliptic curves. The elliptic curve in generalized Edwards form is projected on a projective form so that a point P = (x1, y1) on the elliptic curve is represented by the tuple (x1Z1 : y1Z1: Z1) for any Z1 ? 0. An addition of two projective points (X1 : V1 : Z1) and (X2 : V2 : Z2) is given by X3 = Z1Z2(X1 Y2 + X2Y1)M, Y3 = Z1Z2(Y1 Y2 - e X1X2)N, and Z3 = MN, where M = f Z1 2Z2 2 - d X1X2Y1Y2 and N = f Z1 2Z2 2 + d X1X2Y1 Y2. By rewriting X1 Y2 + X2Y1 as (X1+ Y1)(X2 + Y2) - X1 Y1 - X2Y2, this costs 10M+ 1 S + 1 d + 1 e + 1 f where M denotes a field multiplication, S denotes a field squaring, and d, e, f denote respectively a multiplication by constants d, e, f. Also provided is a special doubling formula, a method, and a computer program (140).