Quebrando a criptografia RSA
Este artigo visa descrever as etapas e os códigos fontes que permitiram vencer o desafio RSA, promovido aqui no VOL, como parte do artigo "Criptografia Assimétrica com o RSA", de Elgio Schlemer.
[ Hits: 97.915 ]
Por: André Vitor Matos em 25/08/2009 | Blog: http://www.google.com/profiles/andre.vmatos
Apresentação
Saudações, linuxers. Recentemente um desafio de criptografia foi postado aqui no Viva o Linux como parte de um artigo sobre o tema de nome Criptografia assimétrica com RSA. Previamente muitos outros artigos relacionados foram publicados sobre os métodos matemáticos e computacionais dos algorítimos criptográficos mais avançados existentes, focando em um dos protocolos de criptografia mais utilizados atualmente, o RSA.
O RSA é um algorítimo de criptografia baseado no conceito de chaves assimétricas e funções matemáticas de mão única. É extremamente seguro, sendo um dos mais utilizados em protocolos de serviços dos nossos dias. Os maiores exemplos são o SSH e o SSL, dos quais, literalmente, dependem o mundo. Uma brecha de segurança relativamente grande em qualquer um dos dois poderia parar a internet. O SSL é utilizado em comunicações criptografadas na rede e o SSH é o principal e mais seguro serviço de administração e comunicação entre servidores, largamente utilizado por empresas e governos, como o dos Estados Unidos. Estes chegam até a designar comissões específicas para trabalhar na auditoria do código desses protocolos, assegurando, praticamente, a invulnerabilidade dos mesmos.
Como parte do artigo sobre RSA, foi lançado em um tópico na comunidade Segurança da Informação um desafio relativo à quebra do protocolo, descoberta da chave privada e, em alguns casos, de descriptografia de mensagens de alguns caracteres. Desafio este do qual eu, felizmente, fui o vencedor, depois de várias horas de apreensão e algumas toneladas de processamento contínuo, além de diversas versões de códigos desenvolvido em Python, a melhor linguagem de programação, em minha humilde opinião.
O desafio proposto pode ser lido na íntegra, bem como sua evolução, em Ganhe um livro aqui no VOL. Antes deste, um outro desafio menor, valendo pontos no Viva o Linux, foi postado em Desafio RSA número 1 e até mesmo um "aquecimento", com algumas dicas foi previamente idealizado em Aquecimento: desafio RSA. Em cada um destes tópicos tem exemplos, dicas e links para informações úteis a quem se aventurasse a participar.
Então, vamos ao desafio!
O RSA é um algorítimo de criptografia baseado no conceito de chaves assimétricas e funções matemáticas de mão única. É extremamente seguro, sendo um dos mais utilizados em protocolos de serviços dos nossos dias. Os maiores exemplos são o SSH e o SSL, dos quais, literalmente, dependem o mundo. Uma brecha de segurança relativamente grande em qualquer um dos dois poderia parar a internet. O SSL é utilizado em comunicações criptografadas na rede e o SSH é o principal e mais seguro serviço de administração e comunicação entre servidores, largamente utilizado por empresas e governos, como o dos Estados Unidos. Estes chegam até a designar comissões específicas para trabalhar na auditoria do código desses protocolos, assegurando, praticamente, a invulnerabilidade dos mesmos.
Como parte do artigo sobre RSA, foi lançado em um tópico na comunidade Segurança da Informação um desafio relativo à quebra do protocolo, descoberta da chave privada e, em alguns casos, de descriptografia de mensagens de alguns caracteres. Desafio este do qual eu, felizmente, fui o vencedor, depois de várias horas de apreensão e algumas toneladas de processamento contínuo, além de diversas versões de códigos desenvolvido em Python, a melhor linguagem de programação, em minha humilde opinião.
O desafio proposto pode ser lido na íntegra, bem como sua evolução, em Ganhe um livro aqui no VOL. Antes deste, um outro desafio menor, valendo pontos no Viva o Linux, foi postado em Desafio RSA número 1 e até mesmo um "aquecimento", com algumas dicas foi previamente idealizado em Aquecimento: desafio RSA. Em cada um destes tópicos tem exemplos, dicas e links para informações úteis a quem se aventurasse a participar.
Então, vamos ao desafio!
Páginas do artigo
1. Apresentação2. O RSA e o desafio proposto
3. Quebrando o RSA
4. A parte difícil
5. Conclusão
Outros artigos deste autor
Instalando o KDE 4.1 no Slackware 12.1
MOC - O player de áudio para consoles
Leitura recomendada
Criando VPNs entre servidores Linux sem mistérios (parte I)
Instalar o Nagios 4 no Ubuntu ou Debian
Principais fontes de vulnerabilidade no Linux
Segurança da Informação: Necessidades e mudanças de paradigma com o avanço da civilização
OpenVPN se comportando como PPTP
Comentários
[1] Comentário enviado por elgio em 25/08/2009 - 10:52h
O André está de parabéns. Não apenas venceu o desafio, como também topou um outro desafio, este sem ganhar nada, de escrever este artigo. Pretendo, em breve, atualizar o artigo sobre RSA contando o meu lado da estória e citando os outros participantes que se esforçaram muito também.
O André está de parabéns. Não apenas venceu o desafio, como também topou um outro desafio, este sem ganhar nada, de escrever este artigo. Pretendo, em breve, atualizar o artigo sobre RSA contando o meu lado da estória e citando os outros participantes que se esforçaram muito também.
[2] Comentário enviado por mago_dos_chats em 25/08/2009 - 17:15h
Parabéns Andre, pelo primeiro lugar no desafio e pelo artigo, que ficou bem escrito, descrevendo seu esforço passo a passo pra resolver o problema.
Abraço
Parabéns Andre, pelo primeiro lugar no desafio e pelo artigo, que ficou bem escrito, descrevendo seu esforço passo a passo pra resolver o problema.
Abraço
[3] Comentário enviado por cesperanc@ em 25/08/2009 - 20:21h
Parabéns André e obrigado por partilhares a tua experiência.
Um abraço
Parabéns André e obrigado por partilhares a tua experiência.
Um abraço
[4] Comentário enviado por clovesjr em 25/08/2009 - 22:06h
Quero deixar meus parabéns ao André por ter vencido o desafio de forma magistral...
Muito legal contar sua experiência porque como também participei, encontrei desafios semelhantes aos que você encontrou mas você conseguiu superá-los antes de todos os outros participantes.
Assim que conseguir, também vou escrever uma dica ou um artigo sobre esta experiência porque usei o C como linguagem e inicialmente esbarrei naquele problema do tamanho do número e pretendo mostrar como consegui superar este problema usando o próprio C (sem usar a dica do Prof. Elgio).
Parabéns novamente...
Abraços...
Cloves Jr
Quero deixar meus parabéns ao André por ter vencido o desafio de forma magistral...
Muito legal contar sua experiência porque como também participei, encontrei desafios semelhantes aos que você encontrou mas você conseguiu superá-los antes de todos os outros participantes.
Assim que conseguir, também vou escrever uma dica ou um artigo sobre esta experiência porque usei o C como linguagem e inicialmente esbarrei naquele problema do tamanho do número e pretendo mostrar como consegui superar este problema usando o próprio C (sem usar a dica do Prof. Elgio).
Parabéns novamente...
Abraços...
Cloves Jr
[5] Comentário enviado por thiagods.ti em 29/09/2009 - 14:03h
Cara, mandasse muito bem.
Só aconselho a quando escrever um programa utilizar variáveis mais legiveis.
E não apenas "d" "r" "c". Fica pior a leitura do código.
Abraços!
Cara, mandasse muito bem.
Só aconselho a quando escrever um programa utilizar variáveis mais legiveis.
E não apenas "d" "r" "c". Fica pior a leitura do código.
Abraços!
[6] Comentário enviado por andre.vmatos em 29/09/2009 - 15:02h
Olá, Thiago. Tem razão. Normalmente, preservo essas técnicas de boa programação nos programas que faço, entretanto, estes usavam realmente estes nomes para as variáveis. Por exemplo, no RSA, a mensagem criptografada é realmente chamada de "c", por isso usei letras como variáveis nos meus programas, também, as mesmas utilizadas pelo Prof. Elgio nos programas dele. Mas obrigado mesmo assim. Qualquer coisa, estamos ai pra tirar qqr dúvida. Abçss
Olá, Thiago. Tem razão. Normalmente, preservo essas técnicas de boa programação nos programas que faço, entretanto, estes usavam realmente estes nomes para as variáveis. Por exemplo, no RSA, a mensagem criptografada é realmente chamada de "c", por isso usei letras como variáveis nos meus programas, também, as mesmas utilizadas pelo Prof. Elgio nos programas dele. Mas obrigado mesmo assim. Qualquer coisa, estamos ai pra tirar qqr dúvida. Abçss
[7] Comentário enviado por thiagods.ti em 29/09/2009 - 15:08h
Sim sim, eu li que os nomes eram esses mesmo, e como era um programa pequeno não tem muito problema. ;D
Sim sim, eu li que os nomes eram esses mesmo, e como era um programa pequeno não tem muito problema. ;D
[8] Comentário enviado por elgio em 03/10/2009 - 12:28h
Oi Thiago.
Só para lhe dar uma resposta, escolher nomes de variáveis PEQUENOS, como i, j, k, vai de acordo com a sugestão "Coding Style" de K&R (capítulo 4, nomes de variáveis).
Ela é uma crítica a outros padrões e sugere que se coloque nomes curtos, preferencialmente UMA ÚNICA LETRA, para variáveis locais, que não devem ser muitas (se forem, então tu não dividiu corretamente teu código em funções).
Sugere que variáveis Globais (Argh) tenham sua primeira letra maiúscula e que estas sim tenham um nome que digam o que ela é. E sugere que constantes sejam todas maiúsculas.
Assim, neste formato de codificação, este seria um PÉSSIMO exemplo:
int f;
int soma (int variavelIntSoma1, int VariavelIntSoma2)
{
int resultadoSoma;
..
}
Mas esta seria ideal:
int Configuracao;
int soma (int x, int y)
{
int s;
...
Uma versão completa deste padrão pode ser encontrada em http://lxr.linux.no/#linux+v2.6.31/Documentation/CodingStyle
Ele é o padrão sugerido para programar em Linux (e, até onde sei, exigido para quem quiser contribuir com o kernel)
[]s
Oi Thiago.
Só para lhe dar uma resposta, escolher nomes de variáveis PEQUENOS, como i, j, k, vai de acordo com a sugestão "Coding Style" de K&R (capítulo 4, nomes de variáveis).
Ela é uma crítica a outros padrões e sugere que se coloque nomes curtos, preferencialmente UMA ÚNICA LETRA, para variáveis locais, que não devem ser muitas (se forem, então tu não dividiu corretamente teu código em funções).
Sugere que variáveis Globais (Argh) tenham sua primeira letra maiúscula e que estas sim tenham um nome que digam o que ela é. E sugere que constantes sejam todas maiúsculas.
Assim, neste formato de codificação, este seria um PÉSSIMO exemplo:
int f;
int soma (int variavelIntSoma1, int VariavelIntSoma2)
{
int resultadoSoma;
..
}
Mas esta seria ideal:
int Configuracao;
int soma (int x, int y)
{
int s;
...
Uma versão completa deste padrão pode ser encontrada em http://lxr.linux.no/#linux+v2.6.31/Documentation/CodingStyle
Ele é o padrão sugerido para programar em Linux (e, até onde sei, exigido para quem quiser contribuir com o kernel)
[]s
[9] Comentário enviado por andre.vmatos em 16/12/2009 - 19:45h
Se alguém se interessar em aprofundar-se um pouco mais na teoria dos números na qual me baseei pra gerar o algorítimo de divisão de números grandes (congruência), pode estar dando uma lida nesse material:
http://www.rumoaoita.com/site/index.php?option=com_content&view=article&id=65:apostila-de-congruenci...
É bastante teórico, mas pra quem gosta, pode ser interessante. Na época do desafio, não usei esse material, pq não o conhecia ainda, então, usei explicações bem mais simples, mas que foram suficientes. Então, essa semana, estudando pro vestibular do ITA, que está ocorrendo agora, entre os dais 15 e 18 de dezembro, do qual estou participando, encontrei essa apostila, no site Rumo ao ITA. Pode ser útil a alguém. T+
Se alguém se interessar em aprofundar-se um pouco mais na teoria dos números na qual me baseei pra gerar o algorítimo de divisão de números grandes (congruência), pode estar dando uma lida nesse material:
http://www.rumoaoita.com/site/index.php?option=com_content&view=article&id=65:apostila-de-congruenci...
É bastante teórico, mas pra quem gosta, pode ser interessante. Na época do desafio, não usei esse material, pq não o conhecia ainda, então, usei explicações bem mais simples, mas que foram suficientes. Então, essa semana, estudando pro vestibular do ITA, que está ocorrendo agora, entre os dais 15 e 18 de dezembro, do qual estou participando, encontrei essa apostila, no site Rumo ao ITA. Pode ser útil a alguém. T+
[11] Comentário enviado por maurisilvestre em 28/05/2010 - 10:45h
Ótimo artigo André, parabéns em dobro, primeiro por vencer o desafio e segundo por compartilhar conosco, assim todos podem ter um material de apoio para aprendizado.
t+ Fica com Deus e boa sorte nos próximos desafios =)
Ótimo artigo André, parabéns em dobro, primeiro por vencer o desafio e segundo por compartilhar conosco, assim todos podem ter um material de apoio para aprendizado.
t+ Fica com Deus e boa sorte nos próximos desafios =)
[12] Comentário enviado por andre.vmatos em 28/05/2010 - 11:55h
Olá, maurisilvestre. Obrigado pelas congratulações. Espero mesmo ter sido útil. T+
Olá, maurisilvestre. Obrigado pelas congratulações. Espero mesmo ter sido útil. T+
[13] Comentário enviado por removido em 26/09/2011 - 11:36h
Olá. (celestina23love@yahoo.com)
Fiquei muito impressionado ao seu perfil em (vivaolinux.com.br) e eu sinto como ter uma boa amizade com você, meu nome é Celestina, eu gosto de você para me escrever de volta com o meu e-mail(celestina23love@yahoo.com) para que eu possa enviar-lhe uma foto e dizer mais sobre mim, obrigado por acolher o meu pedido de amizade, eu estarei esperando por sua resposta ao meu endereço de email.
Celestina.
Hello. ( celestina23love@yahoo.com )
I was very impressed to your profile at ( vivaolinux.com.br ) and i feel like to have a good friendship with you, My Name is Celestina, i will like you to write me back with my email
( celestina23love@yahoo.com ) so that i can send you a picture and tell you more about me, thanks for welcome my friendship request, i will be waiting for your respond at my mail address.
Celestina .
Olá. (celestina23love@yahoo.com)
Fiquei muito impressionado ao seu perfil em (vivaolinux.com.br) e eu sinto como ter uma boa amizade com você, meu nome é Celestina, eu gosto de você para me escrever de volta com o meu e-mail(celestina23love@yahoo.com) para que eu possa enviar-lhe uma foto e dizer mais sobre mim, obrigado por acolher o meu pedido de amizade, eu estarei esperando por sua resposta ao meu endereço de email.
Celestina.
Hello. ( celestina23love@yahoo.com )
I was very impressed to your profile at ( vivaolinux.com.br ) and i feel like to have a good friendship with you, My Name is Celestina, i will like you to write me back with my email
( celestina23love@yahoo.com ) so that i can send you a picture and tell you more about me, thanks for welcome my friendship request, i will be waiting for your respond at my mail address.
Celestina .
[14] Comentário enviado por Zaraki em 11/11/2011 - 19:12h
muito bom o artigo, vou testar agora e compartilhar com meus colegas de faculdade!
Obrigado e PArabéns!
muito bom o artigo, vou testar agora e compartilhar com meus colegas de faculdade!
Obrigado e PArabéns!
[15] Comentário enviado por andre.vmatos em 12/11/2011 - 00:32h
Obrigado, Kyouraku.
Qualquer coisa, estamos ai pra tirar qualquer dúvida.
Abçs
Obrigado, Kyouraku.
Qualquer coisa, estamos ai pra tirar qualquer dúvida.
Abçs
[16] Comentário enviado por nandobravo06 em 19/11/2011 - 01:11h
Um meio interessante de conseguir um desempenho extra no algoritmo de força bruta, é ao invés de tentar todos os ímpares (3, 5, 7, 9, 11, 13...), é só observar que tirando o 2 e o 3, todos os demais números primos é fruto da multiplicação de (x por 6) + ou - 1...
x=1:
5 = (1 * 6) - 1
7 = (1 * 6) + 1
x=2:
11 = (2 * 6) - 1
13 = (2 * 6) + 1
Isso não significa que x * 6 + ou - 1 sempre vá gerar números primos, mas significa uma redução de UM TERÇO do processamento em relação ao algoritmo que testa todos os ímpares.
Uma outra observação é que, sendo N um número gigante, se ((N+1)%6 !=0)&&((N-1)%6 !=0), Se essa condição for verdadeira, SEGURAMENTE O NÚMERO É COMPOSTO!
Um meio interessante de conseguir um desempenho extra no algoritmo de força bruta, é ao invés de tentar todos os ímpares (3, 5, 7, 9, 11, 13...), é só observar que tirando o 2 e o 3, todos os demais números primos é fruto da multiplicação de (x por 6) + ou - 1...
x=1:
5 = (1 * 6) - 1
7 = (1 * 6) + 1
x=2:
11 = (2 * 6) - 1
13 = (2 * 6) + 1
Isso não significa que x * 6 + ou - 1 sempre vá gerar números primos, mas significa uma redução de UM TERÇO do processamento em relação ao algoritmo que testa todos os ímpares.
Uma outra observação é que, sendo N um número gigante, se ((N+1)%6 !=0)&&((N-1)%6 !=0), Se essa condição for verdadeira, SEGURAMENTE O NÚMERO É COMPOSTO!
[17] Comentário enviado por elgio em 19/11/2011 - 13:55h
Que dica maravilhosa Fernando.
Se tiver mais dicas sobre números primos, manda.
Eu, particularmente, levei um pau no passado para descobrir e implementar o euclides extendido para calcular o D do RSA. Não é algo que se encontra de forma clara por ai.
[]'s
Que dica maravilhosa Fernando.
Se tiver mais dicas sobre números primos, manda.
Eu, particularmente, levei um pau no passado para descobrir e implementar o euclides extendido para calcular o D do RSA. Não é algo que se encontra de forma clara por ai.
[]'s
[19] Comentário enviado por joaocpimenta em 04/12/2012 - 20:13h
Cara, muito massa mesmo! Parabéns por todo o raciocínio e pelo post!
Cara, muito massa mesmo! Parabéns por todo o raciocínio e pelo post!
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Artigos
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Dicas
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Tópicos
Arch Linux - Guia para Iniciantes (0)
Dificuldade para renderizar vídeo no kdenlive (6)
xubuntu sem sons de eventos (3)
Erro ao iniciar serviço samba4 como novo dc em um ambiente com ad [RES... (9)
Top 10 do mês
-
Xerxes
1° lugar - 68.714 pts -
Fábio Berbert de Paula
2° lugar - 50.904 pts -
Renato Michnik de Carvalho
3° lugar - 27.302 pts -
Buckminster
4° lugar - 17.966 pts -
Mauricio Ferrari
5° lugar - 15.409 pts -
Alberto Federman Neto.
6° lugar - 14.290 pts -
Diego Mendes Rodrigues
7° lugar - 14.100 pts -
Daniel Lara Souza
8° lugar - 14.002 pts -
edps
9° lugar - 11.875 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
10° lugar - 11.329 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:
