elparaiso.mat.uned.es

¡Pulsa Aquí!

LO DIJO...

Marcus Jacobson  
 
La ciencia puede descubrir lo que es cierto, pero no lo que es bueno, justo y humano.
 
El Paraíso de las Matemáticas - Criptotaller ~ Cifrado exponencial (I)
.: Criptotaller :.
Cifrado exponencial (I)

    Ley de Hofstadter: Siempre lleva más tiempo del que se preveía aun cuando se toma en cuenta la Ley de Hofstadter

    Discutiremos ahora sobre un sistema basado en la exponenciación modular, debido a Pohlig y Hellman (1978). Veremos que el método es resistente al criptoanálisis.

    Sea p un número primo impar, y sea e la clave, un entero que verifique (e, p-1)=1, en otras palabras que e y p-1 no tienen divisores comunes.

    Para cifrar un mensaje procederemos como de costumbre, convirtiendo las letras A...Z en sus equivalentes numéricos 0...25.

    A continuación agrupamos los números resultantes en bloques de 2m dígitos decimales, donde 2m es el mayor entero positivo tal que todos los bloques correspondientes a m letras sean menores que p. A ver si consigo explicarme, supongamos que p=9973, entonces m=2 ya que 2525<9973 y 2525 es el mayor entero que puede conseguirse con dos letras.

    Una vez establecido m, encriptamos usando la relación C = P^e (mod p). De este modo el texto cifrado consistirá en una serie de enteros menores que p correspondientes a cada uno de los bloques iniciales. Como en otros métodos, suele ser necesario añadir caracteres sin sentido al final del texto inicial para que el número de ellos sea divisible por m.

    Vamos a desarrollar un ejemplo donde usaremos p=2633 y como clave e=29, que nos sirve pues (29, 2632)=1. Cifremos entonces la palabra VIRTUAL. Empezamos con los equivalentes numéricos: 2108 1719 2000 1123, observad que hemos añadido 23 (X) para hacer par el número de letras (vamos a tomar m=2). Ahora ciframos bloque a bloque mediante la transformación C = P^29 (mod 2633) empezando por 2108. El número 2108^29 es aprox. 2.5x10^96 y sería muy poco apropiado calcular este enorme número para luego reducirlo módulo 2633.

    Existe un algoritmo para hacerlo eficientemente que no incluiré aquí para no recargar en exceso el artículo. Si alguien interesado me escribe puedo enviárselo (junto con el código en C si le interesa); si recibo varias peticiones lo publicaremos en esta sección.

    Bien, 2108^29 = 631 (mod 2633) y haciendo lo mismo con los otros bloques (1719 2000 1123) obtenemos 871 1948 1133 que sería el resto de la palabra ya cifrada.

    Ahora a la inversa, para descifrar un texto C necesitamos una clave d tal que de = 1 (mod p-1). Con este d tendremos que C^d = P como se puede comprobar con un poco de álgebra y aplicando el pequeño teorema de Fermat.

    Siguiendo con nuestro ejemplo necesitamos un inverso de 29 módulo 2632 que resulta ser d=2269. Se puede comprobar por ejemplo que 631^2269 = 2108 (mod 2633) lo que nos da el bloque VI inicial.

    Sin entrar de momento en notaciones, diremos que el cifrado y descifrado puede hacerse "rápidamente" y que esta velocidad depende en esencia del tamaño del primo p.

    Como siempre, cuanto más nos cuesta cifrar más difícil tambien es romper el código. Pongámonos en el papel del criptoanalista y supongamos que conocemos el primo p usado como módulo y para darnos más facilidades que conocemos una parte del texto inicial P que corresponde con otra C del cifrado. Entonces necesitamos encontrar un número e tal que C = P^e (mod p).

    Se dice en este caso que e es un logaritmo de C en base P módulo p. Hay varios algoritmos para calcularlo el más rápido de los cuales requiere exp(Raiz(ln p.ln(ln p))) operaciones de nivel bit. Resulta que esto coincide con el número de operaciones necesarias para factorizar un entero que como veremos al hablar de RSA es un proceso muy costoso.

    En concreto factorizar un entero de 100 dígitos podría llevar decenas de años. Esta estimación está basada en suponer una operación de nivel bit cada 10^-6 segundos. Por cierto, aquí me gustaría pedir información en dos campos: primero a los fans del ensamblador, que seguro que me saben decir el tiempo que necesita una operación de bit en, digamos un Pentium IV a 3 GHz for example. Y dos, seguro que alguno tiene por ahí algo más reciente sobre métodos de factorización y sus tiempos de ejecución.

    Terminamos, dejando para el siguiente apartado algún comentario más sobre este método incluyendo la manera de jugar al poker a distancia, sin que ninguno de los jugadores pueda hacer trampa!

Area On-Line
  Todo tipo de material, para disfrutar de él completamente On-Line, sin necesidad de descargar archivos ni tener que andar descomprimiendo estos. No te olvides de pasar por el Diccionario, y las secciones Origami y Geointeractiva. Son de lo más interesante.

Criptotaller

Criptografía (clásica y moderna), criptoanálisis (primos, primos de Mersenne, etc.) y otras técnicas.

Material para descargar

Código Fuente C

Método Hill
Método Jefferson
Exponenciación Modular
Cálculo números primos
Test de Lucas-Lehmer
Factores num. Mersenne
Verificación FIPS 140.2
Teorema chino del resto
+ Códigos Fuente C

Código Fuente Python

Generación de claves

Artículos

La máquina Enigma
Criptografía y seguridad
    M. J. Lucena
Seguridad Informática
   y Criptografía PDF PPT
    J. Ramió
Criptografía clásica PDF
    J. Ramió

Programas
Cripto1 ZIP 2391 KB
    J. L. Rubio

Enlaces

Página personal de Jaime Suárez Martínez, colaborador de esta sección.

Munitions, colección de programas para Linux.

Kriptopolis, toda una referencia en castellano.

Ciphersaber

Criptonomicón: la página de Gonzalo Alvarez Marañón.

Página de Chris Caldwell, una página bien elaborada sobre números primos.

Colección de links de Peter Gutmann.

www.gnupg.org es la página original de GPG, un programa libre alternativo a PGP.

Lunes, 22 / 07 / 2019
   BUSCADOR
 

   TU CORREO
Usuario
Contraseña

   MATRACAS
Lista de correo gratuita
.: Chismes de Adán y Eva :.
Adios a Elisenda Fo...
WolframAlpha: El mo...
WIRIS para Mac...
Third CEU Summersch...
¡Más y más actualiz...
Cerca de 500 MB de ...
Ha llegado el momen...
WIRIS, matemáticas ...
El Universo Matemát...
Segundas Jornadas d...
Los Elementos de Eu...
VI Semana de la Cie...
Tras varios meses d...
¡Chiflados por los ...
Otro verano más, to...

 

Todos los derechos reservados. El Paraíso de las Matemáticas 2015Información Legal Política de PrivacidadAyudaEmail