Quebrando o RSA

[Baguio Loko]

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()

Fonte: Apenas usuários registrados e ativados podem ver os links., Clique aqui para se cadastrar...

[H4S_KJ27]

Muito bom Jonatan, tá mandando bem nos poste!
abraços!

[Lord Beni-Aretz]

pergunto: sera que esse poste não ficaria melhor na área de scripts?
ou ta melhor aqui mesmo?

[Baguio Loko]

Opa, desculpa a demora, eu tava viajando, muda pra min o post lord

[CryptoSystem]

Jonatan seu sacana kkkkkkkkk.

RSA era a mais segura.

E ta ai o modo de quebra-la.

Parabens fiel.

[H4S_KJ27]

kkkkkk' disse bem era a mais segura kkk

[x_mah_x]

as criptografias são seguras por um tempo, mas sempre tem alguém que as quebram, a RSA era a mais segura, e agora, o que é seguro??