Hace unos meses publiqué un vídeo donde comentaba algunos conceptos básicos de la criptografía moderna. La idea era hacer un recorrido histórico, desde el cifrado César a los potentes sistemas criptográficos de la actualidad, pasando por el famoso cifrado indescifrable de Vigenère. Un cifrado que, irónicamente, se podía descifrar en menos de un segundo con la técnica y la tecnología adecuadas. En este artículo comparto los códigos que utilicé en la creación del vídeo.

No quiero repetir aquí todas las ideas que introduje en el vídeo: solo quiero compartir los códigos. Estos códigos destacan por su valor pedagógico, ya que tienen algunas simplificaciones para destacar los conceptos clave sin perdernos en detalles técnicos. De hecho, casi todo el análisis estadístico que empleo se reduce a ver cuál es la letra más común de un texto.

El cifrado César

Una de las formas más sencillas de cifrar un mensaje es el cifrado César. Para verlo de forma intuitiva, podemos imaginar que un texto está formado por cilindros donde aparecen todas las letras del alfabeto en orden. Escribir un mensaje consiste en colocar los cilindros en una posición determinada, donde sea visible el texto que queremos cifrar. Para cifrarlo solo tienes que elegir una clave secreta (un número secreto) y mover todos los cilindros tantas posiciones como indique el número secreto.

Por simplicidad, en los códigos de este artículo trabajaremos siempre con un alfabeto de 25 letras, que está guardado en la lista albe. Solo se cifrarán o descifrarán las letras que estén en este alfabeto: el resto de símbolos no se modifican.

Entremos en materia. ¿Cómo se traducen los cilindros a una función matemática? Para cambiar una letra x por la letra que está n posiciones más adelante en el alfabeto, utilizamos una suma modular. Este proceso se denomina encriptación y se describe matemáticamente por la función E(i). La letra que ocupa la posición i en el alfabeto se sustituirá por la que ocupa la posición i+n ~\text{mod }25. Si no conoces la notación modular, el \text{mod } 25 indica que si i+n se pasa de 25, vuelves a contar por el principio del alfabeto, de forma circular. En resumen,

E(i)=i+n ~~~~\text{mod }25

Para devolver una letra encriptada x a su posición original, tenemos que cambiarla por la letra que está n posiciones atrás en el alfabeto. Este proceso se denomina desencriptación y se describe matemáticamente por la función D(i).

D(i)=i-n ~~~~\text{mod }25

albe = ['a','b','c','d','e','f','g','h','i','j','l','m','n',
        'ñ','o','p','q','r','s','t','u','v','x','y','z']


def desplazar_letra(letra, desplazamiento):
    # Cambia una letra del abecedario por la letra
    # que está x posiciones a su derecha.
    if letra not in albe:
        return letra
    i = albe.index(letra)
    return albe[(i + desplazamiento) % 25]


def en_letra(letra_real, desplazamiento):
    # Encripta una letra con el cifrado César.
    return desplazar_letra(letra_real, desplazamiento)


def desen_letra(letra_cod, desplazamiento):
    # Desencripta una letra con el cifrado César.
    return desplazar_letra(letra_cod, -desplazamiento)

El cifrado indescifrable

Antes de continuar, déjame introducir otro tipo de cifrado que utilizaremos más adelante. Es una versión del cifrado de Vignère, el famoso cifrado indescifrable. En lugar de utilizar un número secreto para cifrar todo un mensaje, usaremos varios números de forma cíclica. Por ejemplo, si usamos una clave de tres números, como [3, 14, 16], escribimos la clave sobre los cilindros del mensaje:

Después, movemos cada cilindro tantas posiciones como indica el número de la clave: la B se mueve tres posiciones, la U se mueve catorce, etc. Es como un cifrado César donde cambias la clave en cada letra, de forma periódica.

Para cifrar un texto, primero lo limpiaremos con la función normalizar. Esta elimina los espacios del texto, cambia mayúsculas por minúsculas y borra todas las tildes que encuentra. Mantiene las comas, puntos y otros símbolos. Es una decisión personal, porque los espacios dan mucha información para descifrar un texto sin conocer la clave secreta, y por eso he decidido eliminarlos. Las comas y los puntos no aportan tanto, por eso he decidido mantenerlos. Esta función prepara el texto para cifrarlo.

Las funciones para encriptar o desencriptar un texto no tienen mucho misterio: recorren el texto y cambian cada una de las letras. Solo cambian las letras que detecta en el alfabeto albe, el resto de símbolos los deja como estaba. Estas funciones necesitan un texto y una clave. La clave debe introducirse en forma de lista. Si la lista solo tiene un elemento (como clave=[2]), el cifrado será como un cifrado César: todas las letras se desplazan las mismas posiciones. Si la lista tiene varios elementos (como clave=[3,14,16]), el cifrado será como un cifrado Vignère.

import unicodedata

def normalizar(texto):
    # Quita los espacios, tildes y convierte
    # mayúsculas en minúsculas. Mantiene las eñes,
    # un guiño entrañable a la seña del español.
    
    texto = texto.lower().replace(' ', '')
    texto = texto.replace('Ñ', 'ñ')
    texto = texto.replace('ñ', '<TEMP_N>')  # Marcador temporal para 'ñ'
    texto = ''.join(c for c in unicodedata.normalize('NFD', texto)
                    if unicodedata.category(c) != 'Mn')
    texto = texto.replace('<TEMP_N>', 'ñ') # Restauramos las 'ñ'
    return texto


def encriptar(texto, clave):
    # Toma un texto y lo cifra con una clave.
    resultado = ''
    longitud_clave = len(clave)
    for i in range(len(texto)):
        letra = texto[i]
        desplazamiento = clave[i % longitud_clave]
        resultado += en_letra(letra, desplazamiento)
    return resultado


def desencriptar(texto, clave):
    # Toma un texto y lo descifra con una clave.
    resultado = ''
    longitud_clave = len(clave)
    for i in range(len(texto)):
        letra = texto[i]
        desplazamiento = clave[i % longitud_clave]
        resultado += desen_letra(letra, desplazamiento)
    return resultado

Por poner un ejemplo, para cifrar un texto con la clave [1,2,3,4,5] haríamos lo siguiente:

texto = (
    "Muchos años después, frente al pelotón de fusilamiento, el coronel \n"
    "Aureliano Buendía había de recordar aquella tarde remota en que su \n"
    "padre lo llevó a conocer el hielo. Macondo era entonces una aldea \n"
    "de veinte casas de barro y cañabrava construidas a la orilla de un \n"
    "río de aguas diáfanas que se precipitaban por un lecho de piedras \n"
    "pulidas, blancas y enormes como huevos prehistóricos. El mundo \n"
    "era tan reciente, que muchas cosas carecían de nombre, y para \n"
    "mencionarlas había que señalarlas con el dedo. Todos los años, por \n"
    "el mes de marzo, una familia de gitanos desarrapados plantaba su \n"
    "carpa cerca de la aldea, y con un grande alboroto de pitos y timbales\n"
    "daban a conocer los nuevos inventos. Primero llevaron el imán.\n"
    "Un gitano corpulento, de barba montaraz y manos de gorrión, que se \n"
    "presentó con el nombre de Melquíades, hizo una truculenta demostración\n"
    "pública de lo que él mismo llamaba la octava maravilla de los sabios \n"
    "alquimistas de Macedonia. Fue de casa en casa arrastrando dos lingotes \n"
    "metálicos, y todo el mundo se espantó al ver que los calderos, las \n"
    "pailas, las tenazas y los anafes se caían de su sitio, y las maderas \n"
    "crujían por la desesperación de los clavos y los tornillos tratando\n"
    "de desenclavarse, y aun los objetos perdidos desde hacía mucho tiempo \n"
    "aparecían por donde más se les había buscado, y se arrastraban en \n"
    "desbandada turbulenta detrás de los fierros mágicos de Melquíades.\n"
    "«Las cosas tienen vida propia —pregonaba el gitano con áspero acento—,\n"
    "todo es cuestión de despertarles el ánima.»"
)


texto = encriptar(normalizar(texto), [1,2,3,4,5])
print(texto)

Este código debería devolvernos el texto cifrado según la técnica de Vignère, sin espacios y sin mayúsculas. Si quisiéramos descifrarlo, deberíamos usar la función desencriptar(texto, [1,2,3,4,5]), que nos devuelve el texto original. Si usamos una clave distinta a [1,2,3,4,5], el mensaje desencriptado no encajará con el mensaje original. Ahora bien: ¿es posible recuperar el mensaje original si no conocemos la clave?

La respuesta es que sí, con un poco de estadística. Eso sí: a veces un texto como el de antes es muy corto para hacer un análisis estadístico sobre él. Puede ser útil emplear las siguientes funciones para trabajar con el texto que está en un archivo externo. Así podemos introducir un libro entero en el código de forma cómoda.

def cifrar_archivo(archivo, clave):
    # Cifra todo el texto de un archivo .txt y 
    # guarda el resultado en otro archivo de texto.
    # archivo = nombre del archivo
    # clave = clave para cifrar
    
    with open(archivo + ".txt", "r", encoding="utf-8") as f:
        texto = normalizar(f.read())
    codificado = encriptar(texto, clave)
    
    with open(archivo + "_cod.txt", "w", encoding="utf-8") as f2:
        f2.write(codificado)


def descifrar_archivo(archivo, clave):
    # Descifra todo el texto de un archivo .txt y 
    # guarda el resultado en otro archivo de texto.
    # archivo = nombre del archivo
    # clave = clave para descifrar
    
    with open(archivo + "_cod.txt", "r", encoding="utf-8") as f:
        texto = f.read()
    descodificado = desencriptar(texto, clave)
    
    with open(archivo + "_descod.txt", "w", encoding="utf-8") as f2:
        f2.write(descodificado)

Cómo descifrar el cifrado César

Como ya explicamos en el vídeo, el cifrado César tiene una debilidad que pueden aprovechar los espías. El idioma español deja una huella muy particular en los texto escritos: no todas las letras aparecen con la misma frecuencia. La letra e y la a son los caracteres más frecuentes en un mensaje común. Y esta huella no desaparece con el cifrado César.

En el cifrado César, todas las letras se desplazan el mismo número de posiciones, según lo indique la clave secreta. Eso quiere decir que todas las letras e se transforman en la misma letra cifrada. Por tanto, si tomamos un texto cifrado y contamos cuántas veces aparece cada letra, es probable que la letra más frecuente sea la e encriptada. A partir de ahí sabremos cuántas posiciones se han movido los cilindros y averiguaremos la clave secreta.

Con esta idea diseñé la siguiente función, que recibe un texto cifrado al estilo César y devuelve cuál es la clave secreta más probable. En la primera versión, mi función se limitaba a decir que la letra más común del texto es la e y, con esa información, encontraba la clave. Por desgracia, hay textos donde la letra más común es la a, y tuve que modificarla para tener en cuenta esas pequeñas anomalías estadísticas.

¿Cómo sabe mi función si la letra más común es la a o la e? La función calcula cuáles son las tres letras más comunes del texto y asume que la letra a y la e están en este grupo de letras. Como la letra e está cuatro posiciones a la derecha de la letra a en el alfabeto, esta distancia de cuatro posiciones también se mantiene en el texto cifrado. Es decir, si encuentras que dos de las letras más comunes del texto son la B y la F (la F está cuatro posiciones a la derecha de la B en el alfabeto), es muy probable que estas letras correspondan a la A y a la E, respectivamente. Con esta idea, los textos cortos se descifran mejor. No hace maravillas, pero se descifran mejor.

import time
from collections import defaultdict

def encontrar_clave_cesar(texto):
    # Recibe un texto cifrado y busca cuál es la clave
    # secreta más probable. Lo hace calculando la
    # frecuencia de las letras. 
    
    # Frecuencias de las letras
    letras = defaultdict(int)
    for l in texto:
        if l in albe:
            letras[l] += 1

    # Elegir las tres más frecuentes
    letras_ordenadas = sorted(letras.items(), key=lambda x: x[1], reverse=True)
    top_letras = [item[0] for item in letras_ordenadas[:3]]

    # Buscar un par con diferencia de 4 (e está 4 posiciones delante de a)
    posiciones = [albe.index(l) for l in top_letras]
    pose = None

    for i in range(3):
        for j in range(i+1, 3):
            d = (posiciones[j] - posiciones[i]) % 25
            if d == 4:
                pose = posiciones[j]
                break
            elif d == 21:  # 25 - 4
                pose = posiciones[i]
                break
        if pose is not None:
            break

    # Si no enceuntra un par válido, dice que la más frecuente es la e
    if pose is None:
        pose = posiciones[0]

    return((pose-4)%25)

Un pequeño apunte: hasta aquí solo hemos utilizado como herramienta estadística que las letras e y a son las más frecuentes en un texto español. ¡Imagina si usáramos argumentos más elaborados!

Cómo descifrar el cifrado indescifrable

Como decíamos en el vídeo, hacer estadística con el cifrado de Vignère es más complicado, pero no imposible. Todo empieza por advertir que este cifrado es como hacer varios cifrados César por separado. Si utilizamos como clave secreta [3,14,16], todas las letras del texto que estén en la posición primera, cuarta, séptima, etc., estarán cifradas por el número 3. Es decir, es como si una parte del texto, algunas letras sueltas, estuvieran cifradas con un cifrado César de clave 3.

Si supiéramos qué longitud tiene la clave secreta, podríamos calcular las frecuencias como lo hacíamos con el cifrado César. ¿Pero cómo sabemos qué longitud tiene una clave secreta? Hay varias técnicas para averiguarlo.

La más sencilla de implementar es el índice de coincidencia, una medida estadística que indica la probabilidad de que dos letras elegidas al azar de un texto sean iguales. Es un tema bastante extenso, pero la idea clave es la siguiente: como las letras de un texto no están distribuidas uniformemente (hay letras mucho más comunes que otras), podemos hacer un cálculo con las frecuencias de todas las letras y obtener un número que nos diga si un texto encaja con la frecuencia de letras del español o no.

El índice de coincidencia se calcula según la expresión

\textbf{IC}  = \cfrac{\displaystyle\sum_{i=1}^{25}n_i(n_i-1)}{N(N-1)/25},

donde n_i es la cantidad de veces que aparece la letra i-ésima del alfabeto y N es el número total de letras del texto. Para un texto corriente en español, este valor es aproximadamente 1.94. Y este valor no cambiar al aplicar un cifrado César. Por tanto, si te encuentras un texto en español cifrado al estilo César y calculas el índice de coincidencia, debería ser similar a 1.94.

¿Cómo utilizar esto para averiguar la longitud de una clave secreta? Imagina que la clave secreta tiene cuatro números, que representamos en la siguiente imagen. Las letras que están sobre el mismo color se han cifrado con el mismo número.

Si calculamos la frecuencia de todas las letras del mensaje, cada una estará cifrada con un número distinto y las frecuencias no encajarán con las del español. Sin ir más lejos, hay dos F en el mensaje cifrado, pero cada una se ha cifrado con un número distinto, así que proceden de dos letras distintas. Si calculamos el índice de coincidencia con todas las letras del texto, no se parecerá al 1.94 típico del español, lo que nos indica que el texto no está cifrado con un único número. No es un cifrado César.

Ahora nos fijamos solo en las letras que aparecen en las posiciones pares. De nuevo, cada una está cifrada con un número distinto. Al calcular las frecuencias, veremos que tampoco se corresponden a las de un texto en español, porque el índice de coincidencia es distinto a 1.94. Deduciremos que la clave no es de longitud 2.

Ahora nos fijamos solo en las letras que aparecen cada tres posiciones. Cada una está cifrada con un número distinto. Al calcular las frecuencias, veremos no se corresponden a las del español, porque el índice de coincidencia es distinto a 1.94. Deduciremos que la clave no es de longitud 3.

Si nos fijamos solo en las letras que aparecen cada cuatro posiciones, la situación cambia. Estas letras están cifradas con el mismo número, como si fuera un cifrado César. Al computar sus frecuencias y calcular el índice de coincidencia, es esperable que se parezca a 1.94.

Con esta idea podemos crear una función que revise todas las longitudes de claves. La función debería separar las letras del texto en grupos de dos, tres, cuatro, etc., y calcular el índice de coincidencia para cada grupo. Aquella separación que produzca un índice de coincidencia más parecido a 1.94 será la longitud más probable de la clave.

def calcular_ic(subtexto):
    # Calcula el índice de coincidencia de un texto. 

    # Cuenta la frecuencia de todas las letras
    # del texto, creando un diccionario.
    letras = defaultdict(int)
    letras_totales = 0

    for letra in subtexto:
        if letra in albe:
            letras[letra] += 1
            letras_totales += 1

    # Calcula el índice de coincidencia a partir 
    # de las frecuencias.
    ic = 0
    for l in albe:
        ic += letras[l]*(letras[l]-1)*25

    if letras_totales > 1:
        return ic/(letras_totales**2-letras_totales)
    else:
        return 0


def long_clave(texto):
    # Estima la longitud de la clave secreta a partir
    # del índice de coincidencia.
    
    ic_teo = 1.94 # Índice de coincidencia del español.
    tol_min = 0.90 # Porcentaje de satisfacción de la clave.
    long_max = 100 # Longitud máxima de la clave.
    long_tanda = 10 # Probar claves de 10 en 10.
    media = False # Calcular la media de los índices.
    lg = 2 # Primera longitud que prueba
    
    lista_ic = {}
    tol = 0 
    
    start = time.time()

    while tol < tol_min and lg < long_max:
        for long in range(lg, lg + long_tanda):

            #Si lo calculas con la media.
            if media:
                ics_subtextos = []
                for columna in range(long):
                    subtexto = texto[columna::long]
                    ic_col = calcular_ic(subtexto)
                    ics_subtextos.append(ic_col)
    
                ic_medio = sum(ics_subtextos) / len(ics_subtextos)
                lista_ic[long] = 1 - (ic_medio - ic_teo)**2
                
            #Si lo calculas sin la media.
            else:
                subtexto = texto[::long]
                ic_col = calcular_ic(subtexto)
                lista_ic[long] = 1 - (ic_col - ic_teo)**2

        tol = max(lista_ic.values())
        lg += long_tanda

    # Ordenar las logitudes más probables
    lista_ic = dict(sorted(lista_ic.items(), key=lambda x: x[1], reverse=True))
    longs = list(lista_ic.keys())
    ics = list(lista_ic.values())

    print('Longitudes más probables de la clave:\n')
    for i in range(0, 3):
        print('\tLongitud = ' + str(longs[i]) + '\t ({:.2f} %)'.format(ics[i] * 100))

    tiempo_total = time.time() - start
    print('\nTiempo empleado: {:.3f} s.'.format(tiempo_total))

    return longs[0], tiempo_total

La función long_clave recibe un texto cifrado y estima cuál es la longitud de clave más probable. El programa separa el texto en grupos de letras y calcula el índice de coincidencia con la primera letra de cada grupo. La función empieza con grupos de longitud lg, y prueba todas las longitudes hasta long_max. Es posible que el programa se detenga antes: no comprueba todas las claves de golpe, sino que lo hace por tandas de 10 claves (se puede modificar con la variable long_tanda). Si encuentra alguna longitud que produzca un índice de coincidencia muy bueno entre los diez primeros intentos, ya no busca más. Si no lo encuentra, comprueba las diez siguientes. Así hasta llegar a long_max.

También está el parámetro media. La idea es que la función calcula el índice de coincidencia solo con las primeras letras de cada grupo (en el ejemplo de arriba, solo con las letras que están cifradas con el color azul). Para textos largos es perfecto, porque es un proceso más rápido y da buenos resultados. Para textos cortos puede ser un problema, porque hay muy pocas letras para hacer estadística. En ese caso, podemos activar media = True y la función calculará el índice con las letras de color azul, luego las verdes, luego las rojas y después las amarillas, y hará la media de todas ellas. O sea, calculará el índice con todas las letras del grupo, no solo con las primeras. Es más largo, pero para textos cortos ayuda ligeramente a mejorar la estadística.

¡A descifrar el texto!

Ya solo queda juntar todo lo anterior en una función que reciba un texto cifrado e intente descifrarlo.

Al descubrir qué longitud tiene la clave secreta, hemos reducido el problema a varios cifrados César. Siguiendo el ejemplo anterior: como las letras cifradas con el color azul forman un cifrado César, podemos estudiar la frecuencia de todas ellas y suponer que la más frecuente es la e o la a. Lo mismo para las letras cifradas en verde, amarillo o rojo. Uno por uno, resolvemos cada cifrado César con un análisis de frecuencias.

def intento_descifrar(texto):
    # Intenta descifrar el texto calculando índices de
    # coincidencia y probando la longitud de clave más 
    # probable.
    
    long, tiempo_total = long_clave(texto)
    prob_clave = []

    start = time.time()
    
    for resto in range(long):
        cesar = encontrar_clave_cesar(texto[resto::long])
        prob_clave += [cesar]
    
    print('\nClave más probable: \t'+ str(prob_clave))
    print('\nTiempo total: {:.3f} s.'.format(tiempo_total + time.time() - start))
    print('\n\n------ Texto descifrado ------')
    print(desencriptar(texto[:300], prob_clave) + '...')

Y ya habríamos terminado. Al introducir una línea de código como esta,

intento_descifrar(texto)

la consola nos devuelve este resultado:

Longitudes más probables de la clave:

	Longitud = 5	 (96.55 %)
	Longitud = 10	 (93.69 %)
	Longitud = 6	 (46.72 %)

Tiempo empleado: 0.002 s.

Clave más probable: 	[1, 2, 3, 4, 5]

Tiempo total: 0.002 s.


------ Texto descifrado ------
muchosañosdespues,frentealpelotondefusilamiento,elcoronel
aurelianobuendiahabiaderecordaraquellatarderemotaenquesu
padrelollevoaconocerelhielo.macondoeraentoncesunaaldea
deveintecasasdebarroycañabravaconstruidasalaorilladeun
riodeaguasdiafanasqueseprecipitabanporunlechodepiedras
pulidas,blancasyenor...

¡El resultado es increíble para un texto tan corto! La experiencia me dice que no es habitual que los textos cortos se descifren tan bien. Sobre todo porque solo hemos usado dos herramientas estadísticas: el índice de coincidencia y que las letras más frecuentes son la a y la e. Podríamos incluir métodos más elaborados, pero para textos de varias páginas es más que suficiente.

Otra cosa en la que poner atención: los múltiplos y divisores de la longitud de la clave dan índices de coincidencia más grandes que el resto de longitudes. Al usar una clave de 15 números, veremos que el programa detecta índices de coincidencia bastante altos para claves de tres y cinco números (los divisores) y para claves de treinta o cuarenta y cinco números (sus múltiplos). Dejo al lector que piense por qué ocurre esto.

Y un último apunte: cuando el programa indica las longitudes más probables de la clave, el porcentaje que muestra en pantalla no es una probabilidad como tal. Es un porcentaje que mide la diferencia entre el índice de coincidencia del español (1.94) y el del texto que estamos estudiando.