Encoding points of an elliptic curve
View Patent ↗The method comprises, in an electronic component, carrying out a cryptographic calculation that includes the step of obtaining points P on an elliptic curve following the equation Y 2 +a 1 XY+a 3 Y=X 3 +a 2 X 2 +a 4 +X+a 6 (1) where a 1 , a 2 , a 3 , a 4 et a 6 are elements of a set A of elements; where A is a ring of modular integers Z/qZ where q is a positive integer resulting from a number I of different prime numbers strictly higher than 3, I being an integer higher than or equal to 2, where A is a finite body Fq with q the power of a prime integer; where X and Y are the coordinates of the points P and are elements of A. The method comprises determining a diameter (11), and obtaining the coordinates X and Y of a point P (13) by applying a function (12) to said parameter. The Euler function φ of A corresponds to the equation φ(A) mod 3=1. The function is a reversible and deterministic function expressed by a rational fraction in a 1 , a 2 , a 3 , a 4 and a 6 and in said parameter in A, and reaches at least a number q/4 1 of points P, with I being equal to 1 for a finite body Pq. The method further comprises using the point P in a cryptographic application for ciphering or hashing or signature or authentication or identification.
1. A method of executing a cryptographic computation in an electronic component comprising:
obtaining points P on an elliptic curve satisfying the following equation:
Y 2 +a 1 XY+a 3 Y=X 3 +a 2 X 2 +a 4 +X+a 6 (1)
where a 1 a 2 , a 3 , a 4 and a 6 are elements of a set A of elements,
where A is a ring of the modular integers Z/qZ where q is a positive integer product of a number I of different prime numbers that are strictly greater than 3, I being an integer greater than or equal to 2, or A is a finite field F q with q a power of a prime integer;
where X and Y are the coordinates of the points P and are elements of A,
said method further comprising:
/a/ determining a parameter;
/b/ obtaining coordinates X and Y of a point P by applying a function to said parameter;
the Euler function φ of A satisfying the equation: φ(A) mod 3=1,
the function being an invertible and deterministic function expressed by a rational fraction in a 1 , a 2 , a 3 , a 4 and a 6 and in said parameter within A, and attaining at least a number q/4 I of points P, with I equal to 1 for a finite field F q ;
/c/ using said point P in a cryptographic encryption or hash or signature or authentication or identification application.
2. The method of executing a computation as claimed in claim 1 , in which A is different from F 2n ,
equation (1) being written:
Y 2 =X 3 +aX+b , and
where a=a 2 and b=a 6 ;
in which the deterministic function provides the coordinates of a point of the elliptic curve according to the following respective equations:
X
=
(
v
2
-
b
-
u
6
27
)
(
2
φ
(
A
)
+
1
)
/
3
+
u
2
3
and
(
4
)
Y
=
ux
+
v
(
5
)
where u is the parameter determined in step /a/, and
where v =(3 a−u 4 )/(6 u ) (6).
3. The method of executing a computation as claimed in claim 1 , in which q satisfies the equation:
q= 2′;
where n is an odd integer,
equation (1) being written:
Y 2 +XY=X 3 +aX 2 +b
where a=a 2 and b=a s ;
in which the deterministic function provides the coordinates of a point of the elliptic curve according to the following respective equations:
X =( w 4 +w 3 +b ) (2φ(A)+1)/3 +w (16)
Y=uX+w 2
where u is the parameter determined in step /a/, and
where w=a+u 2 +u.
4. The method of executing a computation as claimed in claim 1 , wherein said determining a parameter comprises obtaining the parameter by applying a hash function.
5. The method of executing a computation as claimed in claim 4 , in which the hash function is one-way.
6. The method of executing a computation as claimed in claim 1 , wherein said determining a parameter comprises obtaining the parameter by applying a first hash function h and a second hash function h′,
said cryptographic computation comprising the application of the following function:
f ( h )+ h′·G
where f is the deterministic function, and
where G is a generator of a group of points of the elliptic curve.
7. A method of authentication by at least one password implementing a method of executing a cryptographic computation as claimed in claim 1 , wherein said determining a parameter comprises determining the parameter as a function of the password, said password being included in the parameter, and further comprising performing an authentication on the basis of the point P.
8. A method of encrypting a datum, said encryption being based on the Boneh-Franklin identity on an elliptic curve admitting a coupling operation;
where the identity is a numerical value identifying an entity,
said method comprising:
/a/ obtaining a point by applying to the identity a method of executing a cryptographic computation;
/b/ obtaining an encrypted datum by combining said point, a random parameter and the datum;
wherein said obtaining a point by applying to the indentity a method of executing a cryptographic computation comprises obtaining said point on an elliptic curve satisfying the following equation:
Y 2 +a 1 XY+a 3 Y=X 3 +a 2 X 2 +a 4 +X+a 6 (1)
where a 1 , a 2 , a 3 , a 4 and a 6 are elements of a set A of elements,
where A is a ring of the modular integers Z/qZ where q is a positive integer product of a number I of different prime numbers that are strictly greater than 3, I being an integer greater than or equal to 2 , or A is a finite field F q with q a power of a prime integer;
where X and Y are the coordinates of said point and are elements of A,
and wherein said obtaining a point by applying to the identity a method of executing a cryptographic computation further comprises:
obtaining said coordinates X and Y of said point by applying a function to said identity;
the Euler function φ of A satisfying the equation: φ(A) mod 3=1,
the function being an invertible and deterministic function expressed by a rational fraction in a 1 , a 2 , a 3 , a 4 and a 6 and in said identity within A, and attaining at least a number q/4 I of points, with I equal to 1 for a finite field F q .
9. A method of executing a cryptographic computation in an electronic component comprising obtaining points P on an elliptic curve satisfying the following equation:
Y 2 +a 1 XY+a 3 Y=X 3 +a 2 X 2 +a 4 +X+a 6 (1)
where a 1 , a 2 , a 3 , a 4 and a 6 are elements of a set A of elements,
where A is a ring of the modular integers Z/qZ where q is a positive integer product of a number I of different prime numbers that are strictly greater than 3, I being an integer greater than or equal to 2, or A is a finite field F q with q a power of a prime integer;
where X and Y are the coordinates of the points P and are elements of A,
said method comprising:
/a/ determining a point P with coordinates X and Y on the elliptic curve;
/b/ obtaining a parameter by applying a function to the point P;
the Euler function φ of A satisfying the equation: φ(A) mod 3=1,
the function being the function inverse to an invertible and deterministic function expressed by a rational fraction in a 1 , a 2 , a 3 , a 4 and a 6 and in said parameter within A, and attaining at least a number q/4 I of points P, with I equal to 1 for a finite field F q ;
/c/ using said parameter in a cryptographic encryption or hash or signature or authentication or identification application.
10. A method of data compression in which the data to be compressed correspond respectively to pairs of data X and Y corresponding to coordinates of points P of an elliptic curve satisfying the following equation:
Y 2 +a 1 XY+a 3 Y=X 3 +a 2 X 2 +a 4 X+a 6 (1)
where a 1 , a 2 , a 3 , a 4 and a 6 are elements of a set A of elements,
where A is a ring of the modular integers Z/qZ where q is a positive integer product of a number I of different prime numbers that are strictly greater than 3, I being an integer greater than or equal to 2, or A is a finite field F q with q a power of a prime integer;
where X and Y are the coordinates of the points P and are elements of A,
comprising, for each of said pairs of data:
determining a point P with coordinates X and Y corresponding to each of said pairs of data on the elliptic curve;
obtaining a parameter by applying a function to the point P;
the Euler function φ of A satisfying the equation: φ(A) mod 3=1,
the function being the function inverse to an invertible and deterministic function expressed by a rational fraction in a 1 , a 2 , a 3 , a 4 and a 6 and in said parameter within A, and attaining at least a number q/4 I of points P, with I equal to 1 for a finite field F q ;
in which said pairs of data are represented by the parameters respectively obtained.
11. An electronic device arranged to execute a cryptographic computation, where:
the electronic device is arranged to obtain points P on an elliptic curve satisfying the following equation:
Y 2 +a 1 XY+a 3 Y=X 3 +a 2 X 2 +a 4 +X+a 6 (1
where a 1 a 2 , a 3 , a 4 and a 6 are elements of a set A of elements,
where A is a ring of the modular integers Z/qZ where q is a positive integer product of a number of different prime numbers that are strictly greater than 3, I being an integer greater than or equal to 2, or A is a finite field F q with q a power of a prime integer;
where X and Y are the coordinates of the points P and are elements of A,
and wherein:
the electronic device is arranged to determine a parameter;
the electronic device is arranged to obtain coordinates X and Y of a point P by applying a function to said parameter;
the Euler function φ of A satisfying the equation: φ(A) mod 3=1,
the function being an invertible and deterministic function expressed by a rational fraction in a 1 , a 2 , a 3 , a 4 and a 6 and in said parameter within A, and attaining at least a number q/ 4 I of points P, with equal to 1 for a finite field F q ;
the electronic device is arranged to use said point P in a cryptographic encryption or hash or signature or authentication or identification application.
12. An electronic device arranged to execute a cryptographic computation, wherein:
the electronic device is arranged to obtain points P on an elliptic curve satisfying the following equation:
Y 2 +a 1 XY+a 3 Y=X 3 +a 2 X 3 +a 4 +X+a 6 (1)
where a 1 , a 2 , a 3 , a 4 and a 6 are elements of a set A of elements,
where A is a ring of the modular integers Z/qZ where q is a positive integer product of a number I of different prime numbers that are strictly greater than 3, I being an integer greater than or equal to 2, or A is a finite field F q with q a power of a prime integer;
where X and Y are the coordinates of the points P and are elements of A,
and wherein:
the electronic device is arranged to determine a point P with coordinates X and Y on the elliptic curve;
the electronic device is arranged to obtain a parameter by applying a function to the point P;
the Euler function φ of A satisfying the equation: φ(A) mod 3=1,
the function being the function inverse to an invertible and deterministic function expressed by a rational fraction in a 1 , a 2 , a 3 , a 4 and a 6 and in said parameter within A, and attaining at least a number q/4 I of points P, with I equal to 1 for a finite field F q ;
the electronic device is arranged to use said parameter in a cryptographic encryption or hash or signature or authentication or identification application.