Desencriptando (I): el problema de un mal amigo

Tengo un muy mal amigo que, sabiendo cómo soy para esas cosas y de qué manera me quitan el sueño, quiso alterar mi solaz enviándome esto:

cadena <- c(
"s","u","t","k","r","k","b","s","w","f","s","t","s","u","z","k","q","x","p","k","s","r",
"t","z","z","a","s","r","f","q","z","u","s","r","w","z","u","t","g","f","s","b","k","y",
"z","y","s","v","y","g","s","e","f","s","m","p","s","d","s","e","p","w","u","u","z","c",
"z","c","k","s","w","f","g","z","r","s","e","j","g","w","t","s","r","z","u","z","e","s",
"w","f","s","w","v","k","z","t","s","u","v","z","e","g","z","f","s","r","z","b","p","w",
"s","s","w","u","z","e","j","r","g","h","k","c","z","e","s","u","s","v","v","k","g","w",
"s","e","z","p","f","g","w","g","c","k","v","z","e","z","f","r","z","d","s","e","t","s",
"u","d","g","f","g","z","u","z","g","j","v","k","g","w","t","s","u","z","k","q","x","p",
"k","s","r","t","z","z","a","s","r","f","q","z","u","s","f","s","b","k","y","z","y","s",
"v","y","g","j","a","u","k","v","z","p","w","z","v","z","r","f","z","z","f","r","z","d",
"s","e","t","s","p","w","z","j","z","b","k","w","z","l","s","a","t","s","z","j","g","o",
"g","z","e","p","v","z","p","e","z","e","p","e","v","r","k","f","z","s","w","w","g","c",
"a","r","s","t","s","u","g","e","v","k","w","v","g","v","g","w","t","s","w","z","t","g",
"e","s","w","s","e","f","s","v","z","e","g","s","u","c","k","e","c","g","o","z","n","z",
"k","s","q","e","z","a","k","z","b","z","g","w","k","z","z","v","k","w","f","g","r","i",
"z","k","f","q","g","t","r","k","b","p","s","q","o","k","r","s","w","z","a","z","u","s",
"f","z","p","w","t","k","z","t","s","e","j","p","s","e","t","s","u","z","w","g","f","k",
"n","k","v","z","v","k","g","w","t","s","u","n","z","u","u","g","t","s","u","r","k","a",
"p","w","z","u","p","j","r","s","c","g","x","p","s","y","z","r","s","a","z","m","z","t",
"g","t","s","t","k","s","q","z","e","s","k","e","z","w","g","e","o","c","s","t","k","g",
"e","p","v","g","w","t","s","w","z","o","u","z","t","s","k","s","q","e","z","a","k","z",
"b","z","o","t","s","g","v","y","g","z","e","s","k","e","z","w","g","e","u","z","e","t",
"s","u","r","s","e","f","g","t","s","s","w","v","z","p","e","z","t","g","e","u","u","k",
"t","s","r","t","s","u","z","z","w","f","k","b","p","z","z","f","z","e","p","w","z","r",
"s","e","j","g","w","e","z","a","k","u","k","q","z","t","s","u","z","e","s","w","f","s",
"w","v","k","z","z","u","g","e","s","w","s","c","k","b","g","e","t","s","u","z","j","z",
"q","s","w","f","r","s","u","g","e","x","p","s","v","k","f","z","z","u","j","r","s","e",
"k","t","s","w","f","s","t","s","u","g","a","k","s","r","w","g","z","r","k","z","w","g",
"z","m","g","o","z","u","e","s","v","r","s","f","z","r","k","g","b","s","w","s","r","z",
"u","t","s","u","u","n","r","s","t","g","s","r","s","q","p","a","z","u","v","z","a","z",
"o","z","u","j","r","s","e","k","t","s","w","f","s","t","s","u","d","z","e","v","g","w",
"f","g","w","k","g","z","e","z","b","g","k","f","k","f","s","b","k","e","g","e","f","k",
"s","w","s","x","p","s","s","e","f","g","e","t","k","r","k","b","s","w","f","s","e","j",
"g","u","k","f","k","v","g","e","e","s","g","j","g","w","s","w","z","u","z","j","z","q",
"j","g","r","x","p","s","w","g","f","k","s","w","s","w","z","b","s","w","t","z","j","z",
"r","z","s","u","u","z","o","e","s","e","s","w","f","k","z","w","v","g","c","g","t","k",
"e","k","c","z","c","s","w","f","s","k","w","e","f","z","u","z","t","g","e","s","w","s",
"u","s","e","x","p","s","c","z","z","w","f","k","f","s","r","r","g","r","k","e","f","z",
"x","p","s","u","s","e","j","s","r","c","k","f","k","z","g","v","p","u","f","z","e","p",
"d","s","r","t","z","t","s","r","z","w","z","f","p","r","z","u","s","q","z","z","w","f",
"k","t","s","c","g","v","r","z","f","k","v","z","r","s","j","z","r","s","c","g","e","v",
"g","w","t","s","u","s","k","f","s","u","z","c","z","e","r","s","n","k","w","z","t","z",
"t","s","u","z","e","r","s","e","j","p","s","e","f","z","e","t","s","c","g","v","r","z",
"f","k","v","z","e","y","z","b","z","c","g","e","x","p","s","j","g","r","j","r","k","c",
"s","r","z","d","s","q","s","w","u","z","y","k","e","f","g","r","k","z","s","u","k","w",
"t","s","j","s","w","t","s","w","f","k","e","c","g","t","k","e","j","p","f","s","v","g",
"w","z","u","f","z","e","j","g","e","k","a","k","u","k","t","z","t","s","e","t","s","z",
"u","v","z","w","q","z","r","u","z","d","k","v","f","g","r","k","z","u","z","e","j","r",
"g","h","k","c","z","e","s","u","s","v","v","k","g","w","s","e","d","z","e","v","g","w",
"b","z","t","z","e","y","z","j","r","g","j","p","s","e","f","g","s","u","t","k","r","k",
"b","s","w","f","s","z","a","s","r","f","q","z","u","s","s","w","v","z","r","v","s","u",
"z","t","g","s","w","u","z","j","r","k","e","k","g","w","t","s","g","b","r","g","w","g")

Se trata de una cadena de 1144 caracteres que, aparentemente, encerraban algún tipo de mensaje. De hecho, era probable que se tratase de un mensaje codificado con una técnica que, dicen, ya empleaba Julio César en la campaña de las Galias y que describí en otra ocasión: a saber, mediante una permutación de letras.

Desencriptar supone, por lo tanto, encontrar una permutación inversa. En mi autocita de más arriba cuento cómo Sherlock Holmes utilizó la frecuencia relativa de las letras para encontrar el significado oculto tras unos símbolos que parecían garabatos de niño. Sin embargo, yo usé una técnica algo más sofisticada y que dará pie a varias entradas que irán apareciendo en los próximos días según refine el método y establezca vínculos que no todos esperaréis. En particular, usé una técnica probabilística bastante conocida:

  1. Asociar a cada permutación de caracteres una determinada probabilidad de ocurrencia
  2. Buscar aquella permutación que maximiza dicha probabilidad; es decir, la de la máxima verosimilitud.

Si s es una permutación dada de letras, le asigné la probabilidad de ocurrencia

P(s) = \prod_i M( s(c_i), s(c_{i+1}) )

donde c_i son los caracteres que conforman la cadena que quería desencriptar y M, una matriz de transición. (Nota: abusaré del lenguaje y diré que P es una probabilidad aun cuando no lo es propiamente: debería dividir por una constante normalizadora para que la suma \sum_s P(s)=1; pero el que no sea posible o práctico calcular dicha constante no altera para nada el resto de la exposición).

En efecto, en español, dada una letra, existe una probabilidad dada de que le siga una letra determinada. Por ejemplo, a la q casi siempre (si no siempre) le sigue la u. Después de una hache suele haber una vocal. Etc. Combinaciones como zy o bf son mucho menos probables que za o ba respectivamente.

Con mi definición de probabilidad, penalizo aquellas permutaciones que dan lugar a concatenaciones exoespañolas (es decir, inhabituales en el discurso en español).

Para construir M utilicé un texto que tenía a mano, el Quijote, y lo procesé de la siguiente manera:

quijote <- readLines( "http://www.gutenberg.org/cache/epub/2000/pg2000.txt", encoding = "UTF-8" )
tmp <- sapply( quijote, function(x) strsplit(x, ""))
tmp <- do.call( c, tmp )
tmp <- tolower(tmp)
 
tmp[ tmp == "á" ] <- "a"
tmp[ tmp == "é" ] <- "e"
tmp[ tmp == "í" ] <- "i"
tmp[ tmp == "ó" ] <- "o"
tmp[ tmp == "ú" ] <- "u"
 
tmp <- tmp[tmp %in% letters]
names(tmp) <- NULL
 
b <- as.factor(tmp)
 
b.from <- b[-length(b)]
b.to   <- b[-1]
 
res <- tapply( b.to, b.from, table )
res <- do.call( rbind, res ) + 1
 
res <- res / rowSums(res)

El objeto res que crea es dicha matriz de transiciones (mirad la fila q, por ejemplo).

Para calcular la probabilidad asociada a una cadena utilicé la función

m <- res
 
markov <- function( x, m ){
	sum(log( m[ cbind(x[-length(x)], x[-1] ) ] ) )
}
 
p.0 <- markov( cadena, m )

En muchos contextos, existen vías ya muy transitadas para maximizar probabilidades: piénse en los mínimos cuadrados en problemas de regresión, etc. En nuestro caso, tendríamos que explorar el universo de permutaciones, calcular la probabilidad asociada a cada una de ellas, etc. No existe método de Newton-Raphson o similar en este caso. Pero sí que se puede utilizar una técnica no particularmente recomendable pero suficiente en este caso:

  1. Comenzar con una permutación
  2. Construir otra a partir de la anterior
  3. Comparar las probabilidades de ocurrencia de ambas
  4. Descartar la menos probable e iterar

En particular, a partir de una determinada permutación, se puede generar otra seleccionando al azar dos posiciones de la permutación e intercambiándolas. Así se puede navegar el espacio de permutaciones en busca de la, con suerte, óptima.

Esto es lo que hace el siguiente pedazo de código (no particularmente bien pulido):

while( TRUE ){
	cadena.alt <- factor( cadena )
	cambiar <- sample( nlevels(cadena.alt), 2 )
	levels.alt <- levels( cadena.alt )
 
	char.tmp <- levels.alt[cambiar[1]]
	levels.alt[cambiar[1]] <- levels.alt[ cambiar[2] ]
	levels.alt[cambiar[2]] <- char.tmp
 
	levels( cadena.alt ) <- levels.alt
 
	cadena.alt <- as.character( cadena.alt )
 
	p.1 <- markov( cadena.alt, m )
 
	if( p.1 > p.0 ){
		print( c(p.0, p.1) )
		cadena <- cadena.alt
		p.0 <- p.1
		print( cadena ); flush.console()
	}
}

Y si alguien se molesta en ejecutarlo verá cómo al cabo de unos segundos aparece en su pantalla un texto relativamente legible y cuyo contenido, realmente, es irrelevante para los más de nosotros.

Sorprendente, ¿verdad?

4 comentarios sobre “Desencriptando (I): el problema de un mal amigo

  1. sergiojsj 22 mayo, 2012 12:51

    Una sugerencia que supongo que en este ejemplo no tiene mayor importancia, pero como tu blog suele tener espiritu didáctico. Como algoritmo de optimización algo más eficiente podría usarse el simulated annealing que es esencialmente el que has descrito pero que permite cambios a configuraciones con menor probabilidad de existencia con una probabilidad exp(-\Delta p /T) donde T es un parámetro que juega el papel de la temperatura de un sistema físico y que se va enfriando paulatinamente. Esta implementado en la función optim de R

  2. datanalytics 22 mayo, 2012 13:01

    @sergiojsj Llegaré, llegaré a algo «parecido» a eso. De todos modos, la intención de esta serie de entradas no es la optimización sino algo un poco distinto. Pero si tienes el código para hacer esa optimización, ¿podrías pasárnoslo al resto?

  3. sergiojsj 22 mayo, 2012 13:17

    Si tengo algo de tiempo intentaré escribir un código que resuelva este problema al modo que el «Numerical Recipes in C» el problema del viajante. Es decir usando el algoritmo de simulated annealing y permitiendo 3 movimientos básicos en el cambio de permutación: la inversión de 2 caracteres, el despazamiento de un segmento de texto y la inversión de un segmento. Pero no prometo nada que mi tiempo libre es escaso y las obligaciones familiares elevadas

Los comentarios están desabilitados.