Kriptópolis

56 comentarios sobre Kriptorreto Huffman (caja blanca)

• 

  Más códigos

  Agustín
  30 Noviembre 2010 - 11:33pm

  Eliminando los códigos que aparecen tres veces consecutivas, y dando varias pasadas de Gran Recursión, obtengo 24 códigos. No sé cómo estará la cosa. Les voilà

  1110 10010 11001 111111 00101 00001 01000 0001 01111 11000 01001 0110 0101 111110 11110 101 10001 0011 00000 10011 01110 10000 00100 1101

  por orden de aparición. Sus frecuencias son:

  111111 208
  101 147
  0011 147
  01111 141
  1110 133
  0001 129
  01001 105
  11001 101
  0101 97
  11110 97
  10011 94
  10010 84
  00101 76
  0110 75
  111110 75
  00001 73
  10001 65
  01000 64
  11000 64
  1101 61
  10000 61
  00000 59
  01110 56
  00100 48

  Como ya no obtengo caracteres con ocurrencias triples, el procedimiento no puede continuar de manera automática. Habrá que deducir de sus frecuencias cuáles son los códigos "bastardos" Puede que sea útil ver las frecuencias de las ocurrencias dobles, que son las siguientes:

  0001 11
  101 11
  0101 9
  0011 9
  10011 9
  10010 7
  01001 6
  10000 6
  111111 5
  00101 4
  10001 3
  1110 3
  0110 2
  01000 2
  00100 1
  01111 1
  11000 1
  11001 1

  Me preocupa que el código 111111, firme candidato a ser el espacio, presente cinco ocurrencias dobles.

  Hasta aquí he llegado.

Terminación
SkAsI
1 Diciembre 2010 - 12:06pm
Ya que estáis haciendo un trabajo tan espectacular. ¿Por qué no os atrevéis a hacer textos? Me explico, ya que teneis códigos, porque no hacer la sustitución monoalfabética y ver qué textos salen.
Agustín: ¿Por qué te preocupan las ocurrencias dobles del espacio? Seguro que DEDDS que ha visto el código puede darte una respuesta informada acerca de eso.
Kriptosaludos.

Ya lo probé
Agustín
1 Diciembre 2010 - 3:39pm
Y sale un churro con palabras kilométricas que, evidentemente, no son correctas. El asunto es que si no son correctos todos los códigos, los caracteres correctos pueden no estar en su sitio.
Lo que necesito saber -aunque sea una pista quizá demasiado fuerte- es si en esa lista hay al menos 20 códigos correctos. A partir de ahí podríamos empezar a plantearnos cuáles son los códigos ilegítimos.

Al César
DEDDS
1 Diciembre 2010 - 1:04pm
lo que es del César. El que ha visto tu código no soy yo, sino lucho.krp y por lo tanto a él le corresponde el mérito.
La "respuesta informada" para Agustín es que las apariciones dobles del espacio se corresponden con la pareja "espacio" + "\n" (retorno de línea) o con la pareja "\n" + "\n". En román paladino, "nuevo párrafo".
Un saludo.

Vale
Agustín
1 Diciembre 2010 - 6:55pm
Gracias por recordarme la info. Cuando la leí en su día entendí que esa duplicación sólo se daba al final del cifrado.
Aún así, me salen otros 17 códigos que duplican, unos más que otros, cuando en castellano sólo pueden duplicar -que yo sepa- 6 letras [R L C N E O], una más que otras. Estoy convencido de que cuando se disponga de los códigos correctos, las falsas duplicidades desaparecerán.
A ver si se os ocurre algo.
• 

  7 bits

  DEDDS
  30 Noviembre 2010 - 2:02pm

  He trabajado un poco con la hipótesis de códigos de 7 bits (el espacio se representaría como [1111111]) y un fragmento del principio del texto me quedaría de la siguiente forma:

  1110 1001 01100 1111111 0010 1111111 1110 0000111100100000010111111101100001001011001010000 1011111 1111111 1110 0000111100100000010111111101100001001011001010000101 1111111 0010 1111111

  Las dos ristras de códigos largas están así porque aún no tengo muy claro como dividirlas. Por lo demás, coincido con Agustín en los códigos de 4 bits.

  A título de curiosidad, he encontrado otro "chorizo" inmenso que se repite dos veces:

  11100110011111110100111110000111111111111110100010001110010111111110010011100111111110111100011101100110001111111

  Persevero despacito :)

  Un saludo.
• 

  Resultado parcial

  Agustín
  30 Noviembre 2010 - 3:22am

  La Gran Recursión ha petado -sí, como suena-. Pero antes ha soltado estos dieciséis códigos como candidatos. Espero que ninguno sea prefijo de otros, que a estas horas ya no veo ná.

  00000 00001 0001 0010 0011 0100 0101 0110 0111 1001 101 110 1110 11110 111110 111111

  De éstos, a mi entender, son buenos los cortos: 101 y 110, que han superado todas las pruebas mientras iban cayendo algunos de cuatro bits. También son buenos los largos: 111110 y 111111, que no pueden ser prefijos de nadie. "Pero podrían ser sufijos de los nuevos", me diréis. Ahivalahostia, pues también es verdad.

  El algoritmo ya lo he ido contando a lo largo de este foro. Se basa en ir formando códigos, primero de 3 bits, luego de 4, etc., de forma arborescente y recursiva. Se van almacenando con la condición de que no sean prefijos ni sufijos de los ya almacenados. Para salir de ese bucle infernal, se calculan las frecuencias de cada uno de los encontrados, y si superan el valor máximo esperable para el carácter más frecuente -el espacio-, para la longitud de código procesado, se eliminan -y se regresa en la recursión-. ¿Y cómo sé yo la frecuencia del espacio? Pues estimando el número de letras del mensaje, a razón de 4 con algo bits/letra, y con la longitud media de las palabras del castellano que es, creo, de unas 4 con algo letras/palabra.

  Serán muy bienvenidas las correcciones que me hagáis. En esto y en lo demás. La idea es que un código malo puede estar repetido muchas veces, como parte de otros. Por ejemplo, el 0000 puede estar en 00001, en 10000, 100001, etc.

  Ya me estoy enrollando, pero es que el problemita se las trae. Bueno, pues cada vez que quitas un código sospechoso, se abre la posibilidad de encontrar otros. Por ejemplo, al rechazar el código 0000, se pueden añadir el 00000 y el 00001, que él tenía bloqueados, como prefijo de ellos que es.

  Pero llega un momento en que falta texto, o la frecuencia de los códigos ya no es relevante para decidir si son buenos o malos. Por cierto, sigue pareciendo que el 111111 corresponde al espacio.

  Ahora necesitaría saber qué códigos de 4 o de 5 bits son malos.

  Y todo ello partiendo de que sólo hay códigos de 3,4,5 y 6 bits.

  ¡Socorrooooo!

  P.S.
  El orden de aparición de los códigos es

  1110 1001 0110 0111 11110 0101 111111 00001 0100 110 0001 0010 00000 111110 0011 101

Gran trabajo
SkAsI
30 Noviembre 2010 - 1:12pm
Estás haciendo un trabajo magnífico, ahora sí parece que los códigos van por buen camino. Siento no estar colaborando ni como atacante ni como padre de la criatura como debiera, pero tengo otras obligaciones ahora mismo que me lo impiden. No obstante, espero poder atacar dentro de poco.
Kriptosaludos.
• 

  ¿Resuelto?

  Agustín
  29 Noviembre 2010 - 2:41pm

  No estoy seguro, porque no sé si parto de premisas válidas. Suponiendo -a partir de cierta información de WikiLeaks- que los códigos tienen longitudes entre 3 y 6, la Gran Recursión aplica las restricciones de prefijos y sufijos, y tiene en cuenta la frecuencia de los códigos para descartar algunos demasiado repetidos. Así se obtiene la siguiente lista:

  0000 00001 000010 0001 00010 000101 0010 0100 0101 01010 01011 010111 0110
  0111 01111 011111 1001 101 1011 10111 101111 110 1110 11100 111001 11110
  111100 111110

  No esperaba obtener los 28, porque era posible que ni la K ni la W estuvieran en el texto.

  Si esto fuera verdad, el camino a seguir sería rutinario; pero antes de emprenderlo me gustaría que el padre de la criatura diera alguna opinión. Te advierto que a más de uno lo han enchironado por abandonar a su criatura.

:(
SkAsI
29 Noviembre 2010 - 3:41pm
No sé bien cómo lo has hecho aún, pero lo que sí sé es que no es la solución. Primeramente porque veo prefijos repetidos, así que ni siquiera la lista de códigos es válida a nivel de algoritmo Huffman, porque no se podría codificar un mensaje con esos códigos, pero mirando la solución (como si de una tarjeta de Trivial se tratara) y tampoco es parecida.
Como veo que la intención es buena, te diré que todos y cada uno de los elementos del alfabeto aparecen en el texto claro, por si te sirve de algo ya que has hecho mención en tu comentario.
Kriptosaludos.

Tienes razón
Agustín
29 Noviembre 2010 - 5:50pm
Hay códigos prefijos de otros, cachislamar. No sé cómo se me han colado. Volveré a la carga.
Gracias por la info.
• 

  Bueno

  Agustín
  28 Noviembre 2010 - 12:37am

  Ya veo que la ingeniería social no ha sido suficiente. Pues yo estoy con la Gran Recursión. Pero se me resiste.

  *********
  Reedición
  *********

  Se resiste. Y se resistirá. Hay problemas insalvables en la toma de decisiones de cuánto mide un código. Hay que seguir con los tanteos. Por cierto ¿hay alguien en ello? ¿Hay alguien en algo?

  SkAsI, me temo que has ganado. Así sabrás lo que se siente cuando te abandona el calor de tu público. Hala.

Y dale
DEDDS
28 Noviembre 2010 - 9:41pm
Mira que estás negativo, ¿eh, Agustín?
Como tu bien dices hay que ir tanteando, y eso lleva su tiempo.
Creo que Infosniper financiaba vacaciones con una enfermera y no me acuerdo que tipo de camisa especial ;)
Un saludo.

No estoy negativo
Agustín
29 Noviembre 2010 - 2:50am
Es que soy negativo. Ya sabes que un pesimista es un optimista bien informado.
Bueno, pues la Gran Recursión ha hablado. Basándose en la restricción de sufijos y prefijos, y en algunas cosillas más, ha encontrado los siguientes códigos:
0000 0001 001 010 011 100 101 110 1110 11110 111110 111111
Puede que encuentre alguno más, porque aún sigue buscando y, tal como está programada, no creo que termine nunca. Pero, aquí entre tú y yo, sospecho de alguno de los códigos cortos, ya que aceptados éstos, impiden la entrada de otros de los que serían prefijos. Si consiguiéramos eliminar alguno de ellos, aparecerían los que faltan. ¿Alguna idea?
De todas formas, me encantaría que el Jefe les echara un vistazo. Y dijera algo, claro
**********
Reedición
**********
Llamando a Lucho.krp ... Llamando a Lucho.krp ...
Me gustaría mucho que desarrollaras tu idea, para eliminar los códigos cortos erróneos. Eliminando el 0000 obtengo los trece siguientes (aparecen el 00000 y el 00001):
00000 1110 100 101 111111 00001 010 011 001 0001 111110 110 111
Debería haber alguna forma de deducir cuáles son los cortos malos, pero no se me ocurre
• 

  Una idea

  Lucho.krp
  26 Noviembre 2010 - 10:15pm

  Mirando el árbol que se genera en el caso de la caja negra (con la clave HUFFMAN), noto algunas particularidades:

  • todos los posibles códigos de 5 bits que comienzan con 1 están usados (asignados a alguna letra)
  • de los de 6 bits, están los primeros posibles (es decir, los menores, empezando del 000000 y subiendo)
  • de los de 4 bits, ídem (excepto que no está el 0000)
  • de los de 5 bits que no empiezan en 1, aparecen los mayores posibles

  La idea es que la naturaleza del algoritmo de Huffman puede dar alguna pista acerca de qué códigos son posibles y cuáles no. Y eso puede ser muy útil a la hora de "cortar la longaniza". Por ejemplo, el hecho de que esté armado de derecha a izquierda (y de que el 1 corresponde a las ramas derechas) puede explicar algo.
  Haciendo la misma prueba con claves más largas (de entre 30 y 50 dígitos), también aparecen patrones, aunque no tan fáciles de interpretar. Pero hay algo que parece mantenerse: nunca aparece el mayor código posible (6, 7 u 8 unos seguidos, según el caso). Entonces, si (ahora en este reto) el espacio es 1111111 (7 unos), eso significa que tiene que haber seguro códigos de 8 bits (hasta acá, nada demasiado novedoso). Y más: todos ellos empiezan con 100xxxxx o con 000xxxxx (esto es una conjetura difícil de explicar, pero surge de probar y ver que de los códigos más largos se usan los menores, contando todos los bits menos el primero, que puede ser 0 o 1). Si es así, podemos descartar cientos de códigos por imposibles (101xxxxx, 110xxxxx, 111xxxxx, 001xxxxx, etc., asumiendo que no hay de 9 bits), lo que puede ayudar a desambiguar ciertos trozos.
  De todos modos, lo veo muy lejos de poder ser aplicado, pero creo que es una punta...
• 

  Bug

  Lucho.krp
  25 Noviembre 2010 - 3:28pm

  Creo haber encontrado lo que menciona SkAsI: su sistema codifica el salto de línea (\n) como un espacio (línea 50 del código py). Si esto es cierto y también lo es que el último caracter es 111111, entonces el 111111 corresponde al espacio...

Muy bien
DEDDS
25 Noviembre 2010 - 10:49pm
Una información valiosa, si señor.
Sin embargo, yo me inclino a pensar que los dos últimos caracteres ocupan 14 dígitos, divididos en dos grupos de 7 (os advierto que sin ninguna razón aparentemente lógica)
1011111 1111111
En ese caso el espacio se representaría por [1111111], que al ser el final del texto creo que sería más lógico pensar que es un salto de línea.
Voy a ver si avanzo un poco más con esta suposición.
Un saludo.

Bravo
Agustín
25 Noviembre 2010 - 9:56pm
Muy bien. Eso será muy importante para el descifrado.
De todos modos, cuando esto termine -si termina-, SkAsI, me gustaría que pusieras un cifrado sin estas "ayudas", para poder probar su fuerza verdadera.

No hay problema
SkAsI
26 Noviembre 2010 - 9:51am
Si quieres más guerra, tendrás más guerra. No obstante esta "ayuda" no ha sido gratis, DEDDS ha tenido que "bucear" en mi código (que no estaba precisamente limpio y aseado) para encontrarla, así que un viva por él.
Kriptosaludos.

A buen entendedor...
SkAsI
25 Noviembre 2010 - 6:15pm
pocas palabras bastan... ;)
Kriptosaludos.
• 

  Una pregunta

  DEDDS
  25 Noviembre 2010 - 2:38pm

  Esta va dirigida a ti, SkAsI. Al ir intentando localizar secuencias de códigos empezando por el principio del texto, me he encontrado con que la secuencia

  1111111111000001111001000000101111111011000010010110010100001011111

  está repetida dos veces y además una a continuación de la otra. Como no creo que represente la letra "R" ni la "L" la pregunta es si el fichero origen que nos has dado es realmente así.

  Un saludo.

Fichero origen
SkAsI
25 Noviembre 2010 - 6:18pm
El fichero está generado con el mismo script que tenéis a vuestra disposición, directamente y sin cambios. Ahora cabe esperar un análisis más profundo de tu hallazgo, curioso de cualquier forma. Aunque puede ser una coincidencia de esto de los 0's y 1's.
Kriptosaludos.

Sin acritud
DEDDS
25 Noviembre 2010 - 10:54pm
No me gustaría que vieras ironia, sarcasmo o mala leche en mi pregunta. Es simplemente que me ha sorprendido un poco la coincidencia dada la longitud de la cadena.
De todos modos gracias por la información, porque ahora sabemos que ambas cadenas se subdividen de distinta forma ;)
Un saludo.

Disculpa...
SkAsI
26 Noviembre 2010 - 9:49am
si has atisbado alguna de esas características en mi anterior comentario. No me lo he tomado a mal, aunque releyendo mi comentario si puede parecer algo seco. Ánimo ;)
Kriptosaludos.
• 

  Paciencia

  Lucho.krp
  24 Noviembre 2010 - 5:55pm

  Aunque desde las sombras, yo también estoy participando (o eso intento). Me permito matizar y disentir con algunas de las cosas que se dijeron hasta acá.

  Creo que solo una clave MUY larga, siempre que sea legible en algún idioma (y sepamos en cuál), debilita al sistema. En el sentido de que le "transmite" las frecuencias: el espacio, la E, etc. (en español), tendrán los códigos de menos bits. Pero una clave mediana o arbitraria (es decir, que no necesariamente respete las frecuencias del idioma), resuelve el inconveniente. A menos que SkAsI haya elegido como clave una página entera del Quijote (cosa que dudo), no intentaría por ahí el ataque.
  De todos modos, cada vez me parece que obtener la clave solo sería un mínimo avance... Porque el problema parece ser el de dónde empieza una letra y termina otra. Si tuviéramos el alfabeto, ¿sería computable en un tiempo razonable un algoritmo que pruebe distintas combinaciones hasta dar con algo legible? Supongo que sí, pero a mí me excede. Pero en el caso de que allí resida la potencia del cifrado, este sistema podría mejorarse. Un sistema que asignara códigos binarios de longitudes variables a las letras (de un modo dependiente de alguna clave) alcanzaría. Usar el algoritmo de Huffman es un caso particular, y no el más efectivo (porque no genera códigos de tan diversas longitudes), de hacer eso...

  Por último, no estoy de acuerdo con Agustín en su apreciación de que el sistema cifra y comprime (o podría hacerlo pasando a ASCII grupos de código). Este uso del algoritmo de Huffman puede no comprimir, según el caso. Además, genera un cifrado donde se usan varios bits por letra, por lo que da un mensaje por lo menos 4 o 5 veces mayor que el original. El recurso de agrupar partes y convertirlas en elementos menores es otra cosa, que, además, es aplicable (mediante la elección de algún método de sustitución) al resultado de cualquier cifrado (más fácil cuando este es binario, claro).

Coincido, y no
Agustín
24 Noviembre 2010 - 6:59pm
Coincido en lo del papel de la clave en las frecuencias. Pero lo de

Además, genera un cifrado donde se usan varios bits por letra, por lo que da un mensaje por lo menos 4 o 5 veces mayor que el original.
no lo pillo. Precisamente, si para un carácter se necesitan 4 bits, habida cuenta de que para representar un carácter en la transferencia de ficheros se suele emplear el código ASCII, que requiere 8 bits, pues el ahorro es del 50%. Algo menos, porque habrá que comunicar también los códigos.
Por otra parte, te aseguro que ni DEDDS ni yo estamos intentando averiguar la clave del mago. Tan solo buscamos una cosita....¡dónde c. termina el primer p. código!
Por otra parte, bien venido al combate. Ya puedes ir buscando repeticiones de cadenas de bits. Y si hablas C, échale un vistazo al código maligno del Maligno.

Estoy de acuerdo.
DEDDS
25 Noviembre 2010 - 12:10am
El objetivo (al menos de momento) no es intentar localizar la clave, sino intentar convertir los códigos a texto (legible o no). Esto requiere, como dice Agustín, saber cual es el subconjunto de códigos que tenemos que utilizar.
El algoritmo que propone Agustín me parece un poco salvaje. Yo he pensado en otro sistema que a lo mejor da algún resultado. Se basa en el "chiste" de SkAsI del primer y el último elemento. Yo concretamente he empezado por el último elemento, que tiene un chorizo de 12 1's (111111111111). Es muy improbable que sea un solo código de 12 dígitos. Podría ser una letra de 6 dígitos repetida, o una letra de 4 dígitos "tripitida", pero la verdad es que me sorprendería un texto que terminara de esa forma. Eso nos deja solamente una opción, y es que algunos de los 1's de más a la izquierda pertenecen al final de otro código. Si conseguimos averiguar cual es, tendríamos las dos letras (codificadas, claro) del final del texto. La hipótesis que hago es que ese par de letras no será único en el texto, es decir, se repetirá una o más veces, asi que voy ampliando la cadena y mirando a ver si se repite en otro lugar del texto.
[0111111111111] está 12 veces
[10111111111111] está 6 veces
[010111111111111] está 4 veces
[1010111111111111] está 2 veces
[11010111111111111] ya no se repìte, por lo que supongo que ya no vale.
A partir de aquí habría que ir viendo que ocurre en el texto (de 0's y 1's) cuando elegimos una u otra opción. Lo importante es que, esté donde esté en el texto, el "1" de más a la derecha marca el final de un código.
Quizá lo mismo sería aplicable al primer elemento, aunque aún no lo he probado. ¿Alguien se anima?
Un saludo.

Máquina
Agustín
25 Noviembre 2010 - 1:50am
Eres una máquina, DEDDS (por qué no se me habrá ocurrido a mí mirar el maldito último código). Lo que me fastidia es que no te hayas aplicado con toda tu fuerza sobre ACYNOS..., que diga, ejem, estábamos hablando del Huffaman. Pues es muy interesante, porque si hemos de creer a SkAsInSkI, la longitud máxima de los códigos es 6, y no se me ocurre ninguna posibilidad de justificar esos 12 1s que no sea la de un doble 111111, salvo que aceptemos que pueda haber tres letras iguales consecutivas, cosa que en castellano no se da, que yo sepa. Si parte de la ristra procediera del penúltimo código, habría que asignarle al último una longitud mayor de 6, en contra de las informaciones filtradas por el señorito. Por otra parte, no es imposible que una palabra -la última del texto- termine en una letra repetida, aunque no es frecuente. Tenemos las formas verbales, presente de indicativo 3ª persona singular: "provee", "sobresee", y del modo subjuntivo todos los verbos terminados en "ear", como "acarrear" ("acarree"). Aunque no se me ocurren ejemplos para las otras letras duplicables (R, L, C, N, O). Pero el gestor del reto no está obligado a terminar la última palabra, ni a empezar la primera. Es un truco muy empleado por los profesores de criptografía en sus ejercicios: "ugar de la Mancha de cuyo nombr", y se quedan tan panchos. Quiero decir que la última palabra inacabada puede ser "acción", "hallaba", etc.
Concluyendo:
1. Has encontrado un código 111111
2. El código 111111 pertenece al conjunto de letras [R L C N E O]
3. No existen los códigos prefijos 111, 1111 ni 11111, que, doquiera que estén, serán parte de otros códigos, bien por delante, bien por detrás. No es lo que estáis pensando.
No está nada mal, para empezar. Y eso le vendrá bien al algoritmo recursivo, si es que alguna vez llego a escribirlo.
Bravo DEDDS (por qué no se me habrá ocurrido mirar el puñetero último código. Quizá ya es hora de dedicarse a la petanca) En tus manos lo dejo. Ya, si eso, me llamas cuando quieras algo.
(No te asustes de que haga afirmaciones tan atrevidas, es que así el señorito se verá obligado a decir cosas como: "No, no, no. Yo no he dicho eso", o "No, no he hecho así las cosas". Ingeniería social, le llaman ahora. Tirar de la lengua, se decía en mi pueblo)

No es C, es Python
SkAsI
25 Noviembre 2010 - 10:13am
No sé de dónde se ha sacado Agustín que el código está escrito en C, cuando en realidad es Python del de toda la vida. Eso por lo pronto.
Ahora con los avances. DEDDS ha hecho grandes avances gracias a lo que todo el mundo interpretó como un chiste, cuando en realidad era una pista-perogrullada. Bravo. Justo la pista que os daba del bug en el algoritmo va por esa línea, no me extrañaría que se descubriera pronto, y con eso ... ya casi estaría resuelto todo.
Ahora voy con otro dato que veo que no habéis mencionado y que seguro ayuda (recordad que participo en calidad de atacante también). No hay que perder tiempo buscando todos los códigos, sino que es mejor tener 1 código, partir el criptograma por las ocurrencias de este código y volver a empezar sabiendo más puntos donde empiezan y acaban los códigos.
Kriptosaludos.

Mira por dónde
Agustín
25 Noviembre 2010 - 1:46pm
No sé de dónde se ha sacado Agustín que el código está escrito en C, cuando en realidad es Python
Pues de tres fuentes:
1. De no haberlo mirado
2. De no recordar de otros retos, que tú usabas Python
3. De tener el mismo dominio sobre ambos lnguajes
Ya me di cuenta de que habías soltado pistas sobre el final del texto; pero no antes de que DEDDS lo señalara.
partir el criptograma por las ocurrencias de este código y volver a empezar sabiendo más puntos donde empiezan y acaban los códigos.
A mí eso no me parece nada fácil. La ocurrencia 111111 (en realidad 111111111111) es nítida al final, creo yo. Tabién lo sería al principio; pero en medio del texto queda enmascarada por las diferentes posibilidades de corte para los códigos anterior y posterior.
He aquí una secuencia de 111111 con su contexto, en algún lugar del código cifrado:
110100|111111|0010011
11010|011111|10010011
1101|001111|110010|011
puede considerarse "repartida" de diversas maneras entre el código anterior y el posterior.
Otro ejemplo. El cifrado empieza con:
11101001011001111111001011111111110000011110
donde encontramos sendas secuencias de 7 y 10 1's
Como ya sabemos que el código 111 no puede existir, para el primer código podríamos hacer cortes como los siguientes:
1110|1001011001111111001011111111110000011110
11101|001011001111111001011111111110000011110
111010|01011001111111001011111111110000011110
Y, para cada caso, caben varias posiblidades de separar el segundo código, y el tercero, etc. No hay modo exacto de asegurar ni de localizar un código 111111 en esa zona.
Una secuencia de 12 1's puede garantizar la presencia de un código 111111, pero no su exacta ubicación, porque también caben diversas particiones de los códigos del entorno:
1100010110|111111|111111|000010100
110001011|011111|111111|1000010100
11000101|101111|111111|11000010100
1100010|110111|111111|111000010100
entre otras numerosas posibiliddes.
O sea, que nos veo a todos embarcados en la Gran Recursión, je, je. Ya la tengo bastante pensada. Pero como sabéis, desde que uno concibe un algoritmo hasta que rueda un programa, puede pasar un largo período.
• 

  Vacaciones

  DEDDS
  24 Noviembre 2010 - 9:35am

  Querido amigo Agustín: creo que necesitas unas vacaciones urgentemente :)
  No te puedes rendir todavia porque no llevamos ni 20 comenentarios, asi que a tomárselo con calma y vamos pasito a pasito.

  Con la clave "mediana" esa que te has sacado de la manga, yo obtengo la misma codificación que tú. Te la pongo.

  [A:011] [B:000110] [C:000101] [D:11001] [E:101] [F:01000111] [G:000100]
  [H:110100] [I:11011] [J:0100001] [K:0100000] [L:00001] [M:110001] [N:00000]
  [O:1001] [P:01001] [Q:110000] [R:1000] [S:0101] [T:1111] [U:1110]
  [V:0001111] [W:01000110] [X:01000101] [Y:01000100] [Z:0001110] [_:001] [Ñ:110101]

  Me parece muy buena idea buscar cadenas largas de unos. También podemos buscar cadenas largas de ceros y también podemos buscar otro tipo de cadenas que se repitan con cierta frecuencia, por ejemplo la que correspondería con la palabra "_que_" (con sus espacios al principio y al final.

  Pero despacito, ¿eeeeehhhhhhh? que ya sabes que yo soy un poquito lento para esto.

  Un saludo.

Ah, y gracias
Agustín
24 Noviembre 2010 - 11:48am
Gracias por lo de "querido amigo". No creas que no se valoran estas muestras de afecto a estas alturas de la vida, querido amigo.

Bueeeno
Agustín
24 Noviembre 2010 - 11:45am
Te haré caso, pero que conste que lo veo muy crudo.
Me parece biene tu idea de buscar cadenas repetidas. Se podría hacer una estadística de las cadenas de 3 bits en adelante. A lo mejor habría que ampliar hasta 24, para "cazar" trigramas que, en algún caso, podrán estar formados por tres códigos de 8 bits ¿o habría que considerar también los de 9? Las más cortas no serán muy significativas, creo yo, porque podrán corresponder a códigos o a fragmentos de códigos. Pero, en general, me parece una línea muy interesante. También me gustaría conocer tu opinión sobre el algoritmo recursivo que propuse en mi post anterior.
• 

  Un momento

  Agustín
  24 Noviembre 2010 - 1:55am

  Aún queda una esperanza, aunque no creo que a mí me sirva. Mantengo mi rey tumbado, pero expongo un algoritmo, a ver qué os parece

  1. Aceptemos que los códigos miden entre 3 y 8 bits.
  2. Generamos todos los códigos posibles desde 0 hasta 11111111.
  3. Tomamos 3 bits del mensaje cifrado para formar el primer código
  4. Eliminamos todos los códigos de los que es prefijo
  5. Tomamos otros 3 bits para formar el segundo, etc.
  6. Seguimos con la secuencia 3, 3, 3... hasta que tengamos menos de 28 códigos disponibles, entonces se para la secuencia y tomamos el escalón anterior, 3 ,3, .. 4
  7. Seguimos las secuencia 3, 3, ... 4, 3 ,3

  Cada vez que se fracasa, se vuelve al escalón anterior

  En algún momento estaremos probando secuencias como
  3, 3, 5, 4, 3
  Además, si los códigos formados no están disponibles, se rechazan, probando otro de longitud superior.

  Es una recursividad bestial que, en algún momento nos podría llevar a revisar la longitud del primer código, con lo que la secuencia volvería a empezar:
  4, 3, 3,...

  Las restricciones de de los códigos disponibles reducirían drásticamente las dimensiones de la explosión combinatoria pero, aparte de la dificultad de programar esto, que a lo mejor a vosotros no os parece tanto, ¿pensáis que esto es computable en un tiempo aceptable?
• 

  Pavor y desolación

  Agustín
  24 Noviembre 2010 - 1:09am

  He encontrado en el cifrado dos grupos de 15 "unos" consecutivos, y estaba a punto de afirmar triunfalmente que había un código 111111 -ya ves tú qué descubrimiento-, cuando me he dado cuenta de que en el ejemplo que he puesto también aparecen códigos de 7 y de 8 bits. No es que esto dé una nueva dimensión al problema, sino que hace que los ilusos nos demos cuenta de la imposibilidad de resolverlo. A razón de unos 4 bits/carácter, nos enfrentamos a un problema morrocotudo, con unas 2600 letras codificadas con grupos de entre 3 y 8 bits, y ni eso es seguro. El ir probando con diferentes longitudes del primer código, y luego con las del segundo, etc. es un problema de 5^2600. Pero aunque nos conformáramos con tratar un centenar, ya sería inabordable.

  A menos que a alguien se le ocurra algo, yo me rindo. Enhorabuena, SkAsI, no se podía esperar menos de ti. Lo que siento es que la diversión haya durado tan poco o, como se dice, t'has pasao. Bueno, ha valido la pena, porque hemos aprendido el Huffman ése.

  P.S.
  La debilidad de la clave larga, que puse al principio, es una tontería. Lo único que quería decir es que si la clave es larga -y legible-, las frecuencias de las letras se parecerán más a las del idioma, y podríamos imaginar que las letras más frecuentes, incluyendo el "espacio", tendrán códigos más cortos, probablemente de 3 letras. Y ya está.

  P.S.II
  Para que los cifrados no ocupen tanto, podrías empaquetarlos, tomando los bits de 8 en 8 y guardándolos como caracteres ASCII en un fichero binario. A lo mejor tienes que hacer un padding en el último byte, pero se puede hacer con un código que no esté en la lista. Esto haría menos visible la codificación. Bueno, supongo que esto ya lo sabes, porque imagino que formará parte de la compresión Huffman. O sea, que has inventado un cifrado que además comprime. Qué bestia.
• 

  ¿Una debilidad?

  DEDDS
  23 Noviembre 2010 - 8:00pm

  Haciendo pruebas con diferentes claves, creo haber descubierto un posible resquicio por el que atacar. Debido a la forma en la que se genera la codificación de las letras (alfabeto+clave) he visto que en todos los casos se generan códigos de 3, 4, 5 o 6 bits. Pero hay varias peculiaridades:

  - Para claves medianas, todos los códigos de 4 bits corresponden a letras que están en la clave. No hay códigos de 3 bits.
  - Las claves "000000" y "000001" no siempre existen (en contra de lo que parezca). Si aparecen quizá nos puedan dar una idea de la longitud de la clave.
  - Solamente las claves realmente largas (p.e. "externocleidomastoideos" que modifica 13 elementos) consiguen que aparezcan códigos de 3 bits, en concreto solamente dos.

  Si SkAsI ha trabajado con una clave mediana (o incluso un poquito larga) tendremos todas las posibles combinaciones de códigos de 4 bits, por lo que podríamos intentar aislarlos sabiendo que los de mayor número de bits no pueden comenzar con ellos.

  ¿Que opinais?

  Un saludo.

Sorprendido
SkAsI
24 Noviembre 2010 - 10:54am
Estoy gratamente sorprendido de todas las ideas que estáis mostrando. Yo no tenía ni idea de todas estas cosas, así que la clave que he utilizado no cumple ninguna premisa de "malignidad", ya que no me paré a pensar en las cosas que estáis poniendo ahora.
Como aporte, aunque no he llegado a desarrollarlo, podríamos volver a cosas clásicas, como repeticiones de códigos de 3, 4, 5 y 6 dígitos, para ver si hay patrones más repetidos que otros ¿espacios?. Lo que está claro es que el espacio seguirá teniendo una presencia mayor que cualquier otro código, aunque como su propio código depende de la clave, no sabemos a priori si es corto o largo.
También me gusta la idea de las ristras de 1's y de 0's, aunque como no sabemos "partirlas", no sabremos si corresponde a 111, 1111, 00111, 100, etc, o combinaciones de todos ellos.
Kriptosaludos.

Disiento
Agustín
24 Noviembre 2010 - 1:13pm
Lo que está claro es que el espacio seguirá teniendo una presencia mayor que cualquier otro código, aunque como su propio código depende de la clave, no sabemos a priori si es corto o largo.
Con todos los respetos al Mago de Ozzman, creo que a los signos más frecuentes les corresponden siempre códigos más cortos, si el árbol está bien construido. Si no fuera así no se conseguiría la eficiente compresión que el algoritmo proporciona.
¿Has oído, DEDDS? Códigos de 3, 4, 5 y 6 dígitos. Algo es algo

Códigos
DEDDS
24 Noviembre 2010 - 11:36pm
Por las pruebas que yo he realizado (con algunas claves nada más, eso es cierto) he visto que obtener códigos de 3 dígitos lleva aparejado una clave larga y por lo tanto la aparición de códigos de hasta 8 dígitos. así que no se si fiarme mucho.
Un saludo.

Disiento ^2
SkAsI
24 Noviembre 2010 - 3:47pm
Eso sería así si el algoritmo se aplicara sobre el texto, pero no es así. Se aplica sobre la clave y los códigos que se obtienen podrían conducir a un código largo para el espacio, como en el caso de la clave HUFFMAN en la que el espacio tiene código [_:01111] mientras que la F tiene código [F:0001].
El algoritmo está ideado para la compresión, pero en este reto puede no comprimir, ya que los códigos como digo se obtienen del análisis de frecuencia de alfabeto+clave y no del texto en claro que haría que se produjera dicha compresión.
No obstante, lo que apuntaba al principio se mantiene cierto. El código binario del espacio será el que más ocurrencias tenga.
PD: Para que no digáis que soy maligno, el algoritmo tiene un bug a propósito (que se puede descubrir ahora que tenéis el código fuente de la encriptación) y que he introducido a propósito para proporcionar un "gancho" para romper el cifrado. Aunque no sé si esta postdata os ayudará u os despistará.

Pistas...pistas...pistas
DEDDS
24 Noviembre 2010 - 11:42pm
La experiencia me dice que cuando el maligno creador del reto empieza a soltar "información clarificadora" en formato "voy a ver como lo digo para que parezca que estoy diciendo lo que en realidad no quiero decir, no sea que me revienten el engendro", malo...malo...malo :P
Un saludo.

Disiento^(-1)
Agustín
24 Noviembre 2010 - 5:29pm
Mi disentimiento se basaba en que la clave está supuestamente escrita en buen castellano, y en la creencia de que fuera larga, o sea formada por varias palabras. Si pones pocas palabras largas, entonces la frecuencia del espacio será baja. Sólo así podrá tener un código largo. Todo eso si el árbol está bien construido. Por lo que apuntas, ahí está el problema. A mí ya me mosqueaba la ordenación contra natura que hacías. Yo había aprendido el Huffman en la internete, y era justo al contrario. Pero comprobé que el número de bits/carácter era el mismo. Habrá que ver en el código. Lo malo es que yo no hablo C, aunque lo entiendo un poco, más o menos como el chino.

No acabo de verlo
Agustín
23 Noviembre 2010 - 11:16pm
No estoy seguro de que no haya códigos de tres bits. Con la clave ¿mediana?:
ABCDEFGHIJKLMNOPQRSTUVWXYZ_ÑESTA_VA_A_SER_LA_CONTRASEÑA_PARA_LA_CAJA_BLANCA_SEGURAMENTE_
LA_HA_PUESTO_LARGA_AUNQUE_ESO_ES_UN_ERROR_PERO_QUIEN_SABE_DONDE_GUARDA_LOS_ZAPATOS_ESTE_
HOMBRE_DE_KRIPTOPOLIS
obtengo este árbol:
[197 [116 [63 [32 [16 [8 N] [8 L]] [16 [8 [4 G] [4 C]] [8 [4 B] [4 [2 Z] [2 V]]]]] [31 _]] [53 [28 [15 [8 [4 [2 K] [2 J]] [4 [2 [1 Y] [1 X]] [2 [1 W] [1 F]]]] [7 P]] [13 S]] [25 A]]] [81 [45 [25 [13 R] [12 O]] [20 E]] [36 [20 [11 [6 [3 Q] [3 M]] [5 D]] [9 [5 [3 H] [2 Ñ]] [4 I]]] [16 [8 U] [8 T]]]]]
y estos códigos:
[A 011 B 000110 C 000101 D 11001 E 101 F 01000111 G 000100 H 110100 I 11011 J 0100001 K 0100000 L 00001 M 110001 N 00000 O 1001 P 01001 Q 110000 R 1000 S 0101 T 1111 U 1110 V 0001111 W 01000110 X 01000101 Y 01000100 Z 0001110 _ 001 Ñ 110101]
¿Qué obtienes tú con esa clave? O dime qué claves has probado tú.
El Test de Tres me da alguna o varias ocurrencias triples para todos los códigos de tres bits menos para el 011. Por ejemplo, para el 001 obtengo 6 ocurrencias. Las pongo con su "entorno":
011000100100100011
111001001001110
00110010010011110
100000100100101001
000000100100110101
111110010010011010
Quizá debería haber puesto más entorno, pero tú mismo puedes hacerlo.
¿Se puede concluir que 001 no es un código? A lo mejor se trata tan solo de dobles repeticiones, que parecen triples por el "entorno". Pero ¿No serían muchas repeticiones? Claro que también podrían no ser dobles, por el mismo problema del entorno.
Evidentemente hay varias posibilidades que obvian la repetición:
0110|0010|01001|00011
etc.
O sea, que estoy tocando el violón
A ver si se te ocurre algo, porque yo estoy más seco que una piedra.

Buen trabajo
Agustín
23 Noviembre 2010 - 8:33pm
Buen trabajo, Flannaghan. Yo estoy en lo siguiente:
1. Genero todos los códigos posibles, desde 3 hasta 6 bits, aunque coincido contigo en que quizá no haya ninguno de 3.
2. Trato de determinar la longitud del primer código -eso ya sería un gran paso- Para ello, voy a asignarle diferentes tamaños, y para cada uno de ellos eliminaré de la lista de códigos posibles, aquellos para los que el primer código sería prefijo. Es decir, si el primer código es 0011, eliminaré todos los códigos de 5 y de 6 bits que empiecen por 0011.
3. El siguiente paso es tomar el segundo código con la restricción de que esté en la lista de los posibles. A su vez, eliminaremos todos los posibles códigos que lo tengan como prefijo.
3 Seguir con el resto de códigos
La idea es que ajustando las longitudes de los primeros códigos consigamos que nos queden 28 relucientes códigos posibles, que serán LOS CÓDIGOS Si llegáramos a eso el resto estaría chupao.
Otra línea de trabajo es el Test de Tres. Si el texto está en castellano no podrá haber más de dos letras repetidas, que serían algunas de éstas: R L C N O E (aRRoz, LLanura, aCCión, iNNovación, cOOperación, provEEr). Puede que me falte alguna. Pero, a lo que iba, ningún código estará tres veces repetido. Así es como creí ver que el único posible código de 3 bits sería el 011; pero cometí el error de confundir "posible" con "verdadero". Quizá no haya ninguno de 3 bits, como tú crees. El problema del Test de Tres es que parte de los bits de la ristra triplicada pueden pertenecer al código anterior, y parte al posterior.
• 

  Desde luego

  DEDDS
  22 Noviembre 2010 - 11:43pm

  la "caja" que nos ha colocado Admin tiene un aspecto impresionante.

  Dame un respiro, Agustín, y enseguida estoy contigo ;)

  Un saludo.

