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!