VENCIDO. Desafio RSA número 1 [RESOLVIDO]

1. VENCIDO. Desafio RSA número 1 [RESOLVIDO]

Elgio Schlemer
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.


  


2. MELHOR RESPOSTA

Carlos Eduardo Dorst
cemdorst

(usa Slackware)

Enviado em 07/08/2009 - 14:16h

Usei um 8 core para quebrar N=6, N=5, N=4, e um dual core para quebrar
o N=1, 2 e 3.
O algoritmo eh bem simples:
#!/usr/bin/ruby
#Le um numero e calcula p e q tal que p * q = numero
i = 0
z = ARGV[0]

z = Integer(z)
for i in Integer((Math.sqrt(z)*7)/8)..Integer(Math.sqrt(z))
if z.modulo(i) == 0
puts "p = " + String(i)
puts "q = " + String(z/i)
puts " "
end
end

Eu quebrei o problema em 8, ja que eu tinha 8 cores e rodei um script
em cada core. O algoritmo calcula o modulo do teu N com um "i" do meu
for, que varia de 2 ate a raiz do N. Esse espaco foi dividido em 8,
assim fazendo com que cada core fosse responsavel por um espaco de
possibilidades de p e q.

Para N=6 demorarou aprox. 1h
Para N=5 e 4 aprox 20min
Para N=1,2 e 3 demorou segundos

N1 = 249871121
p1 = 15077
q1 = 16573

N2 = 30076707867601
p2 = 4141877
q2 = 7261613


N3 = 498989965716559
p3 = 16164557
q3 = 30869387

N4 = 13237830388031467381
p4 = 3496864817
q4 = 3785628293


N5 = 23463599906637311887
p5 = 3523179743
q5 = 6659779409

N6 = 123284359934864420371
p6 = 7798535519
q6 = 15808655309

3. Re: VENCIDO. Desafio RSA número 1 [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 07/08/2009 - 10:04h

cloves quebrou N1, N2, N3 e N4 as 10:03.



4. Re: VENCIDO. Desafio RSA número 1 [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 07/08/2009 - 12:30h

Ainda esperando N5 e N6


5. DICA NUMERO 1

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 07/08/2009 - 12:33h

Certamente o N não é par. Se fosse, seria um N [*****] pois dividiria por 2.

N não sendo PAR, é certo que ele não divide por nenhum P ou Q par.

Logo, diminua os testes pela METADE começando os testes em 3 e incrementando de 2 em 2 (3, 5, 7, 9...). Muito melhor que começar testando em 2 indo de 1 em 1 (2, 3, 4, 5, 6...)


6. Re: VENCIDO. Desafio RSA número 1 [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 07/08/2009 - 14:07h

Carlos Eduardo Dorst enviou todas as respostas CORRETAS de N1, N2, N3, N4, N5 e N6.

No entanto, ainda não postou aqui NESTE FORUM as respostas e nem o código comentado. Quando o FIZER, AQUI, encerrará o desafio


7. Re: VENCIDO. Desafio RSA número 1 [RESOLVIDO]

César...
cesar

(usa CentOS)

Enviado em 07/08/2009 - 16:03h

Meu algoritmo foi +/- isso também, porém com número GRANDES ele dava pau, kkk

Mas valeu a tentativa...vou esperar o outro desafio! (quem sabe eu ganho né) =P

[]'s


8. Re: VENCIDO. Desafio RSA número 1 [RESOLVIDO]

César...
cesar

(usa CentOS)

Enviado em 07/08/2009 - 16:07h

Ah...detalhe minha máquina é um Celeron 1.8Ghz com 128k de cache, não chega nem aos pés do hardware usado pelo outros, kkkk






Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts