DISPOSITIVO Y PROCEDIMIENTO DE EJECUCIÓN DE UN ALGORITMO CRIPTOGRÁFICO.

Dispositivo y procedimiento de ejecución de un algoritmo criptográfico. La invención concierne el ámbito de los algoritmos criptográficos destinados, en particular, a los dispositivos electrónicos comunicantes, un ejemplo de ello no restrictivo es una tarjeta inteligente. Los algoritmos criptográficos se ejecutan corrientemente en estos dispositivos para asegurar el cifrado de los datos emitidos y/o el descifrado de datos recibidos, cuando estos deben permanecer confidenciales. A tal efecto, se prevé un microprocesador apto a ejecutar el algoritmo criptográfico, asociado a una memoria fija (ROM) para registrar el programa que contiene el algoritmo y una memoria regrabable (RAM) para constituir registros y contener los datos evolutivos. Las informaciones codificadas del dispositivo transitan entre el microprocesador y una interfaz de comunicación, formando un puerto hacia el exterior. Los defraudadores tienen la posibilidad de interferir con el algoritmo criptográfico actuando a nivel de la interfaz de comunicación, o en el microprocesador y sus memorias, con el fin de romper el código para que los datos cifrados resulten inteligibles o modificar estos datos en beneficio suyo. Para minimizar este tipo de riesgo de ataque, ya se han previsto varias estrategias de protección, tanto a nivel de la realización material de los dispositivos como en los procesos de cálculo. En el ámbito de la tarjeta inteligente, entre otras cosas, existen varios ataques posibles, uno de elfos llamado ataque por falta. En este tipo de ataque, el atacante induce cualquier tipo de falta durante el cálculo de un algoritmo criptográfico, con el fin de explotar la presencia de esta falta para extraer una información secreta. Este tipo de ataque puede preverse, principalmente, con el algoritmo RSA (Rivert, Shamir, Adleman), que es el más utilizado en criptografía en este campo de aplicación. La seguridad se basa en la factorización. Se establece un número N que es el producto de dos grandes números primos p y q, sea N = p.q. Para firmar un número x que expresa un mensaje, se utiliza una clave secreta d con objeto de calcular el valor y = x d módulo N. Recordamos de manera general que un valor v expresado módulo N (abreviatura v mód N) es igual al resto inferior de N después de una sustracción de un múltiple entero de N; por ejemplo 11 módulo 3 = 2, sea el resto inferior a 3 después de la sustracción del múltiplo 3 veces 3. Para comprobar que la firma del código es correcta, se utiliza una clave correspondiente, dicha clave pública, es un exponente e. Se comprueba simplemente que x = y e mód N es igual al valor constitutivo del mensaje. La figura 1 ilustra el proceso de cálculo de la firma y = x d módulo N utilizando el teorema de los restos chinos (TRC). El teorema de los restos chinos es conocido igualmente por su denominación anglosajona Chinese remainder theorem (CRT). Para ahorrar tiempo, ejecución cuatro veces más rápida del algoritmo, no se efectúan los cálculos directamente en el módulo N, sino que se efectúan en primer lugar los cálculos módulo p y módulo q. Se designan los valores de x módulo p y x módulo q respectivamente por xp y xq. Por otra parte, se designa por dp el valor d módulo (p-1), y por dg el valor d módulo (q-1). Se efectúa el cálculo módulo p por cálculo de y p = x p exponente dp módulo p. Del mismo modo, se calcula módulo el valor yq = xq exponente dq módulo q. Después de haber obtenido los valores yp e yq respectivamente módulo p y módulo q, volvemos a combinarlos con el teorema de los restos chinos para obtener el valor citado anteriormente. Supongamos ahora que un atacante, que emplee cualquier tipo de método, induce un error durante el cálculo de yp, pero no durante el cálculo de yq. Esto implicaría que el valor de yp fuese incorrecto. El hecho de que se trate de un valor incorrecto está indicado por un acento circunflejo encima del y en la figura 1. En cambio, el valor de y q será correcto. Por esta razón, cuando el TRC vuelva a combinar los valores ^y p e y q, la firma que de ello resulte será incorrecta. Si el atacante conoce el valor de la clave pública de verificación e, puede calcular el valor ^y e - x módulo N. Por otra parte, tenemos la firma correcta, y, igual a x d módulo N. A partir de la relación preestablecida x = y e , el atacante sólo tiene que calcular ^y e - x módulo N. Extraerá el mayor común divisor (pgcd) con N, sea: pgdc (^y e - x mód. N,N) = q. Entonces obtiene el factor secreto q. Como consecuencia, el código RSA está efectivamente roto. Dicho de otro modo, si alguien es capaz de inducir cualquier tipo de error durante un cálculo módulo p cuando el cálculo módulo q es correcto, puede romper completamente el código RSA. Una primera contramedida para evitar este tipo de situación consiste en recalcular el conjunto del algoritmo. Se comparan los valores obtenidos de los sucesivos cálculos. Si son idénticos, se supone que no ha habido ningún error 2 ES 2 371 333 T3 inducido. Un problema con este modo de proceder radica en que no detecta una falta permanente. Por ejemplo, no se podrá descubrir un ataque en el que el error inducido consiste en forzar sistemáticamente un bit de un estado lógico determinado. Otro método que pretende esquivar este ataque se basa en una comprobación. Se obtiene una firma que la calcula el TRC. A continuación, se comprueba que la firma sea correcta y que la clave pública sea la adecuada. Este enfoque es muy fiable, pero el algoritmo de firma no conoce siempre la clave de comprobación e, lo que impide poder emplearla en algunas aplicaciones. Otro inconveniente de este método es que si e es grande, implica dos exponenciaciones. La firma será entonces dos veces más lenta. Un tercer método descrito en el documento US-A-6 144 740, consiste en modificar el valor x multiplicándolo por un aleatorio y asegurándose más tarde en el cálculo de x^d que el valor es divisible por dicho aleatorio. Un inconveniente primordial de este método radica en la necesidad de emplear operaciones de inversión modular y/o división conocidas por ser costosas en tiempo de ejecución. Según otra contramedida al ataque por falta descrita por Shamir en el documento de la patente WO 98/52319, se emplea el siguiente algoritmo: 1. Elegir un número aleatorio r de poco valor, 2. Calcular: y rp = x d mód rp, y yrq = x d mód rq, 3. Si y rp y rq (mód r), entonces hay un error, (quizá sea inducido por un ataque y, por consiguiente se interrumpe el algoritmo, en caso contrario; 4. Emitir a la salida: y = TRC (yrp mód p, qrq mód q). De este modo, para un número aleatorio r, en vez de calcular módulo p, se calcula módulo r.p. y módulo r.q. Seguidamente, se comprueba que estos dos valores sean iguales al módulo r. Si estos dos valores son diferentes, es seguro que existe un error. En cambio, si son iguales, podemos suponer que no se ha producido ningún error, con una probabilidad de 1/r de equivocarse en esta suposición. Un inconveniente de este método es que se calcula yrp = x d mód rp, y no x dp mód rp. Ahora bien, el valor d al tamaño del módulo, es generalmente un número de 1024 bits, mientras que dp es un número del tamaño de la mitad del módulo, lo que representa 512 bits en el ejemplo. Esto implica que en el esquema normal, sin detección de falta, se efectúa una primera exponenciación con un expositor y un módulo de 512 bits, y una segunda exponenciación con un expositor y un módulo de 512 bits. En cambio, con el método de contramedida según el documento patente 5.633.929, no se utilizará dp, sino d. Esto implica que el expositor tendrá un tamaño de 1024 bits por cada lado. Por consiguiente, se pierde en eficacia. Otro inconveniente del método Shamir es que sólo funciona para el modo de cálculo basado en el TRC. Ahora bien, también es posible calcular directamente x d módulo n, es decir, sin recurrir al teorema de los restos chinos. En efecto, existen dos maneras de almacenar la clave secreta. Sea, se guarda el valor d, sea se guardan los valores dp, dq, p y q. Cuando se calcula directamente, se utiliza el modo estándar; cuando se calcula módulo p y módulo q, se utiliza el modo TRC. Habida cuenta de lo que precede, la invención propone contramedidas, en particular, a los ataques por defecto, que autorizan exponenciaciones con un expositor del tamaño del módulo y que puedan adaptarse al modo estándar o al modo TRC. Más concretamente, la invención concierne, según un primer objeto, un dispositivo de ejecución de un algoritmo criptográfico que incluye medios de cálculo, medios de memorización de datos y medios de comunicación de datos. Según la invención, los medios de memorización contienen valores determinados r, p, q, dp y, dq, una función predeterminada f(x) de un valor x, donde f(x) es igual a x^d, d es una clave privada, así como un algoritmo del... [Seguir leyendo]

1. Dispositivo (1) de ejecución de un algoritmo criptográfico que incluye medios de cálculo (2), medios de memorización de datos (4, 6) y medios de comunicación de datos (8) y un valor determinado r caracterizado porque los medios de memorización (4, 6) contienen: valores determinados p, q, dp y, dq, una función predeterminada f(x) de un valor x, donde f(x) es igual a x^d, d es una clave privada, así como un algoritmo que utiliza el teorema de los restos chino (TRC) que permiten a los medios de cálculo (2) establecer: - un valor zp igual a x^dp, mód p*r y un valor zq es igual a x^dq, mód q*r; - un valor b p igual a z p^d q mód r y un valor b q es igual a z q^d p mód r; - se constata un error en el cálculo si el valor de bp mód r no es igual al valor de bq mód r; - un valor es igual a TRC [Zp mód p, zq mód q] si no se ha constatado ningún error. 2. Dispositivo de ejecución de un algoritmo criptográfico según la reivindicación 1, caracterizado porque un entero dp igual a dp+r1* [p-1] pueda utilizarse en vez de un entero dp, r1 es un entero aleatorio. 3. Dispositivo de ejecución de un algoritmo criptográfico según la reivindicación 1, caracterizado porque un entero x+t*N puede utilizarse en lugar de x, siendo t un entero aleatorio y N igual a p*q. 4. Dispositivo de ejecución de un algoritmo criptográfico según cualquiera de las reivindicaciones 1 a 3, caracterizado porque: - el valor de y pueda ser igual a TRC[zp mod p, zq mod q]; - puede establecerse una constatación de un error de cálculo si el valor de [y-z p]* [y-z q] es diferente de 0 módulo N, siendo igual a p*q; - el valor y sólo puede enviarse si no se ha constatado ningún error. 5. Dispositivo de ejecución de un algoritmo criptográfico según la reivindicación 4, caracterizado porque los medios de cálculo establecen: - un valor = [y-z p] mod p*r y un valor ß = [y-z q] mod q*r; - un valor que es el doble del tamaño del entero r expresado en número de bits; - un valor t = *ß/N mód 2^; - cuando se constata un error de cálculo si = *ß-t*N es diferente de 0 y porque el valor y sólo se envía si no se ha constatado ningún error. 6. Dispositivo según cualquiera de las reivindicaciones 1 a 5, caracterizado porque el algoritmo es del tipo RSA (Rivert, Shamir, Adleman). 7. Dispositivo según cualquiera de las reivindicaciones 1 a 6, caracterizado porque interrumpe la comunicación de datos en caso de que se constate un error establecido durante dichos cálculos. 8. Dispositivo según cualquiera de las reivindicaciones 1 a 7, caracterizador porque se trata de una tarjeta inteligente (1). 9. Procedimiento de ejecución de un algoritmo criptográfico caracterizado porque comprende, a partir de valores determinados r, p, q, dp y dq, de una función predeterminada f(x) de un valor x tal que f(x) es igual a x^d, d es una clave privada, y un algoritmo que utiliza el teorema de los restos chinos (TRC), las siguientes etapas: - Calcular un valor z p igual a x^d p mód p*r y un valor de z q igual a x^d q mód q*r; - Calcular un valor bp igual a zp^dq mód r y un valor de bq igual a zq^dp mód r; - Determinar un error constatado en el cálculo si el valor de b p mód r no es igual al valor de b q mód r; 8 ES 2 371 333 T3 - Calcular un valor y igual a TRC (zp mód p, zq mód q) si no se ha constatado ningún error. 10. Procedimiento de ejecución de un algoritmo criptográfico según la reivindicación 9, caracterizador porque el cálculo de un entero dp igual a dp+r1* [p-1] pueda utilizarse en vez de un entero dp, r1 es un entero aleatorio. 11. Procedimiento de ejecución de un algoritmo criptográfico según la reivindicación 9, caracterizado porque el cálculo de un entero x+t*N se utiliza en vez de x, siendo t un entero aleatorio y N igual a p*q. 12. Procedimiento de ejecución de un algoritmo criptográfico según cualquiera de las reivindicaciones 9 a 11, caracterizador porque incluye además las siguientes etapas: - calcular un valor y igual a TRC[z p mod p, z q mod q]; - constatar un error de cálculo si el valor de [y-zp]* [y-zq] es diferente de 0 módulo N, siendo N igual a p*q; - reenviar el valor y si no se ha constatado ningún error. 13. Procedimiento de ejecución de un algoritmo criptográfico según la reivindicación 9, caracterizado porque incluye además las siguientes etapas: - calcular un valor igual a [y-zp] mod p*r y un valor ß igual a [y-zq] mod q*r; - determinar un valor que es el doble del tamaño del entero r expresado en número de bits; - calcular un valor igual *ß/N mód 2^; siendo N igual a p*q - determinar un error de cálculo si *ß-t*N es diferente de 0. - reenviar el valor y si no se ha constatado ningún error. 9 ES 2 371 333 T3 ES 2 371 333 T3 11