VENCIDO. Desafio RSA número 1 [RESOLVIDO]
1. VENCIDO. Desafio RSA número 1 [RESOLVIDO]
elgio
(usa OpenSuSE)
Enviado em 06/08/2009 - 11:35h
..
.
.
========================================
. . . . . . . . DEFINIÇÃO . . . . . . .
========================================
Este desafio é parte integrante do artigo "Criptografia assimétrica com o RSA" http://www.vivaolinux.com.br/artigo/Criptografia-assimetrica-com-o-RSA/ em especial o capítulo 6.
Trata-se da quebra do algoritmo de criptografia assimétrico RSA.
*** 500 pontos no Viva o Linux serão dados como prêmio ao vencedor. ****
(além da glória :-D)
Um aquecimento foi realizado no fórum http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Quebre-o-algoritmo-RSA/ Alguns participantes até deram dicas de como quebrar!
========================================
. . . . . . . . REGRAS . . . . . . . . .
========================================
1 - não podem participar deste desafio alunos ou ex-alunos meus;
2 - quem participar deverá desenvolver a sua ferramenta, em qualquer linguagem, devendo postar o código caso vença;
3 - vencerá o desafio o PRIMEIRO que postar a resposta correta para todos os N's;
4 - caso ninguém envie a resposta correta de todos os N's em 7 dias, será decretado o vencedor aquele que mais se aproximou, ou seja, quebrou o maior número de Ns;
5 - questões técnicas como alguém demorar para ler o fórum ou não ter acesso a Internet no momento que conseguiu quebrar (vindo a perder para outro participante) não podem ser gerenciadas e, portanto, serão ignoradas. Quem primeiro postar, GANHA! Simples assim.
6 - um participante pode enviar quantas respostas quiser (POR EMAIL) a medida que for descobrindo novos valores;
7 - caso haja EMPATE, ou seja, mais de um conseguiu se aproximar da resposta quebrando (por exemplo, 3 participantes quebraram 4 valores, mas não todos), ganhará quem enviou a resposta primeiro.
========================================
. . . . . . . SISTEMÁTICA . . . . . . .
========================================
Aquele que quebrar TODOS os N's deve, o mais rápido possível, postar todos os valores de P e Q aqui neste fórum, registrando sua conquista. Depois, com calma, o autor da resposta envia outro post com o seu código e explicações sobre seu feito. A explicação do código é parte do desafio.
Quem já ir quebrando pode enviar as repostas parciais ** POR EMAIL ** (NÂO NO FÓRUM, para não entregar os N's já quebrados aos demais :-D). Assim que eu receber um email com alguns Ns quebrados, eu irei formalizar a resposta neste FÓRUM mantendo sempre um "estado atual": "Fulano já quebrou N1, N2 e N3. Atualmente é o vencedor", mas sem contar detalhes da quebra (os detalhes só no final do desafio).
Ao FINAL deste desafio, que será vencido por quem primeiro quebrar TODOS ou por quem mais se aproximar ao final de uma semana, um NOVO DESAFIO VALENDO UM LIVRO será postado. Eu mesmo envio o livro para o endereço fornecido pelo vencedor.
O desenrolar deste desafio, além de registrado neste fórum, será adicionado como um anexo ao artigo já publicado, sendo que os nomes dos vencedores serão citados no artigo.
Exemplos de N:
N = 529 Resposta: P = 23 Q = 23, porque 23*23 = 529
N = 166306807 Resposta: P = 12893 Q = 12899, porque 12893*12899 = 166306807
EMAIL PARA ENVIAR AS RESPOSTAS PARCIAIS: elgio.schlemer at gmail.com
========================================
. . VALORES DE N A SEREM QUEBRADOS . .
========================================
N1 = 249871121 P1 = ??? Q1 = ???
N2 = 30076707867601 P2 = ??? Q2 = ???
N3 = 498989965716559 P3 = ??? Q3 = ???
N4 = 13237830388031467381 P4 = ??? Q4 = ???
N5 = 23463599906637311887 P5 = ??? Q5 = ???
N6 = 123284359934864420371 P6 = ??? Q6 = ???
========================================
POSIÇÃO ATUAL DO DESAFIO:
- - 6/Ago/2009: publicação do post. Desafio ainda inativo
- - 7/Ago/2009: Inicio do desafio as 10h. Valores de N publicados
- - 7/Ago/2009: 10:03. Cloves quebrou com sucesso N1, N2, N3 e N4 http://www.vivaolinux.com.br/perfil/verPerfil.php?login=clovesjr A menos que alguém consiga o N5, ele é atual vencedor.
- - 7/Ago/2009: 12:10. Duas horas após, ainda sem N5 e N6
- - 7/Ago/2009: 11:55. Dorst enviou por email TODAS as respostas corretas. Falta ele mesmo postar AQUI as respostas junto com os detalhes do código. Conforme a regra, vence quem PRIMEIRO postar AQUI!
- - 7/Ago/2009: 13:48. Carlos Ferreira O. Machado enviou as respostas de N1, N2, N3, N4 e N5. Dorst pode encerrar o desafio e não sei pq ainda não o fez!
- - 7/Ago/2009 Vencido por Dorst. Covardia! 8 cores! Bom, fazer o que!
========================================
CONSIDERAÇÕES FINAIS!
Uma ferramenta simples, mas que funciona, rodando em apenas um core levou 1h41m em um Pentium 4 de 3.03.
Uma outra ferramenta, em C, extremamente otimizada (dentro de minhas limitações), levou 3 minutos usando DOIS cores de um Pentium 2.5G.
Mas o Dorst tinha acesso a uma máquina com OITO cores!! E ainda outra com dois cores e usou todos!
Parabens. Ganhou os 500 pontos. Tomei a liberdade de dar 500 pontos também ao Cloves pelo esforço já que o Dorst foi privilegiado ao ter acesso a um hardware deste porte. Ambos ganharam.