Elliptic curves in Edwards form, known for their speed and efficiency, are highly promising for asymmetric cryptosystems. The CSIDH protocol is particularly notable for post-quantum cryptography. Recent studies classify these curves and demonstrate CSIDH's implementation on quadratic and twisted Edwards curves, highlighting their unique properties through graphical models like the wheel representation of point exponentiation. The model in the form of a graph of points of an elliptic curve in the form of Edwards was studied. The algorithm for the reconstruction of the series of points kP of all groups of points of the Edwards curve without the use of a group operation for 1/8 of the known points has been refined. The possibility of reconstructing the order of these points is also shown. post-quantum cryptography, elliptic curve, point exponentiation, exponentiation graph, point reconstruction, reconstruction pattern 1 † These authors contributed equally.
Elliptic curves in Edwards’s form [1], which have been studied and modernized by the authors of the work [2], today are the fastest and most promising in asymmetric cryptosystems. One of the promising protocols for postquantum cryptography is CSIDH [3]. In work [4] a new classification of these curves is proposed, and in works [5, 6] the implementation of the CSIDH algorithm on quadratic and twisted
and illustrated with examples. In works [7, 8] an analysis of the special properties of quadratic and twisted Edwards supersingular curves is carried out and a graphic model of the process of exponentiation of curve points in the form of a wheel is used. In [8], a method for finding all points of the scalar product kP of a point is proposed if a segment of 1/8 of all points is known. Additional studies of the method of reconstruction of the points of these curves make it possible to further simplify and speed up the finding of these points and their orders.
An elliptic curve in the generalized Edwards form is defined by the equation [4] , : +
= 1 + , { , } ∈ ∗, ≠ , ≠ 1.
In case ( ) = 1, ( ) = ( ) = 1 there is an isomorphism of the curve (1) with the quadratic Edwards curve [4]. The curve has a parameter , which is defined as a quadratic excess, in addition, and for these curves, it is usually accepted = 1 . According to the classification [4], the quadratic curve is described by the equation: : + = 1 + , ( ) = 1, ≠ 1. (1) (2) CPITS-II 2024: Workshop on Cybersecurity Providing in Information 1 −
+ 1 + 2( , ) =
− 1 −
2 1 +
The law of doubling the point ( , ), accordingly, has the form (3) (4) 1 √
Quadratic Edwards’s curves (2) have a noncyclic subgroup of the 4th order, which includes three points of the 2nd order and a neutral element of the group of points О. Two of these points are special and have an infinite second coordinate. Curves (2) also have two singular points of the
, = ± , ∞ at = 1.
± = ∞, ± at = 1.
When implementing crypto algorithms, it is necessary to know the order of the used points of the curve. The order of the point P is determined in the process of exponentiation of the point by multiplication by a scalar number ( = 1 … )
and construction of the exponentiation group () = {, 2, 3, … , , … , } the point if = О(1,0) , where the K-order of , and numbers , 2, … , form a group of curve points = {| = 1 … } [4].
Curve (2) with a minimum cofactor of 8 has an order = 8 ( is odd), while the maximum order of the point is equal 0000-0002-5145-2782 (S. Abramov); 0000-0002-9349-7946 (V. Sokolov); 0000-0002-8026-1475 (V. Abramov) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org to 4 . Let = ( , ), Ord = 4 . Then, for example, a subgroup 〈 〉 = {| = 1 … 4 } is cyclic and runs through all points kP where = 1 … 4 . At the same time, there are 4 basis points = , 2 = , 3 = − , 4 = = (1,0). It is convenient to represent the cyclic subgroup of the curve (2) in the form of a wheel of exponentiation points (Bessalov’s wheel) [4].
The exponentiation of curve points is carried out using expressions (3,4), which are quite complex, and therefore the creation of methods for simplifying and accelerating exponentiation is relevant for research [9–13]. In work [8], based on the interconnection of families of high-order points, the kP points of the Edwards curve are reconstructed without the use of group operations, reducing the number of point calculations to 1/8 of the order of the group.
This paper considers some features of the exponentiation process that can further simplify calculations.
Consider an example from work [14], which uses the Edwards quadratic curve (2) with parameters = 1, = 5 mod 23 = 2. At р = 23, it is supersingular and has an order = 24, = 3 . The curve has base points ± = (0, +1), = (−1,0), = (1,0), special points (9, ∞), (−9, ∞), (∞, 9), (∞, −9) and two families of 8 nonbasic points of high order in each (±5, ±10), (±10, ±5), (±6, ±11), (±11, ±6). Table 1 shows the coordinates of the points of all its subgroups of orders 4 = 12 and 2 = 6 .
A family of points of high order is eight points of a curve (±, +) , (±, ±) which lie on a plane х—у on one circle with a radius not equal to one (wheel of points). Fig. 1 shows an example of placing a family of points of high order in affine coordinates , . The family includes four points (±, ±) and four points where x and y coordinates are interchanged (±, ±) . For convenience, the first 4 points can be called the initial subfamily, and the last four points can be called swap points (swap subfamily). Each family is located symmetrically for both the -axis and the y-axis. We will call each family modulo the coordinates of the first point, which we will call the initial point.
Curve (2) of order = 24 at = 23 has four families
of non-basis points of order 3, 6, and 12. These points are
generators of cyclic exponentiation subgroups (rows). Table 1
shows these points and subgroups of their exponentiation.
The curve under consideration has the following families:
(
In Table 2, we can observe interesting features, for
example, all doubling points of all groups (column 2P) are
exclusively points of the family (
The points of the wheel show the scalar coefficients multiplied by the point is the generator of the group < > . The coordinates of the points of the group are located on the outside of the wheel, and the order of the corresponding points is on the inside. The difference from Fig. 1 is that the points of the curve in Bessalov’s wheel are in the order of their location in the exponentiation group and their number is equal to the order of the corresponding group. At the same time, the properties related to symmetry are similar. To construct each group of order K, it is necessary to carry out operations of multiplication by a scalar coefficient = 1 … [4]. has diametrical points and ∗ located at the ends of the wheel diameter: +
= ( , ) + (−1,0) = (− , − ) = ∗.
Vertical (mirror) symmetry is formed by points symmetrical about the vertical axis. These points are from the same family with the same y coordinate, and the x coordinate changes sign: these are points ( , ) and (− , ). similarly using the reverse (inverse) point at which the sign of the coordinate changes : − = ( , − ).
In Table 2, point families (
Other groups of this family can be presented in the form
of a transformed first wheel. The transformation consists of
the fact that at odd points (1 , 3 , … ) we invert the sign of
the coordinate, and at even points (2 , 4 , … ) is the
coordinate (Figs. 2b, 3b).
4. Wheel template of a cyclic group
The wheel in Fig. 2 shows the exponentiation of the points
(
As with the wheel, Fig. 5 presents the points of the
curve, the exponentiation factor k, and the order of the
points r. To construct the entire group, as it was said in [4],
it is enough to find the points of the first half-sector (1/8
part of all points of the wheel). Next, you should fill out the
template according to certain rules.
5. Example of constructing the
wheels of all cyclic groups of the
Edwards curve
Consider an example from work [7], this is an Edwards
curve of order
From the solution of the equation, we get a complete set of
curve points. In Table 3, the points are arranged in
ascending
order of the
coordinate. For ease of
consideration, we write the > 9 coordinate as = −
28 points in total, curve order 28. It is convenient to use
of order 4, it becomes clear that there is also point 2 of order
cyclic subgroups to find the order of points. Consider the
cyclic subgroup formed by the point (
–1
28
0
2
1
0
1
The subgroup has order 28 and includes all points of the
curve. The table has base points with a known order: points
7 and 21 order 4, 14 order 2, and neutral point (1,0).
Non-base points can have an order of 28, 14, and 7, you can
find their orders using a minimum number of calculations.
There are 28 points in the table and it ends with the point
(1, 0), so the order of the generator point (
For example, for the third point 3 we have to 3 then = × / = 28 × /3 = 2 × 2 × 7 × /3. There are no common factors and the integer s can be at = = 3, then the order of this point is = 28. For point 6 we have = 6 = 2 × 3 then = 2 × 2 × 7 × /2 × 3, we reduce by a common factor of 2 and get = 14.
Applying this rule further, we will get a suitable template for each order of the group, for example, the following template for the point of order 28. Here the wheel is shown in the form of a table, the cells of the table are more convenient for filling with data (Fig. 6). 6. Rules for reconstruction of points Now in this template, you need to place the points that depend on the first point of 1 . Rules and formulas to simplify this process are developed in [4]:
For a curve of order , there can be subgroups of order | , and the first point 4 of the order , if any, will appear on the step ( /4) × Р.
Algorithm for constructing the wheel of the cyclic subgroup of the point P of the Nth order curve.
1. 2.
Using the expressions (3,4), we find the points 2 , 4 , 8 , … , 2 , etc.
If the last dot appeared from a family that was already significant, we moved to the second sector of the wheel. And point is between the last k and penultimate ( − 1) points < ( | ) < − 1. Hence, the order of the point is determined. Choose the appropriate wheel template and fill it with points accordingly [4].
Let’s consider some properties of the wheel.
Examining the points of various curves, it is possible to identify some regularities. Yes, points from the same family are not repeated in each sector.
If the group has points of orders 2 and 4, then the order
of this group is a maximum of 4 . Then, on the border of
the half-sector, we get points from swap families. For
example, in groups (3,5) (Table 5), the boundary of the
semi-sector passes between points 3 and 4, and these points
of families (
If the group does not have a point of order 4, then the
order of this group is 2 . For example, in groups (5,3), the
border of sectors 1 and 2 passes between points 3 and 4
(Table 6), where the first mirror point from the families
appears (
If there are no points of order 2 and 4, then the order of
this group is . For example, in groups (
Points of the same family are not repeated within the sector. 8 coordinates of the points are shown on the green background, the scalar exponentiation factor is on the yellow, and the orders of the points are on the gray Рk. All the properties described above are present. There is a neutral point (1,0), two special points of the 4th order (∞, ±35), and point 2 of the order. There is an opportunity for 1/8 of all points to reconstruct other points. Based on the obtained data, it is possible to reconstruct the rest of all groups of this family without even knowing 1/8 of its points.
For any group ×
of order # ( , ) regardless of the coordinates of the points, the orders are arranged in the same way. Of the order factors of the group # ( , ) = × × … ×
remove the elements that coincide with the multipliers of the scalar = × × …, and the remaining factors give the value of the order of the points. For example, in our example with # ( , ) = 40 = 2 × 2 × 2 ×
= 2 × 2 × 2 have (8 ) = 2 × 2 × 2 × 5 = 5. And for a symmetrical point 12 = 2 × 2 × 3 have 2 × 2 × 2 × 5 = 10. The orders of the remaining symmetric points coincide.
Consider one of the groups of maximal order, let its reconstruct the exponentiation points and their orders, for
Even points are taken from the initial families and odd ones from the swap families.
Coordinate signs are arranged as follows: at the second point, the sign of the x coordinate is inverted, at the 3rd point, both coordinates are inverted, at the 4th point, the coordinate is inverted, at the 5th point, the signs do not change, so the process is repeated until the sector is filled [15].
The considered properties make it possible to find all kP points of all groups of the curve by the value of 1/8 of the points of only one group (wheel). With the known order of the group, each exponentiation coefficient k corresponds to its order of the point, which does not depend on the coordinates of the point, but only on the order of the group and . This can be used to create a template from which to example, when modeling algorithms. properties of Edwards curves.
In the future, we plan to continue to explore the