La Mengambrea

Recetas para revolver letras

En diciembre pasado se me ocurrió la brillante idea de escribir sobre algoritmos de cifrado "manuales" (de lápiz y papel). Desde entonces he ido preparando pedacitos de esto en los ratos libres: una explicación aquí, una función Javascript allá… Y el fin de semana pasado decidí juntar todo y publicarlo. Para mi horror, el artículo resultó enorme. Larguísimo, denso, inductor de terribles dolores de cabeza.

Al final opté por partirlo en dos. Esto que está usted leyendo ahora puede considerarse una discusión preparatoria de conceptos y métodos que serán usados en la segunda parte, a publicar mañana. Y es que ¿qué tanto recuerda usted de Criptografía I, en el kinder? Considere esto un "curso propedéutico", si le parece.

Este artículo contiene además unas "calculadoras" que quizá funcionen en su navegador. Software incrustado, pues. Y permítame contarle: si de por sí es feo escribir Javascript, es una maldita pesadilla incrustarlo en Blogger…

Eh bueno. No deje que las calculadoras lo ablanden. Fortalezca su carácter: vaya por su lápiz y su papel cuadriculado.

Suma y resta sin acarreo

El primer procedimiento que discutiremos hoy sirve para producir números a partir de otros números, cosa que suele ser necesario hacer como parte de algoritmos más complicados. Es un procedimiento trivial: sumar y restar, pero sin acarrear las decenas. Nada de "ocho mas cuatro es dos y llevamos uno", y esas cosas; la idea es combinar números, no hacer aritmética. Sin la necesidad del acarreo, estas operaciones pueden realizarse en cualquier dirección. De izquierda a derecha, si lo desea.

+ ▼

− ▼

Suma encadenada

La "suma encadenada" es un método para obtener series de números al azar, de longitud arbitraria, sin patrones de repetición obvios. El procedimiento es como sigue. Toma usted los dos primeros dígitos de una secuencia corta, la "semilla", y los suma ignorando el acarreo. El dígito resultante se agrega al final de la semilla. Luego toma el segundo y el tercer dígito y los suma, agregando el resultado al final, etc. Cuando se agotan los dígitos de la semilla original se usan los que ya han sido generados. El procedimiento se repite hasta que se hayan producido los números que se requieran. En la calculadora, abajo, usted puede teclear una semilla y esta se expandirá a 50 dígitos.

▶

Esto no es otra cosa que un registro de desplazamiento con retroalimentación lineal: un mecanismo común para generar secuencias de números pseudo-aleatorios.

Permutación

Ahora, un sistema para reordenar los caracteres de un "texto" con base en una "llave", donde texto y llave son cadenas de la misma longitud.

Para realizar la permutación, busque la primer ocurrencia del "menor" caracter en la llave. Este es el dígito más pequeño, o la letra que aparece primero en el alfabeto. Escriba, en la posición donde lo encuentre, el primer caracter del texto. Si el menor caracter ocurre de nuevo en la llave, asigne ahí el segundo caracter del texto, etc. Luego busque el siguiente caracter menor y ponga ahí el siguiente caracter del texto, y así hasta terminar la permutación.

En la calculadora, abajo, usted puede teclear cualquier llave y texto, y el software realizará la permutación por usted (¡recuerde hacer llave y texto de la misma longitud!).

Llave
Texto
	▼
Resultado

Sustitución alfabética

La sustitución alfabética es el primer algoritmo criptográfico completo que discutiremos hoy. "Completo" en el sentido de que, con base en una regla general, puede transformar un mensaje de longitud arbitraria en un amasijo ilegible a primera vista. Por supuesto, esto es terriblemente primitivo y no ofrece ninguna seguridad: es criptografía de nivel de premio de caja de cereal. Pero es útil como componente de un procedimiento más elaborado.

En esta transformación, el alfabeto origen es el conjunto de caracteres con los que escribirá sus mensajes en claro; el alfabeto destino, el conjunto de caracteres que aparecerán en los mensajes cifrados. Para cifrar, se toma cada ocurrencia en el texto del primer caracter del alfabeto origen y se reemplaza por el primer caracter en el alfabeto destino. Luego el segundo caracter, luego el tercero, etc.

Origen
Destino
Texto
	▼▲
Resultado

Note que la calculadora, arriba, sabe cifrar y descifrar. Note también que los espacios en blanco son suprimidos: una práctica común que incrementa marginalmente la seguridad.

Transposición de columnas

¿Listo para algo más complejo? La transposición de columnas básica es otro algoritmo de cifrado primitivo, un poco menos inocente que el anterior. Se trata de crear una matriz cuadrada, tan ancha como la longitud de una "llave", que puede ser una palabra arbitraria. Luego se copian los primeros caracteres del texto en el primer renglón de la matriz, y se continúa copiando en renglones subsecuentes.

Enseguida se identifica la primer ocurrencia del menor caracter en la llave, y se comienza a escribir el texto cifrado copiando los caracteres en esa columna, de arriba a abajo. Luego, si el caracter menor vuelve a ocurrir en la llave, se copia esa columna; luego la del siguiente menor, etc. El resultado es el texto cifrado.

Llave
Texto
	▼
Matriz	MITOCONDRIA ----------- AGENTEOCHOD OSENPOSICIO NSTOPESPERA NDOINSTRUCC IONES
	▲
Resultado

Para "descifrar" una transposición de columnas se sigue el procedimiento inverso: se llenan las columnas verticalmente, en el orden dado por la llave, y luego se lee horizontalmente. Hay una ligera complicación: debe medir la longitud del texto cifrado antes de comenzar a llenar la matriz, para saber cuántos espacios le van a "sobrar" en el último renglón. Y tacharlos o algo.

La calculadora, arriba, opera también en dirección inversa: pruebe escribir como "llave" el texto PELIAGUDO y como "resultado" el texto ESRQP OIERO EAEAD ZVAUE DAOAL NLHTE UNNIN RSTLA VESEL y dele al botón "Descifrar".

Straddling checkerboard

Ahora veremos el primer sistema de nivel superior al preescolar. El straddling checkerboard es un sistema para representar un mensaje con un alfabeto pequeño, comúnmente los dígitos, ocultando en cierta medida la frecuencia en que ocurre cada letra en el texto original. Para esto se construye una matriz. En el primer renglón se escriben los dígitos, en un orden dado por una llave arbitraria. En el segundo renglón, los caracteres más frecuentes del idioma de los mensajes, en alguna combinación preacordada, y dejando algunos "huecos". Finalmente, en los siguientes renglones se escribe el resto del alfabeto. Se escriben también, como "etiquetas" para el segundo renglón y los subsecuentes, los dígitos que hayan quedado sobre los "huecos" de arriba.

Esto es más fácil de entender viendo un ejemplo. Observe la matriz en la calculadora. Cambie la llave (¡que debe ser de diez posiciones!) y el idioma, si desea ver matrices alternativas. Y, si se está preguntando esto: las letras más frecuentes del español son E, A, O, S, R, N, I y D.

Para cifrar un caracter, observe en qué parte de la matriz aparece. Si aparece en el renglón de las letras frecuentes, simplemente escriba el dígito arriba de él. Si aparece en los renglones de abajo, escriba primero el dígito "etiqueta" de su renglón, y luego el dígito de la columna.

Llave	▶
Idioma	españolinglésruso
Texto
	▼
Matriz	9 0 4 5 7 6 3 1 2 8 +--------------------- | I R D E A S N O 4 | B C F G H J K L M P 6 | Q T U V W X Y Z . *
	▲
Resultado

Para descifrar una secuencia producida por un straddling checkerboard, lea uno por uno los dígitos cifrados. Si lee uno de los dígitos "etiqueta" de los renglones inferiores en la matriz, lea el siguiente dígito, identifique el caracter y escríbalo. De lo contrario, el caracter será uno de los caracteres frecuentes; simplemente identifíquelo por su columna.

La calculadora soporta también la operación de descifrado. Por ejemplo, escriba HIPOPOTAMO como llave, seleccione el idioma español, escriba la secuencia 73594 67783 89759 82216 39836 75296 10818 70163 73671 24659 35683 0 como "resultado" y déle al botón.

Observe que esta calculadora ordena los dígitos de 1 a 9, con 0 como último dígito, haciendo una permutación a partir de una llave (por eso debe ser de diez caracteres).

Transposición de columnas con discontinuidad

Esta es la última operación del propedéutico, la más difícil de explicar. Es una transposición de columnas similar a la descrita más arriba, pero con una complicación adicional.

Se prepara una matriz en la forma descrita para trasponer columnas, pero definiendo unas "secciones triangulares" que afectan el orden en que la matriz se llena. La primer sección triangular comienza en el primer renglón, justo en la columna del menor caracter en la llave. Si estuviera haciendo esto en papel, podría marcar esa celda, y todas las subsecuentes hasta el final del renglón, con un resaltador amarillo. En el siguiente renglón haría lo mismo, pero iniciando un caracter a la derecha. En el siguiente, uno más a la derecha, etc. hasta que sólo haya qué marcar una celda, la última. Luego salta un renglón, e inicia una nueva sección triangular bajo el siguiente caracter menor de la llave.

Para entender esto con un ejemplo, escriba PENTOTAL como llave en el simulador abajo, llene con algo el campo de texto y observe las áreas triangulares que se producen.

Para llenar la matriz escriba los caracteres del mensaje, igual que antes, pero evitando las áreas triangulares. Cuando llegue al final de la matriz, llene el resto del mensaje en las áreas triangulares. Juegue con la calculadora para entender visualmente este concepto.

Llave
Texto
	▼
Matrices	PENTOTAL -------- MISION COMPLET ASTOPREG R ES AND	PENTOTAL -------- MISIONOA COMPLETB ASTOPREG RASECONL ESAMERCA ANDNCIA
	▲
Resultado

Para descifrar, la matriz se llena de la misma manera que una transposición simple: por columnas, de arriba a abajo, en el orden dado por la llave. Y luego se lee el resultado considerando a las áreas triangulares.

Y sí, la calculadora sabe descifrar. Por ejemplo, pruebe la llave JOROBADO y el "resultado" OAMEV JGTNV STSUA ZIATA MSSIA RNBCT NMIEE RPIAN AAESA SIEOV .

¿Qué sigue?

Ya lo verá.

Vínculos: A reserva de la bibliografía completa, eche un ojo al capítulo Pencil and Paper Systems del Cryptographic Compendium de John Savard.

[Foto: Tabula recta, observada en algún lugar secreto en Berlín. Fuente: mrittenhouse's photostream en Flickr. Copyright © 2002 Magdalena Rittenhouse, algunos derechos reservados. El uso de esta fotografía está permitido bajo los términos de la licencia Attribution-NonCommercial-NoDerivs 2.0, como la publica Creative Commons.]

Etiquetas: cómo, cripto, hacks

Comentarios

La Mengambrea es el blog personal de César Rincón. Salvo donde se indica otra cosa, los textos, imágenes, software y otros materiales publicados en este sitio son Copyright © 1996-2007 César Rincón, pero su uso está permitido bajo los términos de la Licencia de Atribución 2.5 México, como la publica Creative Commons. This work is licensed under a Creative Commons Attribution 2.5 Mexico License. Coma frutas y verduras.