Cryptography on a simplified 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 satisfying: −f(X 1 (t))·f(X 2 (t))=U(t) 2 in the finite body F q , irrespective of the parameter t, q=3 mod 4. A value of the parameter t is obtained and the point P is determined by: (i) calculating X 1 =X 1 (t), X 2 =X 2 (t) and U=U(t); (ii) testing whether the term f(X −1 ) is a squared term in the finite body F q and, if so, calculating the square root of the term f(X 1 ), the point P having X 1 as abscissa and Y 1 , the square root of the term f(X 1 ), as ordinate; (iii) otherwise, calculating the square root of the term f(X 2 ), the point P having X 2 , as abscissa and Y 2 , the square root of the term f(X 2 ), as ordinate. The point P is useful in encryption, scrambling, signature, authentication or identification cryptographic applications.
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), and U(t) satisfying the following equality:
− f ( X 1 ( t ))· f ( X 2 ( 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) and U=U(t)
/ii/ 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 Y 1 ;
/iii/ 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
)
q
-
1
2
if R 1 is equal to 1,
deciding that the term f(X 1 ) is a squared term in field F q ; and
calculating
Y
1
=
f
(
X
1
)
q
+
1
4
otherwise, calculating
Y
2
=
f
(
X
2
)
q
+
1
4
3. Method of execution of a cryptographic calculation according to claim 1 , in which at step /2/-/ii/, the following steps are carried out:
calculating R 1 ′ such that:
R
1
′
=
f
(
X
1
)
q
-
1
-
q
+
1
4
calculating R 2 ′ such that:
R 2 ′=R 1 ′ 2
calculating R 3 ′ such that:
R 3 ′=R 2 ′·f ( X 1 )
in which if R 3 ′ is not equal to 1, at step /2/-/iii/, the square root of f(X 2 ) is obtained ( 316 ) according to the following equation:
√{square root over ( f ( X 2 ))}= R 0 ·R 1 ′
where R 0 satisfies the following equation:
R
0
=
U
(
t
)
·
(
-
1
)
q
-
1
-
q
+
1
4
.
4. Method of execution of a cryptographic calculation according to claim 3 , in which, if R 3 ′ is equal to 1, at step /2/-/iii/, obtaining the square root of f(X 1 ) according to the following equation:
√{square root over ( f ( X 1 ))}= R 3 ′·f ( X 1 )
5. Method of execution of a cryptographic calculation according to claim 1 , in which the polynomials 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 expressed in Jacobian coordinates are X′ 1 (t), X′ 2 (t), Z(t) and U′(t) and satisfy the equality in Jacobian coordinates:
U ′( t ) 2 =−f Z(t) ( X′ 1 ( t ))· f Z(t) ( X′ 2 ( 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.