Quebrando a criptografia RSA

Autor: André Vitor Matos <andre.vmatos at
gmail.com>

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 e o desafio proposto

No artigo Criptografia
assimétrica com o RSA
foi abordado em detalhes os conceitos
matemáticos e métodos utilizados na criptografia assimétrica, sendo que,
previamente, houve uma introdução no assunto abordado pelo artigo Fundamentos
da criptografia assimétrica
. Farei um pequeno resumo para que este
artigo possa ficar completo.

O RSA trabalha com o conceito de pares de chaves assimétricas, no qual
são criadas duas chaves, a pública e a privada. A chave pública é capaz
apenas de criptografar as mensagens, não sendo possível derivar dela a
outra chave, e deve ser distribuída a todos de quem se queira receber as
mensagens criptografadas.

A chave privada deve ser mantida no mais absoluto sigilo, sendo ela a
única capaz de descriptografar as mensagens criptografadas com a chave
pública. Para a geração das chaves obtém-se dois números primos
grandes, na ordem de 100 dígitos em chaves relativamente fracas, um
número chamado de P e e outro de Q. Eles são a base do RSA, pois a
partir deles são geradas a chave pública e privada.

Usando P e Q, um outro número, chamado de N, é calculado pelo simples
produto entre eles. A criação das chaves segue calculando um número
chamado de D escolhendo-se um outro chamado de E. Criptografa-se então a
mensagem desejada utilizando a fórmula C = ME % N (% aqui
representa a operação de módulo), onde C é a mensagem final,
criptografada, M a mensagem original, a qual se deseja criptografar, N a
chave pública e E um número primo escolhido respeitando algumas regras,
como a de ser primo relativo a (P-1) * (Q-1)). O E não é importante
para a segurança do algorítimo, sendo um primo padronizado no RSA em
65537. Para descriptografar a mensagem, faz-se M = CD % N, no
qual D é a chave privada.

Note que, no RSA, é virtualmente impossível se conseguir M com base
apenas em C e N, já que foi-se tirado o módulo (resto da divisão) de uma
potência grande de M por N, e apenas com o resto da divisão não se pode
fazer muita coisa. Isso é chamado de algorítimo de mão única, no qual
apenas com as variáveis determinadas não se consegue obter a função
inversa (que desfaz a função inicial).

Quebrar o RSA consiste exatamente em se fatorar o número N e descobrir
P e Q
, para que, a partir deles, obter-se a chave privada. Esse é
um sistema de força bruta. Entretanto, deve-se ressaltar que o número N é
o produto de dois números primos gigantes. Não parece tão
impressionante, mas contando que não existe uma forma prática matemática
de se fatorar um número rapidamente e a única possibilidade é por
tentativa e erro, um computador potente levaria alguns milhões de anos
de processamento para conseguir chegar nos dois fatores de N de uma
chave RSA atual relativamente forte (que é de, pelo menos, 1024 bits).

Quanto ao desafio, obviamente, as chaves eram bem menores, sendo que a
mais forte poderia ser quebrada no máximo em cerca de 48h de forma
direta, sem grandes otimizações (de acordo com experiências relatadas
pelo autor do artigo). Oito valores de N e algumas mensagens cifradas
foram enviados no desafio, que são os seguintes (mais detalhes em Ganhe
um livro aqui no VOL
):

N1 = 391
E1 = 7
MSG1 = 273 – 291 – 133 (São somente 3 caracteres)

N2 = 1395118689832499977
E2 = 65537
MSG2 = 326026020400037122 – 807404586589519912 – 281075936473600704 –
353132823001634071 (3 caracteres e um número inteiro)

N3 = 7037566921193896543
E3 = 65537

MSG3 = 2952982415375107879 – 1067648351130204034 – 1342021018018043152 –
5618319547902349498 (3 caracteres e um número inteiro)

Para N1, N2 e N3, havia o desafio de encontrar P e Q, para que com eles
se calculasse o valor do D e depois disso se usasse este valor para
descobrir qual era a mensagem cifrada.

N4 = 23085033109316605813

N5 = 252539935250032846903
N6= 1080732373142027068783

N7 = 13529301124273579600009

N8 = 52477496982124296201703

Para N4 até N8 o desafio era apenas recuperar P e Q e calcular o valor
do D. Não havia mensagem cifrada.

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

A parte difícil

Como dito, não existe grande dificuldade em se escrever um programa para
fatorar N. Mesmos os menos otimizados encontrariam o resultado mais
cedo ou mais tarde. Talvez a maior dificuldade neste sentido seria o de
ter uma linguagem que conseguisse trabalhar com números inteiros de
qualquer tamanho, sendo que o python já tem isto. Os maiores desafios
foram o cálculo do D e a decifragem da mensagem. Outros desafiados
chegaram mais rápido do que eu nos valores de P e Q, mas não
conseguiram, a tempo, algoritmos para o D e a mensagem.

Descobrindo a chave privada D

Essa parte não foi difícil, visto que eu estava programando em Python.
Na parte anterior, obteve-se o P e o Q, fatores primos da chave pública.
Para se descobrir a chave privada, usa-se um pequeno algorítimo,
baseado no algorítimo de Euclides. Este programa é uma completa
reimplementação do programa fornecido pelo Prof. Elgio em Algoritmo
de euclides estendido
.

Porém, propositadamente, o programa do prof. foi escrito em C, que,
sabe-se, é bastante limitado no tratamento de números grandes,
comportando números de, no máximo 32 bits (ou 64, dependendo da sua
arquitetura), o que não ajuda muito com a ordem de tamanho de números
que estamos trabalhando. Já Python não possui limitação alguma quanto ao
tamanho dos números, dando suporte nativo a números de qualquer tamanho
(posteriormente foi publicado um artigo ensinando como lidar com
números de qualquer tamanho em C. O mesmo pode ser conferido em Programação
com números inteiros gigantes
). Esse realmente foi um diferencial
que me ajudou muito. Segue o código do algorítimo de Euclides estendido
em python.

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

from sys import argv

def euclides_ext(a, b, c):
   r = b % a
   if r == 0:
     return ( (c / a) % ( b / a) )

   return ( ( euclides_ext(r, a, -c) * b + c) / (a % b) )

if len(argv) != 4:
   raise SyntaxError, "São requeridos 3 valores como argumentos"

p, q, e = argv[1:]
p=int(p)
q=int(q)
e=int(e)

n = p * q

qq = (p – 1) * (q – 1)

d = euclides_ext(e, qq, 1)
print "N =", n
print "QQ =", qq
print "D =", d

Este programa foi o que, inicialmente, me deu uma grande vantagem em
relação aos outros participantes, por ser razoavelmente complexa sua
implementação em C. Aqui não houve criatividade alguma, sendo esse
programa uma cópia quase exata do fornecido pelo professor Elgio, porém,
em python, o que o expande a números gigantes.

Decifrando as mensagens

Eis aqui o problema que, creio eu, mais deu dor de cabeça aos outros
participantes. Bem, pelo menos deu a mim, até que conseguisse
resolvê-lo. Para fazer a descriptografia das mensagens é necessário
elevar um número enorme a outro maior ainda, e depois tirar o módulo por
um número grande também.

Mesmo para computadores potentes, essas operações se tornam inviáveis,
pois elas fazem a potência do número, e depois tiram o módulo. Mas não
nos importa saber a potência, apenas o módulo. E essa operação é bem
mais fácil de ser realizada, com a técnica correta. O algorítimo que eu
implementei é, na realidade, uma técnica bem parecida com a que
professor Elgio descreveu, após o término do desafio, em Cálculo
da potência modular de forma eficiente
:

def potencia(c, d, n):
   r = c % n
   l = []

   while d > 1:
     l.append(d & 1)
     d = d >> 1
   while l:
     v = l.pop()
     r = ((a ** v) * r ** 2) % n
return r

Então, vamos lá. Note que o operador d >> 1 divide d por 2
(por isso da potência dois lá em baixo no (r**2)) e arredonda o
valor para baixo, porque vai decrescendo o d até 1 (e até 0, se
continuar, por isso d > 1). O operador d & 1 é um
simples operador lógico, que, neste caso, retorna 1 se o número for
ímpar, e 0 se o número for par.

Isso, como você pode imaginar, faz com que a lista l tenha, arredondado
pra baixo, log2(d) elementos, sendo 0 os que foram tirados
quando d era par e 1 quando d era impar. Esses serão os restos da
divisão que serão apropriadamente compensados na próxima função.

Após isto, a função l.pop() vai retirando o próximo valor (FILO, first
in, last out) da lista l, retornando-o a v e deletando-o da lista. Esse
valor, que, lembro, é 0 ou 1, eleva a, e o multiplica ao quadrado de r,
calculado previamente, antes das alterações das variáveis. Se 0, o valor
é multiplicado por 1, resultando nele mesmo, e tirado o modulo por n,
se 1, o a multiplica a potência, fazendo o papel do resto das divisões
anteriores por 2, e então, novamente, tirado o módulo por n.

Quando l se esgotar, o laço termina, e a função retorna o valor final de
r, que, por sempre estar sendo tirado o módulo por n, retornará o mesmo
valor da potência final.

Matematicamente, os restos parciais da divisão do número d, elevado
quantas vezes necessário aos fatores 2 de n, e tirado o resto novamente,
retorna o próprio número. Na prática, é algo como: o resto de uma
potência por um número n é igual ao resto por n do resto desse número
também por n elevado ao expoente que se queira.

Conclusão

