Un método de descifrado de un mensaje cifrado representado por una secuencia C,

o de firma electrónica de una secuencia C, estando dicha secuencia C constituida por datos que pertenecen a un cuerpo finito K=GF(q), siendo q>1, en donde se trata bloques sucesivos, que comprenden cada uno (n·d) datos sucesivos de la secuencia C, siendo n y d enteros predeterminados superiores a 1, comprendiendo el tratamiento de un tal bloque las etapas siguientes: - se aplica una transformación afín inversible predeterminada t -1 a dicho bloque, - el bloque resultante se interpreta como estando formado por n elementos sucesivos (y1,y2,...,yn) de una extensión E=GF(q d ) del cuerpo K, - se calcula un n-uplete (x1,x2,...,xn) de elementos del cuerpo E resolviendo un sistema f de n polinomios predeterminados de la forma **Fórmula** en donde los coeficientes ak (ij) , b(i) y ck , pertenecen a E y en donde los exponentes α i ,β j y γ i de los enteros positivos o nulos, - dicho n-uplete (x1,x2,...,xn) se interpreta como siendo un nuevo bloque formado por (n·d) elementos sucesivos del cuerpo K y - se aplica una transformación afín inversible predeterminada s-1 a dicho nuevo bloque

La invención se refiere al campo de la criptografía. Más concretamente, la invención se refiere al cifrado de mensajes y la firma electrónica.

Se conoce, desde hace mucho tiempo, algoritmos de cifrado de mensaje, en particular algoritmos de cifrado por bloques, tales como el DES (iniciales de las palabras inglesas "Data Encryption Standard" que significa "Norma de Cifrado de Datos"), que utiliza una clave de 56 bits (actualmente obsoleta), o el "Triple DES" (publicado por la sociedad IBM en 1999) que utiliza tres tales claves, o también AES (iniciales de las palabras inglesas "Advanced Encryption Standard" que significa "Norma de Cifrado Avanzado") elegida en octubre de 2000 en Estados Unidos por el NIST («National Institute of Standards and Technology») que utiliza claves de 128, 192 o 256 bits.

La mayor parte de los algoritmos conocidos son algoritmos simétricos, es decir algoritmos tales que la entidad que cifra el mensaje y la entidad que lo descifra compartan una misma clave secreta. Estos algoritmos simétricos tienen, por inconveniente, que la elección de la clave, o la comunicación de la clave de una entidad a la otra, se debe realizar de forma segura para impedir que un intruso tenga conocimiento; considerando la longitud exigida para las claves (al menos 128 bits), las precauciones que ello impone son muy restrictivas.

Por lo tanto, se ha buscado construir algoritmos de cifrado asimétricos, es decir algoritmos tales que cualquier entidad que desee enviar un mensaje cifrado a un destinatario determinado puede utilizar una variante pública de este algoritmo, siendo la variante característica del destinatario, pero tal que sólo este destinatario sea capaz de descifrar el mensaje cifrado; se constatará que incluso el emisor del mensaje cifrado, de forma asimétrica, no puede, de forma propiamente dicha, descifrar este mensaje cifrado (en el supuesto de que el emisor conozca el mensaje sin cifrar desde el inicio). Al ser el algoritmo de cifrado accesible a todos, no hay ninguna precaución de seguridad a tomar al nivel de entendimiento entre el emisor de un mensaje y su destinatario.

Por otro lado, se hace constar que la mayor parte de los algoritmos asimétricos pueden servir tanto para el cifrado como para la firma de mensaje, siendo estos dos protocolos simplemente el inverso uno del otro. Dicho de otro modo, para el cifrado, se cifra con la clave pública y se descifra con la clave secreta, mientras que para la firma, se firma con la clave secreta y se verifica la firma con la clave pública.

En particular, en el caso de los algoritmos asimétricos en donde la clave secreta es un "truco" (tal como, por ejemplo, el algoritmo de "aceite y vinagre desequilibrados" descrito a continuación), la firma electrónica procede de la forma siguiente. En el momento de la firma de una secuencia C (que puede ser un condensado de un documento original), el signatario utiliza el mismo algoritmo (secreto) que si esta secuencia C fuera un mensaje cifrado que se tratara de descifrar. Se obtiene, así, una "firma" M, que se pone a la disposición del público, o de al menos un verificador, al mismo tiempo que el documento original. A continuación, para la verificación de esta firma M, el verificador aplica a la secuencia M el mismo algoritmo público que si se tratara de cifrar esta secuencia M; si la firma es auténtica, el verificador obtiene una secuencia idéntica a la secuencia C, es decir, al documento original puesto a su disposición o a su condensado.

El algoritmo asimétrico más conocido es, sin duda, el RSA (para una descripción detallada de RSA, véase el artículo de R.L. Rivest, A. Shamir y L.M. Adleman titulado "Un método para obtener Firmas Digitales y Criptosistemas de claves públicas", Communications of the ACM, volumen 21 n° 2, páginas 120 a 126, 1978). Asimismo, se conoce los algoritmos que utilizan curvas elípticas (véase, por ejemplo, el artículo de Neal Koblitz titulado "Criptosistemas de curvas elípticas", Mathematics of Computation, volumen n° 48, páginas 203 a 209, 1987, o el artículo de V. Miller titulado “Uso de Curvas Elípticas en Criptografía”, CRYPTO 85, 1985). Estos algoritmos presentan el inconveniente de necesitar cálculos muy complicados.

En el sistema denominado "aceite y vinagre desequilibrado" dado a conocer por A. Kipnis, J. Patarin, y L. Goubin (véase su artículo titulado "Sistemas de Firmas de Aceite y Vinagre desequilibrado", EUROCRYPT 1999, páginas 206 a 222), la clave pública consiste en un sistema de h polinomios cuadráticos multivariados con n variables x1 a xn, con n > h > 1, en un cuerpo finito K. Estos polinomios son, por lo tanto, de la forma

**(Ver fórmula)**

ij 

i

en donde los coeficientes  , y pertenecen a K.

kk k

A modo de "clave secreta", este sistema utiliza un "truco". Este truco consiste en mezclar dos tipos de variables, denominadas variables de «aceite» y variables de «vinagre», lo que permite constituir un cierto sistema de h ecuaciones cuadráticas multivariadas con n = v + h variables, en donde el entero v designa el número de variables de vinagre y el entero h designa el número de variables de aceite. Se necesita que v > h; además, cada polinomio del sistema comprende todos los monomios posibles, cuyos coeficientes son determinados al azar, excluidos los monomios

40

45

constituidos por el producto de dos variables de aceite, que están ausentes. La particularidad de realización del método saca partido de que un sistema lineal aleatorio de h ecuaciones y h incógnitas presenta una gran probabilidad de tener una solución única. Fijando, de forma aleatoria, el valor de las variables de vinagre, es posible resolver el sistema lineal en las h variables de aceite resultante. Si, para una elección aleatoria dada de las variables de vinagre, el sistema resultante no es inversible, basta efectuar otra elección aleatoria de variables de vinagre.

Con el fin de enmascarar esta estructura al público, se aplica, a la entrada del sistema, un cambio de variables inversible de (v+h) variables hacia (v+h) variables. El sistema así transformado constituye la clave pública, mientras que el cambio de variables y el sistema original constituyen la clave secreta.

Este sistema tiene, por inconveniente, que sólo puede servir de algoritmo de firma, y no de algoritmo de cifrado. Además, es ineficaz debido a la necesidad de añadir a las variables de aceite (directamente asociadas al mensaje a firmar) un gran número de variables suplementarias (las variables de vinagre) en el momento de la firma.

Otros algoritmos asimétricos conocidos, por ejemplo el algoritmo "C*" (véase el artículo de Tsutomu Matsumoto y Hideki Imai titulado "Public Quadratic Polynomial Tuples for Efficient Signature Verification and Message Encryption", Eurocrypt‘88, páginas 419 a 453) han sido, por sí mismos, eliminados.

La presente invención se refiere, por lo tanto, en primer lugar, un método de descifrado de un mensaje cifrado representado por una secuencia C o por una firma electrónica de una secuencia C, estando dicha secuencia C constituida por datos que pertenecen a un cuerpo finito K=GF(q), siendo q>1, en donde se tratan bloques sucesivos que comprenden cada uno (n·d) datos sucesivos de la secuencia C, en donde n y d son enteros predeterminados superiores a 1, comprendiendo el tratamiento de un tal bloque las etapas siguientes:

- se aplica una transformación afín inversible predeterminada t-1 a dicho bloque,

- el bloque resultante se interpreta como estando formado por n elementos sucesivos (yl,y2,…,yn) de una extensión E=GF(qd)del cuerpo K,

- se calcula un n-uplete (xl,x2,…,xn) de elementos del cuerpo E resolviendo un sistema ƒ de n polinomios predeterminados de la forma :

**(Ver fórmula)**

ij 

i

en donde los coeficientes ak , bk y ck , pertenecen a E y en donde los exponentes i , j y  i son enteros

positivos o nulos,

- dicho n-uplete (xl,x2,…,xn) interpretado como siendo un nuevo bloque formado por (n·d) elementos sucesivos del cuerpo K y

- se aplica una transformación afín inversible predeterminada... [Seguir leyendo]

1. Un método de descifrado de un mensaje cifrado representado por una secuencia C, o de firma electrónica de una secuencia C, estando dicha secuencia C constituida por datos que pertenecen a un cuerpo finito K=GF(q), siendo q>1, en donde se trata bloques sucesivos, que comprenden cada uno (n·d) datos sucesivos de la secuencia C, siendo n y d enteros predeterminados superiores a 1, comprendiendo el tratamiento de un tal bloque las etapas siguientes:

- se aplica una transformación afín inversible predeterminada t-1 a dicho bloque,

- el bloque resultante se interpreta como estando formado por n elementos sucesivos (y1,y2,…,yn) de una extensión E=GF(qd) del cuerpo K,

- se calcula un n-uplete (x1,x2,…,xn) de elementos del cuerpo E resolviendo un sistema ƒ de n polinomios predeterminados de la forma

**(Ver fórmula)**

ij  i

en donde los coeficientes ak , bk y ck , pertenecen a E y en donde los exponentes i ,j y i de los enteros positivos o nulos,

- dicho n-uplete (x1,x2,…,xn) se interpreta como siendo un nuevo bloque formado por (n·d) elementos sucesivos del cuerpo K y

- se aplica una transformación afín inversible predeterminada s-1 a dicho nuevo bloque. 2. El método de descifrado o de firma electrónica, según la reivindicación 1, caracterizado porque q es igual a

2.

3. Método de descifrado o de firma electrónica según la reivindicación 1, caracterizado porque q es igual a 8.

4. Método de cifrado de un mensaje representado por una secuencia M, o verificación de una firma electrónica representada por una secuencia M, estando dicha secuencia M constituida por datos que pertenecen a un cuerpo finito K=GF(q), siendo q>1, en donde se trata bloques sucesivos, comprendiendo cada uno (n·d) datos sucesivos de la secuencia M, en donde n y d son enteros predeterminados superiores a 1, la construcción secreta del algoritmo de tratamiento público de un tal bloque, que comprende las etapas siguientes:

- se aplica una transformación afín inversible predeterminada a dicho bloque,

- el bloque resultante se interpreta como estando formado por n elementos sucesivos (x1,x2,…,xn) de una extensión E=GF(qd) del cuerpo K,

- se calcula un n-uplete (y1,y2,…,yn) de elementos del cuerpo E por medio de un sistema ƒ de n polinomios predeterminados de la forma

**(Ver fórmula)**

ij  i

en donde los coeficientes ak , bk y ck , pertenecen a E y en donde los exponentes i ,j y i son enteros positivos o nulos,

- dicho n–uplete (y1,y2,…,yn) se interpreta como siendo un nuevo bloque constituido por (n·d) elementos sucesivos del cuerpo K y

- se aplica una transformación afín inversible predeterminada t a dicho nuevo bloque.

5. Método de cifrado o de verificación de una firma electrónica según la reivindicación 4, caracterizado porque q es igual a 2.

6. Método de cifrado o de verificación de una firma electrónica, según la reivindicación 4, caracterizado porque q es igual a 8.

7. Dispositivo de descifrado de un mensaje cifrado representado por una secuencia C, o de firma electrónica de una secuencia C, estando dicha secuencia C constituida por datos que pertenecen a un cuerpo finito K=GF(q), siendo q>1, en donde se trata bloques sucesivos, comprendiendo cada uno (n·d) datos sucesivos de la secuencia C, en donde n y d son enteros predeterminados superiores a 1, comprendiendo dicho dispositivo, con el fin de tratar un tal bloque:

- medios para aplicar una transformación afín inversible predeterminada t-1 a dicho bloque,

- medios para interpretar el bloque resultante como estando formado por n elementos sucesivos (y1,y2,…,yn) de una extensión E=GF(qd) del cuerpo K,

- medios para calcular un n-uplete (x1,x2,…,xn) de elementos del cuerpo E resolviendo un sistema ƒ de n polinomios predeterminados de la forma

**(Ver fórmula)**

ij  i

en donde los coeficientes ak , bk y ck , pertenecen a E y en donde los exponentes i ,j y i son enteros

positivos o nulos,

- medios para interpretar dicho n-uplete (x1,x2,…,xn) como siendo un nuevo bloque formado por (n·d) elementos sucesivos del cuerpo K y

- medios para aplicar una transformación afín inversible predeterminada s-1 a dicho nuevo bloque.

8. Dispositivo de descifrado o de firma electrónica, según la reivindicación 7, caracterizado porque q es igual a

2.

9. Dispositivo de descifrado o de firma electrónica según la reivindicación 7, caracterizado porque q es igual a

8.

10. Circuito electrónico, caracterizado porque comprende un dispositivo de descifrado o firma electrónica, según una cualquiera de las reivindicaciones 7 a 9.

11. Medio de almacenamiento de datos inamovible, o parcial o totalmente amovible, que presenta instrucciones de código de programa informático para la ejecución de las etapas de un método según una cualquiera de las reivindicaciones 1 a 6.

12. Programa informático que se puede telecargar desde una red de comunicación y/o almacenar en un soporte legible por ordenador y/o ejecutable por un microprocesador, caracterizado porque comprende instrucciones para la ejecución de las etapas del método de cifrado o de descifrado, o de firma o de verificación de firma, según una cualquiera de las reivindicaciones 1 a 6, cuando se ejecuta en un ordenador.