domingo, março 23, 2025
Os computadores quânticos estão nas notícias com resultados bombásticos.
em particular, saiu uma notícia em que um computador quântica resolveu em 20 minutos um problema que, num computador normal,. demoraria um milhão de anos (ver, pplware).
Vou esquecer que são apenas notícias e vou-me concentrar na capacidade desta anunciado incremento quebrar uma password.
A quebra de uma password obriga a experimentar todas as alternativas possíveis.
Vamos supor o PIN do cartão multibanco. Como tem 4 dígitos, existem 10000 alternativa diferentes.
Uma pessoa vai conseguir quebrar o PIN se experimentar todos os números possíveis mas, em média, só precisa experimentar metade dos números (nuns casos precisará experimentar mais e noutros casos menos).
Se conseguisse experimentar mil códigos por segundo, consigo quebrar o PIN em 5 segundos (o sistema tem um controlo que apenas permite experimentar 3 valores em 24 horas). Isto é possível porque, sempre que experimentamos um número, a máquina multibanco contacta o servidor que regista a tentativa.
Agora, imaginemos um PIN com 77 dígitos (256 bits).
48195847382089182738496857364738202967558493847195847362859265845371678491644
Se um computador conseguir experimentar mil milhões de número por segundo e a sua capacidade duplicar a cada 2 anos, vou demorar 452 anos a quebrar este PIN.
Agora, estranhamente, se a capacidade do computador aumentar 2300 milhões de vezes (o que traduz fazer em 20 minutos o que demorar um milhão de anos), demorará 388 anos a quebrar o PIN!!!!!!!!!
Um aumento de 2300 milhões de vezes não vai reduzir o tempo na mesma proporção (reduz o tempo para quebrar a chave em apenas 15%) porque a segurança das chaves assume que a capacidade dos computadores vai duplicar a cada dois anos.
Bastará aumentar a chave de 77 dígitos para 87 dígitos para voltar a demorar 452 anos para a quebrar.
A questão está nos algoritmos "em tempo linear".
Se uma chave com 4 dígitos tem 10 mil hipóteses, com 5 dígitos tem 100 mil e com 6 dígitos tem 1 milhão. Então, ao aumentar um dígito, o tempo para quebrar a chave aumenta 10 vezes.
Esta proporção denomina-se por "tempo exponencial".
Os algoritmos de encriptação são de forma a que, conhecendo a chave, o tempo seja linear, isto é, calcular a mensagem encriptada com uma PIN de 8 dígitos, 62345198, demora o dobro de calcular a mensagem encriptada com um PIN com 4 dígitos, 7625.
Já a encriptação terá de ser em tempo exponencial, se com 8 dígitos demora o dobro do tempo a encriptar, demora 10 mil vezes mais tempo a quebrar o PIN.
Agora, se o computador ficar mais rápido 2300 milhões de vezes, basta aumentar o tamanho do PIN em 9 ou 10 dígitos, passar de 4 dígitos para 14 dígitos, para ter o mesmo nível de segurança.
Não existe nenhum algoritmo em tempo linear para quebra as "chaves simétricas".
Uma chave simétrica é aquela que usamos para encriptar o nosso ficheiro Word ou o PIN do multibanco: a chave que é usada para encriptar é decidida por nós e é usada a mesma a encriptar e a descodificar a mensagem.
Eventualmente, há uma algoritmos em tempo linear para quebrar as "chaves assimétricas".
No Whatsapp, a password usada não é decidida por nós mas é construída depois de se transmitir informação entre nós e o servidor. Vou apresentar um exemplo apenas ilustrativo.
A Ana e o João pretendem comunicar à distância sem se encontrarem.
A Ana sorteia uma password e um número primo, por exemplo, 473827387 e 735276697. Agora, a Ana faz a operação:
Resto = 2^473827387 % 735276697 = 331346109
A Ana envia os números (331346109; 735276697) ao João.
Com estes dois números, o João não é capaz de calcular a password da Ana, isto é, não consegue inverter a operação que não seja por tentativa e erro (melhor dizendo, existe uma algoritmo mais eficiente mas que continua a ser é em tempo exponencial).
É esta impossibilidade que permite a comunicação segura https quando acedemos a páginas de Internet e é este algoritmo que, eventualmente, está em crise com a Algoritmo de Shor.
Mas, mesmo que daqui a 100 anos se consiga fazer computadores quânticos, não há certeza de que o Algoritmo de Shor consiga mesmo quebrar as chaves em "tempo linear".
0 comentários:
Enviar um comentário