O que é criptografia?
A palavra “criptografia” vem do termo grego κρυπτός (kryptós,“oculta”) tal qual a palavra “cripta” e de γραφία (graphía, “escrita”) tal qual a palavra “caligrafia”. A partir de sua etimologia podemos ter um vislumbre do referente da palavra: uma escrita ocultada. Ela é definida usualmente como o conjunto de métodos usados para transformar uma informação em uma forma ininteligível, de modo que apenas pessoas autorizadas (que possuam a chave) possam recuperar o texto original.
Aqui devemos dinstinguir entre criptografia simétrica e assimétrica, dado que a estrutura matemática diverge entre as duas pelo fato da primeira possuir uma chave e a segunda duas (uma de encriptar e outra de desencriptar). Nesse texto trataremos apenas do tipo simétrico, que podemos definir formalmente a partir de uma função bijetiva (para uma chave de criptografia fixa) que realiza permutações e possui um modo de operação, que dita como essas permutações devem ser realizadas e cuja função é garantir confidencialidade.
A criptografia é composta de duas funções principais (uma sendo a inversa da outra, bastando definir apenas uma bijetiva para caracterizá-las): encriptação \(E\) e decriptação \(D\). A primeira é responsável por gerar o texto encriptado (ciphertext – \(C\)) e a segunda é responsável por desencriptar o texto, retornando ao texto original (plaintext – \(P\)). Ambas levam uma chave \(K\) como parâmetro
$$C=E(K, P)$$
$$P=D(K, C)$$
Onde \(D(K,E(K,P))=P\), o que caracteriza a bijetividade na segunda variável e o fato de que \(D\) e \(E\) são inversas.
Destaca-se ainda o fato de que, em muitos casos, como no caso das AES e das DES da criptografia moderna, a encriptação é realizada iterativamente, de forma que o processo de bruteforcing da chave se torna mais complexo. Nesse caso teríamos:
$$C_n = E^{(n)}(K,P)$$
Claro que nem toda permutação é considerada uma permutação segura, para isso existem características necessárias que uma permutação deve cumprir. Mas antes vamos relembrar, matematicamente o que é uma permutação.
O que são permutações?
Uma permutação sobre um conjunto \(A\) é uma função bijetiva \(\sigma: A \rightarrow A\) que mapeia elementos de \(A\) em elementos de \(A\).
Supondo permutações no conjunto \(A={1,2,3,4,5,6}\), elas podem ser representadas de duas maneiras principais:
- Matrizes:
$$
\begin{pmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
\end{pmatrix}
$$
Nesse caso os elementos 1, 2, 3 são mapeados (ou permutados) com os elementos 4, 5, 6 respectivamente.
- “Mapsto”:
$$1 \mapsto 4, 2 \mapsto 5, 3 \mapsto 6$$
Utilizando Teoria de Grupos, um extenso campo de estudo em matemática com uma enorme gama de aplicações na física, vemos também que um conjunto \(S_n\) com todas as permutações possíveis de {1, 2, 3, …, n}, com a operação de composição de funções, obedece os axiomas de grupo:
- A1 (Fechamento): Toda composição de função em \(S_n\) resulta em um elemento de \(S_n\)
$$∘ : S_n\rightarrow S_n$$
- A2 (Associatividade): Toda composição de \(\sigma_i \in S_n\) é associativa:
$$\sigma_1∘(\sigma_2 ∘ \sigma_3) = (\sigma_1∘\sigma_2)∘\sigma_3$$
- A3 (Elemento neutro): O conjunto possui o elemento neutro dado pela identidade (permutação que trocam os números por eles mesmos)
$$Id∘\sigma_i = \sigma_i∘ Id = \sigma_i$$
- A4 (Funções inversas): Sendo as funções \(\sigma_i \in S_n\) bijetivas, elas possuem uma inversa \(\sigma_i^{-1}\):
$$\sigma_i^{-1}(\sigma_i) = Id$$
Esse grupo é denominado de grupo simétrico e tem uma enorme importância histórica no desenvolvimento da Teoria de Galois, elaborada por Évariste Galois (1811–1832), que trata a respeito da resolubilidade de equações algébricas.
Os métodos de criptografia atuam em sub-espaços do espaço definido pelo grupo simétrico, e as cifras modernas buscam fazer com que, para o atacante (aquele que busca descobrir a chave de criptografia), a transformação do plaintext para o ciphertext seja indistinguível de uma permutação aleatória (pseudorandom permutation – PRP), escolhida em um grupo simétrico, de forma a maximizar a segurança da cifra.
A matemática das cifras clássicas
Antes mesmo de existirem computadores e todas as noções de segurança (como IND-CPA e IND-CCA) que temos hoje na criptografia, algumas cifras existiam para garantir confidencialidade em situações mais simples.
Um exemplo dessas é a Cifra de Cesar, uma cifra que realizava, a partir de uma chave de valor único (uma das 26 letras do alfabeto), uma translação simples de todas as letras do plaintext por um valor fixo, definido pela chave.
Como exemplo, imagine que temos \(P\)=CESAR, e \(K\)=I. Nesse caso, para encriptar, devemos transladar para a direita todas as letras em \(K\)=I=8 posições e obteríamos \(C\)=KMAIZ. Repare que a translação é cíclica, após o Z, temos o A novamente. Para decriptar, temos, trivialmente, que transladar todas as letras de \(C\) para a esquerda pela mesma quantidade.
A permutação realizada pode ser descrita por uma expressão simples:
$$c_i=(p_i + K) \mod26$$
Onde \(c_i\) e \(p_i\) são letras do ciphertext e do plaintext respectivamente.
Temos nesse caso um espaço de permutações possíveis de cardinalidade 26. Bastaria para um atacante testar as 26 chaves possíveis para descobrir o texto original. Além disso, a chave tem problemas como o fato de que duas letras iguais no plaintext sempre serão trocadas por outras duas letras iguais no ciphertext.
Uma cifra que buscou resolver essa alta previsibilidade da cifra de Cesar foi a cifra de Vigenère, que trocou a chave monoalfabética por uma polialfabética com um número \(|K|\in\mathbb{Z},|K|\leq|P|\) de letras. As permutações básicas (de cada letra) são equivalentes às da cifra de Cesar, para cada letra \(k_i\) da chave. A chave deve ser estendida, ciclicamente, para que tenha o mesmo número de caracteres do texto original.
Cada permutação básica é descrita como:
$$c_i=(p_i+k_{i\:mod\:|P|})\mod26$$
Vamos verificar se essas permutações, para qualquer chave \(k\), que evidentemente são elementos de \(S_{26}\), formam um subgrupo:
- A2 e A4 são necessariamente verdadeiras;
- A3: o subgrupo contém o elemento neutro, dado pela permutação com \(k_{i\:mod\:|K|}=A=0\).
- A1: Se para qualquer elemento desse subgrupo, for realizada uma composição com outra permutação do subgrupo, teríamos:
$$
\begin{align}p’_i & =(p_i+k_{i\:mod\:|K|})\bmod26 \\[6pt]
p”_i &= (p’_i + k’_{\,i \bmod |K|}) \bmod 26 \\[6pt]
&= \big((p_i + k’_{\,i \bmod |K|}) \bmod 26 + k_{\,i \bmod |K|}\big) \bmod 26 \\[6pt]
&= (p_i + k_{\,i \bmod |K|}+k’_{\,i \bmod |K|}) \bmod 26
\end{align}
$$
Isso é, a permutação resultante ainda pertence ao subgrupo (isso é esperado pois cifrar com uma chave \(k\) e depois com outra \(k’\) intuitivamente gera apenas um novo texto transladado por \(k+k’\)).
Assim esse conjunto obedece todos os axiomas de grupo e é por si só, de fato, um subgrupo.
Agora, vamos representar P e K em vetores e definir as permutações de Vigenère para uma chave fixa como uma função:
$$\tau_K(P)=(P+K)\bmod26$$
O conjunto dessas permutações também pertencem a um subgrupo de \(S_{26^{|P|}}\):
- A1 (Fechamento):
$$\tau_{K_1}∘\tau_{K_2}=(P+K_1+K_2)\bmod26=\tau_{K_1+K_2}$$
- A2 (Elemento Neutro): \(\tau_0\) (translação por vetor \(K=\vec{0}\) )
- A3 (Inversa): \(\tau_{-K}\), onde \(-K\equiv(26-K)\bmod 26\)
- A4 (Associativa): segue da associatividade do grupo \(S_{26^{|P|}}\)
O que é interessante agora é notar que as permutações básicas são dada por funções com K sendo um vetor proporcional a algum vetor de uma base canônica de um espaço \(\mathbb{Z}^{|P|}_{26}\) (isso significa que a partir das permutações básicas (de Cesar) podemos obter todos os \(26^{|P|}\) textos possíveis de tamanho \(|P|\) e todas as \(26^{|P|}\) permutações de translações possíveis.
Não por acaso, o grupo das permutações \(\tau_K\) é isomorfo ao grupo de translações vetoriais \((\mathbb{Z}^{|P|}_{26},+)\).
Apesar disso, é importante notar que o grupo simétrico \(S_{26^{|P|}}\) tem um número astronomicamente maior de permutações possíveis do que as da cifra de Vigenère para um mesmo plaintext de tamanho \(|P|\). Enquanto a segunda possui \(26^{|P|}\) permutações possíveis (para chaves de mesmo comprimento que o plaintext), a primeira possui \(26^{|P|}!\), com muitas delas realizando a mesma transformação \(P\mapsto C\) e \((26^{|P|}-1)!\) levando a ciphertexts iguais ao plaintext \(P\mapsto P\).
Podemos formalizar isso em termos de ações de grupo. Considere o grupo simétrico \(S_{26}^{|P|}\) agindo no conjunto de plaintexts possíveis, que vamos chamar de \(X\), com \(|X|=26^{|P|}\). A ação, evidentemente, é apenas aplicar uma permutação em \(X\) e deve obedecer as seguintes propriedades para todos \(g\) e \(h\) pertencentes a \(S_{26}^{|P|}\) e todo P pertencente a \(X\):
- 1. \(PId=P\)
- 2. \(P(g∘h)=(Pg).h\)
O ciphertext \(C\), portanto é apenas a imagem produzida pela ação do grupo no elemento \(P\).
Definimos a relação de equivalência \(\equiv\) da seguinte forma:
Def: Se \(P_1,P_2\in P\), dizemos que \(P_1\equiv P_2\) se existe \(g\in S_{26}^{|P|}\) tal que \(P_1g=P_2\).
E é útil definirmos as classes de equivalência de \(\equiv\), também chamadas de órbitas:
Def: \(PS_{26}^{|P|}:=\{C\in X\: | \: P\equiv C\}=\{Pg\: | \: g\in S_{26}^{|P|}\}\)
Ou seja, é o conjunto de ciphertexts obtíveis a partir das permutações do grupo simétrico.
Dizemos que um grupo \(G\) é transitivo em \(X\) se para quaisquer \(P_1,P_2\in X\), existe \(g\in G\) tal que \(P_1g=P_2\). Isso é, sempre é possível obter os elementos de X a partir de uma ação em outro elemento de X.
Evidentemente, o grupo \(S_{26}^{|P|}\) é transitivo em \(X\), pois sempre é possível obter um plaintext a partir de uma permutação de outro, mesmo se considerarmos apenas o pequeno subconjunto das permutações de Vigenère (i.e o grupo dessas permutações \(\tau\) também é transitivo em \(X\)).
Definimos ainda o estabilizador de um elemento \(P\in X\) no grupo \(S_{26}^{|P|}\) como \(G_P=\{g\in S_{26}^{|P|}\: | \: Pg=P\}\). Isso é, o conjunto de elementos do grupo que levam um \(P\) ao mesmo \(P\). Em criptografia esse conjunto de permutações não tem utilidade alguma, pois apenas levam um texto a ele mesmo, não escondendo a mensagem.
Agora, enunciamos o importante Teorema Órbita-Estabilizador: Seja \(G\) um grupo finito que age transitivamente em um conjunto \(X\) e seja \(P\in X\). Então:
$$|G|=|G_P|.|X|$$
Ora, para \(G=S_{26}^{|P|}\), vimos que temos \(26^{|P|}!\) elementos e, para \(X\), vimos que temos \(26^{|P|}\) elementos possíveis. Logo:
$$|G_P|=\frac{|G|}{|X|} \Rightarrow |G_P|=\frac{26^{|P|}!}{26^{|P|}} = (26^{P}-1)!$$
Isso confirma o que haviamos dito anteriormente.
Referências
BARATA, J. Grupos e Tensores: Notas de curso. São Paulo: Instituto de Física, Universidade de São Paulo, 2021. Disponível em: https://fma.if.usp.br/~jbarata/Grupos_e_Tensores-2021/Index.html. Acesso em: 17 set. 2025.
KATZ, J.; LINDLEY, A. Serious Cryptography: A Practical Introduction to Modern Encryption. [S.l.]: No Starch Press, 2018.
STALLINGS, W. Cryptography and Network Security: Principles and Practice. 8. ed. [S.l.]: Pearson, 2020.
Deixe um comentário