Fundamentos da criptografia assimétrica

Algorítimos assimétricos, mais conhecidos como de "chave pública e privada", são baseados em alguns princípios matemáticos considerados inexistentes, até que o "tolo" Whitfield Diffie conseguiu o que todos julgavam impossível, inaugurando uma nova era de cifras. Este artigo descreve esta história e como "Deus recompensa os tolos!".

[ Hits: 143.964 ]

Por: Elgio Schlemer em 03/08/2009 | Blog: http://gravatai.ulbra.tche.br/~elgio


Introdução



Usar técnicas matemáticas para esconder o significado de uma informação não é um artifício de uso recente, pois muito se usou em guerras ou mesmo incidentes governamentais. Histórias incríveis podem ser obtidas, por exemplo, no fantástico livro de Simon Singh, "O Livro dos Códigos".

Basicamente um algoritmo de criptografia pode ser dividido em simétrico ou assimétrico. Os algoritmos simétricos são aqueles que simplesmente possuem uma chave e esta precisa ser compartilhada entre as partes envolvidas na comunicação secreta (Introdução a criptografia, uma leitura desejável antes de prosseguir a leitura deste).

Os simétricos ainda podem dividir-se em dois tipos, os chamados cifras de bloco e os de fluxo (veja Criptografia chave simétrica de bloco e de fluxo).

A ciência da criptografia pode ser descrita como a eterna e incansável guerra entre os criptógrafos, que querem esconder informações, e os criptoanalistas, que querem torná-las legíveis.

Durante a segunda guerra mundial, por exemplo, os alemães usaram a famosa máquina Enigma para cifrar suas mensagens. Aliados tentavam achar fraquezas neste equipamento a fim de quebrá-lo mas tinham certas dificuldades, seja pela falta de informações ou pela força do algoritmo em si. O desafio era ainda maior pois a chave usada pelos alemães trocava diariamente, sendo que cada mensagem ainda tinha três letras aleatórias em uma espécie de chave de sessão. Descobrir, com algum esforço, a chave do dia era uma vitória, pois todas as mensagens seriam decifradas, mas os aliados voltariam a estaca zero a meia noite, quando a chave usada pelos alemães seria substituída.

Contudo, se o uso da enigma desta forma era um desafio para os aliados, também o era para os alemães. Com navios, submarinos e exércitos espalhados em vários pontos e com uma chave descartável, usada somente durante um único dia, como dar a conhecer aos operadores de rádio a chave do próximo dia? Não se pode simplesmente transmití-la, mesmo que de forma cifrada. Não é nada seguro transmitir a chave da terça-feira para todos, cifrando-a com a chave da segunda, pois se os aliados conseguiram quebrar a chave da segunda podem simplesmente ler a nova chave sem esforço algum.

Os alemães resolveram isto com a publicação de livros de códigos. Cada livro tinha chaves para vários dias e era entregue em mãos ao operador de comunicações. Este tinha fortes recomendações para destruir o livro e o equipamento imediatamente quando estiver prestes e ser capturado. Jamais deveria o livro e tampouco a máquina, cair em mãos inimigas.

A primeira maneira que os aliados encontraram para quebrar a enigma foi subornar um oficial alemão descontente que lhes entregava uma cópia do livro. Hans-Thilo Schmidt sentia-se rejeitado pelo exército e tinha ciúmes do sucesso de seu irmão mais velho, do alto escalão alemão. Devido a influência deste seu irmão, acabou em um cargo burocrático e logo passou a vender informações para um agende secreto francês. E eis que um forte esquema de cifras, com chaves de uso diário, é posto por terra por causa de uma fraqueza humana e o compartilhamento de chaves.

A máquina enigma acabou sendo quebrada de forma definitiva por Alan Turing e suas "bombas" (a história de Turing é muito triste. Sem jamais receber reconhecimento em vida, um dos maiores gênios da criptoanálise acabou cometendo suicídio em 7 de Junho de 1954).

