Procedimiento para la determinación segura de datos.

Procedimiento para la determinación segura de datos, en el que en un primer procesador se aplica una operación matemática con una clave en un punto de una curva elíptica,

pudiendo representarse la clave como número binario con una secuencia de bits (bi),

- con una primera orden (x) que da lugar en otro procesador a una primera operación (X) en al menos un contenido de registro y una segunda orden (y), que da lugar en el otro procesador a una segunda operación (Y), que incluye las etapas:

- determinación de al menos un valor (d) en función de ambas órdenes (x, y);

- inicialización de una primera magnitud auxiliar (R) y de una segunda magnitud auxiliar (S);

- secuencialmente para cada bit (bi) de la clave, realización de las siguientes etapas:

(a) transmisión de la primera magnitud auxiliar (R) a un primer registro y de la segunda magnitud auxiliar (S) a un segundo registro del otro procesador,

(b) en función del valor del bit (bi) y de al menos un valor (d), asignación de una orden a una variable de salida (A) tal que

* bien se asigna la primera orden (x),

* o bien se asigna la segunda orden (y),

(c) transmisión de la variable de salida (A) al registro de órdenes del otro procesador,

(d) determinación de la primera (R) y segunda (S) magnitud auxiliar actualizadas en el otro procesador,

- tras finalizar las etapas para los bits (bi), emisión de la primera (R) y/o de la segunda (S) magnitud auxiliar y determinación de un resultado de la operación matemática procedente de la primera (R) y/o de la segunda magnitud auxiliar (S),

conduciendo la primera operación (X) sobre contenidos del registro del otro procesador, que está asignado a la primera orden (x), a un intercambio de los contenidos del primer y del segundo registro y en el que la segunda operación (Y) sobre contenidos del registro del otro procesador, que está asignado a la segunda orden (y), no conduce a ningún intercambio de contenidos en el primer y el segundo registro.

Procedimiento para la determinación segura de datos.

La invención se refiere a un procedimiento para la determinación segura de datos, en el que en un primer procesador se aplica una operación matemática con una clave en un punto de una curva elíptica, pudiendo representarse la clave como número binario con una secuencia de bits (bi) .

Los sistemas criptográficos asimétricos garantizan mediante el establecimiento de pares de claves formados por una clave privada y una clave pública un elevado nivel de seguridad en el sentido de que para un atacante es casi imposible decodificar en un tiempo finito la clave privada o el mensaje codificado con clave pública. Los sistemas criptográficos usuales, como por ejemplo los que se basan en curvas elípticas, se basan en una codificación que puede realizarse en tiempo polinómico, pero que sólo puede invertirse en tiempo exponencial respecto a la longitud de la clave en bits. En sistemas basados en curvas elípticas se utilizan hoy en día longitudes de claves de n = 160 a 192 bits y en los sistemas basados en algoritmos RSA han de utilizarse al respecto longitudes de n = 1024 a 1536 bits para un nivel de seguridad aproximadamente igual.

Así los procedimientos criptográficos en base a curvas elípticas son de mayor rendimiento y precisan de una inferior anchura de banda para transmitir los parámetros del sistema que otros procedimientos criptográficos para un grado comparable de seguridad alcanzable.

Como ejemplo citaremos aquí el conocido procedimiento Diffie-Hellman para acordar una clave común entre dos interlocutores de comunicación basándose en el contorno de curvas elípticas. Aquí conoce el primer interlocutor de la comunicación A un parámetro de seguridad ra y el segundo interlocutor de la comunicación B un parámetro de seguridad rb. Una vez que ambos interlocutores de la comunicación se han puesto de acuerdo sobre una curva elíptica y sobre un punto común P situado en esta curva elíptica, determina el interlocutor de la comunicación A un valor Qa = ra * P

y el interlocutor de la comunicación B un valor

Qb = rb * P.

A continuación de ello transmite el interlocutor de la comunicación A el valor Qa al interlocutor de la comunicación B y el interlocutor de la comunicación B el valor Qb al interlocutor de la comunicación A. En otra multiplicación escalar determina ahora el interlocutor de la comunicación A la clave común K = ra * Qb = ra * rb * P

y el interlocutor de la comunicación B la misma clave común

K = rb * Qa = rb * ra * P.

Estas multiplicaciones escalares forman así un módulo esencial en procedimientos criptográficos en base a curvas elípticas. Especialmente ventajosa es la aplicación de curvas elípticas, ya que la operación de inversión, es decir, la determinación de un escalar ra, b a partir del conocimiento de los puntos Qa, b y P, tal que Qa, b = rab sólo puede calcularse con un coste de cálculo considerable. Según el estado actual de conocimientos, puede calcularse la multiplicación escalar en tiempo polinómico, pero sólo puede invertirse en tiempo exponencial.

No obstante, los procedimientos criptográficos conocidos en base a curvas elípticas son vulnerables mediante los llamados ataques de canal lateral. Estos son una alternativa a los métodos de ataque en basados en la inversión de la codificación, para romper de la manera más eficiente posible el algoritmo que sirve de base a la codificación. Los mismos pueden utilizarse en particular en medios auxiliares móviles como por ejemplo smartcards (tarjetas inteligentes)

o dongles (candados electrónicos) en los que está memorizado material secreto de claves, para posibilitar un intercambio codificado de mensajes o generar firmas digitales o decodificar mensajes.

El atacante aprovecha la accesibilidad relativamente fácil de líneas de datos de los correspondientes circuitos para medir magnitudes físicas como intensidad, emisión electromagnética, resultados en faltas inducidas o tiempos de recorrido de determinados cálculos. En una evaluación inmediata de los valores de medida en base a un sencillo análisis de la intensidad (SPA) o mediante registro de valores de medida como la intensidad mediante un osciloscopio de memoria y subsiguiente evaluación estadística, pueden obtenerse de manera eficiente informaciones sobre los algoritmos que sirven de base o en el peor de los casos informaciones sobre una clave existente en ese momento.

Esto último se describirá más en detalle en base a un ejemplo: Un procedimiento para la codificación prevé tanto para algoritmos basados en curvas elípticas como también para los basados en el procedimiento RSA la aplicación de una operación matemática.

En el caso de las curvas elípticas ha de realizarse una multiplicación escalar

Q = k * P

como operación matemática, siendo P un punto sobre una curva elíptica sobre un cuerpo finito K y k de nuevo una clave o una magnitud derivada de la misma.

Una posible conversión de la multiplicación escalar puede realizarse implementando el siguiente algoritmo sobre una unidad operativa, estando predeterminada la clave k por una representación binaria (bi, i = n-1…0) :

Algoritmo 1: EC curva elíptica: Q = k * P

(1.1) Q + 0

(1.2) i + n-1

(1.3) siempre que i > -1

(1.3.1) Q + 2 * Q

(1.3.2) en el caso de que bi = 1 entonces Q + Q + P

(1.3.3) i + i - 1

(1.4) da como resultado Q

En el caso de un análisis sencillo de la intensidad (SPA) , se analiza el perfil del consumo de corriente de una multiplicación escalar. La multiplicación escalar está compuesta principalmente por adiciones y duplicaciones. Las operaciones se diferencian no obstante considerablemente en la cantidad de operaciones elementales en K, con lo que también es diferente el consumo de corriente. Por lo tanto mediante el correspondiente ataque de canal lateral pueden deducirse los bits individuales y con ello la propia representación binaria de k.

Un posible paso para defenderse de tales ataques consiste en igualar los flujos de corriente y tiempos de recorrido del cálculo dependiente del valor del correspondiente bit para ambos estados posibles del bit 0 y 1, tal como se muestra a continuación es:

Un punto P de una curva elíptica E viene definido por su coordenada x y su coordenada y. En base a la ecuación de la curva elíptica E existen para un valor x como máximo dos valores y diferentes y1 e y2, con lo que los puntos (x, y1) y (x, y2) son puntos de la curva elíptica E. Para fijar así un punto sobre la curva elíptica E inequívocamente, es necesario además de la coordenada x adicionalmente sólo un bit como información adicional.

En el caso de una curva elíptica E sobre cuerpos primos finitos, es suficiente por ejemplo el llamado Least Significant Bit (LSB, el bit menos significativo) de la coordenada y o bien el signo de la coordenada y del punto correspondiente como información adicional.

Estas características de curvas elípticas se utilizan en el llamado algoritmo Montgomer y -Leiter, que representa un método común para implementar la multiplicación escalar sobre curvas elípticas. El algoritmo Montgomer y -Leiter puede implementarse tal que para calcular la coordenada x de un múltiplo escalar de un punto P sólo se utiliza la coordenada x de P. Puesto que el Montgomer y -Leiter es a la vez, tal como mostraremos a continuación, un método muy bueno para contrarrestar análisis de intensidad sencillos, se implementa el mismo a menudo en criptosistemas que corren sobre Embedded Systems (sistemas embutidos) .

Según el procedimiento descrito a continuación de un algoritmo Montgomer y -Leiter, se calcula un múltiplo k * P de un punto P que se encuentra sobre una curva elíptica.

El escalar k = (bn-1, …, bi, …, b0) , que se da en representación binaria, se procesa por bits, comenzando en el llamado Most Significant Bit (MSB, N1) o bit más significativo.

Algoritmo 2: EC -curva elíptica: Q = k*P Montgomer y -Leiter (2.1) R + P, S + 0

(2.2) i + n-1

(2.3) siempre que i > -1

(2.3.1 en el caso de que bi = 1: {S + S + R, R + 2 * R}

(2.3.2) caso contrario (R + R + S, S + 2 * S)

... [Seguir leyendo]

1. Procedimiento para la determinación segura de datos, en el que en un primer procesador se aplica una operación matemática con una clave en un punto de una curva elíptica, pudiendo representarse la clave como número binario con una secuencia de bits (bi) , -con una primera orden (x) que da lugar en otro procesador a una primera operación (X) en al menos un contenido de registro y una segunda orden (y) , que da lugar en el otro procesador a una segunda operación (Y) , que incluye las etapas:

- determinación de al menos un valor (d) en función de ambas órdenes (x, y) ; -inicialización de una primera magnitud auxiliar (R) y de una segunda magnitud auxiliar (S) ; -secuencialmente para cada bit (bi) de la clave, realización de las siguientes etapas:

(a) transmisión de la primera magnitud auxiliar (R) a un primer registro y de la segunda magnitud auxiliar (S) a un segundo registro del otro procesador,

(b) en función del valor del bit (bi) y de al menos un valor (d) , asignación de una orden a una variable de salida (A) tal que

• bien se asigna la primera orden (x) , • o bien se asigna la segunda orden (y) ,

(c) transmisión de la variable de salida (A) al registro de órdenes del otro procesador,

(d) determinación de la primera (R) y segunda (S) magnitud auxiliar actualizadas en el otro procesador,

- tras finalizar las etapas para los bits (bi) , emisión de la primera (R) y/o de la segunda (S) magnitud auxiliar y determinación de un resultado de la operación matemática procedente de la primera (R) y/o de la segunda magnitud auxiliar (S) ,

conduciendo la primera operación (X) sobre contenidos del registro del otro procesador, que está asignado a la primera orden (x) , a un intercambio de los contenidos del primer y del segundo registro y en el que la segunda operación (Y) sobre contenidos del registro del otro procesador, que está asignado a la segunda orden (y) , no conduce a ningún intercambio de contenidos en el primer y el segundo registro.

2. Procedimiento según la reivindicación 1, en el que la primera magnitud auxiliar (R) representa un punto sobre una curva elíptica sobre un cuerpo finito y en la etapa de la inicialización recibe la asignación de un punto fijo (P) .

3. Procedimiento según una de las reivindicaciones 1 a 2, en el que la segunda magnitud auxiliar (S) representa un punto sobre una curva elíptica sobre un cuerpo finito y en la etapa de la inicialización recibe la asignación de un valor 0.

4. Procedimiento según una de las reivindicaciones 1 a 3, en el que la operación matemática incluye una multiplicación escalar (k*P) .

5. Procedimiento según una de las reivindicaciones 1 a 4, en el que la actualización realizada en el otro procesador de la primera (R) y segunda (S) magnitud auxiliar incluye las siguientes etapas, -en una primera operación de cálculo se realiza una adición de dos puntos sobre una curva elíptica, -y en una segunda operación de cálculo se realiza una multiplicación escalar de un punto sobre una curva elíptica por un factor 2 o bien la adición consigo mismo,

- y la determinación de las magnitudes auxiliares primera y segunda actualizadas se realiza tal que en función del valor del bit (bi) se asigna en cada caso un resultado de la primera y segunda operación de cálculo a una de ambas magnitudes auxiliares (R, S) .

6. Procedimiento según una de las reivindicaciones 1 a 5, en el que el valor (d) es un valor diferencial procedente de la diferencia de la representación de bits entre ambas órdenes (x, y) .

7. Procedimiento según la reivindicación 6, en el que en la etapa (b) el valor diferencial (d) se añade a la primera orden (x) en función del valor del bit actual (bi) , sucediendo que -se forma una primera palabra de ordenador (h1) , que contiene el bit actual (bi) en el procesamiento secuencial; -la primera palabra del ordenador (h1) se multiplica por el valor diferencial (d) para formar un primer producto (m1) ; -se determina un primer valor intermedio a partir de una adición del primer producto (m1) a la primera orden (x) , -a partir de la primera palabra de ordenador (h1) se forma una segunda palabra de ordenador (h2) , en la que el bit

se coloca en la posición del bit actual (bi) en cero; -la segunda palabra de ordenador (h2) se multiplica por el valor diferencial (d) para formar un segundo producto (m2) ;

- la variable de salida (A) se determina a partir de una sustracción del segundo producto (m2) del primer resultado intermedio,

- tal que la variable de salida (A)

• bien se asigna a la primera orden (x) , • o bien se asigna a la segunda orden (y) .

8. Procedimiento según la reivindicación 6, en el que en la etapa (b) en función del valor del bit (bi) se sustrae el valor diferencial (d) de la segunda orden (y) , tal que la variable de salida (A)

• bien se asigna a la primera orden (x) , • o bien se asigna a la segunda orden (y) .

9. Procedimiento según una de las reivindicaciones 1 a 8, en el que el bit actual (bi) es en el procesamiento secuencial el bit menos significativo (LSB) .

10. Procedimiento según una de las reivindicaciones a 1 a 9, en el que -la primera orden (x) da lugar a la transmisión del contenido de un tercer registro del otro procesador al primer registro del otro procesador y la segunda orden (y) a una transmisión del contenido del tercer registro al segundo registro del otro procesador,

- tras la etapa (a) en otra etapa adicional se transmite una orden para la transmisión del contenido del primer registro al tercer registro y un orden para la transmisión del contenido del segundo registro al primer registro al registro de órdenes del otro procesador.

11. Procedimiento según una de las reivindicaciones 1 a 10, en la primera (x) y la segunda (y) orden tienen el mismo peso Hamming.