ALGORITMOS BÁSICOS EM CRIPTOGRAFIA
Rafael Antonio da Silva Rosa (IC)
Instituto Tecnológico de Aeronáutica (ITA)
Pça. Mal. Eduardo Gomes, 50, Vila das Acácias, 12228-901, S. José dos Campos – SP
[email protected]
Antonio Cândido Faleiros (PQ)
Instituto Tecnológico de Aeronáutica (ITA)
Divisão de Ensino Fundamental
[email protected]
RESUMO
Devido ao nível avançado da criptografia atual, faz-se necessária a possibilidade de se operar com
números relativamente grandes, mas para isso deve ter uma estrutura de dados para tal. Esse foi o
enfoque principal deste trabalho, juntamente com a elaboração de funções de operações utilizando
essa estrutura. Posteriormente, a titulo de exemplificação, estudou-se e simulou-se a máquina
criptográfica Enigma, importante arma alemã na Segunda Guerra Mundial.
ABSTRACT
Because of advanced level of present criptography, operations with large numbers are necessary, but
one should have a data structure. That was our main goal, together with the elaboration of functions
which utilize it.As an example, it is studied and simulated the criptographic machine Enigma,
important German device in the Second World War.
1. INTRODUÇÃO
Nos dias de hoje, com a ampliação das comunicações via Internet, a questão de segurança dos
dados transmitidos tem se mostrado crucial. A cada dia que passa, amplia -se o número de pessoas
dedicadas ao estudo e desenvolvimento de técnicas que têm por finalidade proteger a informação. Uma
das técnicas a nossa disposição para garantir a integridade dos dados é justamente a criptografia, unida
aos diversos protocolos desenvolvidos para assegurar uma comunicação sem interferências indevidas e
não autorizadas. Apesar disso, a criptografia é, provavelmente, tão antiga quanto a própria escrita.
Entretanto, só recentemente, se tornou alvo de extenso estudo científico.
Esse assunto tem se tornado cada vez mais importante e já existem restrições para a venda de
programas que realizam uma criptografia segura. Trata-se, portanto, de um assunto emergente e
urgente para ser estudado e desenvolvido aqui em nosso país, com o intuito de evitar a dependência de
produtos cujo fornecimento pode ser descontinuado a qualquer momento.
Nesse trabalho, foi proposto primordialmente o desenvolvimento de uma série de algoritmos
que deveriam ser implementados em forma de programas em linguagem C, necessários para a
execução de criptografia de textos e de dados, também em linguagem C. Numa etapa inicial, a
proposta foi o estudo de alguns algoritmos básicos e, logo após, o início de suas respectivas
implementações:
· operações de expansão e redução;
· operações de adição, subtração e multiplicação de números inteiros;
· aritmética modular: módulo de Barret;
·
·
máximo divisor comum;
simulação em linguagem C da máquina Enigma, usada pelos alemães na Segunda Grande
Guerra Mundial, e análise de suas seqüências.
2. AS FERRAMENTAS CRIPTOGRÁFICAS
Iniciados os estudos, começou-se a implementação de algumas operações inteiras. Na
criptografia moderna é importante, freqüentemente, fazer operações algébricas com números inteiros
muito grandes (100 algarismos decimais ou mais), e essa foi a tarefa inicial: implementar algoritmos
para se efetuar essas operações de maneira eficiente. E como as operações normais de um computador
não são suficientes para essa criptografia, teve-se que criar “novas” técnicas envolvendo números
inteiros muito grandes.
2.1. A Primeira Forma de Armazenamento de Dados
Usou-se inicialmente como modo de armazenamento o tipo “caracter”, em que cada algarismo
era armazenado como um “caracter”, ou seja, um número era uma “string”, e o sinal era armazenado
como sendo o “+” ou o “-”.
A primeira operação feita (na verdade é uma pseudo-operação, pois não altera o valor do
número) foi a redução, que verifica e faz com que o número fique com o menor número possível de
algarismos. Essa operação é normalmente usada no fim de algoritmos, para que se tenha certeza de
que o número não estará desperdiçando memória.
Depois ainda foram implementados com esse método de armazenamento os programas:
Conversão de Bases; Operação de Módulo Clássico (“resto” de uma divisão); MDC de Euclides
(algoritimo de Euclides para o cálculo do máximo divisor comum); MDC de Euclides Extendido (que
fornece X e Y, sendo que A.X + B.Y = D, onde D = mdc (A,B) ); MDC Binário; e MDC Binário
Extendido.
2.2. Armazenamento de Dados Utilizando Números Binários
Foi percebido que uma nova forma de armazenamento dos números seria mais viável, mais
prática, mais simples para se fazer cálculos e ainda ocuparia menos posições da memória. Essa idéia
de armazenamento consistia em se trabalhar puramente com os números binários, sem pensar em
qualquer correspondência em decimal, ou seja, o número binário não era “divido” por algarismos, era
um número só, era um binário puro.
Os bits mais significativos eram armazenados nas posições de menor endereço da memória. E
o sinal era armazenado no bit mais significativo do número (o bit menos significativo na memória),
sendo que “0” correspondia a um número positivo e “1” logicamente a um negativo.
Mas agora, era preciso criar até as funções para o armazenamento dos números, já que se
estaria trabalhando com um “novo” tipo de variável. E o primeiro programa feito utilizando esse novo
método foi o mais básico e importante para a continuação do trabalho: leitura e armazenamento de
dados, usando-se leitura do teclado, para fins de testes, assim como a função que rotaciona o número e
a função que o imprime na tela.
Outros algoritmos também implementados, agora com esse tipo de armazenamento, foram os
seguintes: Operação de Redução, Operação Maior ( > ), Operação de Expansão, Operação de Soma de
Dois Números Inteiros Positivos, Operação de Subtração de Dois Números Inteiros Positivos, e
Operação de Soma de Dois Números Inteiros Quaisquer (utiliza os dois últimos programas: soma e
subtração de dois números positivos).
2.3. Utilizando “Structs” para Fazer a Passagem de Dados
Para resolver alguns problemas que surgiram na execução dos programas, devido ao grande
número de ponteiros , teve-se a idéia de criar estruturas de dados em que vários ponteiros fazem parte
de uma “mesma variável”: as chamadas “structs”. Assim, quando for necessário fazer a passagem de
dados para uma função, todos os dados são passados de uma só vez.
Os programas feitos que utilizaram essas idéias descritas até aqui foram a Operação de Soma
de Dois Números Inteiros Quaisquer (que teve pouquíssimas mudanças) e a Operação de Subtração de
Dois Números Inteiros Quaisquer.
3. A CONSTRUÇÃO E A UTILIZAÇÃO DE UMA BIBLIOTECA PRÓPRIA
A partir desses programas, utilizou-se uma biblioteca “criptográfica” exclusivamente
construída nesse trabalho. Essa biblioteca contém, nada mais nada menos que, todas as funções já
implementadas, e com o passar do tempo, essa biblioteca foi sempre alterada (acrescentada de novas
funções), assim os programas ficam pequenos, com somente a função principal. É uma maneira muita
mais prática de se trabalhar com essas funções.
O primeiro programa implementado utilizando essa biblioteca foi a Operação de Multiplicação
de Dois Números Inteiros Quaisquer, que usa como função a operação de soma.
4. A FORMA MAIS EFICIENTE DE ARMAZENAMENTO: O USO DA BASE 256
Descobriu-se uma outra nova idéia de armazenamento de dados, que funciona como se o
número fosse escrito na base 256 (duzentos e cinqüenta e seis), de forma que todos os bytes são
completamente preenchidos, ou seja, se um número não ocupar um número de bits que seja múltiplo
de 8 (oito), ele é remanejado de forma a ocupar completamente o byte menos significativo e
completando o mais significativo com zeros, ou melhor, esse número é expandido de forma a ocupar
perfeitamente uma “quantidade inteira” de bytes. Assim, os operações ficam incrivelmente mais
simples, mais rápidas e mais fáceis de serem implementadas e executadas, com uma menor chance de
erro.
Outra mudança feita conjuntamente de forma a facilitar ainda mais as implementações foi a do
armazenamento do sinal. A partir de agora o sinal é armazenado em uma outra variável e não mais
junto com o próprio número. É armazenado na variável que contém o tamanho do número (possui a
quantidade de bytes) da seguinte forma, se o número for positivo, a variável que contém o número de
bytes possui um número positivo, caso contrário, essa variável guarda um número negativo, portanto
essa variável armazena um número que em módulo é igual à quantidade de bytes do número.
Mas devido a essa mudança completa na estrutura de dados, foi necessário mais uma vez refazer todos
os programas anteriormente já feitos: Leitura e Armazenamento de Dados, Operação de Redução,
Operação de Expansão, Operação Maior ( > ), e a Operação de Soma de Dois Números Inteiros
Positivos. E assim, a biblioteca criptográfica foi totalmente alterada.
5. SIMULAÇÃO DO ENIGMA
5.1. A Máquina
O Enigma foi uma máquina de codificação de mensagens utilizada pelos alemães na Segunda Guerra
Mundial. Era uma máquina eletromecânica constituída basicamente de discos com circuitos elétricos
que transmitiam um sinal proveniente de um teclado, indicando para cada dígito uma outra letra,
codificando assim a mensagem.
Cada um de seus discos possuía 26 pontos em cada uma de suas faces, correspondendo às
letras do alfabeto, sendo que cada ponto de uma face era conectado a um outro ponto da face oposta
por meio de circuitos elétricos. E cada disco se interligava com outro através do simples contato. O
último disco era diferente, chamado de refletor, possuía pontos em apenas uma das faces, e cada ponto
era ligado a outro da mesma face.
Quando um tecla era acionada, um sinal gerado passava por todos os discos percorrendo um
caminho de acordo com as conexões, indo até o disco refletor e voltando até o primeiro disco, e uma
lâmpada era acesa indicando uma outra letra.
Além disso, a cada tecla digitada, o primeiro disco girava uma posição (um ponto, ou 1/26 de
uma volta), e a cada volta completa do primeiro disco, o segundo também girava uma posição, e assim
por diante. Assim, o enigma era uma excelente máquina criptográfica, dificílima de ser decodificada,
pois para isso era preciso saber quais eram as ligações internas de cada um dos discos, sua ordem e
suas respectivas posições iniciais.
5.2. O Programa Simulador
Este programa simula a máquina descrita acima, sendo que o principal artifício utilizado foi a
utilização de matrizes para a simulação dos discos. São matrizes numéricas, com 52 posições (26
extras para facilitar a rotação), que possuem em cada posição o índice da próxima matriz, ou seja, em
que ponto do próximo disco o ponto do disco “atual” está em contato.
Para cada um dos discos existem duas matrizes: uma de “ida” e outra de “volta”, pois não há
como utilizar a mesma matriz para os dois sentidos. E como os dois sentidos tem que seguir
rigorosamente o mesmo “caminho”, a matriz de volta é construída através da matriz de ida, da
seguinte forma: “mv [ mi [ i ] ] = i”, onde “mi” é a matriz de ida e “mv” a matriz de volta. Por
exemplo: se a posição 5 da matriz de ida possui o valor 7, a posição 7 da matriz de volta possui o valor
5. Apenas o disco refletor possui uma única matriz. E todas as matrizes são utilizadas uma só vez por
tecla digitada.
Neste programa, utiliza-se a função randômica para construir os discos, e a rotação desses
discos é feita através da adição de uma variável a cada índice de cada uma das matrizes,
incrementando-os nos momentos necessários.
Foi feito neste programa a decodificação, voltando cada disco à sua posição inicial, para que
assim, através da digitação da mensagem codificada, obtenha-se a mensagem original.
6. CONCLUSÕES
Com todo o estudo inicial, conclui-se que a criptografia deve ser pesquisada bem a fundo, de
forma a se desenvolver bons programas criptográficos no país, garantindo assim a nossa segurança,
pois hoje, o que realmente poderia nos preocupar seria uma “guerra eletrônica”, e a criptografia busca
justamente uma proteção nessa área.
Claramente pode-se ver que as liberdades individuais estão comprometidas. Cabe ao nosso
país concorrer nessa competição criptográfica, tanto na área comercial quanto na militar, além do que
todas as pessoas têm direito a uma proteção criptográfica eficaz.
No desenvolvimento desse trabalho, encontrou-se mais dificuldades do que se imaginava no
início. As operações entre números binários causavam “bugs” na memória, da mesma forma que os
diversos “ponteiros” utilizados.
Foi preciso diversas vezes encontrar formas “alternativas” para contornar esses problemas, o
que causou a necessidade de refazer diversas vezes os mesmos programas, ocasionando assim um
grande “atraso” no cronograma inicial, pois alguns programas foram feitos até quatro vezes.
Essas formas, aqui chamadas de “alternativas”, foram encontradas mediante árduo estudo,
pesquisa e criação. E como isso demanda um tempo considerável, essa foi mais uma causa do grande
“atraso”. Cada um desses problemas e suas respectivas soluções foram explicados anteriormente no
decorrer do relatório.
Este fato também é verificado quando se analisa a quantidade de programas/algoritmos
implementados. Fez-se até aqui exatamente 22 (vinte e dois) programas, 4 (quatro) versões de
bibliotecas criptográficas e um programa de simulação, sendo que apesar destes números expressivos,
não foram implementados nem 20% do esperado em número de funções diferentes; pois nunca fora
cogitada a possibilidade de implementar mais de uma vez cada um dos programas propostos.
E finalmente, na etapa final do trabalho, realizou-se uma simulação do Enigma (máquina
criptográfica alemã utilizada na II Grande Guerra Mundial), que não chegou a ser uma versão
definitiva, podendo assim ser melhorada, mas que mesmo assim alcançou grande sucesso.
AGRADECIMENTOS
Os autores gostariam de agradecer à professora Tania Nunes Rabelo pela ajuda e pelo
acompanhamento neste trabalho.
REFERÊNCIAS BIBLIOGRÁFICAS
1. Carvalho, D.B.; Segurança de Dados com Criptografia: Métodos e Algoritmos; Book Express; Rio
de Janeiro, 2000.
2. Stinson, D.R.; Cryptography: Theory and Practice; CRC Press; New York, 1995.
3. Terada, R.; Segurança de Dados: Criptografia em Redes de Computadores; Edgard Blücher; Rio de
Janeiro, 2000.
4. Singh, S.; O Livro dos Códigos - A Ciência do Sigilo: do Antigo Egito à Criptografia Quântica;
Record; Rio de Janeiro, 2001.