116. O criptossistema RSA é seguro caso o problema da fatoração de números
inteiros seja intratável, ou seja, não exista um algoritmo de fatoração de tempo
polinomial. (ERRADO)

117. A segurança do algoritmo RSA reside no fato de que não são conhecidos
algoritmos suficientemente rápidos de fatoração de números inteiros. (CORRETO)

Sobre o RSA:
Situação 1: Provando-se ou não possibilidade de um algoritmo de tempo polinomial
que fatore inteiros ainda assim o RSA não é seguro. Por quê?

Situação 2. Porque ainda sobra a possibilidade de conseguirmos achar a função
inversa.
Em 1. achamos a chave privada. Em 2. chegamos na mensagem original sem precisar
achar a chave privada

A questão 116 generaliza demais e por isso está errada. (Ignora a existência da
situação 2).

A questão 117 está incompleta, mas isso não a invalida. (Apenas não cita a
situação 2)




--- Em timasters@..., Thiago Cavalcanti <rcthiago@...> escreveu
>
> Pessoal ... falei com minha professora de algoritmo e veja o cometario dela
> sobre a questão:
>
>
> me: professora !me da uma maozinha rapidinho
>
> Professora: [image: :-)]
> diga la
>
> me: O criptossistema RSA é seguro caso o problema da
> fatoração de números inteiros seja intratável, ou seja,
> não exista um algoritmo de fatoração de tempo polinomial.
> o que esta errado nisso?
>
> Professora: intratavel = np-completo
> hj em dia nao podemos dizer q nao existe alg pol. Dizemos ate o momento
> nao se coonhece alg polinimial para os intrataveis
> NAO SE CONHECE AINDA
> e a questao P = NP
> a sentenca q vc escreveu
> se verdadeira diria q P diferente de NP
> entendeu??
>
> me: sim ... mas hoje em dia o que se sabe não eh que P != NP ou não podemos
> afirmar isso tb?
>
> Professora: nao podemos afirmar isto
> esta em aberto a questao P = NP ??
> O que se conjectura, o que a maioria acredita
> e q seja diferente
> mas nunca conseguimos provar nada
> e a busca continua
> e uma pergunta q vale um milhao de dolares
> serio questao central da teoria de complexidade computacional
> sostenes(um professor do departamento de Matematica da UFPE que criou uma
> teoria que tenta provar isso, infelizmente ja encontraram uma falha no
> algoritmo dele, mas ele continua tentando (brasileiro ... num desite nunca!
> )) naquelas palestras esta tentando provar q P = NP
> ele acredita nisto mas nao conseguiiu provar ainda
>
> Acho que agora fica mais claro pq a primeira esta errada e a segunda certa !
>
> Espero ter ajudado!
>
>
>
>
> 2009/7/3 josuemrosario <josuemrosario@...>
>
> >
> >
> > Pessoal esquecam o ultimo paragrafo...eu estou errado, acabei de procurar
> > com cuidado na net e encontrei o seguinte :
> >
> > 1.3 Algoritmos quânticos. Em 1994 Shor mostrou que é possível fatorar em um
> > tempo polinomial esperado, em um computador quântico. No entanto, apesar dos
> > melhores esforços de vários grupos de pesquisa, tal computador ainda não foi
> > construído, e ainda é incerto quando será perceptível a construção de em
> > computadores clássicos um. Por isso a atenção será dada apenas a algoritmos
> > os quais são executados (seriais ou paralelos).
> >
> > vide :
> >
http://homepages.dcc.ufmg.br/~nivio/cursos/pa04/seminarios/seminario12/seminario\
12.html<http://homepages.dcc.ufmg.br/%7Enivio/cursos/pa04/seminarios/seminario12\
/seminario12.html>
> >
> > --- Em timasters@... <timasters%40yahoogrupos.com.br>,
> > "josuemrosario" <josuemrosario@> escreveu
> >
> > >
> > > Pra mim as duas estão corretas.
> > >
> > > problema tratável = problema pouco complexo para solucionar
> > >
> > > Problema intratável = Problema muito complexo para solucionar (vide
> >
http//www.cos.ufrj.br/~ines/courses/cos740/leila/cos740/IAparte1.doc<http://www.\
cos.ufrj.br/%7Eines/courses/cos740/leila/cos740/IAparte1.doc>
> > >
> > > algoritmo polinomial = Um algoritmo que consome um tempo limitado(e
> > conhecido) para solucionar um problema. (vide
> >
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/NPcompleto2.html<http://ww\
w.ime.usp.br/%7Epf/analise_de_algoritmos/aulas/NPcompleto2.html>
> > )
> > >
> > > Os dois estão corretos apesar do primeiro conter uma anbiguidade. A banca
> > deveria ter colocado "enquanto o problema de fatoração de números inteiros
> > seja intratável", pois pode ocorrer de encontrarem um algoritmo de tempo
> > polinomial para fatorar numeros primos. Quem é que sabe rs rs rs, até
> > Einstein ninguém pensava em fisica quântica.
> > >
> > > Lembrando que, se não estou enganado, mesmo utilizando computação
> > quântica ainda assim não existe um algoritmo que fatore rapidamente um
> > numero primo . O algoritmo vai ficar vulnerável porque um computador
> > quântico vai poder calcular o produto de numeros primos muito rapidamente ou
> > seja poderemos quebrar a chave de criptografia por força bruta, fatorando
> > diversos numeros primos até encontrar a chave que queremos( que é o que
> > fazemos hoje com as chaves de criptografia de algoritmos simétricos).
> > >
> > >
> > > --- Em timasters@... <timasters%40yahoogrupos.com.br>,
> > Leonardo Pimenta <leolima84@> escreveu
> > > >
> > > > Pessoal, tava lendo o fórum e me deparei com estas questões. A
> > discussão de
> > > > lá não me convenceu muito, pra mim foi erro do CESPE mesmo.
> > > > As duas se contradizem, não?
> > > >
> > > > (CESPE 2008 TST) 116 O criptossistema RSA é seguro caso o problema da
> > > > fatoração de números inteiros seja intratável, ou seja,
> > > > não exista um algoritmo de fatoração de tempo polinomial.
> > > > Gabarito: E
> > > >
> > > > (CESPE - SGAAC 2007)117 A segurança do algoritmo RSA reside no fato de
> > que
> > > > não são
> > > > conhecidos algoritmos suficientemente rápidos de fatoração de números
> > > > inteiros.
> > > > Gabarito:C
> > > >
> > > > * Não coloquei a tag [Questao] porque, sendo assim, teria que
> > separá-las em
> > > > duas, o que não vem ao caso. =)
> > > >
> > > >
> > > > [As partes desta mensagem que não continham texto foram removidas]
> > > >
> > >
> >
> >
> >
>
>
>
> --
> ------------------------------------------------------------
> Thiago Rodrigues Cavalcanti
> Samsung Project - Software Engineer
> Computer Science Engineer
> Federal University of Pernambuco
> ------------------------------------------------------------
>
> "Às vezes, só uma mudança de ponto
> de vista é suficiente para transformar
> uma obrigação cansativa numa
> interessante oportunidade."
> -- Albert Flanders
>
>
> [As partes desta mensagem que não continham texto foram removidas]
>