Criptografia Teoria dos Numeros

Prévia do material em texto

CENTRO UNIVERSITÁRIO JORGE AMADO – UNIJORGE 
BACHAREL EM CIÊNCIAS DA COMPUTAÇÃO 
 
 
ADNAM WILLIAM 
FILIPE DA SILVA 
JOÃO GABRIEL 
MARCOS VINICIUS 
SAULO LINS 
 
 
 
 
 
 
 
 
 
 
 
 
CRIPTOGRAFIA 
Conceitos e Aplicações na Área de Informática 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Salvador - BA 
2018 
 
 
ADNAM WILLIAM 
FILIPE DA SILVA 
JOÃO GABRIEL 
MARCOS VINICIUS 
SAULO LINS 
 
 
 
CRIPTOGRAFIA 
Conceitos e Aplicações da Área de Informática 
 
 
 
Trabalho final, apresentado a disciplina de 
Teoria dos Números, como parte das 
exigências para a obtenção de nota da 3ª 
avaliação. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Salvador – BA 
2018
1 
 
SUMÁRIO 
 
1 Introdução ........................................................................................................... 2 
2 Criptografia ......................................................................................................... 3 
2.1 Histórico ........................................................................................................ 3 
2.2 Tipos de criptografia ...................................................................................... 5 
2.2.1 Chaves Simétrica ................................................................................... 5 
2.2.2 Chaves Assimétrica ................................................................................ 5 
2.2.3 Criptografia nas Redes Sem Fio ............................................................. 6 
2.2.4 Assinatura Digital .................................................................................... 7 
2.2.5 Criptografia Quântica .............................................................................. 7 
3 Criptografia RSA ................................................................................................. 8 
4 Referências ....................................................................................................... 11 
 
 
2 
 
1 INTRODUÇÃO 
Do latim cryptographia, a palavra criptografia nasce da união do termo grego cripto, 
que significa oculto, secreto, obscuro e inteligível, com graphía, cujo sentido é de 
escrita, formando o que seria a “escrita secreta”. Basicamente, a criptografia é uma 
forma de codificação, isto é, a criação de um código que protege os dados. 
Muito embora hoje seja vinculada à tecnologia, o uso da criptografia é tão antigo 
quanto a necessidade do homem em esconder informação. Pesquisadores atribuem 
o uso mais antigo da criptografia aos hieróglifos encontrados em monumentos do 
Antigo Egito, cerca de 4.500 anos atrás, época em que o mundo parecia se dividir 
apenas em gregos e romanos. Era a época da criptografia clássica. 
Sabendo-se então da importância da criptografia na proteção dos dados e de diversos 
tipos de informação, e sua ampla utilização atualmente por meios tecnológicos, fez-
se necessário a elaboração de uma pesquisa, afim de poder compreender melhor a 
história, o conceito e as suas principais abordagens nos meios modernos. 
3 
 
2 CRIPTOGRAFIA 
O termo Criptografia surgiu da fusão das palavras gregas "Kryptós" e "gráphein", que 
significam "oculto" e "escrever", respectivamente. Trata-se de um conjunto de regras 
que visa codificar a informação de forma que só o emissor e o receptor consigam 
decifrá-la. Para isso várias técnicas são usadas, e ao passar do tempo modificada, 
aperfeiçoada e o surgimento de novas outras de maneira que fiquem mais seguras. 
Na computação, a técnica usada são a de chaves, as chamadas “chaves 
criptográficas”, trata-se de um conjunto de bits baseado em um algoritmo capaz de 
codificar e de decodificar informações. Se o receptor da mensagem usar uma chave 
diferente e incompatível com a do emissor ela não conseguirá ter a informação. 
A primeira técnica utilizava apenas um algoritmo de decodificação. Assim, bastava o 
receptor do algoritmo para decifrá-la, mas caso um intruso conhecesse esse mesmo 
algoritmo, ele poderia decifrar a informações se interceptasse os dados 
criptografados. Hoje, entre as técnicas mais conhecidas há o conceito de chaves, ou 
então chaves criptográficas, no qual um conjunto de bits baseado em um determinado 
algoritmo é capaz de codificar e de decodificar informações. Há dois tipos de chaves, 
a simétrica e a assimétrica, ou chave pública. Caso o receptor da mensagem resolva 
usar uma chave incompatível com a chave do emissor, a informação não será 
compartilhada. Há ainda outros conceitos envolvidos na área da criptografia, como a 
Função Hashing, usada em assinaturas digitais para garantir integridade, e as 
aplicações, como a certificação digital. 
 
2.1 Histórico 
A história da criptografia começa há milhares de anos, com os Hebreus a 600 a.C., 
por meio de cifras de substituição monoalfabéticas (onde um símbolo do alfabeto é 
substituído por outro símbolo no alfabeto cifrado), como por exemplo, a cifra Atbash, 
que consiste na substituição da primeira letra do alfabeto pela última, da segunda pela 
penúltima, e assim por diante. Com o início das pesquisas sobre criptoanálise por volta 
de 800 d.C., o matemático árabe Ibrahim Al-Kadi inventou a técnica de análise de 
frequência para quebrar esse tipo de cifra. Ele também expôs métodos de cifragem 
como, por exemplo, a criptoanálise de certas cifragens e a análise estatística de letras 
e combinações de letras em árabe. 
Até o início da primeira guerra mundial, nada de inovador havia sido desenvolvido no 
campo de criptografia, até que Alexander´s Weekly escreveu um ensaio sobre 
métodos de criptografia, que se tornou útil como uma introdução para os 
criptoanalistas britânicos na quebra dos códigos e cifras alemães durante a I Guerra 
Mundial; e escreveu uma história famosa, O Escaravelho de Ouro, um conto 
ambientado no século XIX onde a criptoanálise era um elemento de destaque. 
4 
 
Além de ser um importante instrumento de quebra de códigos navais alemães, que 
chegaram a decidir o destino de batalhas, a contribuição mais importante do uso de 
seus conceitos, foi decodificar o telegrama de Zimmermann, enviado ao embaixador 
alemão no México, Heinrich Von Eckardt, instruindo-o a se aproximar do governo 
mexicano e propor uma aliança militar contra os EUA, em troca ele prometia ao México 
terras norte-americanas, caso o país aceitasse o acordo. O telegrama foi interceptado 
pela Inglaterra e enviado ao governo norte americano, o que apressou a entrada dos 
EUA na primeira guerra mundial. 
 
 
2-1 Telegrama alemão interceptado pela Inglaterra. 
 
Durante a segunda guerra mundial, os alemães usaram uma máquina eletromecânica 
para criptografar e descriptografar, denominada de Enigma. Logo após o estopim da 
segunda guerra mundial, um grupo de criptógrafos britânicos (alguns matemáticos e 
mestres em xadrez, tais como Newman e Alan Turing, o pai da computação moderna) 
conseguiu quebrar as cifras da Enigma e decifrar mensagens secretas dos nazistas. 
Os militares alemães implantaram maquinas usando one-time pad (cifra de chave 
única), um algoritmo de criptografia onde o texto é combinado com uma chave 
aleatória; enquanto isso, os ingleses criaram o primeiro computador digital 
programável, o Colossus, para ajudar com sua criptoanálise. Agentes britânicos do 
SOE usavam inicialmente "cifras poema" (poemas memorizados eram as chaves de 
encriptação/desencriptação), mas, mais tarde, durante a Segunda Guerra, eles 
modificaram para o one-time pad. 
5 
 
Durante a chamada "Guerra Fria", entre EstadosUnidos e União Soviética, foram 
criados e utilizados diversos métodos para esconder mensagens com estratégias e 
operações. Desses esforços, surgiram outros tipos de criptografia, tais como: por 
chave simétrica, onde existe uma chave com um segredo e essa chave é 
compartilhada pelos interlocutores; por chave assimétrica, onde existem 2 chaves, 
uma pública e uma privada, a chave privada é usada para cifrar a mensagem, com 
isso garante-se que apenas o dono da chave poderia tê-la editado; por hash e até a 
chamada criptografia quântica, que se encontra, hoje, em desenvolvimento. 
Atualmente, a criptografia é comumente usada na internet, principalmente na proteção 
de transações financeiras, em segurança e acesso em comunicação. A criptografia 
quântica também é um tema que tem ganhado atenção nos laboratórios de pesquisa, 
ela se destaca por não correr um alto risco de interceptação ao necessitar de uma 
comunicação secreta prévia para envio de chaves, pois esta técnica criptográfica não 
se baseia em funções, mas nas leis da física. 
2.2 Tipos de criptografia 
2.2.1 Chaves Simétrica 
A mesma chave é utilizada tanto pelo emissor quanto por quem recebe a informação. 
Ou seja, a mesma chave é utilizada para codificação e para a decodificação dos 
dados. Não é recomendado seu uso para guardar informações muito importantes. 
Vamos ver alguns exemplos: 
• DES (Data Encryption Standard): Criado em 1977 pela IBM, é considerado 
inseguro devido a suas chaves de 56-bits (permite até 72 quatrilhões de 
combinações). Foi quebrado utilizando o método de “força bruta” (tentativa e 
erro); 
• IDEA (International Data Encryption Algorithm): Criado em 1991 por James 
Massey e Xuejia Lai. Utiliza chaves 128-bits e possui estrutura parecida com a 
do DES; 
• RC (Ron's Code ou Rivest Cipher): Existem diferentes versões do algoritmo, 
como a RC4, RC5 e RC6, todas criadas por Ron Rivest na empresa RSA Data 
Security. Muito utilizado em e-mails, usa chaves de 8 a 1024 bits. 
• Blowfish: Desenvolvido em 1993 por Bruce Schneier, utiliza chaves de 32 a 
448-bits. O algoritmo não é patenteado, tem sua licença grátis e está à 
disposição de todos. 
 
2.2.2 Chaves Assimétrica 
Trabalha com duas chaves: uma privada e outra pública. Alguém deve criar uma chave 
de codificação e enviá-la a quem for lhe mandar informações. Essa é a chave pública. 
6 
 
Outra chave deve ser criada para a decodificação. Esta, a chave privada, é secreta. 
Veja alguns exemplos: 
• El Gamal: Criado pelo estudioso de criptografia egípcio Taher Elgamal em 
1984. Utiliza o problema “logaritmo discreto” para segurança. 
• RSA (Rivest, Shamir and Adleman): Criado por três professores do MIT, é um 
dos algoritmos mais usados e bem-sucedidos. Utiliza dois números primos 
multiplicados para se obter um terceiro valor. A chave privada são os números 
multiplicados e a chave pública é o valor obtido. Utilizada em sites de compra 
e em mensagens de e-mail. 
 
2.2.3 Criptografia nas Redes Sem Fio 
As redes wireless abriram uma brecha enorme na segurança dos dados. Isso porque 
os dados podem ser facilmente interceptados com algum conhecimento técnico. 
Isso obrigou o desenvolvimento de técnicas de criptografia para tornar esse tipo de 
comunicação viável, não só para empresas que decidem conectar seus usuários por 
meio de redes sem fio, mas também para que os usuários domésticos possam realizar 
suas transações financeiras com mais segurança e privacidade. 
Os tipos de criptografia mais usados nas redes wireless são: 
• WEP: esta técnica usa uma chave secreta compartilhada e o algoritmo de 
criptografia RC4. O roteador wireless ou ponto de acesso, bem como todas as 
estações que se conectam a ele devem usar a mesma chave compartilhada. 
Para cada pacote de dados enviado em qualquer direção, o transmissor 
combina o conteúdo do pacote com uma soma de verificação desse pacote. O 
padrão WEP pede então que o transmissor crie um IV (Initialization Vector, 
vetor de inicialização) específico para o pacote, que é combinado com a chave 
e usado para criptografar o pacote. O receptor gera seu próprio pacote 
correspondente e o usa para decodificar o pacote. Em teoria, essa abordagem 
é melhor do que a tática óbvia de usar apenas a chave secreta compartilhada, 
pois inclui um bit de dado específico para o pacote que dificulta sua violação. 
Entretanto, se uma chave compartilhada estiver comprometida, um invasor 
poderá bisbilhotar o tráfego de informações ou entrar na rede. 
• WPA e WPA2: estes certificados de segurança são baseados no padrão da Wi-
Fi Alliance para redes locais sem fio e utilizados por muitas empresas e até em 
redes domésticas. Eles permitem autenticação mútua para verificação de 
usuários individuais e criptografia avançada. A WPA fornece criptografia para 
empresas, e a WPA2 – considerada a próxima geração de segurança Wi-Fi – 
vem sendo usada por muitos órgãos governamentais em todo o mundo. “O 
WPA2 com AES é a novidade, tanto para o uso corporativo quanto para o 
7 
 
pessoal. Ao usuário residencial, ele garante um excelente padrão de segurança 
e, aos usuários corporativos, permite agregar um servidor de autenticação para 
controle dos usuários em conjunto com a criptografia”, avalia Diogo Superbi, 
engenheiro de vendas da Linksys no Brasil. 
 
2.2.4 Assinatura Digital 
Um recurso conhecido por Assinatura Digital é muito usado com chaves públicas. 
Trata-se de um meio que permite provar que um determinado documento eletrônico é 
de procedência verdadeira. 
Quem recebe um documento assinado digitalmente usa a chave pública fornecida 
pelo emissor para se certificar da origem. Além disso, a chave é integrada ao 
documento – isso implica que qualquer alteração realizada nas informações vai 
invalidar o documento. 
 
2.2.5 Criptografia Quântica 
Este tipo de codificação de informação difere dos demais métodos criptográficos 
porque não precisa do segredo nem do contato prévio entre as partes. 
8 
 
3 CRIPTOGRAFIA RSA 
RSA (Rivest-Shamir-Adleman) é um dos primeiros sistemas de criptografia de chave 
pública e é amplamente utilizado para transmissão segura de dados. Neste sistema 
de criptografia, a chave de encriptação é pública e é diferente da chave de decriptação 
que é secreta (privada). No RSA, esta assimetria é baseada na dificuldade prática da 
fatoração do produto de dois números primos grandes, o "problema de fatoração". O 
acrônimo RSA é composto das letras iniciais dos sobresnomes de Ron Rivest, Adi 
Shamir e Leonard Adleman, fundadores da atual empresa RSA Data Security, Inc., os 
quais foram os primeiros a descrever o algoritmo em 1978. Cliffor Cocks, um 
matemático Inglês que trabalhava para a agência de inteligência britânica Government 
Communications Headquarters (GCHQ), desenvolveu um sistema equivalente em 
1973, mas ele não foi revelado até 1997. 
A construção de chaves é feita através da multiplicação de dois números primos 
relativamente grandes que gera um número que será elevado a um expoente que é 
um número público, e após isso ele é novamente elevado a outro expoente que é um 
número privado. Assim teremos um número público e um número privado. O processo 
de descriptografia (em que os números primos são novamente gerados) será revertido 
através de fatoração, que é o inverso da multiplicação. 
O RSA foi construído sobre uma das áreas mais clássicas da matemática, a teoria dos 
números. Ele se baseia na dificuldade em fatorar um número em seus componentes 
primos (números divisíveis por 1 e por ele mesmo). Todo número inteiro positivo maior 
que 1 pode ser decomposto de forma única em um produto de números primos, por 
exemplo, 26 é um produto de 2 * 13,44 é um produto de 2 * 2 * 11. Apesar de parecer 
simples fatorar esses números pequenos, a situação fica bastante complexa e 
demorada quando temos que fatorar números grandes não podendo ser resolvidos 
em um tempo polinomial determinístico. No RSA a chave pública e a chave privada 
são geradas com base na multiplicação de dois números primos e o resultado desta 
multiplicação será público, mas se o número for grande o suficiente, fatorar este 
número para descobrir os primos que multiplicamos para formá-lo pode demorar anos. 
Por isso que o RSA é seguro, sendo impossível quebrar a sua criptografia. 
O método do RSA se dá primeiramente com a construção de uma tabela atribuindo a 
cada letra um número. Isto é necessário visto que o RSA codifica somente números. 
Após isso, escolhemos os números primos e quanto maior for esses números melhor. 
A RSA Data Security, que é responsável pela padronização do RSA, recomenda que 
se utilizem chaves de 2048 bits (o que resulta em um número com 617 dígitos) se 
quisermos garantir que a chave não seja quebrada até pelo menos o ano de 2030. 
Após a atribuição de números para as letras agora temos que calcular a função 
“totiente” que diz a quantidade de co-primos de um número que são menores que ele 
mesmo. Feito isso, o próximo passo é calcular a chave pública que é onde escolhe-
se um número "e" em que 1 < e < função totiente. Com a chave pública em mãos 
9 
 
podemos agora cifrar a mensagem aplicando, para cada letra, a fórmula “c = m ^ e 
mod n”, onde "e" é a chave pública e "m" é o valor numérico da letra. 
Para exemplificar o funcionamento do algoritmo vamos escolher inicialmente dois 
números primos quaisquer “P” e “Q”. Obviamente que vamos escolher dois números 
primos pequenos apenas por questão de exemplificação. Portanto, consideramos que 
“P = 17” e “Q = 11”. 
Após definirmos os valores dos números primos devemos calcular dois novos 
números N e Z de acordo com os números P e Q escolhidos, portanto temos que: 
𝑁 = 𝑃 × 𝑄 
𝑍 = (𝑃 − 1) × (𝑄 − 1) 
Assim, após substituir os valores teremos como resultado: 
𝑁 = 17 × 11 = 187 
𝑍 = 16 × 10 = 160 
O próximo passo é definir um número D que tenha a propriedade de ser primo em 
relação a Z. Podemos escolher qualquer número como, por exemplo, o número “7”. 
Agora podemos começar o processo de criação da chave pública e da chave privada. 
Devemos encontrar um número E que satisfaça a propriedade (𝐸 × 𝐷)𝑚𝑜𝑑 𝑍 = 1 . Se 
tomarmos o número “1” e substituindo os valores na fórmula teremos 
𝐸 = 1 ⇒ (1 × 7) 𝑚𝑜𝑑 160 = 7 que não satisfaz a condição, pois o resultado foi “7”. Se 
tomarmos os números “2”, “3” até o “22” nenhum satisfará a condição, mas o número 
“23” satisfará resultando em 𝐸 = 23 ⇒ (23 × 7) 𝑚𝑜𝑑 160 = 1. Outros números 
também satisfazem essa condição, como “183”, “343”, “503”, etc. 
Dessa forma, tomamos como referência 𝐸 = 23. Agora podemos definir as chaves de 
encriptação e desencriptação. Para criptografar utilizamos “E” e “N”, esse par de 
números é utilizado como chave pública. Para descriptografar utilizamos “D” e “N”, 
esse par de números é utilizado como chave privada. 
Assim, temos as equações definidas abaixo: 
𝑇𝑒𝑥𝑡𝑜 𝐶𝑟𝑖𝑝𝑡𝑜𝑔𝑟𝑎𝑓𝑎𝑑𝑜 = (𝑇𝑒𝑥𝑡𝑜 𝑃𝑢𝑟𝑜𝐸)𝑚𝑜𝑑(𝑁) 
𝑇𝑒𝑥𝑡𝑜 𝑃𝑢𝑟𝑜 = (𝑇𝑒𝑥𝑡𝑜 𝐶𝑟𝑖𝑝𝑡𝑜𝑔𝑟𝑎𝑓𝑎𝑑𝑜𝐷)𝑚𝑜𝑑(𝑁) 
Como um exemplo prático vamos imaginar uma mensagem bastante simples que tem 
o número “4” no seu corpo e será retornada ao destinatário. Para criptografar essa 
mensagem teríamos o texto original como sendo “4”, o texto criptografado seria 
423 𝑚𝑜𝑑(187) que é 70.368.744.177.664 mod(187) resultando em “64”. 
10 
 
Para descriptografar destinatário recebe o texto “64”. Recebido o texto criptografado 
e aplicando a fórmula temos que o texto original será 647 𝑚𝑜𝑑(187) ou 
398046511104 𝑚𝑜𝑑(187) que resulta em “4” que é o texto originalmente criado. Como 
o RSA trabalha com número devemos converter um alfabeto em número, assim a letra 
A seria 0, B seria 1, C seria 2, e assim por diante. 
Podemos notar que a escolha dos números primos envolvidos é fundamental para o 
algoritmo, por isso escolhe-se números primos gigantes para garantir que a chave 
seja inquebrável. 
 
 
11 
 
4 REFERÊNCIAS 
1. Myers, Lysa. Tudo sobre criptografia: O que é e quando devemos usar? 
welivesecurity. [Online] eset, 31 de Agosto de 2017. [Citado em: 22 de Novembro de 
2018.] https://www.welivesecurity.com/br/2017/08/31/tudo-sobre-criptografia-quando-
usar/. 
2. Nunes, Emily Canto. O que afinal de é criptografia e porque ela é importante? Intel 
IQ-BR. [Online] Intel, 18 de Outubro de 2016. [Citado em: 22 de Novembro de 2018.] 
https://iq.intel.com.br/o-que-afinal-e-criptografia-e-por-que-ela-e-importante/. 
3. Garrett, Filipe. O que é criptografia? techtudo. [Online] Globo Comunicação e 
Participações S.A, 30 de Setembro de 2016. [Citado em: 22 de Novembro de 2018.] 
https://www.techtudo.com.br/artigos/noticia/2012/06/o-que-e-criptografia.html. 
4. Romagnolo, Cesar Augusto. O que é criptografia? Oficina da Net. [Online] M3 
Mídia, 24 de Agosto de 2007. [Citado em: 22 de Novembro de 2018.] 
https://www.oficinadanet.com.br/artigo/443/o_que_e_criptografia. 
5. Santiago, Emerson. Criptografia. Info Escola. [Online] UOL Educação, 7 de Agosto 
de 2012. [Citado em: 22 de Novembro de 2018.] 
https://www.infoescola.com/informatica/criptografia/. 
6. Alecrim, Emerson. Criptografia. Infowester. [Online] Infowester, 12 de Agosto de 
2005. [Citado em: 22 de Novembro de 2018.] 
https://www.infowester.com/criptografia.php. 
7. Andrade, Eder. A História da Criptografia. PETNews. [Online] Grupo PET 
Computação UFCG, Abril de 2014. [Citado em: 22 de Novembro de 2018.] 
http://www.dsc.ufcg.edu.br/~pet/jornal/abril2014/materias/historia_da_computacao.ht
ml. 
8. Schuncke, Alex. Quais os tipos de criptografia? Oficina da Net. [Online] M3 Mídia, 
29 de Novembro de 2012. [Citado em: 22 de Novembro de 2018.] 
https://www.oficinadanet.com.br/post/9424-quais-os-principais-tipos-de-criptografia. 
9. González, Daniela. Conheça os tipos de criptografia digital mais utilizados. PC 
World. [Online] IT Mídia, 04 de Outubro de 2007. [Citado em: 22 de Novembro de 
2018.] https://pcworld.com.br/idgnoticia2007-10-040383475254/. 
10. Wikipedia. RSA (sistema criptográfico). Wikipedia. [Online] Wikipedia. [Citado em: 
22 de Novembro de 2018.] 
https://pt.wikipedia.org/wiki/RSA_(sistema_criptogr%C3%A1fico). 
11. Medeiros, Higor. Criptografia Assimétrica: Criptografando e Descriptografando 
Dados em Java. Devmedia. [Online] DevMedia, 2014. [Citado em: 22 de Novembro 
de 2018.] https://www.devmedia.com.br/criptografia-assimetrica-criptografando-e-
descriptografando-dados-em-java/31213.