Ver la versión completa : concurso (criptografia)
He terminado el proyecto del criptosistema que quedó sin que nadie le hiciera caso, ahora pongo una prueba y reto para la comunidad.
Este reto, creo que se sale un poco de lo ordinario, y se necesita una buena capacidad de razonamiento. Esa prueba consiste en crear un programa capaz cde averiguar la matriz y desencriptar el archivo cripted.txt, (se aceptan soluciones parciales)
Adjunto los programas de encriptar y desencriptar junto con el código fuente y el archivo cripted.txt
La encriptacion esta basada en calculos matriciales es decir, tenemos una matriz A, y el tomamos de dos en dos letras del texto para formar varias matrices. Así vamos multiplicando A por cada una de las matrices para cifrarlas.
El proceso de descifrado es simplemente calcular la inversa de A y multiplicarla por las matrices cifradas para volver al texto original.
Reconozco que soy pésimo para explicar las cosas, pero es muy fácil averiguar algo de calculos con matrices, y sólo se necesita saber lo básico, además que uso matrices pequeñas de 2x2 porlo que con fuerza bruta no será difícil conseguirlo, si algo no está del todo claro, no duden en preguntar.
http://foros.solocodigo.com/viewthread.php?action=attachment&tid=3570&pid=9010
Ánimo
Giskard mil disculpas, yk como recordaras (supongo) yo fuí el ke dejó inconcluso el trabajo, pero fuè por problemas en mi escuela y le dejé de dedicar tiempo al programa y darle prioridad a mis materias... pero bueno trataré en estas vacaciones de reinvindicarme... aunke no entiendo del todo lo ke pides, supuestamente se trata de descifrar el archivo de txt ke incluyes en el Zip, pero eso de las matrices o la explicación ke diste me sacó de onda... bueno saludos...
Exactamente, se trata de descifrar el archivo. Viendo el código fuente y sabiendo poquito de álgebra lineal todo queda claro.
aclaro que este reto no es para aquellos con "muchas ganas de aprender", sino a aquellos que de verdad saben razonar, puesto que sólo se necesitan, además del álgebra, conocimientos básicos de c++ (borland). En cuanto termine el semestre en la univ. publicaré la solución y un tutorial.
Sinceramente dudo que alguien pueda resolver esta prueba, pero ya veremos.
Saludos
Disculpen lo idiota que puedo llegar a ser, pero de donde bajo el zip, con la prueba.
ParanoiK
15-05-2003, 19:56
Scar_T haz clic sobre el link que ha puesto Giskard y se te descargará solo.
Je jejeej, ahora si que me vi IDIOTA :D
Esta chungo, a simple vista.
El objetivo es desencriptar el texto, pero hay que adivinar la matriz 2x2 que dio a la encriptación.
Para adivinar o sacar la matriz 2x2 se puede hacer por:
fuerza bruta.
o
si os fijasteis algunos números se repiten, eso si no me equivoco quiere decir que pueden ser las dos mismas letras. PQ dos mismas letras encriptadas dan el mismo numero, o puede que sea casualidad. jejeje bueno suponemos que si un número se repite mucho, son 2 letras que van juntas muchas veces, pues entonces ya tendríamos una posible fila de la matriz. en fin, este puede ser un razonamiento válido.... ála de aqui a programarlo....uufff ke pereza.
suerte.
Yo tengo a medio hacer un crackeador por fuerza bruta, un pequeño programa que lee el fichero y prueba todas las combinaciones de la matriz posible excluyendo en las que el determinante es 0 claro esta xD Pq si no provoca un error de division por 0 :P
Lo que pasa que ahora tengo un fichero de 6 Megas xD Con todos los textos posibles xDD
Yo hice, lo mismo que tu RooT, nada mas que esto va pa largo :).
Mmmmm Giskard? Es un texto lo que hay encriptado? Es decir si solo tiene numeros y letras? Porque si es así podria descartar todos akellos textos que tengan carateres extendidos xD
|RooT|: independientemente de si hay o no caracteres extendidos no pasa del rango de ascci que es de 128, esto seguramente te ahorrará unos cuantos megas de textos posibles.
oBjEt: las sílabas más repetidas es una buena observación
Object no se si no te entendi pero pongo una semi explicacion:
El encriptador lo que hace es tomar un fichero, una matriz 2x2 (dnd introducimos los valores), y ahora esta va introduciendo en un vector de enteros los siguiente:
0---|1er char del txt * elem[0][0] + 2ºchar * elem[0][1] |
1---|1er char del txt * elem[1][0] + 2ºchar * elem[1][1] |
2---|3er char del txt * elem[0][0] + 4ºchar * elem[0][1] |
......
Por lo tanto si un numero se repite es porque se encuentran consecutivos y en posiciones pares (tomando pares 0 y 1, y no 1 y 2)
Me explico con un ej (q soy bastante malo explicandome), por ej:
Tenemos lo siguiente:
-Texto:
hola kaos, que tal kaos?
-Matriz:
[20 23]
[16 12]
Esto dará como salida al encriptar:
primera pareja---primera pareja--seg pareja---------seg pareja ....
primer num------seg num---------tercer num-------cuarto num ....
h*20+o*23------h*16+o*12-------l*20+a*23--------l*16+a*12 ....
***********************
----------Apuntes:-----------
h=104
o=111
l=108
a=97
***********************
Descompongamos pues el texto en parejas:
[ho][la][ k][ao][s,][ q][ue][ t][al][ k][ao][s?]
Dando como resultado:
***[ho]-----------[ho]--------------[la]----------------[la]
***prim pareja--primera pareja--segunda pareja--segunda pareja
***4633----------2996-------------4391---------------2892
Según lo que explique es algo asi como:
***ho--------------ho----------------la---------la ....
***4633 -----------2996-------------4391-------2892 ....
***h*20+o*23----h*16+o*12-------l*20+a*23--------l*16+a*12 ....
Evidentemente y como vemos, hay una pareja de numeros que s repiten: 4493 2884, y esto se debe evidentemente a que son la misma! xD, a*20+o*23=4493 y a*16+o*12=2884. Por eso se repiten.
Bueno espero haber aclarado algo. (Si me he equivocado en algo decidmelo plis)
Saludos, KaoS
Si teneis alguna dudilla más preguntad. (Aun sigo mirando a ver si encuentro la solucion):0=
Seria demasiado bruto probar algo así:
Probar desde la pareja de ascii 00,01,02...(128^2=16384 posibilidades) multiplicando las matrices posibles (leyendo, el numero y calculando el mayor numero que pueden alcanzar los indices de la matriz),y calculando todas estas matrices
(ej,num inicial 4000,siguiente 3400, entonces en los valores de la matriz 00 01 ninguno puede ser mayor que 4000, y tendo en cuenta el 2º, ninguno podria ser mayor que 3400)
probariamos todas las combinanciones , desde 0 0,0 0 , a 4000 0, 0 4000, en los dos primeros y 3400 0, 0 3400.
Que no tengo ganas de pensar cual es la eficiencia xD
Comprobar si alguna coincide con el numero, -> desencripte el texto con dicha matriz. E imprimir en el fichero el resultado.
Y luego realizar un depurado de los textos(por ej eleminicando los que no contengan un % de espacios).
Es algo muy raro?me he rallado mucho? weno normal son las 7:30 de la mañana y me duele el cuello xD, ale me voy a acostar.
Ns bmos
yo lo que haría sería realizar alguna suposicion, por ejemplo: coger un par de letras que se repitan mucho en castellano, o tener un diccionario de par de letras ke más se repitan, por ejemplo los pares de letras que más pueden repetirse son:
[en,de,on,er, q,...]
y generar dos numeros correspondientes a la primera fila, podemos fijarnos en las magnitudes de las cantidades del archivo cifrado juntos con las magnitudes del numero ascii de cada par de letras para intentar acotar la búsqueda de la solución.
Con esos numeros y las letras que más repiten hariamos las cuentas, obteniendo un resultado y lo comparamos con todos los numeros de las posiciones impares del archivo cifrado, si alguna cuadra suponemos que ya tenemos la 1ª fila de la matriz, por tanto podemos obtener más sencillamente la 2ª fila. Obtendriamos una posible matriz desencriptadora, hay ke comprobar ke sea la correcta...
si no es correcta habría que seguir probando.
EUREKA!!
Tomamos los 2 juegos de valores más repetidos [1805 2579] y [2252 3092] que necesariamente se tienen que corresponder con combinaciones de letras minúsculas o espacios. Probamos todas las combinaciones de estos resolviendo el sistema correspondiente que nos dará la matriz que buscamos correspondiente a esos caracteres.
[a1 b1] [A B] = [1805 2579]
[a2 b2] [C D] = [2252 3092]
Si tenemos en cuenta que los coeficientes de la matriz deben ser enteros positivos solo nos da una combinación posible:
[13 17; 19 23]
Si usamos esto en el decodificador obtendremos la frase de Aurobindo escondida.
Este codigo en matlab lo resuelve, en cuanto pueda lo pasaré a C incluyendolo en el decodificador.
COD = [1805 2579; 2252 3092];
alfa = [97:122,32];
for i = [1:length(alfa)]
a1= alfa(i);
for j = [1:length(alfa)]
b1=alfa(j);
for k = [1:length(alfa)]
a2=alfa(k);
for l = [1:length(alfa)]
b2=alfa(l);
LEG=[a1 b1 ; a2 b2];
if det(LEG) ~= 0
S=inv(LEG)*COD;
V = S > 0;
if (V == ones(2,2)) & ((S-fix(S)) < 0.01*ones(2,2))
S'
[a1 b1; a2 b2]
end
end
end
end
end
end
Hombre, enhorabuena si es esa la solucion :)
Cuanto tiempo t ha llevado dar cn ella?
Venga, salu2
KaoS
Me estuve 4 horas dándole vueltas, ha sido entretenido.
¿No teneis otro un poco más compliado de resolver?
:D Efectivamente tenemos un ganador del primer lugar.
Chan cha cha chan, :0=
No fue ferza bruta y eso tiene mérito, publicaré la solución que yo tenia, aunque es diferente