PROCEDIMIENTO DE CONTRAMEDIDA EN UN COMPONENTE ELECTRONICO QUE EMPLEA UN ALGORITMO DE CODIFICACION CON CLAVE PUBLICA DE TIPO CURVA ELIPTICA.

Procedimiento de contramedida en un componente electrónico que aplica un algoritmo de criptografía de clave pública de tipo curva elíptica que utiliza la representación de los puntos de dicha curva elíptica en coordenadas proyectivas que consisten en representar un punto P de la curva elíptica por los datos (X,

Y, Z) tales como x = X/Z^2 y y = Y/Z^3, x e y son los datos del punto de la curva elíptica en coordenadas afines, dicha curva incluye n elementos y se define en un cuerpo terminado GF (p), p es un número primo, dicha curva tiene como ecuación y^2 = x^3+a por x+b, o se define en un cuerpo terminado GF (2 A n), dicha curva tiene como ecuación y^2+x por y = x^3+a por x^2+b, donde a y b son parámetros enteros fijados al principio, dicho procedimiento elige un representante entero aleatorio entre n elementos posibles en coordenadas proyectivas de la curva elíptica y consiste en una modificación de la operación de duplicación de puntos, de adición de dichos puntos y de la operación de multiplicación escalar, caracterizada en que el procedimiento de contramedida se aplica cualquiera que sea el procedimiento o el algoritmo, anotado a continuación A, utilizado para realizar la operación de duplicación de punto, el procedimiento A está remplazado por el procedimiento A'''' en 3 etapas, utilizando una entrada definida por un punto P = (X1, Y1, Z1) representado en coordenadas proyectivas y una salida definida por un punto Q = (X2, Y2, Z2) representada por coordenadas proyectivas, tales como Q =

Procedimiento de contramedida en un componente electrónico que emplea un algoritmo de codificación con clave pública de tipo curva elíptica.

La presente invención concierne un procedimiento de contramedida en un componente electrónico que emplea un algoritmo de codificación con clave pública de tipo curva elíptica.

En el modelo clásico de la criptografía de clave secreta, dos personas que desean comunicar por medio de un canal no asegurado deben ponerse de acuerdo de antemano sobre una clave secreta de codificación K. la función de codificación y la función de decodificación utilizan la misma clave K. El inconveniente del sistema de codificación con clave secreta radica en que dicho sistema requiere la comunicación previa de la clave K entre ambas personas por medio de un canal asegurado, antes de que pueda enviarse cualquier mensaje codificado a través del canal no asegurado. En la práctica, resulta difícil generalmente encontrar un canal de comunicación perfectamente asegurado, sobre todo si la distancia que separa las dos personas es importante. Se entiende por canal asegurado un canal para el que resulta imposible conocer o modificar la información que transita por dicho canal. Este tipo de canal asegurado puede realizarse mediante un cable que conecta dos terminales, que poseen esas dos personas.

Whitfield DIFFIE y Martin HELLMAN inventaron el concepto de criptografía de clave pública en 1976. La criptografía de clave pública permite solucionar el problema de la distribución de las claves a través de un canal no asegurado. El principio de la criptografía de clave pública consiste en utilizar un par de claves, una clave pública de codificación y una clave privada de decodificación. Debe resultar imposible calcular la clave privada de decodificación a partir de la clave pública de codificación. Una persona A que desea comunicar una información a una persona B utiliza la clave pública de codificación de la persona B. Solamente la persona B poseerá la clave privada asociada a su clave pública. Por tanto, sólo la persona B es capaz de descifrar el mensaje que se le ha enviado.

Otra ventaja de la criptografía de clave pública, con respecto a la criptografía de clave secreta es que la criptografía de clave pública permite la autenticación mediante la utilización de una firma electrónica.

La primera realización de esquema de codificación de clave pública fue puesta a punto en 1977 por Rivest, Shamir y Adleman, que inventaron el sistema de codificación RSA. La seguridad de RSA se basa en la dificultad de descomponer en factores un gran número que es el producto de dos números primos.

Desde entonces, se propusieron numerosos sistemas de codificación de clave pública, cuya seguridad se basa en la necesidad de efectuar distintos problemas de cálculo: (esta lista no es exhaustiva).

- Mochila de Merckle-Hellman

Este sistema de codificación se basa en la dificultad del problema de la suma de subconjuntos.

- McEliece

Este sistema de codificación se basa en la teoría de los códigos algébricos. Se basa en el problema de la decodificación de códigos lineales.

- ElGamal

Este sistema de codificación se basa en la dificultad del logaritmo discreto en un cuerpo terminado.

- Curvas elípticas

El sistema de codificación de curva elíptica constituye una modificación de los sistemas criptográficos que existen para aplicarlos al campo de las curvas elípticas.

La utilización de curvas elípticas en sistemas criptográficos fue propuesta independientemente por Victor Miller y Neal Koblitz en 1985. Las verdaderas aplicaciones de las curvas elípticas se previeron a principios de los 90.

La ventaja de los criptosistemas a base de curva elíptica es que proporcionan una seguridad equivalente a los demás criptosistemas pero con tamaños de clave menores. Esta ganancia en tamaño de clave implica una disminución de las necesidades de memoria y una reducción del tiempo de cálculo, lo que hace que la utilización de las curvas elípticas sea especialmente adaptada para aplicaciones de tipo tarjeta inteligente.

Una curva elíptica en un cuerpo terminado GF (q^n) (q es un número primo y n un entero) es el conjunto de los puntos (x, y) con x la abscisa e y la ordenada que pertenece a GF (q^A) solución de la ecuación:

y^2 = x^3 + a*x + b

si q es superior o igual a 3

e y'2 + x*y = x^3 + a*x^2 + b

si q = 2.

Existen 2 procedimientos para representar un punto de una curva elíptica:

En primer lugar, la representación en coordenadas afines; en este procedimiento, un punto P de la curva elíptica está representado por sus coordenadas (x, y).

En segundo lugar, la representación en coordenadas proyectivas.

La ventaja de la representación en coordenadas proyectivas es que permite evitar las divisiones en el cuerpo terminado, dichas divisiones son las operaciones más costosas en tiempo de cálculo.

La representación en coordenadas proyectivas más corrientemente utilizada es aquella que consiste en representar un punto P de la curva elíptica por las coordenadas (X, Y, Z), tales como x=X/2 y y=Y/Z^3.

Las coordenadas proyectivas de un punto no son únicas porque el triplete (X, Y, Z) y el triplete (?^2*X, k^3*Y, k*Z representan el mismo punto, cualquiera que sea el elemento 2. que pertenece al cuerpo terminado en el que se ha definido la curva elíptica.

Las 2 clases de curvas más utilizadas en criptografía son las siguientes:

1) Curvas definidas en el cuerpo terminado GF (p) (conjunto de los enteros módulo p, p es un número primo) cuya ecuación es la siguiente y^2 = x^3 + a*x + b

2) Curvas definidas en el cuerpo terminado GF (2^n) cuya ecuación es la siguiente: y^2 + x*y = x^A3 + a*x^2 + b.

Para cada una de estas dos clases de curvas, se definen las operaciones de adición de punto y duplicación de punto.

La adición de punto es la operación que a partir de dos puntos P y Q calcula la suma R=P+Q, R, es un punto de la curva cuyas coordenadas se expresan con ayuda de las coordenadas "Elliptic curve public key cryptosystem" por Alfred J. Menezes

La duplicación de punto es la operación que, a partir de un punto P, calcula el punto R=2*P, R es un punto de la curva cuyas coordenadas se expresan mediante coordenadas del punto P según fórmulas cuya expresión se facilita en la obra "Elliptic curve public key cryptosystem" por Alfred J. Menezes.

Las operaciones de adición de punto y duplicación de punto permiten definir una operación de multiplicación escalar: basándonos en un punto P que pertenece a una curva elíptica y un entero d, el resultado de la multiplicación escalar de P por d es el punto Q tal y como Q=d*P=P+P+... +P d veces.

La seguridad de los algoritmos de criptografía en curvas elípticas se basa en la dificultad del problema del logaritmo discreto en curvas elípticas, dicho problema consiste a partir de dos puntos Q y P que pertenecen a una curva elíptica E, en encontrar, si existe, un entero x como Q=x*P.

Existen numerosos algoritmos criptográficos que se basan en el problema del logaritmo discreto. Estos algoritmos pueden transponerse fácilmente a las curvas elípticas.

Así pues, es posible emplear algoritmos que garanticen la autenticación, la confidencialidad, el control de integridad y el intercambio de clave.

Un punto común a la mayoría de los algoritmos criptográficos que se basan en las curvas elípticas es que tienen como parámetro una curva elíptica definida en un cuerpo acabado y, un punto P que pertenece a esta curva elíptica. La clave privada es un entero d elegido de manera aleatoria. La clave pública es un punto de la curva Q tal y como Q=d*P. Estos algoritmos criptográficos hacen intervenir por lo general una multiplicación escalar en el cálculo de un punto R=d*T donde d es la clave secreta.

En el siguiente párrafo, se describe un algoritmo de codificación a base de curvas elípticas. Este esquema es similar al esquema de codificación, Un mensaje m se codifica de la siguiente manera:

El codificador elige un entero k de manera aleatoria y calcula...

1. Procedimiento de contramedida en un componente electrónico que aplica un algoritmo de criptografía de clave pública de tipo curva elíptica que utiliza la representación de los puntos de dicha curva elíptica en coordenadas proyectivas que consisten en representar un punto P de la curva elíptica por los datos (X, Y, Z) tales como x = X/Z^2 y y = Y/Z^3, x e y son los datos del punto de la curva elíptica en coordenadas afines, dicha curva incluye n elementos y se define en un cuerpo terminado GF (p), p es un número primo, dicha curva tiene como ecuación y^2 = x^3+a*x+b, o se define en un cuerpo terminado GF (2^An), dicha curva tiene como ecuación y^2+x*y = x^3+a*x^2+b, donde a y b son parámetros enteros fijados al principio, dicho procedimiento elige un representante entero aleatorio entre n elementos posibles en coordenadas proyectivas de la curva elíptica y consiste en una modificación de la operación de duplicación de puntos, de adición de dichos puntos y de la operación de multiplicación escalar, caracterizada en que el procedimiento de contramedida se aplica cualquiera que sea el procedimiento o el algoritmo, anotado a continuación A, utilizado para realizar la operación de duplicación de punto, el procedimiento A está remplazado por el procedimiento A' en 3 etapas, utilizando una entrada definida por un punto P = (X1, Y1, Z1) representado en coordenadas proyectivas y una salida definida por un punto Q = (X2, Y2, Z2) representada por coordenadas proyectivas, tales como Q = 2.P, de la curva elíptica, dichas etapas son las siguientes:

        1)        Coger al azar un entero ? tal como O<?<p;

        2)        Calcular X'1 = ?^2*X1, Y'1 = ?^3*Y1, Z'1 = ?*Z1, X'1, Y'1 y Z¹1 que definen las coordenadas del punto P' = (X'1, Y'1, Z'1);

        3)        Calcular Q2*P' con el algoritmo A.

2. Procedimiento de contramedida según la reivindicación 1 caracterizado porque el algoritmo de duplicación de puntos, u operaciones de duplicación de puntos de una curva elíptica definida en dicho cuerpo terminado GP (p) se efectúa en ocho etapas:

        1)        Coger al azar un entero X tal como 0<?<p;

        2)        Calcular X'1 = ?^2*X1, Y'1 = ?^3*Y1, Z¹1 = ?*Z1;

        3)        Calcular M = 3*X'1^2+a*Z'1^4;

        4)        Calcular Z2 = 2*Y'1*V1;

        5)        Calcular Z2 = X'1*Z'1^2;

        6)        Calcular X2 = M^2-2*S;

        7)        Calcular T = 8*Y'1^4;

        8)        Calcular Y2 = M*(S-X2)-T.

3. Procedimiento de contramedida según la reivindicación 1 caracterizado porque más generalmente el procedimiento de la contramedida se aplica cualquiera que sea el procedimiento o el algoritmo anotado a continuación A utilizado para realizar la operación de adición de puntos en una curva elíptica definido en dicho cuerpo terminado GF (p), y se efectúa en cinco etapas:

        1)        Coger al azar un elemento ? no nulo de GF (2^n);

        2)        Remplazar XO por X^2*X0, YO por k^3*Y0 y Z0 por ?*ZO;

        3)        Coger al azar un elemento no nulo de GF(2^en);

        4)        Remplazar X1 por µ^2*X1, Y1 por µ^3*Y1 y Z1 por µ*Z1;

        5)        Cálculo de R = P+Q con el algoritmo A, con P = (X0, Y0, Z0) y Q = (X1, Y1, Z1).

4. Procedimiento de contramedida según la reivindicación 1 caracterizado porque la modificación del algoritmo de adición de punto de una curva elíptica definida en el cuerpo terminado GF (p), donde p es un número primo, es la siguiente: las coordenadas proyectivas del punto R = (X2, Y2, Z2) tales como R = P+Q con P. (X0, YO, Z0) y Q = (X1, Y1, Z1) se calculan por el siguiente procedimiento en 16 etapas, en cada una de las etapas, los cálculos se efectúan módulo p:

        1)        Coger al azar un entero que pertenezca a dicho cuerpo terminado GF(p) tal como 0<?<p

        2)        Remplazar XO por ?^2*X0, YO por ?^3*Y0 y ZO por ?*ZO;

        3)        Coger al azar un entero µ tal y como 0<µ<p;

        4)        Remplazar X1 por µ^2*X1, Y1 por µ^3*Y1 y Z1 por µ*Z1;

        5)        Calcular U0X0*Z1^2;

        6)        Calcular SO = YO*Z1^3;

        7)        Calcular U1 = X1*Z0^2;

        8)        Calcular S1 = Y1*Z0^3;

        9)        Calcular W = U0-U1;

        10)        Calcular R = SO-S1;

        11)        Calcular T = U0+U1;

        12)        Calcular M = S0+S1;

        13)        Calcular Z2 = Z0*Z1*W;

        14)        Calcular X2 = R^2-T*W^2;

        15)        Calcular V = T+W^2-2*X2)

        16)        Calcular 2*Y2 = V*R-M*W^3.

5. Procedimiento de contramedida según la reivindicación 1 caracterizado porque más generalmente la modificación del algoritmo de duplicación de punto de una curva elíptica definida en el cuerpo terminado GF(2^n), donde n es un número primo, es la siguiente: las coordenadas proyectivas del punto P = (X1, Y1, Z1) tales como R = P+Q y Q = (X2, Y2, Z2) se calculan mediante el siguiente procedimiento en 3 etapas, en cada una de las etapas, los cálculos se efectúan módulo p:

        1)        Coger al azar un elemento ? no nulo de GF (2^n);

        2)        Calcular X'1 = ?^2*X1, Y'1 = ?^3*Y1, Z'1 = 1*Z1, X'1, Y'1 y Z'1 definen las coordenadas del punto P' = (X'1, Y'1, Z'1);

        3)        Cálculo de Q = 2.P' con el algoritmo A.

6. Procedimiento de contramedida según la reivindicación 1 caracterizado porque el procedimiento de contramedida consiste en una modificación del procedimiento anterior, el procedimiento de duplicación de punto de una curva elíptica se define en el cuerpo terminado GF (2^n), y consiste en las 6 siguientes etapas:

        1)        Coger al azar un elemento no nulo ? de GF (2^n);

        2)        Calcular X'1 = ?^2*X1, Y'1 = ?^3*Y1, Z¹1 = ?*Z1;

        3)        Calcular Z2- X'1*Z'1^A2;

        4)        Calcular X2 = (X'1+c*Z'1^2)^4)

        5)        Calcular U = Z2-X'1^2+Y'1*Z¹1;

        6)        Calcular Y2 = X'1^4*Z2+U*X2.

7. Procedimiento de contramedida según la reivindicación 1 caracterizado porque más generalmente la modificación del algoritmo de adición de punto de una curva elíptica definida en el cuerpo terminado GF(2^n), donde n es un número primo, es la siguiente: Las coordenadas proyectivas del punto P = (X0, YO, Z0) y Q = (X1, Y1, Z2) en entrada y R = (X2, Y2, Z2) se calculan mediante el siguiente procedimiento en 5 etapas, los cálculos se efectúan con el módulo;

        1)        Coger al azar un elemento 1 no nulo de GF(2^n);

        2)        Remplazar XO por ?^2*X0, YO por ?^3*Y0 y ZO por ?*ZO;

        3)        Coger al azar un elemento µ no nulo de Gp(2^n);

        4)        Remplazar X1 por µ^2*X1, Y1 por µ^3*Y1 y Z1 por µ*Z1;

        5)        Cálculo de R = P+Q con el algoritmo A.

8. Procedimiento de contramedida según la reivindicación 1 caracterizado porque el procedimiento de contramedida consiste en una modificación del procedimiento anterior, el procedimiento de adición de punto de una curva elíptica se define en el cuerpo terminado GF (2^n), y consiste en las 16 siguientes etapas:

        1)        Coger al azar un elemento ? no nulo de GF(2n);

        2)        Remplazar XO por ?^2*X0, YO por ?^3*Y0 y ZO por ?*ZO;

        3)        Coger al azar un elemento µ no nulo de GF(2^n);

        4)        Remplazar X1 por µ^2*X1: Y1 por µ^3*Y1 et Z1 por µ*Z1;

        5)        Calcular U0 = X0*Z1^2;

        6)        Calcular SO = Y0*Z1^3;

        7)        Calcular U1 = X1*Z0^2;

        8)        Calcular S1 = Y1*Z0'3;

        9)        Calcular W = UO+U1;

        10)        Calcular R = SO+S1;

        11)        Calcular L = ZO*W;

        12)        Calcular V = R*X1+L*Y1;

        13)        Calcular Z2 = L*Z1;

        14)        Calcular T = R+Z2;

        15)        Calcular X2 = a*Z2^2+T*R+W^3;

        16)        Calcular Y2 = T*X2+V*L^2.

9. Procedimiento de contramedida según la reivindicación 1 caracterizado porque una primera variante de modificación de la operación de multiplicación escalar consiste en hacer aleatoria la representación de un punto al principio del procedimiento de cálculo por la utilización del algoritmo "double and add" el procedimiento modificado de multiplicación escalar es el siguiente en 5 etapas, tomando en entrada un punto P y un entero d, el entero d se anota d = (d(t), d(t-1), ..., d(0)), donde (d(t)d (t-1), ..., d (0)) es la representación binaria de d, con d(t) el bit de peso fuerte y d (0) el bit de peso bajo, el algoritmo que envía a la salida el punto Q = d.P, el procedimiento Do es el procedimiento de duplicación de puntos, el procedimiento Do' es el procedimiento de duplicación de los puntos modificados según cualquiera de las reivindicaciones anteriores, esta primera variante se ejecuta en cinco etapas:

        1)        Inicializar el punto Q con el valor P;

        2)        Remplazar Q por 2.Q utilizando el procedimiento Do';

        3)        Si d(t-1) = 1 remplazar Q por Q+P utilizando el procedimiento Ad, el procedimiento Ad es el procedimiento de adición de puntos;

        4)        Para i que va de t-2 a 0 ejecutar:

4a)        Remplazar Q por 2Q;

4b)        Si d(i) = 1 remplazar Q por Q+P;

        5)        Enviar Q.

10. Procedimiento de contramedida según la reivindicación 1 caracterizado porque una segunda variante de la operación de multiplicación escalar consiste en hacer aleatoria la representación de un punto al principio del procedimiento de cálculo y al final del procedimiento de cálculo, esto en el caso de la utilización del algoritmo "double and add" el procedimiento modificado de multiplicación escalar es el siguiente en 7 etapas, tomando en entrada un punto P y un entero d, el entero d se anota d = (d(t), d(t-1), ..., d(0)), donde (d (t), d(t-1), ..., d (0)) es la representación binaria de d, con d(t) el bit de peso fuerte y d (0) el bit de peso bajo, el algoritmo que envía a la salida el punto Q = d.P, dicha segunda variante se ejecuta en siete etapas:

        1)        Inicializar el punto Q con el valor P;

        2)        Remplazar Q por 2.Q utilizando el procedimiento Do';

        3)        Si d(t-1) = 1 remplazar Q por Q+P utilizando el procedimiento Ad;

        4)        Para i que va de t-2 a 1 ejecutar:

4a)        Remplazar Q por 2Q;

4b)        Si d(i) = 1 remplazar Q por Q+P;

        5)        Remplazar Q por 2.Q utilizando el procedimiento Do';

        6)        Si d(0) = 1 remplazar Q por Q+P utilizando el procedimiento Ad;

        7)        Enviar Q.

11. Procedimiento de contramedida según la pretensión 1 caracterizado porque una tercera variante de la operación de multiplicación escalar se realiza en tres etapas:

        1)        Inicializar el punto Q con el valor P;

        2)        Para i que va de t-2 a 0 ejecutar:

2a)        Remplazar Q por 2.Q utilizando el procedimiento Do';

2b)        Si d(i) = 1 remplazar Q por Q+P utilizando el procedimiento Ad', Ad' es el procedimiento de adición de los puntos modificados según las anteriores reivindicaciones;

        3)        Enviar Q.

12. Procedimiento de contramedida según la pretensión 1 caracterizado porque la cuarta variante de la operación de multiplicación escalar se realiza en tres etapas:

        1)        Inicializar el punto Q con el valor P;

        2)        Inicializar el contador co al valor T.

        3)        Para i que va de t-1 a 0 ejecutar:

3a)        Remplazar Q por 2Q utilizando el procedimiento Do si co es diferente de 0, en caso contrario utilizar el procedimiento Do'.

3b)        Si d(i) = 1 remplazar Q por Q+P utilizando el procedimiento Ad.

3c)        Si co = 0 entonces reinicializar el contador co al valor T.

3d)        Decrementar el contador co.

        4)        Enviar Q.

13. Componente electrónico, por ejemplo tarjeta inteligente, que contiene medios para aplicar el procedimiento según cualquiera de las reivindicaciones anteriores.