AMIGOS PARA SIEMPRE: Criptografía

Cifrados clásicos

El cifrado afín por bloques es un cifrado de clave simétrica por bloques en el que se utilizan transformaciones afines de aritmética modular. Este tipo de cifrado es similar al cifrado afín en el que, en lugar de sustituir o cifrar unos símbolos por otros, se cifran bloques.

Descripción

El mecanismo para cifrar se basa en sustituir bloques de n caracteres de texto en claro por bloques de n caracteres de texto cifrado utilizando una función afín de aritmética modular de la forma

(ax+b) \mod\ n

Para describir este tipo de cifradores veamos un ejemplo:

Supongamos que tenemos la secuencia 00,01,..,99 y supongamos que los número 00,...,25 representan las letras de la A a la Z respectivamente.
Supongamos que queremos enviar el mensaje "HOWDY DOO"
Primero agrupamos y dividimos el texto en claro en bloques de por ejemplo 4 caracteres quedando: HOWD YDOO
A continuación sustituimos cada letra por su equivalente numérico obteniendo: 07142203 24031414
Podemos decir que el entero más grande que puede aparecer en un bloque de tamaño 4 es ZZZZ=25252525, así que nosotros escogemos 25252525 como nuestro módulo n=25252525.
A continuación elegimos un valor de b entre 1 y n. Por ejemplo b=23210025.
Finalmente elegimos un valor de a de forma que mcd(a,n)=1. Por ejemplo nos vale a=21035433
Aplicando la función afín en aritmética modular $(21035433*x+23210025) \mod\ 25252525$

a los números obtenidos al cifrar los bloques obtenemos

(21035433*7142203+23210025) \mod\ 25252526=8007496

(21035433*24031414+23210025) \mod\ 25252526=20470469

lo que nos da en mensaje cifrado

08007496 20470469

y este es el mensaje cifrado.

Para descifrar aplicamos el proceso inverso. Calculamos el inverso multiplicativo de a=21035433 (por ejemplo usando el algoritmo de Euclides extendido) obteniendo $a^{-1}=5174971.$ . Despejando x en la ecuación afín en aritmética modular obtenemos $P_i=(a^{-1}(C_i-b)) \mod\ n$ y aplicando a los dos bloques cifrado tenemos:

P=(5174971(8007496-23210025)) \mod\ 25252526 =7142203

P=(5174971(20470469-23210025)) \mod\ 25252526 =24031414

lo que equivale a "HOWD YDOO"

Criptoanálisis

Este tipo de cifrados no es vulnerable a análisis de frecuencias, sin embargo es susceptible a ataque en los que se conoce el texto cifrado de un texto claro también conocido (es lo que se llama ataque de texto en claro conocido)

Ataque de texto en claro conocido

Supongamos que conocemos el texto cifrado conocido (0800749620470469) de un texto en claro también conocido (HOWD YDOO). Al conocer el texto en claro podemos intuir aproximadamente cual es el valor del módulo con el que vamos a trabajar. Por ejemplo vamos a suponer que trabajamos con el alfabeto de del inglés con 25 caracteres. Por tanto n=25252525. A partir de ahí podemos establecer las siguiente ecuaciones:

8007496=(7142203 m + b) \mod\ 25252526

20470469=(24031414 m + b) \mod\ 25252526

Restado de la segunda ecuación la primera obtenemos:

12462973=(16889211*m) \mod\ 25252526

Despejando

m=21035433

y reemplazando en la primera ecuación obtenemos:

b=23210025 \mod\ 25252526.

el cifrado César, también conocido como cifrado por desplazamiento, código de César odesplazamiento de César, es una de las técnicas de cifrado más simples y más usadas. Es un tipo de cifrado por sustitución en el que una letra en el texto original es reemplazada por otra letra que se encuentra un número fijo de posiciones más adelante en el alfabeto. Por ejemplo, con un desplazamiento de 3, la A sería sustituida por la D(situada 3 lugares a la derecha de la A ), la B sería reemplazada por la E, etc. Este método debe su nombre a Julio César, que lo usaba para comunicarse con sus generales.

El cifrado César muchas veces puede formar parte de sistemas más complejos de codificación, como el cifrado Vigenère, e incluso tiene aplicación en el sistema ROT13. Como todos los cifrados de sustitución alfabética simple, el cifrado César se descifra con facilidad y en la práctica no ofrece mucha seguridad en la comunicación.

Ejemplo

La transformación se puede representar alineando dos alfabetos; el alfabeto cifrado es un alfabeto normal que está desplazado un número determinado de posiciones hacia la izquierda o la derecha. Por ejemplo, aquí el cifrado César está usando un desplazamiento de seis espacios hacia la derecha:

Texto original:   ABCDEFGHIJKLMNÑOPQRSTUVWXYZ
Texto codificado: GHIJKLMNÑOPQRSTUVWXYZABCDEF

Para codificar un mensaje, simplemente se debe buscar cada letra de la línea del texto original y escribir la letra correspondiente en la línea codificada. Para decodificarlo se debe hacer lo contrario.

Texto original:   WIKIPEDIA, LA ENCICLOPEDIA LIBRE
Texto codificado: CÑPÑVKJÑG, QG KSIÑIQUVKJÑG QÑHXK

La codificación también se puede representar usando aritmética modular, transformando las letras en números, de acuerdo al esquema A = 0, B = 1,..., Z = 26.¹ La codificación de la letra x con un desplazamiento n puede ser descrita matemáticamente como:²

$E_n(x) = x + n \mod {27}.$

La decodificación se hace de manera similar:

$D_n(x) = x - n \mod {27}.$

La operación de sustitución se conserva siempre a lo largo de todo el mensaje, por lo que el cifrado se clasifica como un cifrado de tipo sustitución monoalfabética, en oposición a la sustitución polialfabética.

Historia y uso

El cifrado César fue nombrado así en honor a Julio César, quien usó un alfabeto con desplazamiento de tres espacios.

El cifrado César recibe su nombre en honor a Julio César, que, según Suetonio, lo usó con un desplazamiento de tres espacios para proteger sus mensajes importantes de contenido militar:

Si tenía que decir algo confidencial, lo escribía usando el cifrado, esto es, cambiando el orden de las letras del alfabeto, para que ni una palabra pudiera entenderse. Si alguien quiere decodificarlo, y entender su significado, debe sustituir la cuarta letra del alfabeto, es decir, la D por la A, y así con las demás.

Suetonio, Vida de los Césares 56 [1].

Aunque César es la primera persona de la que se sabe que haya usado este sistema, anteriormente ya se utilizaron otros cifrados por sustitución. El sobrino de Julio César, Augusto, también empleó el cifrado pero con un desplazamiento de uno:

Cuando escribía un texto cifrado, sustituía la B por la A, la C por la B y el resto de las letras de ese mismo modo, usando AA para la X.

Suetonio, Vida de Augusto 88.

Hay indicios de que Julio César usaba también sistemas más complicados, y un escritor, Aulus Gellius, hace referencia a un tratado (ahora perdido) sobre el cifrado:³

Hay incluso un tratado ingeniosamente escrito del gramático Probus referente al significado secreto de las letras en la composición de las epístolas de César.

Aulus Gellius, 17.9.1–5.

No se sabe cuán efectivo resultaba realmente el cifrado César en esa época, pero debió ser razonablemente seguro, ya que pocos enemigos de César habrían sabido leer, y mucho menos podrían haber llevado a cabo el criptoanálisis necesario. Asumiendo que el atacante pudiera leer el mensaje, no existen pruebas de la existencia de técnicas para solucionar este tipo de codificación.⁴

En el siglo XIX, la sección de avisos personales de los periódicos servía a veces para intercambiar mensajes codificados usando técnicas de cifrado simples. David Kahn (1967) describe algunos ejemplos de comunicación secreta entre amantes que utilizaban este cifrado en el periódico The Times.⁵ Incluso en 1915, el cifrado César aún era utilizado: la armada rusa lo empleaba sustituyendo a otros cifrados más complicados que habían resultado muy difíciles de utilizar por sus tropas; los criptoanalistas alemanes y austriacos no tuvieron mucha dificultad para decodificar los mensajes.⁶

El cifrado César se puede encontrar en la actualidad en algunos juguetes modernos, como los anillos decodificadores. En el algoritmo ROT13 se usa el cifrado César con un desplazamiento de 13, un método simple para ofuscar el texto que se usa en algunos foros de internet para ocultar texto (como la línea final de un chiste o partes de una historia que no se quieren revelar), pero no se usa como método de codificación.⁷

El cifrado Vigenère usa el cifrado César con un desplazamiento diferente en cada posición del texto; el valor del desplazamiento se define usando una palabra clave repetitiva. Si la palabra clave fuera escogida al azar y tan larga como el mensaje (para que no se repita), el sistema resultante sería, en teoría, indescifrable. Para claves más cortas que el mensaje (es decir, por el cifrado Vigenère), que es lo que se usaba históricamente, aparece en el texto un patrón cíclico que se puede detectar con elmétodo Kasiski, y saber la longitud de la clave. Una vez conocida la longitud de la clave, por ejemplo k, entonces el criptograma se descompone en criptogramas k de César que se pueden descifrar con un análisis frecuencial.⁸

A modo anecdótico, cabe señalar también que el capo mafioso Bernardo Provenzano, recientemente detenido, utilizaba para comunicarse, en pleno siglo XXI, notas escritas con una máquina de escribir, codificadas mediante este rudimentario algoritmo, renegando de cualquier tecnología nueva como el teléfono móvil o internet. A pesar de lo rudimentario del sistema, ha conseguido tener a la policía despistada durante años.⁹

Descifrado

Desplazamiento	Posible mensaje original
0	`Ep exeuyi`
1	`Do dwdtxh`
2	`Cn cvcswg`
3	`Bm bubrvf`
4	`Al ataque`
5	`Zk zszptd`
6	`Yj yryosc`
...
23	`Hs hahxbl`
24	`Gr gzgwak`
25	`Fq fyfvzj`

El descifrado del cifrado César puede hacerse fácilmente, incluso si sólo se dispone de un texto cifrado corto. Se pueden considerar dos situaciones:

Un atacante conoce (o adivina) que se puede utilizar alguna forma simple de sustitución de letras, pero no sabe que se usa el cifrado César.
Un atacante sabe que se ha empleado el cifrado César, pero no conoce el valor del desplazamiento.

En la primera situación se pueden aplicar dos métodos. El primero se basa en un ataque de fuerza bruta:¹⁰ como sólo existe un determinado número de valores de desplazamiento, 27 en español, se pueden probar todos y cada uno hasta encontrar un mensaje coherente.¹¹ Una forma de hacer esto es usar una tabla y en cada renglón escribir el texto con un desplazamiento diferente.¹² El ejemplo de texto cifrado dado en la tabla de la derecha es "Ep exeuyi"; se puede reconocer el mensaje original a simple vista con un desplazamiento de cuatro.

En la segunda situación, el proceso de descifrado es aún más directo. Como sólo hay un número limitado de posibles desplazamientos, se pueden probar todos por orden, en un ataque por fuerza bruta.¹³ Una forma de hacerlo es escribir una tabla en la que se descifra un pedazo del texto con todos los desplazamientos posibles¹⁴ — esta técnica a veces se conoce como «completando el componente claro».¹⁵ En el ejemplo de la tabla de la derecha se intenta decodificar el texto cifrado «Ep exeuyi»; en este caso, el texto coherente se reconoce instantáneamente a simple vista, encontrándose codificado por un desfase de cinco letras hacia la izquierda. Otra forma de obtener la solución mediante este método es escribiendo debajo de cada letra el alfabeto en orden inverso y empezando por esa letra. Este proceso se puede acelerar usando cintas verticales con el alfabeto escrito en orden inverso y alineado, de modo que formen el texto cifrado en una fila. Así, el texto coherente debe aparecer en alguna de las filas.

Distribución de las letras en un texto común enespañol.

El segundo método de descifrado consiste en comparar las distribuciones de frecuencias de las letras (análisis de frecuencia). Representando las frecuencias de las letras en el texto cifrado y conociendo la distribución de letras en el idioma original del mensaje original, una persona puede determinar fácilmente el valor del desplazamiento. Por ejemplo, en español, las frecuencias de las letras E y A (las más frecuentes) y las de la K y la W (las menos frecuentes) son particularmente distinguibles.¹⁶ Los ordenadores también pueden hacerlo a base de mediciones, haciendo que la distribución actual coincida con la distribución esperada (se puede utilizar por ejemplo unanálisis de distribución chi cuadrado).¹⁷

La mayoría de las veces sólo se encontrará un mensaje descifrado. Sin embargo, cuando el mensaje es muy corto pueden aparecer varias palabras descifradas. Por ejemplo, "ezaz" puede ser descifrado como "topo" o "jefe"; de manera similar "xzyz" puede ser descifrado como "cede" o "mono".

Repetir el proceso de cifrado varias veces no mejora la seguridad. Esto se debe a que usar dos desplazamientos, por ejemplo el desplazamiento A y el desplazamiento B, sería equivalente a usar un desplazamiento de A + B. En terminología matemática, el cifrado repetido con diferentes claves forma un grupo.