Por supuesto
Agustín
23 Noviembre 2010 - 12:34am
Te contesto aquí a tu pregunta del foro anterior:
Si he entendido bien el invento, para crear las frecuencias que dan lugar al HUFFMAN no se usa el texto a comprimir, sino que se usa el combinado alfabeto+clave, ¿no?
Por supuesto, pero como no tenemos la clave, nos enfrentamos a una longaniza de 0s y 1s, sin saber dónde termnina un código y empieza el siguiente, ya que puede haber códigos de 3, 4, 5 y hata 6 bits. Los de 1 y 2 bits pueden descartarse, y de tres sólo hay uno, creo. Algo es algo, siempre que no haya metido la pata.

No es del todo cierto
SkAsI
23 Noviembre 2010 - 11:54am
que no sepas dónde termina un código o empieza otro, ya que sabes dónde empieza uno de ellos (el primero) y dónde acaba otro de ellos (el último). ;)
Kriptosaludos.

¡Muy gracioso!
Agustín
23 Noviembre 2010 - 1:07pm
Sí señor, muy gracioso. Aquí rompiéndonos los cuernos, y el señorito se pone a hacer chistes.

Pero tiene razón
DEDDS
23 Noviembre 2010 - 7:43pm
¿O no?
Un saludo.

No me refería
Agustín
23 Noviembre 2010 - 12:36am
a la caja de admin, sino al problemón que nos ha atizado SkAsI
• 1
• 2
• siguiente
• final