viernes, 23 de septiembre de 2016

Criptografía (XXXI): ¿Sabías que...? (VII)

En el post anterior de esta serie puse un ejemplo de criptograma cifrado con la clave "Bocho" en la guerra civil española y comentaba que, según algunos autores, el descifrado de esta clave y de otras dos facilitó la captura del mercante "Mar Cantábrico" por parte del bando nacional, lo que contribuyó, quizás de forma decisiva, al resultado de la guerra en la zona norte republicana, y no sólo porque éste traía de América suministros de vital importancia para el desarrollo de la contienda, sino por el efecto desmoralizador que también tuvo para el bando republicano.  


También decía en el post anterior que voy a intentar descifrar yo también el criptograma que puse como ejemplo. ¿Cómo lo consiguieron ellos?. Pues no lo sé, pero descartado un criptoanálisis basado en la  fuerza bruta (incluido un ataque de diccionario) porque en aquella época no había ordenadores, supongo que realizando un análisis de frecuencias (caracteres, bigramas, trigramas,...) para intentar reconstruir la tabla de homófonos utilizada en el cifrado. Tarea que como también decía no es nada fácil, y diría que incluso imposible, si no se dispone de una gran cantidad de texto cifrado.

Pero bueno, este criptograma tiene una longitud de 880 caracteres, lo que, junto con algunas vulnerabilidades adicionales de los métodos de sustitución por homófonos empleados en la guerra civil española, puede ser suficiente para su descifrado utilizando un simple análisis de frecuencias.

Las citadas vulnerabilidades de las que nos vamos a intentar aprovechar son las siguientes:

- En todas las claves que he visto, y "Bocho" no es una excepción, los homófonos se colocan por decenas en la misma fila de la tabla. Es decir, por ejemplo, si consideramos que la tabla utilizada contiene los números del "00" al "99", la primera decena (del "00" al "09") se coloca siempre en una misma fila, la segunda (del "10" al "19") en otra misma fila, y así sucesivamente. Esto es claramente una vulnerabilidad, ya que si conseguimos, por ejemplo, identificar que "09" se corresponde con el carácter "E" en el texto en claro ninguno del resto de homófonos de la misma decena podría ser candidato a ser la "E".

- En la mayoría de las claves que he visto cada carácter tiene entre 3 y 5 homófonos, lo que hace que en criptogramas largos persistan en cierta medida las características propias del idioma en cuanto a la frecuencia de aparición de las letras.  

- Además, si consideramos que un carácter tiene una media de 4 homófonos y que cada uno de ellos tiene una probabilidad de 1/4 de ser elegido para sustituir a su letra, entonces, si multiplicamos por cuatro la frecuencia de aparición de cada uno de ellos en el criptograma nos aproximaremos bastante a la frecuencia del carácter al que sustituye en el texto en claro y, por tanto, podremos comparar esta última con la frecuencia de aparición de cada letra en un texto escrito en español.

Vamos a intentarlo:

1.- Criptograma:

2883720527235753640527423488347782628801210454210453
5452625398533804732593145288613112054588520393225433
8212285704731056045704782334573665316365633319012873
0524540388082388599138637854124927889572011219612719
1716531445493915536536039183863482035653302343531462
2888149373302873420465615453382312885697639823510495
7753830465180151018204344354279354782316919424491293
2149435328179788017791053482175001303377885049834382
6204595312086146995628331363672377956333739591003493
0487226254579127337204034254629146993104133373770453
6204333883915334563423694936032327617728624922003343
3601270567389185910393254328673338884505523801788878
7388589349834246010900623605345354592834085347312163
0573228212177265314265465354095282466795632728655422
2193516382345346287398237336650538436198881488509122
5023322812982334776322018273285765534333970118884653
9501773377697861347253389504342390032394015961555691
9121053378611250427842823405951753678803333391382350
5961509398912704100004917398544623385356348833091988
4973210151934973041726052700500182502334502801735736
4983284505523801510528469028383334440510315305347204
0474886262885205917384546529319312333261726549885767
3661335317360050630538013427912163549733095312970428
8217632542430177337703043134423854414278823403549093
4432863892041251420551888349380481564228959136232149
5309913497615953988812935182678865884703232186519801
5346959185536593210583164686476263784975913649092822
5954379309230484679112829183083393120198930597424888
0477042231537308545731215317059503826214497547380418
2753129753779127914628020095017788215317810053534647
6103914647042236616723170125636293215421389133436326
284608042465496991789723

