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

Por: André Vitor Matos em 25/08/2009 | Blog: http://www.google.com/profiles/andre.vmatos


Quebrando o RSA



E cá estamos nós, a parte mais demorada do desafio consiste na criação de um programa que teste todas as possibilidades de divisão para os números N a fim de se obter seus fatores P e Q. Facilmente já se pode perceber uma otimização fraca, mas que já diminui o esforço pela metade. O primeiro impulso poderia ser construir um programa que tentasse dividir N por 2, depois por 3, 4, 5. No entanto os múltiplos de 2 não precisam ser testados. A rigor, testando-se apenas a divisibilidade do número por 2 é suficiente para todos os pares, mas, claro, qual é o sentido em se fazer uma chave par? Por esse motivo, os testes podem ser feitos apenas nos ímpares, começando em 3.

Esta parte do desafio não exige grande habilidade, programas complexos ou raciocínio lógico. O problema dos divisores de um número é extremamente clássico, sendo um dos primeiros exercícios aos aprendizes de qualquer linguagem de programação. Um programa simples em python para resolver este problema, e minha primeira versão da resolução deste exercício, que funcionou satisfatoriamente bem para as primeiras e mais simples chaves:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# André Vitor de Lima Matos
# andre.vmatos@gmail.com

from math import sqrt
from sys import argv

def verifica_primo(n):
   d=3
   x=int(sqrt(n))
   if n % 2 == 0:
     print "É par"
     return False

   while d <= x:
     if n % d == 0:
       print d, '*', n / d, '=', n
       return False
     else:
       d += 2
   return True

if verifica_primo(n=int(argv[1])):
   print("É primo")
else:
   print("Não é primo")

Note que este programa era, inicialmente, um programa apenas de verificação de primos. Importante ressaltar, para alguns, que, na fatoração de um número qualquer, basta que se testem as possibilidades de 2 à raiz quadrada daquele número, já que, matematicamente, se um número tiver divisores (não for primo) ao menos um deles será, certamente, menor ou igual que a raiz do mesmo.

Este programa me ajudou muito, principalmente na quebra das primeiras chaves, as mais fracas (com divisores pequenos), mas logo se mostrou insuficiente ao trabalhar com chaves maiores. A principal limitação dele, como da maior parte dos programas inicialmente feitos pra isso, é a de ser single-thread. Isso quer dizer que, mesmo com processadores relativamente potentes, com mais de um núcleo, ele fica limitado a apenas um, não usufruindo nem de metade da potência computacional da máquina. A segunda versão do programa, e que incluiu os últimos recursos importantes, obrigou-me a aprender multi-threading em python para implementação no programa. Sempre gostei de python, mas nunca tinha me aprofundado a esse ponto, até por falta de necessidade pra isso. Segue o programa final:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# André Vitor de Lima Matos
# andre.vmatos@gmail.com


from math import sqrt
from sys import argv, exit
from processing import Process, currentProcess

def verifica_primo(n, th, cores):
   qth=int(sqrt(n) / cores) # Tamanho de cada "pedaço" do processamento. Raiz de n sobre número de cores
   qth_prox=qth * (th+1) + 3 # Próxima parte

   d = qth * th - 3 # Colocar d pra começar um pouco antes do lugar certo. Margem de segurança
   if d < 0: d = -d # Mas, para isso, tem que corrigir o primeiro
   if d % 2 == 0:
     d += 1 # Temos que ter certeza que d é impar

   if n % 2 == 0: # Uma verificaçãozinha pra ter certeza que n não é par. Not FAIL =D
     print "É par"
     return False

   while d <= qth_prox: # Fazer os testes enquanto d for menor do que a próxima parte
     if n % d == 0:
       print d, '*', n / d, '=', n # Imprime P e Q
       return False # Era, originalmente uma função de testes de primos
       exit(1)
     else:
       d += 2 # Incrementando o d ímpar de dois em dois
   return True # Teste de primos
   exit(0)

if __name__ == '__main__':
   if len(argv) != 3:
     raise SyntaxError, "Uso: %s N cores" % argv[0]
   for parte in range(int(argv[2])):
     p = Process(target=verifica_primo, args=[int(argv[1]), parte, int(argv[2])]) # Multi-Threading
     p.start()


Este programa, sim, poderia tirar o máximo do computador, dentro da limitação do python por ser uma linguagem interpretada. Mas esta ainda não foi a versão utilizada para se vencer o desafio. Esta é a versão correta do programa, que divide o trabalho em partes iguais, no número de núcleos do computador, e executa os testes em cada parte, de ímpar em ímpar.

Após a dica 3 do Elgio, que infelizmente não deduzi de início, de que era muito mais provável que as chaves estivessem mais próximas da raiz do número do que do começo, o que evitaria um trabalho enorme, um programa mais informal, adaptado ao meu computador com 2 núcleos, foi criado com base nesse anterior, para que fizesse a busca na mesma faixa de números nos dois núcleos simultaneamente, mas decrementando em 4, ao invés de dois. Sendo assim, um dos núcleos processaria os números 13, 9 e 5 (num exemplo onde 13 seria a raiz de N), enquanto o outro faria 11, 7 e 3:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# André Vitor de Lima Matos
# andre.vmatos@gmail.com


from math import sqrt
from sys import argv, exit
from processing import Process, currentProcess

def verifica_primo(n, nth): # nth é o desemparelhamento dos processos
    qth=int(sqrt(n))
    d = qth + 3
    if d % 2 == 0:
        d = d + 1

    d = d - nth
    if n % 2 == 0:
        print "É par"
        return False
    while d >= 3:
        if n % d == 0:
            print d, '*', n / d, '=', n
            return False
        else:
            d -= 4
    return True

if __name__ == '__main__':
    p = Process(target=verifica_primo, args=[int(argv[1]), 2]) # Um processador iniciando em 2
    p.start()
    p = Process(target=verifica_primo, args=[int(argv[1]), 4]) # E outro em 4
    p.start()


Graças a este programa e à última dica do Elgio, pude vencer o desafio, sendo que nunca conseguiria terminar o processamento da última chave a tempo (poderia levar dias).

Página anterior     Próxima página

Páginas do artigo
   1. Apresentação
   2. O RSA e o desafio proposto
   3. Quebrando o RSA
   4. A parte difícil
   5. Conclusão
Outros artigos deste autor

MOC - O player de áudio para consoles

Instalando o KDE 4.1 no Slackware 12.1

Leitura recomendada

FproxyAdmin - Gerenciador WEB do Proxy

Instalando o antivírus BitDefender no Linux

Aplicação do firmware intel-microcode no Slackware

PaX: Solução eficiente para segurança em Linux

Sudoers 1.8.12 - Parte IV - Manual

  
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.

[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

[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

[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

[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!

[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

[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




[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

[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+

[10] Comentário enviado por s0l1d_k3rn3l em 08/01/2010 - 04:49h

aew

muito bom artigo...

flw

[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 =)

[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+

[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 .

[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!

[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

[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!

[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

[18] Comentário enviado por danilosampaio em 20/04/2012 - 12:40h

Excelente artigo! Parabéns!

[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!


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts