Procedimiento de procesamiento criptográfico de datos y dispositivo asociado.

Procedimiento de procesamiento criptográfico de datos aplicado dentro de una entidad electrónica,

en el que sedetermina, a partir de un primer punto en una curva elíptica representado mediante al menos tres primeroselementos de un cuerpo de Galois, un segundo punto en la curva elíptica representado mediante al menos tressegundos elementos del cuerpo de Galois, siendo obtenido cada uno de los segundos elementos a partir de losprimeros elementos mediante un primer conjunto de operaciones que comprende multiplicaciones y adiciones, enel que se aplica un segundo conjunto de operaciones sucesivas que tienen cada una un tipo, formando la seriede los tipos de las operaciones sucesivas del segundo conjunto una repetición periódica de una pluralidad detipos de operación que incluye al menos una multiplicación y una adición en el cuerpo de Galois, comprendiendoel segundo conjunto de operaciones el primer conjunto de operaciones, caracterizado porque la pluralidad detipos de operación comprende una puesta al cuadrado en el cuerpo de Galois.

Procedimiento de procesamiento criptográfico de datos y dispositivo asociado La invención se refiere a un procedimiento de procesamiento, preferentemente criptográfico, de datos, por ejemplo aplicado dentro de una entidad electrónica, y a un dispositivo asociado (por ejemplo esta entidad electrónica) .

En el ámbito del procesamiento de datos (pudiendo estos datos representar por ejemplo un mensaje que se ha de intercambiar o una clave criptográfica de cifrado de un mensaje de este tipo) , se utilizan las propiedades de las curvas elípticas en los cuerpos acabados durante los cálculos criptográficos implicados por el procesamiento de los datos, por ejemplo para firma de un mensaje o intercambio de claves entre interlocutores.

Para poner en práctica estos procesamientos, de manera general en una entidad electrónica, se utiliza una representación particular de los puntos de la curva elíptica mediante por ejemplo una pluralidad de elementos de un cuerpo de Galois (que forma las coordenadas de punto) , tal como por ejemplo la representación proyectiva jacobiana (representación por un triplete de puntos del cuerpo de Galois Fp) o una representación proyectiva jacobiana modificada (mediante cuatro elementos o coordenadas del cuerpos de Galois Fp) , como se describe por ejemplo en el artículo "Efficient elliptic curve exponentiation using mixed coordinate" de H. Cohen, T. Ono, y A. Miyaji, en K. Ohta y P. Dinggyi, editors, Advances in Cr y ptology - ASIACRYPT '98, volumen 1514 de Lecture Notes in Computer Science, páginas 51-65. Springer, 1998.

Las operaciones en la curva elíptica se refieren entonces en efecto a operaciones en el cuerpo de Galois Fp.

De este modo por ejemplo una adición o una duplicación en la curva elíptica (operaciones que permiten por

composición realizar la multiplicación por un escalar en la curva elíptica como se describe por ejemplo en el artículo mencionado anteriormente) se realizan por la aplicación de operaciones en el cuerpo de Galois Fp en las coordenadas del o de los puntos en cuestión (debiendo estas operaciones en el cuerpo de Galois dar como resultado típicamente adiciones, sustracciones, multiplicaciones y elevaciones a una potencia 2, 3 o 4) .

Para protegerse de los ataques por canal auxiliar (en inglés "Side Channel Attacks") , tales como la observación del consumo energético de la entidad electrónica para intentar determinar las operaciones que se aplican, se ha propuesto la realización de las operaciones mencionadas anteriormente en el cuerpo de Galois entre un conjunto más amplio de operaciones, de las cuales algunas son por consiguiente ficticias, de manera que la serie de los tipos de operaciones sucesivas forma una repetición periódica de un número de tipos predeterminado, y esto, cualquiera que sea la operación en la curva elíptica en cuestión. Esta técnica se describe de manera general en la solicitud de patente FR 2 838 210 y en su aplicación a las curvas elípticas en el artículo "Low-cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity" de B. Chevallier-Mames, M. Ciet, y M. Joye, IEEE Transactions on Computers, 53 (6) : 760-768, 2004 (véase también "Aspects of Fast and Secure Arithmetics for Elliptic Curve Cr y ptography" de M. Ciet, tesis de doctorado, Universidad católica de Lovaina, junio 2003) .

En este artículo, se propone de este modo aplicar la repetición de un bloque elemental (denominado bloque atómico) formado por la sucesión de una multiplicación, una adición, una oposición y una nueva adición (siendo consideradas todas estas operaciones en el cuerpo de Galois Fp) . Como ya se ha indicado, cualquiera que sea la operación (duplicación o adición) realizada en la curva elíptica, esta operación se aplica prácticamente a la entidad electrónica 45 por la repetición de bloques elementales del mismo tipo (10 bloques en el caso de la duplicación y16 bloques en el caso de la adición) , variando sin embargo los datos manipulados de un bloque elemental a otro.

La aplicación sistemática de multiplicaciones por la entidad electrónica (con la ayuda por ejemplo de una instrucción de multiplicación dentro de un microprocesador de la entidad electrónica) , en los casos en que los dos operandos son distintos como en el que los dos operandos son idénticos, permite en este contexto utilizar con frecuencia operaciones del mismos tipo (en este caso multiplicaciones) y participan por lo tanto en la posibilidad de definir el bloque elemental que ha de repetirse.

En este contexto, la invención propone un procedimiento de procesamiento criptográfico de datos aplicado en una 55 entidad electrónica, en el que se determina, a partir de un primer punto en una curva elíptica representado mediante al menos tres primeros elementos de un cuerpo de Galois, un segundo punto en la curva elíptica representada mediante al menos tres segundos elementos del cuerpo de Galois, siendo obtenido cada uno de los segundos elementos a partir de los primeros elementos mediante un primer conjunto de operaciones que comprenden multiplicaciones y adiciones, en el que se aplica un segundo conjunto de operaciones sucesivas que tienen cada una un tipo, la serie de los tipos de operaciones sucesivas del segundo conjunto que forma una repetición periódica de una pluralidad de tipos de operación que incluyen al menos una multiplicación y una adición en el cuerpo de Galois, comprendiendo el segundo conjunto de operaciones el primer conjunto de operaciones, caracterizado porque la pluralidad de tipos de operación comprende una puesta al cuadrado en el cuerpo de Galois.

El uso de una operación de puesta al cuadrado, cuya aplicación es más rápida que una multiplicación (especialmente para un microprocesador de una entidad electrónica) , permite reducir el tiempo de aplicación de las operaciones en la curva elíptica, sin que por ello se comprometa la posibilidad de efectuar estas operaciones por la repetición de bloques elementales a tipos de operación predefinidos, contrariamente a lo que podía parecer deseable como se ha indicado anteriormente.

Dichos tres primeros elementos son por ejemplo coordenadas proyectivas jacobianas del premier punto y dichos tres segundos elementos por ejemplo coordenadas proyectivas jacobianas del segundo punto.

Según una realización considerada más adelante en la descripción, el segundo punto es el producto escalar del primer punto por un número entero; este producto escalar puede formar parte de un algoritmo criptográfico de firma 10 (por ejemplo según el protocolo ECDSA) o de intercambio de claves criptográficas (por ejemplo según el protocolo ECDH) .

Tal producto escalar es por ejemplo aplicado mediante adiciones en coordenadas proyectivas jacobianas y de duplicaciones en coordenadas proyectivas jacobianas modificadas, lo que limita el número de multiplicaciones que 15 han de efectuarse.

En una variante, el segundo punto puede ser una suma del primer punto y de un tercer punto de la curva elíptica.

La curva elíptica puede en la práctica tener por ecuación proyectiva jacobiana de Weierstrass Y2 = X3 + aXZ4 + bZ6, 20 en la que a y b son elementos del cuerpo de Galois y 4a3 + 27b2 no es el elemento nulo.

Según una realización considerable, la entidad electrónica puede ser un microprocesador, en cuyo caso cada una de dichas operaciones corresponde a una instrucción del microprocesador. En una variante, la entidad electrónica puede ser una placa de microcircuito que integra un procesador capaz de ejecutar instrucciones que corresponden a dichas operaciones.

La invención propone asimismo una entidad electrónica de procesamiento criptográfico de datos que comprende medios de procesamiento capaces de determinar, a partir de un primer punto en una curva elíptica representado mediante al menos tres primeros elementos de un cuerpo de Galois, un segundo punto en la curva elíptica 30 representado mediante al menos tres segundos elementos del cuerpo de Galois, siendo obtenido cada uno de los segundos elementos a partir de los primeros elementos mediante un primer conjunto de operaciones que comprende multiplicaciones y adiciones, siendo los medios de procesamiento capaces de aplicar un segundo conjunto de operaciones sucesivas, teniendo cada una un tipo, formando la serie de los tipos de las operaciones sucesivas del segundo conjunto una repetición periódica de una pluralidad de tipos de operación que incluyen al menos una multiplicación y una adición en el cuerpo de Galois, comprendiendo el segundo conjunto de operaciones el primer conjunto de operaciones, caracterizado porque la pluralidad de tipos de operación comprende una puesta al cuadrado en el cuerpo de Galois.

Otras características y ventajas... [Seguir leyendo]

1. Procedimiento de procesamiento criptográfico de datos aplicado dentro de una entidad electrónica, en el que se determina, a partir de un primer punto en una curva elíptica representado mediante al menos tres primeros 5 elementos de un cuerpo de Galois, un segundo punto en la curva elíptica representado mediante al menos tres segundos elementos del cuerpo de Galois, siendo obtenido cada uno de los segundos elementos a partir de los primeros elementos mediante un primer conjunto de operaciones que comprende multiplicaciones y adiciones, en el que se aplica un segundo conjunto de operaciones sucesivas que tienen cada una un tipo, formando la serie de los tipos de las operaciones sucesivas del segundo conjunto una repetición periódica de una pluralidad de tipos de operación que incluye al menos una multiplicación y una adición en el cuerpo de Galois, comprendiendo el segundo conjunto de operaciones el primer conjunto de operaciones, caracterizado porque la pluralidad de tipos de operación comprende una puesta al cuadrado en el cuerpo de Galois.

2. Procedimiento según la reivindicación 1, en el que dichos tres primeros elementos son coordenadas proyectivas 15 jacobianas del primer punto.

3. Procedimiento según la reivindicación 1 o 2, en el que dichos tres segundos elementos son coordenadas proyectivas jacobianas del segundo punto.

4. Procedimiento según una de las reivindicaciones1 a 3, en el que el segundo punto es el producto escalar del primer punto por un número entero.

5. Procedimiento según la reivindicación 4, en el que el producto escalar se aplica mediante adiciones en coordenadas proyectivas jacobianas y duplicaciones en coordenadas proyectivas jacobianas modificadas. 25

6. Procedimiento según una de las reivindicaciones1 a 3, en el que el segundo punto es la suma del primer punto y de un tercer punto de la curva elíptica.

7. Procedimiento según una de las reivindicaciones1 a 6, en el que la curva elíptica tiene por ecuación proyectiva

jacobiana de Weierstrass y2 = X3 + aXZ4 + bZ6, en la que a y b son elementos del cuerpo de Galois y 4a3 + 27b2 no es el elemento nulo.

8. Procedimiento según una de las reivindicaciones1 a 7, en el que la entidad electrónica es un microprocesador y

en el que cada una de dichas operaciones corresponde a una instrucción del microprocesador. 35

9. Entidad electrónica de procesamiento criptográfico de datos que comprende medios de procesamiento capaces de determinar, a partir de un primer punto en una curva elíptica representado mediante al menos tres primeros elementos de un cuerpo de Galois, un segundo punto en la curva elíptica representado mediante al menos tres segundos elementos del cuerpo de Galois, siendo obtenido cada uno de los segundos elementos a partir de los primeros elementos mediante un primer conjunto de operaciones que comprende multiplicaciones y adiciones, siendo los medios de procesamiento capaces de aplicar un segundo conjunto de operaciones sucesivas que tienen cada una un tipo, formando la serie de los tipos de las operaciones sucesivas del segundo conjunto una repetición periódica de una pluralidad de tipos de operación que incluyen al menos una multiplicación y una adición en el cuerpo de Galois, comprendiendo el segundo conjunto de operaciones el primer conjunto de 45 operaciones, caracterizado porque la pluralidad de tipos de operación comprende una puesta al cuadrado en el cuerpo de Galois.