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.
Parte 5: 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
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