Criptografía sobre una curva elíptica simplificada.

Un procedimiento de ejecución de un cálculo criptográfico en un componente electrónico que comprende unaetapa de obtención de un punto P(X,

Y) a partir de al menos un parámetro t, sobre una curva elíptica que verifica laecuación:

Y2 ≥ f(X); y

a partir de polinomios X1(t), X2(t) y U(t) que verifican la igualdad siguiente:

-f(X1 (t)).f(X2(t))≥U(t)2

en el cuerpo finito Fq, cualquiera que sea el parámetro t, q verificando la ecuación q ≥ 3 mod 4;

comprendiendo dicho procedimiento las etapas siguientes:

/1/ obtener un valor del parámetro t;

/2/ determinar el punto P efectuando las subetapas siguientes:

/i/ calcular (11) X1 ≥ X1(t), X2 ≥ (X2(t) y U≥U(t)

/ii/ probar (12) si el término f(X1) es un término al cuadrado en el cuerpo finito Fq y

en este caso, calcular (13) la raíz cuadrada del término f(X1), teniendo el punto P por abscisa X1 y por ordenada Y1 laraíz cuadrada del término f(X1);

/iii/ si no calcular (14) la raíz cuadrada del término f(X2), teniendo el punto P porabscisa X2 y por ordenada Y2 la raíz cuadrada del término f(X2);

/3/ utilizar dicho punto P en una aplicación criptografía sea de cifrado o de aplicación defunciones hash o de firma de autentificación o de identificación.

Criptografía sobre una curva elíptica simplificada.

El presente invento se refiere a la criptografía de mensajes basada en la utilización de puntos de una curva elíptica, y más particularmente a tal criptografía de manera determinista.

A fin de aplicar un cálculo criptográfico a un mensaje, se emplean clásicamente algoritmos de inserción de valores arbitrarios en el seno de estructuras matemáticas. A este efecto, las curvas elípticas son estructuras matemáticas que permiten a la vez facilitar el empleo de tales cálculos criptográficos y guardar espacio de memoria con relación al empleo de otros cálculos criptográficos.

Sin embargo los algoritmos eficaces de inserción de valores arbitrarios que utilizan las curvas elípticas son probabilistas. Por consiguiente, el tiempo de empleo de tales algoritmos no es constante, es función del mensaje a codificar. Así, si un atacante determina diferentes tiempos de empleo del algoritmo aplicado, puede obtener informaciones sobre el mensaje codificado.

A fin de enmascarar el tiempo utilizado por un algoritmo de inserción probabilista, es posible prever añadir etapas inútiles en este algoritmo con el fin de que su aplicación se despliegue siempre sobre un período de tiempo de longitud idéntica, cualquiera que sea el mensaje tratado.

Un punto P de una curva elíptica está definido por su abscisa X y su ordenada Y, verificando X e Y la siguiente ecuación:

f (X) = Y2 (1)

donde f (X) es el polinomio f (X) = X3 + aX + b

Se conoce una familia de polinomios, que verifican la igualdad de Skalba que permite determinar un punto de una curva elíptica, tal como se ha definido en el documento 'Construcción de Puntos Racionales sobre Curvas Elípticas sobre campos finitos' de Andrew Shallue y Christiaan van de Woestijne.

Los polinomios X1 (t) , X2 (t) , X3 (t) y U (t) verifican la igualdad de Skalba si verifican la siguiente ecuación:

f (X1 (t) ) .f (X2 (t) ) .f (X3 (t) ) =U2 (t) (2)

donde f es la función que define la curva elíptica considerada, y

donde t es un parámetro.

Los polinomios que verifican la igualdad de Skalba pueden tomar dos parámetros u y t. En este caso, la igualdad de Skalba se escribe:

f (X1 (t, u) ) .f (X2 (t, u) ) .f (X3 (t, u) ) =U2 (t, u)

Se puede utilizar este tipo de ecuaciones con dos parámetros u y t. Sin embargo, en las aplicaciones consideradas, se puede prever ventajosamente fijar u, o incluso fijar t, a un valor cualquiera. Así, queda por elegir el valor de un solo parámetro.

Dados los parámetros elegidos t y u, se observa que X1 = X1 (t, u) , X2=X2 (t, u) , X3=X3 (t, u) , U=U (t, u) , donde X1, X2, X3 y U son elementos de Fq. Esta ecuación (2) significa que uno al menos de entre los valores f (X1) , f (X2) y f (X3) corresponde a un término al cuadrado en el cuerpo finito Fq.

Luego, una vez que el término al cuadrado de Fq, f (Xi) , es identificado, se puede obtener a continuación un punto de la curva elíptica P (X ,

i El cálculo de f (Xi ) puede hacerse con ayuda de un cálculo de exponenciación cuando la característica q del

cuerpo Fq verifica:

q = 3 mod 4 En este caso, se sabe que:

q+1) /4

f (Xi ) = f (Xi ) ( (3)

Para determinar un punto de la curva elíptica (1) , conviene por tanto determinar qué valor de entre los tres valores f (X1) , f (X2) y f (X3) corresponde a un término al cuadrado en el cuerpo finito Fq. Se podría a este efecto prever controlar en primer lugar si el término f (X1) es un término al cuadrado en el cuerpo finito Fq, luego, si no es este el caso, aplicar este mismo control al término f (X2) , y finalmente si sigue sin ser el caso nunca, el término f (X3) de manera similar. Sin embargo, procediendo así, la determinación de un punto sobre la curva elíptica no consume siempre el mismo tiempo, ya que esta determinación es efectuada más rápidamente si el primer término controlado es un término al cuadrado que si solo el tercer término es un término al cuadrado.

Un atacante potencial podría extraer parte de esta diferencia de tiempo transcurrido en determinar un punto sobre la curva elíptica para violar el secreto unido al parámetro que ha permitido generar este punto. Ahora bien, en el dominio de la criptografía, estos parámetros deben permanecer secretos.

Estos parámetros pueden en particular corresponder a contraseñas. Así, es importante que la determinación de estos puntos no proporcione en sí misma informaciones que permitan violar el secreto del parámetro, y por este hecho, hay que evitar ataques basados sobre un análisis del tiempo transcurrido en determinar un punto de la curva.

Para paliar esta desventaja, sería posible controlar de manera sistemática los tres términos f (Xi) yendo i de 1 a 3. Así, el tiempo para determinar un punto de la curva no sería ya función del punto determinado.

Pero, el hecho de controlar si un término de la ecuación (2) es un término al cuadrado en el cuerpo finito Fq es una operación compleja que pone en práctica en particular una exponenciación que es costosa en tiempo de ejecución. En el caso en que se desea determinar un punto de una curva elíptica sobre la base de las igualdades de Skalba, efectuando al mismo tiempo estas determinaciones en tiempo constante, se requieren cuatro operaciones de exponenciación en el caso descrito anteriormente, una exponenciación por control de cada uno de los términos de la ecuación (2) de Skalba y una exponenciación para calcular la raíz cuadrada, tal como se ha descrito en la ecuación (3) .

El presente invento pretende mejorar la situación.

Un primer aspecto del presente invento propone un procedimiento de ejecución de un cálculo criptográfico en un componente electrónico que comprende una etapa de obtención de un punto P (X, Y) a partir de al menos un parámetro t, sobre una curva elíptica que verifica la ecuación:

Y2 = f (X) ; y

a partir de polinomios X1 (t) , X2 (t) y U (t) que verifican la igualdad siguiente:

-f (X1 (t) ) .f (X2 (t) ) =U (t) 2

en el cuerpo finito Fq, cualquiera que sea el parámetro t, verificando q la ecuación q = 3 mod 4;

comprendiendo dicho procedimiento las etapas siguientes:

/1/ obtener un valor del parámetro t;

/2/ determinar el punto P efectuando las sub etapas siguientes:

/i/ calcular X1 = X1 (t) , X2 = (X2 (t) y U (t) =U (t)

/ii/ probar si el término f (X1) es un término al cuadrado en el cuerpo finito Fq y en este caso, calcular la raíz cuadrada del término f (X1) , teniendo el punto P por abscisa X1 y por ordenada la raíz cuadrada del término f (X1) ;

/iii/ si no calcular la raíz cuadrada en el término f (X2) , teniendo el punto P por abscisa X2 y por ordenada la raíz cuadrada del término f (X2) ;

/3/ utilizar dicho punto P en una aplicación criptografía sea de cifrado o de aplicación de funciones hash o de firma de autentificación o de identificación.

Conviene aquí observar que la determinación de un punto sobre una curva elíptica es efectuada sobre la base de una ecuación ventajosa:

-f (X1) .f (X2) =U (t) 2 (4)

Esta ecuación proviene de la igualdad de Skalba (2) . En efecto, se puede obtener esta ecuación poniendo:

f (X3) = -1

Ahora bien, en el cuerpo finito Fq con q = 3 mod 4, el -1 no es un término al cuadrado. Por consiguiente, solamente dos términos de la ecuación (4) quedan aún por ser controlados para decidir cuál de los dos términos corresponde a un término al cuadrado en Fq.

Gracias a estas disposiciones, se puede determinar un punto de una curva elíptica de manera adaptada a una utilización en el dominio de la criptografía, ya que por una parte, esta determinación consume el mismo tiempo cualquiera que sea el parámetro de entrada t y por otra parte, es eficaz pues el número de operaciones pesadas es reducido.

Esta determinación consume un tiempo constante que no depende del o de los parámetros de entrada. En efecto, incluso si este procedimiento ofrece diferentes voces de tratamiento en función del término que corresponde a un término cuadrado en la igualdad de Skalba, el mismo número de operaciones del mismo tipo es efectuado cualquiera que sea el punto de la curva determinado. De manera más precisa, cualquiera que sea el punto de la curva determinado, se efectúa la lista de las operaciones siguientes:

- ensayo de un término al cuadrado en Fq;

-determinación de una raíz cuadrada.

No es por tanto posible proceder a un ataque de tipo ' ataque de temporización'.

Además, esta determinación es eficaz ya que el número de las operaciones... [Seguir leyendo]

1. Un procedimiento de ejecución de un cálculo criptográfico en un componente electrónico que comprende una etapa de obtención de un punto P (X, Y) a partir de al menos un parámetro t, sobre una curva elíptica que verifica la ecuación:

Y2 = f (X) ; y a partir de polinomios X1 (t) , X2 (t) y U (t) que verifican la igualdad siguiente:

-f (X1 (t) ) .f (X2 (t) ) =U (t) 2 en el cuerpo finito Fq, cualquiera que sea el parámetro t, q verificando la ecuación q = 3 mod 4; comprendiendo dicho procedimiento las etapas siguientes:

/1/ obtener un valor del parámetro t;

/2/ determinar el punto P efectuando las subetapas siguientes:

/i/ calcular (11) X1 = X1 (t) , X2 = (X2 (t) y U=U (t)

/ii/ probar (12) si el término f (X1) es un término al cuadrado en el cuerpo finito Fq y

en este caso, calcular (13) la raíz cuadrada del término f (X1) , teniendo el punto P por abscisa X1 y por ordenada Y1 la raíz cuadrada del término f (X1) ; /iii/ si no calcular (14) la raíz cuadrada del término f (X2) , teniendo el punto P por abscisa X2 y por ordenada Y2 la raíz cuadrada del término f (X2) ; /3/ utilizar dicho punto P en una aplicación criptografía sea de cifrado o de aplicación de funciones hash o de firma de autentificación o de identificación. 2. Un procedimiento de ejecución de un cálculo criptográfico según la reivindicación 1, en el que en la etapa /2/-/ii/, se efectúan las etapas siguientes:

-calcular (21) R1 tal que:

q-1 R1 = f (X1) 2

-si R1 es igual a 1 (22) ,

-decidir que el término f (X1) es un término al cuadrado en el cuerpo Fq; y

q+1

-calcular (24) Y1 = f (X1) 4

q+1

-si no (23) , calcular Y2 = f (X 2) 4

3. Un procedimiento de ejecución de un cálculo criptográfico según la reivindicación 1, en el que en la etapa /2/-/ii/, se efectúan las etapas siguientes:

-calcular (311) R1' tal que:

q+1

q-1-

R1'= f (X1) 4

-calcular (312) R2' tal que:

R2'= R1'2

-calcular (313) R3' tal que:

R '= R '.f (X )

1

en el que si R3' no es igual a 1, en la etapa /2/-/iii/, se obtiene (316) la raíz cuadrada de f (X2) según la ecuación siguiente:

f (X ) =R .R '

01

donde R0 verifica la ecuación siguiente:

q+1

q-1-

R0 = U (t) . (-1) 4

4. Un procedimiento de ejecución de un cálculo criptográfico según la reivindicación 3, en el que, si R3' es igual a 1, entonces en la etapa /2/-/iii/, se obtiene (315) la raíz cuadrada de f (X1) según la ecuación siguiente:

f (X ) = R '.f (X )

1

5. Un procedimiento de ejecución de un cálculo criptográfico según la reivindicación 1, en el que los polinomios son expresados en coordenadas jacobianas según las cuales el punto P (X, Y) se escribe P (X', Y', Z) tales que X' = X.Z2, Y' = Y.Z3 donde la función f se escribe fZ (X') y verifica:

fZ (X') = X'3+a.x'.Z4 + b.Z6

verificando la curva elíptica la ecuación:

Y'2 = fZ (X')

en la que los polinomios expresados en coordenadas jacobianas son X'1 (t) , X'2 (t) , Z (t) y U' (t) y verifican la igualdad siguiente en coordenadas jacobianas:

U' (t) 2 = -fZ (t) (X'1 (t) ) .fZ (t) (X'2 (t) ) )

y en la que Z (t) es determinada de manera que las operaciones de inversión sean transformadas en operación de multiplicación. 6. Un procedimiento de ejecución de un cálculo criptográfico según cualquiera de las reivindicaciones precedentes, en el que en la etapa /1/, el valor del parámetro t puede ser obtenido en función de una contraseña o un identificador.

7. Un procedimiento de ejecución de un cálculo criptográfico según cualquiera de las reivindicaciones 1 a 6, en el que la aplicación criptográfica es una aplicación de autentificación o de identificación por una entidad de control, y en el cual, en la etapa /1/, se realizan las etapas siguientes: /a/ generar un valor aleatorio;

/b/ obtener un valor cifrado cifrando dicho valor aleatorio sobre la base de una función de cifrado utilizando una clave de cifrado determinada a partir de una contraseña o identificador correspondiente al parámetro; y

/c/ transmitir el valor cifrado a la entidad de control.

8. Un dispositivo electrónico que comprende medios adaptados para la puesta en práctica de un procedimiento de ejecución de un cálculo criptográfico según una cualquiera de las reivindicaciones 1 a 7.