PROCEDIMIENTO DE TRATAMIENTO DE DATOS QUE IMPLICA UNA EXPONENCICION MODULAR Y UN DISPOSITIVO ASOCIADO.

Procedimiento de tratamiento criptográfico de datos, en el cual un mensaje (m) es sometido a una primera operación con una clave secreta (d),

que comprende una etapa de actualización por una segunda operación de una primera variable (B; a0; S''p, S''q), o de una segunda variable (A; a1; Sp, Sq) según que un bit correspondiente de la clave secreta valga 0 o 1, caracterizado por una etapa de prueba (E116, E210; E308) de una relación entre un primer valor (B; a0; S'') resultante de la primera variable y un segundo valor (A; a1; S) resultante del asegunda variable, con el fin de detectar un fallo en el transcurso del cálculo

Procedimiento de tratamiento de datos que implica una exponenciación modular y un dispositivo asociado.

La invención se refiere a un procedimiento de tratamiento de datos que implica una exponenciación modular, y a un dispositivo asociado.

Los cálculos de exponenciación modular se utilizan frecuentemente en los algoritmos criptográficos y en este marco hacen intervenir en general un secreto, es decir un número almacenado por el dispositivo que pone en práctica el algoritmo criptográfico y que no es accesible desde el exterior.

Las etapas que ponen en práctica la exponenciación modular son particularmente objeto de ataques por parte de personas malintencionadas; puede tratarse de ataques por generación de fallo (especialmente del tipo DFA del inglés "Differential Fault Analysis") o por análisis del consumo de corriente del dispositivo que pone en práctica el algoritmo (del tipo SPA del inglés "Statistical Power Analysis" o DPA del inglés "Differential Power Analysis").

Debido a esto, se ha buscado ya proteger estas etapas, en particular en el caso en que el secreto que hay que proteger corresponde al exponente utilizado en la exponenciación modular.

Así, cuando se utiliza un algoritmo del tipo "square-and-multiply" (término inglés que significa "elevación al cuadrado y multiplicación") en el cual una variable es actualizada por multiplicación para cada bit del exponente que vale 1 (y solamente para estos bits), se ha buscado simetrizar el proceso, por ejemplo efectuando una multiplicación engañosa cuando el bit vale 0, con el fin de hacer frente a los ataques por medición de corriente (indicados a veces por SPA) o por medición de tiempo ("timing attacks").

Partiendo de esta idea general, se han desarrollado diversos algoritmos protegidos contra los ataques de tipo SPA, tales como el descrito en el artículo "The Montgomery Powering Ladder", de B.S. Kaliski Jr., C.Q. Koç y C. Paar, "Cryptographic Hardware and Embedded Systems" - CHES 2002, páginas 291-302.

Por otra parte, se ha buscado proteger los algoritmos criptográficos, y entre estos aquéllos que utilizan una exponenciación modular, de los ataques por fallos, por medio de los cuales un atacante intenta deducir informaciones sobre el funcionamiento interno que pone en práctica el procedimiento criptográfico generando un fallo de funcionamiento en el seno de este procedimiento.

Una solución utilizada habitualmente para luchar contra este último tipo de ataques consiste en doblar los cálculos efectuados con el fin de verificar que las dos iteraciones del mismo cálculo dan el mismo resultado, lo que en general tiende a probar que no se ha producido ningún fallo durante su desarrollo. Esta solución no obstante implica doblar el tiempo de cálculo para cada operación que se desee proteger (sin contar la subsiguiente etapa necesaria de verificación) lo que naturalmente no es deseable.

Con el fin de poner remedio a este inconveniente, la solicitud de patente WO 98/52319 propone, cuando se utiliza el teorema chino de los restos (o CRT del inglés "Chinese Remanider Theorem"), aprovechar la identidad supuesta de dos valores obtenidos cada uno en una de las derivaciones del algoritmo que utiliza este teorema para verificar anticipadamente el desarrollo sin fallos del algoritmo en sus dos derivaciones.

Esta solución, que se aprovecha de una particularidad de las puestas en práctica que utilizan el teorema chino de los restos, no es aplicable sin embargo a otros tipos de implementación. Por otra parte, puede recodarse a este respecto que la utilización del teorema chino de los restos implica el conocimiento de la descomposición en números primos p, q del módulo público n = p.q.

