¿Qué es la criptografía de clave privada?

Este curso cuenta cómo se cifra de verdad un mensaje con una clave secreta compartida: desde la libreta de un solo uso, un cifrado perfecto pero impracticable, hasta AES, el estándar de cifrado actual. Hoy estamos en el punto de partida: ¿qué es exactamente un cifrado de clave privada y qué se le puede pedir? Si has leído cómo se rompe un cifrado sin la clave o por qué funciona RSA, ya has visto el otro lado de la moneda. Aquí empezamos por el principio.

La idea

Tres personajes. Alicia quiere enviar un mensaje a Bernardo. Eva (en inglés, Alice, Bob y Eve) escucha el canal: puede leer todo lo que pasa entre ellos, pero no tocarlo. Si Alicia envía el mensaje tal cual, Eva lo lee. Así que Alicia lo cifra antes de enviarlo, y Bernardo lo descifra al recibirlo.

Para eso hace falta que Alicia y Bernardo compartan algo que Eva no sepa: una clave. Alicia y Bernardo usan la misma clave, la que cifra y la que descifra. De ahí el nombre: cifrado de clave privada o, dicho de otro modo, cifrado simétrico. A partir de ahora usaremos los dos nombres.

Es lo mismo que una caja fuerte con una sola llave: la copia Alicia y la copia Bernardo. Quien tenga la llave, abre.

Definición

Un cifrado simétrico consta de dos funciones:

• Cifrar: toma un mensaje $m$ (el texto en claro) y una clave $k$ y produce un criptograma $c = E_k(m)$ (también se dice texto cifrado).
• Descifrar: toma el criptograma y la misma clave y devuelve el mensaje: $m = D_k(c)$.

La condición de corrección es que descifrar deshaga el cifrado, para cualquier clave $k$ y cualquier mensaje $m$:

$$D_k(E_k(m)) = m.$$

Eva ve $c$ y conoce el algoritmo, pero no $k$. Lo que queremos es que, sin $k$, $c$ no le diga nada útil sobre $m$.

El principio de Kerckhoffs

¿Y si Alicia y Bernardo mantienen también en secreto el algoritmo? Parece más seguro, pero es un error. En 1883, Auguste Kerckhoffs formuló en «La cryptographie militaire» (Journal des sciences militaires) lo que hoy llamamos principio de Kerckhoffs: un sistema de cifrado no debe exigir secreto, y no debe causar problema si cae en manos del enemigo. En su versión moderna: el algoritmo es público y todo el secreto está en la clave.

Las razones son prácticas:

• Un algoritmo lo usan muchos, durante años, en muchos aparatos. Tarde o temprano se filtra o alguien lo desmonta.
• Si se filtra la clave, basta con cambiarla. Si se filtra el algoritmo, hay que inventar otro.
• Un algoritmo público lo revisan miles de expertos. Uno secreto, solo quien lo diseñó. Es lo que pasará con AES, que se eligió en un concurso abierto (lección 10).

Espacio de claves y fuerza bruta

Si Eva conoce el algoritmo, tiene siempre un ataque posible: probar todas las claves hasta que una descifre algo con sentido. Se llama fuerza bruta o búsqueda exhaustiva. El número de claves posibles es el espacio de claves.

El César. Es el cifrado más sencillo que existe: cada letra se desplaza $k$ posiciones en el alfabeto. Con las 26 letras del alfabeto, hay 26 claves ($k = 0$ no cifra nada, pero cuenta). Alicia cifra HOLA con $k=3$ y obtiene KROD. Eva no necesita ser lista: prueba las 26 claves.

$k$	descifrado de KROD
0	KROD
1	JQNC
2	IPMB
3	HOLA
4	GNKZ

(y así hasta $k=25$). Solo una tiene sentido. En unos segundos a mano, Eva ha leído el mensaje.

Repaso Potencias de 2

$2^{10} = 1024$, que es casi mil. Por eso $2^{10}$ es «unos mil», $2^{20}$ «un millón» y $2^{30}$ «mil millones». Cada 10 bits más son unos tres ceros más. Un año tiene unos $3{,}16 \cdot 10^{7}$ segundos.

Claves de 56 y de 128 bits. Una clave de $b$ bits da $2^b$ claves posibles. Dos casos que veremos en el curso:

• DES usa claves de 56 bits: $2^{56} = 72\,057\,594\,037\,927\,936$ claves, unos $7{,}2 \cdot 10^{16}$.
• AES-128 usa claves de 128 bits: $2^{128} \approx 3{,}4 \cdot 10^{38}$ claves.

¿Cuánto tarda Eva en recorrerlas? Depende de su velocidad. Supongamos, como hipótesis de cálculo y no como dato de ningún aparato real, un ordenador que prueba mil millones de claves por segundo ($10^9$ por segundo). Probar todas las claves de 56 bits llevaría

$$\frac{2^{56}}{10^9} \approx 7{,}2\cdot 10^{7}\ \text{segundos} \approx 2{,}3\ \text{años}.$$

Con claves de 128 bits:

$$\frac{2^{128}}{10^9} \approx 3{,}4\cdot 10^{29}\ \text{segundos} \approx 1{,}1\cdot 10^{22}\ \text{años}.$$

En la práctica, Eva encuentra la clave antes de acabar: de media, a mitad del recorrido. Eso no cambia el orden de magnitud.

