Esto es lo que tenemos en la categoría 'Criptografía'

Jueves 25 de agosto

Apuntes de criptografía V: Elgamal

Retomamos nuestras clases particulares sobre criptografía. En la última entrega hablamos sobre lo que se puede considerar el padre de la criptografía asimétrica, el intercambio de Diffie-Hellman. En esta ocasión vamos hablar sobre el algoritmo de cifrado Elgamal, no tan conocido como RSA, pero sobre él versó mi proyecto de fin de carrera.

En 1985 Taher Elgamal propuso un algoritmo de cifra que hace uso del problema del cálculo de un logaritmo en campo discreto de números. Por ejemplo, Alicia tiene un número primo p y un generador g; Alicia elige un número aleatorio a y calcula A=ga. A, g y p es la clave pública de Alicia, a es su clave privada.

Benito quiere enviarle un mensaje m a Alicia para ello. Benito genera un número aleatorio k el cual es menor que p, luego Benito calcula c1 = gk mod p y c2 = Ak * m mod p y le envía a Alicia c1 y c2.

Alicia para decodificar el mensaje solo tiene que calcular c1-a * c2 mod p y obtendrá m. Esto es debido a que Alicia conoce g, p y i – su clave privada – por lo cual puede calcular c1= gk-a mod p = g-ak mod p = (ga)–k mod p = A-k mod p. Luego c1-a * c2 mod p = A-k * Ak * m = 1 * m = m

Si una persona que no conociera la clave privada – a – y quiera decodificar el mensaje tendría que despegar m de c2. Para ello debe resolver un algoritmo en campo discreto de números, lo que supone un tiempo de ejecución no polinomial.

Si lo que queremos cifrar no es número sino un mensaje deberemos transformar ese mensaje M al número m – podemos usar para ello el código ANSI. Si el texto es demasiado grande tendremos que ir rompiendo M en bloques de tamaño g-1.

Elgamal – como todos los algoritmos de clave pública – requiere mucha computación además por cada trozo de mensaje que codifiquemos deberíamos enviar c1 y c2 , con lo cual estamos duplicando la información original. Lo ideal es usar un sistema de cifrado híbrido.

perpetrado por Alfred-λ @ 25/08/05 11:36
Esto es: Criptografía

Viernes 20 de mayo

Apuntes sobre Criptografía V: Intercambio de claves de Diffie y Hellman

En el capítulo anterior expandimos un poco más nuestro conocimientos sobre los algoritmos de clave pública. Hoy veremos lo que se puede catalogar como el padre de estos algoritmos: el intercambio de claves seguro de Diffie y Hellman. Whitfiled Diffie y Martín Hellman en 1976 desarrollaron un protocolo para realizar el intercambio de claves e intentar así solventar el gran problema de los algoritmos simétricos. Básicamente el protocolo consiste en los siguientes pasos:

  • A y B generan un grupo multiplicativo (con inverso) p – siendo p primo – y un generador g de dicho primo. Estos dos valores son públicos.
  • A genera un número aleatorio a y le envía a B ga mod p.
  • B genera un número aleatorio b y le envía a A gb mod p.
  • B calcula (ga)b mod p = gab mod p, y borra b.
  • A calcula (gb)a mod p = gba mod p, y borra a.
  • La clave secreta que solo comparten A y B es gab mod p.

Si un intruso que conoce g y p y que intercepte ga mod p y gb mod p no podrá descubrir gab mod p porque es incapaz de descubrir el valor de a y b, a menos que resuelva un logaritmo en un campo discreto de números. Resolver este problema tiene un orden exponencial a p, lo que es lo mismo que para resolver este problema se necesitan “2 elevado a p” iteraciones del algoritmo, haced cuentas si p tiene una longitud de 1024 bits. Siendo conocido gab mod p – llamemosle R- g y p, tendría que resolver la siguiente ecuación para encontrar el valor de a: a = log g R mod p, esto es un logaritmo discreto.

Pero el intercambio de diffie-hellman es sensible a un ataque de “hombre en el medio” – “man in middle” es decir:

  • A genera un número aleatorio a y le envía a B ga mod p.
  • C intercepta ga mod p, genera un valor c y envía a B, gc mod p.
  • B genera un número aleatorio b y le envía a A gb mod p.
  • C intercepta gb mod p, genera un valor c y envía a A, gc mod p.
  • B calcula (gb)c mod p = gbc mod p, y borra b.
  • A calcula (ga)c mod p = gac mod p, y borra a.
  • C calcula (gc)b mod p = gcb mod p y (gc)a mod p = gac mod p
  • C a partir de este momento haría de puente entre las conversaciones de A y B, pudiendo hasta modificar los mensajes de ambos y falsear la comunicación.

Por último comentar que es posible ampliar el intercambio a más de dos individuos, ampliando hasta n individuos, al final todos acabarían calculando gabc mod p – en este caso n=3, basta con ir enviando los cálculos en anillo – A envía a B ga mod p, B envía gb mod p a C, etc.

perpetrado por Alfred-λ @ 20/05/05 15:32
Esto es: Criptografía

Lunes 16 de mayo

Resuelto el RSA-200

Un equipo de científicos holandeses y alemanes ha encontrado la solución a la factorización de número primo de 200 dígitos decimales – unos 640 bits. Para tal proeza de la computación – el record anterior estaba en 160 dígitos, unos 570 bits – estos investigadores han tardado un año y medio, lo que traducido a número de operaciones matemáticas es el equivalente de dejar un AMD Opteron 2.2 Mhz trabajando 55 años.

¿Bueno y que significa esto? Pues muy fácil, la factorización de número primero nos permite obtener a partir de una clave pública la clave privada para el algoritmo RSA y ya sabemos que significa eso ¿Verdad?

El algoritmos RSA es muy usado, por ejemplo en transacciones electrónicas, en firma digitales como PGP y en cifrado SSL de los navegadores.

Pero que no entre el pánico, que esto no va a significar una caída de las bolsas del todo el mundo, no es fin de la era de la seguridad electrónica, no habrá tercera guerra mundial – al menos hoy. Un año y medio sigue siendo mucho tiempo para romper una clave y además la longitud que se viene usando es de 1024 bits – que aun esta lejos de ser rota. Así que respiremos tranquilos que el mundo está a salvo.

La empresa que ha sacado el concurso – RSA Security – aun no lo ha confirmado la solución pero solo hay que multiplicar para saber si es correcta. Así que aquí os dejo los numeritos, para que lo comprobéis vosotros mismos – nota: con la calculadora del Windows no lo vais a poder a hacer.

El Número a factorizar
27.997.833.911.221.327.870.829.467.638.722.601.621.070.446.786.955.428.
537.560.009.929.326.128.400.107.609.345.671.052.955.360.856.061.822.351.
910.951.365.788.637.105.954.482.006.576.775.098.580.557.613.579.098.734.
950.144.178.863.178.946.295.187.237.869.
221.823.983
Primer factor
3.532.461.934.402.770.121.272.604.978.198.464.368.671.197.400.197.625.023.
649.303.468.776.121.253.679.423.200.058.547.956.528. 088.349
Segundo factor
7.925.869.954.478.333.033.347.085.841.480.059.687.737.975.857.364.219.960.
734.330.341.455.767.872.818.152.135.381.409.304.740.185.467

Vía Hispasec. Más información en MathWorld.

perpetrado por Alfred-λ @ 16/05/05 09:18
Esto es: Criptografía

Jueves 12 de mayo

Apuntes sobre Criptografía IV: Algoritmos asimétricos

Los algoritmos de clave pública o asimétrico son la base de la criptografía moderna, a este tipo de algoritmos criptográficos le vamos a dedicar una serie de artículos, ya a uno solo se me antoja poco para todo lo que hay que decir sobre ellos. En el primer articulo que escribí ya vimos algunas de las características de los algoritmos asimétricos. Aquí vamos a ampliar esa información inicial antes de ponernos analizar algoritmos con nombre y apellidos.

¿Como funciona un algoritmo de clave pública? ¿En que se basa? Los algoritmos asimétricos están basados en funciones matemáticas y no en operaciones con bits y bytes como los algoritmos simétricos. La idea básica que utilizan son problemas matemáticos que son fácilmente resueltos en un sentido y casi imposible en otros. Como ejemplo no válido de este pensamiento es mucho más fácil calcular el cuadrado de un número que su raíz cuadrada, los algoritmos de clave simétrica utilizan esta idea pero sin usar funciones tan simples como cuadrado y raíces.

El hecho de disponer de dos claves – una pública y otro privada – tiene grandes repercusiones en la confidencialidad, la distribución de claves y autentificación. Básicamente una comunicación utilizando un algoritmos asimétricos sigue los siguientes pasos:

  • B genera una pareja de claves, y da a conocer su clave pública.
  • A codifica el mensaje que quiere mandar a B con la clave pública de B.
  • B recibe el mensaje codificado y lo descifra con su clave privada. Nadie más es capaz de descifrar el mensaje si no dispone de la clave privada de B.
Image hosted by Photobucket.com
Ejemplo de comunicación

Como ventaja ya sabemos que resolvemos el problema de la distribución de las claves y que además son mas versátiles que los algoritmos simétricos, ya que nos ofrecen más servicios que los segundos. Pero por el contrario son más lentos, y basar solo una comunicación el algoritmos asimétrico es muy pesada. Por lo cual se suele utilizar algoritmos híbridos – de los cuales ya hablaremos más adelante.

perpetrado por Alfred-λ @ 12/05/05 12:30
Esto es: Criptografía

Viernes 29 de abril

Apuntes de Criptografía III: Algoritmos Simétricos, Red de Feistel.

Siguiente con nuestros breves apuntes de criptografía, hoy me dispongo a hablaros con un poco más de profundidad de los algoritmos simétricos. Existen dos grandes grupos de algoritmos simétricos, los de codificación por flujo o codificación por rondas. En este artículo nos centraremos en un algoritmo por rondas, ya que son lo más usados.

Un algoritmo de cifrado simétrico utiliza, como ya vimos, la misma clave para cifrar o descifrar. El algoritmo que vamos estudiar básicamente sigue los siguientes pasos:

  • Dado la un mensaje de una longitud N – típicamente 64 bits, 128 bits, etc -, se divide en dos bloques de tamaño N/2, A y B.
  • Se toma una función F, la cual es muy difícil de invertir.
  • Se realizan una serie operaciones con la función F y la clave Ki con solo con una de mitades del mensaje – A o B , cada iteración se permute la mitad. Este proceso es repetido n-veces.

Image hosted by Photobucket.com

Red de Feistel

El inventor de esto fue Horst Feistel. Feistel uso este método para su algoritmo LUCIFER, en 1970. En 1974 se propone a la NSA (Agencia de la Seguridad Nacional), como resultado nació DES. No todos los algoritmos modernos de clave simétrica se basan en Feistel, pero marco el principio. Por ejemplo, AES – actual estándar mundial – no se basa en una red Feistel, sino en una red de sustitución – usando S-Cajas – y permutaciones.

perpetrado por Alfred-λ @ 29/04/05 11:47
Esto es: Criptografía