Libreta de un solo uso: inviolable una vez, rota con dos

Aplica la operación XOR entre cada byte de un mensaje y un byte aleatorio de la clave: el criptograma no revelará nada a un adversario. Pero si empleas esa misma clave en dos mensajes, se desvanece; basta con suponer una palabra, deslizarla y leer el otro mensaje que asoma debajo.

Ejemplo resuelto — Libreta de un solo uso: inviolable una vez, rota con dos

Caracteres	14
Claves posibles de esta longitud	5,2 × 10³³

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Libreta de un solo uso: inviolable una vez, rota con dos

Una libreta de un solo uso combina cada carácter de un mensaje con un carácter de clave elegido al azar, utilizado para ese único carácter y nunca más. Aquí la combinación se realiza mediante la operación binaria XOR (o exclusivo), byte a byte: C = P ⊕ K, y el descifrado es idéntico: P = C ⊕ K. Si la clave es aleatoria y tan larga como el mensaje, el sistema ofrece secreto perfecto: conocer el criptograma no altera en nada la probabilidad de qué mensaje se envió. Si se reutiliza la clave en dos mensajes, esta se anula, C₁ ⊕ C₂ = P₁ ⊕ P₂, y la técnica del crib dragging desliza una palabra supuesta w a lo largo del resultado: en cualquier punto donde un mensaje contenga realmente w, el cálculo w ⊕ C₁ ⊕ C₂ revelará el otro mensaje.

Qué significa cada símbolo

P: el mensaje, a razón de un byte por carácter
K: la clave: bytes aleatorios, tantos como caracteres tenga el mensaje
C: el criptograma, P ⊕ K
⊕: o exclusivo (XOR): cada bit del resultado vale 1 donde los dos bits difieren
w: el crib, una palabra que se conjetura presente en uno de los mensajes

Supone: Los mensajes constan de letras minúsculas y espacios almacenados como bytes ASCII. Los bytes de la clave proceden de un generador inicializado con una semilla de 32 bits, de modo que la página solo puede generar 2³² ≈ 4,3 × 10⁹ claves; a partir de siete caracteres hay menos claves que mensajes y, según la formulación de Shannon, la libreta de esta página no alcanza el secreto perfecto. Una libreta real exige bytes que nadie pueda reproducir. Consideramos que un fragmento «parece texto real» cuando cada byte es una letra o un espacio y cada secuencia de tres caracteres figura en los dos primeros tercios de «El escarabajo de oro» de Poe (1843); las parejas analizadas proceden del tercio final. Se emplea XOR en vez de suma de letras módulo 26 porque el XOR carece de signo: el fragmento resultante es el mismo sin importar cuál de los dos mensajes contenga el crib.

Probar todas las claves equivale a encontrar todos los mensajes 🖖

Avanza paso a paso por Ataque al amanecer y fíjate en las dos últimas filas. Contienen la clave que transformaría este mismo criptograma en «retreat at ten». Si escribes en la segunda casilla cualquier otra combinación de 14 letras y espacios simples, aparecerá también su clave correspondiente, porque la operación XOR es reversible: el criptograma XOR tu mensaje da la clave. Por tanto, un adversario que pruebe las 256¹⁴ claves posibles no encontrará el mensaje auténtico; obtendrá todas y cada una de las 27¹⁴ ≈ 1,1 × 10²⁰ cadenas de esa longitud, generada cada una por una clave única. Dado que todas las claves eran igual de probables al inicio, interceptar el mensaje no hace que ninguna de esas lecturas sea más probable que las demás. Shannon llamó a esto secreto perfecto en 1949 y demostró su peaje matemático: hacen falta al menos tantas claves como mensajes posibles. Una clave de Vigenère que se repite cuenta con muchísimas menos, razón por la cual un simple recuento de frecuencias puede romperla.

Los espacios asoman antes de aventurar una sola palabra 🖖

Pulsa Dónde están los espacios. La clave se ha cancelado: C₁ ⊕ C₂ es P₁ ⊕ P₂, byte a byte, sin que quede nada de la clave original. Observa ahora los bytes azules, 19 de los 50. Una letra minúscula se codifica entre 0x61 y 0x7a, mientras que el espacio vale 0x20. Como solo el cruce de una letra con un espacio activa el bit 0x40, cualquier byte igual o mayor que 64 señala un punto donde exactamente uno de los dos mensajes tiene un espacio. Antes de tantear palabra alguna, las separaciones entre términos ya se hacen visibles, aunque todavía no sepamos a qué mensaje corresponde cada una. En 2 000 pares de pasajes de 60 caracteres de «El escarabajo de oro», alrededor del 30 % de las posiciones muestran uno. El tráfico soviético que Meredith Gardner empezó a leer en 1946, bajo el nombre en clave estadounidense Venona, sumaba dígitos de clave a grupos de código en lugar de aplicar XOR a bytes, pero restar dos criptogramas anula la clave compartida con el mismo resultado. Esa clave se compartió por accidente: apremiada por el avance alemán sobre Moscú, la imprenta que producía las libretas del KGB fabricó unas 35 000 páginas de claves duplicadas.

Los dos espacios que rodean al crib hacen casi todo el trabajo 🖖

