Algorithms for Base Point Generation on an Edwards Curve with the Use of Point Divisibility Criteria
- PDF / 132,001 Bytes
- 10 Pages / 594 x 792 pts Page_size
- 118 Downloads / 181 Views
ALGORITHMS FOR BASE POINT GENERATION ON AN EDWARDS CURVE WITH THE USE OF POINT DIVISIBILITY CRITERIA L. V. Kovalchuk,1† A. V. Bessalov,1‡ and O. Y. Bespalov1††
UDC 681.3.06
Abstract. New criteria for Edwards curve point divisibility by 2, 4, and other natural numbers are obtained and proved. Using these results, new algorithms are constructed for extracting the root of arbitrary degree in the Edwards curve group and also new algorithms are obtained for generating the base point of such a curve that are proven to have some advantages. Keywords: Edwards curve, point divisibility, base point generation.
INTRODUCTION At present, elliptic curves in the Edwards form are most promising as applied to asymmetric cryptosystems. Their properties [1, 2] such as maximum execution speed, universality of the addition law, and also the possibility of representation of the neutral element in affine coordinates are especially important in constructing cryptosystems. The symmetry of the equation of an Edwards curve with respect to both coordinates determines useful properties of such curves. If Edwards curves are studied up to isomorphism, then it suffices to use only one parameter d instead of two usual parameters a and b of the classical curve in the canonical Weierstrass form. In [3], the class of Edwards curves called twisted Edwards curves is generalized and extended by the addition of a new parameter a. An investigation of new properties of this class of twisted Edwards curves is presented in [4] where alternative formulas for the law of addition of points of a curve are found, their features are determined, a method for computing coordinates of the sum of points in extended projective coordinates is proposed, and also the number of operations in adding different points is reduced from 10M + 2S + 2D to 9M + 1D (M is multiplication in a field, S is squaring, and D is the multiplication by the curve parameter), which has increased the speed of the operation of addition of points by a factor of approximately 1.36. In [5], sufficient and necessary conditions are given for the isomorphism between an elliptic curve specified in canonical form and some Edwards curve. Based on these criteria, the exact number of Edwards curves over an arbitrary finite field is found; this number depends on the field characteristic. In this article, criteria for Edwards curve point divisibility by an arbitrary natural number are formulated and proved and, with the use of them, algorithms are developed for extracting an arbitrary nth root of a curve point or, in terms of an additive group, algorithms for finding the point of division by an arbitrary natural number. Based on these criteria, new algorithms are created for computing coordinates of the base point of a curve (or the generator of the subgroup of prime order n in the group of points of the curve) and also a detailed comparative analysis of new and classical algorithms for computing base points of curves is performed and the execution speed of the algorithms proposed below is shown to be larg
Data Loading...
