Resumen
Method to produce an encryption system with public key and digital signature with polynomials of few variables based on vectorial exponentiation. In the field of public-key cryptography there is a growing interest in building secure encryption against current attacks and also against attacks from future quantum computers. The present invention describes a new multivariable pubic key encryption system (MPKC) that uses a new method to construct the central invertible applications that allows obtaining a public key with polynomials of very few variables, which guarantees a high efficiency and speed in the encryption, decryption and digital signature processes. (Machine-translation by Google Translate, not legally binding)
Reivindicaciones
1. REIVINDICACIONES 1. Método para producir un sistema de cifrado con clave pública que comprende: a) Elegir un número primo pequeño (p), un cuerpo común para todos <img class="EMIRef" id="583112125-imgf000012-0027" /> los pares de claves y un - isomorfismo unos <img class="EMIRef" id="583112125-imgf000012-0030" /> <img class="EMIRef" id="583112125-imgf000012-0026" /> parámetros ( <img class="EMIRef" id="583112125-imgf000012-0029" /> de modo que <img class="EMIRef" id="583112125-imgf000012-0025" /> una aplicación invectiva h y una aplicación que se <img class="EMIRef" id="583112125-imgf000012-0028" /> define de tal forma que si j está en la imagen de <img class="EMIRef" id="583112125-imgf000012-0024" /> componente j-esima es <img class="EMIRef" id="583112125-imgf000012-0023" /> Si <img class="EMIRef" id="583112125-imgf000012-0019" /> ,1a componente se elige aleatoriamente en con la <img class="EMIRef" id="583112125-imgf000012-0020" /> <img class="EMIRef" id="583112125-imgf000012-0022" /> condición de que al componer H<0>con la biyección natural entre <img class="EMIRef" id="583112125-imgf000012-0021" /> las componentes de la imagen de <img class="EMIRef" id="583112125-imgf000012-0016" /> <img class="EMIRef" id="583112125-imgf000012-0017" /> por la aplicación de relleno (padding) son no nulas. <img class="EMIRef" id="583112125-imgf000012-0018" /> <img class="EMIRef" id="583112125-imgf000012-0015" /> b) Construir una aplicación polinómica que se obtiene como <img class="EMIRef" id="583112125-imgf000012-0014" /> composición <img class="EMIRef" id="583112125-imgf000012-0013" /> de cinco aplicaciones según el Diagrama 1 , donde las aplicaciones son isomorfismos lineales y las <img class="EMIRef" id="583112125-imgf000012-0011" /> <img class="EMIRef" id="583112125-imgf000012-0012" /> aplicaciones son altamente no lineales y caóticas <img class="EMIRef" id="583112125-imgf000012-0010" /> <img class="EMIRef" id="583112125-imgf000012-0001" /> La construcción de las aplicaciones lineales se realiza como una <img class="EMIRef" id="583112125-imgf000012-0031" /> composición de aplicaciones biyectivas; las aplicaciones G<1>definida en definida en , no lineales y biyectivas en <img class="EMIRef" id="583112125-imgf000012-0003" /> <img class="EMIRef" id="583112125-imgf000012-0004" /> <img class="EMIRef" id="583112125-imgf000012-0002" /> son esencialmente una exponenciación de vectores <img class="EMIRef" id="583112125-imgf000012-0006" /> con exponentes las matrice respectivamente, con las <img class="EMIRef" id="583112125-imgf000012-0007" /> <img class="EMIRef" id="583112125-imgf000012-0005" /> siguientes propiedades: - Las entradas de son de la forma p° <img class="EMIRef" id="583112125-imgf000012-0009" /> - Se fijan dos números enteros pequeños s y t, y elige de tal forma <img class="EMIRef" id="583112125-imgf000012-0008" /> que cada fila de A<t>tiene a lo más s entradas no nulas, y la matriz B<2>se elige de forma que cada fila tiene a lo más t entradas no nulas. Con estas condiciones se tiene que cada componente tiene a lo más depende de la mezcla M <img class="EMIRef" id="583112125-imgf000013-0016" /> y cada monomio tiene a lo más s + t variables. De esta forma se consigue que si s y t son pequeños el número de monomios es relativamente pequeño. c) Generar la clave pública como el par <img class="EMIRef" id="583112125-imgf000013-0015" /> a partir del que se construye la aplicación de cifrado D <img class="EMIRef" id="583112125-imgf000013-0014" /> 2. Método para producir un sistema de cifrado con clave pública, según reivindicación 1 , donde para definir G<1>se elige una matriz A <img class="EMIRef" id="583112125-imgf000013-0013" /> tal que det( son primos entre si y se define G<1>por la fórmula: <img class="EMIRef" id="583112125-imgf000013-0012" /> <img class="EMIRef" id="583112125-imgf000013-0011" /> La condición mcd (det hace que G<l>sea una biyección en con inversa definida como en la fórmula anterior por la <img class="EMIRef" id="583112125-imgf000013-0010" /> <img class="EMIRef" id="583112125-imgf000013-0009" /> matriz inversa de A<1>Hay que destacar que la condición mcd (det <img class="EMIRef" id="583112125-imgf000013-0008" /> 1 ) = 1 es equivalente a que exista la inversa de y esta <img class="EMIRef" id="583112125-imgf000013-0007" /> es la propiedad clave de todo el invento. La aplicación G<2>se define de la misma forma: se elige una matriz tal que son <img class="EMIRef" id="583112125-imgf000013-0005" /> <img class="EMIRef" id="583112125-imgf000013-0006" /> primos entre si y se define G<2>por la fórmula: <img class="EMIRef" id="583112125-imgf000013-0001" /> Sí <img class="EMIRef" id="583112125-imgf000013-0003" /> son las coordenadas iniciales las <img class="EMIRef" id="583112125-imgf000013-0002" /> coordenadas finales la composición de las cinco aplicaciones que dan F permite calcular las componentes F¡ qué son polinomios <img class="EMIRef" id="583112125-imgf000013-0004" /> generalmente con muchos monomios. 3. Método para producir un sistema de cifrado con clave pública, según reivindicaciones <img class="EMIRef" id="583112125-imgf000014-0002" /> que además comprende la generación de una clave privada que consiste en y las aplicaciones que hay que <img class="EMIRef" id="583112125-imgf000014-0029" /> <img class="EMIRef" id="583112125-imgf000014-0003" /> invertir para descifrar un mensaje calculando <img class="EMIRef" id="583112125-imgf000014-0004" /> dado un mensaje cifrado <img class="EMIRef" id="583112125-imgf000014-0006" /> , se calcula y se descartan las <img class="EMIRef" id="583112125-imgf000014-0005" /> entradas aleatorias de dadas por h. <img class="EMIRef" id="583112125-imgf000014-0007" /> 4. Método para producir un sistema de cifrado con clave pública, según reivindicación 3, donde la evaluación de los polinomios F<t>en para <img class="EMIRef" id="583112125-imgf000014-0009" /> obtener el mensaje cifrado se realiza de forma eficiente y rápida a partir <img class="EMIRef" id="583112125-imgf000014-0008" /> de la evaluación de sus monomios del siguiente modo: si de es el número de monomios que contiene un grupo de polinomios m, se pueden calcular dichos monomios multiplicado entre sí los monomios iniciales elevados a <img class="EMIRef" id="583112125-imgf000014-0010" /> las entradas de G<1>y G<2>como sigue : - Si se define el producto <img class="EMIRef" id="583112125-imgf000014-0011" /> <img class="EMIRef" id="583112125-imgf000014-0012" /> mj] como la lista que contiene todos los productos <img class="EMIRef" id="583112125-imgf000014-0013" /> - Detonando por a la lista de monomios de x<k>la <img class="EMIRef" id="583112125-imgf000014-0014" /> aplicación G<1>hace que la lista de monomios de cada vector de la imagen sea que tiene n<s>monomios. La aplicación M <img class="EMIRef" id="583112125-imgf000014-0015" /> hace que en la lista de monomios de <img class="EMIRef" id="583112125-imgf000014-0017" /> aparecen los de más los de <img class="EMIRef" id="583112125-imgf000014-0018" /> los vectores que se añaden al final. SI es el número de vectores <img class="EMIRef" id="583112125-imgf000014-0016" /> distintos añadido en total serán a lo más <img class="EMIRef" id="583112125-imgf000014-0019" /> monomios. Al aplicar G<2>cada monomio d produce a lo mas Mo - <img class="EMIRef" id="583112125-imgf000014-0020" /> monomios, donde <img class="EMIRef" id="583112125-imgf000014-0021" /> <img class="EMIRef" id="583112125-imgf000014-0028" /> - Para obtener los coeficientes de cada monomio en F¡ se toma un número k de mensajes iniciales <img class="EMIRef" id="583112125-imgf000014-0022" /> se calculan sus correspondientes mensajes cifrados Cada componente es de la forma <img class="EMIRef" id="583112125-imgf000014-0023" /> <img class="EMIRef" id="583112125-imgf000014-0027" /> dado que los son conocidos, estas igualdades <img class="EMIRef" id="583112125-imgf000014-0024" /> <img class="EMIRef" id="583112125-imgf000014-0025" /> dan lugar a k ecuaciones lineales donde las incógnitas son los coeficientes tomando k suficientemente grande para que las <img class="EMIRef" id="583112125-imgf000014-0026" /> ecuaciones sean linealmente independientes se resuelven de manera eficiente para obtener los coeficientes de F. • Se pueden evaluar los monomios de <img class="EMIRef" id="583112125-imgf000014-0001" /> usando el mismo algoritmo. Se empieza con la lista de las coordenadas de un mensaje dado c, es decir se obtiene como resultado una lista <img class="EMIRef" id="583112125-imgf000015-0001" /> que da la evaluación de los monomios de cada F, . De esta forma se evalúan los polinomios F¡ con un número significativamente menor de multiplicaciones y exponenciaciones en F<4>. Método para producir un sistema de cifrado con clave pública, según cualquiera de las reivindicaciones anteriores, que además comprende la generación de una firma digital para un mensaje z: <img class="EMIRef" id="583112125-imgf000015-0002" /> donde el usuario tiene que calcular un valor x. tal que y es posible <img class="EMIRef" id="583112125-imgf000015-0003" /> que no exista tal χ porque la aplicación no es sobreyectiva. Para resolver esto se firma un mensaje de longitud <img class="EMIRef" id="583112125-imgf000015-0005" /> se utiliza una aplicación invectiva de la misma forma que con h, es decir, <img class="EMIRef" id="583112125-imgf000015-0004" /> se completan las entradas de z con valores aleatorios en las coordenadas que no están en la imagen de hasta obtener La longitud del mensaje a firmar <img class="EMIRef" id="583112125-imgf000015-0014" /> <img class="EMIRef" id="583112125-imgf000015-0013" /> <img class="EMIRef" id="583112125-imgf000015-0015" /> no tiene porqué ser fijada a priori. la firma se verifica calculando <img class="EMIRef" id="583112125-imgf000015-0007" /> y descartando las entradas aleatorias usando La firma se verifica <img class="EMIRef" id="583112125-imgf000015-0012" /> calculand descartando las entradas aleatorias usando Λ, <img class="EMIRef" id="583112125-imgf000015-0006" /> Método para producir un sistema de cifrado con clave pública, según reivindicaciones anteriores, donde una de las partes (por ejemplo ALICIA) puede firmar un mensaje cifrado para la otra parte (por ejemplo BOB) sin necesidad de usar el mecanismo de relleno de la siguiente forma: si x es el mensaje, se cifra con la clave pública de BOB obteniendo si z <img class="EMIRef" id="583112125-imgf000015-0008" /> <img class="EMIRef" id="583112125-imgf000015-0009" /> no se puede firmar, entonces no se pueden añadir entradas aleatorias porque su longitud es máxima (Ni = e n-m) pero se puede cifrar de nuevo con <img class="EMIRef" id="583112125-imgf000015-0010" /> obteniendo un mensaje cifrado distinto porque el cifrado es no determinista <img class="EMIRef" id="583112125-imgf000015-0011" /> =D M(x) y se firma Z<t>Este proceso puede repetirse hasta cero. Método para producir un sistema de cifrado con clave pública, según reivindicaciones anteriores, que comprende además la encapsulación de claves (KEM) que permite a las dos partes ponerse de acuerdo en una clave común para un cifrado simétrico. Para ello, ambas partes se ponen de acuerdo en una función hash HS y una de las partes genera un mensaje aleatorio x y lo envía cifrado a la otra parte. De esta forma, ambos pueden calcular w HS(x) .
