Tor es un cojunto de herramientas que pretende conseguir el anonimato online. Usa una red de máquinas o nodos a través de los cuales enruta el tráfico de red, tal y como se muestra en el esquema siguiente:

Como se ve en el dibujo una conexión a través de la red Tor usa tres nodos intermediarios entre el origen y el destino. De esta manera la máquina destino que recibe la conexión solo tendrá acceso a la IP del último nodo.

Tor ofrece una interfaz SOCKS a las aplicaciones, por lo que cualquier aplicación preparada para usar SOCKS podrá utilizar la red Tor sin problemas.
Sin embargo, no es necesario que una aplicación disponga de soporte para SOCKS, dado que Tor distribuye un script llamado "torify" que permite que cualquier aplicación use la red tor.

Este script emplea la herramienta tsocks para permitir que una aplicación use SOCKS de forma transparente.


Para que un usuario pueda conectarse a la red Tor necesita obtener un listado de nodos de la red. Este proceso, como indica el dibujo, se realiza sin cifrar.



A continuación se empieza a crear el circuito por el que viajaran los datos en la red Tor. Cada servidor conoce únicamente al servidor que le proporciona los datos y al servidor al que se los envía. por lo que ninguna máquina conoce el recorrido completo. Además, en cada tramo, los servidores afectados negocian claves diferentes, impidiendo que las conexiones sean rastreadas.



Una vez el circuito ha sido establecido se utilizará durante unos diez minutos. Posteriormente se creará un circuito nuevo.







La forma de instalar Tor depende en gran medida del sistema operativo utilizado, por lo que para instalarlo lo mejor es partir de la documentación oficial.

Una vez instalado su uso es sencillo. Por ejemplo, podríamos torificar la aplicación netcat con el comando siguiente:

$ torify nc www.google.com 80

Observemos el funcionamiento de Tor. Si no usamos el comando "torify" vemos que estamos realizando una conexión directa a google.

$ nc www.google.com 80

# En otro terminal
$  netstat  | grep ESTABLISHED
tcp        0      0 192.168.1.69:34362          nf-in-f99.google.com:http   ESTABLISHED

Sin embargo, torificando netcat los resultados son diferentes.

$ torify nc www.google.com 80

# En otro terminal
$ netstat  | grep ESTABLISHED
tcp        0      0 192.168.1.69:34352          tor.outra.net:9090          ESTABLISHED
tcp        0      0 192.168.1.69:34351          cyberphunk.eu:9001          ESTABLISHED

