cripto-2014
CRIPTO-2014
http://www.eldiario.es/turing/criptografia/Breve-historia-criptografia_0_261773822.html Criptografía
de curva elíptica De Wikipedia, la enciclopedia libre
Saltar a: navegación,
búsqueda La Criptografía de Curva Elíptica (del inglés: Elliptic curve
cryptography, ECC) es una variante de la criptografía asimétrica o de clave pública basada en las matemáticas de las curvas elípticas. Sus autores argumentan que la CCE puede ser más rápida y usar claves más cortas que los métodos antiguos — como RSA — al tiempo que proporcionan un nivel de seguridad equivalente. La utilización de curvas elípticas en criptografía fue propuesta de forma independiente por Neal Koblitz y Victor Miller en 1985. Índice
[ocultar]
Introducción[editar]
Los sistemas de criptografía asimétrica o de clave pública utiliza dos claves distintas: una de ellas puede ser
pública, la otra es privada. La posesión de la clave pública no proporciona suficiente información para determinar cuál es la clave privada. Este tipo de sistemas se basa en la dificultad de encontrar la solución a ciertos problemas matemáticos. Uno de estos problemas es el llamado logaritmo discreto. Encontrar el valor de b dada la ecuación , cuando a y c son valores conocidos, puede ser un problema de complejidad exponencial para ciertos grupos finitos de gran tamaño; mientras el problema inverso, la exponenciación discreta puede ser evaluado eficientemente usando por ejemplo exponenciación binaria Una curva elíptica es una curva plana
definida por una ecuación de la forma .
Con el conjunto de puntos G que forman la curva (i.e., todas las
soluciones de la ecuación más un punto O, llamado punto en el infinito) más una operación aditiva +, se forma un grupo abeliano. Si las coordenadas x e y se escogen desde un cuerpo finito, entonces estamos en presencia de un grupo abeliano finito. El problema del logaritmo discreto sobre este conjunto de puntos (PLDCE) se cree que es más difícil de resolver que el correspondiente a los cuerpos finitos (PLD). De esta manera, las longitudes de claves en criptografía de curva elíptica pueden ser más cortas con un nivel de seguridad comparable. Introducción Matemática[editar]
Sea 3" o:spid="_x0000_i1132">
3" src="file:///C:\Users\PC\AppData\Local\Temp\msohtmlclip1\01\clip_image003.png"> primo. La curva elíptica E: sobre es el conjunto de soluciones en la congruencia ,
donde son constantes tal que
Se define una operación aditiva como sigue: Considerando que
y
son puntos en E y es un punto
en el infinito. Si e , entonces ; de lo contrario , donde ,
,
y
.
Finalmente, definimos
.
Con esto se puede mostrar que E es un grupo
abeliano con elemento identidad . Cabe notar que la inversa de (x, y) (que se escribe como -(x, y) ya que la operación es aditiva) es (x, -y), para todo De acuerdo al teorema de Hasse, el número de puntos #E que
contiene E es cercano a p. Más precisamente se satisface la siguiente desigualdad .
Como se sabe que cualquier grupo de orden primo es cíclico, lo que se requiere
es encontrar un subgrupo de E de orden q (q primo) para tener un isomorfismo con donde el problema del logaritmo discreto sea intratable. En este caso, siendo un generador del grupo cíclico (el cual puede ser cualquier elemento del grupo distinto de , la identidad), se pueden calcular las «potencias» de (las que se escriben como múltiplos de , debido a que la operación del grupo es aditiva). Ejemplo[editar]
Sea E la curva elíptica sobre . Se calculan los puntos sobre E verificando los posibles valores
de , y luego verificando si es un residuo cuadrático. Los valores se tabulan en la siguiente Tabla:
Como E tiene 12 puntos + , sigue que
es cíclico e isomorfo a . Considerando el generador , entonces: Entonces tenemos
y
Por lo tanto
Uso en criptografía[editar]
En criptografía, se elige un punto base G específico y publicado
para utilizar con la curva E(q). Se escoge un número entero aleatorio k como clave privada, y entonces el valor P = k*G se da a conocer como clave pública (nótese que la supuesta dificultad del PLDCE implica que k es difícil de deducir a partir de P). Si María y Pedro tienen las claves privadas kA y kB, y las claves públicas PA y PB, entonces María podría calcular kA×PB = (kA×kB)×G; y Pedro puede obtener el mismo valor dado que kB×PA = (kB×kA)×G. Esto permite establecer un valor «secreto» que tanto María como Pedro
pueden calcular fácilmente, pero que es muy complicado de derivar para una tercera persona. Además, Pedro no consigue averiguar nada nuevo sobre kA durante ésta transacción, de forma que la clave de María sigue siendo privada. Los métodos utilizados en la práctica para cifrar mensajes basándose en
este valor secreto consisten en adaptaciones de antiguos criptosistemas de logaritmos discretos originalmente diseñados para ser usados en otros grupos. Entre ellos se podrían incluir Diffie-Hellman, ElGamal y DSA. La realización de las operaciones necesarias para ejecutar este sistema
es más lenta que para un sistema de factorización o de logaritmo discreto módulo entero del mismo tamaño. De todas maneras, los autores de sistemas de CCE creen que el PLDCE es significativamente más complicado que los problemas de factorización o del PLD, y así se puede obtener la misma seguridad mediante longitudes de clave mucho más cortas utilizando CCE, hasta el punto de que puede resultar más rápido que, por ejemplo, RSA. Los resultados publicados hasta la fecha tienden a confirmar esto, aunque algunos expertos se mantienen escépticos. La CCE ha sido ampliamente reconocida como el algoritmo más fuerte para
una determinada longitud de clave, por lo que podría resultar útil sobre enlaces que tengan requisitos muy limitados de ancho de banda. NIST y ANSI X9 han establecido unos requisitos
mínimos de tamaño de clave de 1024 bits para RSA y DSA y de 160 bits para ECC, correspondientes a un bloque simétrico de clave de 80 bits. NIST ha publicado una lista de curvas elípticas recomendadas de 5 tamaños distintos de claves (80, 112, 128, 192, 256). En general, la CCE sobre un grupo binario requiere una clave asimétrica del doble de tamaño que el correspondiente a una clave simétrica. Certicom es la principal empresa
comercial de CCE, esta organización posee 130 patentes, y ha otorgado licencias sobre tecnología a la National Security Agency (NSA) por 25 millones de dólares. Certicom también ha patrocinado varios desafíos al algoritmo CCE. El más complejo resuelto hasta ahora, es una clave de 109 bits, que fue roto por un equipo de investigadores a principios de 2003. El equipo que rompió la clave utilizó un ataque masivo en paralelo basado en el 'birthday attack', mediante más de 10000 PC de tipo Pentium funcionando continuamente durante 540 días. Se estima que la longitud de clave mínima recomendada para CCE (163 bits) requeriría 108 veces los recursos utilizados para resolver el problema con 109 bits. Referencias[editar]
Enlaces externos[editar]
Criptografía
cuántica De Wikipedia, la enciclopedia libre
Saltar a: navegación,
búsqueda La criptografía cuántica es la criptografía
que utiliza principios de la mecánica cuántica para garantizar la absoluta confidencialidad de la información transmitida. Las actuales técnicas de la criptografía cuántica permiten a dos personas crear, de forma segura, una propiedad única de la física cuántica para cifrar y descifrar mensajes. La criptografía cuántica como idea se propuso en 1970, pero no es hasta
1984 que se publica el primer protocolo. Una de las propiedades más importantes de la criptografía cuántica es
que si un tercero intenta hacer eavesdropping durante la creación de la clave secreta, el proceso se altera advirtiéndose al intruso antes de que se transmita información privada. Esto es una consecuencia del principio de incertidumbre de Heisenberg, que nos dice que el proceso de medir en un sistema cuántico perturba dicho sistema. La seguridad de la criptografía cuántica descansa en las bases de la
mecánica cuántica, a diferencia de la criptografía de clave pública tradicional la cual descansa en supuestos de complejidad computacional no demostrada de ciertas funciones matemáticas. La criptografía cuántica está cercana a una fase de producción masiva,
utilizando láseres para emitir información en el elemento constituyente de la luz, el fotón, y conduciendo esta información a través de fibras ópticas. Índice
[ocultar]
Conceptos básicos[editar]
La criptografía es la disciplina que trata de la
transmisión y almacenamiento de datos de manera que no puedan ser comprendidos ni modificados por terceros. Los diferentes métodos de criptografía actualmente utilizados necesitan que dos personas que deseen comunicar información intercambien de forma segura una o más claves; una vez que las claves han sido intercambiadas, los interlocutores pueden transferir información con un nivel de seguridad conocido. Pero esta forma de trabajar basa la seguridad de las transmisiones exclusivamente en el intercambio de claves. La forma más segura de realizar este intercambio de claves es de manera presencial, pero ello no es posible en la mayoría de los casos, dado el múltiple número de interlocutores con los que se desea intercambiar información confidencial (bancos, tiendas en Internet, colegas de trabajo en sedes distantes, etcétera). De manera que el punto donde hay menor seguridad en el intercambio de información confidencial está en el proceso de intercambio y transmisión de las claves. La mecánica cuántica describe la dinámica de cada
partícula cuántica (fotones, electrones, etc.) en términos de estados cuánticos, asignando una probabilidad a cada posible estado de la partícula por medio de una función. Algunos aspectos a considerar de la mecánica cuántica:
Las partículas utilizadas habitualmente en la criptografía cuántica son
los componentes de la luz o fotones, y los estados que se utilizan para ser entrelazados o superpuestos entre sí son sus dos estados de polarización, que es una de las características conocidas de la luz, aunque no sea directamente perceptible. Un fotón puede ser polarizado artificialmente en una dirección en
particular con respecto a su dirección de desplazamiento. Dicha polarización puede ser detectada mediante el uso de filtros, orientados en el mismo sentido en el que la luz fue polarizada. Estos filtros dejan pasar los fotones polarizados en un estado y absorben los polarizados en el otro. Intercambio de claves
cuánticas[editar] Como se dijo anteriormente, las técnicas actuales de la criptografía
cuántica permiten la construcción de una clave secreta compartida que puede ser usada como llave para cifrar y descifrar mensajes. Dos protocolos distintos[editar]
BB84[editar]
Este protocolo se publicó en 1984 por Charles Bennett y Gilles
Brassard y con él se produce el nacimiento de la criptografía cuántica. En este protocolo, la transmisión se logra utilizando fotones
polarizados enviados entre el emisor (tradicionalmente de nombre Alice (en el lado A)) y el receptor (de nombre Bob (en el lado B)) mediante un canal cuántico, por ejemplo, una fibra óptica. Por otro lado, también se necesita la existencia de un canal público (no necesariamente cuántico) entre Alice y Bob, como por ejemplo Internet u ondas de radio, el cual se usa para mandar información requerida para la construcción la clave secreta compartida. Ninguno de los canales necesita ser seguro, es decir, se asume que un intruso (de nombre Eve) puede intervenirlos con el fin de obtener información. Cada fotón representa un bit de información, cero o uno y la información
se logra mediante la codificación de estados no-ortogonales, por ejemplo rectilíneamente (horizontal y vertical) o bien diagonalmente (en ángulos de 45º y 135º), como se muestra en la tabla de abajo. También se puede ocupar una polarización circular (horario o antihoraria). Tanto Alice como Bob, pueden emitir fotones polarizados.
Primer paso: El protocolo comienza cuando Alice decide
enviar una secuencia de fotones polarizados a Bob. Para ello, Alice genera una secuencia aleatoria de bases, por ejemplo, entre rectilíneas (+) y diagonales (x), la cual es almacenada momentáneamente. Una vez hecho esto, Alice usa el canal cuántico para emitir a Bob un fotón polarizado al azar usando las bases que ella generó (un fotón por cada base), registrando la polarización con la que fue emitido. Alice tiene entonces la secuencia de bases utilizadas y la polarización
de los fotones emitidos. La mecánica cuántica dice que no es posible realizar una medición que
distinga entre 4 estados de polarización distintos si es que estos no son ortogonales entre sí, en otras palabras, la única medición posible es entre dos estados ortogonales (base). Es así que por ejemplo, si se mide en una base rectilínea, los únicos resultados posibles son horizontal o vertical. Si el fotón fue creado con una polarización horizontal o vertical (con un generador de estados rectilíneo), entonces esta medición arrojará el resultado correcto. Pero si el fotón fue creado con una polarización de 45º o 135º (generador diagonal), entonces la medición rectilínea arrojara un resultado de horizontal o vertical al azar. Es más, después de esta medición, el fotón quedará polarizado en el estado en el cual fue medido (horizontal o vertical), perdiéndose toda la información inicial de la polarización. Segundo paso: Como Bob no sabe las bases que ocupó Alice
para generar los fotones, no le queda otra opción más que medir la polarización de los fotones usando una base aleatoria generada por él (rectilínea o diagonal). Bob registra las bases que utilizó para medir los fotones y también los
resultados de cada medición. Tercer paso: Alice y Bob se contactan por medio del canal
público para comunicarse las bases que utilizaron para generar y leer respectivamente: Bob envía las bases que él usó y Alice envía las bases que ella usó. Ambos descartan las mediciones (bits) en donde no coincidieron en las
bases (en promedio se descarta la mitad de los bits). Los bits que quedaron fueron generados y medidos con la misma base, por lo que la polarización registrada es la misma para Alice y para Bob. Hasta este paso, en una comunicación ideal, Alice y Bob ya tienen una
clave secreta compartida determinada por los bits que quedaron.
Cuarto paso: Dado que puede existir alguna impureza en el
canal cuántico o, peor aun, un intruso pudo haber interceptado la transmisión de fotones, la polarización de los fotones pudo haber sido alterada por lo que Alice y Bob deben comprobar que efectivamente los bits que no fueron descartados coinciden en su valor. Si un intruso intenta medir los fotones que mandó Alice, al igual que
Bob no sabe con qué base se generaron, por lo que tiene que realizar sus mediciones usando bases al azar lo que inevitablemente introduciría una perturbación en los fotones enviados por Alice si es que no coinciden en la base. Tampoco podría generar los fotones originales de Alice ya que el teorema de no-clonación garantiza que es imposible reproducir (clonar) la información transmitida sin conocer de antemano el estado cuántico que describe la luz. Si un intruso intentó obtener información de los fotones entonces, con
una alta probabilidad, la secuencias de bits de Alice y Bob no coinciden. Con el fin de detectar la presencia del intruso, Alice y Bob revelan segmentos de la clave generada. Si difieren en una cantidad superior a un mínimo determinado, entonces se asume la existencia de un intruso y se aborta la comunicación. Existen técnicas para que la información revelada de la clave sea lo
menor posible (por ejemplo usando funciones de Hash). También existen técnicas para poder reparar la secuencia de bits en caso de que no haya habido un calce total (por ejemplo, en el caso de una interferencia). Quinto paso: Para codificar un mensaje se puede utilizar el
mismo canal cuántico con fotones polarizados, o utilizar el canal público cifrando el mensaje con un algoritmo de cifrado, ya que la clave para el cifrado se ha transmitido de manera absolutamente segura. Fotones Entrelazados E91[editar]
El esquema de criptografía cuántica basada en pares de fotones
entrelazados fue propuesto por Artur Ekert en 1991. El esquema de comunicación es similar al del protocolo BB84. La
diferencia es que se necesita además una fuente que produzca una serie de pares de fotones entrelazados. Dicha fuente puede estar en manos de Alice, Bob o algún tercero, lo importante es que de cada par de fotones entrelazados producido, un fotón llegue a Alice y el otro a Bob. Si Alice y Bob miden para ver qué tipo de polarización rectilínea tienen sus respectivos fotones (ambos miden en la misma base), obtendrán siempre respuestas opuestas (anticorrelación). Previo a la medición es imposible predecir que estado obtendrá cada
fotón, por lo que Alice y Bob miden independientemente con una base aleatoria. Si ambas bases no coinciden, entonces la anticorrelación se pierde y el resultado de la medición no servirá. Debido a esto y análogamente al protocolo BB84, Alice y Bob se intercambian las bases que utilizaron para medir sus respectivos fotones, para saber qué bits son los que corresponden a la clave generada. Si un intruso intentase medir de alguna forma alguno de los fotones
entrelazados, no podrá saber de antemano las bases de Alice y Bob por lo que no tiene otra opción más que medir con una base aleatoria, esto provocará que su intento de medición alterará el resultado de Alice y Bob. Al igual que en el protocolo BB84, también se necesita verificar parte
de la clave secreta con el fin de saber si alguien estuvo interceptando la comunicación y de reparar la clave en caso de interferencia o errores de transmisión. La ventaja de este protocolo, es que la clave se genera
"naturalmente al azar" ya que es imposible saber de antemano qué polarización tendrá cada fotón. Implementación de la
criptografía cuántica[editar] Basado en estos principios, se definen protocolos de comunicación que
utilizan la polarización de los fotones para codificar información binaria que conformará la clave secreta. Estos protocolos incluyen mecanismos de corrección en caso de errores de transmisión. Los primeros productos comerciales de criptografía cuántica salieron al
mercado en 2002. Desde entonces los avances no dejan de producirse y la adopción de esta tecnología, si bien lenta al principio, tiende a acelerarse. Bibliografía[editar]
Complejidad
y criptografía De Wikipedia, la enciclopedia libre
Saltar a: navegación,
búsqueda La criptografía es la ciencia encargada del estudio y
diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la información original escondida en un conjunto de datos cifrado. Los avances en computación de la segunda mitad del siglo XX pusieron en
riesgo la integridad de los sistemas usados hasta entonces, a la vez que proporcionaban medios para la creación de otros nuevos y más seguros. Es en este punto donde la teoría de la complejidad, encargada de estudiar los recursos necesarios para el cómputo de los algoritmos, cobra importancia dentro de la criptografía. Esto es debido a que los nuevos algoritmos criptográficos basarán su seguridad en la dificultad de ejecutar las operaciones necesarias para obtener la información original de un criptograma, siendo la ya mencionada teoría de la complejidad quien determinará cuál es esta dificultad. Un algoritmo tiene utilidad si es fácilmente resoluble, esto es,
pertenece a la clase P (Talbot, 2006:15). Sin embargo, desde un punto de vista criptográfico, no poder hallar una solución a un problema de una forma práctica en términos computacionales (es decir, no pertenecer a la clase P) se traduce en seguridad (Rothe, 2005:2). A pesar de haberse desarrollado por separado, en la actualidad ambos
campos están fuertemente ligados: La criptografía depende de los resultados proporcionados por la teoría de la complejidad, a la vez que las investigaciones en ésta última son en muchas ocasiones promovidas por problemas desarrollados en un marco criptográfico (Rothe, 2005:1). Índice
[ocultar]
Problemas matemáticos útiles
en criptografía[editar] En la actualidad, la criptografía está considerada una rama tanto de la
informática como de las matemáticas. Existe una serie de problemas matemáticos comúnmente utilizados en los sistemas criptográficos. Tests de primalidad[editar]
Los números primos han sido la base de varios criptosistemas de clave pública, entre
ellos RSA o el criptosistema de Rabin. Su utilidad reside en la facilidad de multiplicar dos números primos grandes para obtener un número compuesto y en la dificultad de hallar la descomposición en factores primos dado un número obtenido de la multiplicación de dos primos grandes. Sin embargo, no es trivial comprobar que uno de estos números sea realmente primo. Este problema ha sido investigado a conciencia y se han descubierto algunos tests de primalidad que reducen su complejidad. Test de Fermat[editar]
El test de Fermat se fundamenta en el pequeño teorema de Fermat, que demuestra
que, si n es primo, para cualquier número natural a coprimo con n se cumple que Se trata de un test probabilístico que, para determinar si un número n
es primo, realiza la prueba anterior para diferentes valores de a. Cuantos más valores se prueben, mayor probabilidad de que n sea realmente primo. La fiabilidad de este test reside en el hecho de que si un número es compuesto, entonces es muy probable obtener un valor de a tal que Para un número k de pruebas y un tamaño de entrada m, la
complejidad del algoritmo es . No obstante, este test apenas se utiliza, debido entre otras cosas a los números de Carmichael, que siempre satisfacen la igualdad del pequeño teorema de Fermat pero no son primos. Solovay-Strassen[editar]
Se trata de un test probabilístico basado en el criterio
de Euler, del cual se obtiene que para un número n primo se cumple que siempre que a y n sean coprimos. Su
coste computacional para una entrada de tamaño m es , donde k es el número de valores diferentes de a con los que se prueba. En caso de devolver como resultado “primo”, la probabilidad de que n no lo sea es menor que (1/2)k. Sin embargo, el uso de este test ha caído ante el de Miller-Rabin, ya que éste último es más eficiente en la práctica y al menos tan fiable como el de Solovay-Strassen (Rothe, 2005:329) (Menezes, 1997:137). Miller-Rabin[editar]
El test de primalidad de Miller-Rabin
es el más usado en la actualidad. Al igual que los anteriores, se trata de un test probabilístico. Está basado en el siguiente hecho: Sean n un número primo y a un número coprimo con n. Para cualquier n existe un r impar tal que n - 1 = 2sr. Entonces, o bien o bien existe algún j tal que para el que se cumple que
El coste computacional de este algoritmo, al igual que ocurría con
Solovay-Strassen, es de para una entrada de tamaño m. Sin embargo, Miller-Rabin no sólo es más rápido en la práctica, sino que es más fácil de implementar (no incluye al símbolo de Jacobi en sus operaciones) y ofrece una cota de error de (1/4)k frente a (1/2)k para k pruebas distintas (Menezes, 1997:141). AKS[editar]
Diseñado en 2002 por Manindra Agrawal, Neeraj Kayal y Nitin Saxena, AKS es el primer algoritmo determinista
de primalidad. Sirvió además para demostrar que éste problema pertenece a la clase de complejidad P y, por tanto, es computacionalmente practicable. Sin embargo, su orden de complejidad es , por lo que, para propósitos generales, se sigue recomendando Miller-Rabin (Talbot, 2006:75). Factorización de enteros[editar]
La dificultad de descomponer números enteros en sus factores
primos ha sido la base de diversos criptosistemas, entre ellos RSA. Aún no se conocen algoritmos eficientes para resolver este problema, por lo que la seguridad de aquellos sistemas basados en esto está garantizada en este aspecto. Sí existen, sin embargo, algoritmos para factorizar números con determinadas características, por lo que conviene tomar ciertas precauciones a la hora de elegir los números que serán la base de un criptosistema. División por tentativa[editar]
Dado un número n obtenido a partir de la multiplicación de dos
números primos, probar con todos los números impares menores que hasta encontrar el primero que lo divida. Es fácil demostrar que, en el peor caso, habría que hacer divisiones (si no se comprueba que cada divisor sea verdaderamente primo). Por tanto, este algoritmo requiere operaciones para una entrada de tamaño m. Algoritmo p - 1 de
Pollard[editar] El algoritmo p - 1 de
Pollard es efectivo para números n obtenidos del producto de p y q primos tales que los factores primos de p – 1 son pequeños. El tiempo de cómputo de este algoritmo es para una entrada de tamaño m, donde B es el límite superior de los números pequeños. Dado que requiere tiempo polinómico, es de suma importancia evitar este tipo de números en criptosistemas basados en el producto de números primos, como RSA, ya que éstos podrían ser factorizados de forma rápida, poniendo en peligro su seguridad. Criba general de campo de
números[editar] Actualmente es el algoritmo de factorización más rápido conocido. Su
complejidad, dado un número de tamaño m, es , siendo c una constante que depende de la variante del algoritmo. Algoritmo de Shor para
factorización de enteros[editar] Se trata de un algoritmo cuántico capaz de descomponer un
número n en tiempo . Dado que se trata de un algoritmo teórico, los criptosistemas basados en la factorización de enteros no corren peligro. Sin embargo, si llegase a implementarse en un computador cuántico, estos criptosistemas pasarían a ser inseguros, entre ellos RSA.1 Problema del logaritmo
discreto[editar] Al igual que ocurría con los números primos, el problema del logaritmo discreto ha sido la base de diversos
sistemas criptográficos, entre ellos el criptosistema de ElGamal o el protocolo de intercambio de claves de Diffie-Hellman. Consiste en lo siguiente: Sea p un número primo, un generador de y un elemento , encontrar un x tal que o lo que es lo mismo:
Este problema también ha sido estudiado en profundidad, aunque ni se ha
descubierto aún ningún algoritmo eficiente ni se ha logrado determinar su complejidad (Rothe, 2005:369). Búsqueda exhaustiva[editar]
Es el algoritmo de fuerza bruta para el problema del logaritmo discreto.
Siendo p, y conocidos, se puede optar por probar todos los posibles valores de x menores que p. No obstante, esto requeriría del orden de p operaciones. Por tanto, para una entrada de tamaño m, este algoritmo tiene una complejidad temporal de . Algoritmo paso-gigante
paso-enano[editar] Se trata de un algoritmo cuya complejidad temporal y espacial es . Pese a mejorar al anterior algoritmo, éste sigue siendo poco eficiente
y, en consecuencia, desaconsejado (Rothe, 2005: 368). Algoritmo rho de Pollard para
logaritmos discretos[editar] Este algoritmo, cuya complejidad temporal para una entrada de m
bits es , tiene una complejidad espacial despreciable, siendo entonces más eficiente que el algoritmo paso-gigante paso-enano y por tanto preferible (Menezes, 1997:106). Algoritmo de Shor para
logaritmos discretos[editar] El mismo algoritmo cuántico usado para la factorización de enteros
también puede ser aplicado al problema del logaritmo discreto.1 Criptosistemas de clave
pública[editar] Los criptosistemas de clave pública son
aquellos que utilizan claves distintas para cifrar y descifrar, siendo una de estas claves accesible por todos los usuarios (pública) y la otra conocida solo por su propietario (privada). Suelen estar fundamentados en el uso de funciones trampa, esto es, funciones fáciles de computar si se conoce cierta información, pero difíciles si se desconoce. Una característica fundamental es que no se pueda deducir la clave privada a partir de la clave pública. La mayoría de estos sistemas están basados en los problemas de la factorización de enteros y el logaritmo discreto. También hubo diseños basados en el problema de la mochila, pero algunos fueron criptoanalizados con éxito, por lo que este enfoque ya no se utiliza. RSA[editar]
Presentado en 1977 por Ron Rivest, Adi Shamir
y Leonard Adleman, se trata del criptosistema de clave pública más usado hasta la fecha (Menezes, 1997:285). Por esta razón, ha sido objeto de estudios minuciosos que, aunque no han logrado criptoanalizarlo, han detectado debilidades cuando se usan determinadas claves. Está basado en el problema de la factorización de enteros. Su proceso de
generación de claves es el siguiente:
Para cifrar un texto m, éste se parte en trozos m1,
... , mk tales que mi representa un entero en el rango [0, n-1]. A continuación, para cada uno de los mi se computa .
Para descifrar el criptograma, para cada ci se computa
.
Un ataque para hallar la clave privada d podría ser intentar
factorizar n y hallar e siguiendo un proceso similar al de generación de claves. Esto demuestra que romper RSA tiene a lo sumo la misma complejidad que la factorización de enteros. Riesgos en la generación de
claves de RSA[editar]
Criptosistema de
Merkle-Hellman[editar] Diseñado por Ralph Merkle y Martin
Hellman en 1978, este criptosistema se basaba en el problema de la mochila, el cual se sabe que pertenece a la clase NP. Como clave privada se usa una sucesión supercreciente de n elementos y como clave pública una sucesión obtenida a partir de la multiplicación modular de la primera, que no resultará supercreciente. Para cifrar un mensaje M de n bits, se suman los valores i-ésimos de la clave pública tales que para el bit i-ésimo del mensaje se cumple mi = 1, obteniendo un criptograma C. Para descifrar el mensaje, se usa un algoritmo voraz que halla los valores i de la sucesión supercreciente que suman C. Los procesos de cifrado y descifrado son considerablemente más rápidos que los de RSA (Talbot, 2006:162). La seguridad del criptosistema de Merkle-Hellman se
basaba en que, dado un criptograma C y una clave pública Kpu, hallar los valores de Kpu tales que suman C se reduce a resolver el problema de la mochila, el cual es computacionalmente intratable. Sin embargo, en 1984 Adi Shamir diseñó un algoritmo que, para la mayoría de los casos, permitía obtener la clave privada partiendo de la clave pública en tiempo polinómico, y con ello descifrar los criptogramas (Menezes, 1997:302). Sin embargo, debe hacerse notar que este algoritmo NO resuelve el problema de la mochila, tan solo halla la clave privada del criptosistema. En consecuencia, no aporta nueva información sobre el problema P=NP (Talbot, 2006:162). Criptosistema de McEliece[editar]
Diseñado en 1978 por Robert McEliece, el criptosistema de McEliece
se fundamenta en otro problema de la clase NP, la corrección de códigos lineales. En concreto, se usan códigos de Goppa, ya que para éstos se conocen algoritmos de corrección eficientes. La idea principal es ocultar el mensaje introduciendo errores de un modo que el receptor sepa corregirlos. La clave privada consiste en una matriz G correctora de hasta un número t de errores, una matriz binaria invertible S y una matriz de permutaciones P. La clave pública consiste en el producto SGP de las tres matrices anteriores y el parámetro t. A pesar de tratarse de un criptosistema cuyos procesos de cifrado y
descifrado son relativamente rápidos, apenas recibe uso. Esto es debido principalmente a sus tamaños de clave (219 bits = 64 Mbytes para la clave pública) y a su factor de expansión del mensaje (para los parámetros recomendados por McEliece, el criptograma tiene un tamaño un 60% mayor que el mensaje en claro) (Menezes, 1997:299). Sin embargo, dado que el algoritmo de Shor no afecta a este criptosistema, parece fiable frente a la computación cuántica. Criptografía de curva
elíptica[editar] Propuesta de forma independiente por Neal Koblitz y Victor Miller en 1985, la criptografía de curva elíptica se
basa en las matemáticas de curvas elípticas. Su fortaleza reside en el problema del logaritmo discreto, el cual se cree que para el caso de los conjuntos de puntos usados en estos criptosistemas es aún más difícil de resolver que en el caso de los campos finitos del problema original. Esto permite que la criptografía de curva elíptica garantice la misma seguridad que otros criptosistemas asimétricos con una longitud de clave mucho más corta (RSA-1024 ECC-160, RSA-3072 ECC-256, RSA-15360 ECC-5122 ). No obstante, existen algunas curvas específicas para las que se conocen algoritmos que resuelven el logaritmo discreto en tiempo polinómico. Éstas deben evitarse. Por ello, el NIST ha elaborado una lista de curvas recomendadas.3 Referencias[editar]
Notas[editar]
1. ↑ Saltar
a: a b «[quant-ph/9508027] Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer». <img
src="//es.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;" /> |
