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

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


Algoritmo Diffie-Hellman



Com a descoberta do princípio matemático, todas as propriedades foram satisfeitas. A força, evidentemente, deve ser obtida através da escolha de números realmente muito grandes, que inviabilize o esforço da tentativa e erro.

Porém, como números grandes demandam operações aritméticas gigantescas, irei demonstrar o funcionamento do algoritmo usando números pequenos, para que todos possam reproduzir em suas calculadoras de linha de comando bc!

O algoritmo de troca de chaves Diffie-Hellman constitui em uma série de operações matemáticas feitas por ambas as partes, sendo que ambos chegarão a um mesmo valor, a um mesmo número. Este número pode ser usado, então, como chave para algum algoritmo simétrico. Ele permite compartilhar uma única chave entre duas partes mas sem jamais enviá-la pela rede e sem possibilidade de alguém a descobrir.

Consiste nas seguintes etapas, feitas por ambas as partes:
  1. Ambos, em conjunto, escolhem dois números que não serão segredos, o número P e E. P deve ser um número primo e E deve ser menor que o P.
  2. Cada um escolhe para si um número X, mantendo-o em segredo
  3. Cada um usa o seu valor de X na operação modular, envolvendo P e E. Obtém com isto um número que chamaremos de Y
  4. Cada um envia para o outro o seu valor de Y
  5. Cada um realiza novamente a operação de módulo, porém usando o Y que recebeu do outro. Magicamente ambos obterão o mesmo resultado.

Confuso? Acredito que um exemplo completo, com operações e valores reais ajude na compreensão.
Linux: Fundamentos da criptografia assimétrica
Com números pequenos ainda se é vulnerável ao ataque por força bruta, pois o atacante, não tendo nenhum dos valores de X, poderá tentar usar alguns possíveis valores até acertar. Porém se usar números realmente grandes, da ordem de 512 bits, o número de tentativas torna inviável este ataque.

Página anterior     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

Túneis cifrados com SSH

Programação com números inteiros gigantes

Cuidado com números em Ponto Flutuante

Sinais em Linux

Armazenamento de senhas no Linux

Leitura recomendada

Resumo da Norma ISO/IEC 13335-3

Prevenção e rastreamento de um ataque

Hidden Service - Disponibilizando seu site na Deep Web através do Tor

Segurança na Internet

Tratamento de dados fornecidos pelo usuário: projetando sistemas com mais segurança

  
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

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts