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


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

Anúncios

Publicado em 30 de agosto de 2011, em Vivaolinux e marcado como . Adicione o link aos favoritos. 2 Comentários.

  1. este numero de E = 65537 foi um padrão usado no desafio, ou realmente pode ser usado para qualquer mensagem?

    Curtir

Um comentário começa grandes debates!

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

%d blogueiros gostam disto: