A História da Criptografia.
A criptografia, não é um recurso que passou a ser usado recentemente, mas, de acordo
com a história, vem sendo aprimorada desde épocas antigas ,como no uso de
hieróglifos, onde era necessário uma interpretação para entender a mensagem, até os
dias de hoje.
A criptografia é a arte de cifrar/codificar uma mensagem como mecanismo de
segurança. A história da criptografia começa há milhares de anos, com os Hebreus a 600
a.C.,( podemos ver a história dos Hebreus na Bíblia) 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.
Na primeira guerra mundial houve uma pequena menção sobre cliptografia mas
foi durante a segunda guerra mundial, que 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, no decorrer da Segunda Guerra, eles
modificaram para o one-time pad.
Durante "Guerra Fria", entre Estados Unidos 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.
Aqui temos um exemplo de como seria associando letras e números:
Mensagem original: PET
Função: f(x)=2x+1
Mensagem Associada: 16 5 20
Mensagem Cifrada: 33 11 41
O interessante da criptografia é perceber que alguns dos números cifrados não
existem na tabela e, se alguém interceptar a tabela, não conseguirá decifrar a mensagem,
pois precisará da função, a mensagem traduzida ficaria:
?K?
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 criptografica
não se baseia em funções, mas nas leis da física.
Em cliptografia, temos o sistema El gamal , que possui esse nome por causa do
estudioso da criptografia egípcio chamado de Taher Elgamal , onde o mesmo
desenvolveu esse sistema em 1985. Sua segurança se baseia na dificuldade de solução
que o problema do logaritmo discreto pode apresentar. O ElGamal é uma cifra híbrida e
nele podemos combinar os pontos fortes da criptografia simétrica com os pontos fortes
da criptografia assimétrica (de chave pública). Na verdade, a cifra é simétrica, mas usa
um mecanismo público de acordo de chaves.
Podemos definir e calcular logaritmos discretos , utilizando conhecimentos da
aritméticas dos restos , congluências e teorema chinês dos restos.
Veja um exemplo:
Se Mariana quer enviar uma mensagem de forma segura para Barbara , em que somente
ela ( Barbara) possa decifrar, ela deve encriptar a mensagem utilizando a chave pública
dela. Somente Barbara tem acesso à sua chave privada, logo, ela será a única capaz de
decriptar a mensagem de volta para sua forma original, mesmo que outra pessoa tenha
acesso a mensagem criptografada, a mesma vai permanecer confidencial, ja que
nenhuma outra pessoa , a não ser barbara pode decifrar a mensagem. Vamos ver como
seria:
Gerando Chave:
Passos a seguir na criação do sistema de cliptografia
• Escolher um primo grande p;
• Escolher uma raiz primitiva r deste primo;
• Escolher um n´umero natural 2 < x ≤ p − 2 aleatoriamente;
• Calcular r x ≡ a (mod p);
• Divulgar sua chave pública (p, r, a);
• Manter sua chave privada x em segredo.
Por exemplo, digamos que Mariana e Barbara queiram se comunicar de forma segura.
Então Mariana utiliza p = 1009, r = 11 e x = 13. Ele calcula 1113 ≡ 752 (mod 1009) e
divulga a chave pública (1009, 11, 752), mantendo x em segredo.
ENCLIPTAÇÃO
• Obter a chave pública (p, r, a) do receptor; • Escolher um número natural 2 < y ≤ p −
2 aleatoriamente; • Calcular r y ≡ b (mod p); • Calcular C ≡ M.a y (mod p); • Enviar o
ciframento c = (b, C).
Suponhamos que Mariana deseja enviar mensagem K = 281813 a Barbara. Ela primeiro
vai dividir a mensagem nos blocos 281 e 813. Para encriptar o primeiro bloco M = 281,
ela escolhe y = 69, e calcula b ≡ 11 69 ≡ 899 (mod 1009) e C ≡ 281.752 69 ≡ 281.371 ≡
324 (mod 1009). Mariana então envia a mensagem cifrada c = (899, 324), e repete o
processo para o segundo bloco 813.
DESCRIPTAÇÃO
Para decifrar a mensagem c = (b, C) recebida, o receptor deverá: • Utilizar a chave
privada para calcular P ≡ [Link]-1-x (mod p) • Temos que C ≡ M.a y (mod p) e que b ≡ ry
(mod p), ent˜ao: P ≡ (M.a y )(ry )p-1-x ≡ M(r x ) y (ry(p-1)-xy ) ≡ M(rp-1 )y ≡ M (mod p). Ao
receber a mensagem cifrada c = (899, 324), Barbara ira calcular P ≡ 324.8991009-1-13 ≡
324.359 ≡ 281 (mod 1009), recuperando assim a mensagem original 281 = M.
Teorema de Euler.
Leonhard Euler nasceu na Basiléia, Suíça, em 1707, e morreu aos 74 anos. Foi, sem
dúvida, um dos grandes matemáticos do século XVIII. As obras completas de Euler
ocupam 75 volumes. Foi estimado que, só para copiar à mão as obras do matemático,
uma pessoa levaria 50 anos, trabalhando oito horas por dia. Euler ficou completamente
cego durante os últimos 17 anos de sua vida. Sua produção matemática neste período,
no entanto, aumentou graças à sua incrível memória e capacidade de realizar cálculos
complexos, sem auxílio de lápis e papel. Cerca de metade de sua produção matemática
foi feita neste período.
Em relação com a criptografia RSA, podemos verificar que é fácil calcular ø(n) , caso
conheçamos a fatoração de n . Porém o que acontece quando não conhecemos essa
fatoração? Se n for muito grande, pode ser computacionalmente impraticável checar
diretamente quais inteiros entre 1 e n-1 são coprimos com n . De forma geral, a maneira
mais rápida de calcular ø(n) será fatorando n . Se não for possível fatorar n , não há
como calcular ø(n) . Este simples fato está na base da segurança do RSA. Veremos que
a chave pública do RSA é um par ( n,e ) , em que n é um produto de dois primos
distintos n=p⋅q e o inteiro e tem inversa módulo ø(n) . A chave privada é o par (n ,d ) ,
em que d é a inversa de e módulo ø(n) . Quem conhece ø(n) pode facilmente calcular a
inversa de e módulo ø(n) , usando o algoritmo de Euclides estendido.
CRIVO DE ARISTOTELES ( Peneira de Aristoteles)
O Crivo de Eratóstenes, também conhecida como a peneira de Eratóstenes, é um dos
algoritmos mais antigos e eficazes para encontrar números primos em um intervalo
específico. Este método foi desenvolvido pelo matemático grego Eratóstenes de Cirene
por volta de 240 a.C. e continua sendo uma ferramenta fundamental na teoria dos
números e na matemática computacional até hoje.
A busca por números primos é uma das questões mais antigas e fundamentais da
matemática. Os números primos são aqueles que só têm dois divisores: 1 e eles
mesmos. Eles desempenham um papel crucial em várias aplicações, como criptografia,
fatoração de números e teoria dos números.
A Peneira de Eratóstenes funciona de maneira sistemática, eliminando os múltiplos de
cada número primo à medida que avança. Aqui está uma descrição detalhada de como
esse processo ocorre:
1. Criação de uma lista de números: Primeiro, você cria uma lista de números inteiros a
partir do intervalo desejado, normalmente começando pelo número 2 (o menor número
primo).
2. Seleção do menor número primo na lista: Começando com o número 2, o qual é o
menor número primo, marque-o como um número primo e risque todos os seus
múltiplos da lista. Os múltiplos de um número são todos os números que podem ser
obtidos multiplicando-se esse número por um inteiro positivo.
Exemplo: Se começarmos com 2, marcaremos 2 como primo e riscaremos todos os seus
múltiplos na lista (4, 6, 8, 10, etc.).
3. Seleção do próximo número não marcado: Em seguida, escolha o próximo número não
marcado na lista. Este será o próximo número primo.
4. Riscando múltiplos: Marque esse número como primo e risque todos os seus múltiplos
na lista.
5. Repetição do processo: Continue selecionando o próximo número não marcado e
riscando seus múltiplos até que tenha marcado todos os números primos no intervalo
desejado.
6. Conclusão: Quando o processo terminar, todos os números não riscados na lista
são números primos.
Na criptografia, a geração de chaves públicas e privadas muitas vezes envolve a seleção
de números primos. A Peneira de Aritóstenes pode ser usada para encontrar números
primos adequados para criptografia, garantindo que os números escolhidos sejam
realmente primos e difíceis de fatorar.
Pequeno teorema de Fermat na criptografia.
O Pequeno Teorema de Fermat é um dos resultados fundamentais na teoria dos números
e tem inúmeras aplicações na criptografia e na aritmética modular. Essa propriedade é
extremamente útil para simplificar cálculos em aritmética modular, especialmente em
casos onde os expoentes são grandes. Também serve como base para métodos de
criptografia, como o RSA, onde a segurança das comunicações depende de propriedades
dos números primos.
A Matemática não está restrita somente aos livros, mas é uma ciência viva, que é
utilizada em larga escala por outras áreas do conhecimento e não como um fim em si
mesma, ela contribuiu para uma considerável evolução da criptografia quando essa
assimilou os conceitos da matemática e tornou-se uma disciplina científica estudada por
matemáticos, especialistas em estatística e cientistas ligados ao campo da informática
entre outros.