This work is dedicated to studying the cryptographic properties of elliptic curves in Edwards form (ECEF) and to the subsequent use of those in the asymmetric cryptosystems in order to increase their speed. The main focus is on the elliptic curves in the Edwards form over fields modulo p, where p is prime. An improved classification of elliptic curves in generalized Edwards form is presented, which splits the set of these curves into three non-intersecting classes. New analytical results about properties of newly introduced ECEF classes are obtained. The existence conditions are determined and a cardinality are evaluated for elliptic curves in Edwards form with the minimum cofactor that can be used in the cryptographic algorithms.
Analytical estimates of the point exponentiation efficiency on the elliptic curves in Edwards form and on curves in Weierstrass form are obtained. Comparative performance analysis are provided in terms of the number of scalar products. It is proved that the point exponentiation in complete and twisted ECEF classes is many times faster than the exponentiation of a point on the Weierstrass curves.
Analysis of published works has shown that some inaccuracies arise in the ECEF properties describing because of the incorrect classification of curves proposed by D. Bernstein and co-authors. However, known results about the properties of the Edwards curves have not been sufficiently mathematically researched for the purpose to find the fastest and easiest-to-implement curves for use in cryptosystems.
Based on the new proposed classification, conditions were obtained for the existence of ECEF with a minimum order coefficient of the curve, which allowed to calculate the number of curves that can be used to find crypto-resistant ECEF for use in the asymmetric cryptosystems. As a result of the calculations, it was obtained that over a prime finite field there are about 3/8 of the total number of elliptic curves in the generalized Edwards form which have order 4n, where n is prime, which can be used to find cryptographically strong curves for use in the asymmetric cryptosystems.
A comparative analysis of the point exponentiation on the Edwards curves and the Weierstrass curves was performed, using the method of calculating the number of operations for the scalar product of the curve points, which allowed to estimate analytically the efficiency of point exponentiation on different curves. The results of the analysis show that the point exponentiation of classes of complete and twisted ECEF (by new classification) is 1.6 times faster than the point exponentiation on the Weierstrass curves used in the modern digital signature algorithms. In particular, the Edwards curves win with the ternary representation of k.
A new method for determining the order of random points of the ECEF has been developed on the base of three theorems about properties of points and curve parameters, which makes it possible to simplify the finding of a prime order point by testing the coordinate of a random point. A new algorithm for finding a cryptosystem generator using the proposed method of determining the order of the random points is formulated, which allows to find the cryptosystem generator on the Edwards curves in О(logn) times faster than on the Weierstrass curves (here n is the order of the group of points of the elliptic curve).
Using the new algorithms of cryptosystem generator search and the method of minimization of complexity of operations, parameters of 25 twisted and 39 complete cryptographically strong elliptic curves in Edwards form over the prime fields with a modulo length p = 192, 224, 256, 384 і 521 bit (recommended by standards FIPS-186-2-2000, FIPS-186-4-2013 and ISO/IECCD 15946) are found, that allows to use them in asymmetric cryptoalgorithms.
A new, simpler and faster than known, method of finding the ECEF order and reconstructions of all points of the complete Edwards curve is proposed. It can be used for teaching disciplines related to elliptic mathematics.
The dissertation consists of an introduction, four sections, conclusions, a list of sources used, five appendices.
The introduction substantiates the relevance of the topic of the dissertation, formulates the purpose and objectives of the research, scientific novelty and practical significance of the obtained results. The information about implementation of work results, their validation, publications and personal contribution of the applicant are given.
