Underc0de

Matemáticas en la Criptografía

Las matemáticas como ciencia siempre han tenido gran penetración en todas las áreas de desarrollo de la humanidad, a veces de manera indirecta, otras de manera más inmediata. Desde sus campos más abstractos como la teoría de los números, la geometría algebraica, la topología, el análisis real y complejo, hasta los más aplicados, como la probabilidad, las ecuaciones diferenciales. Todas tienen una aplicación a diferentes áreas de la tecnología, y es imposible desligar a las matemáticas del desarrollo actual en todo el mundo.

Sin embargo no es fácil en ocasiones explicar cómo, definiciones, teoremas, metateoremas, o alguna teoría abstracta puede llegar a convertirse en el ala de avión, en un medicamento, en algún dispositivo electrónico.

A la mitad de la década de los 70s, se dio a conocer al mundo, uno de los descubrimientos más importantes en la criptografía moderna, la invención de la criptografía de clave pública.
Por una parte fue notable la solución del problema de la distribución de claves, y por el otro fue interesante que haya sido con problemas matemáticos que hasta esos momentos parecían no atraer la atención, como el problema de la factorización entera, y el problema del logaritmo discreto.

A partir de esos años han sido muchas las aportaciones que las matemáticas han tenido a la criptografía de clave pública, y en contra de las predicciones de los "matemático-fóbicos", con la designación del nuevo estándar de la criptografia simétrica AES, ahora también la criptografía simétrica es área de trabajo del álgebra.

En esta sección listamos de manera muy ligera algunas de las aportaciones de las matemáticas que en estos momentos tienen importante penetración en la criptografía. El objetivo es tratar de mostrar como deferentes áreas han sido usadas en la criptografía.

1.- Numeros Primos: Desde el inicio de la criptografía fueron usados los números enteros, más particularmente se ha trabajado con elementos de ℤ p, se podía decir que el cifrado de mensajes se reducía a encontrar una buena permutación en ℤp y esto prevaleció casi en gran parte de la historia de la criptografía. No fue sino hasta el comienzo de la criptografía moderna a la par del invento de la computadora y los algoritmos, cuando nuevas formas de cifrar información fueron surgiendo. En esos tiempos los números primos no eran de mucha trascendencia, simplemente se usaba que en ℤ p debería de ser primo para que todos los elementos tuvieran inverso multiplicativo.

En la actualidad, los números primos tienen diversas aplicaciones, entre las cuales están: la generación de claves RSA, la generación del dominio de parámetros para firma digital DSA, del esquema de intercambio de claves DH y las versiones elípticas EDSA, y EDH.

Es sabido que existen una cantidad infinita de números primos y además que tienen una distribución "uniforme". De donde se puede deducir que siempre es posible encontrar un número primo de cualquier longitud. La base fundamental de este hecho es el Teorema del Número Primo, conectado con la Hipótesis de Riemann, y todas las funciones relacionadas.

Un problema fundamental es el encontrar números primos de cierta longitud, desde 128 hasta 1024 bits, de manera eficiente, en muchos casos son necesarios para aplicaciones de tiempo real.
Este problema había quedado abierto ya que solo se contaban con algoritmos probabilísticos (método de Miller-Rabin). Que aunque la probabilidad de obtener un error era insignificante (1/2100) para propósitos prácticos. Siempre existía la inquietud de lograr un método deterministico y eficiente, finalmente fue logrado por un grupo de investigadores de la India. En Agosto del 2002 Agrawal, Kayal and Saxena (AKS), encontraron un método determinístico y de tiempo de ejecución polinomial para encontrar números primos. Recientemente se dieron algunas mejoras del método AKS que fueron hechas por Berrizbeitia, Cheng, y Bernstein. El Método AKS se basa en una generalización del Teorema Pequeño de Fermat, y dice que un número n es primo si y sólo si (x-a)n = xn-a en el anillo ℤn

• /(xr-1), donde los números a,r son elegidos adecuadamente.
  
  
  2.- Factorización: Paralelamente a la búsqueda de primos, y como es conocido del sistema de clave pública RSA que basa su seguridad en la imposibilidad de factorizar un número de cierta longitud producto de dos números primos. El problema de la factorización es fundamental en la criptografía, y en los últimos años es quizá el problema más estudiado. En la actualidad se tienen diferentes métodos de factorización de números enteros de diferentes formas, y existe una estrategia estándar para poder factorizar un número entero, sin embargo se considera aún "imposible" de hacerlo en ciertas condiciones.
  
  La historia de la factorización se puede resumir tomando como ejemplo los números de Fermat.
  
  Fermat había conjeturado que los números de la forma 22n+1, eran primos a estos números se les llamo números de Fermat Fn, inmediatamente se observa que F0=3, F1=5, F2=17, F3=257, F4=65537, son primos, sin embargo a partir de F5 los números ya no son primos. Se ha tomado como ejemplo ilustrativo la factorización de algunos números de Fermat.
  
  Así en 1732 se factorizó F5, por Euler.
  En 1880 se factorizó F6, por Landry y Lasseur.
  En 1970 se factorizó F7=65537, por Morrison y Brillhart con el método de Fracciones Continuas.
  En 1980 se factorizó F8=65537, Brent y Pollard con el método "rho" de Pollard.
  En 1990 fue factorizado F9=65537, por Lenstra usando el método "Number Field Sieve(NFS)".
  En 1995 se factorizó F10=65537, por Brent usando el método "Elliptic Curves Method (ECM)"
  En 1989 se factorizo F11=65537, también por Brent y con el mismo ECM.
  Más información (actualizada)sobre la factorización de los números de Fermat y mucha más puede encontrarse en la  Página del Número Primo
  
  
  3.- Operaciones en el anillo ℤ n: también se ha usado ampliamente el anillo ℤ n , por ejemplo al operar con el sistema RSA. También se han usado funciones y resultados relacionados como la función phi de Euler, la función Lamda de Carmichael, el teorema Chino del residuo etc.
  
  
  4.- Problema del Logaritmo Discreto PLD: este problema esta definido en general sobre un grupo cíclico, en la práctica se toma un elemento de algún grupo abeliano y el PLD se define en el subgrupo cíclico generado por ese elemento.
  Dado un generador a y un elemento b en el subgrupo generado por a, entonces el resolver el PLD, es encontrar un número entero x, tal que b=ax.
  Este problema fue propuesto por Diffie y Helmman en 1976, a partir de ahí nace de la criptografía de clave pública. Desde su descubrimiento una de las ramas de investigación mas intensas, ha sido encontrar un grupo "particular" donde el PLD se defina y no pueda ser resuelto en tiempo polinomial. Esto implica en gran parte poder diseñar sistemas criptográficos de clave pública seguros. El grupo más simple y más usado es el grupo multiplicativo ℤ *p. En este caso hay números p donde es fácil de resolver el PLD llamados "primos suaves", y hay otros donde es difícil de resolver que son los que se usan en criptografía, particularmente en el esquema de firma digital DSA, y el esquema de intercambio de claves DH. Uno de los principales problemas en la criptografía es encontrar grupos ya sea donde el PLD sea fácil de resolver (existe un algoritmo eficiente), o contrariamente encontrar grupos donde el problema sea difícil de resolver (no haya un algoritmo eficiente). La criptografía elige grupos donde el PLD no es fácil, y descarta los grupos donde el PLD es fácil.
  
  
  5.- Campos finitos generales: es conocido que todo campo finito tiene la forma GF(qn), donde q=pm. El grupo multiplicativo donde se define el PLD es en GF*(qn). Si p=2, se tiene la característica adicional de ser muy bien vistos en desarrollo de hardware, por lo que son usados ampliamente para implementar esquemas criptográficos. Últimamente los campos finitos de característica 3, son también considerados en aplicaciones eficientes de firmas cortas dentro de la criptografía bilineal.
  
  
  6.-Curvas elípticas: uno de los grupos más importantes donde se ha definido el PLD es el grupo de puntos racionales de una curva elíptica definida en un campo finito. Las curvas elípticas habían sido una de los campos más abstractos dentro de las matemáticas, sin embargo fue en 1985 cuando N. Koblitz y V. Miller propusieron el grupo que genera una curva elíptica para que sea definido el PLD y así poder ser usado en los sistemas criptográficos. En la actualidad se considera a las curvas elípticas una de las mejores opciones para ser usadas, y la mayoría de los estándares criptográficos las consideran. Hoy día se considera que los esquemas que usan curvas elípticas son los más seguros y versátiles, y varios estándares e instituciones en el mundo los recomiendan. Las principales características de un sistema elíptico son el reducido tamaño de las claves y que el PLD elíptico tiene un tiempo totalmente exponencial para su solución .
  
  
  7.-Curvas hiperelípticas: de manera natural la generalización inmediata a las curvas elípticas son las curvas hiperelípticas. Ahí es posible definir de manera similar esquemas criptográficos, ahora el grupo es el Jacobiano de una curva hiperelíptica. Las curvas hiperelípticas son usadas en Europa y Japón de manera comercial.
  
  
  8.-Curvas algebraicas: con la idea de generalizar más, podemos buscar otro tipo de curvas, como las curvas de Picard, donde también se pueda definir un grupo o casi un grupo y entonces definir el PLD.
  
  
  9.- Campos numéricos algebraicos: otra forma de definir el PLD es considerando campos numéricos reales, es decir campos donde los elementos tienen la forma a+db, donde a, b son números reales y d es una raíz no real adecuada. En estos campos se pueden definir ciertos conjuntos llamados "ideales", y es en el conjunto de ideales donde se define el PLD. Este tipo de criptografía es usada en Europa de manera comercial.
  
  
  10.- Grupos especiales: un grupo especial del cual se ha hablado últimamente es el subgrupo G de GF(p6), de orden q, donde q es un primo grande que divide a p2-p+1, con p congruente con 2 mod 3. Este esquema conocido como XTR tiene la particular ventaja de operar con la aritmética de GF(p2) y ser tan seguro como el grupo GF(p6).
  
  
  11.- Lattices: otra área muy usada en criptografía es la teoría de retículas o lattices. Donde ahora en lugar del problema de la factorización o el PLD, tenemos el problema de encontrar un vector con longitud mínima dada una lattice. En este tipo de criptografía se han definido varios esquemas de cifrado y de firma digital, por ejemplo es esquema de Goldreich, el esquema de Ajtai-Dwork, y el sistema NTRU(Number Theory Research Unit). Otra manera de usar las lattices en criptografía es usandolas como un ataque a esquemas como a RSA.
  
  
  12.- Mapeos bilineales, Weil y Tate: recientemente un área que ha tenido gran atención ha sido el tipo de criptografía que usa mapeos bilineales, particularmente el mapeo de Weil y de Tate. Este tipo de mapeos tiene dos nuevos elementos que añaden a la criptografía de clave pública, el primero es la definición del problema bilineal de Diffie-Hellman y el otro que se pueden implementar esquemas criptográficos basados en la identidad, es decir, el usar una "identidad" del usuario como clave pública. Esto enmarca a este nuevo tipo de criptografía en lo que se ha llamado "ID-based cryptography" o criptografia basada en la identidad (CBI). Por otra parte la criptografía que hace uso de mapeos bilineales es conocida como criptografía bilineal(CB), "pairing cryptography". Hasta el momento se han creado una buena cantidad de esquemas de firma digital, de cifrado, de intercambio de claves, etc. que usan la criptografía bilineal. También hay una buena cantidad de preguntas y problemas por resolver. la CBI, y la CB son campos de intensa investigación en nuestros días.
  
  
  13.- Grupos de trenzas, "Braid Groups": otro tipo diferente de grupos donde se han propuesto sistemas criptográficos son los grupos de trenzas, aunque aquí el grupo no es abeliano, es posible definir una especie de "medio PLD" y así definir un esquema criptográfico. Es también un campo de amplia investigación en nuestros días.
  
  
  14.- Ecuaciones Multivariables: aunque a través de la historia de la criptografía el problema de resolver un sistema de ecuaciones con muchas variables había estado presente. Ha sido hasta los últimos años que ha ganado gran popularidad este nuevo tipo de criptografía. Es reconocida por varios estándares en la actualidad lo que la convierte como una de las mejores opciones en ciertas aplicaciones. Su gracia recae en tener claves de longitud equivalente a la criptografía simétrica y en que su complejidad de ataque es totalmente exponencial. Algo también notable de este tipo de criptografía es que existe un algoritmo llamado XL para resolver cierto tipo de sistemas de ecuaciones y que ha sido propuesto para atacar al sistema simétrico AES.
  
  
  15.- Criptografía simétrica: uno de los campos donde las matemáticas no habían sido usadas de manera intensa, era la criptografía simétrica. Sin embargo con sorpresa en Septiembre del 2000 una institución de estándares Norteamericana, el NIST, dio a conocer que el algoritmo elegido para ser usado como estándar comercial occidental fuera "Rijndael". Rijndael esta basado en la representación de un byte (8 bits) visto como elemento del campo finito GF(28), y sus operaciones básicas son operaciones sobre campos finitos y anillos de polinomios.
  
  
  Fuente: [email protected]

Maravilloso aporte!!!!!
Ya lo incluí en el índice de temas importantes! (http://underc0de.org/foro/index.php?topic=9549.msg33664#msg33664)
Saludos!

CrazyKade

A sus órdenes siempre.  ️


Enviado desde iOS utilizando Tapatalk.

Muy Buena info...
Un abrazo

Gracias!!


Enviado desde iOS utilizando Tapatalk.

excelente post mas el tema de los primos es algo muy interesante el estudio de los polinomios

que entiendes por curvas elipticas tambien se usa para esto.

Que maravilla que las matemáticas sean el alma de todo el universo!!!