ISSN 2318-471X
ISBN: 978-85-8215-047-4
Números Inteiros Aplicados à Criptografia
José Rui Castro de Sousa, Samuel Chaves Dias, Weslley Florentino de Oliveira,
João Victor Quaresma Santos*, Jhonny Rodrigues Aguilar*, Jamille Lisboa
Silva*, Sara Botelho Moreira*.
Instituto Federal do Norte de Minas Gerais – Campus Almenara
Rodovia BR-367, s/n. Almenara, MG. 39900-000
E-mail: [email protected], [email protected], [email protected]
[email protected], [email protected], [email protected]
[email protected]
RESUMO
A Criptografia ou Criptologia é a prática e o estudo de métodos e processos para a
criação e o envio de mensagens codificadas, ou seja, disfarçadas. Esses disfarces são elaborados
com o objetivo de ocultar informações importantes de forma que apenas os destinatários sejam
capazes de ler a mensagem original. Dessa maneira, caso um terceiro indivíduo intercepte a
mensagem enviada ele não poderá compreendê-la em vista do disfarce elaborado. O processo
de transformar o texto original no texto codificado é chamado de codificação e o processo
inverso é de decodificação, ou seja, decodificar consiste em transformar o texto codificado no
texto original [1] [5]. De um modo geral a criptografia trata da construção e análise de
protocolos que estão relacionadas a vários aspectos de segurança da informação, tais como a
confidencialidade dos dados, integridade de dados, autenticação.
A criptografia moderna transita entre diversas áreas, principalmente na Matemática, na
Ciência da Computação e na Engenharia Elétrica. Aplicações de criptografia incluem cartões
eletrônicos, senhas de computador, e comércio eletrônico [1].
O desenvolvimento e segurança da maioria dos processos modernos estão intimamente
ligados à teoria dos números inteiros, mais especificamente aos números primos, que exercem
papel fundamental em tais processos [6].
Com o passar do tempo e com o desenvolvimento da ciência e consequentemente da
tecnologia, diversos métodos de criptografia foram criados e outros métodos já existentes
tornaram-se frágeis no que se refere segurança da informação.
Dentre os diversos métodos modernos de criptografia, existe o método RSA [3]. O
método tem esse nome devido às iniciais dos nomes de seus inventores (Rivest, Shamir e
Adleman). É um dos métodos mais populares de codificação com chave pública e funciona da
seguinte forma: Um indivíduo que deseja receber mensagens codificadas de certo grupo
disponibiliza para esse grupo um algoritmo para codificar as mensagens, esse algoritmo contém
um par de números chamado de chave pública. Depois de codificada a mensagem, não é
possível decodificá-la usando a chave pública da codificação, somente quem disponibilizou a
chave pública conhece outra chave, chamada chave privada, com a qual é possível decodificar a
mensagem.
A segurança do RSA está na dificuldade de se obter a chave privada. Mesmo
conhecendo a chave pública, a descoberta da chave privada está relacionada com a fatoração de
números inteiros muito grandes [4] [6]. Essa fatoração é feita utilizando-se algoritmos, que hoje
não são eficientes, do ponto de vista de tempo. Essa ineficiência permite que chave privada seja
mantida em segredo por tempo suficientemente para que a informação contida na mensagem
não seja mais interessante. O presente trabalho tem como objeto o estudo do método de
criptografia RSA. Procurar-se-á entender qual sua segurança do ponto de vista matemático e
computacional, e, com isso, possibilitar aos integrantes desse projeto um aprendizado de
conceitos matemáticos ligados à Aritmética e Teoria dos Números, um aprendizado em
programação e de conceitos em Ciência Computacional, bem como vivenciar a aplicabilidade
de conceitos matemáticos no mundo moderno.
A pesquisa foi dividida em três etapas:
* Aluno do curso Técnico Integrado de Informática e Bolsista de Iniciação Científica BIC
JUNIOR/FAPEMIG.
52
ISSN 2318-471X
ISBN: 978-85-8215-047-4
1. Construir junto com os alunos bolsistas os saberes necessários no que se refere
a números inteiros e criptografia. Nesse primeiro momento será utilizada uma
bibliografia básica, que são utilizadas normalmente em cursos de Matemática
Discreta, e já nessa etapa os alunos começarão a construir diversos algoritmos
de acordo com os conceitos estudados [2] [3] [6].
2. Um estudo mais específico e aprofundado do método RSA [6]. Por ser o objeto
da pesquisa, é importante que os alunos estudem o método mais a fundo,
investigando qual a segurança em termos matemáticos e em termos
computacionais. Pretende-se investigar também as possibilidades de
melhoramento do processo utilizado por esse método. Nessa etapa, os alunos
utilizarão os algoritmos construídos na fase anterior para construir o algoritmo
que utilize o Método de decodificação RSA.
3. Finalmente, a última etapa consiste em testar e melhorar o algoritmo construído
na etapa anterior e posteriormente partir para a solução de problemas que
envolvam a criptografia. Nessa fase os alunos poderão perceber a aplicabilidade
do método, bem como terão a oportunidade de visualizar possíveis fragilidades
do mesmo [1] [4] [5].
É importante ressaltar que durante todo o desenvolvimento da pesquisa criar-se-á
softwares que auxiliem nessa investigação. A criação de softwares para o apoio a pesquisa será
voltado para o desenvolvimento desktop. A princípio os alunos bolsistas deverão estudar alguns
conceitos de programação, de orientação a objetos e por fim aplicar a interdisciplinaridade entre
as questões matemáticas e computacionais. É importante ressaltar que a informática se
apresentará com ferramenta para o projeto. A linguagem abordada será a linguagem C++ [2],
tendo em vista sua conotação acadêmica, estando coerente com os conceitos de Ciência da
Computação, além de propor robustez e eficiência aos cálculos. Outro fator importante para
escolha da linguagem é a semelhança com a linguagem PHP (Personal Home Page), geralmente
utilizada para programação Web e que é apresentada para os alunos do curso técnico em
informática.
A pesquisa ainda encontra-se em andamento. Atualmente, o grupo de trabalho está
finalizando a primeira etapa. Para dar base matemática aos alunos do curso Técnico de
Informática integrado ao Ensino Médio, criou-se um grupo de estudo que trabalhou temas como
Números Naturais, Números Inteiros, Divisão Euclidiana, Máximo Divisor Comum, Mínimo
Múltiplo Comum, Equações Diofantinas, Congruência Módulo ݊, etc.
Junto ao estudo bibliográfico [3] [6], iniciou-se o desenvolvimento de alguns algoritmos
em linguagem C++, para solução de problemas que envolvam Teoria dos Números e que
futuramente servirão como partes do algoritmo capaz de codificar e decodificar pelo método
RSA. Foram implementados algoritmos de fatoração, de números inteiros e identificação se um
dado número inteiro é primo ou composto, algoritmo da divisão euclidiana, algoritmo
euclidiano para cálculo do Máximo Divisor Comum, algoritmo para o cálculo do Mínimo
Múltiplo Comum usando o anterior. O algoritmo para a solução de Equações Diofantinas
também já foi criado pelo grupo, e será usado em breve nos problemas envolvendo
congruências.
Até o presente momento os algoritmos tem sido capazes de resolver os problemas
propostos de forma eficiente. Tais algoritmos são partes importantes na construção do trabalho,
visto que além de constituírem um treinamento para os alunos integrantes do grupo na
linguagem C++, serão utilizados na implementação dos algoritmos de criptografia na fase final
do projeto e servirão de teste para análises relacionadas a tempo computacional gasto para
quebrar uma determinada chave de criptografia.
O processo investigativo desse projeto é marco diferencial na formação dos alunos
participantes. Esses têm a possibilidade de melhorar suas habilidades em programação, se
inteirar sobre problemas atuais em Ciência Computação, compreender de forma científica os
métodos utilizados para segurança de dados na atualidade, inserir-se o universo da pesquisa de
* Aluno do curso Técnico Integrado de Informática e Bolsista de Iniciação Científica BIC
JUNIOR/FAPEMIG.
53
ISSN 2318-471X
ISBN: 978-85-8215-047-4
forma a compreender a aplicação dos saberes para a solução de problemas atuais, vivenciar a
interdisciplinaridade, observar que as áreas do conhecimento dialogam e perceber o quanto a
Matemática se faz presente e necessária em nossa vida, desmistificando a ideia de que a
Matemática é uma Ciência isolada e sem aplicabilidade.
Palavras-chave: Criptografia, Números Inteiros, método RSA.
Referências
[1] C. Rackoff and D. Simon. Non-interactive zero-knowledge proof of knowledge and chosen
ciphertext attack. Advances in Cryptology – CRYPTO ’91, “Lecture Notes in Computer
Science Vol. 576” (J. Feigenbaum ed.), Springer-Verlag, 1991.
[2] H. M. Deitel, P. J. Deitel, “C++ Como Programar: 3 ed”. Bookman, São Paulo, 2001.
[3] M. C. Polcino; S. P. Coelho, “Números: Uma introdução à matemática”. Edusp, São Paulo,
2001.
[4] M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext
attacks. “Proceedings of the 22nd Annual Symposium on the Theory of Computing”,
ACM,1990.
[5] R. L. Rivest, A. Shamir, L. A. Adleman, A method for obtaining digital signatures and
public-key cryptosystems, Comm. ACM, vol. 21, pp. 120-126, (1978).
[6] S. C. Coutinho, “Números inteiros e criptografia RSA”. IMPA, Rio de Janeiro, 2009.
* Aluno do curso Técnico Integrado de Informática e Bolsista de Iniciação Científica BIC
JUNIOR/FAPEMIG.
54