Queda claro que no saltamos directamente al servidor de google sino que entramos en la red Tor. Veamos ahora con que dirección IP llegamos a nuestro destino. Necesitaremos una web que nos diga la dirección IP (http://www.vermiip.es/) y otra que nos diga la localización geográfica (http://www.ip2location.com/free.asp),

Esto nos permitirá obtener la IP con el comando:

$ torify lynx --dump http://www.vermiip.com 2>/dev/null | grep "Tu ip" | cut -c 18-30
85.214.63.25

Y su localización geográfica:

$ torify lynx --dump http://www.ip2location.com/free.asp?ipaddresses=85.214.63.25 \
2>/dev/null | grep "85.214.63.25\|mapit" |  sed -e 's/\[.*\]//'
          85.214.63.25 DE GERMANY
BERLIN BERLIN STRATO RECHENZENTRUM BERLIN

De esta manera podemos construir un sencillo script que nos de el listado de nodos de salida de Tor.

$ cat  print_tor_nodes.sh
#!/bin/bash

while true; do

IP=`torify lynx --dump http://www.vermiip.com 2>/dev/null | grep "Tu ip" | cut -c 18-30`;

DATA=`torify lynx --dump http://www.ip2location.com/free.asp?ipaddresses="$IP" \
2>/dev/null | grep "$IP\|mapit" |  sed -e 's/\[.*\]//'`

echo $DATA
sleep 300

done

Del que extraemos el siguiente listado, que nos permite ver los nodos que nos dan acceso a Internet en último lugar.

208.64.29.34 US UNITED STATES NEW YORK NEW YORK R & D TECHNOLOGIES LLC
217.20.117.1 DE GERMANY BERLIN BERLIN NETDIREKT E. K
128.197.11.3 US UNITED STATES MASSACHUSETTS BOSTON BOSTON UNIVERSITY
88.191.29.92 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
88.191.25.27 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
89.149.207.1 DE GERMANY BERLIN BERLIN NETDIREKT E.K
87.234.124.1 DE GERMANY BERLIN BERLIN QSC AG DYNAMIC IP ADDRESSES
88.191.29.92 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
87.234.124.1 DE GERMANY BERLIN BERLIN QSC AG DYNAMIC IP ADDRESSES
88.191.29.92 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
128.197.11.3 US UNITED STATES MASSACHUSETTS BOSTON BOSTON UNIVERSITY
75.72.79.46 US UNITED STATES
203.26.16.68 AU AUSTRALIA NEW SOUTH WALES WEST WYALONG TPG INTERNET PTY LTD
88.191.11.18 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
88.198.50.14 DE GERMANY - - HETZNER-RZ-NBG-NET
83.243.80.77 DE GERMANY BERLIN BERLIN SERVERCREW LTD. PI
88.191.29.92 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
209.160.32.1 US UNITED STATES DISTRICT OF COLUMBIA WASHINGTON HOPONE INTERNET CORPORATION
60.167.39.24 CN CHINA BEIJING BEIJING CHINANET ANHUI PROVINCE NETWORK
83.217.66.50 BE BELGIUM OOST-VLAANDEREN DENDERMONDE NMV-CUST-DIGITALROOT
128.2.141.33 US UNITED STATES PENNSYLVANIA PITTSBURGH CARNEGIE MELLON UNIVERSITY83.171.182.9 DE GERMANY BAYERN NüRNBERG MNET TELEKOMMUNIKATION GMBH
85.214.63.25 DE GERMANY BERLIN BERLIN STRATO RECHENZENTRUM BERLIN
74.208.46.15 US UNITED STATES NEW YORK NEW YORK 1&1 INTERNET INC
122.145.8.19 JP JAPAN - - FREEBIT CO. LTD
71.226.252.2 US UNITED STATES PENNSYLVANIA WEST CHESTER COMCAST CABLE COMMUNICATIONS INC
83.233.181.9 SE SWEDEN - - PROVIDER LOCAL REGISTRY
166.70.207.2 US UNITED STATES UTAH SALT LAKE CITY XMISSION
195.71.90.10 DE GERMANY - - PROVIDER LOCAL REGISTRY
...

Respecto al script anterior, realiza un sleep de cinco minutos antes de reintentar, lo que hace el procese extremadamente lento. Si se reinicia Tor antes de cada petición el circuito se crea de nuevo y se obtiene un nodo diferente. De esta manera puede suprimirse el sleep del script.



En el momento de escribir este artículo la red Tor es relativamente pequeña, lo que disminuye notablemente el grado de anonimato. Aunque, sin duda, tiene un futuro prometedor.


Referencias:
- Tor Project: http://www.torproject.org

Continuando con la serie de artículos sobre factorización, hoy veremos el método Rho de Pollard. Un instructivo algoritmo que permite factorizar números bastante más grandes que los que podríamos factorizar mediante divisiones sucesivas de números primos o aplicando directamente el método de Fermat, tal y como vimos en "Factorización I: Introducción".

A lo largo de este artículo (y de los siguientes) se usará la operación mod. Esta operación representa el resto de una división entera. Por ejemplo 6 mod 5 =1 pues si dividimos seis entre cinco la division no es exacta, dado que tiene resto 1. Otros ejemplos pueden ser: 101 mod 99 = 2, 4^2 mod 15=1 o 33² mod 989 = 10².

Ahora supongamos que tenemos la ecuación F(x)=x² mod n. Si aplicamos esta ecuación para diferentes valores de x queda claro que el resultado siempre será menor que n. Por lo tanto, si aplicamos la ecuación para diferentes valores de x es lógico pensar en que en algun momento los resultados empezarán a repetirse, pues son finitos!

Veamos un ejemplo para n=323, empezando por ejemplo con x=2.

F(2) = 2² mod 323 = 4
F(4) = 4² mod 323 = 16
F(16) = 16² mod 323 = 256
F(256) = 256² mod 323 = 290
F(290) = 290² mod 323 = 120
F(120) = 120² mod 323 = 188
F(188) = 188² mod 323 = 137
F(137) = 137² mod 323 = 35
F(35) = 35² mod 323 = 256
F(256) = 16² mod 323 = 290
F(290) = 290² mod 323 = 120

Como se ve marcado en rojo, a partir de F(35) los resultados empiezan a repetirse, entrando en un ciclo.

Si representamos en un dibujo los resultados obtenidos vemos que su forma es similar al de la letra griega rho. Lo que da nombre al algoritmo.



El algoritmo Rho de Pollard permite encontrar ciclos cuando se trabaja con grupos donde los elementos son finitos. De manera que lo único que hemos hecho hasta ahora es encontrar un ciclo en un campo de números finitos con n=323. Pero, ¿Cómo aplicar esto para factorizar?

Si nos fijamos bien en la Rho dibujada vemos un hecho interesante producido al cerrar el ciclo. Llegamos al número 256 tanto a partir de 16² como a partir de 35². Este hecho, conocido como colisión, nos permite ver que 35²=16² mod 323. Lo que se conoce como congruencia y significa que 35² mod 323 = 16². Así pues, de forma similar a como vimos en el método de Fermat encontraremos un factor p mediante 35-16=19.

Resumiendo, el algoritmo Rho de Pollard nor permitirá encontrar colisiones, que a su vez nos permitiran encontrar un factor de n.

Para aplicar el método Rho de Pollard tal y como lo hemos visto, es necesario almacenar todos los elementos y compararlos con los elementos nuevos que se van generando. Esto es muy costoso tanto en tiempo como en espacio. Afortunadamente, existe una variación conocida como método de Floyd para encontrar ciclos, que permite encontrar una colisición sin almacenar apenas datos. Este método consiste en mantener dos valores. El primero recorrera en cada paso un elemento de la Rho, el segundo recorrerá dos. El tiempo estimado en el que ambos se encontrarán de nuevo, formando una colisión, es en el peor de los casos la raiz de n.

Algoritmo:

1. Elegir un entero aleatorio a entre 1 y n-3.
2. Elegir un entero aleatorio s entre 0 y n-1.
3. Inicializar U=V=s;
4. Calcular U=F(U), V=F(F(V)));
5. Si MCD(U-V, n) = 1, volver al punto 4.
6. Si MCD(U-V, n) = n, volver al punto 1.
7. MCD(U-V, n) es un factor de n.

NOTA: MCD=Máximo Común Divisor.



Hemos visto que el tiempo estimado para factorizar un número es de raiz de n en el peor de los casos. Pero existe una manera de mejorar considerablemente el tiempo de resolución del algoritmo cuando se dispone de cierta información sobre uno de los factores de n.

Se estima que usando F(x)=x^(2k) +a mod n, el número de iteraciones necesarias para encontrar un factor de n es de c*RAIZ(p)/RAIZ(MCD(p-1,2K)-1).
Es decir, quanto más factores comunes existan entre p-1 y 2k, menor será el número de iteraciones necesario para encontrar p.
Si no sabemos que factores puede tener p-1 puede ser útil calcular el factorial de un número B y usarlo como k: k=B!. Cuanto más grande sea B menos operaciones seran necesarias para encontrar el factor. Pero tampoco se puede abusar del tamaño de B, pues para valores demasiado grandes el tiempo por iteración será muy elevado.


Veamos un ejemplo usando el programa rho_2k.cpp que pego al final:

$ g++ -lgmpxx rho_2k.cpp -o rho_2k
$ ./rho_2k [n number] [B bound]

El primer parámetro es el número que queremos factorizar, el segundo el número B que usaremos para calcular k mediante su factorial.

Intentemos factorizar el número de 32 bits: 2930992620606930277. Primero con B=1, que equivale a k=1:

$ ./rho_2k 2930992620606930277 1
factor: 1065951967
count: 19188

Hemos necesitado 19.188 operaciones. Intentemoslo ahora con B=10:

./rho_2k 2930992620606930277 10
factor: 2749647931
count: 9516

El número de iteraciones baja. Con B=100:

./rho_2k 2930992620606930277 100
factor: 2749647931
count: 50

Como podemos observar la mejora es tangible. Finalmente con B=1000:

./rho_2k 2930992620606930277 700
factor: 2749647931
count: 1

En una sola operacion!


Hemos visto que cuantos más factores coinciden entre p-1 i k mejores son los resultados. Hasta el punto de que si todos los factores de p-1 estan en k, se resuelve la factorización en una sola operación. Sin embargo B no puede incrementarse indefinicademente, pues el factorial crece muy rápido, y no tardaremos en llegar a valores que relentizarán demasiado las operaciones.


Finalmente dejo una copia del programa usado:

#include <gmpxx.h>
#include <iostream>

// F(x) = x^2k + a mod n
mpz_class F(mpz_class &x, mpz_class &k, mpz_class &a, mpz_class &n)
{
  mpz_class res;
  mpz_class pow;

  pow = 2*k;
  mpz_powm(res.get_mpz_t(), x.get_mpz_t(), pow.get_mpz_t(), n.get_mpz_t());
  res += a;

  return res;
}

