Criptografía de una curva elíptica.

Procedimiento de ejecución de un cálculo criptográfico en un componente electrónico que comprende una etapade obtención de un punto P(X,

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

Y2 ≥ f(X), y

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

f(X1(t)).f(X2(t)).f(X3(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 el citado procedimiento las etapas siguientes:

/1/ obtención de un valor del parámetro t;

/2/ determinación del punto P efectuando las subetapas siguientes:

/i/ cálculo de X1 ≥ X1(t), X2 ≥ X2(t), X3 ≥ X3(t) y U ≥ U(t)

/ii/ si el término f(X1).f(X2) es un término al cuadrado en el cuerpo finito Fq se prueba entones si el términof(X3) es un término al cuadrado en el cuerpo finito Fq y se calcula la raíz cuadrada del término f(X3), teniendo el puntoP por abscisa X3 y por ordenada la raíz cuadrada del término f(X3);

/iii/ si no, se prueba si el término f(X1) es un término al cuadrado en el cuerpo finito Fq y en este caso, secalcula la raíz cuadrada del término f(X1), teniendo el punto P por abscisa X1 y por ordenada la raíz cuadrada deltérmino f(X1);

/iv) si no, se calcula la raíz cuadrada del término f(X2), tendiendo el punto P por abscisa X2 y por ordenada laraíz cuadrada de término f(X2).

Criptografía de una curva elíptica La presente invención concierne a la criptografía de mensajes basada en la utilización de puntos de una curva elíptica, y de modo más particular a una criptografía de este tipo de manera determinista.

A fin de aplicar un cálculo criptográfico a un mensaje, se ponen en práctica clásicamente algoritmos de inserción de valores arbitrarios en el seno de estructuras matemáticas. A tal efecto, las curvas elípticas son estructuras matemáticas que permiten a la vez facilitar la puesta en práctica de tales cálculos criptográficos y ahorrar espacio de memoria con respecto a la puesta en práctica de otros cálculos criptográficos.

Sin embargo, los algoritmos eficaces de inserción de valores arbitrarios que utilizan curvas elípticas son probabilistas. Por consiguiente, el tiempo de puesta en práctica de tales algoritmos no es constante, éste es función del mensaje que haya que codificar. Así, si un atacante determina diferentes tiempos de puesta en práctica del algoritmo aplicado, éste 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 a este algoritmo etapas inútiles a fin de que su aplicación se extienda siempre en 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 ecuación siguiente:

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 permiten determinar un punto de este tipo de una curva elíptica, tal como se define en el documento ‘Construction of Rational Points on Elliptic Curves over finite fields’ de Andrew Shallue y Christiaan van de Woestijne.

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

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

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

donde t es un parámetro.

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) .fX3 (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 también fijar t, a un valor cualquiera. Así, queda por elegir el valor de un solo parámetro.

Dados parámetros elegidos t y u, se anota por 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 al menos uno de los valores f (X1) , f (X2) y f (X3) corresponde a un término al cuadrado en el cuerpo finito Fq.

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

El cálculo de f (Xi ) puede hacerse con la 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 conoce que:

(q+1) /4

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

Así pues, para determinar un punto de la curva elíptica (1) , conviene 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. A tal efecto, podría preverse controlar en primer lugar si el término f (X1) es un término al cuadrado en el cuerpo finito Fq, después, si este no es el caso, 2 10

aplicar este mismo control al término f (X2) , y finalmente si éste sigue sin ser el caso controlar de manera similar el término f (X3) . Sin embargo, procediendo así, la determinación de un punto en la curva elíptica no lleva siempre el mismo tiempo, puesto que esta determinación es efectuada más rápidamente si el primer término controlado es un término al cuadrado que si el tercer término es solamente un término al cuadrado.

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

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

Para paliar esta desventaja, sería posible controlar sistemáticamente los tres términos f (Xi) yendo i de 1 a 3. Así, el tiempo para determinar un punto de la curva ya no sería 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 especialmente pone en práctica una exponenciación que es laboriosa en tiempo de ejecución. En el caso en que se desee determinar un punto de la curva elíptica sobre la base de las igualdades de Skalba, efectuándose estas determinaciones a tiempo constante, se requieren cuatro operaciones de exponenciación en el caso anteriormente descrito, 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 describe en la ecuación (3) .

La presente invención pretende mejorar la situación.

Un primer aspecto de la presente invención 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, en una curva elíptica que verifique la ecuación:

Y2 = f (X) , y

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

f (X1 (t) ) .f (X2 (t) ) .fX3 (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 el citado procedimiento las etapas siguientes:

/1/ obtención de un valor del parámetro t;

/2/ determinación del punto P efectuando las subetapas siguientes:

/i/ cálculo de X1 = X1 (t) , X2 = X2 (t) , X3 = X3 (t) y U = U (t)

/ii/ si el término f (X1) .f (X2) es un término al cuadrado en el cuerpo finito Fq entones se prueba si el término f (X3) es un término al cuadrado en el cuerpo finito Fq y se calcula la raíz cuadrada del término f (X3) , teniendo el punto P por abscisa X3 y por ordenada la raíz cuadrada del término f (X3) ;

/iii/ si no, se prueba si el término f (X1) es un término al cuadrado en el cuerpo finito Fq y en este caso, se calcula 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) ;

/iv/ si no, se calcula la raíz cuadrada del término f (X2) , tendiendo el punto P por abscisa X2 y por ordenada la raíz cuadrada de término f (X2) ;

/3/ utilización del citado punto P en una aplicación criptográfica de cifrado o de hashing o de firma o de autenticación o de identificación.

Gracias a estas disposiciones, se puede determinar un punto de una curva elíptica de manera adaptada a una utilización en el ámbito de la criptografía, puesto que, por una parte, esta determinación lleva el mismo tiempo cualquiera que sea el parámetro de entrada t y, por otra, ésta es eficaz porque se reduce el número de operaciones.

Esta determinación lleva un tiempo constante que no es dependiente del parámetro o de los parámetros de entrada. En efecto, aunque este procedimiento ofrece diferentes vías de tratamiento en función del término que corresponda a un término al cuadrado en la igualdad de Skalba, se efectúa el mismo número de operaciones del mismo tipo, 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:

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

-determinación de una raíz cuadrada.

No es posible por tanto proceder a un ataque de tipo ‘timing attack’.

Además, esta determinación es eficaz puesto que el número de las operaciones laboriosas puestas en práctica es limitado. En efecto, es posible controlar el hecho de que uno de entre los tres términos de la ecuación... [Seguir leyendo]

1. 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, en una curva elíptica que verifica la ecuación: Y2 = f (X) , y a partir de polinomios X1 (t) , X2 (t) , X3 (t) y U (t) que verifican la igualdad de Skalba siguiente: f (X1 (t) ) .f (X2 (t) ) .f (X3 (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 el citado procedimiento las etapas siguientes: /1/ obtención de un valor del parámetro t; /2/ determinación del punto P efectuando las subetapas siguientes: /i/ cálculo de X1 = X1 (t) , X2 = X2 (t) , X3 = X3 (t) y U = U (t)

/ii/ si el término f (X1) .f (X2) es un término al cuadrado en el cuerpo finito Fq se prueba entones si el término f (X3) es un término al cuadrado en el cuerpo finito Fq y se calcula la raíz cuadrada del término f (X3) , teniendo el punto P por abscisa X3 y por ordenada la raíz cuadrada del término f (X3) ;

/iii/ si no, se prueba si el término f (X1) es un término al cuadrado en el cuerpo finito Fq y en este caso, se calcula 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) ;

/iv) si no, se calcula la raíz cuadrada del término f (X2) , tendiendo el punto P por abscisa X2 y por ordenada la raíz cuadrada de término f (X2) ; /3/ utilización del citado punto P en una aplicación criptográfica de cifrado o de hashing o de firma o de autenticación o de identificación.

2. Procedimiento de ejecución de un cálculo criptográfico de acuerdo con la reivindicación 1, en el cual en la etapa /2/-/ii/ se efectúan las etapas siguientes:

- cálculo de R1 tal que:

q+1

R1 = ( f (X1) .f (X 2) ) 4

- si R12 es igual a f (X1) .f (X2) , entonces decidir que el término f (X1) .f (X2) es un término al cuadrado en el cuerpo Fq;

en el cual, en la etapa /2/-/iii/, se prueba si el término f (X1) es un término al cuadrado en el cuerpo finito Fq según las etapas siguientes:

-cálculo de R2’ tal que

q+1

(q−1) −'

R2 = f (X1) 4

-cálculo de R3’ tal que:

' '

R = R

2

-cálculo de R4’ tal que

' '

R4 = R3. f (X1)

en el cual, si R4’ no es igual a 1, en la etapa /2/-/iv/, se obtiene la raíz cuadrada de f (X2) según la ecuación siguiente:

'

f (X 2) = R1.R2

3. Procedimiento de ejecución de un cálculo criptográfico de acuerdo con las reivindicaciones 1 o 2, en el cual los polinomios que verifican la igualdad de Skalba son expresados en coordenadas jacobianas según las cuales el punto P (X, Y) se escribe P (X’, Y’, Z) tales que X '=X .Z 2 ,

Y '=Y.Z donde la función f se escribe FZ (X ') y verifica:

46

fZ () ' =X ' aX 'Z

X +⋅⋅ +b ⋅Z

verificando la curva elíptica la ecuación:

Y '2 =fZ (X ')

en el cual los polinomios que verifican la igualdad de Skalba expresados en coordenadas jacobianas son X’1 (t) , X’2 (t) , X’3 (t) , Z (t) y U’ (t) y verifican la igualdad de Skalba en coordenadas jacobianas:

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

y en el cual Z (t) es determinada de modo que las operaciones de inversión sean transformadas en operación de multiplicación.

4. Procedimiento de ejecución de un cálculo criptográfico de acuerdo con las reivindicaciones 1 o 2, en el cual los polinomios que verifican la igualdad de Skalba son tales que es posible fijar el valor de X3 (t) para cualquier t posible, tal que f (X3 (t) ) no sea nunca un término al cuadrado en Fq,

y en el cual, en la etapa /2/-/ii/, el término f (X1) .f (X2) no es un término al cuadrado en el cuerpo finito Fq,

en el cual, en la etapa /2/-/iii/, se prueba si el término f (X1) es un término al cuadrado en el cuerpo finito Fq según las etapas siguientes:

-cálculo de R2’ tal que

(q−1) −q+1'

R2 =f (X1) 4

-cálculo de R3’ tal que:

2''

R =R

-cálculo de R4’ tal que

''

R4 =R3. f (X1)

después, si R4’ no es igual a 1, en la etapa /2/-/iv/, se obtiene la raíz cuadrada de f (X2) según la ecuación siguiente:

'

f (X 2) =R1.R2

q+1

donde R1 = ( f (X1) .f (X 2) ) 4

en el cual R1 es obtenido previamente según la ecuación siguiente:

q+1 q+1

(q−1) −

R1 = ( f (X ) .f (X 2) ) 4 =U.f (u) 4

5. Procedimiento de ejecución de un cálculo criptográfico de acuerdo con la reivindicación 4, en el cual los polinomios que verifican la igualdad de Skalba son expresados en coordenadas jacobianas según las cuales el punto P (X, Y) se escribe P (X’, Y’, Z) tales que X '=X .Z 2 ,

Y '=Y.Z

donde la función f se escribe FZ (X ') y verifica:

46

fZ () ' =X ' aX 'Z

X +⋅⋅ +b ⋅Z

verificando la curva elíptica la ecuación:

Y '2 =fZ (X ')

en el cual los polinomios que verifican la igualdad de Skalba expresados en coordenadas jacobianas son X’1 (t) , X’2 (t) , Z (t) y U’ (t) y verifican la igualdad de Skalba en coordenadas jacobianas:

U ' (t) =fZ (t) (X '1 (t) ) .fZ (t) (X '2 (t) ) .f (X 3 (t) )

y en el cual Z (t) es determinado de modo que las operaciones de inversión sean transformadas en operación de 10 multiplicación.

6. Procedimiento de ejecución de un cálculo criptográfico de acuerdo con una cualquiera de las reivindicaciones precedentes, en el cual, en la etapa /1/, el valor del parámetro t es obtenido en función de una contraseña o un identificador.

7. Procedimiento de ejecución de un cálculo criptográfico de acuerdo con una cualquiera de las reivindicaciones 1 a

5, en el cual la aplicación criptográfica es una aplicación de autenticación o de identificación por una entidad de control, y

en el cual, en la etapa /1/, se realizan las etapas siguientes:

/a/ generación de un valor aleatorio;

/b/ obtención de un valor cifrado, cifrando el citado valor aleatorio sobre una base de una función de cifrado que 20 utiliza una clave de cifrado determinada a partir de una contraseña o identificador correspondiente al parámetro; y

/c/ transmisión del valor cifrado a la entidad de control.

8. 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 de acuerdo con una cualquiera de las reivindicaciones 1 a 7.