En la siguiente tabla se indica para cada posible homófono: su frecuencia de aparición en el criptograma (número de veces y porcentaje) y el porcentaje resultado de multiplicar por cuatro la frecuencia anterior:

Homófono     Fr.    Fr. (%)  Fr. x 4 (%)
00 8 0,91% 3,64%
01 24 2,73% 10,91%
02 2 0,23% 0,91%
03 14 1,59% 6,36%
04 35 3,98% 15,91%
05 23 2,61% 10,45%
06 0 0,00% 0,00%
07 0 0,00% 0,00%
08 7 0,80% 3,18%
09 7 0,80% 3,18%
10 3 0,34% 1,36%
11 0 0,00% 0,00%
12 18 2,05% 8,18%
13 2 0,23% 0,91%
14 7 0,80% 3,18%
15 1 0,11% 0,45%
16 3 0,34% 1,36%
17 12 1,36% 5,45%
18 3 0,34% 1,36%
19 4 0,45% 1,82%
20 0 0,00% 0,00%
21 15 1,70% 6,82%
22 11 1,25% 5,00%
23 24 2,73% 10,91%
24 4 0,45% 1,82%
25 4 0,45% 1,82%
26 2 0,23% 0,91%
27 16 1,82% 7,27%
28 26 2,95% 11,82%
29 1 0,11% 0,45%
30 3 0,34% 1,36%
31 11 1,25% 5,00%
32 4 0,45% 1,82%
33 24 2,73% 10,91%
34 25 2,84% 11,36%
35 0 0,00% 0,00%
36 12 1,36% 5,45%
37 1 0,11% 0,45%
38 21 2,39% 9,55%
39 1 0,11% 0,45%
40 0 0,00% 0,00%
41 1 0,11% 0,45%
42 13 1,48% 5,91%
43 12 1,36% 5,45%
44 2 0,23% 0,91%
45 4 0,45% 1,82%
46 19 2,16% 8,64%
47 8 0,91% 3,64%
48 2 0,23% 0,91%
49 21 2,39% 9,55%
50 11 1,25% 5,00%
51 10 1,14% 4,55%
52 7 0,80% 3,18%
53 38 4,32% 17,27%
54 23 2,61% 10,45%
55 1 0,11% 0,45%
56 9 1,02% 4,09%
57 11 1,25% 5,00%
58 1 0,11% 0,45%
59 7 0,80% 3,18%
60 0 0,00% 0,00%
61 17 1,93% 7,73%
62 14 1,59% 6,36%
63 17 1,93% 7,73%
64 1 0,11% 0,45%
65 19 2,16% 8,64%
66 0 0,00% 0,00%
67 9 1,02% 4,09%
68 0 0,00% 0,00%
69 3 0,34% 1,36%
70 0 0,00% 0,00%
71 0 0,00% 0,00%
72 7 0,80% 3,18%
73 20 2,27% 9,09%
74 1 0,11% 0,45%
75 2 0,23% 0,91%
76 0 0,00% 0,00%
77 16 1,82% 7,27%
78 11 1,25% 5,00%
79 0 0,00% 0,00%
80 0 0,00% 0,00%
81 2 0,23% 0,91%
82 17 1,93% 7,73%
83 11 1,25% 5,00%
84 3 0,34% 1,36%
85 2 0,23% 0,91%
86 5 0,57% 2,27%
87 1 0,11% 0,45%
88 31 3,52% 14,09%
89 0 0,00% 0,00%
90 3 0,34% 1,36%
91 32 3,64% 14,55%
92 1 0,11% 0,45%
93 21 2,39% 9,55%
94 2 0,23% 0,91%
95 13 1,48% 5,91%
96 0 0,00% 0,00%
97 9 1,02% 4,09%
98 10 1,14% 4,55%
99 2 0,23% 0,91%
880 100,00%

