Cryptography on a elliptical curve
View Patent ↗A cryptographic calculation includes obtaining a point P(X,Y) from a parameter t on an elliptical curve Y 2 =f(X); and from polynomials X 1 (t), X 2 (t), X 3 (t) and U(t) satisfying: f(X 1 (t))·f(X 2 (t))·f(X 3 (t))=U(t) 2 in Fq, with q=3 mod 4. Firstly a value of the parameter t is obtained. Next, the point P is determined by: (i) calculating X 1 =X 1 (t), X 2 =X 2 (t), X 3 =X 3 (t) and U=U(t); (ii) if the term f(X 1 )·f(X 2 ) is a square, then testing whether the term f(X 3 ) is a square in F q and if so calculating the square root of f(X 3 ) in order to obtain the point P(X 3 ); (iii) otherwise, testing whether the term f(X 1 ) is a square and, if so, calculating the square root of f(X 1 ) in order to obtain the point P(X 1 ); (iv) otherwise, calculating the square root of f(X 2 ) in order to obtain the point P(X 2 ). This point P is useful in a cryptographic application.
1. Method of execution of a cryptographic calculation in an electronic component comprising a step of obtaining a point P(X,Y) from at least one parameter t, on an elliptical curve satisfying the equation:
Y 2 =f ( X ); and
starting from polynomials X 1 (t), X 2 (t), X 3 (t) and U(t) satisfying the following Skalba equality:
f ( X 1 ( t ))· f ( X 2 ( t )· f ( X 3 ( t )= U ( t ) 2
in the finite field F q , regardless of the parameter t, q satisfying the equation q=3 mod 4;
said method comprising the following steps:
/1/ obtaining a value of the parameter t;
/2/ determining the point P by executing the following substeps:
/i/ calculating X 1 =X 1 (t), X 2 =X 2 (t), X 3 =X 3 (t) and U=U(t) and calculating a term f(X 1 )·f(X 2 );
/ii/ if the term f(X 1 )·f(X 2 ) is a squared term in the finite field F q then testing whether the term f(X 3 ) is a squared term in the finite field F q and calculating the square root of the term f(X 3 ), point P having X 3 as abscissa and the square root of the term f(X 3 ) as ordinate;
/iii/ otherwise, testing whether the term f(X 1 ) is a squared term in the finite field F q and in this case, calculating the square root of the term f(X 1 ), point P having X 1 as abscissa and the square root of the term f(X 1 ) as ordinate;
/iv/ otherwise, calculating the square root of the term f(X 2 ), point P having X 2 as abscissa and the square root of the term f(X 2 ) as ordinate;
/3/ using said point P in a cryptographic application selected from the group consisting of encryption or hashing or signature or authentication or identification.
2. Method of execution of a cryptographic calculation according to claim 1 , in which the following steps are executed at step /2/-/ii/:
calculating R 1 such that:
R
1
=
(
f
(
X
1
)
·
f
(
X
2
)
)
q
+
1
4
if R 1 2 is equal to f(X 1 )·f(X 2 ), then deciding whether the term f(X 1 )·f(X 2 ) is a squared term in field F q ;
in which, at step /2/-/iii/, testing whether the term f(X 1 ) is a squared term in the finite field F q according to the following steps:
calculating R′ 2 such that:
R
2
′
=
f
(
X
1
)
q
-
1
-
q
+
1
4
calculating R′ 3 such that:
R′ 3 =R′ 2 2
calculating R′ 4 such that:
R′ 4 =R′ 3 ·f ( X 1 )
in which, if R′ 4 is not equal to 1, at step /2/-/iv/, obtaining the square root of f(X 2 ) from the following equation:
√{square root over ( f ( X 2 ))}= R 1 ·R′ 2 .
3. Method of execution of a cryptographic calculation according to claim 1 , in which the polynomials that satisfy Skalba's equality are expressed in Jacobian coordinates according to which the point P(X,Y) is written P(X′,Y′,Z) such that:
X′=X·Z 2 ,
Y′=Y·Z 3
where the function f is written f z (X′) and satisfies:
f z ( X ′)= X′ 3 +a·X′·Z 4 +b·Z 6
with the elliptical curve satisfying the equation:
Y′ 2 =f z ( X ′)
in which the polynomials that satisfy Skalba's equality expressed in Jacobian coordinates are X′ 1 (t), X′ 2 (t), X′ 3 (t), Z(t) and U′(t) and satisfy Skalba's equality in Jacobian coordinates:
U ′( t ) 2 =f Z(t) ( X′ 1 ( t ))· f Z(t) ( X′ 2 ( t ))· f Z(t) ( X′ 3 ( t ))
and in which Z(t) is determined in such a way that the operations of inversion are transformed into operations of multiplication.
4. Method of execution of a cryptographic calculation according to claim 1 , in which the polynomials that satisfy Skalba's equality are such that it is possible to set the value of X 3 (t) for any possible t, such that f(X 3 (t)) is never a squared term in F q ,
and in which, at step /2/-/ii/, the term f(X 1 )·f(X 2 ) is not a squared term in the finite field F q ,
in which, at step /2/-/iii/, it is tested whether the term f(X 1 ) is a squared term in the finite field F q according to the following steps:
calculating R′ 2 such that:
R
2
′
=
f
(
X
1
)
q
-
1
-
q
+
1
4
calculating R′ 3 such that:
R′ 3 =R′ 2 2
calculating R′ 4 such that:
R′ 4 =R′ 3 ·f ( X 1 )
in which, if R′ 4 is not equal to 1, at step /2/-/iv/, obtaining the square root of f(X 2 ) from the following equation:
f
(
X
2
)
=
R
1
·
R
2
′
where
R
1
=
(
f
(
X
1
)
·
f
(
X
2
)
)
q
+
1
4
in which R 1 is obtained beforehand from the following equation:
R
1
=
(
f
(
X
)
·
f
(
X
2
)
)
q
+
1
4
=
U
·
f
(
u
)
q
-
1
-
q
+
1
4
.
5. Method of execution of a cryptographic calculation according to claim 4 , in which the polynomials that satisfy Skalba's equality are expressed in Jacobian coordinates according to which the point P(X,Y) is written P(X′,Y′,Z) such that:
X′=X·Z 2 ,
Y′=Y·Z 3
where the function f is written f z (X′) and satisfies:
f z ( X ′)= X′ 3 +a·X′·Z 4 +b·Z 6
with the elliptical curve satisfying the equation:
Y′ 2 f z ( X ′),
in which the polynomials that satisfy Skalba's equality expressed in Jacobian coordinates are X′ 1 (t), X′ 2 (t), Z(t) and U′(t) and satisfy Skalba's equality in Jacobian coordinates:
U ′( t ) 2 =f Z(t) ( X′ 1 ( t ))· f Z(t) ( X′ 2 ( t ))· f ( X′ 3 ( t ))
and in which Z(t) is determined in such a way that the operations of inversion are transformed into operations of multiplication.
6. Method of execution of a cryptographic calculation according to claim 1 , in which, at step /1/, the value of the parameter t is obtained as a function of a password or an identifier.
7. Method of execution of a cryptographic calculation according to claim 1 , in which the cryptographic application is an application of authentication or identification by a checking entity, and
in which, at step /1/, the following steps are executed:
/a/ generating a random value;
/b/ obtaining an encrypted value by encrypting said random value based on an encryption function using an encryption key determined from a password or identifier corresponding to the parameter; and
/c/ transmitting the encrypted value to the checking entity.
8. A method for obtaining, with an electronic component, a point P(X,Y) on an elliptical curve satisfying the equation Y 2 =f(X) and starting from polynomials X 1 (t), X 2 (t), X 3 (t) and U(t) satisfying the Skalba equality:
f ( X 1 ( t ))· f ( X 2 ( t ))· f ( X 3 ( t ))= U ( t ) 2
in the finite field F q for any value oft, the method comprising:
(a) selecting a parameter t;
(b) calculating X 1 =X 1 (t), X 2 =X 2 (t) and X 3 =X 3 (t);
(c) calculating a term f(X 1 )·f(X 2 );
(d) determining if the term f(X 1 )·f(X 2 ) is a squared term in the finite field F q , if (d) is true, then:
(e1) testing whether the term f(X 3 ) is a squared term in the finite field F q , and
(e2) calculating the square root of the term f(X 3 ), and
(e3) assigning point P with an abscissa equal to X 3 and an ordinate equal to the square root of the term f(X 3 ).
if (d) is not true, then:
(f) testing whether the term f(X 1 ) is a squared term in the finite field F q , and
if (f) is true, then:
(g1) calculating the square root of the term f(X 1 ), and
(g2) assigning point P with an abscissa equal to X 1 and an ordinate equal to the square root of the term f(X 1 ).
if (f) is not true, then:
(h1) calculating the square root of the term f(X 2 ), and
(h2) assigning point P with an abscissa equal to X 2 and an ordinate equal to the square root of the term f(X 2 ).
9. The method of claim 8 , wherein the value oft is a function of a password or an identifier.
10. The method of claim 8 , further comprising using said point P in a cryptographic application selected from the group consisting of encryption or hashing or signature or authentication or identification.
11. The method of claim 10 , in which the cryptographic application is an application of authentication or identification by a checking entity, the method further comprising:
generating a random value;
obtaining an encrypted value by encrypting said random value based on an encryption function using an encryption key determined from a password or identifier corresponding to the value of t; and
transmitting the encrypted value to the checking entity.
12. The method of claim 8 , wherein the polynomials that satisfy Skalba's equality are expressed in Jacobian coordinates.
13. A method for obtaining, with an electronic component, a point P(X,Y) on an elliptical curve satisfying the equation Y 2 =f(X) and starting from polynomials X 1 (t), X 2 (t), X 3 (t) and U(t) satisfying the Skalba equality:
f ( X 1 ( t ))· f ( X 2 ( t ))· f ( X 3 ( t ))= U ( t ) 2
in the finite field F q for any value of t, the method comprising choosing the polynomials that satisfy Skalba's equality such that the value of X 3 (t) for any value of t is such that f(X 3 (t)) is never a squared term in F q , the method further comprising:
(a) selecting a parameter t;
(b) calculating X 1 =X 1 (t) and X 2 =X 2 (t);
(c) determining if the term f(X 1 ) is a squared term in the finite field F q ,
if (c) is true, then:
(d1) calculating the square root of the term f(X 1 ), and
(d2) assigning point P with an abscissa equal to X 1 and an ordinate equal to the square root of the term f(X 1 )
if (c) is not true, then:
(d3) calculating the square root of the term f(X 2 ), and
(d4) assigning point P with an abscissa equal to X 2 and an ordinate equal to the square root of the term f(X 2 ).