Pulsa Sin los espacios. «the» en la posición 26 produce «org». Son únicamente letras y cada grupo de tres aparece en el texto de referencia; aun así, ninguno de los dos mensajes contiene «the» en ese lugar. Vuelve a añadir los espacios, « the », y en esta pareja solo saldrán adelante los aciertos auténticos. Al analizar 2 000 pares de fragmentos de 60 caracteres del tercio final de «El escarabajo de oro» (que el modelo de referencia jamás vio), « the » superó el filtro en 3 661 posiciones y estaba presente de verdad en 3 281: cerca de nueve de cada diez. En cambio, «the» pasó en 9 615 y solo era real en 4 169, menos de la mitad. El motivo está en los bytes azules. Un espacio en el crib solo produce una letra sobre un byte de 64 o más, y solo da un espacio sobre un 0; frente a cualquier otro valor arroja un byte que ni siquiera es una letra. Por eso cada espacio del crib debe coincidir con una separación real, y una posición incorrecta rara vez acierta dos veces.

Problema resuelto al detalle

Cinco letras a partir de dos mensajes que comparten libreta 4 pasos
Se transmitieron dos mensajes de 50 caracteres con una misma libreta de un solo uso. En las posiciones 32 a 36, C₁ ⊕ C₂ muestra 54 06 09 0c 4e en hexadecimal. Conjetura que uno de los mensajes contiene « the » en ese tramo, con los bytes 20 74 68 65 20. ¿Qué dice el otro mensaje en esas cinco posiciones? Si la conjetura corresponde al mensaje 2, cuyo criptograma en ese intervalo es 9d 8e 23 40 9e, ¿cuáles son los cinco bytes de la clave? Pulsa después Ejemplo resuelto y avanza el siguiente paso en la página.

Abre este problema en la herramienta
1. Escribe el primer par en binario: 0x54 es 01010100 y el espacio 0x20 es 00100000. El XOR fija un bit a 1 allí donde ambos difieren, lo que da 01110100, es decir, 0x74: la letra t. El bit 0x40 de 0x54 ya indicaba, antes de cualquier conjetura, que uno de los mensajes contenía un espacio en la posición 32.
  
  $0x54 \oplus 0x20 = 01010100 \oplus 00100000 = 01110100 = 0x74 = t$
2. Las otras cuatro posiciones: 0x06 ⊕ 0x74 = 0x72, r; 0x09 ⊕ 0x68 = 0x61, a; 0x0c ⊕ 0x65 = 0x69, i; 0x4e ⊕ 0x20 = 0x6e, n. El otro mensaje dice «train», y sus tres secuencias de tres caracteres, «tra», «rai» y «ain», figuran en el texto de referencia.
  
  $54 06 09 0c 4e \oplus 20 74 68 65 20 = 74 72 61 69 6e = train$
3. Si « the » está en el mensaje 2, la clave se calcula como C₂ ⊕ P₂: 0x9d ⊕ 0x20 = 0xbd, 0x8e ⊕ 0x74 = 0xfa, 0x23 ⊕ 0x68 = 0x4b, 0x40 ⊕ 0x65 = 0x25, 0x9e ⊕ 0x20 = 0xbe. Si la palabra hubiese correspondido al mensaje 1, el mensaje 2 diría «train» y los bytes de clave serían C₁ ⊕ « the ». Como C₁ ⊕ C₂ es idéntico en ambos sentidos, la aritmética no puede revelar cuál es cuál.
  
  $K = C_{2} \oplus P_{2} = 9d 8e 23 40 9e \oplus 20 74 68 65 20 = bd fa 4b 25 be$
4. En la página, « the » se fija en el mensaje 2 en la posición 32, y la casilla del crib pasa a contener « train » en la posición 31, apostando a que «train» es una palabra completa en el mensaje 1. El resultado para el mensaje 2 es «y the r»: letras y espacios donde cada secuencia de tres ya se ha visto antes. Si la confirmas en el mensaje 1, ambas filas crecerán hasta siete caracteres.
  
  $(C_{1} \oplus C_{2})_{31..37} \oplus 20 74 72 61 69 6e 20 = 59 54 06 09 0c 4e 52 \oplus 20 74 72 61 69 6e 20 = 79 20 74 68 65 20 72$
Respuesta

«train», y los bytes de clave bd fa 4b 25 be si la conjetura correspondía al mensaje 2. Nada en C₁ ⊕ C₂ indica cuál de los mensajes contiene « the », ni podrá indicarlo jamás: intercambia ambos mensajes por completo y C₁ ⊕ C₂ seguirá intacto. Lo que decide la siguiente conjetura es qué fragmentos pertenecen al mismo mensaje. La página cuenta también cuántos caracteres recuperados son correctos porque conoce ambos mensajes originales. Un interceptor solo tiene las dos filas y su criterio para juzgar si tienen sentido.

$train, K_{32..36} = bd fa 4b 25 be$

Ruta de aprendizaje

Cómo se rompen los códigos

Referencias (2)

The first insight's perfect secrecy and its cost in keys, and the Vigenère link: C. E. Shannon, "Communication Theory of Secrecy Systems," Bell System Technical Journal 28(4), pp. 656–715, October 1949. §10 "Perfect Secrecy", Theorem 6 (pp. 679–682).
The second insight's Venona history: the additive key, the duplicate pages, Gardner's first message: "VENONA: An Overview," Cryptologic Almanac 50th Anniversary Series, Center for Cryptologic History, National Security Agency. DOCID 3575728, approved for release 2009.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.