Patent Application

App. No. 14/261,959

Abstract

Claims (177)

1 . An electronic component configured to execute a cryptographic calculation and to 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), 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, wherein said electronic component is configured to:

obtain a value of the parameter t; and

determine the point P 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 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;

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

)

·

f



(

X

2

)

)

q

+

1

4

if R 1 2 is equal to f(X 1 )·f(X 2 ), then decide whether the term f(X 1 )·f(X 2 ) is a squared term in field F q ;

test whether the term f(X 1 ) is a squared term in the finite field F q by:

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 ′·ƒ( X 1 )

if R 4 ′ is not equal to 1, obtain the square root of f(X 2 ) from the following equation:

√{square root over (ƒ( X 2 ))}= R 1 ·R 2 ′.

3 . The electronic component according to claim 1 , wherein 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 ƒ 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 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 =ƒ Z(t) ( X′ 1 ( t ))·ƒ Z(t) ( X′ 2 ( t )·ƒ 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 . The electronic component according to claim 1 , wherein 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

wherein when determining the point P, the term f(X 1 )·f(X 2 ) is not a squared term in the finite field F q ,

wherein determining the point P further comprises testing whether the term f(X 1 ) is a squared term in the finite field F q by:

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 ′·ƒ( X 1 )

wherein, if R 4 ′ is not equal to 1, determining the point P further comprises obtaining the square root of f(X 2 ) according to the following equation:

√{square root over (ƒ( 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 . The electronic component according to claim 4 , wherein 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 ƒ 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 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 =ƒ Z(t) ( X′ 1 ( t ))·ƒ Z(t) ( X′ 2 ( 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.

6 . The electronic component according to claim 1 , wherein obtaining a value of the parameter t comprises obtaining the value 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 obtaining the value of the parameter t further comprises:

/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.

Assignments (9)