int main(int argc, char *argv[])
{
  using namespace std;

  mpz_class n;
  mpz_class U;
  mpz_class V;
  mpz_class s;
  mpz_class g;
  mpz_class k;
  mpz_class a;
  mpz_class count;

  if (argc!=3)
  {
     cout << argv[0] << " [n number]  [B bound]" << endl;
     return 0;
  }

  n = argv[1];
  int B = atoi(argv[2]);
  count = 0;
  s = 2;
  U = s;
  V = s;
  g = 1;

  mpz_fac_ui(k.get_mpz_t(), B);
  a = 3;

  while(g==1)
  {
     U = F(U, k, a, n);
     V = F(V, k, a, n);
     V = F(V, k, a, n);

     g = U-V;
     mpz_gcd(g.get_mpz_t(), g.get_mpz_t(), n.get_mpz_t());

     if(g==n)
     {
        cout << "bad seed" << endl;
        U++;
        V++;
        g=1;
     }
     count ++;
  }

  cout << endl << "factor: " << g << endl;
  cout << "count: " << count << endl;

  return 0;
}

Referencias:
- Prime Numbers, A Computational Perspective. Crandall & Pomerance. Ed Springer.

Ya hablamos de la importancia que tiene la factorización en criptografía en "Rompiendo claves RSA". En esta serie de artículos se hará un repaso a los algoritmos usados para factorizar números grandes, empezando por los algoritmos más básicos hasta llegar a los más actuales y modernos sistemas, que permiten factorizar números de más de 150 dígitos decimales.

Como veremos, existen decenas de algoritmos de factorización, pero los más destacados por su mayor velocidad (o menor complejidad) son:

- Quadratic Sive (QS): El algoritmo más rápido para factorizar números grandes de propósito general menores de 110 dígitos decimales (aproximadamente).

- Number Field Sieve (NFS): El algoritmo más rápido para factorizar números grandes de propósito general mayores de 110 dígitos decimales (aproximadamente).

- Elliptic Curve Method (ECM): El algoritmo más rápido para factorizar números grandes cuando uno de los factores es relativamente pequeño.


Estos tres algoritmos tienen un complejidad subexponencial que es lo más rápido que se ha conseguido llegar en el campo de la factorización. Si se encontrase un algoritmo de complejidad polinómica, podríamos decir que el problema de la factorización queda resuelto y dejaría de poder utilizarse en criptografía. Esto significaría, entre otras cosas, el fin de algoritmos como RSA.

Los algoritmos QS i NFS se basan en una vieja estratégia atribuída al genial matemático Pierre de Fermat. La vemos a continuación:
Supongamos que disponemos de un número n del cual queremos obtener su representación como multiplicación de dos factores, es decir n=pq. Ecuación que también podríamos representar como n=(x+y)(x-y).

Si encontramos dos números enteros positivos que cumlan la ecuación de manera que x-y sea mayor que 1, diremos que hemos encontrado un factor no trivial de n, quedando el problema resuelto. Pero para buscar a y b cambiaremos el enfoque del problema.

Sabemos que (x+y)(x-y)=x²-y² , lo que nos permite un cambio de estrategia importante, pues ya no tenemos que buscar directamente factores de n, sino parejas de cuadrados cuya diferencia sea n.
Veamos un ejemplo para n=989. Si realizamos una búsqueda de cuadrados empezando por la raiz entera de 989, es decir 31, tenemos que 32²-989=35 no es cuadrado, continuamos, 33³-989=100 y bingo! Pues vemos que 33²-10²=989. Partiendo de la fórmula anterior tenemos que el factor p corresponde a p=33-10=23 y el factor q corresponde a q=33+10=43. Quedando n factorizado como 989=23*43.

El método utilizado puede parecer muy rápido, pues hemos factorizado el 989 en solo dos operaciones. Si nos hubiesemos dedicado a probar con todos los números primos menores que 31 habríamos necesitado 9 operaciones! (2, 3, 5, 7, 11, 13, 17, 19, 23). Pero lo cierto es que cuando tratamos de factorizar números más grandes vemos que el enfoque no es el adecuado, pues resulta extremadamente lento.

Lo que debemos tener en cuenta de la idea de Fermat es que proporciona una estrategia diferente para atacar el problema, de manera que pasamos de buscar factores de n a buscar diferencias de cuadrados. Como veremos en próximos artículos, esta estratégia se usa con éxito en los algoritmos QS y NFS.

En criptografía se habla de curva elíptica en referencia a una ecuación y²=x³+Ax+B que cumple 4A³+27B²≠0. Dando diferentes valores a A y B obtenemos todo un conjunto de curvas que, al ser dibujadas, ofrecen una forma similar. Son ejemplos de curvas elípticas y²=x³-x (izquierda) y y²=x³-x+1 (derecha).

Las curvas elípticas tienen ciertas características que las hacen especiales en el mundo de la criptografía. Una de estas características consiste en la posibilidad de poder generar un punto en una curva partiendo de dos puntos dados (o incluso de uno). Este concepto es muy fácil de entender partiendo de la figura siguiente.

Usamos como puntos de partida P y Q, dos puntos conocidos. Trazaremos una linea entre P y Q. Si la linea corta la curva en un tercer punto, lo reflejaremos a través del eje, dando lugar a un nuevo punto R. Esta operación se representa como R=P+Q. En caso de que la linea que pasa por P y Q no corte a la curva en ningún otro punto, diremos que corta la curva en un punto O en el infinito y representaremos esta operación como P+Q=O.

Partiendo de la suma, no es difícil encontrar un mecanismo que nos permita realizar multiplicaciones de tipo kP, siendo k un escalar. Por ejemplo, imaginemos que queremos realizar la operación 13P, es decir, multiplicar 13 por un punto P. Bastaría con realizar la siguiente secuencia de doblado de puntos:

Este simple mecanismo para generar nuevos puntos dota a una curva elíptica de la posibilidad de realizar operaciones aritméticas sobre ella, base de los criptosistemas que estudiaremos en breve.

En criptografía las curvas elípticas se usan sobre campos finitos (Fq) con q muy grande. Un ejemplo de campo finito podría ser F5={0,1,2,3,4}. De manera que el número 7 representado en el campo finito correspondería a 7 mod 5 = 2.
Cuando se usan campos finitos el número de puntos que hay en una curva tambien es finito. Este numero se llama orden de la curva y se representa como #E. Debemos diferenciarlo del orden de un punto, que se refiere al valor k más pequeño (diferente de 0) que multiplicado por P da O.

La criptografía de Clave Pública basa su fuerza en la dificultad de resolver ciertos problemas matemáticos. Uno de los más usados es el problema del logaritmo discreto (Discrete Logarithm Problem - DLP). Este problema se basa en la dificultad que representa resolver una ecuación de tipo x = a^y mod n donde x, a y n son conocidas e y es la variable que se busca. De hecho, para valores de n e y sufientemente grandes es computacionalmente imposible resolver el problema, al menos, con los algoritmos y ordenadores actuales.
El algoritmo más rápido conocido para resolver este problema es el Index Calculus que permite resolverlo en tiempo subexponencial.

Existe una problema similar al problema del logaritmo discreto que puede usarse con Curvas Elípticas. Anteriormente hemos visto como realizar una operación tipo Q=kP de una forma sencilla. Sin embargo, obtener k y P partiendo solo de Q es computacionalmente difícil. De hecho, el algoritmo más rápido que permite encontrar una solución es el algoritmo Rho de Pollard, pero este algorimo es de tiempo exponencial, mucho mas lento que en el caso del ataque a DLP mediante el Index Calculus.
Este hecho es muy importante, pues la dificultad de resolver ECDLP frente a DLP permite que los criptosistemas que se basan en el primero usen claves mucho más cortas. De manera que los sistemas que usan ECDLP requieren mucha menos memoria y capacidad de proceso.
Una clave RSA de 4096 bits ofrece la misma seguridad que una clave de un criptosistema de Curva Elíptica de 313 bits.

El intercambio de claves de Diffie-Hellman es un protocolo que permite un intercambio secreto y seguro de claves entre dos partes que no han tenido un contacto previo. Se usa ampliamente en criptografía y se basa en el problema del logaritmo discreto (DLP). Por lo tanto, puede usarse el mismo algoritmo a través del problema ECDLP.

Al algoritmo puede resumirse en los siguientes pasos:

1. Alice y Bob eligen una curva elíptica E sobre un campo finito Fq de manera que el ECDLP sea computacionalmente difícil. También eligen un punto P en dicha curva de manera que su orden sea un número primo grande.

2. Alice elige un entero grande a, calcula PA=aP y envía PA a Bob.

3. Bob elige un entero grande b, calcula PB=bP y envía PB a Alice.

4. Alice calcula aPB=abP

5. Bob calcula bPA=abP


Al finalizar el algoritmo, tanto Alice como Bob disponen de abP. Pero un usario que escuche el canal solo habrá podido obtener PA y PB, los cuales no le permiten calcular abP a menos que resuelva el ECDLP. Alice y Bob solo tendrán que extraer una clave a partir de abP y usarla para enviar datos cifrados. Para tal propósito podrán usar cualquier algoritmo simétrico como DES, AES, etc.

Des de la versión 0.9.8 la herramienta OpenSSL ofrece algunas opciones para trabajar con curvas elípticas. No están muy documentadas, pero nos servirán para realizar una pequeña demostración del uso de la firma digital.

Para generar un clave ejecutaremos el siguiente comando:

$ openssl ecparam -genkey -name secp224r1 -out key.pem

Ahora tanto la clave pública como la privada se encuentran dentro de key.pem. Podemos extraer la pública con el comando:

$ openssl ec -in key.pem -text -pubout -out pubkey.pem

