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 Fq, 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 Fq and, if so, calculating the square root of the term f(X1), 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 a 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 ), the 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 ), the point P having X 2 as abscissa and the square root of the term f(X 2 ) as ordinate Y2; 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 to generate at least one of a secret key, a secret signature and an encrypted message for a user of a device, wherein the cryptographic calculation 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.
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 the calculated R 1 is equal to 1, decide that the term ƒ(X 1 ) is a squared term in the finite field F q ; and
otherwise, calculate the ordinate
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 ; and
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 the term ƒ(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 the term ƒ(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 ;and
Y′=Y·Z 3
where the function 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 =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 =−ƒ Z ( t )( X′ 1 ( t ))·ƒ Z ( t )( X′ 2 ( t ))
and in which Z(t) is determined in such a way that 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.