A multifunctional cryptosystem RCNIE on isogenies of non-supersingular Edwards curves is proposed, which solves the problems of Diffie-Hellman secret sharing, digital signature, and public key encryption. The problems of choosing the parameters of non-supersingular Edwards curves forming pairs of quadratic twist with orders p + 1 ± t ≡ 0mod8 over a prime field Fp are considered. Encryption algorithms with mutual authentication of Alice and Bob based on the sharing of their secrets are given, while the length of the key and the size of the digital signature are minimally short and do not exceed the size of the field Fp element. An illustration is given of the operation of the cryptosystem model on 4 degrees of isogenies {3,5,7,37} over the field F863 for a pair of quadratic twist curves with orders 840 and 888. It is shown that for non-supersingular curves there are main and dual cryptosystems, each of which has also an isomorphic cryptosystem. This allows you to perform parallel computing and speed up algorithms. A comparative evaluation of the arithmetic and properties of CSIDH and RCNIE is given. It is noted that we have not found strong arguments for the slow implementation of the CRS scheme in comparison with CSIDH. Taking into account the peculiarities of each of them, both schemes are certainly promising. Curve in generalized Edwards form, complete curve, twisted curve, quadratic curve, non-supersingular curve, curve order, point order, isomorphism, isogeny.
transitions, associated arithmetic [5–7].
The presentation [1] of the authors of the PQC
algorithm names the
CRS scheme (Couveignes-Rostovtsev-Stolbunov) known since the beginning of the 21st century as the first proposed scheme on isogenies of nonsupersingular elliptic curves [2–4]. Its remarkable properties are the commutativity of isogenic the flexibility, and simplicity with the use of prime field
Further, the appearance of the PQC SIDH (2011) and CSIDH (2018) algorithms already uses the technology of supersingular elliptic curves over the fields 2 and , respectively, which is justified by the relatively faster implementation of the algorithms [8]. In [1] it is noted that CRS encryption is unacceptably slow and can take several minutes at a security level of 128 bits.
Being engaged in recent years in the problems of modeling and modifying CSIDH [9–12], we became interested in the reasons for the above fact, which is not substantiated by anything. One of the goals of this paper is to try to compare the difficulties that hinder the execution of the CSIDH algorithm and our simple CRS-like model on non-cyclic curves.
The main difference from CRS [2] in this work is, as in CSIDH, the use of pairs of quadratic twist curves, which uses the property of isogeny bidirectionality. It should be noted that the set of non-supersingular elliptic curves is wider than the corresponding set of supersingular curves with a rough estimate by a factor of √ , and, as a result, contains many potentialities. We managed to find some of them, which are discussed in this article.
In [1] and early implementations of CSIDH, supersingular curves in the Montgomery form [1] were used, but soon in [13] using the (W: Z)coordinates [14] of curves in the Edwards form, a gain of 20% was obtained in comparison with [1] in the speed of calculations. Further, generalizing the formulas for calculating isogenies for Edwards curves [15] to twisted Edwards curves in [9], we illustrated the implementation of CSIDH models on non-cyclic quadratic and twisted Edwards curves [10–12]. The last curves were first defined in the fundamental work [16], but with unfortunate terminology, so we use the classification of curves in the Edwards form [17, 18]. An analysis of the properties of supersingular Edwards curves of all classes is given in [19, 20]. In this paper, we use non-supersingular Edwards curves of two classes with the same constraint p ≡ 3mod4. This allows one to express the equations of curves of a quadratic twist pair using additively inverse parameters.
A well-known problem of the CSIDH algorithm is the vulnerability to a side channel attack based on the measurement of the computation time of the chain of isogenies of each degree, which is proportional to the secret exponent е of the key. In a large number of articles [21–24], the solution to this problem is proposed by increasing the exponents by fictitious ones to a known maximum (Constant time CSIDH). It is clear that such redundancy significantly reduces the speed of the algorithm. In [11], we proposed randomization of the CSIDH algorithm as a method to counter side-channel attacks. It is also used in this article.
The key encapsulation algorithms [12, 25–27] are now preferred to the classic Diffie-Hellman secret sharing scheme. Such an algorithm can also be constructed using the CRS scheme.
The order of an elliptic curve E over a prime field is defined as # = + 1 − , where t is the trace of the Frobenius endomorphism equation. For a quadratic twist curve , respectively, this order # = + 1 + is symmetric concerning the mean value + 1. For a supersingular curve, = 0 and the orders of both curves + 1 coincide, and the sets of isogeny degrees are the same, but the signs of the exponents of the degrees are inverse to each other, as in CSIDH. In the case of non-supersingular curves, the orders of quadratic twist pairs differ by 2t, then there are different degrees of isogenies on curves of two classes related as quadratic twist pairs with different orders. This is the main specificity of non-supersingular curves. The exponents of the isogeny degrees of these two curves, as in CSIDH, have opposite signs. The alternation of degrees of isogenies according to the randomization method is random, and the simplicity of transitions of the chain of isogenies from one class of curves to another is achieved by the fact that their parameters are additively inverse: ( , ) ↔ (− , − ).
In Section 1, a brief review of the properties of quadratic and twisted Edwards curves [18] is given, and methods and options for choosing the parameters of a pair of these curves as a pair of quadratic twists are proposed. Section 2 presents algorithms of the Randomized Commutative Nonsupersingular Isogeny Encryption (RCNIE) scheme on quadratic and twisted nonsupersingular Edwards curves (NECs). In Section 3 an illustration of the computation of isogenic chains in the corresponding algorithms on a model with degrees {3,5,7,37} over the field 863 is given. Here we discuss the existence of isomorphic and dual cryptosystems on isogenies of non-supersingular curves, expanding their possibilities and applications. Finally, Section 4 compares the CSIDH algorithm and the RCNIE scheme.
The elliptic curve , the equation in the
generalized Edwards form [17] with two
parameters a and d is written as
, : 2 + 2 = 1 + 2 2,
, ∈ ∗, ≠ , ≠ 1.
(
For the first time, such a curve was proposed in the fundamental work [12] with the coefficient a at 2 and the term “twisted Edwards curve.” For the correct division of curves in the Edwards form into non-intersecting classes, we use our classification [17].
If the quadratic character is ( ) = −1, then
curve (
The twisted Edwards curve is defined in [17]
as a special case of the curve (
In [16], curve (
Theorem 2 [10]. For a curve ,
(
Edwards form 2 2 defined over a prime field , there exists 2 + 2 = 1 + a unique quadratic twist curve ⃗ , parameters ̄ = , ̄ = , ∈ ∗.
2
Its proof is given in [10]. From it, in particular,
it follows that in the class of complete Edwards
curves, the quadratic twist curve = −1 lies
inside this class, while for the quadratic curve (
We define a quadratic and twisted Edwards curve as a pair of quadratic twists with parameters (
) = 1, ̅ = , ̅= , ( ) = −1. Since we accept the condition ≡ 3 mod4, we can accept = −1, ̅ = − = −1, ̅= − , where = 1,
are the parameters of the quadratic
curve (
↔ −1,− . Then the twisted Edwards
curve equation (
The orders of quadratic (
= −1 after which all curves (
It is interesting that in equation (
This means that using the multiplicative inversion of the coordinates of eight known points of the curve P = (±x, ±y), Q = (±y, ±x) it is easy to calculate the unique parameter d of the curve. This is useful in cryptanalysis and should be taken into account in algorithms to protect against such an
By analogy with CSIDH, it is easy to form the general parameters of a CRS-like cryptosystem on isogenies of Non-supersingular Edwards Curves (NECs). Let 0 = ∏
=1 and N = 8 0 be the order of a quadratic supersingular Edwards curve over a field with modulus 0 = − 1. By setting the values of the Frobenius trace = ±8 , 1,2,3, …
we determine the sum 0 ± 8
equal to the prime number p. Then over the field
there exists a quadratic NEC (
= 8 1.
Example 1. For a set of isogeny degrees { } = {3,5,7}, 0 = 105, N = 840, 0 = 839, for m = 3 we get a prime number p = 839 + 24 = 863. Then the orders of the curves of the quadratic twist pair are #Ed =840 = 8 ∙ 3 ∙ 5 ∙ 7 and # −1,− =
+ 48 = 888 = 8 ∙ 3 ∙ 37, 1 = 111.
Another method is possible, not always lead to success. You can set two sets of degrees that differ by one or more elements and calculate the arithmetic mean of the products of the elements of these sets u. If 8u−1= p is a prime number, it is the desired modulus of p.
Example 2. Let { } = {5,7}, 0 = 35, 8 0 = 380. In the second set { } = {3,11}, 1 = 33, 8 1 = 364. The mean of orders is 8u = 372, but 372 – 1 = 371 is not a prime number.
However, 16 − 1 = 743 is a prime number, and with
attack.
(
Example 3.
Let { } = {3,5,7,11}, 0 = 1155, 8 0 = 9240. In the second set { } {3,5,7,13} we change element 11 of the first sets by 13 and calculate 1 = 1365, 8 1 = 10920. The average value of the orders of the two curves = is 10080 = + 1, since p = 10079 is a prime number. Here the trace of the Frobenius equation is = 840, and the orders of the curves of the quadratic twist pair are #Ed = 9240, # −1,− = 10920. Note that for p = 9239, it is possible to build CSIDH, for p = 10079 only CRS, and the number 10919 is not prime.
An approach can be considered rational if the sets of isogenies degrees of pair curves of quadratic twist intersect as much as possible. For example, in the second curve with the preservation of all lower degrees, the highest degree
1 can be replaced by a higher one max2, then the orders of the two curves differ by a factor max1/ max2. This difference cannot exceed boundaries.
the allowable
limits 2√ differ for large p with an estimate of 1 − 2 .
Meanwhile, for CSIDH, for example, the ratio of the maximum orders max1/ max2 differs little from 0.99, which is less than 1 on about 1%. In the alternative case, for non-intersecting two sets of degrees, there are also no such sets that would give practically equal products. It is more pragmatic to specify the first non-supersingular curve with minimal isogeny degrees, followed by an appropriate factorization of the order of the twist curve (Example 1). It will only add new degrees of isogenies with a smaller number of them. The number of isogenies degrees in both curves can be made approximately equal by selecting from a table of primes with alternating numbers for the first and second curves (as in
2). The problem of choosing the parameters of quadratic twist pairs of nonsupersingular curves still needs to be studied.
NEC as a pair of quadratic twists have different orders and different structures. Except for the two points (0, ±1), all their points are different. Both curves are non-cyclic concerning points of even order (contain 3 points of the 2nd order each, two of √ which are singular points 1,2 = (±√ [17]). Quadratic NEC, in addition, contains 2 singular points of the 4th order ± 1 = (∞, ± 1 ).
The presence of 3 points of the 2nd order limits the number 8 to the minimum even cofactor of the order
Ord E = 8n (n is odd) of twisted and quadratic Edwards curves [17]. The maximum order of the points of these curves is Ord E/2. Points of even orders mustn't be involved in the calculation of isogenies of odd degrees (the first multiplication by four of a random point P gives a random point R of odd order n or a divisor of n).
The choice of two classes of non-cyclic NECs for cryptosystems on isogenies is justified by their advantages over complete NECs:
1. The number of all quadratic and twisted Edwards curves ( − 3) is twice the number −3 of all complete corresponding proportion is also valid for the number of isogenic NECs and, therefore, the 2 the security of the cryptosystem.
2. The transition to the curve of quadratic twist ↔ −1,−
does not require the laborious inversion of the parameter ↔ −1, which is necessary for a complete NEC.
Along with isogenic curves (with different Jinvariants), there are isomorphic curves with equal J-invariants, which are defined [16, 28] ( , ) = ( − ) ≠ 0.
16( 2 + 2 + 14 )
3
( − )4
,
(
parameter, in particular, recognizes isomorphic curves with different values of the parameter d. As a result of calculations of chains of isogenies, one usually makes the change → ( ). This parameter is also used in the ElGamal encryption scheme. For quadratic and twisted
curves ( ) = ( −1), i.e. inverting the parameters d gives an isomorphic curve.
on Quadratic and Twisted Edwards
Instead of supersingular ones, we start here
with non-supersingular Edwards curves (NEСs)
of two classes (
In all algorithms, the CGA encryption function ( ) encrypts the secret key using the mapping = [ 1 1, 2 2, . . , = ( 1, 2, . . , ) ] and the starting curve 0 into an isogenic curve ′ = 0 ∗ , whose parameter is taken either as the corresponding public key or as a new short secret key. The parameters of the quadratic NEC # (0)= + 1 − = 2
∏ =1 , field modulus ≡ − 1 ≥ 3 and the prime
(
public key А
using the secret key =
( 1, 2, . . . ) on the isogenies of curves (
Input: ∈ , ( ) = 1 and a secret key = ( 1, 2, . . . ). , where , :
2 + 2 = 1 + А,В 2 2, Output: such that [ 1 1, 2 2, . . . ] ∗ = Let 0 = { | > 0} , 1 = { | < 0}, 0 = 1. 2.
∏ ∈ 0 ,
, 1 = ∏ ∈ 1 , While some ≠ 0 do 3. Sample a random ∈ , A nonzero value of by a factor of √ expands the set of curves and offers interesting new applications.
In contrast to the CRS scheme [2] on curves in the Weierstrass form with two parameters, which does not use pairs of quadratic twist, we build speeding up our algorithms are the rejection of the very laborious calculation of the isogenic function ( ) of point and randomization of algorithms [10].
In this paper, we propose a PQC RCNIE scheme. It is distinguished from the known ones by the existence of four parallel cryptosystems (with the addition of dual and two isomorphic ones) and, most importantly, multi-functionality.
The PQC CSIDH [1] algorithm is based on the CGA (class group action) encryption function over a prime field . The CGA function defines an isogenic mapping of a supersingular elliptic curve E of order #E = p + 1 into a curve ′ = ∗ degrees of isogenies and are isogeny exponents (number of isogenic transitions). The sign of the exponent is > 0 for the original curve, and < 0 for the quadratic twist curve. The mapping is commutative and is equally valid for all elliptic curves over the field regardless of their order. exponent
{ } exponents [ ]*[
A pair of non-supersingular quadratic twist curves have different orders and different sets of degrees { } and { } , which intersect. For the intersection { } ∩} { } , as in CSIDH, each l-isogeny has both signs and then may partially − ] = 1. This means that chains of lisogenies of different signs are built in reverse order and cancel each other out. Therefore, the keys in CSIDH give for each degree an of only one sign.
For
nonsupersingular curves, the union of sets { }∪
is constructed, and the signs
are determined by whether the
isogeny belongs to one of the curves of the
quadratic twist pair. One should strive for the
equiprobable use of both curves, which is true for
sets { }and { } of equal power. Since isogeny
curves of corresponding degrees exist in the
classes of curves (
5. Else a −1, 1 2 2 If (( 2 − 1)/( 2 − 1) = 1, : 2 − 2 = 1 − 6. Compute -coordinate of the point = 2 2, ( , ) ∈ , 7. Compute 13. Skip in and set ← ( / ) If = This algorithm has important differences from the original algorithm 2 [1], which are discussed in [11]. In addition to modifications related to the randomization method of the CSIDH algorithm, here we refuse the redundant isogenic function φ(R) of a random point R, which radically speeds up the algorithm.
The idea of randomization is that for any
random value of the variable x (xy ≠ 0, ), the
point P = (x,y) with a known parameter d always
belongs to one of the two curves (
At the beginning of Algorithm 1, two subsets , = 0,1, with degree numbers , are formed, together with two factors 0 and 1 of the number = 0 1: the index λ=0 ( > 0) corresponds to the choice of a quadratic NEC, and λ = 1 is twisted NEC ( < 0). Since the order of the curve is # = 8 0, then in line 7 of the algorithm for the curve the point
= 4 1 of odd order 0 is calculated, and the curve −1,− the point = 4 0 minimizes of odd the order 1is
calculated. cost of the next
This scalar multiplication, which determines the point Q of the isogeny kernel of the degree Further, in line 10 of the algorithm, by doubling points of the kernel <Q> are calculated. the points, = ( − 1)/2 x-coordinates of the (line 9).
In line 7 of Algorithm 1, double doubling the random point P immediately allows you to get rid of points of an even order (including special points of the 2nd and 4th order) and then the calculation of scalar multiplications in subgroups of points of an odd order of the curve. Their task of x-coordinates of the kernel is to find ( −1)
2
according to the formula [15]
points <Q> of prime order . As a result,
′ = 8, = ∏ =1 , s = (
− 1)/2
(
Abelian
groups, and not isogenic functions ( ) of a random point . The laborintensive calculations of the latter in [1] are redundant. 3.1.
compute ∏ modulus the elliptic curve .
1. Choice of parameters. For odd primes , =1 , choose an appropriate field
= 2
∏ =1 − 1, ≥ 3 and start 2. Calculation of public keys. Alice and Bob use secret keys in the form of vectors ,В = ( 1, 2, . . , ) construct isogenic maps ,В = [ 1 1, 2 2, . . , ] and calculate the isogenic curves ,В = ,В ∗ 0 as their public keys. These curves are determined by their parameters up to isomorphism.
3. Key exchange. Here the protocol is similar to item 2 with the replacement 0 → for Alice and 0 → for Bob. Knowing Bob's public key, Alice calculates = ∗ = ∗ ∗ 0.
Similar actions Bob gives the result = ∗ ∗ 0 which coincides with the first one
due to the commutativity of the group operation.
The
J-invariant of the
curve = ∗ В ( ВА) is taken as a shared secret [1]. 3.2.
The tasks of the digital signature are to authenticate the sender of message M and to verify the integrity of the transmitted message by the recipient. Alice usually uses her private key for this, and Bob uses her public key for verification. In the previous secret-sharing problem, both of these functions are performed: Alice encrypts Bob's public key
with the secret key , and computes the shared secret В . Bob uses Alice's public key А and his secret В, to calculate the same curve В. The fact that В = В that the task of authenticating Alice by Bob has means been completed.
When checking, it remains for Bob to make sure that together with the equality В = В for the sent M and received M' messages, the hash codes are identical: H(M') = H(M). Both qualities can be easily combined by concatenation into one with the secret of the first of them preserved. The most secure from a quantum computer for this is hashing the combined equalities above. These symmetric procedures are included in the digital signature algorithm below.
Based on each other’s public keys and В and their private keys ,В = ( 1, 2, . . , ) Alice and Bob perform calculations of the previous Diffie-Hellman secret-sharing scheme and find curves А=
= . Next, Alice respectively forms, and Bob verifies the digital signature DS: A. DS formation 1. Calculation h = H(M) < p. 2. Calculation J( ) = J( А). 3. Calculation DS =H[J(κ)|| h] < p. 4. Dispatch (M, DS)→ B.
B. DS Verification 1. Calculation h' = H(M'). 2. Calculation J( ) = J( ). 3. Calculation 4. Checking
′ = H[J( )|| ℎ′] < . ′ =
. In the case of ′ ≠ , the signature is incorrect.
It is a non-standard signature in the sense that in the asymmetric scheme, it is generated by Alice's private key and verified by Bob with her public key, and Bob's corresponding keys are not required. This is because a non-interactive DiffieHellman scheme was adopted as a basis, equalizing the conditions for Alice and Bob: both parties use their secret keys and the public keys of the other party to form a shared secret. Such conditions mean that they work in the scheme of mutual trust of symmetric cryptography, although on the technology of asymmetric cryptography. Perhaps this is permissible since Bob can write to Alice with the same rights, and she is obliged to believe him. To do this, they created a shared secret. The main thing is that a multifunctional cryptosystem works on this basis.
This original signature does not exceed the size of a prime field module and is rather concise. The signature algorithm is closer to RSA and half as long as the ElGamal signature. Here, only hashing and field operations are performed on both sides, with element inversions as the most complex operations. The algorithm can equally rely on CSIDH. The level of quantum security of finding the secret curve in the Diffie-Hellman secret sharing problem is estimated as 4√ . Calculations in the procedures for generating and verifying a digital signature have the maximal security level for a quantum computer. 3.3.
This asymmetric cryptography algorithm was proposed in [2] without using quadratic twist curves. Interestingly, it is also based on a secretsharing scheme. In the staging part, of the public keys, only the recipient's key is—the В curve. Alice, on the other hand, calculates her public key , in the encryption process and transmits each session to Bob along with the ciphertext. In essence, this means that she uses a one-time secret ,, which forms her one-time public key ,. The combination of Alice's one-time keys ,, ,, and Bob’s long-term keys ,, , allows both parties to compute the one-time shared secret , = В, It is used by Alice to encrypt the short message
, and by Bob to decrypt it. We describe the algorithm from [2] with the notations adopted here. • • • •
isogenies.
General system parameters: is a prime field. • , = 1,2, . . , are isogeny degrees. is integers m ≤ ≤m-exponents of m is the boundary value of the exponent. • 0 is starting the elliptic curve and its equation. • В is Bob’s public key.
is plain text. and
generating 3. Calculation of the shared Diffie-Hellman secret 4. Calculation of the J-invariant of the curve ,: 5. Calculation of the ciphertext S = (M⋅ ) mod p. 6. Sending ( ,, ) to Bob.
B. Decryption 1. Based on the secret key В, = ( 1, 2, . . , ) function form = [ 1 1 , 2 2, . . , ].
2. Calculation of the shared Diffie-Hellman secret В, = , ∗
= . = (
,). 3. Calculation of the J-invariant of the curve ,: 4. Calculation of the plain text M = (S/ ) mod p.
The use of one-time secrets in such a scheme makes it more secure than a non-interactive
All three of the above algorithms solve the main problems of asymmetric cryptography. The last two algorithms include the first one, which becomes the base one. As a result, we can state that in this paper we propose a multifunctional cryptosystem PQC RCNIE on isogenies of nonsupersingular evaluations of its properties are discussed in the next section.
As in the works [2, 29, 30], whose authors concluded the theoretical provisions of
a cryptosystem on isogenies of elliptic curves, resistant to quantum attacks, with examples of encryption of messages on odd
degrees of isogenies, in our works [9–12] we use modeling as a way to easily illustrate the properties of algorithms. Understanding these properties opens the way for something new and better. Sometimes the new is the well-forgotten old, as is the case with curves in the Edwards form.
Based on the data of Example 1 of Section 1,
we obtain four degrees of isogenies { } =
{3,5,7,37}, the first three of which are factors of
order 840 of the quadratic curve (
< 0. Here degree 3 is bidirectional (allows both signs), and degrees 5 and 7 ( > 0) and 37 ( < 0) are unidirectional. Below we discuss these features of the
isogenies of nonsupersingular curves.
With a relatively small field modulus p = 863,
it is not difficult to find estimated √ of the
parameters d of all curves (
Since they are squares, then a full enumeration modulo p of all с = 2,3, … ,431, and
= 2 gives
the set of all 62 values of the parameters d of the
NEC (
For example, ↔ −1 and the same J-invariant
169−1 = 623, (169) =
(623) = 826. Then there are 31 non-isomorphic
curves (
Isogenies of all degrees have a prime period An array of values of 62 quadratic and twisted NEC parameters d at p = 863, #E = 840, #Et=888 (t = 24) 169 19 71 300 688 400 779 616 113 843 729 111 618 311 339 161 308 444 858 623 818 253 302 673 706 210 116 192 725 281 436 705 486 589 181 309 503 318 75 43 32 852 684 665 573 231 551 840 472 728 307
The number above arrow 1 means one step of
the 3-isogeny chain of the quadratic NEC curve
(
(
On the other hand, for bidirectional l-isogenies
of a pair of quadratic twist curves with exponents
±1, we have
(
(
In other words, to multiplicatively reverse one
step of an isogenic chain, it is required in the
general case to find a chain of period π (see (
The above case takes place in CSIDH, which
distinguishes it favorably from CRS. But in
CSIDH, the isogeny of each degree in the keys is
used as a unidirectional exponent, which is
understandable, since different signs of the
exponent only neutralize each other [31]. Property
(
Characteristically, for the starting curve
(0) = 169, the sequence ( ) (
Next, we will see that the same operating
parameters contain all the calculations in the
secret sharing scheme. If you invert the starting
curve 169−1 → 623, you do not need to build
new isogenic chains, it is enough to invert the
results. In this case, the other half of the
parameters of Table 1, not included in (
If the starting curve is given and does not change all parameters ( ) of isogenic chains are unique and there is no need to pass to the J-invariant of the resulting curve. An isomorphic cryptosystem can solve other problems in parallel, which doubles the performance of such a system.
Further, we will see that in addition to the isomorphic cryptosystem, there is also a dual cryptosystem, which also has its isomorphic one.
Overall, there is the potential to quadruple the performance of the RCNIE scheme.
In our model with isogenies of degrees
{3,5,7,37}, to equalize the probabilities of
choosing the curves of a pair of quadratic torsion,
we will take all the degrees to be unidirectional,
then in the secret keys the degrees {5,7} will be
assigned to the quadratic curve ( > 0), and the
degree {3,37} to twisted ( < 0). Let’s take the
secret keys of Alice = (
Alice’s public key with a random choice of
curves and degrees is defined as
(
The previous problem is solved at the precomputation stage and also performs mutual authentication of Alice and Bob. They calculated the shared secret key =161.
In conclusion of this section, we note that the example of the implementation of the encryption algorithm here is redundant since with other conditions it is given by the CRS co-authors in [2]. We will only comment on this example.
In [2], an example was constructed for 6 unidirectional isogenies of degrees {3,5,7,11,13,17} with their product 255255 over a prime field with modulus p = 2038074743 and the order #E = 2038078635 of the curve in the Weierstrass form with two parameters A and B. There is a typo in the last number in the article since it is not divisible by all degrees except 3 and 5. It is not clear why the model required a redundancy of approximately 104 times for the field modulus and curve order. In the corresponding number of times, the calculations become more complicated, and both parameters A and B of the curve increase (these are ten-digit decimal numbers instead of the necessary sixdigit ones). In addition, two Weierstrass curve parameters can now be easily replaced with one Edwards curve parameter d and double the computational speed. Perhaps, here and in other algorithms [29, 30, 33], the reasons for the slowness of the CRS scheme are associated with excessive redundancy of parameters, which can be eliminated. But this is not a reason to consider the CRS scheme unacceptable. We will return in the next section to a discussion of this issue.
In [11], we proposed a randomized CSIDH
model with bidirectional isogenies of degrees
{3.5.7} on curves (
It can already be argued that with the transition from CSIDH to a non-supersingular curve, one or more new degrees of isogenies always appear (in our case, = 37). Their insignificant disadvantage is unidirectional isogenies, and for large cryptosystems, it is practically the inability to inverse the isogenic chains and such tasks should be avoided in algorithms. Here we see mutual advantages and disadvantages.
If we now turn to problems related to speed, then we have not found any new reasons inhibiting the execution of the algorithm. Usually, when choosing a random point P at the beginning of each step in calculating the isogenic curve, the point P may be unsuccessful with a certain degree . This means that the order of point P does not contain a factor . The probability of such an event −1the more, the lower the degree and reaches the maximum value of 1/3. We do not recommend taking too small degrees in cryptosystems, they are the most problematic. In the described case, randomization allows random transitions to other degrees of isogenies. From our experience, unsuccessful random points arise with the same frequency, regardless of whether the curve is supersingular or not. As noted in the previous section, the slowness of the implementation of the calculations of the isogenies is most likely associated with the exorbitant redundancy of the characterization of the prime field and the curve order in the models used. The reason for this redundancy [2] remains unclear.
For NEC, there is a unique ability to build not only a pair of quadratic twists with the orders p + 1 ± t but also inside each class to find a pair of curves with the same order as in a quadratic twist curve. We will call the corresponding curves dual. Their existence allows you to replace quadratic curves with twisted ones and vice versa. For example, the degree of isogenies of l = 37 in our model belongs to the twisted curves −1,− of power 64 and order 888. Over the field 863, there is a curve of order 888 with a minimum parameter d = 6. Calculate for curves parameters ( ) chains of 37-isogenic curves on the period = 31: 678 1
→ (37) (37) 12 (37) →
1
Here we see half of the dual curves
parameters of order 888. As in (
The results of the implementation of the
Edwards-CSIDH model [13] in projective
coordinates ( : ) claim that it is faster than the
Montgomery-CSIDH models in coordinates
( : ) by 20%. Note that this model in [13] is
built on the complete Edwards curves with the
order # = p+1 = 4n (n- odd) and the inversion
of the parameter ↔ −1 when the transition to
the curve of quadratic twist. [9–12] use the fastest
arithmetic of quadratic (
A multifunctional cryptosystem RCNIE on isogenies of non-supersingular Edwards curves is proposed, which solves the problems of DiffieHellman secret sharing, digital signature, and public key encryption. It is built on two classes of non-cyclic Edwards curves forming pairs of quadratic twists.
The basic RCNIE algorithm is a secret sharing algorithm that also serves to mutually authenticate users.
A model for the execution of cryptoalgorithms on isogenies of 4 degrees {3,5,7,37} is constructed and an analysis of its properties is given. Examples of calculations of curve parameters in crypto-algorithms using the randomization method are given.
The existence of the main and dual cryptosystems on non-supersingular curves is illustrated, for each of which there are isomorphic cryptosystems with inverted parameters. The possibility of parallel computing algorithms in these cryptosystems allows you to quadruple the performance of a complex cryptosystem, or use some of them for redundancy and updating.
A comparative evaluation of the arithmetic of cryptosystems on isogenies of supersingular and non-supersingular elliptic curves is given. It is noted that the authors found no reason to consider the latter technology to be slower than that adopted in CSIDH. Since the number of all nonsupersingular curves is estimated to be √ times greater than the number of supersingular ones, it is reasonable to use a number of their advantages mentioned above in future applications.
We believe that CSIDH and CRS technologies should not be opposed, but should be developed as promising, taking into account the features and advantages of each of them.
Further studies, it is planned to study new approaches to the formation of sets of isogeny degrees in RCNIE, as well as the digital signatures algorithm.