Criptografía de clave privada

  • Pere Cruells

  • Germán Sáez

PID_00274108
Tercera edición: septiembre 2020
© de esta edición, Fundació Universitat Oberta de Catalunya (FUOC)
Av. Tibidabo, 39-43, 08035 Barcelona
Autoría: Pere Cruells, Germán Sáez
Producción: FUOC
Todos los derechos reservados
Ninguna parte de esta publicación, incluido el diseño general y la cubierta, puede ser copiada, reproducida, almacenada o transmitida de ninguna forma, ni por ningún medio, sea este eléctrico, mecánico, óptico, grabación, fotocopia, o cualquier otro, sin la previa autorización escrita del titular de los derechos.

1.La criptografía de clave privada: cifrado César

1.1.Introducción

Con la generalización de las comunicaciones electrónicas y la popularización del uso de Internet, la necesidad de seguridad en las comunicaciones ha tomado una gran importancia. La criptografía nació como un arte, utilizada por unos pocos en comunicaciones que tenían una motivación militar o diplomática. Con el tiempo ha pasado a ser una técnica científica utilizada (inconscientemente) por muchos para comunicarse de forma privada e incluso para proteger derechos como son la protección del copyright.
Actualmente, se define la criptografía como la ciencia y el arte de utilizar matemáticas para asegurar una transmisión segura y auténtica de la información. A menudo, se refiere como principal cometido de la criptografía el permitir que dos personas se puedan comunicar de forma segura en un canal inseguro. Se entiende por canal inseguro un canal por donde se transmite la información y en el que terceras personas pueden escuchar lo que se está transmitiendo e, incluso, interceptar e introducir nuevos mensajes. La solución adoptada desde antiguo para poderse comunicar es la de no enviar el mensaje de forma desprotegida, sino de forma cifrada, es decir, de forma ininteligible. De este modo, se espera que un posible oponente no pueda entender lo que se está transmitiendo por el canal. También la criptografía se ocupa de la autenticidad de la comunicación, es decir, de la seguridad de que quien dice que envía el mensaje ciertamente lo sea.
m5e1_rec1.gif
Veamos cuál es el paradigma típico de una comunicación. Alicia quiere enviar un mensaje a Blas por un canal inseguro. Nuestro canal inseguro puede ser cualquier vía usual de comunicación, como una línea telefónica, una línea de fibra óptica, vía satélite, etc.
Óscar es un oponente que quiere escuchar la comunicación para saber qué envía Alicia a Blas. Óscar incluso se puede plantear no sólo escuchar la comunicación, sino suplantarla, es decir, cambiar el contenido de la comunicación o enviar un mensaje nuevo como si fuera Alicia quien lo envía.
Para que Óscar no pueda entender lo que se están enviando Alicia y Blas por el canal, llegan al acuerdo de enviarlo cifrado, es decir, de alguna manera que sólo ellos puedan entenderlo. Por tanto, el problema de Óscar será intentar descifrar lo que se envía por el canal. La habilidad de Alicia y Blas en ponérselo difícil a Óscar será crucial para asegurar la seguridad en la comunicación. Sin embargo, no sólo se considera importante la seguridad en la comunicación. Pensemos que si Blas recibe un mensaje por el canal, no sabrá si es de Alicia o de Óscar. Ésta es la segunda de las preocupaciones de la criptografía, la autenticidad de la comunicación.
La criptología tiene un campo mucho más amplio de actuación que el simple envío de un mensaje de forma secreta y auténtica. Las técnicas de almacenamiento, de compartición, etc. de la información son puntos clave en su estudio. Tampoco es la interacción entre dos personas la única preocupación, sino que se extienden las técnicas a colectivos de personas, o a colectivos de máquinas. Pensemos en la transmisión de datos privados de un cliente por una línea telefónica que conecta un cajero bancario con el ordenador de la sede central del banco. O pensemos en el almacenamiento seguro de información delicada para la seguridad, la seguridad de la televisión de pago, etc.
Clásicamente, se divide la criptografía en criptología y en criptoanálisis. La criptología se ocupa de la transmisión de los mensajes de forma indescifrable para todo oponente ajeno a la comunicación. Cuando se obtiene un método para poder descifrar los mensajes, se dice que se ha roto el criptosistema. El criptoanálisis trata de romper un criptosistema.
Hay dos fechas claves en la evolución histórica de la criptografía que marcan la división en el uso y en el carácter que se le ha dado: 1949 y 1976. En el año 1949, C.E. Shannon publica las bases matemáticas de la criptografía como ciencia y en el año 1976 la introducción de la criptografía de clave pública por parte de W. Diffie y M.E. Hellman.
m5e1_rec2.gif
En 1949 el matemático e ingeniero eléctrico Claude Elwood Shannon funda la criptografía científica. La criptografía se utilizaba como herramienta en las comunicaciones en guerras y en relaciones diplomáticas. Su máxima sofisticación se había conseguido durante la Segunda Guerra Mundial, cuando los alemanes utilizaban la máquina "Enigma" para poder comunicarse de forma segura y los ingleses descifraban los mensajes transmitidos por medio de unas réplicas de la máquina "Enigma" y de "Colossus", el primer ordenador programable, el auténtico precursor de nuestros ordenadores actuales. Al frente de estas dos vías de descifrado de los mensajes de los alemanes se situaba el matemático Alan Turing, célebre por su trabajo en estas dos máquinas, así como en el campo de la lógica matemática, especialmente en la fundamentación del concepto de computable matemáticamente.
m5e1_rec3.gif
m5e1_rec4.gif
Sin embargo, no fue éste el único momento de la historia donde se han utilizado sistemas criptográficos. Sirva como ejemplo que en el siglo V a. C., en tiempos de la Grecia clásica, se utilizaba el "scitalo spartano" que posibilitaba la comunicación segura entre dos personas. Las dos personas disponían de dos bastones idénticos denominados "scitalos". El emisor enrollaba alrededor del bastón una cinta de pergamino o papiro y escribía el mensaje a lo largo de éste. Una vez escrito el mensaje, se desenrollaba la cinta y se enviaba al destinatario. Este último recibía una tira de escritura ininteligible que debía enrollar en su bastón para así poderla entender. Con cualquier otro bastón de una medida diferente no era posible reconstruir el mensaje.
m5e1_rec5.gif
En 1949, la fundamentación de la criptografía científica está formulada, pero el impulso más certero fue dado por W. Diffie y M.E. Hellman en el año 1976, cuando publicaron un artículo que revolucionó el mundo de la criptografía. En este artículo se proponía el modelo general de lo que conocemos actualmente como criptografía de clave pública. Un sistema criptográfico de clave privada se caracteriza por el uso de una clave secreta acordada entre el emisor y el receptor, mientras que en un sistema criptográfico de clave pública, cada usuario dispone de dos claves: una que hace pública a todo el mundo y otra que sólo es conocida por él. El método del "scitalo spartano" era un método de clave privada en el que ésta estaba formada por dos bastones idénticos. Como ventaja principal de los sistemas criptográficos de clave pública, hay que destacar que no es necesario que el emisor y el receptor se pongan de acuerdo previamente sobre qué clave van a utilizar.
m5e1_rec6.gif
m5e1_rec7.gif
Actualmente, se asocia la criptografía con el establecimiento de comunicaciones seguras y auténticas entre personas en un medio electrónico. Éste es el caso del envío de un e-mail y su autentificación, tan importante, por ejemplo, en trabajo desarrollado y transmitido por medios como Internet. La firma digital de documentos es una de las aplicaciones que tiene más futuro. Con una firma digital se consigue lo mismo que con una firma manual, es decir, autentificar la autoría de un documento, un mensaje, etc. La transmisión de las llamadas telefónicas en los móviles también está protegida por medio de sistemas criptográficos. La toma de decisiones compartidas o la ejecución de un determinado proceso (por ejemplo, la activación de un arma nuclear) se protege mediante un sistema criptográfico denominado esquema para compartir secretos. El comercio electrónico abarca desde operaciones bancarias on-line hasta compras por Internet, reservas de billetes de avión, trámites fiscales, etc. El teletrabajo y el telestudio en entornos virtuales necesitan una seguridad en cuanto a la información transmitida de forma que no pueda ser leída por nadie ajeno al sistema. Además, hay que procurar los mecanismos que aseguren que la persona que dice que es la que está enviando una cierta información sea verdaderamente ella. Con el uso de tantas claves para diferentes cometidos se corre el peligro de su olvido o deterioro (a veces son muy largas y hay que almacenarlas en un dispositivo), por lo que se establecen mecanismos de recuperación de claves. El tema de la protección del copyright de los autores de un producto, ya sea un vídeo o una canción, etc. frente a copia indiscriminada es otra de las aplicaciones que tiene más actualidad en criptografía como protección de los derechos de autor de los creadores. Muchas otras actividades basan su validez en sistemas criptográficos, como por ejemplo las votaciones electrónicas y la televisión por cable o por satélite.

1.2.Sistemas de clave privada

En los sistemas criptográficos de clave privada, el emisor y el receptor comparten una única clave. Esta clave que se comparte ha sido transmitida por un canal seguro o bien ha sido acordada previamente. También son denominados de clave simétrica, ya que el mismo proceso que se utiliza para cifrar se utiliza para descifrar. El principal problema que tienen estos criptosistemas es que emisor y receptor se tienen que poner de acuerdo en qué clave se utilizarán en la comunicación. Sin embargo, por otro lado, estos sistemas criptográficos son muy apreciados por su velocidad de cifrado.
Normalmente, denotaremos un mensaje para transmitir con la letra m, y el mensaje cifrado con la letra c. Supongamos que Alicia quiere enviar un mensaje a Blas por medio de una clave secreta k previamente acordada. Alicia dispone para esta clave prefijada de una aplicación Ek, que asigna a cada mensaje m el mensaje cifrado c = Ek (m):
Ek: {mensajes} → {mensajes cifrados}
Blas dispone de una función Dk para descifrar el mensaje c de la siguiente manera: m = Dk (c). Por tanto, la principal característica que deben verificar las funciones de cifrado y descifrado es que:
m = Dk (Ek (m))
para todo mensaje m.
Veamos un primer ejemplo de criptosistema de clave privada para ilustrar todo el proceso: el algoritmo de cifrado de Julio César.
Cifrado César
Dada una clave k del conjunto {1,2,3,...,26} el cifrado de un mensaje lo haremos carácter a carácter y consistirá en cambiar cada carácter por el que está k unidades más adelante en el alfabeto.

A

B

C

D

E

F

G

H

I

J

K

L

M

N

Ñ

O

P

Q

R

S

T

U

V

W

X

Y

Z

 
Por ejemplo si k = 2 el cifrado del carácter H es el carácter J, el cifrado del carácter O es el carácter Q, el cifrado del carácter L es el carácter N y el cifrado del carácter A es el carácter C. Con la notación introducida escribiremos:
E2(H) = J
E2(O) = Q
E2(L) = N
E2(A) = C
Puesto que este proceso de cifrado se realiza carácter a carácter, también tenemos que:
E2 (HOLA) = JQNC
Si por ejemplo hemos recibido el mensaje cifrado c = ÑCVGU, el descifrado se hace cómodamente cambiando cada carácter por el que ocupa dos posiciones anteriores en el alfabeto. Así, se descubre de forma fácil que el mensaje enviado es:
m = D2(ÑCVGU) = MATES.
El método de César debe su nombre a que Julio César utilizó este método con la clave secreta k = 3.
m5e1_rec18.gif
Actividad
Ejercicio 1
Cifrad con el sistema de clave privada de César y clave secreta k = 5 el mensaje m = VOYALCINE (si al buscar el cifrado de un carácter se llega al final del alfabeto, se sigue la cuenta por el principio del alfabeto). ¿Qué nos han contestado si el mensaje recibido es c = DTRTATD?
Ejercicio 2
Encontrad el mensaje cifrado y sin cifrar, así como la clave secreta utilizada si hemos interceptado parcialmente una comunicación y también sabemos parcialmente su descifrado. Ek (E – –E – RE – O) = –WW – GV – X – (el guión "–" sirve para indicar que no se conoce el carácter que va en la posición correspondiente).
Un ejemplo literario y cinematográfico muy conocido es el del nombre HAL del ordenador que aparece en la novela 2001 de Arthur C. Clarke y en la correspondiente película dirigida por Stanley Kubrick, "2001 una odisea en el espacio". No es nada complicado obtener el nombre de una famosa empresa si sabemos que el nombre del maléfico ordenador (HAL) es el cifrado con k = 26 del nombre de la empresa.
Puesto que todos estos cifrados se automatizan por medio del uso de ordenadores, es necesario reducir el cálculo con caracteres a cálculos implementables en estas máquinas. Así, en primer lugar, necesitamos asociar a cada carácter un número. Para hacer esto, hay más de una opción estándar que detallaremos más adelante. Nos interesa que los números que asociemos a los caracteres se puedan manipular por medio de operaciones. Por este motivo, en la siguiente sección se consideran los conjuntos de números enteros modulares debidos a Karl F. Gauss (1777-1855), llamado el Príncipe de la Matemáticas por la trascendencia de sus trabajos en esta materia.
m5e1_rec19.gif

1.3.Aritmética modular

Un conjunto de números que resulta muy útil para el cálculo en sistemas criptográficos es el de los enteros modulares. Estos conjuntos se consideran de forma natural en la vida cotidiana cuando se calculan tiempos en notación de doce horas o de veinticuatro horas. Antes de dar una definición más formal, os damos unos ejemplos para que veáis lo que queremos decir:
a) En notación de doce horas: los números posibles son 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Las operaciones se efectúan con el convenio de que cuando nos pasamos por un bloque de doce horas, este bloque se elimina. Por ejemplo, si son las diez y queremos saber qué hora será dentro de cinco horas, a diez sumamos cinco horas, que da como resultado las quince horas, pero restamos un bloque de doce horas y obtenemos las tres horas. Estos cálculos quedan representados en el diagrama siguiente:
m5e1_rec19a.gif
Lo mismo se hace con la multiplicación: si, por ejemplo, tenemos que hacer tres sesiones de estudio de dos horas cada una y son las once, entonces acabaremos a las 11 + 3 · 2 = 11 + 6 = 17, pero el resultado se dice que es 17 – 12 = 5.
b) En notación de veinticuatro horas: los números posibles son 1, 2, 3, ..., 24. En este caso, las operaciones se hacen con el convenio de que cuando nos pasamos de veinticuatro horas, se elimina este bloque. Por ejemplo, si una jornada de trabajo de siete horas se empieza a las diecinueve horas, entonces acaba a las veintiséis que, obviando el bloque de veinticuatro horas, nos da que acaba a las dos. Lo mismo ocurre con la multiplicación.
c) Este tipo de cálculos en los que se eliminan del resultado los múltiplos de una cierta base también se hacen cuando se trabaja con ángulos. Las operaciones se hacen con los números de la forma usual, pero al final se resta el número de vueltas que sobran. Por ejemplo, si a 355° se le suma 200°, se dice que el resultado es 195°, ya que se le resta una vuelta (360°) al resultado de efectuar la suma (355° + 200° = 555°).
La cantidad base establecida que se resta cuando se supera se denomina módulo. Así, en el caso de la notación en doce horas, el módulo es 12, y en el caso de la notación en veinticuatro horas, el módulo es 24. Para el cálculo de ángulos en notación sexagesimal se utiliza como módulo 360.
En general, se considera a partir de un número entero m el conjunto de los enteros modulo m como el conjunto:
Zm = {0, 1, 2, 3,..., m – 1}
con la suma usual y la multiplicación usual pero con el convenio de que cuando nos pasamos de m restamos los múltiplos de m necesarios, de forma que el resultado esté comprendido entre 0 y m – 1. En el cálculo cotidiano con horas es más usual tomar los números entre 1 y m.
Así como los números enteros se suelen representar como puntos marcados en una recta:
m5e1_rec21.gif
los enteros módulo m se pueden representar encima de una circunferencia:
m5e1_rec22.gif
Para distinguir los cálculos con enteros modulares del cálculo con enteros normales, utilizaremos el símbolo ≡ que leeremos "es congruente", en lugar de "es igual". Además, para indicar qué módulo m estamos utilizando, pondremos al final la anotación de su valor como "mod m" y leeremos "módulo m". Veamos unos ejemplos:

  • 7 + 8 ≡ 3 mod 12, ya que 7 + 8 = 15, pero restando 12 nos da 3;

  • 7 · 4 ≡ 4 mod 24, ya que 7 · 4 = 28, pero restando 24 nos da 4;

  • 5 · 10 ≡ 2 mod 24, ya que 5 · 10 = 50, pero restando dos veces 24 nos da 2;

  • 6 · 9 ≡ 4 mod 10, ya que 6 · 9 = 54, pero restando cinco veces 10 nos da 4.

Por tanto, una operación en Zm se realiza en el conjunto de los números enteros, Z y después se reduce a Zm por medio de una resta de múltiplos de m. El proceso de reducción de un número a a Zm por medio de una resta de múltiplos de m se denomina reducción modular. Una forma de hacer la reducción modular es calcular el resto de la división del resultado entre m, ya que el resto nos da lo que sobra de considerar cuántos múltiplos de m aparecen en el resultado.
Veamos más ejemplos:

  • 4 + 3 ≡ 2 mod 5, ya que 4 + 3 = 7 y el resto de la división de 7 entre 5 es 2;

  • 8 · 9 ≡ 2 mod 7, ya que 8 · 9 = 72 y el resto de la división de 72 entre 7 es 2.

Actividad
Ejercicio 1
Calculad

  • 19 + 17 mod 20

  • 8 · 9 mod 10

  • 8 · 9 mod 20

  • 5 + 4 mod 6

  • 6 · 3 mod 4

  • 9 · 7 mod 13

Ejercicio 2
Calculad
La suma definida en Zm verifica las propiedades:

  • asociativa: para cualesquiera enteros modulares x, y, z tenemos que (x + y) + z = x + (y + z);

  • existencia de elemento neutro: existe el elemento neutro 0, que verifica que x + 0 = 0 + x = x para todo entero modular x;

  • existencia de elemento opuesto: para todo entero modular x existe su opuesto - x, que verifica: x + (–x) = –x + x = 0; también se denomina elemento inverso respecto de la suma.

Por tanto, Zm con la suma se trata de un grupo. Además, la suma presenta la propiedad conmutativa:

  • conmutativa: para cualesquiera enteros modulares x, y tenemos que x + y = y + x.

Todas estas propiedades se resumen diciendo que Zm con la suma es un grupo conmutativo. Veamos un ejemplo de cálculo de la tabla de la suma:

Tabla de la suma en Z4

+

0

1

2

3

0

0

1

2

3

1

1

2

3

0

2

2

3

0

1

3

3

0

1

2
Se observa, como hemos dicho antes, que el elemento neutro es el 0. Los elementos opuestos también se pueden apreciar en la tabla: el opuesto de 0 es el 0, el opuesto de 1 es 3, el opuesto de 2 es el 2 y el opuesto de 3 es el 1. En general, el opuesto de k en Zm es m – k.
Con el producto definido en Zm no tenemos tan buenas propiedades como con la suma, ya que, en general, sólo se verifica:

  • asociativa: para cualesquiera enteros modulares x, y, z tenemos lo siguiente: (x · y) · z = x · (y · z);

  • existencia de elemento neutro: existe el elemento neutro 1, que verifica que x · 1 = 1 · x = x para todo entero modular x;

  • conmutativa: para cualesquiera enteros modulares x, y tenemos lo siguiente: x · y = y · x.

Las dos operaciones conjuntamente verifican:

  • distributiva: para cualesquiera enteros modulares x, y, z tenemos lo siguiente: x · (y + z) = x · y + x · z;

Para resumir las propiedades que verifica Zm con la suma y el producto, se dice que Zm es un anillo conmutativo con unidad.
Veamos un ejemplo de cálculo de la tabla del producto:

Tabla del producto en Z4

·

0

1

2

3

0

0

0

0

0

1

0

1

2

3

2

0

2

0

2

3

0

3

2

1
Se observa, como hemos dicho antes, que el elemento neutro es el 1. Los elementos inversos (u opuestos) respecto del producto no existen siempre. Se pueden ver en la tabla que el inverso de 0 no existe, el inverso de 1 es 1, el inverso de 2 no existe y el inverso de 3 es 3.
En general, el inverso de un número k de Zm existirá cuando el máximo común divisor de k y de m sea 1 (es decir, cuando k y m no tengan ningún factor en común). Así, cuando m sea un número primo, existirá inverso para todo elemento diferente de 0. En este caso, se dice que Zm con la suma y el producto, es un cuerpo.
Como ejemplo de cuerpo, calculemos la tabla de la suma y del producto de Z5:

+

0

1

2

3

4

0

0

1

2

3

4

1

1

2

3

4

0

2

2

3

4

0

1

3

3

4

0

1

2

4

4

0

1

2

3

·

0

1

2

3

4

0

0

0

0

0

0

1

0

1

2

3

4

2

0

2

4

1

3

3

0

3

1

4

2

4

0

4

3

2

1
Como se puede apreciar, todos los elementos excepto el 0 tienen inverso respecto del producto: el inverso de 1 es 1, el inverso de 2 es 3, el inverso de 3 es 2 y el inverso de 4 es 4.
Actividad
Ejercicio 1
Calculad las tablas de la suma y del producto en Z8. Enumerad los opuestos respecto de la suma de cada elemento y los inversos respecto del producto, cuando existan.
Ejercicio 2
Calculad las tablas de la suma y del producto en Z7. Enumerad los opuestos respecto de la suma de cada elemento y los inversos respecto del producto cuando existan.
Un último comentario sobre los enteros modulares es que cuando se utiliza el conjunto Z2 = {0, 1} de los enteros módulo 2, se dice que estamos trabajando con bits (el 0 y el 1). La suma de enteros en este conjunto se denomina "o exclusiva (XOR)" y se representa con el símbolo ⊕. De hecho, también un bit es la unidad mínima de almacenamiento en la memoria de un ordenador, y esta operación con los bits es una de las que aparecen implementadas en el hardware de los ordenadores.
Así, la tabla de sumar en Z2, que es la tabla de la "o exclusiva", será:

+

0

1

0

0

1

1

1

0

1.4.Cifrado César con aritmética modular

El uso de los enteros modulares es muy útil cuando se quiere dar una estructura algebraica a un conjunto finito. Por ejemplo, en el sistema de clave privada de César se numeran todas las letras del alfabeto de 0 hasta 26:

A

B

C

D

E

F

G

H

I

J

K

L

M

N

0

1

2

3

4

5

6

7

8

9

10

11

12

13

Ñ

O

P

Q

R

S

T

U

V

W

X

Y

Z

 

14

15

16

17

18

19

20

21

22

23

24

25

26

 
Por tanto, a partir de ahora identificaremos cada símbolo del alfabeto con su correspondiente número, lo que nos permitirá hacer operaciones con los símbolos del alfabeto. Así, si la clave privada de un criptosistema tipo César es k = 5, entonces la transformación de cifrado y descifrado se puede escribir así:
E5(m) = m + 5 mod 27
D5(m) = m – 5 mod 27
y por ejemplo, el cifrado del mensaje VOY se calcula:
E5(V) = E5 (22) = 22 + 5 = 0 mod 27 = A
E5(0) = E5(15) = 15 + 5 = 20 mod 27 = T
E5(Y) = E5(25) = 25 + 5 = 3 mod 27 = D
Así, podemos concluir que E5 (VOY) = ATD.
Si por ejemplo hemos recibido E5(m1m2) = DT, para descifrar procederemos de la siguiente forma:
D5(D) = D5(3) = 3 – 5 = –2 mod 27 = 25 mod 27 = Y
D5(T) = D5(20) = 20 – 5 = 15 mod 27 = 0
Por tanto, el mensaje enviado es m1m2 = YO.
Para una clave privada de cifrado k, el criptosistema César tiene como transformación de cifrado y descifrado:
Ek(m) = m + k mod 27
Dk(m) = m – k mod 27
Actividad
Cifrado César
Ejercicio 1
Utilizando el cifrado César con clave privada k = 13, cifrad vuestro nombre.
Ejercicio 2
Se ha utilizado cifrado César con clave privada k = 6 para transmitir un nombre en secreto. Se ha recibido BÑIZUX. ¿Cuál es el nombre secreto?
Ejercicio 3
Estableced claves secretas vía e-mail privado y enviad mensajes de forma pública en el foro. Indicad en el tema del mensaje a quién va dirigido. Utilizad el applet del método César.
Ejercicio 4
Intentad romper algún mensaje. Utilizad para ello el applet del método César (ir probando las diferentes claves).
Igual que se ha utilizado una transformación tan sencilla para el método César, ésta se podría haber complicado de diferentes maneras, como se muestra, por ejemplo, en el ejercicio siguiente.
Ejercicio 5
Con clave privada k = 2, utilizad las transformaciones de cifrado y descifrado Ek(m) = 2m + k mod 27, Dk (m) = 14m + 13k mod 27 para cifrar el mensaje HOLA y para descifrar el mensaje CIRFN.
Estos tipos de cifrados funcionan bien siempre que la fórmula que se utilice para cifrar sea una aplicación biyectiva, es decir, si cada letra (o número que la cifra) tiene una letra cifrada (o número) y al revés, si toda letra cifrada lo es de una única letra.
Así, se puede definir un criptosistema de clave privada utilizando una aplicación biyectiva cualquiera previamente acordada como clave privada entre dos personas que se quieren comunicar. Este tipo de criptosistema de clave privada se denomina cifrado por medio de sustituciones. Caso particular de éstos son los cifrados del método César y los del ejemplo anterior.
En la próximo apartado estudiaremos cómo los criptosistemas basados en sustituciones se pueden romper, es decir, cómo se puede conseguir descifrar los mensajes creados con ellos.

2.Criptoanálisis y otros criptosistemas de clave privada

2.1.Criptoanálisis: búsqueda exhaustiva de claves y ataque estadístico

Hemos dicho que el objetivo del criptoanálisis es descubrir la clave privada para así poder descifrar los mensajes. Cuando se utilizan métodos tan sencillos como por ejemplo el cifrado César, descubrir la clave secreta es muy fácil, ya que con sólo probar cada una de las 26 claves privadas posibles podremos encontrar el mensaje transmitido. Por ejemplo, si se ha interceptado el mensaje JXQZDLFHNP, es muy fácil descifrarlo probando las diferentes claves con que ha se ha podido cifrar. Simplemente hay que ir tratando de descifrar el mensaje con las claves k = 1, 2, 3,..., hasta que se obtenga un mensaje con sentido.
m = JXQZDKFHNP
k = 1 → IWPYCJEGMO
k = 2 → HVOXBIDFLÑ
k = 3 → GUÑWAHCEKN
k = 4 → FTNVZGBDJM
k = 5 → ESMUYFACIL
Nos hemos parado en k = 5, ya que hemos llegado a un mensaje con sentido. Por tanto, la clave con que se ha cifrado es k = 5, y el mensaje que se quería transmitir en secreto era m = ESMUYFACIL.
Este ataque criptoanalítico se denomina búsqueda exhaustiva de claves. Evidentemente, si el conjunto de claves posibles es muy pequeño, este método será muy efectivo, ¡incluso haciéndolo de forma manual! Así, en el caso del método César, el conjunto de claves posibles tiene veintiséis elementos, por lo que este método de cifrado se rompe rápidamente. Podemos cuantificar la probabilidad de acertar en un ataque de este tipo con el método César afirmando que es de 1/26, ya que el número de posibles claves para probar es de veintiséis y estamos probando una de ellas.
Probabilidad
La idea intuitiva de la probabilidad es la de cuantificar, para un suceso dado, la posibilidad de que se cumpla. La probabilidad de que se cumpla un determinado suceso se expresa por medio de un número entre 0 y 1, conviniendo que será más alto conforme el suceso sea más probable, y más bajo cuanto más improbable sea éste.
Por ejemplo, si lanzamos un dado (no trucado) al azar, los seis números pueden salir con igual probabilidad y, por tanto, si nos preguntamos por la probabilidad de que salga un 4, diremos que es 1/6, ya que hay una posibilidad (la cara del 4) de entre seis (las seis caras del dado). El mismo resultado se obtiene si nos preguntamos por la probabilidad de que salga cualquier otro número del dado. Si nos preguntamos por la probabilidad de que salga un número par, su probabilidad es de 3/6 = 1/2, ya que hay tres posibilidades (la cara del 2, la del 4 y la del 6) de entre seis (las seis caras del dado).
A veces también se dan las probabilidades en tantos por ciento, por ejemplo, la probabilidad de que salga un número par es 1/2 = 0,5, o lo que es lo mismo, un 50% de probabilidad. La probabilidad de que salga un 4 es 1/6 = 0,166666... Por tanto, es de un 16,6....%.
La probabilidad se calcula en los casos más simples por medio de la fórmula siguiente:
m5e2_rec2.gif
Esta fórmula se puede utilizar siempre que los sucesos más elementales sean equiprobables, es decir, siempre que podamos suponer que tienen la misma posibilidad de suceder. Éste es el caso del lanzamiento de un dado no trucado, ya que los sucesos más elementales (salir 1, salir 2, etc.) tienen la misma probabilidad.
En el caso del lanzamiento de un dado no trucado, si calculamos la probabilidad de que salga un 1, un 2, ..., o un 6, nos dará 6/6 = 1, la máxima de las probabilidades. Por este motivo, este suceso se denomina suceso seguro. De la misma forma, si calculamos la probabilidad de que salga un 7, la probabilidad es 0/7 = 0, ya que no existe ningún caso favorable (evidentemente, el dado tiene caras con los números 1, 2, 3, 4, 5, 6, pero no tiene el 7). Este suceso se denomina suceso imposible.
Así, la probabilidad es una aplicación que asigna a cada suceso un número entre 0 y 1 y que verifica las siguientes propiedades:
1) La probabilidad del suceso seguro es 1.
2) La probabilidad del suceso imposible es 0.
3) Si dos sucesos no pueden nunca suceder a la vez, entonces la probabilidad de que pase uno u otro es la suma de las dos probabilidades.
Un ejemplo de utilización de la tercera propiedad es el siguiente: si calculamos la probabilidad de que salga par en el lanzamiento de un dado, nos da 3/6, y si calculamos la probabilidad de que salga 3, es 1/6; por tanto, la probabilidad de que salga un número par o de que salga el número 3 será 3/6 + 1/6 = 4/6 = 2/3. Está claro que si utilizamos la fórmula de casos favorables entre casos posibles obtenemos el mismo resultado: cuatro casos favorables (el 2, 4, 6 y el 3) dividido entre seis casos posibles. En este caso, la fórmula 3 se puede aplicar porque sacar par o sacar un 3 no puede suceder nunca a la vez. Esta fórmula no se podría aplicar a los sucesos sacar par y sacar múltiplo de 3, ya que sí pueden suceder al mismo tiempo (cuando sale un 6, que es par y múltiplo de 3).
La definición moderna de probabilidad fue creada por Kolmogorov y se reduce a tomar como axiomas las propiedades 1 y 3 anteriores.
Ejercicio
Se extrae una carta de una baraja española (48 cartas). Calculad la probabilidad de:
a) obtener un caballo.
b) que la carta sea de copas.
c) que la carta sea par o de copas.
Más información sobre probabilidad en:
https://www.cut-the-knot.org/probability.shtml
En el caso de los criptosistemas de cifrado por sustitución, ya no es tan fácil romperlos por medio de una búsqueda exhaustiva de la clave, ya que en este caso, el número de claves privadas es el número de permutaciones que se pueden hacer con veintiséis elementos:
26! = 403 291 461 126 605 635 584 000 000
Por tanto, la probabilidad de acertar con la clave en un intento es de m5e2_rec3.gif, es decir, de 0 seguido de 27 ceros y después, un 25.
Permutaciones
Una permutación de cierto número de elementos es una cierta ordenación de los mismos. Por ejemplo, una permutación de las letras ABC puede ser CAB, o también BCA, etc. Para calcular el número de permutaciones que se pueden hacer con estas tres letras, nos ayudaremos por medio de un árbol. Para la primera posición podemos elegir cualquiera de las tres letras: A, B o C.
m5e2_rec4.gif
En total, tenemos tres posibilidades. Para la segunda posición, tendremos en cada uno de los tres casos anteriores dos posibilidades, ya que hemos utilizado una de las tres letras.
m5e2_rec5.gif
Con lo que tenemos 3 · 2 = 6 posibilidades. Y para la tercera posición, tendremos una sola letra en cada caso.
m5e2_rec6.gif
Con lo que tenemos 3 · 2 · 1 = 6 formas distintas de ordenar estas tres letras. Cada una de estas seis posibilidades queda reflejada en el árbol anterior siguiendo las ramas de izquierda a derecha; así, por ejemplo, la primera rama corresponde a la permutación ABC, la segunda rama corresponde a la permutación ACB, y así sucesivamente.
En el caso de querer ordenar n elementos, el número de permutaciones que podremos hacer será: n · (n – 1)·(n – 2)· ... ·3 · 2 · 1. Para abreviar esta expresión, se acostumbra a escribir n! = n · (n – 1)·(n – 2)· ... ·3 · 2 · 1, y se lee "n factorial".
Por ejemplo, si queremos contar de cuántas maneras diferentes se pueden permutar las veintiséis letras de nuestro alfabeto, obtendremos:
26! = 26 · 25 · 24 · ... · 3 · 2 · 1 = 403 291 461 126 605 635 584 000 000
De todos modos, hay otra estrategia para romperlos: el ataque estadístico. Estos ataques se basan en el hecho de que el símbolo cifrado que más se repite seguramente corresponderá con el símbolo más frecuente en la lengua original del mensaje. Así, sólo será necesario obtener un listado de las frecuencias de los caracteres originales y esperar que los símbolos que aparecen en nuestro mensaje se correspondan con frecuencias aproximadas.
Veamos un ejemplo de ataque estadístico fácilmente realizable con un procesador de textos; a continuación tenemos un texto muy interesante sobre qué es la criptografía. Al final hay un párrafo del texto cifrado cuyo descifrado hay que encontrar:
Cryptanalysis is the study of how to compromise (defeat) cryptographic mechanisms, and cryptology (from the Greek kryptós lógos, meaning "hidden word'') is the discipline of cryptography and cryptanalysis combined. To most people, cryptography is concerned with keeping communications private. Indeed, the protection of sensitive communications has been the emphasis of cryptography throughout much of its history [Kah67]. However, this is only one part of today's cryptography.
Encryption is the transformation of data into a form that is as close to impossible as possible to read without the appropriate knowledge (a key; see below). Its purpose is to ensure privacy by keeping information hidden from anyone for whom it is not intended, even those who have access to the encrypted data. Decryption is the reverse of encryption; it is the transformation of encrypted data back into an intelligible form.
Encryption and decryption generally require the use of some secret information, referred to as a key. For some encryption mechanisms, the same key is used for both encryption and decryption; for other mechanisms, the keys used for encryption and decryption are different.
Today's cryptography is more than encryption and decryption.
Authentication is as fundamentally a part of our lives as privacy. We use authentication throughout our everyday lives - when we sign our name to some document for instance - and, as we move to a world where our decisions and agreements are communicated electronically, we need to have electronic techniques for providing authentication.
Cryptography provides mechanisms for such procedures. A digital signature binds a document to the possessor of a particular key, while a digital timestamp binds a document to its creation at a particular time. These cryptographic mechanisms can be used to control access to a shared disk drive, a high security installation, or a pay-per-view TV channel.
Ç*?}@* ?&[[}#$?=%$&# $ç %{* [&ç% ç%@=$!{%/&@\=@¿ }ç* &/ ?@+]%&!@=]{+ . %\& ]*&]<* [=+ ?&[[}#$?=%* ç*?}@*<+ >+ *#?@+]%$#! %{* [*çç=!*ç ç*#% >*%\**# %{*[ . %{$ç ?=# >* ¿&#* $# ç}?{ = \=+ %{=% = %{$@¿ ]=@%+ *=¡*ç¿@&]]$#! [=+ #*¡*@ >* =><* %& ¿*?$]{*@ %{* [*çç=!*ç . \{$<* ç*?}@* ?&[[}#$?=%$&# {=ç *&#176;$ç%*¿ /&@ ?*#%}@$*ç , %{* -*+ [=#=!*[*#% ]@&><*[ {=ç ]@*¡*#%*¿ $% /@&[ >*?&[$#! ?&[[&#]<=?* . %{=#-ç %& %{* ¿*¡*<&][*#% &/ ]}><$?--*+ ?@+]%&!@=]{+ , %{* %&&<ç *&#176;$ç% %& ?@*=%* = <=@!*-ç?=<* #*%\&@- &/ ]*&]<* \{& ?=# ?&[[}#$?=%* ç*?}@*<+ \$%{ &#* =#&%{*@ *¡*# $/ %{*+ {=¿ #*¡*@ ?&[[}#$?=%*¿ >*/&@* .
Tenemos el último párrafo, que es el cifrado de un texto en inglés. Si calculamos las frecuencias que nos salen en el texto sin cifrar, obtenemos:

E

174

M

48

O

140

U

36

T

139

L

35

I

122

F

33

A

117

G

26

R

112

W

18

N

113

V

18

S

104

K

13

C

76

B

12

H

65

Q

2

P

63

J

0

D

60

X

0

Y

56

Z

0
La manera de hacer el recuento cómodamente es utilizar un procesador de textos para pedir que cada símbolo sea cambiado por sí mismo. Casi todos los procesadores informan al usuario del número de sustituciones efectuadas.
Ahora efectuamos el mismo proceso con el texto cifrado y obtenemos las frecuencias de los símbolos cifrados:

*

75

+

15

%

43

}

13

&

36

<

13

=

34

¿

10

#

30

!

10

@

28

>

9

?

28

/

8

Ç

26

\

8

$

24

¡

6

{

24

 

 

[

24

 

 

]

18

 

 
Es de esperar que entre el texto cifrado y el texto sin cifrar no se produzcan muchas desviaciones en las frecuencias de aparición (en tanto por ciento) de las letras. Suponiendo esto, parece razonable que el símbolo "*" es la E. Si procedemos a cambiarla en el texto, obtenemos:
ÇE?}@E ?&[[}#$?=%$&# $ç %{E [&ç% ç%@=$!{%/&@\=@¿ }çE &/ ?@+]%&!@=]{+ . %\& ]E&]<E [=+ ?&[[}#$?=%E çE?}@E<+ >+ E#?@+]%$#! %{E [Eçç=!Eç çE#% >E%\EE# %{E[ . %{$ç ?=# >E ¿&#E $# ç}?{ = \=+ %{=% = %{$@¿ ]=@%+ E=¡Eç¿@&]]$#! [=+ #E¡E@ >E =><E %& ¿E?$]{E@ %{E [Eçç=!Eç . \{$<E çE?}@E ?&[[}#$?=%$&# {=ç E&#176;$ç%E¿ /&@ ?E#%}@$Eç , %{E -E+ [=#=!E[E#% ]@&><E[ {=ç ]@E¡E#%E¿ $% /@&[ >E?&[$#! ?&[[&#]<=?E . %{=#-ç %& %{E ¿E¡E<&][E#% &/ ]}><$?--E+ ?@+]%&!@=]{+ , %{E %&&<ç E&#176;$ç% %& ?@E=%E = <=@!E-ç?=<E #E%\&@- &/ ]E&]<E \{& ?=# ?&[[}#$?=%E çE?}@E<+ \$%{ &#E =#&%{E@ E¡E# $/ %{E+ {=¿ #E¡E@ ?&[[}#$?=%E¿ >E/&@E .
Las siguientes letras más frecuentes en inglés son la O y la T, por lo que los candidatos son los caracteres "%" y "&". Se observa que hay una palabra de dos caracteres, "&/", que comienza por "&"; por tanto, sin cifrar tiene que empezar por "O" o por "T". Buscando en un diccionario en inglés, se ve que la única palabra de dos letras que empieza por "T" es "TO", pero parece poco probable porque entonces "/" tendría que ser la "O". Por tanto, parece razonable que "&" es la "O" y que "%" es la "T". Si realizamos la sustitución, obtenemos:
ÇE?}@E ?O[[}#$?=T$O# $ç T{E [OçT çT@=$!{T/O@\=@¿ }çE O/ ?@+]TO!@=]{+ . T\O ]EO]<E [=+ ?O[[}#$?=TE çE?}@E<+ >+ E#?@+]T$#! T{E [Eçç=!Eç çE#T >ET\EE# T{E[ . T{$ç ?=# >E ¿O#E $# ç}?{ = \=+ T{=T = T{$@¿ ]=@T+ E=¡Eç¿@O]]$#! [=+ #E¡E@ >E =><E TO ¿E?$]{E@ T{E [Eçç=!Eç . \{$<E çE?}@E ?O[[}#$?=T$O# {=ç E&#176;$çTE¿ /O@ ?E#T}@$Eç , T{E -E+ [=#=!E[E#T ]@O><E[ {=ç ]@E¡E#TE¿ $T /@O[ >E?O[$#! ?O[[O#]<=?E . T{=#-ç TO T{E ¿E¡E<O][E#T O/ ]}><$?--E+ ?@+]TO!@=]{+ , T{E TOO<ç E&#176;$çT TO ?@E=TE = <=@!E-ç?=<E #ET\O@- O/ ]EO]<E \{O ?=# ?O[[}#$?=TE çE?}@E<+ \$T{ O#E =#OT{E@ E¡E# $/ T{E+ {=¿ #E¡E@ ?O[[}#$?=TE¿ >E/O@E.
De la palabra con sólo dos caracteres "O/" podemos esperar "OF" u "OR". Consultando la frecuencia de la "F" y de la "R", vemos que es más plausible que "/" sea "F". La siguiente palabra de dos caracteres es "$F", para la que no hay otra posibilidad que "IF"; por tanto "$" es "I". También se puede observar que en inglés sólo se encuentran las letras solas "A" e "I", por lo que el carácter "=" tiene que ser la "A". Otra palabra muy corta que se repite muchas veces es "T{E", que nos lleva a suponer que pueda ser "THE", por lo que "{" es "H". Así, por ahora tenemos:
ÇE?}@E ?O[[}#I?ATIO# Iç THE [OçT çT@AI!HTFO@\A@¿ }çE OF ?@+]TO!@A]H+ . T\O ]EO]<E [A+ ?O[[}#I?ATE çE?}@E<+ >+ E#?@+]TI#! THE [EççA!Eç çE#T >ET\EE# THE[ . THIç ?A# >E ¿O#E I# ç}?H A \A+ THAT A THI@¿ ]A@T+ EA¡Eç¿@O]]I#! [A+ #E¡E@ >E A><E TO ¿E?I]HE@ THE [EççA!Eç . \HI<E çE?}@E ?O[[}#I?ATIO# HAç E&#176;IçTE¿ FO@ ?E#T}@IEç , THE -E+ [A#A!E[E#T ]@O><E[ HAç ]@E¡E#TE¿ IT F@O[ >E?O[I#! ?O[[O#]<A?E . THA#-ç TO THE ¿E¡E<O][E#T OF ]}><I?--E+ ?@+]TO!@A]H+ , THE TOO<ç E&#176;IçT TO ?@EATE A <A@!E-ç?A<E #ET\O@- OF ]EO]<E \HO ?A# ?O[[}#I?ATE çE?}@E<+ \ITH O#E A#OTHE@ E¡E# IF THE+ HA¿ #E¡E@ ?O[[}#I?ATE¿ >EFO@E .
Una palabra muy corta que también aparece en el texto es "FO@". Consultado un diccionario, sólo puede ser: "FOB", "FOG", "FOR" Y "FOX". La primera de éstas no puede ser, ya que la "B" ya la hemos descifrado. De entre las letras posibles para el carácter "@", la más frecuente, y con diferencia, es la "R". Por tanto, cambiaremos el carácter "@" por "R".
ÇE?}RE ?O[[}#I?ATIO# Iç THE [OçT çTRAI!HTFOR\AR¿ }çE OF ?R+]TO!RA]H+ . T\O ]EO]<E [A+ ?O[[}#I?ATE çE?}RE<+ >+ E#?R+]TI#!
THAT A THIR¿ ]ART+ EA¡Eç¿RO]]I#! [A+ #E¡ER >E A><E TO ¿E?I]HER THE [EççA!Eç . \HI<E çE?}RE ?O[[}#I?ATIO# HAç E&#176;IçTE¿ FOR ?E#T}RIEç , THE -E+ [A#A!E[E#T ]RO><E[ HAç ]RE¡E#TE¿ IT FRO[ >E?O[I#! ?O[[O#]<A?E . THA#-ç TO THE ¿E¡E<O][E#T OF ]}><I?--E+ ?R+]TO!RA]H+ , THE TOO<ç E&#176;IçT TO ?REATE A <AR!E-ç?A<E #ET\OR- OF ]EO]<E \HO ?A# ?O[[}#I?ATE çE?}RE<+ \ITH O#E A#OTHER E¡E# IF THE+ HA¿ #E¡ER ?O[[}#I?ATE¿ >EFORE .
Este último cambio deja palabras al descubierto como pueden ser "çTRAI!HTFOR\AR¿", "A#OTHER", ">EFORE", que nos llevan sustituir "#,>,Ç,¿,!,\" por "NBSDGW":
SE?}RE ?O[[}NI?ATION IS THE [OST STRAIGHTFORWARD }SE OF ?R+]TOGRA]H+ . TWO ]EO]<E [A+ ?O[[}NI?ATE SE?}RE<+ B+ EN?R+]TING THE [ESSAGES SENT BETWEEN THE[ . THIS ?AN BE DONE IN S}?H A WA+ THAT A THIRD ]ART+ EA¡ESDRO]]ING [A+ NE¡ER BE AB<E TO DE?I]HER THE [ESSAGES . WHI<E SE?}RE ?O[[}NI?ATION HAS E&#176;ISTED FOR ?ENT}RIES , THE -E+ [ANAGE[ENT ]ROB<E[ HAS ]RE¡ENTED IT FRO[ BE?O[ING ?O[[ON]<A?E . THAN-S TO THE DE¡E<O][ENT OF ]}B<I?--E+ ?R+]TOGRA]H+ , THE TOO<S E&#176;IST TO ?REATE A <ARGE-S?A<E NETWOR- OF ]EO]<E WHO ?AN ?O[[}NI?ATE SE?}RE<+ WITH ONE ANOTHER E¡EN IF THE+ HAD NE¡ER ?O[[}NI?ATED BEFORE .
Ahora el descifrado es inmediato:
SECURE COMMUNICATION IS THE MOST STRAIGHTFORWARD USE OF CRYPTOGRAPHY. TWO PEOPLE MAY COMMUNICATE SECURELY BY ENCRYPTING THE MESSAGES SENT BETWEEN THEM. THIS CAN BE DONE IN SUCH A WAY THAT A THIRD PARTY EAVESDROPPING MAY NEVER BE ABLE TO DECIPHER THE MESSAGES. WHILE SECURE COMMUNICATION HAS EXISTED FOR CENTURIES , THE KEY MANAGEMENT PROBLEM HAS PREVENTED IT FROM BECOMING COMMONPLACE. THANKS TO THE DEVELOPMENT OF PUBLICKKEY CRYPTOGRAPHY, THE TOOLS EXIST TO CREATE A LARGEKSCALE NETWORK OF PEOPLE WHO CAN COMMUNICATE SECURELY WITH ONE ANOTHER EVEN IF THEY HAD NEVER COMMUNICATED BEFORE.
Actividad
Ejercicio 1
Haced un ataque estadístico para descifrar la célebre frase en inglés:
G/* SAV+ %&+ QU++#
Los caracteres del alfabeto son los originales del mensaje.
Ejercicio 2
El escritor norteamericano Edgar Allan Poe explica en su cuento "El escarabajo de oro" cómo encontró el protagonista el tesoro del capitán Kidd, utilizando un ataque estadístico. ¿Sabríais hacer el ataque estadístico? Para ello lo mejor es seguir el proceso del ejemplo anterior haciendo una estadística de frecuencias de caracteres del texto cifrado y del no cifrado.
"– Siga... siga... Me consumo de impaciencia.
– Bueno; habrá usted oído contar alguna de las muchas historias que corren, de esos mil vagos rumores respecto a tesoros enterrados en algún lugar de la costa del Atlántico por Kidd y sus camaradas. Esos rumores debían tener algún fundamento real. Y si seguían corriendo desde hace tanto tiempo y con tanta persistencia, ello se debía, a mi juicio, solamente a la circunstancia de que el tesoro enterrado permanecía enterrado. Si Kidd hubiese escondido su botín durante algún tiempo y lo hubiera recuperado después, no habrían llegado tales rumores hasta nosotros en su invariable forma actual. Fíjese en que esas historias giran todas alrededor de buscadores, no de descubridores de tesoros. Si el pirata hubiera recuperado su botín, el asunto habría terminado allí. Pensaba que algún accidente –por ejemplo, la pérdida de la nota que fijaba el lugar exacto– debía de haberle privado de los medios para recuperarlo, llegando ese accidente a conocimiento de sus compañeros, quienes de otra forma no hubiesen podido saber nunca que un tesoro había sido escondido y que con sus búsquedas infructuosas, por carecer de guía al intentar recuperarlo, dieron origen primero a ese rumor, difundido universalmente en su época, y a las noticias tan corrientes ahora. ¿Ha oído usted hablar de algún tesoro importante que haya sido descubierto en todo lo largo de la costa?
– Jamás.
– Pues es evidente que Kidd los había acumulado inmensos. Daba yo así por supuesto que la tierra seguía reteniéndolos y no le sorprenderá mucho si le digo que abrigaba una esperanza que aumentaba casi hasta la certidumbre: la de que el pergamino tan extraordinariamente hallado contenía la última indicación del lugar donde se ocultaba.
– Pero ¿cómo procedió usted?
– Aproximé de nuevo el pergamino al fuego, después de haberlo avivado; mas no apareció nada. Supuse entonces que era muy posible que la capa de mugre pudiera influir en aquel fracaso: para quitarla, lavé con esmero el pergamino vertiendo agua caliente encima y después, lo coloqué en una cacerola de cobre, con la calavera hacia abajo; puse la cacerola sobre una lumbre de carbón, y a los pocos minutos, estando ya la cacerola calentada intensamente, saqué la tira de pergamino. Fue inexpresable mi alegría al encontrarla manchada, en distintos sitios, con signos que parecían cifras alineadas. Volví a ponerla en la cacerola, y la dejé allí otro minuto. Cuando la saqué, estaba exactamente igual a como va usted a verla.
Al llegar aquí, Legrand, habiendo calentado de nuevo el pergamino, lo sometió a mi examen. Los caracteres siguientes aparecían groseramente trazados, en color rojo, en el espacio comprendido entre la calavera y la cabra:
7€ *7© € α #3& © € \# %&3ψ © @X# Σ © \ &*X3~ & © € \# 3X\\# Σ © \ Σ X#*\& -7#@© €ψ # ± 7€ 4@#Σ &3 ± ψ @© -© ;X€7ψ &3 €&@Σ © 3ψ © -7#@ψ & Σ © \ &j& X? λ 7X© @Σ & Σ © \# -#*© ?# Σ © ;7© @ψ & 7€# \X€© # @© -ψ # Σ © 3Σ © © \ €&@ψ © , ~ @X€-X~ #\ @#;# 3© ~ ψ X;& α #3ψ #4& \#Σ & © 3ψ © 3&\#@ Σ © 3Σ © © \ #@*&\ # ψ @#α © 3 Σ © \# *#\# -X€-7© €ψ # ~ X© 3 %#-X# (7© @#
– Pero –dije, devolviéndole la tira– sigo estando tan a oscuras como antes. Si todas las joyas de Golconda esperasen de mí la solución de este enigma, estoy seguro de que sería incapaz de obtenerlas.
– Sin embargo –dijo Legrand–, la solución no resulta tan difícil como cabe imaginar tras el primer examen superficial de los caracteres. Éstos, según puede adivinarse fácilmente, forman una cifra, es decir contienen un significado; pues por lo que sabemos de Kidd, no habría que suponerle capaz de construir una de las más abstrusas criptografías. Pensé, pues, desde luego, que ésta era de una clase sencilla, aunque tal, no obstante, que resultase absolutamente indescifrable para la tosca inteligencia del marinero, sin la clave.
– ¿Y la resolvió usted, en verdad?
Ejercicio 3
Un caso real de cazadores de tesoros se dio en el estado norteamericano de Virginia en el siglo XIX. El sistema de cifrado que se utilizó para proteger las instrucciones para encontrar el paradero del secreto es conocido como el cifrado de Beale (en honor de T.J. Beale, el cabecilla de la banda de aventureros que escondió el tesoro). Averiguad si el tesoro ha sido encontrado, si el mensaje con las instrucciones ha sido descifrado. ¿Qué se conoce del mecanismo de cifrado de Beale?
Sherlock Holmes
Una historia clásica de detectives de Arthur Conan Doyle, titulada The Adventure of the Dancing Men, en la que Sherlock Holmes utiliza el descifrado de un mensaje para esclarecer un caso, se puede consultar en: https://en.wikipedia.org/wiki/The_Adventure_of_the_Dancing_Men

2.2.Cifrados de Vigenère, de Vernam, en flujo y homofónicos

Una de las principales debilidades del cifrado César es que para una clave dada, cada carácter tiene siempre un mismo cifrado, independientemente de qué posición ocupe dentro del mensaje. Una modificación del método César para evitar el ataque estadístico es la dada por el cifrado de Vigenère. Este cifrado es atribuido erróneamente al criptógrafo del siglo XVI Blaise de Vigenère. Veamos en qué consiste. Se divide el mensaje en bloques de igual longitud previamente acordada. Para el primer carácter de cada bloque se aplica el método César con una clave fijada, para los segundos caracteres de cada bloque se aplica el método con otra clave, y así se procede con todos los caracteres. En el cifrado de Vigenère, la clave privada está formada por la longitud del bloque y por cada una de las claves que se tienen que utilizar. Veamos un ejemplo de aplicación:
Se ha acordado una clave privada para un cifrado de Vigenère formada por longitud de bloque igual a tres caracteres y claves k1 = 1, k2 = 5, k3 = 3 para aplicar a los primeros, segundos y terceros caracteres de cada bloque, respectivamente. Encontremos el cifrado del mensaje m = MULTIMEDIATEAMA. La separación en bloques es la siguiente: m = MUL TIM EDI ATE AMA. Ahora aplicamos cada uno de los cifrados César correspondientes:
E1(M) = N, E1(T) = U, E1(E) = F, E1(A) = B, E1(A) = B
E5(U) = Z, E5(I) = N, E5(D) = I, E5(T) = Y, E5(M) = Q
E3(L) = Ñ, E3(M) = O, E3(I) = L, E3(E) = H, E3(A) = D
y el mensaje cifrado es c = NZÑUNOFILBYHBQD. Fijémonos en que el carácter M es cifrado una vez por N, otra por P y otra vez por Q. Una manera de sistematizar el cifrado es utilizando la equivalencia numérica de cada carácter y disponiendo los cálculos de la siguiente forma:
m5e2_rec7.gif
Los mensajes no deben tener necesariamente una longitud múltiplo de la del bloque. Para descifrar un mensaje, simplemente hay que hacer los mismos cálculos, pero en lugar de sumar la clave correspondiente a cada posición, se debe de restar. Ilustrémoslo con el descifrado de c = ÑTVFWDQFUBYDÑYRPT:
m5e2_rec19.gif
Es decir, que el mensaje original es m = NOSERAPARATANTOOO.
Aunque existen métodos para romper el cifrado de Vigenère, el ataque estadístico simple que hemos explicado no nos permite descifrar. Este método se denomina polialfabético, ya que en el fondo, los primeros caracteres son cifrados en un nuevo alfabeto, los segundos en otro diferente, etc., en contraposición con el método César, que es monoalfabético (sólo existe un cambio de alfabeto).
Un cifrado polialfabético muy famoso fue el de la máquina Enigma, diseñada por A. Scherbius, utilizada por los alemanes en la Segunda Guerra Mundial. Esta máquina estaba basada en el uso de unos rotores, unos discos con veintiséis contactos eléctricos que se hacían girar para producir el cifrado de cada uno de los alfabetos. Aunque esta máquina era muy sofisticada, los aliados consiguieron descifrar en muchas ocasiones los mensajes alemanes. Dentro del equipo de contraespionaje destacaba el matemático inglés Alan Turing.
m5e2_rec8a.gif
m5e2_rec9.gif
m5e2_rec10.gif
Un método con cierto parecido al de Vigenère es el método de Vernam. Este método de cifrado fue propuesto en 1926 por G.S. Vernam, ingeniero de la compañía AT&T. En este método se codifica cada carácter en forma de una tira de 8 bits por medio de un código estándar, como el código ASCII (American Standard Code for Information Interchange). El código ASCII es el siguiente:

Tabla de caracteres ASCII

Decimal

ASCII

Binario

 

Decimal

ASCII

Binario

32

blanco

00100000

 

90

Z

01011010

33

!

00100001

 

91

[

01011011

34

"

00100010

 

92

/

01011100

35

#

00100011

 

93

]

01011101

36

$

00100100

 

94

^

01011110

37

%

00100101

 

95

_

01011111

38

&

00100110

 

96

'

01100000

40

(

00101000

 

97

a

01100001

41

)

00101001

 

98

b

01100010

42

*

00101010

 

99

c

01100011

44

,

00101100

 

100

d

01100100

45

-

00101101

 

101

e

01100101

46

.

00101110

 

102

f

01100110

65

A

01000001

 

103

g

01100111

66

B

01000010

 

104

h

01101000

67

C

01000011

 

105

i

01101001

68

D

01000100

 

106

j

01101010

69

E

01000101

 

107

k

01101011

70

F

01000110

 

108

l

01101100

71

G

01000111

 

109

m

01101101

72

II

01001000

 

110

n

01101110

73

I

01001001

 

111

o

01101111

74

J

01001010

 

112

p

01110000

75

K

01001011

 

113

q

01110001

76

L

01001100

 

114

r

01110010

77

M

01001101

 

115

s

01110011

78

N

01001110

 

116

t

01110100

79

O

01001111

 

117

u

01110101

80

P

01010000

 

118

v

01110110

81

Q

01010001

 

119

w

01110111

82

R

01010010

 

120

x

01111000

83

S

01010011

 

121

y

01111001

84

T

01010100

 

122

z

01111010

85

U

01010101

 

123

{

01111011

86

V

01010110

 

124

|

01111100

87

W

01010111

 

125

}

01111101

88

X

01011000

 

126

~

01111110

89

Y

01011001

 

 

 

 
A partir de una clave privada tan larga en bits como la longitud del mensaje en bits, se dispone en un esquema como el de Vigenère y se realiza la suma bit a bit (o exclusiva, que coincide con la suma de los enteros módulo 2).
Vamos a cifrar el mensaje m = QUE TAL con el método Verman. En primer lugar codificamos cada letra con la tabla de caracteres ASCII.
m = QUE TAL = 01010001 01010101 01000101 00100000 01010100 01000001 01001100
Supongamos que la clave privada es:
k = 01010010011001011001000111101010100010010010010010101000
Entonces sumamos el mensaje con la clave:
m5e2_rec20.gif
Y por tanto, el mensaje cifrado será:
c = 00000011 00110000 11010100 11001010 11011101 01100101 11100100
En las comunicaciones reales, el mensaje cifrado se envía en forma de bits, por lo que no es necesario traducir nuevamente a caracteres por medio de la tabla del código ASCII. Para hacer un descifrado de Vernam, simplemente se tiene que restar la clave secreta al mensaje cifrado para poder recuperar el mensaje original. Sin embargo, se da la casualidad de que, a la hora de efectuar la resta en Z2, coincide con hacer la suma, es decir, que para descifrar hay que sumar bit a bit la clave privada.
Una propiedad muy importante del sistema de clave privada de Vernam es que es perfectamente secreto. Veamos la idea de qué quiere decir perfectamente secreto. Supongamos que un oponente ha capturado el mensaje cifrado anterior que pasa por el canal inseguro. Puesto que desconoce la clave privada empleada, se plantea qué puede haber cifrado en ese mensaje. Como la clave privada puede ser cualquiera, se puede encontrar con muchas sorpresas. Por ejemplo, si la clave empleada hubiese sido:
m5e2_rec21.gif
el mensaje descifrado sería:
m5e2_rec22.gif
que corresponde con m = SEGURO!. Se puede ver cualquier mensaje imaginable de siete caracteres, ya que puede ser el mensaje transmitido utilizando una clave adecuada. Por tanto, el oponente no puede deducir nada al respecto del posible mensaje transmitido, aun utilizando los recursos computacionales que quiera. El único criptosistema de clave privada que es perfectamente seguro es el de Vernam.
Actividad
Ejercicio 1
Encontrad la clave para la que saldría como mensaje cifrado m = PERFECT (observad se puede usar como clave la suma bit a bit de c con m).
Ejercicio 2
Buscad en Internet la tabla de códigos ASCII ampliados, es decir, los que incluyen las vocales acentuadas.
El cifrado de Vernam presenta un inconveniente muy importante: la longitud de la clave secreta tiene que ser tan larga como el propio mensaje. Además, se requiere, como en toda clave privada, que sea difícilmente predecible. También se conoce con el nombre de un cifrado one-time-pad. Este nombre viene de la clave secreta (pad) que se llevaban escrita en una hoja de papel los espías durante la Segunda Guerra Mundial y después de la misma y que utilizaban una sola vez (one-time).
Para solucionar el problema de la longitud de la clave, se han ideado métodos por los que ésta se fabrica a partir de una clave de pocos bits y por medio de un cierto procedimiento. Así, las dos personas que se tienen que comunicar fabrican la clave privada a partir del procedimiento acordado y de la clave de pocos bits en el momento mismo del cifrado y del descifrado. Cuando se utiliza una clave privada fabricada de esta manera y se aplica a continuación un cifrado Vernam, se dice que estamos haciendo un cifrado en flujo.
Este método para fabricar y ahorrarse todos los bits de la clave privada sería muy bueno si la generación de los bits no fuese predecible por un posible oponente.
El método de Vigenère es una generalización del método de César para evitar ataques estadísticos. Se da una modificación para cualquier cifrado construido con sustituciones que evita el ataque estadístico. Se trata de los cifrados homofónicos. La palabra homofónico significa 'con el mismo sonido'. Para explicar en qué consisten, supongamos que utilizamos un cifrado por sustitución y que queremos cifrar el mensaje m = ELEFANTE. Pongamos que el mensaje cifrado es c = (+(% = $#(. Por lo que hemos visto del ataque estadístico, la idea básica es que los caracteres más frecuentes de la lengua original con que está escrito el mensaje se delatan también por su frecuencia en el texto cifrado. En este ejemplo, al mirar las frecuencias de repetición, es evidente cuál es el símbolo que más se repite: el "(" . Para evitar que el criptoanalista pueda suponer que corresponde con la E, podemos diluir la frecuencia de este carácter utilizando diferentes símbolos que signifiquen lo mismo para nosotros (que "suenen igual"). Así podríamos cifrar la E con "(,[,{" alternativa o aleatoriamente, con el fin de igualar las frecuencias que obtendría un criptoanalista del texto cifrado. Una manera de cifrar el mensaje anterior podría ser: c = {+[% = $#(, en el que aparecen todos los símbolos con la misma frecuencia. Evidentemente, a la clave privada del sistema habrá que añadir el convenio de qué símbolos "suenan igual", es decir, qué símbolos debemos considerar iguales a la hora de descifrar.
Actividad
Proponed un cifrado homofónico de caracteres en inglés para los caracteres E, O, T y L que iguale las frecuencias de aparición de los caracteres propuestos. Utilizad como dato de aparición de la E, O, T y L en un texto en inglés las frecuencias que se han obtenido para el ataque estadístico del ejemplo del texto en este idioma.
Otro método de clave privada, basado en transposiciones, consiste en cortar los mensajes en bloques de igual longitud y, dentro de éstos, permutar los caracteres utilizando una cierta regla. En este caso, la clave privada consiste en la longitud del bloque y en la permutación efectuada.
Utilicemos una longitud de bloque de cinco caracteres y dentro de cada bloque, cambiemos los caracteres según esta permutación sobre los mismos:
1 → 4
2 → 2
3 → 5
4 → 1
5 → 3
Por ejemplo, el cifrado de m = HOLAQUETAL se haría de la manera siguiente:
m = HOLAQ → AOQHL
Cálculo que se ha hecho simplemente mirando que en primer lugar hay que poner el carácter que aparece en el lugar 4, es decir, la A; a continuación, hay que poner el que está en el lugar 2; por tanto, tenemos por ahora AO; el siguiente es el carácter del lugar 5, así: AOQ; y para finalizar, los caracteres que están en el lugar 1 y 3, que nos dan AOQHL. De la misma forma, con el segundo bloque se obtiene:
m2 = UETAL → AELUT
Por tanto, el mensaje cifrado quedaría c = AOQHLAELUT. Una manera de sistematizar los cálculos es la siguiente: disponemos el mensaje en una tabla de anchura 5 escrito por filas y, a continuación, hacemos la permutación de los caracteres por columnas:
m5e2_rec15.gif
Y ahora, sólo nos queda leer el mensaje cifrado por filas: c = AOQHLAELUT.
Para descifrar un mensaje escrito con esta clave privada (formada por la longitud del bloque y la permutación), sólo es necesario hacer el proceso al revés. Por ejemplo, si se ha recibido c = EORYPTEOFC:
m5e2_rec16.gif
Como se puede observar, hemos procedido al revés: hemos escrito el mensaje cifrado en una tabla etiquetada con las columnas con la numeración después de permutar y hemos procedido a reordenar las columnas.
Por tanto, el mensaje cifrado corresponde al mensaje m = YOPERFECTO.
Actividad
Ejercicio 1
Cifrad el mensaje m = LACRIPTOGRAFIAGUSTAMUCHO utilizando una longitud de bloque de seis caracteres y la permutación:
1 → 3
2 → 2
3 → 5
4 → 1
5 → 6
6 → 4
Ejercicio 2
Descifrad el mensaje recibido c = EUAPMSONEIGMTSBUAA si se ha utilizado la clave privada anterior.
Como se puede observar, la principal diferencia entre los cifrados por sustitución y por transposición radica en que el criterio para averiguar cuál es el cifrado de cada carácter depende de cuál es el carácter que hay que cifrar (y no depende de la posición que ocupa en el mensaje) y en el segundo caso depende únicamente de la posición y es independiente de qué carácter se trata.

2.3.Criptosistema DES

El criptosistema de clave privada más conocido y utilizado hasta ahora es el DES (Data Encryption Standard). Este cifrado fue desarrollado por IBM y la NSA (National Security Agency) a partir del cifrado Lucifer y establecido por el NBS (National Bureau of Standards of USA) en el año 1977 como el estándar de comunicación entre las Agencias Federales de Estados Unidos.
El cifrado de este método es muy sofisticado, por lo que simplemente daremos una idea de qué se hace para cifrar un mensaje. El mensaje es dividido en bloques de 64 bits que se cifran uno a uno con la ayuda de una clave de 64 bits. Para cifrar un bloque, se siguen los pasos siguientes:
1) Los bits del mensaje se permutan siguiendo una cierta permutación.
2) El bloque se divide en dos subbloques de 32 bits cada uno, y se les aplican 16 transformaciones; estas transformaciones varían en función de una serie de reglas y en función de los valores de los subbloques.
3) Para acabar, los dos bloques se intercambian de orden y se les aplica la permutación inversa del paso 1.
m5e2_rec18.gif

Ejercicios de autoevaluación

1. Alicia manda un mensaje cifrado a Blas con un criptosistema de clave privada. No se han puesto de acuerdo en qué clave van a utilizar. Entonces...

a) Blas no podrá leer el mensaje hasta que Alicia le dé la clave con la que ha cifrado el mensaje
b) Blas no necesita la clave que ha utilizado Alicia, ya que la clave sólo se usa para el cifrado.
c) Blas no necesita la clave que ha utilizado Alicia, le basta con saber el método de clave privada que ha utilizado.

2. La máquina Enigma...

a) fue un ingenio de los ingleses para descrifrar las comunicaciones alemanas durante la Segunda Guerra Mundial.
b) fue utilizada por Alan Turing para sus trabajos en lógica matemática.
c) fue usada por los alemanes durante la Segunda Guerra Mundial para comunicarse de forma segura.

3. Los dos momentos claves en el desarrollo histórico de la criptografía se considera que son...

a) cuando César se comunicaba de forma criptográfica con Cleopatra y cuando Edgar Allan Poe escribió su novela ''El escarabajo de Oro''.
b) cuando Shannon establece las bases matemáticas de la criptografía y Diffie y Hellman proponen el modelo de criptografía de clave pública.
c) la Segunda Guerra Mundial y cuando el RSA se empezó a comercializar en el MIT.

4. Queremos mandar el mensaje "GMMD" usando el método de César con k = 5 , ¿cuál de los mensajes siguientes deberemos mandar? (Utilizando el abecedario de 27 caracteres)

a) LQQI.
b) BHHY.
c) MRRJ.

5. Recibimos el mensaje "XSUK" cifrado por el método de César con k = 23, ¿cuál es el mensaje sin cifrar?

a) TUQG.
b) BWYÑ.
c) KUSX.

6. Para comunicar el mensaje "SOS" cifrado con el método César, mandamos la palabra "FBF", ¿qué clave se ha utilizado?

a) 13
b) 14
c) 15

7. En Z15 el resultado de la operación 13 + 10 es...

a) 6
b) 7
c) 8

8. En Z23, el resultado de la operación 13 · 10 es...

a) 14
b) 15
c) 16

9. ¿Cuál de las siguientes afirmaciones es falsa?

a) 14 + 5 ≡ 3 mod 16.
b) 3 · 5 ≡ 0 mod 15.
c) 7 · 4 ≡ 11 mod 13.

10. El inverso de 7 en Z34 es...

a) No tiene inverso.
b) 5
c) 7

11. Queremos cifrar la palabra "IBM" con el método de Vernam usando la clave k = 10110011 10010101 11001110. ¿Cuál será la palabra cifrada?

a) c = 11111010 11010011 10010011
b) c = 11110000 01101010 01100110
c) c = 11111010 11010111 10000011

12. El cifrado de la palabra "EUROPA" utilizando bloques de tres caracteres y la permutación 1 → 2   2 → 1   3 → 3 es...

a) UERPOA.
b) PREUOA.
c) ROEUPA.

13. El criptosistema DES...

a) no es un sistema de clave privada.
b) está en desuso desde 1977.
c) es el criptosistema de clave privada más conocido y utilizado.

14. Relacionad las palabras de las dos columnas:
06508_m2_03.jpg

15. Respecto al sistema DES, ¿cuál de las siguientes afirmaciones es falsa?

a) Fue desarrollado a partir del cifrado Lucifer.
b) Es idéntico al sistema Vernam.
c) En este criptosistema se operan bloques de 64 bits por medio de una clave siguiendo unos pasos fijados.

Ejercicios de autoevaluación
1. a) Correcto.
b) Incorrecto. La clave es necesaria tanto para cifrar como para descifrar.
c) Incorrecto. Blas necesita conocer el método utilizado, pero de todas maneras, la clave es necesaria para descifrar el mensaje.

2. a) Incorrecto. Falso. Fue un ingenio usado por las tropas alemanas.
b) Incorrecto. Falso. Fue un ingenio usado por las tropas alemanas.
c) Correcto.

3. a) Incorrecto. Aunque en estos dos ejemplos se usara la criptografía, no fueron fechas importantes para esta rama.
b) Correcto.
c) Incorrecto. Aunque durante la Segunda Guerra Mundial se utilizó la máquina Enigma, esta fecha no se considera capital en criptografía. Además, el RSA no se comercializa por medio del MIT.

4. a) Correcto.
b) Incorrecto. Volved a cifrar la palabra.
c) Incorrecto. Volved a cifrar la palabra.

5. a) Incorrecto. Volved a descifrar la palabra.
b) Correcto.
c) Incorrecto. Volved a descifrar la palabra.

6. a) Correcto.
b) Incorrecto.
c) Incorrecto. Comprobad cuántos saltos de letras hay entre estas dos palabras.

7. a) Incorrecto. Repetid la operación.
b) Incorrecto. Repetid la operación.
c) Correcto.

8. a) Incorrecto. Repetid la operación.
b) Correcto.
c) Incorrecto. Repetid la operación.

9. a) Incorrecto. No. Esta afirmación es correcta.
b) Incorrecto. No. Esta afirmación es correcta.
c) Correcto.

10. a) Incorrecto. Comprobad que uno de los números propuestos en las otras respuestas es el inverso.
b) Correcto.
c) Incorrecto. Falso. Comprobad que el producto de estos dos números no es 1.

11. a) Incorrecto. Comprobad los cálculos.
b) Incorrecto. Comprobad los cálculos.
c) Correcto.

12. a) Correcto.
b) Incorrecto. Repetid la permutación.
c) Incorrecto. Repetid la permutación.

13. a) Incorrecto. Sí es de clave privada.
b) Incorrecto. Este criptosistema se creó en 1977 y sigue usándose en la actualidad.
c) Correcto.

14.
06508_m2_03_sol.gif

15. a) Incorrecto. No. Esta respuesta es cierta.
b) Correcto.
c) Incorrecto. No. Esta respuesta es cierta.


Bibliografía

Domingo Ferrer, J.; Herrera Joancomartí, J. (1999). Criptografia per als serveis telemàtics i el comerç electrònic. Barcelona: Ediuoc.
Rifà, J.; Huguet, L. (1991). Comunicación digital. Barcelona: Masson, S.A.
Singh, S. (1998). El enigma de Fermat. Barcelona: Editorial Planeta.
Singh, S. (2000). Los códigos secretos. Madrid: Debate Editorial.
Stinson, D.R. (1995). Cryptography. Theory and Practice. Boca Raton, Florida (EE.UU.): CRC Press.