PDF de programación - Occam's Razon #5 2010

Imágen de pdf Occam

Occam's Razon #5 2010gráfica de visualizaciones

Publicado el 29 de Noviembre del 2019
216 visualizaciones desde el 29 de Noviembre del 2019
3,3 MB
33 paginas
Creado hace 8a (08/01/2011)
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

occams-razor@uvigo.es

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
  • Links de descarga
http://lwp-l.com/pdf16993

Comentarios de: Occam's Razon #5 2010 (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad