Criptografia assimétrica com o RSA
Devido a dificuldade de troca de chaves, os algoritmos assimétricos são o principal motor de comunicações cifradas sobre SSL, como o HTTPS. De fácil compreensão, o RSA é um interessante método matemático que permite a cifra assimétrica baseado em números primos. E você pode brincar de RSA com a sua calculadora bc de linha de comando.
Parte 5: Quebrando o RSA: um desafio para você valendo um livro
A quebra do algoritmo RSA consiste simplesmente em se descobrir o valor de d da chave privada Kd. O d pode ser calculado pelo teorema de euclides, desde que se conheçam os valores do e e de qq (quociente de euclides).
Ora, o valor de e é publicamente conhecido, pois está exposto na chave pública Ke. Logo, quebrar o algoritmo RSA consiste em se descobrir o valor de qq, o quociente de euclides.
Como qq é calculado? Pela multiplicação de (P-1) por (Q -1), então, quebrar o RSA consiste simplesmente em encontrar os valores de P e Q.
Pensar em uma forma de encontrar os valores de P e Q é muito fácil, afinal sabe-se que o valor de N resultou da multiplicação destes dois números. Como o valor de N também é conhecido, pois está exposto na chave pública, quebrar o RSA é simplesmente respondera a pergunta
Quais os dois números que multiplicados um pelo outro resulta em N?
Se lhe é dito que o N é 299, a busca pelo P e pelo Q teria sucesso ao se achar P=13 e Q=23. Pronto. Fácil fácil. Um simples laço em qualquer linguagem de programação resolve isto rapidamente. Que tal uma versão do laço em bash:
Programadores em C, Java, PHP, Perl e até Basic não terão dificuldades em construir seus códigos para quebrar o RSA.
Se considerou isto uma tarefa fácil, topas um desafio?
Desafio 1 (VENCIDO)
Como incentivo será dado 500 pontos no Viva o Linux para o primeiro que responder corretamente os valores de P e de Q para os N propostos. Junto com a simples resposta deve vir um relato sobre o programa ou técnica usada e o tempo de processamento. Alunos e ex-alunos meus não podem participar, pois estudaram em sala de aula técnicas que os colocariam em vantagem em relação aos demais. Vamos lá, tente, já que não estou realmente enviando valores impossíveis.
Para o gerenciamento deste desafio foi criado o tópico Desafio RSA número 1 . Lá estarão todas as regras do desafio e os valores a serem quebrados. Todos estes detalhes serão colocados dois dias após a publicação deste artigo. Assim, caso o desafio ainda não tenha sido publicado, você tem um tempinho para ajustar sua ferramenta.
Desafio 2 (VALE LIVRO)
Após o desafio 1 ter sido vencido, criei outro valendo um livro. A definição e os resultados podem ser vistos em Ganhe um LIVRO aqui no Vol (Desafio 2 RSA)
Devo deixar claro que só serão aceitas respostas se você mesmo implementou sua própria ferramenta e disponibilizou o código fonte, conforme instruções do fórum. Outro aviso de extrema importância é que este desafio será realizado com a concordância do administrador do Viva o Linux, já que envolvem pontos.
Ora, o valor de e é publicamente conhecido, pois está exposto na chave pública Ke. Logo, quebrar o algoritmo RSA consiste em se descobrir o valor de qq, o quociente de euclides.
Como qq é calculado? Pela multiplicação de (P-1) por (Q -1), então, quebrar o RSA consiste simplesmente em encontrar os valores de P e Q.
Pensar em uma forma de encontrar os valores de P e Q é muito fácil, afinal sabe-se que o valor de N resultou da multiplicação destes dois números. Como o valor de N também é conhecido, pois está exposto na chave pública, quebrar o RSA é simplesmente respondera a pergunta
Quais os dois números que multiplicados um pelo outro resulta em N?
Se lhe é dito que o N é 299, a busca pelo P e pelo Q teria sucesso ao se achar P=13 e Q=23. Pronto. Fácil fácil. Um simples laço em qualquer linguagem de programação resolve isto rapidamente. Que tal uma versão do laço em bash:
N=299
for P in `seq 2 $N`
do
[ "`echo "$N % $P"|bc`" == "0" ] || continue
Q="`echo $N / $P|bc`"
echo P=$P Q=$Q
break
done
for P in `seq 2 $N`
do
[ "`echo "$N % $P"|bc`" == "0" ] || continue
Q="`echo $N / $P|bc`"
echo P=$P Q=$Q
break
done
Programadores em C, Java, PHP, Perl e até Basic não terão dificuldades em construir seus códigos para quebrar o RSA.
Se considerou isto uma tarefa fácil, topas um desafio?
Desafio 1 (VENCIDO)
Como incentivo será dado 500 pontos no Viva o Linux para o primeiro que responder corretamente os valores de P e de Q para os N propostos. Junto com a simples resposta deve vir um relato sobre o programa ou técnica usada e o tempo de processamento. Alunos e ex-alunos meus não podem participar, pois estudaram em sala de aula técnicas que os colocariam em vantagem em relação aos demais. Vamos lá, tente, já que não estou realmente enviando valores impossíveis.
Para o gerenciamento deste desafio foi criado o tópico Desafio RSA número 1 . Lá estarão todas as regras do desafio e os valores a serem quebrados. Todos estes detalhes serão colocados dois dias após a publicação deste artigo. Assim, caso o desafio ainda não tenha sido publicado, você tem um tempinho para ajustar sua ferramenta.
Desafio 2 (VALE LIVRO)
Após o desafio 1 ter sido vencido, criei outro valendo um livro. A definição e os resultados podem ser vistos em Ganhe um LIVRO aqui no Vol (Desafio 2 RSA)
Devo deixar claro que só serão aceitas respostas se você mesmo implementou sua própria ferramenta e disponibilizou o código fonte, conforme instruções do fórum. Outro aviso de extrema importância é que este desafio será realizado com a concordância do administrador do Viva o Linux, já que envolvem pontos.
parabéns elgio!
[]'s