Juan Daniel Castrellon Botero – 201729285
Criptoanalista
1. Que encontró luego de correr cada uno de los archivos cifrados
y no cifrados.
En primer lugar, veamos que ocurre con cada uno de los algoritmos.
- Don Quijote
Bare Caesar Vigenere
- Essays
Bare Caesar Vigenere
- Hamlet
Bare Caesar Vigenere
- Kritik der reinen Vernunft
Bare Caesar Vigenere
- La Divina Comedia
Bare Caesar Vigenere
- Les crimes de l’amour
Bare Caesar Vigenere
- Os Lusiadas
Bare Caesar Vigenere
En primer lugar, cabe notar que en todos los casos solo aparecen ciertos
caracteres ASCII, esto se debe a que los textos solo consisten en caracteres
alfanuméricos, por lo que no se tienen en consideración aquellos caracteres
como espacios, o signos de puntuación. Una vez aclarado esto, vemos que,
en primer lugar, los textos planos tienen picos de las letras que son más
usadas dentro de este texto, los cuales, debido a la longitud de estos,
podemos decir que son característicos del idioma en que se escribieron. Estos
corresponden a las palabras más usadas.
Por su lado, respecto al cifrado caesar, nos damos cuenta de que todos
corresponden a la misma distribución, con la diferencia de que tiene un shift.
Esto tiene sentido, puesto que este tipo de cifrado tiene una llave que indica
cuantos caracteres adentro del alfabeto es necesario correr para obtener el
texto cifrado, por lo que lo único que se está haciendo es cambiar los
caracteres más usados por otros.
Por último, respecto a Vigenere, nos damos cuenta de que este es el mejor
cifrado de los tres. En general, vemos que la mayoría de la mayoría de los
caracteres está repetida una misma cantidad de veces. Aun así, nos damos
cuenta de que siguen existiendo picos en la distribución de caracteres. Esto
se debe a que, si se está usando una clave que se debe reusar para cifrar
bloques, esto genera que ciertos caracteres sean más vistos. Dada la longitud
de los textos, es posible encontrar estos patrones y picos dentro de la
distribución del cifrado de Vigenere.
2. You have classic works written in Spanish, English, German,
Italian, French and Portuguese. Write your insights about the
statistic distribution of the characters in every language in the
bare files.
- Ingles
Frankenstein Dracula Pride and Prejudice
En este caso, obtuve los textos del proyecto Guttenberg, y con ayuda de un
script en Python, fue posible convertirlo en el formato bare.
Desafortunadamente, solo encontré obras en inglés. Aún así, nos damos
cuenta que todas las distribuciones son prácticamente iguales. Por lo tanto,
podríamos concluir que este sería una serie de “Huella Dactilar” del idioma.
3. How the frequency distribution changes in the associated
encrypted Caesar file?
Como se mencionó en la pregunta 1, la distribución de caracteres no cambia
en si cuando se cifra con caesar. Lo único que ocurre es que esta distribución
tiene un “shift”.
4. How the frequency distribution changes in the associated
encrypted Vigenère file?
Como se mencionó en la pregunta 1, la distribución de caracteres cambia
considerablemente, y los caracteres pasan a tener una frecuencia bastante
similar. Aun así, seguimos encontrando picos en la frecuencia de palabras,
esto se puede dar debido a que es necesario cifrar por bloques con la misma
clave, por lo que esta repetición termina causando que existan caracteres que
se repitan más que otros.
5. What about the ∏ number? What is the statistic distribution of
the digits in pi?
En este caso, vemos que todos los dígitos de pi se repiten aproximadamente
en la misma cantidad del 1 al 9, siguiendo una distribución uniforme.
6. What did you find? Is there any relationship between the
frequency distribution that you find in the questions 2, 3, 4 and
5 and the entropy values that you are calculating now?
- Don Quijote
Bare: Caesar: Vigenere
Entropy: 4.0294 Entropy: 4.0294 Entropy: 4.6219
Coincidence Index: 0.6879 Coincidence Index: 0.6879 Coincidence Index: 1.1104
- Essays
Bare: Caesar: Vigenere
Entropy: 4.1320 Entropy: 4.1320 Entropy: 4.6439
Coincidence Index: 1.7716 Coincidence Index: 1.7716 Coincidence Index: 1.0756
- Hamlet
Bare: Caesar: Vigenere
Entropy: 4.1881 Entropy: 4.1876 Entropy: 4.6439
Coincidence Index: 1.7290 Coincidence Index: 1.6651 Coincidence Index: 1.0756
- Kritik der reinen Vernunft:
Bare: Caesar: Vigenere
Entropy: 4.0204 Entropy: 4.0200 Entropy: 4.6180
Coincidence Index: 0.0792 Coincidence Index: 0.0710 Coincidence Index: 0.2432
- La Divina Comedia:
Bare: Caesar: Vigenere
Entropy: 4.0127 Entropy: 4.0127 Entropy: 4.6600
Coincidence Index: 1.1079 Coincidence Index: 1.1079 Coincidence Index: 1.0500
- Les crimes de l’amour:
Bare: Caesar: Vigenere
Entropy: 4.0019 Entropy: 3.9965 Entropy: 4.5837
Coincidence Index: 2.1031 Coincidence Index: 2.0279 Coincidence Index: 1.1593
- Os Lusiadas:
Bare: Caesar: Vigenere
Entropy: 3.9710 Entropy: 3.9710 Entropy: 4.6421
Coincidence Index: 1.9772 Coincidence Index: 1.8982 Coincidence Index: 1.0807
Como se ve, en general el texto plano y el cifrado caesar tienen entropías e
índices de coincidencias bastante similares. Esto tiene sentido, puesto que las
distribuciones de caracteres no están cambiando, y estos pequeños cambios
se pueden deber al uso de floats dentro de los computadores. Por su lado, los
textos cifrados con vigenere tienen, en general, una entropía más alta y un
índice de coincidencia más bajo. Esto tiene sentido, puesto que la entropía de
shanon es mayor si la distribución se parece a una distribución uniforme, lo
cual se cumple. Aún así, este valor no alcanca el máximo debido a los picos
que existen, esto nos indica que el cifrado de Vigenere es más difícil de romper
que el Caesar. Por su lado, el índice de coincidencia está relacionado con la
probabilidad de que, al seleccionar dos caracteres, estos sean iguales. Este es
muy alto si la distribución no es uniforme.
Por su lado, estudiando el idioma ingles con las obras seleccionadas:
Frankenstein Dracula Pride and Prejudice
Entropy: 4.1697 Entropy: 4.1764 Entropy: 4.1825
Coincidence Index: 0.8789 Coincidence Index: 2.6272 Coincidence Index: 1.0337
Como se ve, los índices de coincidencia son diferentes entre sí. Aun así, la
entropía en los tres casos es la misma, por lo que se podría decir que existe
una relación entre el idioma de un libro y la entropía de este, siendo esta una
especie de “huella dactilar” del idioma.
7. What about the entropy of the ∏ number?
Como podemos ver, el número pi tiene una entropía de 3.3220 y un índice de
coincidencia de -0.1890. En primer lugar, teniendo en cuenta que la máxima
entropía de una variable aleatoria de 10 elementos es de 3.3219, podemos
ver que la entropía es más alta, esto se puede deber a los errores en las
variables. Aún así, vemos que pi tiene una distribución uniforme, significando
que la probabilidad de obtener dos números iguales de forma aleatoria es
relativamente baja.
8. Read about the coincidence index and its applications in
cryptanalysis. Write your insights about the coincidence index in
every file in the requirements 3 and 4.
Este es un índice que nos indica que tan frecuente es seleccionar dos letras
iguales de un mensaje. En general, los índices de coincidencia más bajos
suelen ser atribuidos a las distribuciones uniformes. De esta forma, dado un
mensaje encriptado, se podría esperar que su índice de coincidencia esté entre
el respectivo a una distribución uniforme con n caracteres y el del lenguaje
que se está usando para cifrar. En caso de un cifrado perfecto, el índice de
coincidencia debe ser en teoría el mínimo, haciendo imposible llegar a
conclusiones.
Este índice fue usado por William F. Friedman, y fue muy usado con el fin de
romper con el cifrario de vigenere. La forma en que se usaba es que se podía
organizar el texto en una matriz, y obtener el índice de coincidencia de cada
columna. En general, el índice de coincidencia será el mayor si el ancho de la
matriz coincide con la longitud de la llave que se usa para encriptar el
mensaje, lo que otorga pistas al criptoanalista de la longitud de la llave.
En general, lo encontrado en el punto 6 tiene sentido respecto a lo esperado,
puesto que el cifrario de vigenere hace que el texto se comporte siguiendo
una distribución más uniforme, por lo que tienen que disminuir respecto al
cifrario de caesar y al texto plano. Aún así, este no alcanza el mínimo para un
alfabeto de 26 caracteres, por lo que el cifrario puede ser desencriptado.
9. Download a significant amount of random bits from the web site
[Link] Run entropy and byte count
over the file. Compare results.
En este caso, se usó el generador aleatorio de número hotbits con el fin de
generar un archivo de bits aleatorios con 2048 bytes de longitud. El resultado
es el siguiente:
Como se ve, y era de esperarse, la distribución es aproximadamente uniforme.
Los picos se generan debido a las desviaciones, pero, de ser posible generar
infinitos números veríamos que se tendería a llegar a la distribución uniforme.
Asimismo, respecto a la entropía, vemos que esta es de 7.9028, siendo la
mayor entropía de una variable con 256 opciones 8 (siendo esta la respectiva
a una distribución uniforme). De esta forma, nos damos cuenta que la entropía
también nos indica esta distribución de bytes es aproximadamente uniforme.
10. What did you find? How much redundancy does the Drosophila
has in its DNA?
- AA142155:
- AC092241:
- Aa140963
- AA181842
- AA141840
- DMU43733
- AA140659
- AC006073
- AA264347
- All genes combined:
En primer lugar, cabe decir que la entropía máxima para una variable aleatoria
de tamaño 4 es de 2. Habiendo dicho esto, vemos que en todos los casos
tenemos una entropía un poco menor a dos. Esto se explica por el pequeño
desbalance que hay en el número de cada nucleótido posible. En general,
podemos ver que la adenina y timina suelen aparecer de forma más seguida
que el resto. De esta forma, podemos ver que, en general una molécula de
ADN se puede escribir de tal forma que únicamente haya 2 bits
aproximadamente. Asimismo, el índice de coincidencia nos dice que, en
general, el ADN tiene mucha redundancia, por lo que elegir aleatoriamente
dos nucleótidos iguales tiene una probabilidad muy alta
11. I wonder if any cryptanalyst have looked at that junk DNA to see
if it's a message from the designer. I'm guessing that it's a code
that says something like, "I am Kaloopah, from the star system
Nebulon IV. I have sent this evolution program into space as my
eighth grade science project". What do you think?