É, não é tão fácil quando não se tem esses códigos, apenas o conceito.
Quinta-feira, 13/08/2009, à tarde, eu e mais alguns participantes, com
um pouco de atraso, vimos o tópico do desafio do Prof. Elgio. Aqui
começa a aventura. No começo, era fácil. Chaves propositalmente fracas,
faziam ficar fácil. A chave 2 quebrou em menos de 20 minutos (usando a
primeira versão do código e apenas um core). A chave N1 mal se pode
falar, já que é o mesmo exemplo do artigo. Enquanto quebrava a 2 e a 3,
eu ia codificando o euclides_ext.py.

Por mais simples que possa parecer, esses passos levaram quase a tarde
toda da quinta-feira. Quando é 17:30h, tenho que sair. Tinha
compromisso. Deixei 3 computadores processando N4, N5 e N7. Não deixei
mais pois não imaginei que as últimas seriam tão difíceis.

Esperava voltar antes das 21h, mas, por problemas que fogem ao nosso
alcance, só pude voltar 23h. Já estava quase perdendo as esperanças.
Tinha certeza que, mesmo tendo saído com uma vantagem de 506 pra 126
pontos (cada item do desafio tinha pontos, sendo que os mais difíceis
pontuavam mais), graças à codificação em python do euclides_estendido,
que já tinha me permitido quebrar até D4, esperava que nesse período os
outros competidores já teriam me superado.

Pensei então que, para vencê-los, teria que terminar o desafio o mais
cedo possível. Deixei 3 computadores processando N6, N7 e N8 de forma
direta (do começo para a raiz) durante a noite. Acordava a cada 2h pra
ver se algum já tinha terminado. N6 terminou de processar por volta das
4h da manhã. N7 e N8 já estavam há quase 12h processando. De manhã, o
prof. Elgio atualizou os dados. Eu estava em segundo!

Nessa hora, gelei. Aff, não posso nadar tanto pra morrer na praia. Por
volta das 9h da manhã, N7 terminou de processar. Mas ainda faltava o
mais difícil, o N8. Estava extremamente nervoso, pois a parte de
processamento pesado já tinha terminado paro o primeiro colocado e para
ele faltavam apenas as mensagens. Aprendi multi-threading com
python em 15min para tentar agilizar o processo.

Com a dica do professor de fazer o processamento de traz para frente
(publicada no fórum do desafio), cancelei tudo que estava fazendo, e
coloquei dois computadores de 2 núcleos pra processarem tudo junto, cada
núcleo com decrementos de 8.

O resultado saiu com cerca de 30min de processamento. Foi um alívio
quando terminou. Calcular o D foi rápido, pois não exige esforço
computacional algum, apenas o algoritmo certo, assim como decifrar as
mensagens. Só não foi mais rápido do que enviar o e-mail para o
professor Elgio. Essa foi muito apertada.

Este desafio foi muito proveitoso, divertido e instrutivo. Aprendi muito
com as dificuldades reais e problemas que aparecem todo dia para
resolvermos. Agradeço em especial a Deus, por ter me dado a oportunidade
de participar de eventos tão legais e compartilhar esse momento com
pessoas de tão alto nível quanto vocês.

Quero agradecer em especial ao professor Elgio pela iniciativa. Os
artigos são ótimos, e esses desafios só fazem aguçar a curiosidade e
interesse dos leitores pelo assunto. Quero parabenizar também os outros
participantes, que, por todo esforço e dedicação, também merecem a
honra.

Para finalizar, seguem os resultados finais.

Obrigado a todos, e até a próxima. E 86 105 118 97 32 79 32 76 105
110 117 120

1:
P1=17
Q1=23
N1=391
QQ1=352
E1=7
D1=151
MSG = Vol

2:
P2=859832243
Q2=1622547539
N2=1395118689832499977
QQ2=1395118687350120196
D2=203125295858749209
MSG = 88 107 122 78654 = Xkz 78654

3:
P3=2087378597
Q3=3371485619
N3=7037566921193896543
QQ3=7037566915735032328
D3=4775219542789892009
MSG = 75 87 44 3456799 = KW, 3456799

4:
P4=3391177067
Q4=6807380639
N4=23085033109316605813
QQ4=23085033099118048108
D4=22977598595017600961

5:
P5=15726738299
Q516057998197
N5=252539935250032846903
QQ5=252539935218248110408
D5=52687467144347565705

6:
P6=31683039737
Q6=34110753959
N6=1080732373142027068783
QQ6=1080732373076233275088
D6=743635295541033912753

7:
P7=104492788403
P7=129475931603
N7=13529301124273579600009
QQ7=13529301124039610880004
D7=9963504424228264636961

8:
P8=220346225717
Q8=238159273259
N8=52477496982124296201703
QQ8=52477496981665790702728
D8=12393711922764592649905


http://www.vivaolinux.com.br/artigo/Quebrando-a-criptografia-RSA

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s