O mais interessante neste assunto de criptografia é todo o sigilo existente em torno dele. O mundo só tomou conhecimento de todos estes detalhes muitos anos depois, permanecendo um completo segredo até então e, talvez, com os alemães ainda achando que sua Enigma fora inquebrável.

Nos dias de hoje não é diferente. Já que não é possível confiar nos meios de comunicação, não se pode usá-lo para transmitir uma chave que será futuramente usada em uma conversa cifrada. A princípio a única maneira realmente segura de troca de um segredo é presencialmente, ou seja, as partes realizando um encontro pessoal e físico.

Mas existiria alguma forma realmente segura e confiável de realizar uma troca de chaves de forma sigilosa sem que um encontro físico ocorresse? Todos haviam desistido desta busca.

    Próxima página

Páginas do artigo
   1. Introdução
   2. A utopia da troca de chaves de forma segura
   3. Os "tolos" venceram
   4. Algoritmo Diffie-Hellman
   5. Conclusão
Outros artigos deste autor

Mecanismo de firewall e seus conceitos

Criptografia assimétrica com o RSA

Programação com números inteiros gigantes

Criptografia chave simétrica de bloco e de fluxo

Autenticação por desafio e resposta no SSH

Leitura recomendada

Segurança em redes wireless

Segurança com Iptables

Segurança na Internet

Quebrando chave WEP (Wired Equivalent Privacy) - parte 1

Nmap do início ao fim (parte 1)

  
Comentários
[1] Comentário enviado por rodrigozanuzzo em 03/08/2009 - 17:03h

Muito bom seu artigo
principalmente para esclarecer algumas duvidas
de iniciantes como eu
Abraço...

[2] Comentário enviado por foguinho.peruca em 04/08/2009 - 11:39h

Elgio,

Parabéns pelo artigo. Muito simples e direto, como uma boa aul deveria ser.... Estou estudando para prestar a poscomp e esse artigo veio bem a calhar...

Jeff

[3] Comentário enviado por acollucci em 23/08/2009 - 14:14h

Cara

Artigo nota 10!!!

nunca vi um artigo sobre criptografia mais claro que esse.

Att,
Anthony Collucci

[4] Comentário enviado por alanbatista em 27/08/2009 - 08:13h

Estudei criptografia assimétrica quase fiquei louco, tem algorítimo muito complexo.

[5] Comentário enviado por luizvieira em 01/09/2009 - 08:35h

Ótimo artigo, Elgio. Passei a interessar-me mais pela criptografia, tanto que já estou pra ler o livro Cryptonomicon :-)
[ ]'s

[6] Comentário enviado por removido em 23/09/2009 - 12:07h

Eu tentei aplicar esse algoritmo em PHP mas ele retorna incrivelmente -1

p=131 e=5 xf=31
pow(5,31)=4.65661287308E+21 % 131 = -1


<?php

$p=131;
$e=5;
$xf=31;

echo "p=".$p." --- e=".$e." --- xf=".$xf."<br>";

$yf = ( pow($e,$xf) % $p );

echo "pow($e,$xf)=".pow($e,$xf)." % ".$p." = ".$yf;

?>

[7] Comentário enviado por removido em 23/09/2009 - 13:19h

Analisando mais profundamente o que acontece:

Considerando P=131 E=5 Xf=31 temos segundo o exemplo:

Yf = 5^31 mod 131 portanto temos:

5^31 = 4,656612873077392e+21

considerando Z = (5^13) / 131 temos Z = 3,554666315326253e+19

agora para pegar o resto temos que multiplicar assim Z*131 que dá 4,656612873077391e+21 e esse valor deve ser subtraído do 5^31, logo:

(5^31) - (Z*131) = ( 4,656612873077392e+21 - 4,656612873077391e+21 ) = 0

Pronto agora todos devem entender o quanto eu sou péssimo em matemática kkkkk no php dá -1, fazendo na mão, o resultado é zero.

Qual a mágica de obter Yf=41 ????

[8] Comentário enviado por elgio em 23/09/2009 - 13:24h

O php não é uma boa linguagem para estes cálculos.

Primeiro porque não é capaz de lidar, naturalmente, com números grandes http://www.vivaolinux.com.br/artigo/Programacao-com-numeros-inteiros-gigantes Então pode ter ocorrido um overflow na operação e tudo já dançou.

Segundo porque o operador de módulo do PHP não é realmente operador de módulo. É o operador de RESTO, que mesmo considerado como sinônimos eles NÃO SÃO!

-4 mod 10 deve dar 6 (-4 está a 4 posições antes do 10)
Mas no PHP, assim como no C, -4 mod 10 = -4

Teoria e detalhes em http://www.vivaolinux.com.br/script/Algoritmo-de-euclides-estendido-(calcula-o-D-RSA)

[]'s

[9] Comentário enviado por removido em 23/09/2009 - 15:47h

Não de forma alguma, passei um tempinho estudando como fazer estes cálculos no PHP e ele possui uma biblioteca matemática para essas operações mais complexas, procurem na área de scripts do VOL por PHP > Segurança > diffiehellman vou postar lá:

p=131 e=5 xf=31 xc=17

e^xf => 5 ^ 31 = 2147483647 mod 131 = 41

e^xc => 5 ^ 17 = 2147483647 mod 131 = 4

kf = 49 kc = 49


agora só falta desenvolver o gerador de números primos.

[10] Comentário enviado por gustavo luis em 08/10/2009 - 13:08h

otimo artigo com bastante fatos historicos mais nao acho q o tema foi adequado para o artigo.
parabens pelas informacoes colhidas

[11] Comentário enviado por claytonnog em 19/11/2009 - 10:47h

Muito bom o artigo!
Me tirou muitas dúvidas.
Obrigado.

[12] Comentário enviado por Win7User em 11/12/2009 - 20:01h

Exelente artigo como todos que tenho lido aqui postados pelo Elgio,muito bacana um pessoa compartilhar de seus conhecimentos para que outros venham a aprender e conhecer melhor alguns conceitos de programação e etc...
"Deus recompensa os tolos!".-tvz como frase de efeito está OK,mas a tradução correta seria : Deus recompensa os sabios!!! que sao julgados tolos ^^
abraços brother

[13] Comentário enviado por removido em 12/02/2010 - 17:54h

GOSTEI MUITO, MAS GOSTARIA DE EXPLICAÇÃO SOBRE A CRIPTOGRAFIA SKIPJACK.. FICARIA BEM GRATO...

LUZ PAZ E AMOR

[14] Comentário enviado por sukelly em 06/08/2010 - 16:38h

Excelente artigo. Queria que você passe uma informação,
Esse algoritmo pode aplicado em java?

[15] Comentário enviado por felipemartinsss em 22/09/2010 - 13:30h

Já havia lido sobre o método de Rabin e o RSA. O algoritmo de Diffie-Hellman ainda não conhecia.
Parabéns pelos artigos.

[16] Comentário enviado por Brown. em 29/10/2010 - 15:45h

Criptografia Assimetrica é segura sim

[17] Comentário enviado por elgio em 29/10/2010 - 16:04h

Desculpe "Brown", mas...

Quem aqui disse que não era?

[18] Comentário enviado por removido em 08/11/2010 - 18:17h

Existe um erro nisto tudo, a matemática é perfeita, ou seja existe sim uma forma de resolver esse algorítimo. Mas eu acho que a graça da criptografia é esta. AHahhAHAhaHahhaHahaha

A propósito na imagem está escrito manidos ao invés de mantidos.

[19] Comentário enviado por Rafaelmspc em 16/11/2010 - 15:39h

Excelente artigo, parabéns e obrigado.

[20] Comentário enviado por gedielp em 27/04/2011 - 19:14h

parabens muito bom

[21] Comentário enviado por enricolo4 em 10/06/2011 - 23:37h

Muito bom seu artigo, gostei muito.

entao pode ser usando um tipo de divisão de polinômios no caso f(x)= Q(x)(x-a) + R(x), sendo (x-a) é a raíz no caso o divisor, f(x) a função o dividendo Q(x) o quociente e o R(x) o resto, no segundo caso também pode ser usado dessa maneira mas usando logaritmo no caso (xln(23)-ln(1311) = ln(1227) sei lah acho q isso ajudaria muito a utilizar um para decifrar certos, ou é somente matemática básica mesmo hehe

[22] Comentário enviado por xiloba em 11/06/2011 - 21:28h

Não vi até hoje nenhuma explicação tão profunda e, ao mesmo tempo, tão cristalina, que me fizesse entender o princípio e os desdobramentos do mecanismo da criptografia.
Parabéns. Aliás, parabéns sempre!
Todos os artigos que você produz são muito bem escritos e elucidativos, obrigado por compartilhar conosco o seu vasto conhecimento.

[23] Comentário enviado por dstter em 14/07/2011 - 23:20h

Muito bacana o artigo. Sua didatica é excelente. Professores assim que o mundo precisa ^^

Achei super maneiro aquela ideia dos cadeados.

Mas eu queria fazer uma pergunta (me ocorreu exatamente agora)

na matemática (que é uma ciência exata) não deve existir (ou já existe) uma forma de desfazer esse modelo usado? Assim como a divisão anula a multiplicação, não teria um calculo pra anular os que foram realizados exemplos e descobrir os números em vermelho? (sem ser por tentativa e erro ou mesmo sendo, mas deixando pistas sobre os mais provaveis, dando pra reduzir uma lista de infinitas para algo mais possível)?

[24] Comentário enviado por Pauliano em 17/07/2011 - 16:45h

Fiquei com vontade de estudar criptografia só de ler este artigo.

Já tinha lido alguma coisa em outros lugares, mas o seu artigo ajudou a esclarecer mais esse assunto.

Muito bom.

[25] Comentário enviado por mrogerio em 05/08/2011 - 17:14h

Muito obrigado por este artigo!

[26] Comentário enviado por davimendes em 16/09/2011 - 09:06h

Parabéns pelo artigo. Realmente interessante e muito bem feito. Claro e sucinto

[27] Comentário enviado por pinkfloyd em 29/09/2011 - 15:39h

muito bom! nas férias vou dar uma bela estudada em criptografia

[28] Comentário enviado por rodrigo.a.sc em 15/11/2011 - 10:43h

??...??

Srs. PAra mim a criptografia ainda é um misterio.
Contudo este artigo me fez ter uma ideia, ainda não pragmatica do sistema.

Sou um analista em fase embrionaria...rsrs, contudo Gostei do assunto da criptografia!

[29] Comentário enviado por nicolas.cb em 02/12/2011 - 20:35h

Muito bom!

[30] Comentário enviado por hugoleal85 em 14/02/2012 - 20:35h

Grande artigo. Passou a mensagem de forma clara, simples e direta. Parabéns.

[31] Comentário enviado por removido em 28/04/2012 - 02:48h

O código que postaram lá em cima:

<?php

$p=131;
$e=5;
$xf=31;

echo "p=".$p." --- e=".$e." --- xf=".$xf."<br>";

$yf = ( pow($e,$xf) % $p );

echo "pow($e,$xf)=".pow($e,$xf)." % ".$p." = ".$yf;

?>

Isso deve ser enxuto, calculando multiplicação por partes e pegando o resto da divisão em cada etapa.

Assim os valores não chegarão a absurdos por causa de estouros dos valores.

[32] Comentário enviado por desouza_flavio em 14/05/2012 - 11:18h

Ótimo artigo, é muito bom sabe mais sobre a história e a criptografia na prática, além de ser uma assunto muito interresante.

Parabéns!

[33] Comentário enviado por wleite em 13/10/2016 - 22:25h

Elgio, parabéns pelo artigo!!!
O conteúdo é muito bom, claro e objetivo. Estou adorando ler todos os seus artigos que falam sobre a criptografia.

E obrigado por compartilhar um pouco do seu conhecimento!!!!


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts