* Aluno do curso Técnico Integrado de Informática e Bolsista de Iniciação Científica BIC JUNIOR/FAPEMIG.

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: jose.sousa@ifnmg.edu.br, samuel.chaves@ifnmg.edu.br, weslley.florentino@ifnmg.edu.br

joao_victorq@yahoo.com.br, jhonysaja@hotmail.com, jamille.portugal@hotmail.com sarinharubim@hotmail.com

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:

52

ISSN 2318-471X ISBN: 978-85-8215-047-4

* Aluno do curso Técnico Integrado de Informática e Bolsista de Iniciação Científica BIC JUNIOR/FAPEMIG.

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

53

ISSN 2318-471X ISBN: 978-85-8215-047-4

* Aluno do curso Técnico Integrado de Informática e Bolsista de Iniciação Científica BIC JUNIOR/FAPEMIG.

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.

54

ISSN 2318-471X ISBN: 978-85-8215-047-4