Finalmente, esta solución practica una verificación por medio de datos empleados en una etapa intermedia del proceso y, por tanto, no permite una verificación del funcionamiento sin fallo en cualquier punto del proceso, como podría desearlo el diseñador: por ejemplo, esta técnica no permite proteger el procedimiento en caso de ataques por fallo durante la recombinación del resultado obtenido por cada una de las derivaciones del algoritmo.

Con el fin de mejorar esta situación y, por tanto, de proponer un procedimiento de tratamiento de datos que implique una exponenciación modular protegida a la vez contra los ataques por análisis de corriente y los ataques por fallo, la invención propone un procedimiento de tratamiento (en general criptográfico) de datos, en el cual un mensaje es sometido a una primera operación, por ejemplo, con una clave secreta, que comprende una etapa de actualización por una segunda operación de una primera variable o de una segunda variable según que un bit correspondiente del operando valga 0 o 1, caracterizado por una etapa de prueba de una relación entre un primer valor resultante de la primera va- riable y un segundo valor resultante de la segunda variable, con el fin de detectar un fallo en el transcurso del cálculo.

En efecto, debido a la complementariedad de las actualizaciones de la primera variable y de la segunda variable, existe una relación que normalmente debe ser verificada entre las dos variables, o entre los valores que resultan de éstas. Por el contrario, la no-verificación de la prueba indica entonces un fallo en el transcurso del cálculo y de esta manera permite detectar un ataque, incluso cuando el ataque va dirigido contra una operación engañosa (caso de ataques "safe error").

El primer valor y el segundo valor son precisamente aquéllos de la primera variable y de la segunda variable; en este caso, la primera variable y la segunda variable pueden ser utilizadas ellas mismas para la prueba, lo que implica especialmente una ganancia de memoria.

La primera operación es, por ejemplo, una exponenciación modular, en cuyo caso la segunda operación es una multiplicación modular y el operando es un exponente.

La etapa de prueba puede comprender entonces la comparación del producto de la primera variable y de la segunda variable con una tercera variable actualizada cualquiera que sea el bit correspondiente del operando.

Una etapa de prueba alternativa comprende la comparación de la primera variable con el producto del elemento y de la segunda variable.

De acuerdo con otra realización posible, la primera operación es una multiplicación a lo largo de una curva elíptica y la segunda operación es una suma a lo largo de la curva elíptica.

La relación puede ser independiente del operando, lo que permite simplificar la etapa de prueba.

La etapa de verificación puede aplicarse especialmente al resultado de la primera operación, es decir después de las etapas de cálculo que implican la segunda operación.

El procedimiento puede comprender igualmente una etapa de verificación de la relación para cada bit del operando. Se detecta, así, un eventual ataque por fallo en cuanto éste haya perturbado un cálculo que pone en práctica la segunda operación, lo que garantiza un buen nivel de seguridad a todo lo largo de las etapas que ponen en práctica la primera operación.

De acuerdo con un modo de puesta en práctica posible, el primer valor resulta de una primera recombinación según el teorema chino de los restos que implica a la primera variable y el segundo valor resulta de una segunda recombinación según el teorema chino de los restos que implica a la segunda variable.

La invención propone igualmente un dispositivo de tratamiento de datos que permite una primera operación sobre un mensaje por medio de una clave secreta, que comprende medios de actualización por una segunda operación de una primera variable o de una segunda variable según que un bit correspondiente del operando valga 0 o 1, caracterizado por medios de prueba de una relación entre la primera y la segunda variable, con el fin de detectar un fallo en el transcurso del cálculo.

Un dispositivo de este tipo está incluido por ejemplo en una tarjeta de microcircuito.

Otras características y ventajas de la invención se pondrán de manifiesto a la luz de la descripción que sigue, hecha refiriéndose a los dibujos anejos, en los cuales:

- la figura 1 representa un procedimiento de tratamiento de datos de acuerdo con un primer modo de realización de la invención;

- la figura 2 representa un procedimiento de tratamiento de datos de acuerdo con un segundo modo de realización de la invención;

- la figura 3 representa un procedimiento de tratamiento...

