De quantos bits eu preciso pra guardar n valores?

GUJ Master Membro desde: 16/12/2004 17:09:19 Mensagens: 1787 Offline

Poxa, isso bem tinha aqui no fórum mas parece que se foi com aquele crash no banco. Acho que foi o thingol que tinha me respondido. Não está no meu favoritos, e não consegui achar.

Tinha algo mirabolante de logs neperianos e tudo mais, mas realmente não me lembro, era algo bem sinistro...

Desculpa o abuso, mas alguém sabe?

Tipo, para guardar dez valores eu sei que preciso de pelo menos 4 bits. Fácil. Mas e para guardar 10^507 valores?

De quantos bits eu preciso pra guardar n valores?

peguei o que vc disse e cheguei nisso, nao sei se ta certo....

10¹ = 4
10² = 40

10^n = 4 x 10^(n-1) p/ n >= 1

entao...

10^507 = 4 x 10^506

Moderador Membro desde: 29/07/2004 16:10:13 Mensagens: 17543 Offline

Você precisa calcular o logaritmo, na base 2, desse valor (10 elevado a 507).
Para saber o logaritmo de x na base 2, divida o logaritmo de x pelo logaritmo da base.
Ou seja:
log (base2) (10 elevado a 507) = log (10 elevado a 507) / log (2)

Como sabemos que log (x elevado a y) é y log (x) então:

507 . log (10) / log (2) = 1684,21...

Ou seja, você precisa de 1685 bits para guardar o valor 10 elevado a 507.

E não tem nada sinistro aí; é matemática do segundo grau.

GUJ Master Membro desde: 16/12/2004 17:09:19 Mensagens: 1787 Offline

Resumindo para um número na forma n * 10^e:

Seria isso?

Moderador Membro desde: 29/07/2004 16:10:13 Mensagens: 17543 Offline

É mais ou menos (use Math.ceil para arredondar para cima.)

GUJ Master Membro desde: 16/12/2004 17:09:19 Mensagens: 1787 Offline

Hummmm...maneiro thingol

Agora, qual seria a segurança de uma chave criptográfica de 1685 bits, em termos de ataques de força bruta?

Moderador Membro desde: 29/07/2004 16:10:13 Mensagens: 17543 Offline

Depende.
A segurança é diferente quando se trata de uma chave assimétrica RSA, ECDSA ou uma chave simétrica (como AES).
Pelo número estúpido de bits (1685) suponho que seja RSA.
Pelo que se diz por aí, 1024 bits está no limite da segurança, e 2048 é o que você deveria usar. Mas é questão de você dar uma pesquisada - cada dia consegue-se fatorar números maiores...

GUJ Master Membro desde: 16/12/2004 17:09:19 Mensagens: 1787 Offline

thingol wrote:Depende.
A segurança é diferente quando se trata de uma chave assimétrica RSA, ECDSA ou uma chave simétrica (como AES).

Pelo o que eu entendi isso teria a ver apenas com ataques de "suscetibilidade", como no caso da fatoração no RSA, pois cada algoritmo tem uma forma diferente de funcionar que é explorada por esse ataque.

Em relação à ataques de força bruta, onde se testa cada valor possível de chave, seria independente do algoritmo ser simétrico ou não.

Na verdade trata-se de um algoritmo simétrico com ~2^1685 possibilidades de chaves diferentes (1685 bits). Como eu li que o DES tem 56 bits se não me engano, e o Skipjack da NSA tem 80, então fiquei curioso...

Moderador Membro desde: 29/07/2004 16:10:13 Mensagens: 17543 Offline

Algoritmo simétrico com 1685 bits?
Provavelmente algum matemático vai publicar algo que diz que desses 1685 bits, apenas 400 (por exemplo) são efetivos - como é o caso do Triple-DES: embora sejam envolvidos 56 x 3 bits = 168 bits, devido a algumas propriedades, ele é equivalente a um algoritmo (como o AES) com cerca de 128 bits.

GUJ Master Membro desde: 16/12/2004 17:09:19 Mensagens: 1787 Offline

thingol wrote:Algoritmo simétrico com 1685 bits?
Provavelmente algum matemático vai publicar algo que diz que desses 1685 bits, apenas 400 (por exemplo) são efetivos - como é o caso do Triple-DES: embora sejam envolvidos 56 x 3 bits = 168 bits, devido a algumas propriedades, ele é equivalente a um algoritmo (como o AES) com cerca de 128 bits.

Mas esse Triple-DES de 168 bits possui 2^168 chaves possíveis?

Moderador Membro desde: 29/07/2004 16:10:13 Mensagens: 17543 Offline

Possui 2 ^168 chaves, das quais algumas são "fracas" e devem ser evitadas.
Mas a quantidade de chaves fracas é pequena.

O problema é que embora existam 2 ^168 chaves, é possível a partir de análise criptográfica (ou seja, usando uma quantidade de memória fantástica) reduzir as alternativas a examinar 2 ^ 128 chaves.

GUJ Master Membro desde: 16/12/2004 17:09:19 Mensagens: 1787 Offline

Thingol, dá uma olhada na tua MP

Notícias, artigos e o maior fórum brasileiro sobre Java