Ir ao conteúdo principal

Seção 7.1 Criptografia de Chave Privada

Em criptossistemas de chave única ou criptossistema de chave privada a mesma clave é usada tanto para encriptar como para decriptar as mensagens. Para encriptar um texto claro, aplicamos na mensagem alguma função que é mantida em segredo, digamos \(f\text{.}\) Esta função devolve uma mensagem encriptada. Dada a forma encriptada da mensagem, podemos recuperar a mensagem original aplicando a transformação inversa \(f^{-1}\text{.}\) A transformação \(f\) deve ser relativamente fácil de calcular, assim como também deve ser \(f^{-1}\text{;}\) mas, devemos ter em mente que \(f\) deve ser muito difícil de adivinhar a partir de exemplos disponíveis de mensagens encriptadas.

Um dos primeiros e mais famosos criptossistemas foi o código de deslocamento usado por Júlio César. Primeiro convertemos o alfabeto em números fazendo \(\text{A} = 00, \text{B} = 01, \ldots, \text{Z} = 25\text{.}\) A função codificadora será

\begin{equation*} f(p) = p + 3 \bmod 26; \end{equation*}

isto é, \(A \mapsto D, B \mapsto E, \ldots, Z \mapsto C\text{.}\) A função decodificadora será

\begin{equation*} f^{-1}(p) = p - 3 \bmod 26 = p + 23 \bmod 26. \end{equation*}

Suponha que recebemos a mensagem encriptada DOJHEUD. Para decriptar esta mensagem, convertemos a números:

\begin{equation*} 3, 14, 9, 7, 4, 20, 3. \end{equation*}

Em seguida, aplicamos a transformação inversa para obter

\begin{equation*} 0, 11, 6, 4, 1, 17, 0, \end{equation*}

isto é ALGEBRA. Note que não exite nada de especial nos números 3 e 26, poderíamos usar um alfabeto maior ou um deslocamento diferente.

A criptoanálise se preocupa em decifrar uma mensagem encriptada recibida ou interceptada. Existem métodos de probabilidade e estatística que são de grande ajuda para decifrar mensagens interceptadas; por exemplo, a análise de frequência dos caracteres que aparecem na mensagem encriptada pode fazer sua decriptação possível.

Suponha que recebemos uma mensagem que sabemos que foi encriptada usando um deslocamento nas 26 letras do alfabeto. Para determinar o deslocamento, devemos encontrar \(b\) na equação \(f(p) = p + b \bmod 26\text{.}\) Podemos fazer isto usando análise de frequência. A letra \(\text{E} = 04\) é a mais frequente no idioma inglês. Suponha que \(\text{S} = 18\) é a letra que ocorre com mais frequência no texto-cifrado. Então temos uma boa razão para suspeitar que \(18 = 4 + b \bmod 26\text{,}\) e \(b= 14\text{.}\) Portanto, a função encriptadora mais provável é

\begin{equation*} f(p) = p + 14 \bmod 26. \end{equation*}

A função decriptadora correspondente é

\begin{equation*} f^{-1}(p) = p + 12 \bmod 26. \end{equation*}

Neste ponto é fácil determinar se a suspeita é ou não correta.

Códigos de deslocamento simples são exemplos de criptossistemas monoalfabéticos. Nestes cifrados um caractere no texto cifrado representa exatamente um caractere na mensagem original. Tais criptossistemas não são muito sofisticados e são muito fáceis de decifrar. De fato, em um deslocamento simples como o descrito no Exemplo 7.1.1, existem só 26 chaves possíveis. Seria muito mais fácil testar todas do que usar a análise de frequência.

Investiguemos um criptossistema ligeiramente mais sofisticado. Suponha que a função encriptadora é dada por

\begin{equation*} f(p) = ap + b \bmod 26. \end{equation*}

Primeiro devemos determinar quando existe uma função decriptadora \(f^{-1}\text{.}\) Tal função existe quando podemos resolver a equação

\begin{equation*} c = ap + b \bmod 26 \end{equation*}

em \(p\text{.}\) Pela Proposição 3.1.4, isso é possível precisamente quando \(a\) tem inverso, isto é quando \(\gcd( a, 26) =1\text{.}\) Neste caso

\begin{equation*} f^{-1}(p) = a^{-1} p - a^{-1} b \bmod 26. \end{equation*}

Um criptossistema deste tipo se denomina criptossistema afim.

Consideremos o criptossistema afim \(f(p) = ap + b \bmod 26\text{.}\) Para que este criptossistema funcione, devemos escolher \(a \in {\mathbb Z}_{26}\) que seja inversível. Isso só é possível se \(\gcd(a, 26) = 1\text{.}\) Reconhecendo este fato, escolheremos \(a = 5\) pois \(\gcd(5, 26) = 1\text{.}\) É muito fácil ver que \(a^{-1} = 21\text{.}\) Portanto, podemos definir nossa função de encriptação como \(f(p) = 5p + 3 \bmod 26\text{.}\) Logo, ALGEBRA se encripta como \(3, 6, 7, 23, 8, 10, 3\text{,}\) ou DGHXIKD. A função decriptadora será

\begin{equation*} f^{-1}(p) = 21 p - 21 \cdot 3 \bmod 26 = 21 p + 15 \bmod 26. \end{equation*}

Um criptossistema seria mais seguro se uma letra do texto cifrado pudesse representar mais de uma letra do texto claro. Para dar um exemplo deste tipo de criptossistema, chamado criptossistema polialfabético, generalizaremos os códigos afins usando matrizes. A idea funciona basicamente como antes; no entanto, no lugar de encriptar uma letra por vez, encriptaremos pares de letras. Podemos armazenar um par de letras \(p_1\) e \(p_2\) em um vetor

\begin{equation*} {\mathbf p} = \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}. \end{equation*}

Seja \(A\) uma matriz inversível de \(2 \times 2\) com coeficientes em \({\mathbb Z}_{26}\text{.}\) Podemos definir uma função encriptadora como

\begin{equation*} f({\mathbf p}) = A {\mathbf p} + {\mathbf b}, \end{equation*}

donde \({\mathbf b}\) é um vetor columa fixo e as operações matriciais são feitas em \({\mathbb Z}_{26}\text{.}\) A função decriptadora deve ser

\begin{equation*} f^{-1}({\mathbf p}) = A^{-1} {\mathbf p} - A^{-1} {\mathbf b}. \end{equation*}

Suponha que desejamos encriptar a palavra HELP. Os números correspondentes são \(7, 4, 11, 15\text{.}\) Se

\begin{equation*} A = \begin{pmatrix} 3 & 5 \\ 1 & 2 \end{pmatrix}, \end{equation*}

então

\begin{equation*} A^{-1} = \begin{pmatrix} 2 & 21 \\ 25 & 3 \end{pmatrix}. \end{equation*}

Se \({\mathbf b} = ( 2, 2)^{\rm t}\text{,}\) então a mensagem encriptada fica como RRGR. A letra R representa mais de uma letra no texto claro.

A análise de frequência ainda é realizável em um criptosistema polialfabético, pois temos boa informação sobre a frequência relativa de pares de letras no idioma inglês. O par th aparece com grande frequência; o par qz nunca aparece. Para evitar decriptação por parte de um terceiro, devemos usar uma matriz maior do que a usada no Exemplo 7.1.4.