1. Procedimiento de tratamiento criptográfico de datos, en el cual un mensaje (m) es sometido a una primera operación con una clave secreta (d), que comprende una etapa de actualización por una segunda operación de una primera variable (B; a₀; S'_p, S'_q), o de una segunda variable (A; a₁; S_p, S_q) según que un bit correspondiente de la clave secreta valga 0 o 1, caracterizado por una etapa de prueba (E116, E210; E308) de una relación entre un primer valor (B; a₀; S') resultante de la primera variable y un segundo valor (A; a₁; S) resultante del asegunda variable, con el fin de detectar un fallo en el transcurso del cálculo.

2. Procedimiento de acuerdo con la reivindicación 1, caracterizado porque el primer valor es el valor de la primera variable y porque el segundo valor es el valor de la segunda variable.

3. Procedimiento de acuerdo con las reivindicaciones 1 o 2, caracterizado porque la etapa de prueba (E116) es aplicada al resultado de la primera operación.

4. Procedimiento de acuerdo con la reivindicación 1, caracterizado porque el primer valor (S') resulta de una primera recombinación según el teorema chino de los restos que implica a la primera variable (S'_p, S'_q) y porque el segundo valor S resulta de una segunda recombinación según el teorema chino de los restos que implica a la segunda variable (S_p, S_q).

5. Procedimiento de acuerdo con una de las reivindicaciones 1 a 4, caracterizado porque la primera operación es una exponenciación modular, porque la segunda operación es una multiplicación modular y porque la clave secreta es un exponente.

6. Procedimiento de acuerdo con la reivindicación 5, caracterizado porque la etapa de prueba comprende la comparación del producto de la primera variable (B) y de la segunda variable (A) con una tercera variable (S) actualizada por el cálculo de un cuadrado, cualquiera que sea el bit correspondiente de la clave secreta.

7. Procedimiento de acuerdo con la reivindicación 5, caracterizado porque la etapa de prueba comprende la comparación de la segunda variable (a₁) con el producto del elemento (m) y de la primera variable (a₀).

8. Procedimiento de acuerdo con una de las reivindicaciones 1 a 4, caracterizado porque la primera operación es una multiplicación a lo largo de una curva elíptica y porque la segunda operación es una suma a lo largo de la curva elíptica.

9. Procedimiento de acuerdo con una de las reivindicaciones 1 a 8, caracterizado porque la relación es independiente de la clave secreta.

10. Dispositivo de tratamiento criptográfico de datos que permite una primera operación sobre un mensaje por medio de una clave secreta, que comprende:

- medios de actualización por medio de una segunda operación de una primera variable o de una segunda variable según que un bit correspondiente de la clave secreta valga 0 o 1,

caracterizado por:

- medios de prueba de una relación entre un primer valor resultante de la primera variable y un segundo valor resultante de la segunda variable, con el fin de detectar un fallo en el transcurso del cálculo.

11. Dispositivo de acuerdo con la reivindicación 10, caracterizado porque el primer valor es el valor de la primera variable y porque el segundo valor es el valor de la segunda variable.

12. Dispositivo de acuerdo con las reivindicaciones 10 u 11, caracterizado porque los medios de prueba son aplicados al resultado de la primera operación.

13. Dispositivo de acuerdo con la reivindicación 10, caracterizado por medios para obtener el primer valor (S') como resultado de una primera recombinación según el teorema chino de los restos que implica a la primera variable (S'_p, S'_q) y por medios para obtener el segundo valor (S) como resultado de una segunda recombinación según el teorema chino de los restos que implica a la segunda variable (S_p, S_q).

14. Dispositivo de acuerdo con una de las reivindicaciones 10 a 13, caracterizado porque la primera operación es una exponenciación modular, porque la segunda operación es una multiplicación modular y porque la clave secreta es un exponente.

15. Dispositivo de acuerdo con la reivindicación 14, caracterizado porque los medios de prueba comprenden medios de comparación del producto de la primera variable (B) y de la segunda variable (A) con una tercera variable (S) actualizada por el cálculo de un cuadrado, cualquiera que sea el bit correspondiente de la clave secreta.

16. Dispositivo de acuerdo con la reivindicación 14, caracterizado porque los medios de prueba comprenden medios de comparación de la primera variable (a₁) con el producto del elemento (m) y de la segunda variable (a₀).

17. Dispositivo de acuerdo con una de las reivindicaciones 10 a 13, caracterizado porque la primera operación es una multiplicación a lo largo de una curva elíptica y porque la segunda operación es una suma a lo largo de la curva elíptica.

18. Dispositivo de acuerdo con una de las reivindicaciones 10 a 17, caracterizado porque la relación es independiente de la clave secreta.

19. Tarjeta de microcircuito que comprende un dispositivo de acuerdo con una de las reivindicaciones 10 a 18.