Ok, acho que encontrei uma falha em ... alguma coisa. Eu sinceramente não sei. Este é um cenário tão estranho.
Eu estava tentando quebrar uma criptografia assimétrica muito pequena (RSA), assim como um projeto de Prova de Conceito para um de meus amigos. Para aqueles de vocês que não sabem muito sobre a RSA, vou examinar os fatos importantes aqui. Se você já conhece o RSA, pule o seguinte parágrafo:
O RSA é um algoritmo de criptografia assimétrica (também conhecido como criptografia de chave pública / privada). Isso significa que existem duas chaves: pública e privada. Ambos podem ser usados para criptografar, mas somente a outra chave pode ser descriptografada. Então, se eu criptografar um pequeno arquivo de texto com a chave privada, apenas a chave pública pode descriptografá-lo. Isso é útil em trocas de chaves. Isso funciona usando um princípio matemático chamado Fatoração Prima (o fato de que a multiplicação de dois números primos é fácil, mas é difícil fatorar os 2 números primos originais do produto). Então imagine sua chave pública que pode criptografar, mas somente sua chave privada pode descriptografar. Sua chave privada tem os 2 números primos, e sua chave pública tem o produto desses 2 primos (o módulo). A única maneira de alguém descriptografar dados criptografados com a chave pública seria fatorar o módulo de volta nos 2 primos e fazer engenharia reversa da chave privada. Isso era o que eu estava tentando fazer, mas em uma escala muito pequena.
Sim, tão importante fatoração! Isso é o que eu estava fazendo. Gerei uma chave RSA de 128 bits (minúscula em termos de criptografia assimétrica, especialmente considerando que meu processador de 2 GHz no meu laptop considerou isso em menos de um segundo). Eu extraí o módulo e, usando um comando inadequado ao traduzi-lo de hexadecimal para decimal (esquecendo de selecionar o ibase ao usar bc), resultou em 97964999429910939982995739699617. Eu então usei o comando factor.
Foi aí que as coisas ficaram divertidas.
Quando eu fatorei, recebi 8 respostas em vez de apenas as 2 que eu esperava.
97964999429910939982995739699617: 3 3 3 17 433 613 937 858164002128703934431
Pensando nisso agora, percebo por que não obtive 2 respostas: esse não foi o verdadeiro módulo para o par de chaves da RSA. Mas esse não é o "bug" que encontrei (ou você não estaria lendo isso).
Para confirmar, decidi multiplicar os números para obter o módulo novamente.
Eu usei o comando
echo $((3*3*3*17*433*613*937*858164002128703934431))
Bem, certamente isso deve resultar no número inicial novamente, certo? Não há razão para que isso não seja 97964999429910939982995739699617.
Bem, essa foi a minha linha de pensamento até eu ter a resposta -8628928582186374751.
Eu não tenho absolutamente nenhum indício de por que esse comando retornaria uma resposta tão obviamente errada. Como poderia até ser negativo? Isso é uma falha nas funções matemáticas nativas? O comando factor estava correto, eu sei que com certeza porque quando eu tentei usar uma calculadora física real (TI-84) ele retornou o valor que eu fatorado originalmente.
Eu tentei este comando no meu laptop no começo (rodando o Kali Linux. O comando "uname -rvo" me diz "4.3.0-kali1-amd64 # 1 SMP Debian 4.3.3-5kali4 (2016-01-13) GNU / Linux "). Então eu conectei remotamente aos servidores Gentoo da minha escola e executei o mesmo comando. Mesma resposta obviamente inválida. Uname diz "4.1.15-gentoo-r1 # 2 SMP Sex 11 Mar 15:12:48 CST 2016 GNU / Linux"
O que é isso?
Você simplesmente transbordou a aritmética inteira do shell:
echo $(( 65536 * 65536 * 65536 * 32768 - 1 ))
9223372036854775807
echo $(( 65536 * 65536 * 65536 * 32768 ))
-9223372036854775808
Você pode usar uma ferramenta de precisão arbitrária como bc para isso
bc
3*3*3*17*433*613*937*858164002128703934431
97964999429910939982995739699617
Ou
echo '3*3*3*17*433*613*937*858164002128703934431' | bc
97964999429910939982995739699617