Occam’s
Razor
Número 5. Invierno 2010
Dirección:
David Martínez Oliveira
Editores:
David Martínez Oliveira
Fernando Martín Rodríguez
Colaboradores:
Fernando Martín Rodríguez,
Laura I. Rodríguez González, Er
Tresdé, Casper van der Guorm,
Er Che vi Gan, Er Mangante
Mengunate, er Cortaó de Yervas
Maquetación y Grafismo
Laura I. Rodríguez González
Publicidad
Occam’s Razor Direct
[email protected]
Impresión
Por ahora tu mismo. . . Si te
apetece
c2010 The Occam’s Razor
Team
Esta obra está bajo una licencia
Reconocimiento 2.5 España de
Creative Commons. Para ver
una copia de esta licencia, visite
http://creativecommons.org/licenses/by/2.5/es/
o envie una carta a Creative
Commons, 171 Second Street,
Suite 300, San Francisco,
California 94105, USA.
Consulta la página 32 para
las excepciones a esta
licencia
Editorial
Feliz 2011!
by The Occam’s Razor Team
No podía terminar 2010 sin que Occam’s Razor diera señales de vida.
Así que aquí estamos, en el límite con una pequeña revista que esperamos
os entretenga durante el pequeño “break” navideño, e intentando mantener
nuestra periodicidad de año y medio :).
Aunque la mayoría de vosotros estaréis leyendo estas líneas en 2011, lo cierto
es que este número 5 se ha terminado el 31 de Diciembre de 2010. Hemos
hecho un pequeño esfuerzo para que nuestra periodicidad, “en la práctica”, de
año y medio no se alargue más.
Este número es un poco más corto de lo habitual, pero esperamos que os
guste tanto como los anteriores. En él encontraréis, un par de artículos sobre
software y un interesante dossier sobre el “nuevo” movimiento de hardware
libre.
Las ratas de biblioteca nos introducen esta vez en el mundo de los gráficos 3D
y la realidad virtual, junto con los chicos de la cacharrería que nos cuentan
como empezar a construir un Dataglove.
En este número hemos sustituido “El Rincón de los Lectores” por una nueva
sección que hemos llamado “Comunidad”. En esta nueva sección no solo nos
haremos eco de vuestros mensajes, sino también de los eventos más intere-
santes en nuestra lista de correo y en nuestro canal de YouTube. Esperamos
veros a todos por allí.
Deseamos que la distrutéis y ....
Feliz 2011!
The Occam’s Razor
Team
Las opiniones expresadas en los artículos, así como los contenidos de los mismos, son responsa-
bilidad de los autores de éstos.
Puede obtener la versión electrónica de esta publicación, así como el código fuente de la misma
y los distintos ficheros de datos asociados a cada artículo en el sitio web:
http://webs.uvigo.es/occams-razor
3| OCCAM’s Razor
DESAFÍO CRIPTOGRÁFICO
La solución
Desvelamos “la clave” de nuestro desafío
por Fernando Martín Rodríguez
Estaba claro que tras el desafío del número
anterior teníamos que publicar la solución. Allá
va.
EL FUNDAMENTO DEL MÉTODO
Supongo que estaréis esperando a que explique qué
hace la función auxiliar que genera los dígitos (aun-
que su nombre es bastante transparente). Recordemos
el fuente:
EL PROGRAMA DESCIFRADOR
Los profesores sabemos que en cualquier ejercicio pue-
de haber diferencias grandes de dificultad según la
forma de redactar el enunciado y también según qué
apartados se pidan y en qué orden. En el caso que nos
ocupa queremos descifrar un criptograma. Lo más fá-
cil es empezar por analizar el “cifrador” y crear un
descifrador.
El cifrador eran dos funciones de matlab... repito aquí
la principal:
fu n ctio n c r i p t o g r a m a = C i f r a r T e x t o ( l l a n o , c l a v e )
r a i z = f l o o r ( s q r t ( c l a v e ) ) ;
r e s t o = c l a v e −r a i z ^ 2 ;
N = len g th ( l l a n o ) ;
f o r i =1:N,
[ r a i z ,
r e s t o , d i g i t o ] =
Di gi toDe c i m al Rai z Cu ad rad a ( r a i z , r e s t o ) ;
c f r = l l a n o ( i )+ d i g i t o ;
i f
c f r >90
c f r = ( c f r −91)+65;
end
c r i p t o g r a m a ( i ) = c h a r ( c f r ) ;
end
La línea 8 (llano(i) + digito) hace un trabajo fun-
damental. El programa obtiene una serie de dígitos
(números entre 0 y 9) y los suma al texto en llano.
Estamos suponiendo que el texto en llano son carac-
teres es ASCII y que sólo usamos mayúsculas, esto es:
llano(i) va de 65 a 90 (la condicional que sigue asegu-
ra que la suma sea circular). Visto esto parece claro
que si restamos en vez de sumar deberíamos tener un
sistema descifrador. Esto es:
fu n ctio n l l a n o = D e s C i f r a r T e x t o ( c r i p t o g r a m a , c l a v e )
r a i z = f l o o r ( s q r t ( c l a v e ) ) ;
r e s t o = c l a v e −r a i z ^ 2 ;
N = len g th ( c r i p t o g r a m a ) ;
f o r i =1:N,
[ r a i z ,
r e s t o , d i g i t o ] =
Di gi toDe c i m al Rai z Cu ad ra d a ( r a i z , r e s t o ) ;
c l l a n o = c r i p t o g r a m a ( i )− d i g i t o ;
i f
c l l a n o <65
c l l a n o = ( c l l a n o −65)+91;
end
l l a n o ( i ) = c h a r ( c l l a n o ) ;
end
Lógicamente debemos volver a tener en cuenta la cir-
cularidad.
OCCAM’s Razor | 4
fu n ctio n [ r a i z ,
r e s t o , d i g i t o ] =
Di gi toDe c i m al Rai z Cu ad ra d a ( r a i z 0 , r e s t o 0 )
s i g u i e n t e d e c im a l de una r a i z cuadrada
% Obtener e l
r e s t o 1 = r e s t o 0 ∗ 1 0 ;
r e s t o 2 = r e s t o 1 ∗ 1 0 ;
aux1 = 2 ∗ r a i z 0 ;
d i g i t o 0 = f l o o r ( r e s t o 1 / aux1 ) ;
f o r c o n t = d i g i t o 0 : − 1 : 0 ,
aux2 = aux1 ∗10+ c o n t ;
aux3 = aux2 ∗ c o n t ;
r e s t o = r e s t o 2 −aux3 ;
i f
( r e s t o >=0)
d i g i t o = c o n t ;
break ;
end
end
r a i z = r a i z 0 ∗10+ d i g i t o ;
El método funcionará si somos capaces de generar nú-
meros (dígitos) “aparentemente” aleatorios a partir de
la clave. Esto es: conociendo la clave debe ser fácil ge-
nerar la secuencia mientras que en caso contrario debe
parecer aleatoria. Como podéis deducir del nombre de
la función a mí se me ocurrió utilizar la “aleatoriedad”
de los decimales de un número irracional. De clave, por
tanto, nos vale un número entero que no sea cuadrado
perfecto.
Hemos implementado el algorit-
mo de la ráiz utilizando un par
de funciones Matlab
Fijaos que quiero los dígitos exactos, sin redondeos,
para eso utilicé el “muy olvidado” algoritmo de la raíz
cuadrada (que todos estudiamos en el colegio alguna
vez). Como todo, se puede encontrar en Internet:
Algoritmo de la raíz
Realmente esta forma de hacerlo puede tener sus “cos-
quillas”... fijaos que el método dejará de ser exacto al
mismo tiempo que la aritmética entera de matlab de-
je de serlo. En el programa, los números decimales
siempre se multiplican por una potencia de 10 para
que sean enteros pero está claro que cualquier sistema
perderá precisión al trabajar con muchos dígitos, lo
que va a ocurrir con mensajes largos.
LA SOLUCIÓN
Pues a partir del criptograma:
DWSGNGGJBVVPIWYXXKJSGHVLLPX
VHQYWYAJBTLEDNLAROLXTBGINPF
ZYJRPXUMUFCVCJTMXRDKXIFUXRW
La idea era probar por fuerza bruta hasta lograr un
texto llano coherente. Para no liarlo mucho decidí ele-
gir una clave menor que 100 con lo que no había mucho
que probar. Además, algo dentro me decía que el sis-
tema podría ser más seguro si la clave es un número
primo (je, je, esto no hacía falta adivinarlo).
Probando
llano
“CONDIEZCANONESPORBANDAVIENTOEN-
POPAATODAVELANOCORTAELMARSINO-
obtenemos
sino
un
conocido:
coherente
con
clave = 67
no
sólo
DESAFÍO CRIPTOGRÁFICO
(ver
VUELAUNVELEROBERGANTIN”
del Pirata”, poema de José de Espronceda).
Sí, sí, se eliminaron los espacios, los acentos y las eñes.
No debería ser muy difícil tener eso en cuenta... O
complicar el método para tener desplazamientos ma-
yores que 9 (agrupando dos dígitos, por ejemplo).
“Canción
LOS ACERTANTES Habíamos prometido pu-
blicar sus nombres, allá van:
Bultza (pseudónimo).
Jorge Muñoz Castañer.
Sergio Mendieta.
Enhorabuena!
Las Soluciones
Como han resuelto el problema los acertantes
Desafío Criptográfico I
enviado por Jorge Muñoz Castañer
27 de Agosto de 2009
Hola Fernando,
Pues nada... que me he puesto con el enigma cripto-
gráfico y lo he sacado. Te cuento:
Nombre completo: Jorge Muñoz Castañer
Criptograma descifrado:
CONDIEZCANONESPORBANDAVIENTOENPOPA
ATODAVELANOCORTAELMARSINOVUELAUN
VELEROBERGANTIN
Valor de la clave: 67
Una explicación breve de lo que hace el método y de
cómo lo habéis atacado:
El método coge cada carácter, su código ASCII, y le
suma un dígito de la raíz cuadrada de la clave. Al pri-
mer carácter el primer dígito y así en adelante. Si es
necesario se calculan decimales de la raíz para tener
dígitos suficientes.
Para atacarlo he usado el poco ortodoxo método de
"fuerza bruta con diccionario inteligente". Primero es-
cribí la función que desencripta un mensaje sabiendo
la clave y la dejé corriendo con enteros sucesivos como
clave. Para sacar el texto en claro inicial me centré en
la primera palabra del mensaje. Por cómo está escrito
el cifrador sólo se pueden usar en el texto letras ma-
yúsculas y cada letra del mensaje cifrado solamente se
puede corresponder con ella misma o una de las nueve
anteriores (porque se le suma una cifra). Así que la
primera palabra tenía que comenzar con U, V, W, X,
Y, Z, A, B, C o D. Probé con algunas palabras (usan-
do grep “a pelo” sobre el fichero de posibles mensajes)
hasta que di con un texto con sentido. Si llego a ver
que tardaba mucho así me habría puesto a ver los ca-
racteres posibles para el segundo carácter del mensaje
y así sucesivamente.
Aprovecho para felicitar a los redactores, editores y
colaboradores de esta revistaza (vosotros sí que sois
unas “malas bestias” ;-).
Un abrazo,
Jorge Muñoz
PD: Aprovecho y os comento algunos articulillos que
si tenéis a bien podíais trabajar para el próximo nú-
mero:
Sistemas empotrados Open Source y Hardware (Ar-
duino, por ejemplo)
Intro a las FPGAs y OpenCores
Desafío Criptográfico II
enviado por Bultza
18 de Septiembre 2009
Mi enhorabuena por la revista, vi el anuncio en barra-
punto y me ha encantado. aquí la solución:
Mensaje llano:
CONDIEZCANONESPORBANDAVIENTOENPOPA
ATODAVELANOCORTAELMARSINOVUELAUN
VELEROBERGANTIN
Clave: 67
5| OCCAM’s Razor
DESAFÍO
Comentarios de: Occam's Razon #5 2010 (0)
No hay comentarios