Criptografia assimétrica com o RSA
Devido a dificuldade de troca de chaves, os algoritmos assimétricos são o principal motor de comunicações cifradas sobre SSL, como o HTTPS. De fácil compreensão, o RSA é um interessante método matemático que permite a cifra assimétrica baseado em números primos. E você pode brincar de RSA com a sua calculadora bc de linha de comando.
[ Hits: 185.697 ]
Por: Elgio Schlemer em 05/08/2009 | Blog: http://profelgio.duckdns.org:8080/~elgio
Quebrando o RSA: um desafio para você valendo um livro
A quebra do algoritmo RSA consiste simplesmente em se descobrir o valor de d da chave privada Kd. O d pode ser calculado pelo teorema de euclides, desde que se conheçam os valores do e e de qq (quociente de euclides).
Ora, o valor de e é publicamente conhecido, pois está exposto na chave pública Ke. Logo, quebrar o algoritmo RSA consiste em se descobrir o valor de qq, o quociente de euclides.
Como qq é calculado? Pela multiplicação de (P-1) por (Q -1), então, quebrar o RSA consiste simplesmente em encontrar os valores de P e Q.
Pensar em uma forma de encontrar os valores de P e Q é muito fácil, afinal sabe-se que o valor de N resultou da multiplicação destes dois números. Como o valor de N também é conhecido, pois está exposto na chave pública, quebrar o RSA é simplesmente respondera a pergunta
Quais os dois números que multiplicados um pelo outro resulta em N?
Se lhe é dito que o N é 299, a busca pelo P e pelo Q teria sucesso ao se achar P=13 e Q=23. Pronto. Fácil fácil. Um simples laço em qualquer linguagem de programação resolve isto rapidamente. Que tal uma versão do laço em bash:
Programadores em C, Java, PHP, Perl e até Basic não terão dificuldades em construir seus códigos para quebrar o RSA.
Se considerou isto uma tarefa fácil, topas um desafio?
Desafio 1 (VENCIDO)
Como incentivo será dado 500 pontos no Viva o Linux para o primeiro que responder corretamente os valores de P e de Q para os N propostos. Junto com a simples resposta deve vir um relato sobre o programa ou técnica usada e o tempo de processamento. Alunos e ex-alunos meus não podem participar, pois estudaram em sala de aula técnicas que os colocariam em vantagem em relação aos demais. Vamos lá, tente, já que não estou realmente enviando valores impossíveis.
Para o gerenciamento deste desafio foi criado o tópico Desafio RSA número 1 . Lá estarão todas as regras do desafio e os valores a serem quebrados. Todos estes detalhes serão colocados dois dias após a publicação deste artigo. Assim, caso o desafio ainda não tenha sido publicado, você tem um tempinho para ajustar sua ferramenta.
Desafio 2 (VALE LIVRO)
Após o desafio 1 ter sido vencido, criei outro valendo um livro. A definição e os resultados podem ser vistos em Ganhe um LIVRO aqui no Vol (Desafio 2 RSA)
Devo deixar claro que só serão aceitas respostas se você mesmo implementou sua própria ferramenta e disponibilizou o código fonte, conforme instruções do fórum. Outro aviso de extrema importância é que este desafio será realizado com a concordância do administrador do Viva o Linux, já que envolvem pontos.
Ora, o valor de e é publicamente conhecido, pois está exposto na chave pública Ke. Logo, quebrar o algoritmo RSA consiste em se descobrir o valor de qq, o quociente de euclides.
Como qq é calculado? Pela multiplicação de (P-1) por (Q -1), então, quebrar o RSA consiste simplesmente em encontrar os valores de P e Q.
Pensar em uma forma de encontrar os valores de P e Q é muito fácil, afinal sabe-se que o valor de N resultou da multiplicação destes dois números. Como o valor de N também é conhecido, pois está exposto na chave pública, quebrar o RSA é simplesmente respondera a pergunta
Quais os dois números que multiplicados um pelo outro resulta em N?
Se lhe é dito que o N é 299, a busca pelo P e pelo Q teria sucesso ao se achar P=13 e Q=23. Pronto. Fácil fácil. Um simples laço em qualquer linguagem de programação resolve isto rapidamente. Que tal uma versão do laço em bash:
N=299
for P in `seq 2 $N`
do
[ "`echo "$N % $P"|bc`" == "0" ] || continue
Q="`echo $N / $P|bc`"
echo P=$P Q=$Q
break
done
for P in `seq 2 $N`
do
[ "`echo "$N % $P"|bc`" == "0" ] || continue
Q="`echo $N / $P|bc`"
echo P=$P Q=$Q
break
done
Programadores em C, Java, PHP, Perl e até Basic não terão dificuldades em construir seus códigos para quebrar o RSA.
Se considerou isto uma tarefa fácil, topas um desafio?
Desafio 1 (VENCIDO)
Como incentivo será dado 500 pontos no Viva o Linux para o primeiro que responder corretamente os valores de P e de Q para os N propostos. Junto com a simples resposta deve vir um relato sobre o programa ou técnica usada e o tempo de processamento. Alunos e ex-alunos meus não podem participar, pois estudaram em sala de aula técnicas que os colocariam em vantagem em relação aos demais. Vamos lá, tente, já que não estou realmente enviando valores impossíveis.
Para o gerenciamento deste desafio foi criado o tópico Desafio RSA número 1 . Lá estarão todas as regras do desafio e os valores a serem quebrados. Todos estes detalhes serão colocados dois dias após a publicação deste artigo. Assim, caso o desafio ainda não tenha sido publicado, você tem um tempinho para ajustar sua ferramenta.
Desafio 2 (VALE LIVRO)
Após o desafio 1 ter sido vencido, criei outro valendo um livro. A definição e os resultados podem ser vistos em Ganhe um LIVRO aqui no Vol (Desafio 2 RSA)
Devo deixar claro que só serão aceitas respostas se você mesmo implementou sua própria ferramenta e disponibilizou o código fonte, conforme instruções do fórum. Outro aviso de extrema importância é que este desafio será realizado com a concordância do administrador do Viva o Linux, já que envolvem pontos.
Páginas do artigo
1. Introdução2. A teoria dos algoritmos assimétricos
3. RSA passo a passo
4. Não frite seu processador
5. Quebrando o RSA: um desafio para você valendo um livro
6. Conclusão
Outros artigos deste autor
Programação com números inteiros gigantes
Mecanismo de firewall e seus conceitos
Armazenamento de senhas no Linux
Cuidado com números em Ponto Flutuante
Leitura recomendada
Kali On The Box - Colocando o Kali para rodar no Raspberry Pi
Como recuperar a senha de root usando uma live distro
Intrusão simples com Metasploit
Acessando o Linux via SSH através do Android
Defesa pessoal com o GPG, Nautilus Scripts, partições encriptadas e leves doses de paranoia
Comentários
[2] Comentário enviado por elgio em 05/08/2009 - 14:53h
VALENDO!
Valores de N publicados!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-1-RSA
VALENDO!
Valores de N publicados!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-1-RSA
[3] Comentário enviado por cesar em 05/08/2009 - 15:17h
@elgio
Fiquei interessado neste "teorema de Euclides e atalhos matemáticos para cálculo de módulo" tem como você me enviar este material por e-mail? não sei se pode mandar por causa do desafio, mas quando concluir o desafio tú me manda?
meu e-mail é cesar_macari@msn.com
[]'s
@elgio
Fiquei interessado neste "teorema de Euclides e atalhos matemáticos para cálculo de módulo" tem como você me enviar este material por e-mail? não sei se pode mandar por causa do desafio, mas quando concluir o desafio tú me manda?
meu e-mail é cesar_macari@msn.com
[]'s
[4] Comentário enviado por elgio em 05/08/2009 - 15:33h
O teorema de euclides é uma pequena variação da fórmula para cálculo do máximo divisor comum. Está publicado no meu site e o link é fornecido no artigo.
Quanto ao atalho matemático, claro. Mas depois. com o tempo. Também teria as explicações dos 3 testes de primaridade. não sou matemático, mas sou curioso. Corri muito atras de alguns conceitos para poder entender e até mesmo ACREDITAR no RSA :-D
Estou escrevendo um NOVO artigo sobre linguagens que irá ajudar MUITO a quebrar o N. Mas este eu vou segurar para publicar depois.
O teorema de euclides é uma pequena variação da fórmula para cálculo do máximo divisor comum. Está publicado no meu site e o link é fornecido no artigo.
Quanto ao atalho matemático, claro. Mas depois. com o tempo. Também teria as explicações dos 3 testes de primaridade. não sou matemático, mas sou curioso. Corri muito atras de alguns conceitos para poder entender e até mesmo ACREDITAR no RSA :-D
Estou escrevendo um NOVO artigo sobre linguagens que irá ajudar MUITO a quebrar o N. Mas este eu vou segurar para publicar depois.
[5] Comentário enviado por fernandoborges em 06/08/2009 - 13:13h
Prof. Elgio, parabéns pelo rigor com que tratou o assunto. Mesmo sendo formado em Matemática, ainda me faltavam alguns conceitos que relacionassem Teoria dos Numeros e Criptografia Assimétrica. Comecei uma Pós nesse ramo em 2007, mas infelizmente tive que trancar. Seu artigo me remeteu ao OpenVPN, que aliás, é uma das minha ferramentas em meu trabalho atual. O Sr poderia fazer uma análise da segurança implementada no OpenVPN com certificados X509 à luz de seu conhecimento sobre criptografia?
Prof. Elgio, parabéns pelo rigor com que tratou o assunto. Mesmo sendo formado em Matemática, ainda me faltavam alguns conceitos que relacionassem Teoria dos Numeros e Criptografia Assimétrica. Comecei uma Pós nesse ramo em 2007, mas infelizmente tive que trancar. Seu artigo me remeteu ao OpenVPN, que aliás, é uma das minha ferramentas em meu trabalho atual. O Sr poderia fazer uma análise da segurança implementada no OpenVPN com certificados X509 à luz de seu conhecimento sobre criptografia?
[6] Comentário enviado por elgio em 06/08/2009 - 13:57h
Fernando:
Não importa qual programa, nenhum deles usa algoritmos Assimétricos para cifrar!
Os assimétricos, como o RSA ou o DSA são computacionalmente inviáveis, devido ao esforço matemático exigido. Um processador não daria conta de cifrar um download de um CD Iso, por exemplo.
TODOS ELES usam algoritmos SIMÉTRICOS, por serem bons e rápidos.
Olhando o man do openvpn vi que ele prefere usar o algoritmo simétrico blowfish em modo CBC (Cipher-Block Chaining, ou seja, como um algoritmo de bloco encadeando-os para evitar repetição).
Mas como toda boa ferramenta profissional, o OpenVPN suporta diversos algoritmos (execute openvpn --show-ciphers para ter uma listagem do seu).
Assim, a segurança dos dados em tráfego dependem do algoritmo e do tamanho da chave. O menor deles, ma minha versão de openvpn, é o DES com 64 bits que já está fraquinho. Usar ele pode significar estar fragilizado.
O Blowfish padrão usa 128 bits que está MUITO, mas MUITO BOM (o pessoal acha que é pouco já que o RSA deve ser de, pelo menos, 1024. Mas são princípios matemáticos distintos: http://www.vivaolinux.com.br/artigo/Introducao-a-criptografia cap 6)
Bom, mas onde entra o certificado e a criptografia assimétrica?
Quando cliente e servidor negociam, há uma troca de certificados. Um certificado tem muitas informações, incluindo a chave pública, podento estar assinado por uma certificadora.
Um certificado usa diversos algoritmos:
- RSA ou algum outro assimétrico: esta chave deve ser de pelo menos 1024 bits. Menos que isto é perigoso
- HASH: Pra as assinaturas digitais. Não convém mais usar o MD5 por conta das colisões descobertas. O bam bam bam de agora é o SHA1
Ocorre que no início cliente e servidor CRIAM uma chave de sessão de 128 bits para ser usado pelo simétrico (no caso o blowfish). Podem fazer isto usando o protocolo Diffie-Hellman. Esta negociação irá precisar de algumas mensagens, TODAS CIFRADAS PELO RSA (e gastando CPU!).
Mas são só estas poucas, pois assim que uma chave de sessão é trocada, abandonam o lentérrimo RSA e usam o "rapidésimo" simétrico (blowfish no exemplo).
Então, caro amigo, o openssl é sim EXTREMAMENTE SEGURO se observadas algumas coisas:
a) que se use algoritmos bons. O padrão que vem nele está "da hora"
b) que se usem certificados bons, sem MD5 de preferência
c) que se use uma chave forte RSA, se for o caso, de, pelo menos, 1024 bits
Fernando:
Não importa qual programa, nenhum deles usa algoritmos Assimétricos para cifrar!
Os assimétricos, como o RSA ou o DSA são computacionalmente inviáveis, devido ao esforço matemático exigido. Um processador não daria conta de cifrar um download de um CD Iso, por exemplo.
TODOS ELES usam algoritmos SIMÉTRICOS, por serem bons e rápidos.
Olhando o man do openvpn vi que ele prefere usar o algoritmo simétrico blowfish em modo CBC (Cipher-Block Chaining, ou seja, como um algoritmo de bloco encadeando-os para evitar repetição).
Mas como toda boa ferramenta profissional, o OpenVPN suporta diversos algoritmos (execute openvpn --show-ciphers para ter uma listagem do seu).
Assim, a segurança dos dados em tráfego dependem do algoritmo e do tamanho da chave. O menor deles, ma minha versão de openvpn, é o DES com 64 bits que já está fraquinho. Usar ele pode significar estar fragilizado.
O Blowfish padrão usa 128 bits que está MUITO, mas MUITO BOM (o pessoal acha que é pouco já que o RSA deve ser de, pelo menos, 1024. Mas são princípios matemáticos distintos: http://www.vivaolinux.com.br/artigo/Introducao-a-criptografia cap 6)
Bom, mas onde entra o certificado e a criptografia assimétrica?
Quando cliente e servidor negociam, há uma troca de certificados. Um certificado tem muitas informações, incluindo a chave pública, podento estar assinado por uma certificadora.
Um certificado usa diversos algoritmos:
- RSA ou algum outro assimétrico: esta chave deve ser de pelo menos 1024 bits. Menos que isto é perigoso
- HASH: Pra as assinaturas digitais. Não convém mais usar o MD5 por conta das colisões descobertas. O bam bam bam de agora é o SHA1
Ocorre que no início cliente e servidor CRIAM uma chave de sessão de 128 bits para ser usado pelo simétrico (no caso o blowfish). Podem fazer isto usando o protocolo Diffie-Hellman. Esta negociação irá precisar de algumas mensagens, TODAS CIFRADAS PELO RSA (e gastando CPU!).
Mas são só estas poucas, pois assim que uma chave de sessão é trocada, abandonam o lentérrimo RSA e usam o "rapidésimo" simétrico (blowfish no exemplo).
Então, caro amigo, o openssl é sim EXTREMAMENTE SEGURO se observadas algumas coisas:
a) que se use algoritmos bons. O padrão que vem nele está "da hora"
b) que se usem certificados bons, sem MD5 de preferência
c) que se use uma chave forte RSA, se for o caso, de, pelo menos, 1024 bits
[7] Comentário enviado por elgio em 07/08/2009 - 10:01h
VALENDO!
Valores de N publicados!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-1-RSA
VALENDO!
Valores de N publicados!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-1-RSA
[8] Comentário enviado por fernandoborges em 08/08/2009 - 16:34h
Prof. Elgio,
Quero agradecê-lo pela rápida abordagem sobre o OpenVPN. Muito esclarecedor pra mim. Será de grande valia para que eu possa avaliar melhor a segurança dos dados que trafegam na minha VPN.
Cordiais saudações,
Fernando.
Prof. Elgio,
Quero agradecê-lo pela rápida abordagem sobre o OpenVPN. Muito esclarecedor pra mim. Será de grande valia para que eu possa avaliar melhor a segurança dos dados que trafegam na minha VPN.
Cordiais saudações,
Fernando.
[9] Comentário enviado por marcelogpl em 09/08/2009 - 01:32h
Parabéns Professor!
Realmente um artigo muito interessante e claro nos conceitos utilizados, vai ajudar muito em projetos onde um dos focos é a segurança.
Obrigado
Parabéns Professor!
Realmente um artigo muito interessante e claro nos conceitos utilizados, vai ajudar muito em projetos onde um dos focos é a segurança.
Obrigado
[10] Comentário enviado por elgio em 12/08/2009 - 16:52h
Novo desafio postado.
ESTE VALE UM LIVRO!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-2-RSA
Novo desafio postado.
ESTE VALE UM LIVRO!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-2-RSA
[11] Comentário enviado por elgio em 13/08/2009 - 10:08h
Ontem pela manhã removi o link do artigo que remetia para o cálculo do D em C. Ele não funcionava para todos os casos. Agora eu REFIZ o código e voltei a citar o código em C no artigo. Esta versão, em C, FUNCIONA e corretamente calcula qualquer valor de D, mas só se ele estiver dentro da capacidade da ULA. Necessário para GANHAR O LIVRO do desafio.
Ah, mas com este código não dá para quebrar todos os D?
Ora, modifique ele: http://www.vivaolinux.com.br/artigo/Programacao-com-numeros-inteiros-gigantes/
Ontem pela manhã removi o link do artigo que remetia para o cálculo do D em C. Ele não funcionava para todos os casos. Agora eu REFIZ o código e voltei a citar o código em C no artigo. Esta versão, em C, FUNCIONA e corretamente calcula qualquer valor de D, mas só se ele estiver dentro da capacidade da ULA. Necessário para GANHAR O LIVRO do desafio.
Ah, mas com este código não dá para quebrar todos os D?
Ora, modifique ele: http://www.vivaolinux.com.br/artigo/Programacao-com-numeros-inteiros-gigantes/
[13] Comentário enviado por rafatmb em 23/11/2010 - 17:23h
Excelente documentação sobre o assunto. Informações fundamentais para todos os administradores de rede linux.
um bom material de apoio em: http://cseweb.ucsd.edu/~mihir/papers/oae.pdf
Acho importante sabermos a história das coisas, e de onde vieram as soluções que hoje fazem parte do dia a dia. Muitas vezes, usamos tanto, que nem atribuimos a devida importante para as ferramentas, e deixamos também de reconhecer aqueles que passaram tanto tempo estudando e desenvolvendo a tecnologia.
Abraço a todos!
Rafael Marangoni
LPIC/1/2/3 - Expertise em Servidor Linux
http://www.brlink.com.br
Excelente documentação sobre o assunto. Informações fundamentais para todos os administradores de rede linux.
um bom material de apoio em: http://cseweb.ucsd.edu/~mihir/papers/oae.pdf
Acho importante sabermos a história das coisas, e de onde vieram as soluções que hoje fazem parte do dia a dia. Muitas vezes, usamos tanto, que nem atribuimos a devida importante para as ferramentas, e deixamos também de reconhecer aqueles que passaram tanto tempo estudando e desenvolvendo a tecnologia.
Abraço a todos!
Rafael Marangoni
LPIC/1/2/3 - Expertise em Servidor Linux
http://www.brlink.com.br
[14] Comentário enviado por uberalles em 01/12/2010 - 01:28h
Grande e excelentíssimo Professor. Que pena que só encontrei este artigo agora.. há dois meses atrás, por volta de outubro, tive que fazer um programa em C, com API MySQL para tratar senhas e tals e acabei usando a função ENCODE() e DECODE() do próprio MySQL, sendo que queria ter feito em C. talvez eu reveja e refaça uma nova versão, mas a que tenho hoje está muito boa.
Um abraço e muito obrigado.
.
Grande e excelentíssimo Professor. Que pena que só encontrei este artigo agora.. há dois meses atrás, por volta de outubro, tive que fazer um programa em C, com API MySQL para tratar senhas e tals e acabei usando a função ENCODE() e DECODE() do próprio MySQL, sendo que queria ter feito em C. talvez eu reveja e refaça uma nova versão, mas a que tenho hoje está muito boa.
Um abraço e muito obrigado.
.
[15] Comentário enviado por DavidsonDFGL em 26/07/2012 - 22:13h
Poxa, de longe o melhor artigo de RSA que já li na internet, tanto que até tive vontade de implementar algo simples em C, mas me veio uns problemas:
o programa gerou aleatoriamente
p = 5
q = 11
e = 7
o n 55
o qq 40
e o d deu 23
acontece que quando cifro o número 10 por ex, o resultado é 10 também, e decifrado vira 18.
Isso seria uma infeliz coincidência, ou tem algo de muito errado com estes valores? confesso que já vi e revi estes valores e aparentemente estão certos, :(
Poxa, de longe o melhor artigo de RSA que já li na internet, tanto que até tive vontade de implementar algo simples em C, mas me veio uns problemas:
o programa gerou aleatoriamente
p = 5
q = 11
e = 7
o n 55
o qq 40
e o d deu 23
acontece que quando cifro o número 10 por ex, o resultado é 10 também, e decifrado vira 18.
Isso seria uma infeliz coincidência, ou tem algo de muito errado com estes valores? confesso que já vi e revi estes valores e aparentemente estão certos, :(
[16] Comentário enviado por sk4d1nh4 em 26/11/2012 - 17:02h
[17] Comentário enviado por DavidsonDFGL em 26/07/2012 - 22:13h:
Poxa, de longe o melhor artigo de RSA que já li na internet, tanto que até tive vontade de implementar algo simples em C, mas me veio uns problemas:
o programa gerou aleatoriamente
p = 5
q = 11
e = 7
o n 55
o qq 40
e o d deu 23
acontece que quando cifro o número 10 por ex, o resultado é 10 também, e decifrado vira 18.
Isso seria uma infeliz coincidência, ou tem algo de muito errado com estes valores? confesso que já vi e revi estes valores e aparentemente estão certos, :(
Caro DavidsonDFGL,
acredito que tenha alguma coisa errada no seu "C". Decifrando o 10 com esses números da 10 mesmo. Faça o teste. echo (10^23)%55 | bc
[17] Comentário enviado por DavidsonDFGL em 26/07/2012 - 22:13h:
Poxa, de longe o melhor artigo de RSA que já li na internet, tanto que até tive vontade de implementar algo simples em C, mas me veio uns problemas:
o programa gerou aleatoriamente
p = 5
q = 11
e = 7
o n 55
o qq 40
e o d deu 23
acontece que quando cifro o número 10 por ex, o resultado é 10 também, e decifrado vira 18.
Isso seria uma infeliz coincidência, ou tem algo de muito errado com estes valores? confesso que já vi e revi estes valores e aparentemente estão certos, :(
Caro DavidsonDFGL,
acredito que tenha alguma coisa errada no seu "C". Decifrando o 10 com esses números da 10 mesmo. Faça o teste. echo (10^23)%55 | bc
[18] Comentário enviado por dougaslinux em 01/10/2013 - 00:19h
Olá, Ótimo poste!
Se alguem poder me confimar alguns sistemas que utilizam a criptografia RSA , ficarei muito grato!
Olá, Ótimo poste!
Se alguem poder me confimar alguns sistemas que utilizam a criptografia RSA , ficarei muito grato!
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Artigos
Servidor de Backup com Ubuntu Server 24.04 LTS, RAID e Duplicati (Dell PowerEdge T420)
Visualizar câmeras IP ONVIF no Linux sem necessidade de instalar aplicativos
Atualizar Debian Online de uma Versão para outra
Dicas
Proteja seu Linux Mint com o Timeshift: Restaure o sistema mesmo que ele não inicie!
Instalando Google Chrome no Debian 13
Tópicos
Top 10 do mês
-
Xerxes
1° lugar - 59.546 pts -
Fábio Berbert de Paula
2° lugar - 36.270 pts -
Buckminster
3° lugar - 20.880 pts -
Sidnei Serra
4° lugar - 13.682 pts -
Mauricio Ferrari
5° lugar - 12.938 pts -
Alberto Federman Neto.
6° lugar - 12.520 pts -
Samuel Leonardo
7° lugar - 11.962 pts -
Daniel Lara Souza
8° lugar - 11.730 pts -
Andre (pinduvoz)
9° lugar - 10.950 pts -
edps
10° lugar - 10.878 pts
Scripts
A maior comunidade GNU/Linux da América Latina! Artigos, dicas, tutoriais, fórum, scripts e muito mais. Ideal para quem busca auto-ajuda.
Site hospedado por:
