(VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

1. (VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 12/08/2009 - 15:57h

.
.
.
.



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

*** PRÊMIO: Um livro sobre criptografia entregue no endereço do vencedor ***

Trata-se do "O Livro dos Códigos" de Simon Sign.

========================================
. . . . . . . . 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 de todos as questões;

4 - caso ninguém envie a resposta correta de todos em 7 dias, será decretado o vencedor aquele que mais somou pontos

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 somaram 20 pontos, mas não todos), ganhará quem enviou a resposta primeiro.

8 - O vencedor deve estar disposto a escrever um artigo no Viva o Linux contando sua história (eu colaborarei no artigo)

========================================
. . . . . . . SISTEMÁTICA . . . . . . .
========================================

Quem já ir quebrando pode enviar as repostas parciais ** POR EMAIL ** (NÂO NO FÓRUM, para não entregar os já quebrados aos demais :-D). Assim que eu receber um email com alguns quebrados, eu irei formalizar a resposta neste FÓRUM mantendo sempre um "estado atual": "Fulano tem X pontos. Atualmente é o vencedor", mas sem contar detalhes da quebra (os detalhes só no final do desafio).

O desafio será vencido por quem primeiro quebrar TODOS ou por quem mais pontos somar ao final de uma semana.

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.

Durante o desenvolvimento do desafio, dicas serão postadas neste fórum.

EMAIL PARA ENVIAR AS RESPOSTAS PARCIAIS: elgio.schlemer at gmail.com

========================================
. . VALORES DE A SEREM QUEBRADOS . .
========================================
Agora tem-se os valores de N e de E, sendo que uma mensagem foi cifrada com Ke e você tem o desafio de recuperar a mensagem. A mensagem é uma sequência de três caracteres e, em alguns casos, um número de 16 bits.

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

Encontrar P1 e Q1 = 1 ponto
Encontrar D1 = 10 pontos
Recuperar a MSG1 = 10 pontos

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

Encontrar P2 e Q2 = 5 pontos
Encontrar D2 = 50 pontos
Recuperar a MSG2 = 50 pontos

+++++++++++++
N3 = 7037566921193896543
E3 = 65537
MSG3 = 2952982415375107879 - 1067648351130204034 - 1342021018018043152 - 5618319547902349498 (3 caracteres e um número inteiro)

Encontrar P3 e Q3 = 10 pontos
Encontrar D3 = 200 pontos
Recuperar a MSG3 = 200 pontos

+++++++++++++
N4 = 23085033109316605813
Encontrar P4 e Q4 = 20 pontos
Encontrar D4 = 200 pontos

+++++++++++++
N5 = 252539935250032846903
Encontrar P5 e Q5 = 30 pontos
Encontrar D5 = 200 pontos

+++++++++++++
N6= 1080732373142027068783
Encontrar P6 e Q6 = 40 pontos
Encontrar D6 = 200 pontos

+++++++++++++
N7 = 13529301124273579600009
Encontrar P7 e Q7 = 50 pontos
Encontrar D7 = 200 pontos

+++++++++++++
N8 = 52477496982124296201703
Encontrar P8 e Q8 = 100 pontos
Encontrar D8 = 200 pontos

As mensagens foram cifradas usando o e e o n. Para recuperar a mensagem é necessário quebrar o RSA, obtendo a chave PRIVADA, ou seja o valor de D.

===========================
. . . . ESTADO ATUAL . . .
===========================

- 12/Ago/2009, 16h: publicação do desafio

- 12/Ago/2009, 17:12: 1h30m depois e ainda ninguém enviou nada, nem mesmo P1 e Q1. Alguém ganhará o livro (só se ninguém participar para o livro não ser entregue)

- 12/Ago/2009, 17:44: edição do desafio, deixando algumas coisas mais claras. 1 ponto para N1, assim alguém ganhará o livro de qualquer jeito, mesmo que com 1 ponto.

- 13/Ago/2009: 10h. Publicado programa em C para cálculo do valor de D (via euclides estendido)

http://www.vivaolinux.com.br/artigo/Programacao-com-numeros-inteiros-gigantes/

Caso deseje participar e queiras se manter informado POR EMAIL sempre que alguma mudança ocorrer neste fórum, deixe um post aqui (algo como "Eu também") e configure sua conta para ser notificado sempre que um post novo ocorrer.

Par isto vá em "Preferências" de sua conta e marque (ou deixe marcada) a opção "Acompanhar comentários."

No post a seguir está o andamento da pontuação


  


2. MELHOR RESPOSTA

André Vitor Matos
andre.vmatos

(usa Arch Linux)

Enviado em 14/08/2009 - 11:46h

Foi muito legal. Parabéns, Elgio, novamente. Muito divertido e disputado esse desafio. Obrigado. Segue o gabarito. Logo logo posto o código dos programas que usei para resolver o desafio. Abçsss


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


*** Programa ***

Segue o programa que criei para descobrir a chave. Dei uma melhorada nele, coisas que queria fazer antes mas não tinha tempo, mas em suma, nada de novo além do que usei. Notem o uso da lib processing, não inclusa nas instalações padrões python ainda, mas facilmente instalada via easy_install. Como o VOL num tava respeitando minhas identações (axo que não sei algo que deveria saber =), resolvi postar no meu google sites (inoperante, só pra funcionalidades msm).

http://sites.google.com/site/andrevitorfilerepository/Home/rsa04_p_q.py


*** Euclides Extendido ***

Estou postando também o link pro meu Google Sites do algorítimo Euclides Extendido, que é uma recodificação em python do programa do prof. Elgio. É o mesmo programa, apenas algumas adaptações pra linguagem, mas a sintaxe e algorítimos são os mesmos. A vantagem é que, como é feito em python, tem suporte nativo a números gigantes, sem ter que recorrer a alguns artifícios em outras linguagens para resolver o problema.

http://sites.google.com/site/andrevitorfilerepository/Home/euclides_ext.py


*** Potencia ***

Segue a função que usei para calcular as potencias modulares de forma mais rápida. Ninguém merece elevar números dakele tamanho à outros de tamanhos equivalentes. Essa função usa alguns conceitos de restos da divisão de potencias, algebra. Algumas fontes são a internet e o livro Majorando IME, que tem uns conceitos muito legais tambem. Como ainda não aprendi a fazer o VOL respeitar minhas indentações, vou colocar um ~ no começo da linha para cada identação dakela linha.

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 = ((c ** v) * r ** 2) % n
~ return r

3. ESTADO AUTAL (sempre atualizado)

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 10:18h

Cloves: 276 pontos
André Vitor: 1776 pontos (VENCE. Matou todos)
Carlos Ferreira: 1526 pontos
Otacílio: 1226 pontos

(última atualização 11:45 de 14/Ago)



4. Re: (VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 14:46h

Cloves quebrou P1, Q1, D1 e MSG1 as 13:49 de 13/Agosto. 21 pontos


5. DICA NUMERO 1

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 15:01h

Para achar o P e o Q é necessário um programa que lide com números gigantes, além da capacidade da ULA. Apenas o N1 pode ser quebrado dentro dos limites do processador.

Escolhendo uma linguagem com esta característica, um processador com apenas UM CORE acha P2 e Q2 em, no MÁXIMO, 20 minutos com um código SIMPLES (um laço) sem otimização alguma.


6. Re: (VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 15:45h

André Vitor mandou respostas corretas de P1/Q1, D1, MSG1 e P2/Q2 passando a frente do Cloves por somar 26 pontos. Agora sim. COMEÇOU!


7. Re: (VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 16:06h

Cloves enviou resposta P1/Q1, D1, MSG1, P2/Q2, P3/Q3 somando 36 pontos.

Carlos Ferreira TAMBÉM, dois minutos após o Cloves (Cloves vence por ter enviado antes. Ao menos por enquanto)


8. Re: (VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 16:17h

Coves envia P4/Q4 passando a frente com 56 pontos.


9. VIRADA GERAL

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 16:21h

André Vitor, que andava quieto, parece que focou seus esforços na quebra do D. Como o D a partir do N2 vale muito, André Vitor enviou corretamente as seguintes respostas:
P1/Q1, D1, MSG1
P2/Q2, D2
P3/Q3, D3

Com isto soma 286 pontos (D3 vale 200 pontos e D2 vale 50)

DISPARA NA FRENTE!
Como parece que André mexeu no código que calcula o D, a menos que alguém faça isto também, não terá como VENCÊ-LO!


10. Re: (VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 16:43h

Estado as 16:43:

Cloves: N1,D1,MSG1,N2,N3,N4,N5 e N6: 126 pontos
Andre: N1,D1,MSG1,N2,D2,N3,D3,D3: 286 pontos
Carlos: N1,D1,MSG1,N2,N3,N5,N6 (NÃO N4): 106 pontos


11. Re: (VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

André Vitor Matos
andre.vmatos

(usa Arch Linux)

Enviado em 13/08/2009 - 16:58h

Eu também, só pra receber as atualizações =D


12. DICA NUMERO 2

Elgio Schlemer
elgio

(usa OpenSuSE)

Enviado em 13/08/2009 - 17:01h

Aceleração da Potência modular.

Dica aqui no VOL a ser publicada a QUALQUER MOMENTO.

Já enviei para a fila de espera.

Não é o código, apenas a descrição de como pode ser feito.

Em outro momento publico o código.

Fiquem de olho nas dicas publicadas no VOL. O nome desta é "Cálculo da potência modular de forma eficiente"



01 02



Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts