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

Por: Elgio Schlemer em 03/08/2009 | Blog: https://profelgio.duckdns.org/~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

Estrutura do Iptables

Armazenamento de senhas no Linux

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

Mecanismo de firewall e seus conceitos

Parâmetros interessantes do scanf e do printf em C

Leitura recomendada

Snort em modo defensivo com Flex Response 2

Proxy reverso e balanceamento de carga utilizando o Pound

Segurança no Linux: Antivírus, Firewall, Wine - Mitos e Verdades

SELinux na prática

Quad9 - O que é e como usar

  
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