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

Logaritmos Discretos: Diffie-Hellman, ElGamal, DSS

Mochilas

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

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.


volver


Extras

Virus-Antivirus

Hosting by