2015/12/29

Gravity Falls

Por motivos que no aclararé, me hallo descifrando los mensajes secretos de Gravity Falls.

If you do not understand spanish, you can ask me to translate this text to english and I will put the job in the backlog

Me basé en unos programitas en python que había desarrollado para Crypto I de Coursera, que comenzé y abandoné dos veces pues al final se pone demasiado matemático para mis capacidades. Aún así, aprendí muchísimo y no dudo en recomendarlo.

La idea es que, según me han contado, hay varios cifrados. Un Caesar(3), una substitución y según pude ver de casualidad en un mensaje, un Atbash, que viene a ser 'a' -> 'z', 'b'->'y'...


$ python GravityFalls.py
?: m
    PU. FDHVDULDQ ZLOO EH RXW QHAW ZHHN. PU. DWEDVK ZLOO VXEVWLWXWH.
    ??. ????????? ???? ?? ??? ???? ????. ??. ?????? ???? ??????????.
?: try Caesar
  1 OT. ECGUCTKCP YKNN DG QWV PGZV YGGM. OT. CVDCUJ YKNN UWDUVKVWVG.
  2 NS. DBFTBSJBO XJMM CF PVU OFYU XFFL. NS. BUCBTI XJMM TVCTUJUVUF.
  3 MR. CAESARIAN WILL BE OUT NEXT WEEK. MR. ATBASH WILL SUBSTITUTE.
  4 LQ. BZDRZQHZM VHKK AD NTS MDWS VDDJ. LQ. ZSAZRG VHKK RTARSHSTSD.

   ...

Tengo entendido que buscando en Internet se halla la tabla de la substitución pero, ¿cuál es la gracia?

Como los mensajes están en inglés, el código y la interfaz tambien.

El programa soporta sólo maýusculas e ignora la puntuación, tal como son todos los mensajes obtenidos.

Emite estadísticas de frecuencia de caracteres, bigramas y trigramas, junto con tablas de frecuencias de las mismas en inglés. Esto sirve para descubrir las tablas de substitución.


¿Unit Testing? Eeeh, si, ad hoc, al comienzo orientado a refactorización y luego derivando a TDD.

¿Performance? Bueno, hay operaciones cuestionables desde ese punto de vista, como recalcular las frecuencias al pedir su visualización sin que nada haya cambiado.

¿Arquitectura? Es como la arquitectura de un banco de plaza, es poco. Es lo más sencilla posible para que sea comprensible y expandible. Lo mencionable es el Chain of Responsability para la ejecución de los comandos y el tímido MVC. Los componentes son Model y teñido por Controller en accept() y View está completamente separado.

Sintetizando, este proyecto te puede servir para aprender o practicar:
  • criptoanálisis básico
  • inglés (mensajes, interfaz, código)
  • programación (python, patrones)
En https://github.com/cpantel/gravityFalls está el código. Sólo he comiteado lo mínimo indispensable pues en el proceso de desarrollo y refactorización he cometido pecados inconfesables y no hace falta se hagan públicos.


Detalles


El protocolo de Chain of Responsability es accept(command, [message], [...]) y la respuesta es (Bool:handled, Bool:error, String:result). Al final, Printer formatea y muestra según la respuesta.

Si se quisiera agregar un módulo, por ejemplo un algoritmo para SubtitutionCipher, habría que agregarlo colgando de él, quizás pasarle el Statistical y que devuelva un dictionary

Usé Chain of Responsability en lugar de Mediator pues tenía ganas de usar Chain of Responsability. Si hiciera falta pasar a Mediator, lo haría. Ganas pero no capricho.

Estas son las tablas de frecuencias en inglés sacadas de [practicalcryptography]

Frecuencia letras (asociada a f1)



E 12.1
T 8.94
A 8.55
O 7.47
I 7.33
N 7.17
S 6.73
R 6.33
H 4.96
L 4.21
D 3.87
C 3.16
U 2.68
M 2.53
F 2.18
G 2.09
P 2.07
W 1.83
Y 1.72
B 1.6
V 1.06
K 0.81
J 0.22
X 0.19
Z 0.11
Q 0.1

Frecuencia palabras (asociada a futura fw)


THE 6.42
OF 2.76
AND 2.75
TO 2.67
A 2.43
IN 2.31
IS 1.12
FOR 1.01
THAT 0.92
WAS 0.88
ON 0.78
WITH 0.75
HE 0.75
IT 0.74
AS 0.71
AT 0.58
HIS 0.55
BY 0.51
BE 0.48
ARE 0.47
FROM 0.47
THIS 0.42
I 0.41
BUT 0.4
HAVE 0.39
AN 0.37
HAS 0.35
NOT 0.34
THEY 0.33
OR 0.3

Frecuencia bigramas (asociada a f2)


TH 2.71
HE 2.33
IN 2.03
ER 1.78
AN 1.61
RE 1.41
ES 1.32
ON 1.32
ST 1.25
NT 1.17
EN 1.13
AT 1.12
ED 1.08
ND 1.07
TO 1.07
OR 1.06
EA 1
TI 0.99
AR 0.98
TE 0.98
NG 0.89
AL 0.88
IT 0.88
AS 0.87
IS 0.86
HA 0.83
ET 0.76
SE 0.73
OU 0.72
OF 0.71

Frecuencia trigamas (asociado a f3)


THE 1.81
AND 0.73
ING 0.72
ENT 0.42
ION 0.42
HER 0.36
FOR 0.34
THA 0.33
NTH 0.33
INT 0.32
ERE 0.31
TIO 0.31
TER 0.3
EST 0.28
ERS 0.28
ATI 0.26
HAT 0.26
ATE 0.25
ALL 0.25
HES 0.24
VER 0.24
HIS 0.24
ETH 0.24
OFT 0.22
ITH 0.21
FTH 0.21
STH 0.21
OTH 0.21
RES 0.21
ONT 0.2

Frecuencia primera letra de palabra (asociado a ffw)

t 16.671
a 11.602
s 7.755
h 7.232
w 6.753
i 6.286
o 6.264
b 4.702
m 4.383
f 3.779
c 3.511
l 2.705
d 2.67
p 2.545
n 2.365
e 2.007
g 1.95
r 1.653
y 1.62
u 1.487
v 0.649
j 0.597
k 0.59
q 0.173
z 0.034
x 0.017

Frecuencia de letras repetidas (asociada a futura fd)


LL
SS
EE
OO
TT
FF
RR
NN
PP
CC
MM
GG
DD
AA
BB

Próximos pasos

Que calcule las frecuencias de letras duplicadas.
Que calcule las frecuencias de palabras
Que calcule las frecuencias de la primera letra de cada palabra
Que calcule el patrón (véase próxima entrada en uno de estos días)

Referencias


[practicalcryptography] http://practicalcryptography.com/cryptanalysis/letter-frequencies-various-languages/english-letter-frequencies/

https://en.wikipedia.org/wiki/Letter_frequency

Frecuencia de letras repetidas y buena parte de mi instrucción tomadas de Secret History:  The Story of Cryptology - Craig P. Bauer