Informatica

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

...