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.547 ]

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


Os "tolos" venceram



Um princípio matemático que respeitasse a característica três (comutatividade) é extremamente fácil e não era mistério. Soma ou multiplicação são exemplos bem simples disto.

Como o real princípio matemático (que irei descrever e demonstrar) é um tanto complexo, vou antes explicar a ideia do algoritmo usando o princípio da multiplicação, apenas para finalidades didáticas:
Linux: Fundamentos da criptografia assimétrica
Da forma como ilustrado, nenhuma das informações que está em vermelho (1357, 35, 89) foi transmitida, no entanto o Receptor foi capaz de recuperar com sucesso a informação correta.

Considerando que um atacante, observando o tráfego, tenha cópias de todas as mensagens, ele tem os valores da mensagem a (47.495), da mensagem b (4.227.055) e da mensagem c (120.773), mas não tem a chave.

O que torna a multiplicação inviável é justamente porque o atacante tem como descobrir estes valores apenas com as mensagens que obteve. Se o atacante dividir b por a, terá o cadeado do receptor (4227055/47495=89). Óbvio! Se ele dividir b por c terá o cadeado do Emissor. Pronto. Não serve. Era necessário não apenas um princípio matemático que tivesse as propriedades citadas, mas que também fosse irreversível. Multiplicação não serve, pois a divisão o reverte.

Finalmente Diffie e Hellman descobriram isto na operação de módulo. Qual é a expressão matemática que desfaz uma operação de módulo?

Módulo, lembra? O resto de uma divisão. Se eu pergunto quanto é 135 MOD 12, facilmente alguém calcula 3 (qual o resto da divisão de 135 por 12?).

Mas e se eu disser que 1239 MOD X = 21, como vocês fariam para descobrir o valor de X? Qual o número (X) que quando se divide 1239 por ele resulta em resto 21? Vocês provavelmente irão fazer por tentativa e erro, ou seja, ir tentando valores de X até achar um que dê 21. Ao tentar o 29, verão que 1239 MOD 29 resulta em 21.

Mas apenas a operação de módulo em si ainda não serve, pois existem vários candidatos a X (29, 42, 58, 87, 174, 203, 406, 609, 1218, ...) e ao menos um deles pode ser facilmente calculado. E ainda tem sim uma forma matemática para reverter esta expressão (deixo como desafio).

Mas que tal esta expressão então:

23X mod 1311 = 1127

Qual é o valor de x?

Agora sim, você terá mesmo que ir testando valores de x na expressão até encontrar um que resulte em 1127. Ao tentar o valor 7 você terá sucesso. Não existe uma fórmula matemática que calcule o x de forma direta.

Finalmente os tolos descobriram o Santo Graal!

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

Introdução a criptografia

Criptografia chave simétrica de bloco e de fluxo

255.255.255.0: A matemática das máscaras de rede

Sinais em Linux

Leitura recomendada

Usando e instalando o Nessus no Linux

Desafio: Análise Forense Computacional - Forense em Tráfego de Rede [Resolvido]

Segurança com Iptables

Segurança da Informação: Necessidades e mudanças de paradigma com o avanço da civilização

Nmap - Escaneando sua Rede e Mantendo-a Segura

  
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