Sección7.1Criptografía de Clave Privada
¶En criptosistemas de clave única o criptosistema de clave privada la misma clave se usa tanto para encriptar como para decriptar los mensajes. Para encriptar un texto-claro, aplicamos al mensaje alguna función que se mantiene en secreto, digamos \(f\text{.}\) Esta función devuelve un mensaje encriptado. 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, así como también lo debe ser \(f^{-1}\text{;}\) pero, \(f\) tiene que ser muy difícil de adivinar a partir de ejemplos disponibles de mensajes encriptados.
Ejemplo7.1
Uno de los primeros y más famosos criptosistemas fue el código de desplazamiento usado por Julio César. Primero convertimos el alfabeto en números haciendo \(\text{A} = 00, \text{B} = 01, \ldots, \text{Z} = 25\text{.}\) La función codificadora será
\begin{equation*}
f(p) = p + 3 \bmod 26;
\end{equation*}
es decir, \(A \mapsto D, B \mapsto E, \ldots, Z \mapsto C\text{.}\) La función decodificadora es entonces
\begin{equation*}
f^{-1}(p) = p - 3 \bmod 26 = p + 23 \bmod 26.
\end{equation*}
Supongamos que recibimos el mensaje encriptado DOJHEUD. Para decriptar este mensaje, lo convertimos a números:
\begin{equation*}
3, 14, 9, 7, 4, 20, 3.
\end{equation*}
Luego le aplicamos la transformación inversa para obtener
\begin{equation*}
0, 11, 6, 4, 1, 17, 0,
\end{equation*}
es decir ALGEBRA. Note que no hay nada especial en los números 3 y 26, podríamos usar un alfabeto mayor o un desplazamiento diferente.
El criptoanálisis se preocupa de descifrar un mensaje encriptado recibido o interceptado. Existen Métodos de probabilidades y estadísticas que son de gran ayuda al descifrar mensajes interceptados; por ejemplo, el análisis de frecuencia de los caracteres que aparecen en el mensaje encriptado puede hacer posible su decriptación.
Ejemplo7.2
Supongamos que recibimos un mensaje que sabemos fue encriptado usando un desplazamiento en las 26 letras del alfabeto. Para determinar el desplazamiento ocupado, debemos encontrar \(b\) en la ecuación \(f(p) = p + b \bmod 26\text{.}\) Podemos hacer esto usando análisis de frecuencia. La letra \(\text{E} = 04\) es la más frecuente en el idioma inglés. Supongamos que \(\text{S} = 18\) es la letra que ocurre con más frecuencia en el texto-cifrado. Entonces tenemos una buena razón para sospechar que \(18 = 4 + b \bmod 26\text{,}\) y \(b= 14\text{.}\) Por lo tanto, la función encriptadora más probable es
\begin{equation*}
f(p) = p + 14 \bmod 26.
\end{equation*}
La correspondiente función decriptadora es
\begin{equation*}
f^{-1}(p) = p + 12 \bmod 26.
\end{equation*}
En este punto es fácil determinar si la sospecha es o no correcta.
Códigos de desplazamiento simple son ejemplos de criptosistemas monoalfabéticos. En estos cifrados un caracter en el texto-cifrado representa exactamente un caracter en el mensaje original. Tales criptosistemas no son muy sofisticados y son muy fáciles de romper. De hecho, en un desplazamiento simple como el descrito en el Ejemplo 7.1, existen solo 26 claves posibles. Sería muy fácil probarlas todas en lugar de usar el análisis de frecuencia.
Investigemos un criptosistema ligeramente más sofisticado. Supongamos que la función encriptadora está dada por
\begin{equation*}
f(p) = ap + b \bmod 26.
\end{equation*}
Primero debemos determinar cuándo existe una función decriptadora \(f^{-1}\text{.}\) Tal función existe cuando podemos resolver la ecuación
\begin{equation*}
c = ap + b \bmod 26
\end{equation*}
en \(p\text{.}\) Por la Proposición 3.4, esto es posible precisamente cuando \(a\) tiene inverso, es decir cuando \(\gcd( a, 26) =1\text{.}\) En este caso
\begin{equation*}
f^{-1}(p) = a^{-1} p - a^{-1} b \bmod 26.
\end{equation*}
Un criptosistema de este tipo se denomina criptosistema afín.
Ejemplo7.3
Consideremos el criptosistema afín \(f(p) = ap + b \bmod 26\text{.}\) Para que este criptosistema funcione, debemos elegir \(a \in {\mathbb Z}_{26}\) que sea invertible. Esto solo es posible si \(\gcd(a, 26) = 1\text{.}\) Reconociendo este hecho, elegiremos \(a = 5\) pues \(\gcd(5, 26) = 1\text{.}\) Es muy fácil ver que \(a^{-1} = 21\text{.}\) Por lo tanto, podemos definir nuestra función de encriptación como \(f(p) = 5p + 3 \bmod 26\text{.}\) Luego, ALGEBRA se encripta como \(3, 6, 7, 23, 8, 10, 3\text{,}\) o DGHXIKD. La función decriptadora será
\begin{equation*}
f^{-1}(p) = 21 p - 21 \cdot 3 \bmod 26 = 21 p + 15 \bmod 26.
\end{equation*}
Un criptosistema sería más seguro si una letra del texto-cifrado pudiese representar más de una letra del texto-claro. Para dar un ejemplo de este tipo de criptosistema, llamado criptosistema polialfabético, generalizaremos los códigos afines usando matrices. La idea funciona básicamente como antes; sin embargo, en lugar de encriptar una letra a la vez, encriptaremos pares de letras. Podemo almacenar un par de letras \(p_1\) y \(p_2\) en un vector
\begin{equation*}
{\mathbf p} =
\begin{pmatrix}
p_1 \\ p_2
\end{pmatrix}.
\end{equation*}
Sea \(A\) una matriz invertible de \(2 \times 2\) con coeficientes en \({\mathbb Z}_{26}\text{.}\) Podemos definir una función encriptadora como
\begin{equation*}
f({\mathbf p}) = A {\mathbf p} + {\mathbf b},
\end{equation*}
donde \({\mathbf b}\) es un vector columna fijo y las operaciones matriciales se llevan a cabo en \({\mathbb Z}_{26}\text{.}\) La función decriptadora debe ser
\begin{equation*}
f^{-1}({\mathbf p}) = A^{-1} {\mathbf p} - A^{-1} {\mathbf b}.
\end{equation*}
Ejemplo7.4
Supongamos que deseamos encriptar la palabra HELP. Los números correspondientes son \(7, 4, 11, 15\text{.}\) Si
\begin{equation*}
A =
\begin{pmatrix}
3 & 5 \\
1 & 2
\end{pmatrix},
\end{equation*}
entonces
\begin{equation*}
A^{-1}
=
\begin{pmatrix}
2 & 21 \\
25 & 3
\end{pmatrix}.
\end{equation*}
Si \({\mathbf b} = ( 2, 2)^{\rm t}\text{,}\) entonces el mensaje encriptado queda como RRGR. La letra R representa más de una letra en el texto-claro.
El análisis de frecuencia aún es realizable en un criptosistema polialfabético, pues tenemos buena información sobre la frecuencia relativa de pares de letras en el idioma inglés. El par th aparece con gran frecuencia; el par qz nunca aparece. Para evitar decriptación por parte de un tercero, debemos usar una matriz de mayor tamaño que la usada en el Ejemplo 7.4.
