Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

apocsantos

RSA de 768-bit Crackado :(

Mensagens Recomendadas

apocsantos

    Segundo o que acabei de ler, o algoritmo RSA de 768 bits foi "crackeado" :confused: Parece que para já o de 1024 bits é seguro!

    http://arstechnica.com/security/news/2010/01/768-bit-rsa-cracked-1024-bit-safe-for-now.ars

    Para quem quizer ler mais aprofundadamente sobre o assunto aqui fica o link para um bom doc.

http://eprint.iacr.org/2010/006.pdf

    Ainda que a velocidade seja lenta, parece que mais uma vez por expressões matematicas e factorização de numeros primos, descobrirar como decifrar chaves RSA de 768bits.

      Espero que seja interesante para alguém esta informação.

Cordiais cumprimentos


"A paciência é uma das coisas que se aprendeu na era do 48k" O respeito é como a escrita de código, uma vez perdido, dificilmente se retoma o habito"

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Atenção que não foi o algoritmo que foi crackado, mas apenas uma chave.

A segurança do RSA sempre assentou sobretudo na complexidade computacional da factorização de inteiros. Do pouco que li do artigo, parece-me que não propuseram nada de novo em termos de algoritmos de factorização, ou seja, não há nenhuma nova técnica para atacar o algoritmo, apenas ficamos a saber que já há recursos computacionais suficiente para quebrar chaves de 768 bits.

Já agora, em 2003 previa-se que em 2009 já houvesse máquinas capazes de quebrar chaves de 1024, recomendando-se já na altura chaves de 1024 para protecção até 2010, e no mínimo de 2048 para períodos de tempo maiores.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
apocsantos

    Eu prefiro de longe 2048, pelo menos para já. Ainda assim cada vez menos confio na segurança dos computadores.... eles são maquinas e consequentemente faliveis.

Cordiais cumprimentos


"A paciência é uma das coisas que se aprendeu na era do 48k" O respeito é como a escrita de código, uma vez perdido, dificilmente se retoma o habito"

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Os 2048 bits vão ao encontro das recomendações do RSA Labs feitas em 2003.

Mas olha que aqui nem é tanto confiar nas máquinas, mas mais no humanos que defendem que o problema da factorização é demasiado complexo. Pessoalmente acho que, tal como já aconteceu com os números primos, mais cedo ou mais tarde irá aparecer um algoritmo polinomial para o problema da factorização, o que acabaria com o RSA.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
_7_up_

mais cedo ou mais tarde irá aparecer um algoritmo polinomial para o problema da factorização, o que acabaria com o RSA.

Talvez mais tarde?

A menos q saia o tal computador quantico!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
fnds

E já existe um computador quântico, só não serve para muita coisa...

Tens info sobre isso, a ultima coisa que li é que já tinham conseguido somar dois bits.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
vbmaster

Mas olha que aqui nem é tanto confiar nas máquinas, mas mais no humanos que defendem que o problema da factorização é demasiado complexo. Pessoalmente acho que, tal como já aconteceu com os números primos, mais cedo ou mais tarde irá aparecer um algoritmo polinomial para o problema da factorização, o que acabaria com o RSA.

Pois, mas isso quereria dizer que P = NP, certo?

E isso ia dar uma grande revolução em muito lado...

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrotuga

Pois, mas isso quereria dizer que P = NP, certo?

E isso ia dar uma grande revolução em muito lado...

Não, apenas quereria dizer que esse problema em particular tinha uma resolução com complexidade do tipo P.

Provando-se que tal solução existe para todo e qualquer problema então concluímos que não há problemas com resoluções do tipo NP.

Actualmente só se conhecem problemas do tipo P, outros há que não se sabe se são do tipo P ou NP, mas não se consegue provar que são nem uma coisa nem outra.

Se se provar que todos os problemas têm uma solução do tipo P, então isso significa que todos os algoritmos de encriptação e afins podem ser comprometidos com um algoritmo cuja complexidade é conhecida à partida.

Dizendo isto lembro-me pelo menos destes dois dados que são recorrentemente esquecidos destas discussões:

1- Nada garante que a complexidade das soluções seja baixa, apenas seria conhecida. Em muitos casos será naturalmente alta.

2- É igualmente dificil encontrar um algoritmo para resolver um dado problema, apenas se saberia que exisitira uma solução com cuja complexidade é conhecia. Isto não facilita em nada a solução de um problema.

FNDS, uma reacção química pode ser entendida como um cálculo feito por um computador quântico (os reagentes). Já colocar isto ao serviço da utilidade diária envolverá tecnologias que ainda não estão aí à porta.

Moral da história. Vamos deixarmo-nos de alarmismos. As discussões sobre segurança, quando piscam o olho a matemática mais complexa ou a outros conceitos teóricos, tendem a descambar para contradições. Se analisarem bem a evolução das tecnologias de segurança vão constatar que EM TODOS os casos, as falhas estão na forma como um sistema é usado e não na 'força' de um algoritmo de encriptação ou de hashing.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
vbmaster

Não, apenas quereria dizer que esse problema em particular tinha uma resolução com complexidade do tipo P.

Provando-se que tal solução existe para todo e qualquer problema então concluímos que não há problemas com resoluções do tipo NP.

Actualmente só se conhecem problemas do tipo P, outros há que não se sabe se são do tipo P ou NP, mas não se consegue provar que são nem uma coisa nem outra.

Se se provar que todos os problemas têm uma solução do tipo P, então isso significa que todos os algoritmos de encriptação e afins podem ser comprometidos com um algoritmo cuja complexidade é conhecida à partida.

Complexidade alta é a exponencial... mesmo que tenhas algo O(n^100) não é considerado complexidade alta embora possa demorar bastante tempo a computar...

Mas certo, descobrir que a factorização é P prova que todos os outros problemas são P (se bem que há uma carrada de categorias NP e pode não significar exactamente isto), mas o algoritmo para encontrar as soluções para os outros problemas ainda teria de ser produzido e provavelmente esses algoritmos não teriam nada a ver com o da factorização, logo não ajudaria nada o facto de se ter encontrado a factorização em P.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Esclarecendo alguns pontos:

P é a classe dos problemas que podem ser resolvidos com recurso a uma máquina de turing determinística num número de passos polinomial, tendo em conta o tamanho do input.

NP é a classe dos problemas que podem ser resolvidos com recurso a uma máquina de turing não determinística num número de passos polinomial, tendo em conta o tamanho do input.

Como a partir de uma MT determinística se obtem facilmente uma não determinística que faz o mesmo, e com a mesma complexidade, qualquer problema que pertence a P, também pertence a NP. A questão é se NP é maior do que P.

O facto de se descobrir um algoritmo polinomial para o problema da factorização só implicaria que P=NP se o problema da factorização fosse NP-completo, o que, tanto quanto sei, não é o caso.

A classe de problemas NP-completos contém os problemas aos quais todos os outros problemas em NP podem ser reduzidos em tempo polinomial. Assim, havendo um algoritmo polinomial para um destes, teríamos um algoritmo polinomial para todos os outros também.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Como a partir de uma MT determinística se obtem facilmente uma não determinística que faz o mesmo, e com a mesma complexidade

Em particular, uma MT determinística é uma MT não-determinística.


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.