Ya disponemos de una clave con la que hacer pruebas, por lo que generaremos un mensaje que firmar:

$ echo "El mensaje de prueba de h4ck1t!" > msg.txt

Y lo firmaremos, operación que solo puede realizar el propietario de la clave privada:

$  openssl dgst -sign key.pem -ecdsa-with-SHA1 < msg.txt > msg.sig

Firmado el mensaje, todo usuario que disponga de la clave pública podrá verificar su procedencia:

$ openssl dgst -verify pubkey.pem -ecdsa-with-SHA1 -signature msg.sig < msg.txt
Verified OK

Referencias:

- Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington. Ed Chapman & HALL/CRC.
- Prime Numbers, a Computational Perspective. Richard Crandall, Carl Pomerance. Ed Springer.
- Criptografía de curva Elíptica, Ataque Rho de Pollard. Daniel Lerch. Hakin9 (6-2007).

Análisis de frecuencias:

El análisis de frecuencias es una forma de criptoanálisis utilizada en cifrados de sustitución, basada en el estudio de la frecuencia de aparición de las letras o símbolos de un criptograma. Este análisis se basa en el hecho de que cada lenguaje dispone de una frecuencia característica de aparición de sus letras o grupos de ellas. Por ejemplo, en inglés es común el uso de la letra E mientras que la X raramente aparece. Lo mismo ocurre en los textos en castellano, donde la E y la A son las letras más habituales.

Aproximadamente la distribución de porcentajes de aparición de cada letra en algunas lenguas comunes es la siguiente:

L       Inglés           Francés         Alemán          Castellano

a       8.167%          7.636%          6.51%           12.53%
b       1.492%          0.901%          1.89%           1.42%
c       2.782%          3.260%          3.06%           4.68%
d       4.253%          3.669%          5.08%           5.86%
e       12.702%         14.715%         17.40%          13.68%
f       2.228%          1.066%          1.66%           0.69%
g       2.015%          0.866%          3.01%           1.01%
h       6.094%          0.737%          4.76%           0.70%
i       6.966%          7.529%          7.55%           6.25%
j       0.153%          0.545%          0.27%           0.44%
k       0.772%          0.049%          1.21%           0.00%
l       4.025%          5.456%          3.44%           4.97%
m       2.406%          2.968%          2.53%           3.15%
n       6.749%          7.095%          9.78%           6.71%
o       7.507%          5.378%          2.51%           8.68%
p       1.929%          3.021%          0.79%           2.51%
q       0.095%          1.362%          0.02%           0.88%
r       5.987%          6.553%          7.00%           6.87%
s       6.327%          7.948%          7.27%           7.98%
t       9.056%          7.244%          6.15%           4.63%
u       2.758%          6.311%          4.35%           3.93%
v       0.978%          1.628%          0.67%           0.90%
w       2.360%          0.114%          1.89%           0.02%
x       0.150%          0.387%          0.03%           0.22%
y       1.974%          0.308%          0.04%           0.90%
z       0.074%          0.136%          1.13%           0.52%

A parte de estudiar la frecuencia de aparición de un símbolo, también podemos fijarnos en la frecuencia de aparición de conjuntos de dos, tres, o más letras. En castellano son frecuentes cadenas de dos letras como DE, LA, EL, EN o palabras de tres como QUE, LOS, DEL, LAS y POR.

A continuación se muestran los conjuntos de dos y tres letras más frecuentes:

En Inglés
Conjuntos de dos letras: TH, HE, AN, IN, ER, RE, ES, ON, EA, TI, AT, ST, EN, ND, OR, TO, NT, ED, IS, AR.
Conjuntos de tres letras: THE, ING, AND, ION, ENT, FOR, TIO, ERE, HER, ATE, VER, TER, THA, ATI, HAT, ERS.

En Francés:
Conjuntos de dos letras: ES, EN, OU, DE, NT, TE, ON, SE, AI, IT, LE, ET, ME, ER, EM, OI, UN, QU.
Conjuntos de tres letras: ENT, QUE, ION, LES, AIT, TIO, ANS, ONT, ANT, OUR, AIS, OUS.

En Alemán
Conjuntos de dos letras: EN, ER, CH, DE, GE, EI, IE, IN, NE, ND, BE, EL, TE, UN, ST, DI, NO, UE, SE, AU, RE, HE.
Conjuntos de tres letras: EIN, ICH, DEN, DER, TEN, CHT, SCH, CHE, DIE, UNG, GEN, UND, NEN, DES, BEN, RCH.

En Castellano:
Conjuntos de dos letras: ES, EN, EL, DE, LA, OS, AR, UE, RA, RE, ER, AS, ON, ST, AD, AL, OR, TA, CO.
Conjuntos de tres letras: QUE, EST, ARA, ADO, AQU, DEL, CIO, NTE, OSA, EDE, PER, IST, NEI, RES, SDE.


Al intentar romper un cifrado mediante análisis de frecuencia nuestro objetivo será identificar la frecuencia de aparición de los símbolos usados. Después buscaremos una equivalencia entre estos símbolos y las letras que más aparecen en la lengua usada intentando encontrar un significado. Nos servirán también las frecuencias de aparición de conjuntos de X letras, así como nuestra imaginación a la hora de rellenar huecos al estilo del juego del ahorcado.

En algunos casos puede ser útil conocer el porcentaje de vocales de cada idioma. En inglés, por ejemplo, el porcentaje de vocales es del 40%, igual que en el alemán. Sin embargo, en francés es del 45% y en castellano del 47%. Estos datos, aunque solo son aproximaciones pueden resultar de gran interés en ciertos criptogramas.


Criptoanálisis de ejemplo

Para experimentar con lo comentado anteriormente, imaginemos un sistema de cifrado por sustitución, de manera que cada letra del mensaje ha sido sustituída por un símbolo. El ejemplo de mensaje cifrado es el siguiente:

3# 16_@!5?6#=_# 2> 23 #6!2 |2 2>16_$_6 15% 13#72 >2162!# 5 |2 /% 45|5 2%_?4#!_15

Para iniciar nuestro criptoanálisis, empezaremos realizando un análisis de frecuencias. Para que este proceso no se haga pesado, adjunto un sencillo programa en C++ que lo hará por nosotros.

#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>


int main(int argc, char* argv[])
{
 using namespace std;

 if(argc!=3)
 {
 cout << "Usage: " << argv[0] << " [file] [max group size]" << endl;
 return 0;
 }

 for(int i=0; i<atoi(argv[2]); i++)
 {
    int c;
    map<string,int> freq;
    ifstream file(argv[1]);
    string group;
    while( (c=file.get()) && !file.eof() )
    {
       if(isspace(c))
       continue;
       group += string(1,c);

       if(group.size()>=i+1)
          freq[group.substr(group.size()-i-1, i+1)]++;
    }

    cout << endl << "-- FREQ SIZE " << i+1 << " --" << endl;
    int count = 0;
    map<string,int>::iterator it = freq.begin();    
    for(;it!=freq.end(); it++)
    {
       if((*it).second>1)
       {
          count ++;
  
          cout << (*it).first << ": " << (*it).second << "\t";

          if(count%6==0)
          cout << endl;
       }
    }
    cout << endl;
 }
}

Partiendo del programa y del un fichero con el texto cifrado "cipher.txt" realizamos el analisis de frecuencias:

$ g++ freq.cpp
$ ./a.out cipher.txt 3
-- FREQ SIZE 1 --
!: 4    #: 7    %: 3    1: 6    2: 10   3: 3
4: 2    5: 6    6: 6    >: 3    ?: 2    _: 6
|: 3

-- FREQ SIZE 2 --
15: 2   16: 3   2>: 3   3#: 3   5|: 2   6_: 2
>2: 2   |2: 2

-- FREQ SIZE 3 --
16_: 2  2>2: 2

Si observamos el análisis de frecuencias podemos ver que los símbolos que más se repiten son '2' y '#', seguidos de '_', '1', '5' y '6'. Por lo que siguiendo la distribución de porcentajes frecuentes es probable que se correspondan con las letras 'a', 'e', 'i', etc.
Es importante tener en cuenta que esto solo nos da una pista de cuál podría ser el valor de cada símbolo, pero no nos lo dice de forma exacta. Por este motivo será necesario probar varias hipótesis.

Empezaremos suponiendo que '2' corresponde a 'e' y '#' corresponde a 'a'. Si nuestra hipótesis falla, continuaremos probando al revés.
Sustituimo en el texto cifrado:

3A 16_@!5?6A=_A E> E3 A6!E |E E>16_$_6 15% 13A7E >E16E!A 5 |E /% 45|5 E%_?4A!_15

Observando el principio del texto cifrado "3A" y la cuarta palabra "E3" deducimos que '3' corresponde a la letra 'L'. Sustituimos de nuevo.

LA 16_@!5?6A=_A E> EL A6!E |E E>16_$_6 15% 1LA7E >E16E!A 5 |E /% 45|5 E%_?4A!_15

También pueden resultar buenas pistas la tercera palabra "E>" y la sexta "|E". Estas nos indican que ">" podría corresponder a 'S' o 'N', y '|' probablemente corresponderá a 'D'. Vea la frecuencia de grupos de dos letras.
Además, si nos basamos en las suposiciones anterioriores, el grupo '/%' que corresponde a una palabra de dos letras que no contiene ni 'A' ni 'E'. Será pues una de las siguientes: NO, UN, SU, LO, SI, MI, ...

