Nas aulas de Tecnologia de Redes de Computadores, com o prof. Cabrini, nós fizemos uma atividade de criptoanálise. Neste post, não falarei da atividade em aula, pois não convém. Falarei de como resolvi o desafio de criptografia na pasta do professor:
📌Criptografia é o 'conjunto de técnicas de descaracterização da informação baseada em algoritmos matemáticos'
O título do arquivo mostrava que a técnica de criptografia era a Cifra de Hill. Primeiro eu tive que pesquisar qual tipo de cifra era essa, como se codificava e como se decodificava. Tudo isso foi encontrado na Wikipédia [1], mas de forma simplificada:
- Cifra de Hill é uma cifra de substituição de chave assimétrica
- A mensagem é codificada com uma matriz quadrada NxN
- E é decodificada com o inverso dessa matriz
O que isso quer dizer?
Uma cifra de substituição significa que a cada letra do alfabeto é atribuído um símbolo e a criptografia se dá pela troca de cada letra da mensagem pelo se par. Essa atribuição pode ser proveniente de uma simples rotação (deslocamento) do alfabeto, como na famosa Cifra de César; de um embaralhamento lógico como a Cifra de Vigenère [2]; ou ao acaso, como recomendado às mulheres no livro Kama-Sutra, para que pudessem manter detalhes de seus relacionamentos em segredo[3].
O processo de criptografar
Cada letra é associada com um número decimal. O exemplo mais simples fornecido pela própria Wikipédia é a da numeração simples do alfabeto, contada a partir do zero:
A mensagem seria, então, reescrita com os números e separada em partes. Cada parte conteria N números. Então, por exemplo, a mensagem:
Cada uma dessas partes, com suas letras já reescritas em seus correspondentes números, são colocadas em uma matriz-coluna Nx1 (N linhas e 1 coluna) de forma ordenada. Assim, com N = 3, o valor correspondente à letra "C" será o elemento da primeira linha, "R" da segunda, e "I" da terceira; "P" será o elemento da primeira linha da próxima matriz, "T" da segunda, e "O" da terceira da terceira linha; e assim por diante (vide imagens abaixo). No final, teremos uma quantidade X de matrizes-coluna, sendo X igual ao número de caracteres na mensagem dividido por N. No exemplo dado, CRIPTOGRAFIA tem 12 letras, logo, com N = 3, teremos 4 matrizes-colunas (X = 12 / 3; X = 4).
A chave de criptografia, por sua vez, deve ser uma matriz quadrada NxN que possua matriz inversa. A criptografia se dá quando multiplicamos as matrizes da forma: CHAVE x TRECHO DA MENSAGEM, nessa ordem, com cada um dos X trechos de mensagem. A matriz resultante será uma nova matriz-coluna Nx1 e os números substituirão os números da mensagem, também de forma ordenada.
Refere-se, então, à tabela utilizada para passar as letras para números para trocar a sequência de número encontrada pela mensagem decodificada.
O processo de descriptografar
Acredito que a Cifra de Hill é uma técnica de criptografia de chave assimétrica porque a chave para codificar e a para decodificar não são as mesmas, mas sim um par de chaves. Quando uma dessas chaves é usada para criptografar, apenas a outra consegue descriptografar a mensagem. O par de chaves da Cifra de Hill é uma matriz NxN e a sua inversa, outra matriz quadrada NxN.
Não vou me prolongar tanto no processo de descriptografia, uma vez que logo abaixo eu colocarei a resolução do desafio dado, mas ele é, basicamente, o mesmo processo usado para criptografar:
- Escreve-se a mensagem substituindo os caracteres por números de acordo com a tabela decidida pelo remetente e destinatário
- Separa-se em X matrizes-coluna de ordem Nx1
- Multiplica-se as matrizes de tal forma: MATRIZ INVERSA x MATRIZ-COLUNA
- Após fazer a multiplicação das X matrizes-coluna, o resultado é escrito sequencialmente
- Refere-se à tabela para substituir os números pelos caracteres
Resolução do desafio
Primeiro passo: encontrar a tabela de conversão
Em aula, usamos American Standard Code for Information Interchange. Cada letra ASCII é associada a um número decimal que é padrão para qualquer computador do mundo, para que os computadores possam se comunicar.
Os computadores se comunicam por binário (bits). Por exemplo: quando digitamos o símbolo “a” no teclado, ele será entendido como o número decimal 97 e será convertido no binário 11000001 para ser transmitido ou armazenado. Até o número 127 da tabela ASCII é padrão e universal a todos os computadores, a partir daí, começa a codificação. No Brasil, por exemplo, usamos a codificação UTF-8, para podermos usar o cedilha, a crase, etc.
🚨Cuidado, é preciso manter a integridade da mensagem! Deve-se respeitar letras maiúsculas e minúsculas. Assim, A (65) ≠ a (97)!
Com planilhas do Excel ou Sheets, é possível fazer a conversão de decimal para binário, hexadecimal, e até para os caracteres da ASCII com fórmulas básicas. Abaixo uma parte da tabela completa feita em aula e a fórmula:
Além do UTF-8, há outras formas de encodings [4]. Para esses caracteres, eu os achei no Unicode no site: symbl.cc [5]. O Unicode [6] é uma forma de encoding mais completo, com 17 planos, incluindo caracteres do alfabeto japonês, turco, etc. Com a tabela que eu iria tentar usar definida, agora eu precisava achar quais números decimais correspondem aos caracteres da mensagem: SŢÕVŝØOƙóMŢÏEŰá.
Segundo passo: calcular a chave
Como foi dado a Chave de Criptografia, bastou calcular a inversa, sabendo que MATRIZ x INVERSA = MATRIZ IDENTIDADE. É possível fazer esse (e os próximos cálculos) facilmente com a Matrix Calculator. O resultado obtido está abaixo:
Terceiro passo: multiplicação CHAVE x TRECHO DA MENSAGEM
Os decimais resultantes foram: 83 65 76 86 65 68 79 82 84 77 82 84 69 78 65
Quarto passo: MI → caracter
Na planilha, usei a fórmula para obter a mensagem final (ou pelo menos eu acredito que cheguei na resposta certa):
Ufa! Fiquei animadíssima de ter conseguido resolver esse desafio, mas eu não podia parar aí. Eu queria fazer um programa em Python que conseguisse quebrar qualquer outra mensagem criptografada com a cifra de Hill, independente da chave. O código está disponível no meu repositório no GitHub.
Abaixo, algumas imagens dos testes unitários do programa:
O Decodificador Hill Cipher:
- Solicita o valor de N;
- Pede ao usuário que insira cada elemento da matriz NxN (chave de criptografia);
- Solicita a mensagem criptografada;
- O output esperado é a mensagem decodificada.
Até agora, o código resolve apenas cenários mais simples do uso de cifra. Em alguns casos, é possível que seja necessário fazer arredondamentos nas contas e outras acomodações, mas esse não era bem o foco do exercício.
Excelente trabalho. Parabéns!
ResponderExcluir