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: 149.500 ]

Por: Elgio Schlemer em 03/08/2009 | Blog: https://profelgio.duckdns.org/~elgio


Conclusão



Com esta descoberta se abriram as portas para uma nova era de algoritmos de criptografia. De Diffie-Hellman para um algoritmo assimétrico de verdade é apenas um pequeno passo.

O algoritmo por si só é vulnerável ao ataque do homem do meio, ataque este que também derruba o forte protocolo SSL. Justamente por causa dele é que torna-se necessário as certificadoras digitais.

Antigamente, no SSL, o cliente ficava responsável por escolher uma chave de sessão completamente aleatória. Clientes mal implementados o faziam com displicência, escolhendo chaves previsíveis, como o caso de uma das versões do Netscape. Usando o Diffie-Hellman, a chave de sessão não é escolhida, mas sim calculada por valores aleatórios que ambas as partes escolheram. Mesmo que um cliente seja irresponsável, escolhendo um X previsível, o protocolo está salvo se o servidor escolher o seu X de uma forma mais decente.

Deve-se mencionar também que todo o esforço de Diffie em ser o primeiro a chegar em uma algoritmo desta natureza foi em vão. Cientistas ligados a governos haviam achado um algoritmo semelhante anos anteriores, mas esta notícia só se tornou pública muitos anos depois. Coisas da criptografia.

Se hoje acredita-se em alguns princípios matemáticos cruciais para a criptografia, como a fatoração de números primos ou a não reversão da operação de módulo, esta crença se dá unicamente ao fato de que ninguém ainda descobriu como vencê-los. Ou, se descobriu, não nos pode contar por força de seus cargos. Daqui a dezenas de anos talvez nos surpreendamos com o fato de que o RSA de 1024 bits já é, hoje, café da manhã na mesa dos cientistas da NSA.

Por fim, quando comecei a escrever este artigo o mesmo era para entrar no conceito dos algoritmos assimétricos, estudando o RSA e finalizando com seu emprego no protocolo SSL e em assinaturas digitais. Quanto vi que esta ideia viraria um "livro", decidi fragmentar a informação. Portanto, fico-vos devendo para um futuro próximo outros artigos para completar a série.

Página anterior    

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

Estrutura do Iptables

Cuidado com números em Ponto Flutuante

Programação com números inteiros gigantes

Guerra Infinita, uma análise da Ciência da Computação

Estrutura do IPTables 2: a tabela nat

Leitura recomendada

TinyOS

ACCT - O contabilizador de processos do Linux

ARP Poisoning: compreenda os princípios e defenda-se

AUDIT: Auditoria de arquivos no Linux para conhecer quem fez alterações em arquivos

IDS com Snort + Guardian + Debian Lenny

  
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

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts