7.1: Criptografía de clave privada
- Page ID
- 111030
En los criptosistemas de clave única o privada se utiliza la misma clave tanto para cifrar como para descifrar mensajes. Para cifrar un mensaje de texto plano, aplicamos al mensaje alguna función que se mantiene en secreto, digamos\(f\text{.}\) Esta función dará lugar a un mensaje cifrado. Dada la forma encriptada del mensaje, podemos recuperar el mensaje original aplicando la transformación inversa\(f^{-1}\text{.}\) La transformación\(f\) debe ser relativamente fácil de calcular, como\(f\) debe ser\(f^{-1}\text{;}\) sin embargo extremadamente difícil de adivinar a partir de los ejemplos disponibles de mensajes codificados .
Uno de los primeros y más famosos criptosistemas de clave privada fue el código de cambio utilizado por Julio César. Primero digitalizamos el alfabeto dejando\(\text{A} = 00, \text{B} = 01, \ldots, \text{Z} = 25\text{.}\) La función de codificación será
\[ f(p) = p + 3 \bmod 26; \nonumber \]
es decir,\(A \mapsto D, B \mapsto E, \ldots, Z \mapsto C\text{.}\)
Solución
La función de decodificación es entonces
\[ f^{-1}(p) = p - 3 \bmod 26 = p + 23 \bmod 26\text{.} \nonumber \]
Supongamos que recibimos el mensaje codificado DOJHEUD. Para decodificar este mensaje, primero lo digitalizamos:
\[ 3, 14, 9, 7, 4, 20, 3\text{.} \nonumber \]
A continuación aplicamos la transformación inversa para obtener
\[ 0, 11, 6, 4, 1, 17, 0\text{,} \nonumber \]
o ALGEBRA. Observe aquí que no hay nada especial en ninguno de los números\(3\) o\(26\text{.}\) Podríamos haber usado un alfabeto más grande o un turno diferente.
El criptanálisis se refiere a descifrar un mensaje recibido o interceptado. Los métodos de probabilidad y estadística son grandes ayudas para descifrar un mensaje interceptado; por ejemplo, el análisis de frecuencia de los caracteres que aparecen en el mensaje interceptado a menudo hace posible su descifrado.
Supongamos que recibimos un mensaje que sabemos que fue cifrado mediante el uso de una transformación de turno en letras simples del alfabeto\(26\) -letra. Para saber exactamente cuál fue la transformación del cambio, debemos computar\(b\) en la ecuación\(f(p) = p + b \bmod 26\text{.}\)
Solución
Podemos hacer esto mediante análisis de frecuencia. La letra\(\text{E} = 04\) es la letra que ocurre con mayor frecuencia en el idioma inglés. Supongamos que esa\(\text{S} = 18\) es la letra que ocurre con mayor frecuencia en el texto cifrado. Entonces tenemos buenas razones para sospechar eso\(18 = 4 + b \bmod 26\text{,}\) o\(b= 14\text{.}\) Por lo tanto, la función de encriptación más probable es
\[ f(p) = p + 14 \bmod 26\text{.} \nonumber \]
La función de descifrado correspondiente es
\[ f^{-1}(p) = p + 12 \bmod 26\text{.} \nonumber \]
Ahora es fácil determinar si nuestra conjetura es correcta o no.
Los códigos de turno simples son ejemplos de criptosistemas monoalfabéticos. En estos cifrados un carácter en el mensaje cifrado representa exactamente un carácter en el mensaje original. Dichos criptosistemas no son muy sofisticados y son bastante fáciles de romper. De hecho, en un simple turno como se describe en Ejemplo\(7.1\), solo hay teclas\(26\) posibles. Sería bastante fácil probarlos todos en lugar de usar el análisis de frecuencias.
Investiguemos un criptosistema un poco más sofisticado. Supongamos que la función de codificación viene dada por
\[ f(p) = ap + b \bmod 26\text{.} \nonumber \]
Primero tenemos que averiguar cuándo\(f^{-1}\) existe una función de decodificación. Tal función de decodificación existe cuando podemos resolver la ecuación
\[ c = ap + b \bmod 26 \nonumber \]
para\(p\text{.}\) Por Proposición\(3.4\), esto es posible exactamente cuando\(a\) tiene una inversa o, equivalentemente, cuando\(\gcd( a, 26) =1\text{.}\) En este caso
\[ f^{-1}(p) = a^{-1} p - a^{-1} b \bmod 26\text{.} \nonumber \]
Tal criptosistema se llama criptosistema afín.
Consideremos el criptosistema afín\(f(p) = ap + b \bmod 26\text{.}\)
Solución
Para que este criptosistema funcione debemos elegir un\(a \in {\mathbb Z}_{26}\) que sea invertible. Esto sólo es posible si\(\gcd(a, 26) = 1\text{.}\) Reconociendo este hecho, vamos a dejar\(a = 5\) ya\(\gcd(5, 26) = 1\text{.}\) que es fácil ver que\(a^{-1} = 21\text{.}\) Por lo tanto, podemos tomar nuestra función de encriptación para ser\(f(p) = 5p + 3 \bmod 26\text{.}\) Así, ALGEBRA se codifica como\(3, 6, 7, 23, 8, 10, 3\text{,}\) o DGHXIKD. La función de descifrado será
\[ f^{-1}(p) = 21 p - 21 \cdot 3 \bmod 26 = 21 p + 15 \bmod 26\text{.} \nonumber \]
Un criptosistema sería más seguro si una letra de texto cifrado pudiera representar más de una letra de texto plano. Para dar un ejemplo de este tipo de criptosistema, llamado criptosistema polialfabético, generalizaremos los códigos afín mediante el uso de matrices. La idea funciona aproximadamente igual que antes; sin embargo, en lugar de cifrar una letra a la vez cifraremos pares de letras. Podemos almacenar un par de letras\(p_1\) y\(p_2\) en un vector
\[ {\mathbf p} = \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}\text{.} \nonumber \]
Dejar\(A\) ser una matriz\(2 \times 2\) invertible con entradas en\({\mathbb Z}_{26}\text{.}\) Podemos definir una función de codificación por
\[ f({\mathbf p}) = A {\mathbf p} + {\mathbf b}\text{,} \nonumber \]
donde\({\mathbf b}\) es un vector de columna fija y las operaciones de matriz se realizan en\({\mathbb Z}_{26}\text{.}\) La función de decodificación debe ser
\[ f^{-1}({\mathbf p}) = A^{-1} {\mathbf p} - A^{-1} {\mathbf b}\text{.} \nonumber \]
Supongamos que deseamos codificar la palabra HELP. La cadena de dígitos correspondiente es\(7, 4, 11, 15\text{.}\) If
\[ A = \begin{pmatrix} 3 & 5 \\ 1 & 2 \end{pmatrix}\text{,} \nonumber \]
Solución
entonces
\[ A^{-1} = \begin{pmatrix} 2 & 21 \\ 25 & 3 \end{pmatrix}\text{.} \nonumber \]
Si\({\mathbf b} = ( 2, 2)^\transpose\text{,}\) entonces nuestro mensaje está encriptado como RRGR. La letra encriptada R representa más de una letra de texto plano.
El análisis de frecuencia aún se puede realizar en un criptosistema polialfabético, porque tenemos una buena comprensión de cómo aparecen los pares de letras en el idioma inglés. El par th aparece con bastante frecuencia; el par qz nunca aparece. Para evitar el descifrado por parte de un tercero, debemos usar una matriz más grande que la que usamos en Ejemplo\(7.4\).