CRYPTOGRAPHY ON A SIMPLIFIED ELLIPTICAL CURVE
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 . An electronic component configured to execute a cryptographic calculation and obtain a point P(X,Y) from at least one parameter t, on an elliptical curve that satisfies the equation: Y 2 =f(X) and 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 electronic component configured to:
obtain a value of the parameter t;
determine the point P 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 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; and
wherein said electronic component is further configured to use said point P in a cryptographic application selected from the group consisting of encryption or hashing or signature or authentication or identification.
2 . The electronic component according to claim 1 , wherein in order to determine the point P said electronic component is further configured to:
calculate R 1 such that:
R
1
=
f
(
X
1
)
q
-
1
2
if R 1 is equal to 1,
decide that the term f(X 1 ) is a squared term in field F q ; and
calculate
Y
1
=
f
(
X
1
)
q
+
1
4
otherwise, calculate
Y
2
=
f
(
X
2
)
q
+
1
4
.
3 . The electronic component according to claim 1 , wherein in order to determine the point P said electronic component is further configured to:
calculate R 1 ′ such that:
R
1
′
=
f
(
X
1
)
q
-
1
-
q
+
1
4
calculate R 2 ′ such that:
R 2 ′=R 1 2 ′
calculate R 3 ′ such that:
R 3 ′=R 2 ′.ƒ( X 1 )
if R 3 ′ is not equal to 1, then obtain the square root of f(X 2 ) according to the following equation:
√{square root over (ƒ( X 2 ))}= R 0 .R 1 ′
where R 0 satisfies the following equation:
R
0
=
U
(
t
)
·
(
-
1
)
q
-
1
-
q
+
1
4
.
4 . The electronic component according to claim 3 , further configured to determine the point P by obtaining the square root of f(X 1 ) according to the following equation:
√{square root over (ƒ( X 1 ))}= R 3 ′.ƒ( X 1 ).
if R 3 ′ is equal to 1.
5 . The electronic component according to claim 1 , wherein 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 ƒ Z (X′) and satisfies:
ƒ Z ( X ′)= X′ 3 +a.X′.Z 4 +b.Z 6
with the elliptical curve satisfying the equation:
Y′ 2 =ƒ 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 =−ƒ Z(t) ( X′ 1 ( t )).ƒ 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 . The electronic component according to claim 1 , wherein in obtaining the value of the parameter t said electronic component is further configured to obtain the value of the parameter t as a function of a password or an identifier.
7 . The electronic component according to claim 1 , wherein the cryptographic application is an application of authentication or identification by a checking entity, and wherein said electronic component in obtaining the value of the parameter t is further configured to:
/a/ generate a random value;
/b/ obtain 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/ transmit the encrypted value to the checking entity.