Por otra parte, la frecuencia de aparición (%) de las letras en un texto escrito en español es la siguiente (adicionalmente he establecido una frecuencia mínima de aparición suponiendo un margen de error del 20%):


Letra     Fr. (%)    Fr. Mín. (%)
E 13,68 10,944
A 12,53 10,024
O 8,68 6,944
S 7,98 6,384
R 6,87 5,496
N 6,71 5,368
I 6,25 5
D 5,86 4,688
L 4,97 3,976
C 4,68 3,744
T 4,63 3,704
U 3,93 3,144
M 3,15 2,52
P 2,51 2,008
B 1,42 1,136
G 1,01 0,808
V 0,9 0,72
Y 0,9 0,72
Q 0,88 0,704
H 0,7 0,56
F 0,69 0,552
Z 0,52 0,416
J 0,44 0,352
Ñ 0,31 0,248
X 0,22 0,176
W 0,02 0,016
K 0,01 0,008

2.- Ahora comparo ambas tablas para establecer los homófonos candidatos a ser la "E" (la letra significativamente más frecuentes en español). Serán candidatos a ser la "E" aquellos homófonos cuya frecuencia estimada de aparición de la letra a la que sustituye en el texto en claro (Fr. x 4) supere a la Frecuencia mínima (Fr. Mín.) establecida para dicho carácter.

E: 53 (17,27%), 04 (15,91%), 91 (14,55%), 88 (14,09%), 28 (11,82%), 34 (11,36%).

Los bigramas más frecuentes en español que empiezan por "E" son: "ES", "EN", "EL" y "ER".

Y los bigramas repetidos (3 o más veces) que se observan en el criptograma que comienzan con los candidatos establecidos para la "E" son los siguientes:

Bigrama  Fr.

5312 3
5317 3
5338 3
5346 5
9127 3
9146 3
2873 3
3453 3


A la vista de los resultados obtenidos hasta ahora, parece claro que el homófono "53" es el candidato más probable a corresponderse con la "E" en el texto en claro, debido a que es el que presenta una significativa mayor frecuencia de aparición en el criptograma (4,32%) y según nuestra extrapolación de aparición de la letra a la que sustituye en el texto en claro (17,27%), y, además, a que los bigramas que empiezan por ese homófono son los que se repiten con mayor frecuencia en el criptograma (en catorce ocasiones).

Además, creo que con bastante probabilidad (atendiendo a los hómofonos que aparecen siguiendo a los candidatos a ser la "E" en los bigramas repetidos y a la frecuencia estándar de cada letra en el idioma español) los homófonos "12", "17", "27", "38", "46" y "73" son candidatos a ser la "S", "N" o "R" en el texto en claro. Inicialmente descartamos que el "34" se corresponda con la "E" porque va seguido del "53" en tres ocasiones y este último es el candidato más probable a ser la propia "E" en el texto en claro.

El homófono "46" que sigue a dos candidatos a ser la letra "E" en 8 ocasiones sería el que con mayor probabilidad se correspondería con la "S" en el texto en claro.

Por tanto, tendríamos (voy marcando en rojo los candidatos más probables):

E: 53 (17,27%), 04 (15,91%), 91 (14,55%), 88 (14,09%), 28 (11,82%).
S: 38 (9,55%), 73 (9,09%), 46 (8,64%), 12 (8,18%), 27 (7,27%), 17 (5,45%).
R: 38 (9,55%), 73 (9,09%), 46 (8,64%), 12 (8,18%), 27 (7,27%), 17 (5,45%).
N: 38 (9,55%), 73 (9,09%), 46 (8,64%), 12 (8,18%), 27 (7,27%), 17 (5,45%).

3.- Comparo ambas tablas para establecer los homófonos candidatos a ser la "A" (la segunda letra significativamente más frecuentes en español). Teniendo en cuenta los candidatos ya establecidos, serán candidatos a ser la "A" aquellos homófonos cuya frecuencia estimada de aparición de la letra a la que sustituye en el texto en claro (Fr. x 4) supere a la Frecuencia mínima (Fr. Mín.) establecida para dicho carácter (descartando inicialmente aquellos homófonos que hemos seleccionado como candidatos a ser la "E").

A: 01 (10,91%), 23 (10, 91%), 33 (10,91%), 05 (10,45%), 54 (10,45%).

Entre los bigramas más frecuentes en español que empiezan por "A" se encuentran: "AR", "AS", "AD", "AI" y "AC".

los bigramas repetidos (3 o más veces) que se observan en el criptograma que comienzan con los candidatos establecidos para la "A" son los siguientes:

Bigrama Fr.
0151 3
0177 4
0182 3
0527 3
0534 3
2334 3
3377 3

Por tanto, creo que con bastante probabilidad (atendiendo a los resultados obtenidos hasta el momento, a los hómofonos que aparecen siguiendo a los candidatos a ser la "A" en los bigramas repetidos y a la frecuencia estándar de cada letra en el idioma español) se confirma que el homófono "27" es candidato a ser la "S", "N" o "R".

El homófono "77" que sigue a dos candidatos a ser la letra "A" en 7 ocasiones  es candidato a corresponderse con la "R", "S" o "N" (con mayor probabilidad de ser la "R").

El homófono "34" que sigue a dos candidatos a ser la letra "A" en 6 ocasiones (añadido a que sigue en 3 ocasiones al "53", el que con mayor probabilidad se correspondería con la "E") es candidato a corresponderse con la "S", "N" o "R".

El homófono "82" que sigue a dos candidatos a ser la letra "A" en 3 ocasiones  es candidato a corresponderse con la "R", "S" o "N" (con mayor probabilidad de ser la "R").

El homófono "51" presenta una frecuencia estimada de aparición de la letra a la que sustituye en el texto en claro que podría corresponderse con la letra "C" (no suficiente, según la frecuencia mínima establecida, ni para ser la "D" ni la "I"). Por si acaso, anoto que podría ser cualquiera de las tres, pero con mayor probabilidad de ser la "C".

E: 53 (17,27%), 04 (15,91%), 91 (14,55%), 88 (14,09%), 28 (11,82%).
A: 01 (10,91%), 23 (10, 91%), 33 (10,91%), 05 (10,45%), 54 (10,45%).
S: 34 (11,36%), 38 (9,55%), 73 (9,09%), 46 (8,64%), 12 (8,18%), 82 (7,73%), 27 (7,27%), 77 (7,27%), 17 (5,45%).
R: 34 (11,36%), 38 (9,55%), 73 (9,09%), 46 (8,64%), 12 (8,18%), 82 (7,73%), 27 (7,27%), 77 (7,27%), 17 (5,45%).
N: 34 (11,36%), 38 (9,55%), 73 (9,09%), 46 (8,64%), 12 (8,18%), 82 (7,73%), 27 (7,27%), 77 (7,27%), 17 (5,45%).
I: 51 (4,55%).
D: 51 (4,55%).
C: 51 (4,55%).

Y hasta aquí esta primera fase para intentar determinaren base a un análisis de frecuencias de los caracteres, los homófonos que podrían corresponderse con las dos letras ("E" y "A") más identificables del castellano, y, a partir de éste y de los bigramas más frecuentes que comenzarían por ellas, de aquellos que serían candidatos a ser las consonantes más frecuentes (he anotado un candidato más a corresponderse con otras letras, pero con todas las reservas).

Como digo tarea nada fácil, me temo que no me queda más que armarme de paciencia para, con mucha suerte, intentar reconstruir una tabla de candidatos que en una primera aproximación me dé las pistas necesarias para "tirar del hilo y desmadejar el ovillo". ¿Alguna idea?.

Yo, por mi parte, en el próximo post intentaré avanzar en el descifrado de este mensaje.  

viernes, 16 de septiembre de 2016

Criptografía (XXX): ¿Sabías que...? (VI)

En este post me pregunto: ¿Qué criptosistemas se utilizaron durante la guerra civil española? y, más concretamente, ¿en Euskadi?.

Pues tal y como he leído por ahí, en la guerra civil española se utilizaron muy diversos métodos de cifrado (incluido el de la versión comercial de la máquina Enigma por parte del bando nacional - parece ser que los alemanes no se fiaban mucho de éste o, al menos, no querían exponer en ese momento la versión militar de la máquina al criptoanálisis de los países que apoyaban al bando republicano, sin saber que los polacos ya estaban en ello y habían criptoanalizado con éxito la versión militar), pero, sin duda, los más utilizados fueron aquellos denominados de "papel y lápiz", y quizás el criptosistema más usado por ambos bandos fue el de la cinta móvil (con algunas variaciones respecto al método original), un caso particular de sustitución por homófonos.

Este tipo de criptosistemas, tal y como comenté en un post anterior, pretende "aplanar" o "suavizar" la frecuencia de aparición de los caracteres, símbolos o grupos de ellos en un criptograma (por ejemplo, sustituyendo cada carácter del alfabeto del texto en claro por varios números de dos dígitos), de forma que las características propias de un idioma en cuanto a la frecuencia de aparición de las letras no se trasladen al criptograma y evitar así el análisis de frecuencias.

Ya contaré en un post posterior en qué consistía exactamente este método, pero, en esencia, se trata de sustituir cada carácter del texto en claro por alguno de los dos dígitos que le corresponden conforme a una tabla similar a la siguiente:
De tal forma que, por ejemplo, mi nombre, "Mikel", podría cifrarse como: "3475421751", es decir, eligiendo un número de dos dígitos en la columna que le corresponde al carácter del texto en claro a cifrar.


Hay muchos ejemplos de claves de cifrado de este tipo que se utilizaron en Euskadi por parte del bando republicano: entre ellas "Bocho" y "Victoria", empleadas para las comunicaciones entre el Ministro de Marina y Aire con el Presidente del Gobierno Vasco y el Delegado del Gobierno en Santander, pero quizás la más conocida es la clave X, cuyo descifrado por parte del bando nacional, junto con el de las dos claves anteriormente mencionadas y según algunos autores, facilitó la captura por el crucero pesado "Canarias" del bando nacional, en marzo de 1937, del mercante "Mar Cantábrico", construido en los astilleros de Euskaduna de Bilbao y que traía desde América un cargamento de suministros vitales para el bando republicano en la zona norte.

En el siguiente post intentaré criptoanalizar un mensaje cifrado con la clave "Bocho", transmitido menos de un mes antes de esta captura, y que fue interceptado y descifrado por el bando nacional. El siguiente:

Clave Bocho.
De Valencia para Bilbao.
Transmitido día 13-2-37. A las 9.15 horas. 880 caracteres.

2883 7205 2723 5753 6405 2742 3488 3477 8262 8801 2104 5421 0453 4608
5452 6253 9853 3804 7325 9314 5288 6131 1205 4588 5203 9322 5433 4893
8212 2857 0473 1056 0457 0478 2334 5736 6531 6365 6333 1901 2873 0443
0524 5403 8808 2388 5991 3863 7854 1249 2788 9572 0112 1961 2719 2838
1716 5314 4549 3915 5365 3603 9183 8634 8203 5653 3023 4353 1462 8827
2888 1493 7330 2873 4204 6561 5453 3823 1288 5697 6398 2351 0495 9549
7753 8304 6518 0151 0182 0434 4354 2793 5478 2316 9194 2449 1293 9112
2149 4353 2817 9788 0177 9105 3482 1750 0130 3377 8850 4983 4382 5791
6204 5953 1208 6146 9956 2833 1363 6723 7795 6333 7395 9100 3493 6557
0487 2262 5457 9127 3372 0403 4254 6291 4699 3104 1333 7377 0453 8447
6204 3338 8391 5334 5634 2369 4936 0323 2761 7728 6249 2200 3343 5346
3601 2705 6738 9185 9103 9325 4328 6733 3888 4505 5238 0178 8878 6349
7388 5893 4983 4246 0109 0062 3605 3453 5459 2834 0853 4731 2163 2865
0573 2282 1217 7265 3142 6546 5354 0952 8246 6795 6327 2865 5422 6173
2193 5163 8234 5346 2873 9823 7336 6505 3843 6198 8814 8850 9122 3133
5023 3228 1298 2334 7763 2201 8273 2857 6553 4333 9701 1888 4653 0256
9501 7733 7769 7861 3472 5338 9504 3423 9003 2394 0159 6155 5691 2486
9121 0533 7861 1250 4278 4282 3405 9517 5367 8803 3333 9138 2350 6523
5961 5093 9891 2704 1000 0491 7398 5446 2338 5356 3488 3309 1988 8322
4973 2101 5193 4973 0417 2605 2700 5001 8250 2334 5028 0173 5736 5443
4983 2845 0552 3801 5105 2846 9028 3833 3444 0510 3153 0534 7204 4646
0474 8862 6288 5205 9173 8454 6529 3193 1233 3261 7265 4988 5767 9151
3661 3353 1736 0050 6305 3801 3427 9121 6354 9733 0953 1297 0428 1747
8217 6325 4243 0177 3377 0304 3134 4238 5441 4278 8234 0354 9093 7728
4432 8638 9204 1251 4205 5188 8349 3804 8156 4228 9591 3623 2149 0414
5309 9134 9761 5953 9888 1293 5182 6788 6588 4703 2321 8651 9801 6134
5346 9591 8553 6593 2105 8316 4686 4762 6378 4975 9136 4909 2822 4973
5954 3793 0923 0484 6791 1282 9183 0833 9312 0198 9305 9742 4888 3227
0477 0422 3153 7308 5457 3121 5317 0595 0382 6214 4975 4738 0418 9388
2753 1297 5377 9127 9146 2802 0095 0177 8821 5317 8100 5353 4647 0438
6103 9146 4704 2236 6167 2317 0125 6362 9321 5421 3891 3343 6326 5465
2846 0804 2465 4969 9178 9723

¿Alguien se anima a intentarlo?. Tarea que entiendo que no es fácil, pero lo intentaré :) y contaré los resultados.

Como pista decir que descarto cualquier criptoanálisis basado en la fuerza bruta (incluido un ataque de diccionario), ya que en aquella época no existían los ordenadores, y lo intentaré mediante un simple análisis de frecuencias.

martes, 13 de septiembre de 2016

Gimnasia mental (XXV): ¿Cuántos cuadrados ves?

Un problema muy en boga en las redes sociales últimamente es dar la respuesta correcta a:

¿Cuántos cuadrados ves en esta figura?.

Ya nos avisan que el 99% de las personas fallan en esta prueba. O sea, que si  no acertamos no es que seamos gilipollas, sino que podemos considerar que estamos dentro de "lo normal" y, por tanto y a lo sumo, que somos moderadamente estúpidos. ¡Joé, qué estrés!, :).

La figura en cuestión es la siguiente:
Voy contando los que yo veo (no vale hacer trampas y ver los que yo he contado antes de dar una respuesta ;) ):

- Uno:
 
- Cuatro:
- Nueve:

- Dieciocho:
- Ocho:
Es decir, Total cuadrados = 1 + 4 + 9 + 18 + 8 = 40.

Con lo que me sigue quedando la duda: ¿son todos los que hay o soy moderadamente estúpido?.