Criptografía de la A-Z

volver

Criptosistemas de Llave Pública (Algortimos Asimétricos)

Los Criptosistemas de clave pública fueron inventados a finales de los años 70, con ayuda del desarrollo de la teoría de complejidad alrededor de esa época.

Observando que basados en la dificultad de un problema y de los miles de años que llevaría resolverlo y con un poco de suerte, se observó que un criptosistema podría ser desarrollado teniendo dos claves, una privada y una pública.

Con la clave pública se puede cifrar mensajes, y descifrarlos con la clave privada. Así el propietario de la clave privada sería el único que podría descifrar los mensajes, pero cualquier persona que conozca la clave pública podría enviarlos en forma privada.

Otra idea que se observó fue la del intercambio de claves. En una comunicación entre dos partes sería de mucha utilidad generar una clave secreta común para cifrado a granel usando un criptosistema de clave secreta (por ejemplo, cifrado de bloques).

De hecho, Whitfield Diffie y Martin Hellman utilizaron ideas de la teoría de números para construir un protocolo de intercambio de claves, el cual dio comienzo a la era de los criptosistemas de clave pública.

Poco después, Ronald Rivest, Adi Shamir, y Leonard Adleman desarrollaron un criptosistema que fue el primer criptosistema de clave pública real, capaz de cifrar y manejar firmas digitales.

Más adelante fueron apareciendo otros criptosistemas de clave pública que usaron diferentes ideas subyacentes (por ejemplo, los problemas de la mochila, diversos grupos en campos finitos, y los enrejados).

Muchos de ellos resultaron ser inseguros. Sin embargo, el protocolo Diffie-Hellman y el RSA parecen ser los dos más fuertes hasta el momento.

Terminología

La dificultad computacional del problema es el ingrediente básico en cualquier criptosistema de clave pública. La seguridad de los criptosistemas esta basada en el hecho de que la clave privada puede ser computada desde la clave pública únicamente solucionando este difícil problema. A continuación presentaremos alguna terminología relevante usada en la criptografía de clave pública.

Algoritmo

Un algoritmo es una descripción explícita de como debe ser resuelto un problema computacional en particular. La eficiencia del algoritmo puede ser medida en base a la cantidad de pasos elementales que se necesiten para resolver dicho problema.

Complejidad computacional

Primos: Un número primo es un número que no tiene ningún divisor a excepción de sí mismo y de 1. Así los números enteros 2, 3, 5, 7, 11... etc. son primos. Hay infinitos numeros primos y el record del mayor numero primo conocido ya fue quebrado varias veces.

Descomponer en factores: Cada número entero se puede representar únicamente como el producto de números primos. Por ejemplo, 10 = 2 * 5 y es único (excepto por el orden de los factores 2 y 5). El arte de la descomposición en factores es casi tan viejo como las matemáticas. Sin embargo, el estudio de algoritmos rápidos para descomponer en factores tiene solamente algunas décadas.

Un posible algoritmo para descomponer en factores un número entero es dividir la entrada por todos los números primos pequeños interactivamente hasta que el resto sea primo. Esto es eficiente solamente para los números enteros que son, por ejemplo, menores que 10^16 que requieren intentar con todos los primos hasta 10^8.

En los Criptosistemas de clave pública basados en el problema de descomponer en factores, los números manejados son del tamaño 10^300 y éste requeriría intentar con todos los primos hasta 10^150 que son alrededor de 10^147 según el teorema del número primo. Esto excede lejos el número de átomos en el universo, y es poco probable que sea enumerado.

El caso fácil de la descomposición en factores es aquel donde el número entero dado posee únicamente factores primos pequeños. Por ejemplo, 759375 es fácil de descomponer en factores escribiendolo 3^5 * 5^5. En criptografía deseamos utilizar solamente aquellos números enteros que tengan solamente factores primos grandes. Seleccionamos preferiblemente un número entero con dos factores primos grandes, como se hace en el criptosistema de RSA.

Actualmente uno de los mejores algoritmos de descomposición factorial es el conocido como Criba Numérica de campo (NFS) que consiste en una fase de tamizado y un paso de matriz. La fase de tamizado se puede distribuir entre una gran cantidad de participantes, pero el paso de matriz necesita ser realizado en superordenadores. La eficacia del algoritmo NFS se vuelve evidente para los números enteros muy grandes, puede factorear cualquier número entero del tamaño 10^150 en pocos meses. El algoritmo del NFS toma el tiempo sub-exponencial (que todavía no es muy eficiente).

Logaritmos discretos: Otra clase importante de problemas es el problema de encontrar n dada solamente y tal que y = g^n. El problema es fácil para los números enteros, pero cuando estamos trabajando en un conjunto levemente diverso se vuelve muy difícil.

Este problema actualmente se considera tan difícil como la descomposición en factores. El mejor método conocido hasta el momento es el algoritmo NFS para logaritmos discretos (que utiliza ideas similares como el NFS para descomponer en factores).

El problema del logaritmo discreto puede parecer más complicado que la factorización de números enteros, pero tienen cierta similitud. Muchas de las ideas que funcionan para la factorizacion se pueden aplicar también en el seteo de logaritmos discretos.

El problema del logaritmo discreto se puede aplicar en muchos otros seteos, tales como curvas elípticas. El problema del logaritmo discreto sobre las curvas elípticas es utilizado comúnmente en criptografía de la clave pública. Una razón es que es que el algoritmo NFS no funciona quí. Hay otros métodos para computar logaritmos discretos sobre curvas elípticas, pero parece incluso más difícil el logaritmo discreto sobre curvas elípticas que sobre GF(p). Esto tiene también el efecto de que hay algunas ventajas en el tamaño de la clave para usar criptosistemas de clave pública basados en curvas elípticas en comparación a criptosistemas basados en factorización.

Mochilas: Dado un pequeño conjunto de números enteros, el problema de la mochila consiste en determinar un subconjunto de estos números enteros tales que su suma sea igual a un número entero dado. Por ejemplo, dado (2, 3, 5, 7) y 10, podemos encontrar la solución 2 + 3 + 5 = 10, y solucionamos así el problema de la mochila, por búsqueda de fuerza bruta.

Criptosistemas prácticos

El interés amplio en criptografía de clave pública ha producido varios criptosistemas prácticamente importantes. A continuación se enumeran en orden del problema subyacente.

Como pauta básica, un criptosistema de clave pública se construye a partir de un problema difícil como sigue: tomar un problema difícil para el cual se pueda encontrar un caso que se pueda solucionar en tiempo polinómico. Para cifrar un mensaje, convertir el mensaje en un caso fácil del problema difícil, entonces se utiliza la clave pública para convertir el problema fácil en difícil. El resultado entonces se envía al recipiente a través de un canal inseguro. Para descifrar uso la clave privada para convertir el problema difícil en el fácil y solucionarlo para recuperar el mensaje. Todos los criptosistemas de la clave pública utilizan este principio, aunque difieren significativamente en los detalles (como el problema subyacente o la estructura de las claves pública y privada).

Para un buen examen en longitudes de clave apropiadas ver Seleccionando tamaños de claves criptográficas de Lenstra y Verheul (publicado en Criptografía de clave pública 2000). Presentan un análisis completo de los tamaños de clave para casi todos los criptosistemas.

Debajo, junto con cada criptosistema, encontrarás las recomendaciones actuales para los tamaños de clave cuando sea apropiado. Estas recomendaciones no son siempre iguales a las de Lenstra y Verheul.

Factorización: RSA, Rabin

• RSA (Rivest-Shamir-Adleman) es el algoritmo de llave pública mas utilizado generalmente. Puede ser utilizado para la encriptación como para las firmas digitales. La seguridad del RSA el generalmente considerada equivalente a la factorización, aunque esto no se ha comprobado.

  Los cálculos del RSA se realizan con el módulo entero n=p*q, para dos primos grandes y secretos p y q.

  Mas detalles estan disponibles en muchos recursos, tal como en el Manual de criptografía aplicada.

  El tamaño de la llave (el tamaño del módulo) debería ser mas grande que 1024 bits (esto es, debe ser de la magnitud de 10^300) para un márgen razonable de seguridad. Llaves de tamaño, sopongamos, de 2048 bits deberían brindar seguridad por décadas.

  Grandes avances en la factorización de enteros largos podrían hacer vulnerable al RSA, pero se conocen también otros ataques contra variantes específicas. Buenas implementaciones utilizan redundancia para evitar ataques utilizando la estructura multiplicativa del texto cifrado. RSA es vulnerable a los ataques de texto plano seleccionado y ataques de hardware y de fallas . También existen ataques contra muchos pequeños exponentes, así como también contra factorizaciones parciales reveladas del módulo.

  Las implementaciones apropiadas del algoritmo RSA con redundancia es bien explicada en el estandar PKCS (ver la definición en el laboratorio RSA).

  El algoritmo plano RSA no debería ser aplicado en ninguna aplicación. Se recomienda que las implementaciones sigan el estandar pues tiene también la ventaja adicional de la inter-operabilidad con la mayoría de los protocolos más importantes.

  El RSA es el algoritmo de llave pública más importante. Fue patentado en los Estados Unidos (la patente expiró en el año 2000).

• El criptosistema Rabin debe ser visto como un "pariente" del RSA, aunque tenga un proceso de decodificación muy distinto. Lo que lo hace interesante es que romper Rabin es probablemente equivalente a factorearlo.

  Rabin utiliza el exponente 2 (o aún cualquier entero) en lugar de un entero peculiar como el RSA. Esto tiene dos consecuencias. Primero, se puede probar que el criptosistema Rabin es equivalente al factoreo; segundo, la desencriptación se hace mas difícil, al menos en algunos aspectos. Como es equivalente a factorear el módulo, el tamaño del módule es el parámetro de seguridad más importante. Módulos de mas de 1024 bits se asumen como seguros.

  No hay actualmente un estandar para el algoritmo Rabin pero es explicado en varios libros. El proyecto IEEE P1363 podría proponer un estandar y de esta manera hacerlo ampliamente utilizado.

  Equivalente a factorear significa solo que ser capaz de desencriptar cualquier mensaje encriptado por el criptosistema Rabin permite factorear el módulo. De esa manera no hay garantías de seguridad en un sentido fuerte.

Logaritmos Discretos: Diffie-Hellman, ElGamal, DSS

• Diffie-Hellman es un protocolo normalmente utilizado para el intercambio de llaves.

  En muchos protocolos criptográficos dos partes desean establecer comunicación. Sin embargo, asumen que inicialmente no poseen un secreto y de esta manera no pueden utilizar un criptosistema de llave secreta. El intercambio de llaves por el protocolo Diffie-Hellman remedia esta situación permitiendo la constricción de una llave secreta común sobre un canal de comunicaciín inseguro.

  Se basa en un problema relacionado con logaritmos naturales, llamado el problema Diffie-Hellman. Este problema es considerado difícil, y es en algunas instancias tan difícil como el problema de logaritmos discretos.

  El protocolo Diffie-Hellman se considera generalmente seguro cuando se utilizan grupos matemáticos apropiados. En particular, el elemento generador utilizado en la "exponenciación" debería tener un período grande.

  Algoritmos de logaritmos discretos se pueden utilizar para realizar ataques contra Diffie-Hellman, y con ataques pasivos que es lo mejor de lo actualmente posible, asumiendo la elección de parámetros correctos.

  Se pueden generar problemas sutiles por la mala elección del generador. Se han escrito muchos artículos sobre los problemas que pueden surgir. Una de las referencias más notorias es Oorschot and Wiener's en Acuerdos de llave Diffie-Hellman con exponentes pequeños (Eurocrypt '96).

  Ataques contra Diffie-Hellman también incluyen el ataque de hombre en medio. Este ataque requiere intervención adaptativa, pero es muy fácil en la práctica si el protocolo no utiliza contramedidas tales como firmas digitales.

  Diffie-Hellman usualmente no es implementado en hardware, y así los ataques de hardware no son una amenaza importante. Este puede cambiar en el futuro, cuando las comunicaciones móbiles se extiendan mas.

• DSS (Digital Signature Standard - Estandar de Firma Digital): Una mecanismo de unicamente-firma avalado por el gobierno de los Estados Unidos. El algoritmo DSA (Digital Signature Algorithm - Algoritmo de Firma Digital) fundamental es similar al algoritmo de firma utilizado por ElGamal o por el Schnorr. También es bastante eficiente, pero no tanto como el RSA para verificación de firma. El estandar define el DSS para utilizar la función hash SHA-1 exclusivamente para calcular el resúmen del mensaje.

  El problema principal con el DSS es el tamaño del subgrupo fijo (el orden del elemento generador), el cual limita la seguridad a alrededor de sólo 80 bits. Los ataques de hadware pueden tener que ver con algunas implementaciones de DSS. Sin embargo, es ampliamente aceptado y utilizado como un buen algoritmo.

• El codificador de llave publica ElGamal: este es una extensión de la idea original de Diffie/Hellman de compartir la generación secreta. Escencialmente, genera un secreto compartido y lo utiliza como un relleno por única vez para encriptar un bloque de dato. ElGamal es el predecesor del DSS y hoy es perfectamente utilizable, a pesar de que no se han creado amplios estandares para él.

• Criptosistemas de Curva Elíptica: son otra forma de implementar los métodos de logaritmos discretos. Una curva elíptica es basicamente un conjunto de puntos que satisfacen la ecuación y^2=x^3 + ax + b cuando se los considera dentro de un campo finito de características p (donde p debe ser mayor que 3). Una ecuación ligeramente diferentese necesita para el caso de características pequeñas, p=2 y p=3.

  Los puntos en una curva elíptica pueden ser agregadas conjuntamente y forman una estructura denominada grupo (en realidad un grupo abeliano). Es justo una manera de decir que puedes hacer aritmética con ellos como lo puedes hacer con enteros cuando solo utilizas adiciones y sustracciones.

  En consideración a la criptografía, las curvas elípticas tienen varios beneficios teóricos y también prácticos.

  Un beneficio práctico de la no existencia de un algoritmo discreto de cálculo para curvas elípticas es que el tamaño de la llave, así como también la firma digital producida y el mensaje encriptado son menores. Efectivamente, una manera simple de calcular el límite se seguridad para el tamaño de la llave es tomar un tamaño de la llave para el criptosistema de llave secreta en bits y luego solo multiplicarlo por 2. Esto da una estimación gruesa, esto es bueno al momento de una instancia genérica de curvas elípticas.

  Las curvas elípticas pueden ser implemntadas eficientemente en hardware y software, y compiten bien en velocidad con criptosistemas tales como el RSA y el DSS. Existen varios intentos de estandarización para criptosistemas de curvas elípticas (por ejemplo, ECDSA y ANSI). Por el momento las curvas elípticas son muy conocidas, pero no muy utilizadas en la practica.

  La seguridad de los criptosistemas de curvas elípticas ha permanecido estable por años, a pesar de que se han logrado muchos avances significativos en ataques contra instancias especiales. No obstante, esto ha sido conjeturado por los investigadores hace ya varios años y no han surgido grandes sorpresas todavía.

  El algoritmo XTR presentado recientemente por Lenstra and Verheul podría convertirse en un buen competidor para las curvas elípticas. Sin embargo, las curvas elípticas parecen ser levemente mejores en performance y definitivamente trata mejor el tamaño de la llave.

• LUC es un criptosistema de llave pública que utiliza un grupo especial basado en la secuencia de LUCAS (relacionado a las Sucesiones de Fibonacci)como su bloque de construcción básico. Puede implementar todos los algoritmos basados en logaritmos discretos, y en un sentido LUC es una clase de algoritmo de llave pública.

  Los diferentes algoritmos de llave pública basados en la aritmética de LUC son llamados LUCDIF (LUC Diffie-Hellman ), LUCELG (LUC ElGamal), y LUCDSA (LUC Digital Signature Algorithm). Varios de estos estan patentados.

  Sin embargo, actualmente parece haber pocas razones para utilziar los criptosistemas LUC, ya que ofrecen pocos beneficios sobre las curvas elípticas o XTR.

• XTR es un criptosistema de llave pública desarrollada por Arjen Lenstra y Eric Verheul. XTR es similar a LUC ya que utiliza un grupo multiplicativo específico de un campo finito particular (de hecho Fp^6) como su grupo.

  Sin embargo, XTR tiene características de novela tales como necesitar aproximadamente solo 1/3 de los bits para las firmas y mensajes encriptados. Esto es obtenido utilizando una representación específica rastreada de los elementos de ese grupo, y realizando todos los cálculos utilizando esta representación.

  Todos los algorítmos de llave pública basados en logaritmos discretos pueden ser implementados con las ideas del XTR. Así de una manera XTR es un nombre genérico para una clase de algoritmo de llave pública, similar al LUC.

  Tal vez sorprendentemente, el algoritmo es eficiente y de acuerdo a Lenstra and Verheul puede ser un buen substituto de las curvas elípticas, DSS y aún del RSA. Tiene la ventaja sobre las curvas elípticas de que está basado escencialmente en el mismo problema de logaritmo discreto como el DSS, el cual puede ayudar a los criptógrafos y otros a aceptar que es rápido como algoritmos fuerte.

Mochilas

Existen pocos de criptosistemas de Mochila de llave pública interesantes, ninguno de los cuales es de particular importancia.

• El criptosistema Rivest-Chor está basado en una variente particular del problema de mochilas. Este es uno de los criptosistemas de mochilas que tiene mejor resistencia a los ataques.

• Merkle-Hellman: Este fue el primer criptosistema de mochilas. Se basaba en la simple idea de ocultar el fácil y super-incremental problema de mochilas con máscaras. Sin embargo, fue roto en 1980.

Enrejado

En los últimos años el interes se ha dirigido hacia criptosistemas basados en enrejados. Una de las razones es que ciertas clases de problemas de enrejados son duros, y se han propuesto muchos criptosistemas eficientes y parecen ser fuertes.

• NTRU es un sistema critográfico propuesto a mediados de 1990 como un cifrador de llave pública eficiente. Se basa en el problema de enrejado, y tiene algunas características interesantes

  Algunas de las versiones iniciales tenían problemas, pero la versión actual ha sido propuesta para algunos estandares de los Estados Unidos.

volver