PROCEDIMIENTO, DISPOSITIVO Y SISTEMA PARA VERIFICAR PUNTOS DETERMINADOS SOBRE UNA CURVA ELÍPTICA.

Procedimiento criptográfico para verificar puntos determinados sobre una curva elíptica,

que se realiza sobre una plataforma de hardware, en el que - se proporciona una curva elíptica, - se elige o determina al menos una coordenada de al menos un primer punto, que se encuentra sobre la curva elíptica, - se multiplica el primer punto según un algoritmo Montgomery-Leiter por un valor escalar, utilizándose en el algoritmo sólo una coordenada del primer punto, caracterizado porque - como resultado de la multiplicación escalar se obtienen otros puntos, que incluyen al menos una coordenada del correspondiente resultado del primer punto multiplicado por el escalar y del primer punto multiplicado por un escalar aumentado en un valor, - los puntos determinados incluyen al menos el primer punto y los otros puntos, - se comprueba si los puntos determinados pueden encontrarse sobre una recta, - los puntos determinados se reconocen como verificados en el caso de que puedan encontrarse sobre una recta

Procedimiento, dispositivo y sistema para verificar puntos determinados sobre una curva elíptica.

La invención se refiere a un procedimiento, un dispositivo y un sistema para verificar puntos determinados sobre una curva elíptica.

Los procedimientos criptográficos basados en curvas elípticas son muy eficientes, lo que se debe en particular a que en estos procedimientos, contrariamente a en los procedimientos criptográficos conocidos hasta ahora, no se conoce ningún método de ataque con tiempo de ejecución subexponencial. Dicho de otra manera, esto significa que la ganancia en seguridad por cada bit de los parámetros de seguridad utilizados en procedimientos basados en curvas elípticas es mayor y con ello pueden utilizarse para la aplicación práctica longitudes de clave más cortas.

Con ello, los procedimientos criptográficos a base de curvas elípticas dan mayor rendimiento y precisan de una anchura de banda inferior a la de otros procedimientos criptográficos para transmitir los parámetros del sistema, para un grado comparable de seguridad alcanzable.

Como ejemplo, describiremos aquí a grandes rasgos el conocido procedimiento Diffie-Hellman para acordar una clave común entre dos interlocutores de comunicación basándose en curvas elípticas. Aquí conoce el primer interlocutor de comunicación A un parámetro de seguridad r_a y el segundo interlocutor de comunicación B un parámetro de seguridad r_b. Una vez que ambos interlocutores de comunicación se han puesto de acuerdo respecto a una curva elíptica y a un punto común P sobre esta curva elíptica, determina el interlocutor de comunicación A un valor

y el interlocutor de comunicación B un valor

A continuación de ello, transmite el interlocutor de comunicación A el valor Q_a al interlocutor de comunicación B y el interlocutor de comunicación B transmite al interlocutor de comunicación A el valor Q_b. En otra multiplicación escalar determina ahora el interlocutor de comunicación A la clave común

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

Estas multiplicaciones escalares constituyen así un módulo esencial en procedimientos criptográficos a base de curvas elípticas. La utilización de curvas elípticas es especialmente ventajosa, ya que la operación de inversión

sólo puede calcularse con un considerable coste de cálculo. Según el actual estado de conocimientos, puede calcularse la multiplicación escalar en tiempo polinómico, pero sólo es invertible en tiempo exponencial.

No obstante, Los procedimientos criptográficos conocidos a base de curvas elípticas pueden ser dañados en los llamados ataques de canal lateral.

Los ataques de canal lateral son una clase de métodos para el análisis criptográfico. Contrariamente a los ataques clásicos a aplicaciones criptográficas, no intenta entonces un atacante romper el algoritmo matemático abstracto que sirve de base, sino que ataca una implementación especial de un procedimiento criptográfico. Para ello utiliza el atacante magnitudes de medida físicas fácilmente accesibles de la implementación concreta, como por ejemplo el tiempo de ejecución del cálculo, el consumo de corriente y la radiación electromagnética del procesador durante el cálculo o el comportamiento de la implementación en faltas inducidas. Los valores de medida físicos de un único cálculo pueden analizarse directamente por ejemplo en un análisis de flujo sencillo SPA, o bien un atacante registra los valores de medida de varios cálculos por ejemplo con un osciloscopio con memoria y evalúa los valores de medida a continuación estadísticamente, por ejemplo en un análisis de flujo diferencial, DPA. Los ataques de canal lateral son a menudo bastante más eficientes que las técnicas criptoanalíticas y pueden incluso romper procedimientos que desde el punto de vista de los algoritmos se consideran como seguros, cuando la implementación de estos algoritmos no está asegurada contra ataques de canal lateral. Así se ha detectado que la implementación concreta de procedimientos criptográficos que se basan en curvas elípticas es de una gran importancia para el grado definitivo resultante de seguridad alcanzable en las correspondientes aplicaciones. En particular para smart card (tarjetas inteligentes) y aplicaciones embedded (alojadas) son imprescindibles tales contramedidas frente a ataques de canal lateral.

Un ejemplo de estos ataques de canal lateral es el llamado análisis de faltas. En el mismo intenta un atacante provocar, mediante una manipulación selectiva de los parámetros de servicio de una implementación de un procedimiento criptográfico, faltas transitorias o permanentes durante el cálculo criptográfico. El ataque es posible, ya que el fabricante sólo puede garantizar el correcto funcionamiento de un componente, como por ejemplo de una smart card o de un sistema embedded, en unas condiciones de entorno fijamente predeterminadas. Existe en consecuencia una amplia banda de posibilidades técnicas para generar tales faltas, tales como la manipulación de la generación de impulsos de reloj, temperatura excesiva o demasiado baja, destellos de luz o perturbaciones selectivas mediante un láser, destrucción parcial de los circuitos eléctricos, emisión energética, etc. Las diferencias entre las salidas del circuito cuando funciona correctamente y cuando funciona incorrectamente pueden dar a un atacante, en función del modelo de faltas utilizado por la implementación, informaciones sobre datos secretos, como por ejemplo sobre claves secretas. En algunos procedimientos criptográficos es suficiente un único resultado de cálculo falso para proporcionar de inmediato la clave secreta. Por ello las implementaciones relevantes para la seguridad deben tener contramedidas adecuadas para proteger frente a un análisis de faltas.

Las contramedidas conocidas hasta ahora abarcan desde sensores que vigilan las condiciones del entorno y cuando las condiciones de servicio son inadmisibles impiden la ejecución de los cálculos criptográficos, hasta medidas de protección algorítmicas. Con las medidas de protección algorítmicas puede realizarse por ejemplo dos veces el cálculo criptográfico y compararse entre sí ambos resultados. No obstante, esto tiene el inconveniente de un coste de cálculo duplicado y ello lleva implícito un tiempo de cálculo al menos duplicado. En otra contramedida conocida para proteger frente a análisis de faltas, se introducen invariantes en resultados intermedios del procedimiento criptográfico, que deben mantenerse iguales durante todo el cálculo. Antes de que se emita el resultado del cálculo, comprueba el aparato si la invariante sigue siendo válida aún al final del cálculo. En el caso de que se haya presentado una falta, ya no se cumple con gran probabilidad la invariante. No obstante, este procedimiento tiene de nuevo el inconveniente de que deben realizarse varios pasos de cálculo adicionales y con ello se formulan elevadas exigencias a la capacidad de cálculo necesaria y al espacio de memoria disponible. Otra contramedida se conoce por la solicitud de patente europea EP 1 443 393 A2.

En entornos especiales en los que deben implementarse procedimientos criptográficos, como por ejemplo smart cards o chips RFID (de identificación por radio frecuencia), han de tenerse en cuenta no obstante exigencias especiales en cuanto a la capacidad de cálculo disponible y al espacio de memoria existente. Pero en estos entornos tienen los procedimientos antes descritos para prevenir ataques de canal lateral, en particular análisis de faltas, el inconveniente de que no pueden utilizarse en tales sistemas debido a sus elevadas exigencias a la capacidad de cálculo y al espacio de memoria disponible.

Así tiene la invención como problema básico ofrecer un procedimiento,...

1. Procedimiento criptográfico para verificar puntos determinados sobre una curva elíptica, que se realiza sobre una plataforma de hardware,

en el que

- se proporciona una curva elíptica,

- se elige o determina al menos una coordenada de al menos un primer punto, que se encuentra sobre la curva elíptica,

- se multiplica el primer punto según un algoritmo Montgomery-Leiter por un valor escalar, utilizándose en el algoritmo sólo una coordenada del primer punto,

caracterizado porque

- como resultado de la multiplicación escalar se obtienen otros puntos, que incluyen al menos una coordenada del correspondiente resultado del primer punto multiplicado por el escalar y del primer punto multiplicado por un escalar aumentado en un valor,

- los puntos determinados incluyen al menos el primer punto y los otros puntos,

- se comprueba si los puntos determinados pueden encontrarse sobre una recta,

- los puntos determinados se reconocen como verificados en el caso de que puedan encontrarse sobre una recta.

2. Procedimiento según la reivindicación 1, en el que

en cada caso se memoriza una coordenada de los puntos determinados.

3. Procedimiento según la reivindicación 1, en el que

se utiliza como una de las coordenadas de los puntos determinados la coordenada x.

4. Procedimiento según la reivindicación 1, en el que

se evalúa un polinomio para comprobar los puntos determinados, dando como resultado la evaluación del polinomio exactamente un valor determinado cuando los puntos a comprobar se encuentran sobre una recta.

5. Procedimiento según la reivindicación 4, en el que

el polinomio para comprobar los puntos determinados evalúa las coordenadas en representación de coordenadas proyectiva y/o afín.

6. Procedimiento según la reivindicación 1, en el que

- el valor escalar se encuentra en representación binaria,

- el valor escalar se procesa bit a bit comenzando en el llamado Most Significant Bit (MSB), bit más significativo.

7. Procedimiento según la reivindicación 6, en el que

tras una cantidad que puede predeterminarse de bits procesados del valor escalar, se realiza una verificación de los puntos determinados.

8. Dispositivo para verificar puntos determinados sobre una curva elíptica, en particular según un procedimiento según una de las reivindicaciones 1 a 7, en el que

el dispositivo presenta medios que están equipados tal que pueden realizarse las siguientes etapas del procedimiento:

- se proporciona una curva elíptica,

- se elige o determina al menos una coordenada de al menos un primer punto, que se encuentra sobre la curva elíptica,

- se multiplica el primer punto según un algoritmo Montgomery-Leiter por un valor escalar, utilizándose en el algoritmo sólo una coordenada del primer punto,

caracterizado porque

- como resultado de la multiplicación escalar se obtienen otros puntos, que incluyen al menos una coordenada del correspondiente resultado del primer punto multiplicado por el escalar y del primer punto multiplicado por un escalar aumentado en un valor,

- los puntos determinados incluyen al menos el primer punto y los otros puntos,

- se comprueba si los puntos determinados pueden encontrarse sobre una recta,

- los puntos determinados se reconocen como verificados en el caso de que puedan encontrarse sobre una recta.

9. Sistema para verificar puntos determinados sobre una curva elíptica, en particular según un procedimiento según una de las reivindicaciones 1 a 7 con un primer ordenador y un segundo ordenador, pudiendo conectarse entre sí el primer ordenador y el segundo ordenador,

- en el que se acuerda entre el primer ordenador y el segundo ordenador una curva elíptica y al menos una coordenada de un primer punto, que se encuentra sobre la curva elíptica,

- en el que el primer ordenador es un dispositivo según la reivindicación 8,

- y en el que los puntos determinados y verificados se transmiten desde el primer ordenador al segundo ordenador, transmitiéndose para puntos que se encuentran sobre la curva elíptica en cada caso sólo una de las coordenadas del correspondiente punto,

- en el que el segundo ordenador presenta una unidad de procesador que está equipada tal que pueden realizarse las siguientes etapas de procedimiento:

- se reciben los puntos transmitidos por el primer ordenador,

- se procesan adicionalmente los puntos recibidos, determinados, utilizándose en todo el procesamiento adicional sólo una de las coordenadas del correspondiente punto sobre la curva elíptica.