domingo, mayo 18, 2008

Solucionario al MiniReto de Criptografía por Bambú

Hola amig@s,

El minireto que nos planteó Jorge Ramió ha sido resuelto por cuatro jugadores que se llevarán 1 punto extra cada uno. Bambú, Oriol, evilteq y NitRic. Mañana os pondré el solucionario de NitRic y como va el campeonato 2008.

Saludos Malignos!

Solucionario por Bambú

1/ Calcular el tamanyo de la palabra repetida en el segundo criptograma.

#texto/31. -> 7.

2/ Observar que ese criptograma se repetia a partir del byte 105(creo).

Lo cual nos dice que la clave tambien se repite.

3/ Como el enunciado decia que el cifrado era de flujo pero no especificaste nada al respeto hize algunas suposiciones. Supuse que el texto claro(Rn) se cifraria con XOR con un "stream" de bytes clave(Kn) y que ese tambien podia ser ciclico.

El criptograma ciclico seria el siguiente :

(R1+K1) (R2+K2) .... (R7+K7) (R1+K8) (R2+K9) ... (Ra+Kn) (Rb+K1)
(Rc+K2) ... [[ a = n/7%7 ]]

// Cada () es un byte real del criptograma, compuesto por el XOR de dos bytes

Si n fuera multiplo de 7 estariamos observando un ciclo de n en el texto cifrado con lo cual queda descartado.

Haciendo autocorrelaciones con XOR obtendremos el tamanyo de la secuencia K cuando encontremos una cadena de 7 caracteres repetida indefinidamente; las K se anularian y solo obtendriamos una sucesion de R descorreladas :

(Rb+K1) (Rc+K2) ....
+(R1+K1) (R2+K2) ....
=(R1+Rb) (R2+Rc) .... (R7+Rh) (R1+Rb) (R2+Rc) ...

Lo cual obtenemos cuando hacemos la correlacion con 15 espacios de diferencia. Es decir la longitud de Kn es 15 [15*7=105] :-) i b=2.

I la secuencia que hemos obtenemos es :

(R1+R2) (R2+R3) (R3+R4) ... (R7+R1) (R1+R2) ..

Cuando llegamos aqui es cuando solo nos falta una informacion para solucionarlo todo, R1, y con el obtendremos R2, R3 y toda la palabra.

Haciendo un bruteforce con los 255 candidatos observamos directamente 'pasi???' como la solucion mas probable.

Con 'pasi???' obtenemos directamente Kn y con ellas conseguimos el mensaje original directamente.

No hay comentarios:

Publicar un comentario