La Mengambrea

Sexo, UNIX y rocanrol
2007/02/06

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
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
Texto
Matriz
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
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: , ,

Enlace permanente   - 20:33 - deje un comentario (hay 9)
Con la llave ZOKETE (sin alusiones personales, por supuesto, salvo hacia mi mismo): AAAÍ..MIPESOM.RDAD
Anonymous Anónimo dijo:
Ya lo dije, flaco: es para fortalecer tu carácter :)
Blogger Herel dijo:
Ya me dirás cómo has conseguido meter javascript, porque yo ya lo intenté y no hubo forma.
Con los ordenadores, estos sistemas que pones como introducción no creo que sean los más óptimos, aunque ya supongo que en el segundo capítulo hablarás de las operaciones a nivel de bit, y para el tercero espero ansioso el ¡Algoritmo Definitivo! :D

Por cierto, ya con el tema. En USA era ilegal crear una encriptación que el gobierno no sea capaz de descifrar ¿no?
Anonymous Anónimo dijo:
Tienes que considerar la incrustación de tags <br> que hace Blogger, y tienes que ignorar una advertencia acerca de que tu html es "inválido" al momento de postear... toda una monserga. Acabé instalando el script en otro servidor, y sólo usándolo en los handlers.

Y no, el siguiente artículo no trata de operaciones de bits. Pero sí trata de el ¡Algoritmo Definitivo! :)

(Ejem, para ciertos valores de "definitivo", esto es.)

En USA era ilegal exportar sistemas criptográficos de cierto nivel para arriba. Ya no lo es. En Francia, era ilegal usar sistemas criptográficos de cualquier tipo, sin permiso de papá gobierno. Antes del 2000, este artículo habría sido ilegal en Francia :S (y a la fecha tienen ciertas leyes extrañas al respecto).

El estatus de la criptografía en las leyes alrededor del mundo se sigue en el Crypto Law Survey, mira su resumen gráfico.

Y por cierto, España tiene una ley curiosita sobre esto: ve el artículo 36 del título III de tu Ley General de Telecomunicaciones :)
Blogger rm dijo:
Todo esto escapa de mi escaso entendimiento, pero ha sido todo un ejercicio estimulante leer tu artículo.

Esperaré el de mañana, compañero
Blogger Herel dijo:
Ah, menos mal que el artículo 36 son sólo unas pocas líneas... con lo divertidas que son sobre todo las introducciones de estos tochos en plan: según lo referido en el artículo 4 relativo a la ley 98/34 derrogada por la 99/45 y según lo dispuesto en lo anterior con referencia a lo posterior y lo de más al lado dictaminado por el 04/56 conforme a lo primero y lo tercero pero no a lo segundo.

Pues nada, a ver qué algoritmo "definitivo" será...
Blogger Zereth dijo:
Dios!


Que sustancia debo ingerir para entender de lo que hablas????

uuuuuuhhhh mañana exige el antidoping a tus lectores antes de iniciar el curso avanzado.


:D al menos me entretuve rellenando espacios, en lo que trataba de captar que diablos hacer con el cursito acelerado para blogueros.... creo que el post se lo enviaré a unos que veo sin quehacer, jajaja.

Saludos
Blogger jobu dijo:
Bueno, por lo menos la explicación del ketchup me quedó clara.
Un saludo.
Anonymous Anónimo dijo:
Ricardo, qué gusto verte por aquí. No sin cierto remordimiento por estarte distrayendo de las cosas importantes que normalmente te ocupan...

Zereth: dietilamida de ácido lisérgico. Amida o hidroxitilamida, en su defecto. Y usté cada día se ve más guapa, doc :)

Gente... estoy empezando a preocuparme. ¿Sí está de plano en chino? Odiaría causar a alguien un aneurisma con el próximo artículo...
Haga clic aquí para dejar un comentario
g