Si Eva dispusiera, también hipotéticamente, de una máquina mil millones de veces más rápida ($10^{18}$ claves por segundo), los 56 bits caerían en menos de una décima de segundo (unos $0{,}07$ s), pero los 128 bits seguirían necesitando unos $1{,}1\cdot 10^{13}$ años. Aquí está toda la gracia: cada bit de clave que añades duplica el trabajo de Eva. Entre 56 y 128 bits hay un factor $2^{72}\approx 4{,}7 \cdot 10^{21}$.

Ojo: que la fuerza bruta sea inviable no demuestra que el cifrado sea seguro. Un algoritmo malo puede caer mucho antes que recorriendo todas las claves. Lo mínimo que se le pide a un cifrado es que ningún ataque conocido sea mucho mejor que probar todas las claves.

El problema que no resuelve

Todo lo anterior supone que Alicia y Bernardo ya comparten la clave. ¿Cómo la acuerdan? Si Alicia se la envía por el canal que Eva escucha, Eva la copia. Si quedan en persona, funciona, pero no escala: una web que atiende a millones de usuarios no puede citarse con cada uno. Es el problema de la distribución de claves.

Su solución fue la criptografía de clave pública. En RSA cada persona tiene una clave pública, que puede ver cualquiera, y otra privada, que solo conoce ella. El intercambio de claves de Diffie y Hellman permite a dos personas que no se han visto nunca acordar una clave secreta compartida hablando a la vista de todos. En ambos casos las operaciones son caras.

De ahí el reparto habitual de tareas:

1. La criptografía asimétrica (clave pública) sirve para acordar una clave $k$ al comienzo.
2. La criptografía simétrica cifra todo lo demás con esa $k$: es mucho más rápida, y es la que este curso estudia.

No compiten: se complementan.

El plan del curso

• Lección 2: la libreta de un solo uso, un cifrado perfecto que exige una clave tan larga como el mensaje.
• Lecciones 3 y 4: los cifrados de bloque, el compromiso práctico, y las redes de Feistel.
• Lecciones 5 a 8: DES, el estándar de 1977, y cómo cayó por su clave corta.
• Lecciones 9 a 12: el cuerpo de 256 elementos y AES, el estándar actual.
• Lección 13: los modos de operación, que convierten un cifrado de bloque en algo útil.

Ejemplo resuelto

Cifremos con el César y descifremos como lo haría Eva, y luego contemos esfuerzo.

Alicia quiere enviar CHAO con $k=5$. Desplaza cada letra cinco posiciones: C→H, H→M, A→F, O→T. El criptograma es $c=$ HMFT. Bernardo, que conoce $k=5$, desplaza cinco hacia atrás y recupera CHAO.

Eva, que solo ve HMFT y sabe que el algoritmo es un César, prueba las 26 claves. Con $k=5$ le sale CHAO, una palabra; las otras 25 dan cosas como GLES (con $k=1$). Basta una mirada para elegir. Coste: 26 intentos.

Compara con una clave de 40 bits, a la velocidad hipotética de $10^9$ claves por segundo: $2^{40} = 1\,099\,511\,627\,776$ claves son $1099{,}5$ segundos, unos 18 minutos. Con 56 bits, 2,3 años; con 64 bits, unos 585 años ($2^{64}/10^9$ segundos). Cada paso de 8 bits multiplica el tiempo por 256.

Ejercicios

Ejercicio 1

Eva intercepta GDGR y sabe que es un César. Prueba claves desde $k=1$ hasta dar con una palabra.

Ver la solución

Descifrar con $k$ es desplazar cada letra $k$ posiciones hacia atrás. Con $k=1$ sale FCFQ; con $k=2$, EBEP; con $k=3$, DADO. La clave es 3 y el mensaje, DADO. Comprobación: D→G, A→D, D→G, O→R.

Ejercicio 2

A la velocidad hipotética de $10^9$ claves por segundo, ¿cuántos bits de clave hacen falta como mínimo para que recorrer todas las claves lleve más de mil años?

Ver la solución

Mil años son unos $3{,}16\cdot 10^{10}$ segundos, que dan para unas $3{,}16\cdot 10^{19}$ claves. Con 64 bits, $2^{64}\approx 1{,}8\cdot 10^{19}$ claves, se queda corto (unos 585 años). Con 65 bits, $2^{65}\approx 3{,}7\cdot 10^{19}$ claves, basta (unos 1.170 años). Hacen falta 65 bits.

Ejercicio 3

Si un día se duplica la velocidad de los ordenadores de Eva, ¿cuántos bits de clave hay que añadir para recuperar la seguridad que había? ¿Y si se multiplica por 1024?

Ver la solución

Cada bit de más duplica el número de claves. Si Eva va el doble de rápido, con un solo bit más Eva tarda lo mismo que antes. Si va $1024 = 2^{10}$ veces más rápido, hacen falta 10 bits más.

En resumen

• Un cifrado simétrico usa la misma clave para cifrar y descifrar: $c = E_k(m)$, $m = D_k(c)$, y $D_k(E_k(m)) = m$.
• Principio de Kerckhoffs (1883): el algoritmo es público y el secreto está solo en la clave.
• La fuerza bruta prueba todas las claves: 26 en el César, $2^{56}$ en DES, $2^{128}$ en AES-128. Cada bit de clave duplica el trabajo.
• El cifrado simétrico no resuelve cómo repartir la clave: eso lo hace la criptografía de clave pública, y se usan juntas.
• Plan del curso: libreta de un solo uso, cifrados de bloque, DES, AES y modos de operación.

Siguiente lección: XOR y la libreta de un solo uso