También es una buena pista el '5' solitario, que muy probablemente corresponderá a una 'y' o una 'o'. Pero viendo en la octava palabra '15%' deducimos que dificilmente corresponderá a una 'Y'.

En base a las observaciones anteriores, una buena hipotesis podría corresponder a las siguientes sustituciones: '5' por 'o', '|' por 'D' y '>' por 'S'.

LA 16_@!O?6A=_A ES EL A6!E DE ES16_$_6 1O% 1LA7E SE16E!A O DE /% 4ODO E%_?4A!_1O

Llegados a este punto, más de unos sería capaz de resolver el mensaje utilizando solamente su imaginación. Pero en lugar de dar la solución, vamos a explorar otra técnica interesante. Esta corresponde a atacar las palabras sin descifrar con un diccionario. Como ejemplo usaremos una lista de palabras en castellano que se puede descargar de:

http://lemarios.olea.org/lemario-espanol-2002-10-25.txt.gz

NOTA: Esta lista contiene acentos y ñ, que es recomendable sustituir para poder seguir los siguientes pasos.


Después de descargar y descomprimir la lista de palabras estudiemos que opciones tenemos para acabar de descifrar el mensaje. Una palabra que tiene posibilidades es '1LA7E', una palabra de 5 letras de las cuales conocemos tres. Tambien es interesante atacar la palabra que viene a continuación 'SE16E!A'.

Podemos hacerlo con dos sencillos comandos grep:

$ grep "^.la.e$" lemario-espanol-2002-10-25.txt
alabe
clase
clave
glase
llave
olaje
$ grep "^se..e.a$" lemario-espanol-2002-10-25.txt
secreta
secuela
segueta
septena
serreta

Sin duda, las palabras que buscamos son "CLAVE SECRETA". Así que continuamos con la sustitución:

LA CR_@TO?RA=_A ES EL ARTE DE ESCR_$_R CO% CLAVE SECRETA O DE /% 4ODO E%_?4AT_CO

La última palabra puede confundirnos, pero está claro cuál es la segunda. En cualquier caso:

$ grep "^cr..to.ra..a$" lemario-espanol-2002-10-25.txt
criptografia.
$ grep "^e....at.co$" lemario-espanol-2002-10-25.txt
enigmatico
enzimatico
estomatico

Con lo que la resolución del mensaje es trivial:

"La criptografia es el arte de escribir con clave secreta o de un modo enigmatico"


Finalmente el mensaje ha quedado descifrado, pero hay que tener en cuenta que aquí no se han expuesto todas las posibilidades. Es normal, cuando se inicia el criptoanálisis, que se tomen algunas hipótesis incorrectas. En estos casos, no queda más remedio que volver a empezar.


Referencias:
- Cryptanalysis a study of ciphers and their solution. Helen Fouché Gaines.

Tres cartas de Zodiac fueron recibidas por el Vallejo Times Herald, el San Francisco Chronicle y el San Francisco Examiner el 1 de agosto de 1969. En ellas Zodiac se hacía responsable de tres asesinatos e incluía un criptograma que supuestamente contenía su identidad. En dichas cartas se exigía su impresión en primera plana, o de lo contrario mataría a una docena de personas ese mismo fin de semana.

El 8 de agosto de 1969, Donald y Bettye Harden descifraron el criptograma que debía contener la identidad de Zodiac. No era así.

I LIKE KILLING PEOPLE BECAUSE IT IS SO MUCH FUN IT IS MORE FUN THAN KILLING WILD GAME IN THE FORREST BECAUSE MAN IS THE MOST DANGEROUS ANAMAL OF ALL TO KILL SOMETHING GIVES ME THE MOST THRILLING EXPERENCE IT IS EVEN BETTER THAN GETTING YOUR ROCKS OFF WITH A GIRL THE BEST PART OF IT IS THAT WHEN I DIE I WILL BE REBORN IN PARADICE AND ALL THE I HAVE KILLED WILL BECOME MY SLAVES I WILL NOT GIVE YOU MY NAME BECAUSE YOU WILL TRY TO SLOI DOWN OR STOP MY COLLECTING OF SLAVES FOR MY AFTERLIFE EBEORIETEMETHHPITI

La historia que rodea al asesino está llena de incógnitas, desde su identidad hasta la solución de ciertos criptogramas. Por ejemplo, el criptograma mostrado al principio, conocido como criptograma 340, continúa sin resolver.

La reciente película "Zodiac" de David Fincher narra la historia de este conocido asesino en serie.