Por LlamameX
Dada la estrepitosa (y previsible) caida de Fractal1, os presento a Koch (o Fractal2). Un algoritmo que espero sea bastante más terrible que el anterior y que creo mucho más elegante...
Cifrado Koch (fractal)
En la primera versión del cifrado fractal (Fractal1) se intentó centrar su fortaleza en la variabilidad de las diferentes Ki, que se obtendrían recursivamente (aunque la implementación fue lineal). Sin ellas quedaría en una simple codificación por sustitución y atacable por análisis estadístico. El caracter recursivo de su generación, sin embargo, exigía que la misma fuera una función caótica, es decir, que pequeñas variaciones de las condiciones iniciales (la K1) implicaran fuertes variaciones del resultado final.
Este objetivo, sin embargo, quedaba lejos de alcanzarse con Fractal1. La generación a partir de las Bi creaba un doble cifrado que acababa aislando la K0 y convergía independizando el resultado de la clave inicial, con lo que el único parámetro relevante era la longitud de la misma. Dicho parámetro era fácilmente obtenible por análisis de las frecuencias.
Para resolver esta situación podría mejorarse la generación de las claves mediante el uso de funciones caóticas pero entonces se estaría trasladando la fortaleza del cifrado a dicha función en lugar de a la recursividad, que era el propósito inicial del proyecto.
Para conseguir un cifrado seguro que no dependa de un algoritmo fuerte de generación de claves se opta por sustituir la función recursiva. Por simplicidad y eficacia de cálculo se elige una función sencilla, la que genera la fractal conocida como la curva de Koch (o copo de nieve de Sierpinsky). La función recursiva sería:
trazar(N) {
girar (0); trazar(N-1);
girar (alfa); trazar (N-1);
girar (-2*alfa); trazar (N-1);
girar (alfa); trazar (N-1);
}
A efectos de codificación la función de giro se implementa como rotación de la Ki siendo esta rotación la única modificación de dicha clave. Así, un giro de n grados positivos se implementa como el desplazamiento de n posiciones a la izquierda. Se establece también la longitud de clave como la unidad mínima de trazado. De esta manera descenderemos por la recursión hasta dicha unidad mínima que se trazará (codificará) con la clave girada (rotada) correspondiente a esa posición de la curva.
En este punto queda claro que debe dotarse al criptosistema de alguna fortaleza añadida, puesto que de codificarse simplemente así bastaría con "desdoblar" la curva para obtener un cifrado de sustitución simple y atacable estadísticamente.
Para obtener fortaleza incluimos los siguientes mecanismos:
- Profundidad variable: A partir de una profundidad mínima (p) en la curva que pueda contener toda el texto plano de longitud LT (es decir LT<=LC*4^P) prefijamos a que profundidad se trabajará. Para ello sumamos a P el índice de la última letra de la clave, es decir un valor entre 0 y 37.
- Posición inicial variable: En lugar de empezar a codificar por el primer tramo posible, se empieza a codificar a partir de una posición arbitraria. En este caso se ha usado la suma de los índices de todos los valores de la clave multiplicado por LC. Podemos asumir un factor de incremento de la dificultad de hasta 38*LC^2 derivado de este concepto.
- Ángulo variable: En lugar de girar un ángulo alfa fijo usamos el índice del primer carácter de la clave como ángulo. Esto nos ofrece un factor 38 añadido a la dificultad de ataque
Con estos tres mecanismos obtenemos un número de posibilidades de codificación derivada de la recursividad igual a 38^3*LC^2, que con una LC de 20 dígitos equivale a 2*107 posibilidades, cada una de ellas a analizar estadísticamente. Obviamente no son en absoluto cifras inabordables para un ataque de fuerza bruta, aunque ofrece la seguridad suficiente para ilustrar el concepto.
Si se desea pueden añadirse nuevos mecanismos que dificulten el ataque, como incluir un ángulo beta en el primer giro, un número arbitrario de giros en el trazado o hacer depender los parámetros de los sistemas anteriores de magnitudes con un rango de valores superior. Otras curvas fractales pueden ofrecer también un mayor número de parámetros con los que multiplicar la complejidad del ataque.
Aunque no es parte del objetivo del proyecto, en la implementación se ha mantenido una posible evolución de las Ki tal y como se utilizó en Fractal1. Como mejora al concepto se permite también su generación con una función caótica. Puede constatarse que usar simplemente dicha evolución adolece de las mismas carencias que ya aparecían en el cifrado anterior.
En definitiva en esta prueba de concepto se muestra un cifrado que maximiza la entropía con variaciones máximas de un 0.4% entre las frecuencias de aparición de los caráctares. Todo ello sin emplear técnicas homofónicas, aleatoriedad ni generar inflación en el texto final. En contrapartida requiere cierta potencia de cálculo para textos grandes imposibilitando tanto el cifrado como el descifrado manual.
Texto cifrado con Koch (Ki no evolutiva, p variable, alfa variable e inicio variable):
Un favor.
DEDDS22 Marzo 2011 - 10:12am
A ver si un alma caritativa me puede poner un texto cifrado con las mismas características que el original del reto. Es porque se me ha quedado el análisis un poco a medias y una vez conocida la solución ya está viciado. Ocurre lo mismo si el texto y la clave los pongo yo, y por eso es preferible que sean ambos desconocidos desde el principio.
Muchas gracias por adelantado.
Un saludo.
Ahí tienes
LlamameX22 Marzo 2011 - 11:48am
Muchísimas gracias
DEDDS22 Marzo 2011 - 12:35pm
:)
SEÑOR_CEANO
AgustínB22 Marzo 2011 - 8:57am
No es exactamente la clave, tengo que encontrar la pequeña variación, pero no me olvido de terminarlo completamente.
Me falta poner la V y la B, pero ahora no tengo tiempo. A ver si esta tarde al regresar del trabajo.
Un saludo
Agustín
SEÑOR_CEANO, si que era la clave de Fractal 2
AgustínB24 Marzo 2011 - 10:22pm
Me contesto yo mismo.
Parece que igual me dejé sin marcar alguna de las opciones y no me lo descifró correctamente.
He pasado unos días con bastante trabajo y poco tiempo para mirar esto.
Ahora me pongo un poco más y sigo pensando que sí que era la clave la pruebo y funciona. Todo descifrado correctamente.
No sé lo que me pasó el otro día pero los primeros 11 caracteres si que salían correctamente pero después ya se trastocaba todo.
Igual también fue por tocal algo al depurar con firebug el javascript pero bueno ya está todo finalizado.
El ataque
AgustínB20 Marzo 2011 - 10:58pm
Bueno, antes de nada decir que este aspirante a agente de la TIA, que no llega ni a botones Sacarino, y sí más bien a operario de la empresa de Pepe Gotera y Otilio; no ha hecho otra cosa que aprovecharse del trabajo de mi tocayo y de DEDDS que corroboraban que la clave era de 11 caracteres.
Es por eso que si admin quiere repartir los puntos, por mí puede hacerlo.
La verdad es que estaba leyendo el reto pero no me decidí a participar hasta que se dijo lo de los puntos. Además se perdió conectividad con la página de ejemplo y yo la había descargado pero no la había usado. Es que como había dicho, estaba intentando pensar por donde hincarle el diente a ACYNOS, y todavía no tengo ni idea.
Bueno, entonces ya viendo que casi se confirmaba que la clave era de 11 caracteres; yo me puse a jugar a cifrar el texto de ejemplo con distintas claves y descifrarlo variando ligeramente la clave después de haber cifrado.
Estas pruebas las hice sin marcar ninguna de las opciones ni Profundidad variable, ni Ángulo variable, ni tampoco Inicio variable.
Con esto, pude observar que los números al final de la clave parecen perjudiciales ya que si se descifraba con MALETA456 o MALETA789 o incluso 123MALETA producían un descifrado que contenía parte del texto original.
Como las opciones marcadas lo que hacían era desplazar los alfabetos, presupuse que probar con algunas palabras podría generar parte del texto.
Dicho y hecho, ahí me pongo manos a la obra en plan chapucero total.
Después de evaluar algunas otras herramientas de pruebas de páginas web que conozco, me decido por utilizar iMacros.
Con esta herramienta, automatizo la pruebas en local de la página web para probar distintas claves. Se podría haber hecho directamente con javascript, pero por no matarme me pareció más sencilla esta opción.
¿De dónde saco las claves?, pues otra vez aprovechándome de un enlace de mi tocayo que proporcionó un lemario para poder atacar ACYNOS.
Lo paso a una base de datos, y me creo unas consultas para obtener palabras primero de 8 letras (porque presupuse que igual había tres nº). Al fallar con la primera suposición me decido a seguí con 7, luego 11 (tampoco), sigo con 9 y finalmente con 10.
A todos ellos les añadí caracteres para completar los 11, desde _123 a ninguno (la palabras de 11 caracteres). A las de diez le puse sólo _
Por si os interesa, en el lemario hay
Para agilizar las pruebas, descifraba sólo los 44 primeros caracteres del texto cifrado proporcionado.
En cada bucle, recogía el texto descifrado para el análisis posterior.
El primer bloque de 8 caracteres, me lo pateé completo para ver si había algo a simple vista. Para los siguientes ya me centré en buscar los trigramas más comunes del castellano.
QUE - Muy difícil que apareciera en los primeros 44 caracteres.
EN_
ES_
ENT
y finalmente el que dio sus frutos
EST
Cifrando con estas nueve claves
DESENFOQUE_
DESPARRAMO_
DINAMITAZO_
SAGAZMENTE_
SEDENTARIO_
SINAMAYERA_
SOBREFUNDA_
SUPERVIVIR_
VIÑAMARINO_
Se obtenías además de EST, ciertas palabras identificables a simple vista.
Poniendo todas las líneas una a una del texto descifrado, empecé a componer trozos de texto hasta encontrar los que he comentado.
Y aquí está el ataque chapucero!!!
Lo dicho, que si admin me quiere rebajar y/o repartir los puntos por mí no hay ningún problema.
Ningún ataque es chapucero
LlamameX22 Marzo 2011 - 10:37am
si produce resultados. Es sencillamente efectivo.
Bueno, ya que hemos llegado hasta aquí os cuento las cosas que le veía a Koch implementado como lo hice. Como dije algunas facilidades las conocía y las dejé adrede para que el reto fuera asequible, ameno y didáctico.
En primer lugar estaba claro que codificar por segmentos y encima de longitud fija era una debilidad, puesto que permitía diversos ataques. Esto ya lo demostro fractal1. Si se descubría fácilmente Koch quedaba muy expuesto. En cualquier caso esa longitud iba a ser corta ya que si no quedaba muy evidente la frecuencia de deterinados carácteres en los segmentos.
La codificación por sustitución simple también era una fragilidad asumida. Ahí radicaba la fuerza del concepto. Si a pesar de usar una codificación trivial la "fractalización" conseguía añadir complejidada suficiente demostrábamos la potencia del sistema. En la misma línea tenemos la generación del alfabeto por compresión de la clave, que deja muchos carácteres adyacentes y es poco sensible a las repeticiones de letras en la misma (AAAAB genera el mismo alfabeto que ABBBB).
Dentro de lo no previsto (aunque previsible) que detecté posteriormente (vosotros también aunque no lo habeis usado directamente), fue que los ángulos de los segmentos 1 y 4 eran, por definición, exactamente los mismos. Eso hace que la codificación sea la misma en ellos. Aunque la profundidad de la recursividad y el punto de inicio no sean conocidos, es de esperar encontrar este patrón muy repetido a lo largo del texto, aumentando la longitud del texto atacable.
Como dije no esperaba que cayera tan pronto la longitud de clave. Esperaba que tuvierais que usar algo de fuerza con ella, ya que era ahí donde confiaba que Koch fuera más resistente. Sin embargo tenía los pies de barro.
Ya podeis intuir como puede fortalecerse el algoritmo si se le quiere dar un uso más serio. Algunas ya las apuntaba en la presentación y otras ya las podeis suponer por lo comentado antes:
Ahora estoy liado con Acynos y con otras ideas locas de las que algún día tendreis noticias, pero posiblemente habrá un Koch Reloaded en un futuro. Si de mientras alguien se anima ahí teneis el código para enredar.
Gracias
Agustín22 Marzo 2011 - 2:23pm
Gracias por tu amable referencia a ACYNOS
¿Chapucero?
DEDDS21 Marzo 2011 - 1:41pm
Si a lo que has hecho le llamas ataque chapucero, no quiero ni pensar el apelativo que le pondrías al mio ;)
Un saludo.
De chapucero, nada.
Agustín21 Marzo 2011 - 12:28am
Es un ataque como debe ser, con imaginación, combinando todos los conocimientos disponibles, y con algo de fuerza bruta, y con mucha tenacidad e ingenio. Me alegro de haber contribuido, junto con DEDDS, por lo menos a establecer el número de letras de la clave.
Lo que más me gusta de estos Sudokus, como les llaman algunos, es que reina el espíritu de equipo, que cada uno presenta lo que descubre, y no se lo guarda para sí mismo, y que cuando alguien logra el triunfo, todos nos sentimos felices, incluso el desafiante. No he viajado mucho por la Red, pero esto sólo lo he visto en Kriptópolis. Enhorabuena a todos.
Koch -> Game Over
AgustínB20 Marzo 2011 - 8:58pm
Todavía tengo que encontrar la clave pero con los fragmentos ya he podido deducir el texto.
Enigma 72
Hardegen y el resto de capitanes pasaban el día en alta mar a altura de periscopio mirando como los barcos de guerra americanos navegaban a toda máquina durante sus “patrullas muy agresivas”. Al caer la noche, subían a la superfície, se acercaban a la costa y sembraban el caos. Muchas veces no hacía falta ni disparar torpedos, sino que hundían los barcos solitarios con el cañón de cubierta.
etc.
La clave ha sido deducir una frase más concluyente
EL_APARATO_DE_PROPAGANDA_ _ _LA_ _INTERNACIONAL_ _DE_MANHATTAN_SACADA_SUPUESTAMENTE_DESDE_EL_SUBMARINO_CAPTUque ya me hizo suponer que se trataba de la máquina enigma. Luego una búsqueda en google y voilà, el texto original.
Sigo un poco hastga localizar la clave real.
Enhorabuena
usrdxt20 Marzo 2011 - 11:13pm
tengo que volver a releer todo el reto, pero eres un hacha, mis felicitaciones.
¡Muy bien!
DEDDS20 Marzo 2011 - 10:20pm
Un trabajo estupendo. Mi mas sincera enhorabuena.
Un saludo.
¡Bravo!
Agustín20 Marzo 2011 - 9:54pm
Bravo, tocayo. Y yo que ya estaba a punto de entender el algoritmo, mecahis.
¡¡Enhorabuena!!
LlamameX20 Marzo 2011 - 9:41pm
El texto os era cercano ¿no?
Ahora que teneis el texto, la clave la encontrareis rápidamente (aunque es lo de menos). Incluso os dareis cuenta de que me equivoqué al colgarlo, puesto que andaba con pruebas sobre como afectaba la variación de una letra y la clave tiene una cambiada respecto a la que tenía que haber sido.
Me espero a que ilustres el ataque para daros el resto de datos de por donde esperaba yo que le hincárais el diente. Por lo que íbais posteando os veia muy bien orientados y ya tenía claro que era cuestión de poco tiempo. Fieras, que sois unas fieras.
Lo que me chocó especialmente fue lo del índice de coincidencia y que cayera tan estrepitosamente con él. Eso no me lo esperaba e imagino que os abrió la puerta a un ataque más elaborado que seguro nos detallarás.
Sin duda te has ganado los puntos.
Desgranando Koch
AgustínB20 Marzo 2011 - 5:46pm
No se como váis Agustín o DEDDS pero yo ya empiezo a obtener frutos.
Creo que empiezo a tener partes del texto, pero todavía no he encontrado la clave correcta.
He lanzado un ataque por fuerza bruta y diferentes claves proporcionan descifrados similares variando alguna letra.
Saludos y seguiremos informando
Espero
Agustín20 Marzo 2011 - 7:13pm
Espero ansioso tus resultados. Yo no he obtenido nada, aparte de que he estado liado con asuntos personales.
He obtenido alguno de los alfabetos
AgustínB20 Marzo 2011 - 7:33pm
Creo que he cazado alguna de las repeticiones de un alfabeto.
Con nueve palabras que he utilizado para descifrar consigo porciones de texto legibles pero todavía no concluyentes.
Cosas como estas, aunque algunas son deducciones he igual hay algún error
EL_RESTO_DE_
_PASABAN_EL_DIA_
_CARROS_DE_GUERRA_
_NAVEGABA
_MAQUINA
PATRULLAS_
_VECES_NO_HACIA_FALTA
_LE_HABIA_MORDIDO_Y_AL_ACERCARSE_SE_
_PASARON_HASTA_LAS_NUEVE_TRANSMITIENDO_LA_
De momento no da para encontrar el texto original con el buscador :-(
Pero bueno, sigo recomponiendo.
Una idea.
DEDDS18 Marzo 2011 - 8:59am
El autor del reto nos dice que para obtener este texto cifrado se ha usado una Ki no evolutiva. Eso significa que una vez calculado el primer alfabeto por "compresión" de la clave, los restantes se obtienen por rotación de una cantidad variable tanto a derechas como a izquierdas. Pero esto supone que como máximo vamos a tener 38 alfabetos diferentes. Dado que con una clave de longitud 11 obtenemos más de ochocientos fragmentos de texto, está claro que hay fragmentos que codifican con el mismo alfabeto. Para un análisis de frecuencias, 11 caracteres son pocos, pero si pudiéramos localizar varios fragmentos codificados con el mismo alfabeto, aún cuando no fueran correlativos, podrían servirnos para realizar un análisis de frecuencias más o menos válido.
En esta dirección es hacia donde estoy encaminando mis pesquisas, a ver que sale.
Un saludo.
Buena idea
Agustín18 Marzo 2011 - 12:38pm
Te aseguro que estaba pensando en lo mismo, pero como no acabo de pillar el algoritmo, no avanzo. ¿Los giros son siempre iguales?
No es tan sencillo
AgustínB19 Marzo 2011 - 10:21am
Al principio iba a escribir
Me temo que estáis equivocados, hay muchos más alfabetos.
Pero al repasar, pues sí ha dicho
Luego al no usar Ki evolutiva lo hace más sencillo ya que "sólo" le aplica rotaciones al alfabeto y es cierto que serán 38. Pero lo que no se sabe es el orden de dichos alfabetos y si se repiten o no, ni cuantas veces.
Haciendo una prueba sencilla con la web proporcionada podéis marcar los tres check-box (Profundidad variable, Ángulo variable y Inicio variable) y probar a cifrar un texto. Al ser de ángulo variable (en el código es la variable alfa) significa que el giro no es de 17 posiciones sino que será de x posiciones, siendo x la posición de la primera letra de la clave dentro del alfabeto base de 38 caracteres.
Y luego resulta que hace
Ki=girar(Ki,0);
Ki=girar(Ki,alfa);
Ki=girar(Ki,360-2*alfa);
Ki=girar(Ki,alfa);
El texto del Quijote del ejemplo con la clave MALETA123 produce los siguientes alfabetos/rotaciones
LC: 9
TC: 59
alfa: 12
inicio: 1206
pmax: 32
Ki=girar(Ki,0);
Ki=girar(Ki,12);
Ki=girar(Ki,360-2*12); = Ki=girar(Ki,336); = Ki=girar(Ki,336%38); = Ki=girar(Ki,32);
Ki=girar(Ki,12);
Como véis, el segundo y el quinto alfabeto se han repetido pero para conocer que esos alfabetos se tienen que repetir, habría que saber la primera letra de la clave y hacer los cálculos pertinentes.
Bueno, y ya se huele el sigiente. Marcar evolutivo y a jugar!!!!
El evolutivo no es el siguiente
LlamameX19 Marzo 2011 - 6:26pm
Eso lo descarto. Se aleja de la filosofía. La gracia es buscar la complejidad en lo fractal. Si quisiera hacerlo más terrible podría haber usado, por ejemplo, ACYNOS ;) para los cifrados de cada segmento. O al revés, aplicar variaciones fractales al alfabeto generado de ACYNOS.
Lo siguiente podría ser algo mas horrible que todo eso. Le he estado dando vueltas a un algoritmo fractal basado en el cubo de rubik a partir del interesante trabajo de principante (es su nick) aquí, donde cada elemento del cubo sería a su vez un nuevo cubo. Estoy buscando la representación adecuada de la información y de los efectos de los movimientos de los cubos en sus subcubos, pero esa ya será otra historia.
Gracias, y disculpa
Agustín21 Marzo 2011 - 12:44pm
No te había agradecido el pequeño homenaje que haces a mi pobre ACYNOS en este post. Mi despiste y mi incuria son los culpables.
Un saludo
Claro que no es tan sencillo
DEDDS19 Marzo 2011 - 2:34pm
Si lo fuera posiblemente ya habría caido. Pero seguro que si nos estrujamos un poco las meninges, damos con la forma correcta de sacudirle al texto cifrado.
Un saludo.
En ello estamos
AgustínB19 Marzo 2011 - 4:26pm
Pues eso, que en ello estamos (por la boca muere el pez, he abandonado temporalmente ACYNOS porque esta versión parece más asequible)
No quiero adelantar nada porque igual resulta que se queda en otra chorrada como la que comenté el otro día.
Mirror de Fractal 2
AgustínB17 Marzo 2011 - 10:45pm
Bueno, como os prometí he creado rápidamente aquí una réplica de la web de LlamameX.
Está creada en estos servidores http://www.000webhost.com/ y ya ni me he parado en la seguridad ya que se puede navegar y ver todo el contenido.
Al zip original le he añadido el fichero koch.txt que contiene el texto a descifrar.
Y ahora paso a mirar las pruebas de ayer que me parece que algo está mal.
Saludos
Muchas gracias
DEDDS18 Marzo 2011 - 8:35am
Como ya dije, a mi también se me pasó bajarme los ficheros.
Un saludo.
Gracias tb
LlamameX18 Marzo 2011 - 1:08am
Estoy buscando otro alojamiemto ya que esta gente ni contesta y en otro lado en que me he registrado sigo esperando el mail de confirmación. Joer esto de lo gratuito es de lo más informal.
Gracias por publicarlo.
Moltes thanks
Agustín18 Marzo 2011 - 12:00am
Pues eso.
No es muy científico
AgustínB17 Marzo 2011 - 1:00am
Pero si la clave es de 11 caracteres; se me ha ocurrido probar, una a una, todas las combinaciones de letras del alfabeto repetidas once veces.
Con esto si se observan el texto descifrado los únicos caracteres que producen cambios (observaba los 12 primeros del texto descifrado) con respecto al texto cifrado son EIOQRUV6790
Se me ha ocurrido formar la "palabra" QUIEROV6790, pero no ha funcionado el descifrado.
Buena idea
Agustín17 Marzo 2011 - 1:23am
¿Y por qué no te parece científico? A mí me parece muy buena idea. ¿Has probado otra combinación? Por ejemplo, los consabidos números en lugar de letras como "QUIER0V679O", o cualquier otra cosa. En todo caso, si tu pista es correcta, estaríamos ante un problema de 11! = 39916800
combinaciones. Eso debería estar chupao.
Tampoco es la clave
AgustínB17 Marzo 2011 - 8:58am
Tengo que repasar porque he visto que igual me he despistado con la F que también produjo cambio.
De todas maneras, no quiero jugar con ventaja y si a la tarde, después de regresar del trabajo no lo ha hecho el autos; publicaré el zip y la web en otro Hosting gratuito para que todos podamos probar.
Saludos y salgo pitando para el trabajo ;-)
Chorrada
AgustínB17 Marzo 2011 - 11:46pm
Nada, que ya decía que no era nada científico.
He aplicado la misma idea al ejemplo cpn clave MALETA123 cifrando
EN_UN_LUGAR_DE_LA_MANCHA_DE_CUYO_NOMBRE_NO_QUIERO_ACORDARME que da como resultado
THXQHXFQ2N82PQ2YN2HAIEBAYT13PA16346_9JAUDGUIÑRÑ5ZEIKZ5A9KDL Y probando con AAAAAAAAA
THXQHXFQ27 RM0AMI7MG0HDA0XS_M9TKOMNOJBMDXGJXLQEARM157MRCAMFN
La A está dos veces en la clave y tampoco cambia nada en los 9 primeros caracteres. El que cambia es el de la posición 10 (LC+1)
Luego no sirve de nada.
¡Coincidencia!
DEDDS16 Marzo 2011 - 4:28pm
Ya he averiguado como calcular el famoso "índice de coincidencia" del texto cifrado. Lo cierto es que es más o menos fácil de hacer. Para comprobar si los resultados que se obtienen son válidos, se me ha ocurrido probarlo primero con el texto cifrado de fractal1, ya que tenemos la ventaja de conocer la longitud de la clave. Los cálculos los he realizado para longitudes de clave entre 6 y 60 caracteres, aunque aquí solo pongo los que se necesitan para ver la variación.
El primer valor es el índice de coincidencia del texto completo y los valores siguientes son los que se obtienen tomando las longitudes de clave expresadas en la columna de la izquierda.
--------------------
0.040038
25 -> 0.060262
26 -> 0.056959
27 -> 0.057289
28 -> 0.057044
29 -> 0.072484
30 -> 0.057564
31 -> 0.056661
32 -> 0.057575
33 -> 0.058322
--------------------
Se puede ver como el valor es significativamente mayor para una longitud de clave de 29, que sabemos que es la correcta.
Los mismos cálculos realizados para el texto de Koch dan como resultado:
--------------------
0.026305
06 -> 0.039104
07 -> 0.042508
08 -> 0.042664
09 -> 0.045301
10 -> 0.044374
11 -> 0.058626
12 -> 0.044647
13 -> 0.043770
14 -> 0.043354
15 -> 0.043643
16 -> 0.042442
--------------------
que nos da una longitud de clave de 11 caracteres.
Como coincide con el cálculo de la longitud que ya había hecho Agustín, yo creo que podemos estar razonablemente seguros de que es la longitud de la clave correcta.
¡Hale Agustín! Pienso que ya podemos trabajar con esta hipótesis para intentar descifrarlo.
Un saludo.
Me alegra
Agustín16 Marzo 2011 - 5:59pm
Me alegro mucho de que coincidamos en la longitud de la clave. Ahora sí que empiezo a fiarme de que mida 11 caracteres. A partir de ahí veo tres líneas de ataque:
1. Estudio de frecuencias de caracteres en los fragmentos de 11 signos
2. Buscar alguna debilidad en el algoritmo, algo que el propio autor ha reconocido que existe
3. Ataque de fuerza bruta sobre la clave
El primer método lo veo inviable: Con fragmentos tan cortos las estadísticas son irrelevantes.
El segundo debería ser lo más elegante, que requerirá sin duda de vuestras habilidades matemáticas, pero no puedo decir gran cosa, porque creo que aún no he entendido bien cómo funciona el algoritmo. Por eso quería hacer unas pruebecillas en la página fantasma.
Sobre el tercero no tengo ni experiencia ni herramientas. La combinatoria dice que tenemos 38^11 claves posibles, o sea unas 2*10^17 Pero estoy seguro de que esos crackeadores de contraseñas con diccionario serían la solución. Este cifrado es vulnerable, como ya dije antes, pues las claves largas lo debilitan.
En cambio, con ACYNOS, cuanto mayor sea la clave, mejor. No es por nada, je je.
==== Edición ===
Por cierto, podrías explicar en qué consiste el método ese de las coincidencias. Me gustaría ver en qué se diferencia de mi método de las frecuencias relativas de las letras más frecuentes.
================
Claro que si
DEDDS16 Marzo 2011 - 9:10pm
Aunque yo creo que es mejor que hagas una búsqueda en google y te leas alguno de los pdf que lo definen, porque viene la formulación matemática (en unos documentos muy sencillita y en otros un poco más a lo bruto) y luego su aplicación a la criptografía.
La diferencia más notable respecto de tu método es que utiliza no solamente el caracter con más frecuencia, sino todos los caracteres que aparecen en cada fragmento de una longitud dada.
En cuanto a la forma de atacarlo, estoy de acuerdo contigo en que son fragmentos muy cortos para hacerlos por frecuencias, asi que nos tendremos que sacar de la manga otro método.
Un saludo.
¿Descortesía?
Agustín17 Marzo 2011 - 12:04am
Ya me sonó extraño que hablaras de un método de análisis sin que pusieras ni una descripción, ni un documento, ni un enlace. Pero que te lo pida expresamente y sigas sin ponerlo me parece claramente descortés, con todo lo que hemos peleado juntos, o separados por un reto. Seguramente me has tomado por un HOYGAN pidiendo HALLUDA. Pues a lo mejor lo soy, fíjate tú.
¡Mil disculpas!
DEDDS17 Marzo 2011 - 11:35am
En absoluto he pretendido faltarte al respeto a ti ni a nadie de los que esté siguiendo este reto. Precisamente por todo lo que hemos peleado juntos o separados sabes que nunca ha ocurrido eso y, por lo que a mi respecta, ni ocurrirá. Asi que de nuevo te reitero mis disculpas.
Yo entendí que me pedias una justificación formal del funcionamiento del método y sinceramente no tengo los conocimientos suficientes para poder hacerlo. Solamente me he limitado a hecer una adaptación mindungui para ver si era útil para este reto.
¿Enlaces? te pongo los que a mi me han parecido más interesantes. La mayoría llevan directamente a documentos PDF, por eso pensé que quizás preferirias cribarlos tu tras una búsqueda por la red.
es.wikipedia.org/wiki/%C3%8Dndice_de_coincidencia
www.cripto.es/enigma/boletin_enigma_32.txt
www.izt.uam.mx/contactos/n33ne/pdf/cripto.pdf
www.bubok.es/ver/preview/5714
www.fi.uba.ar/materias/6669/docs/Vigenere.pdf
www.grupocole.org/~cgomezr/patronfic/07/e/enunc/indice.pdf
Y ahora una explicación de andar por casa.
Ya que nos las tenemos con un cifrado polialfabético empecé a buscar información soble el método Kasiski, y me encontré por casualidad una mención al "índice de coincidencias". Del mozuelo que lo inventó y lo desarrolló no he conseguido mucha información. Básicamente el índice de coincidencia de un texto dado es una cantidad que se deriva de la frecuencia de distribución de las diferentes letras en el texto. El índice de coincidencia puede servir para identificar idiomas porque tiende a un valor distinto en cada idioma. Por ejemplo, los textos largos en inglés suelen tener un índice de coincidencia que ronda 1.73, mientras que en español es 1.94.
Dado un determinado alfabeto, si creamos a partir de él un texto totalmente aleatorio y calculamos el índice de coincidencias obtendremos un valor muy bajo. Pero si creamos un texto siguiendo las reglas de un lenguaje natural (por ejemplo el español) el índice de coincidencia calculado eleva su valor considerablemente. Este principio es el que se utiliza en criptografía. Si calculamos el índice de coincidencia de un cifrado polialfabético nos da un valor bajo. Pero si lo hacemos con un fragmento de la longitud de la clave el valor aumenta.
Mucho me te mo que la explicación a lo mejor ha sido un poco farragosa, pero al final se reduce a realizar los cálculos para distintas longitudes de clave. Por cierto que a posteriori he visto que ganzua tiene una opción para calcular el índice de coincidencia.
Espero, Agustín, que el tocho este sirva para lavar mi falta. Si no es así, por favor házmelo saber.
Un saludo.
Sta bene...
Agustín17 Marzo 2011 - 12:09pm
... Non ti preoccupare.
Grazie
DEDDS17 Marzo 2011 - 2:31pm
:)
Coincidencia
DEDDS15 Marzo 2011 - 10:19pm
Buscando por las internetes información sobre los cifrados polialfabéticos, me he encontrado con que al parecer hay dos formas de atacarlos: una es el método de Kasiski (que no sé que tal irá para este reto) y la otra es un sistema que se llama "cálculo del índice de coincidencia". Este último método está orientado también a intentar averiguar la longitud de la clave para, una vez conseguida, seguir el ataque por el método de frecuencias o algún otro más o menos artesanal.
De momento no he podido determinar como aplicarlo al texto del reto, pero puede ser una buena dirección a seguir.
Mi opinión (y recalco que solamente es una opinión personal) es que todavía tenemos algunas opciones antes de empezar a pedir comodines, ¿no te parece, Agustín?
Un saludo.
Por supuesto
Agustín15 Marzo 2011 - 10:50pm
Ya he dicho que no quería devaluar el reto. O sea que pasamos de comodines.
Tranqui, Agustín
DEDDS15 Marzo 2011 - 9:21am
No te agobies, que ya verás como encontramos por donde meterle mano. Yo tampoco me acordé de bajarme el famoso fichero zip con la página, asi que a lo mejor LlamameX nos puede hacer la merced de volverlo a colgar.
Un saludo.
Vale, es muy difícil
Agustín15 Marzo 2011 - 2:54am
El ataque estadístico es muy difícil, porque es como descifrar chopocientos criptogramas de once caracteres (por ejemplo). Si un criptograma es corto puede resultar indescifrable, por sencillo que sea el método de cifrado, por ejemplo, una sustitución monoalfabética. Es decir, que lo que has conseguido, a mi entender, es un ingenioso método para fraccionar el mensaje, y cifrar cada cachito con un alfabeto-clave distinto, usando el contenido del propio mensaje. Dicho sea esto sin intención de quitarle mérito alguno, porque ya digo que es muy difícil de resolver, objetivo deseado por todo paridor de engendros.
Ahora bien, desde el punto de vista teórico, es una vulnerabilidad que las claves largas sean más vulnerables -valga la rebuznancia- que las cortas, ya que éstas, a su vez, son más susceptibles de ataques por fuerza bruta. O sea, que si alguno tiene un programilla de esos que crackean contraseñas, igual lo puede aplicar a esto y ganarse seis mil eurillos, digo... seis mil puntitos. Perdona, admin, no sé en qué estaría yo pensando.
Y como estamos de acuerdo en que los retos imposibles son un coñazo... ¿te importaría confirmar o desmentir si la clave es de once caracteres?
Casi mejor que eso
LlamameX15 Marzo 2011 - 5:23pm
Usar una longitud de clave es una facilidad para el ataque. No habría costado nada hacer un giro después de cada letra y habría sido mucho más difícil abordarlo.
Mejor que confirmar o desmentir os ofrezco comodines XD
1) El Recifrado - Cifrar el mismo texto con otra clave.
2) El Traidor - Comentaros una debilidad detectada.
3) La confirmación - Os digo si 11 es o no la LC.
Ahora bien, igual si usais comodines nuestro amado Admin decide que el reto ha quedado devaluado y no os da los puntos. Vosotros direis XD
No quiero devaluar el reto
Agustín15 Marzo 2011 - 8:13pm
para que alguien pueda disfrutar de esa fortuna moral, pero si de mí dependiera te pediría que presentaras un cifrado con una clave decente, entre 80 y 100 caracteres, je, je.
Dead link
Agustín14 Marzo 2011 - 9:59pm
Quería hacer unas pruebecillas en la página que has puesto para ahorrarme la tarea de programar, pero el enlace no pirula, de nuevo. Bueno, no está muerto del todo, pero no sale la página que se espera. Como no sea que yo tenga el ordenata infectado...
Confirmo
AgustínB14 Marzo 2011 - 11:46pm
Te confirmo que no funciona. Pero también podías haber descargado el zip con el código fuente. Contenía un fichero html y otro javascript y con eso lo tenías todo para ejecutar en local en tú máquina.
Es la historia de mi vida
Agustín15 Marzo 2011 - 12:29am
Siempre dejo escapar las oportunidades
No se que ha pasado
LlamameX15 Marzo 2011 - 5:08pm
Pero parece que redirige a una página de baja reputación. Voy a pedir al admin que quite el link mientras miro a ver que pasa. Miraré de colgar los archivos mientras en otro servicio de publicación.