Why does the factor command produce nonsense on an RSA modulus?

Question

Ok, so I think I may have found a flaw in... something. I honestly don't know. This is such a weird scenario.

I was attempting to break very small asymmetric (RSA) encryption, just as a Proof of Concept project to one of my friends. For those of you who don't know much about RSA, I'll brush over the important facts here. If you already know about RSA, skip the following paragraph:

RSA is an asymmetric encryption algorithm (also known as public/private key cryptography). This means that there are 2 keys: Public and Private. Either can be used to encrypt, but only the other key can decrypt. So if I encrypt a small text file with the Private key, only the Public key can decrypt it. This is useful in key exchanges. This works by using a mathematical principle called Prime Factorization (the fact that multiplying two prime numbers together is easy, but factoring the original 2 prime numbers from the product is difficult). So imagine your public key that can encrypt, but only your private key can decrypt. Your private key has the 2 prime numbers, and your public key has the product of those 2 primes (the modulus). The only way someone would be able to decrypt data encrypted with the public key would be to factor the modulus back into the 2 primes and reverse engineer the private key. This was what I was trying to do, but on a very small scale.

Right, so prime factorization! That's what I was doing. I generated a 128-bit RSA key (tiny in terms of asymmetric encryption, especially considering my 2GHz processor in my laptop factored it in under a second). I extracted the modulus and, using an improper command when translating it from hexadecimal to decimal (forgetting to select the ibase when using bc), resulted in 97964999429910939982995739699617. I then used the factor command.

This was where things got funky.

When I factored it, I got 8 answers instead of just the 2 I was expecting.

97964999429910939982995739699617: 3 3 3 17 433 613 937 858164002128703934431

Thinking of it now, I realize why I didn't get 2 answers: This wasn't the real modulus to the RSA keypair. But that's not the "bug" I found (or you wouldn't be reading this).

To double check, I decided to multiply the numbers together to get the modulus again.

I used the command

echo $((3*3*3*17*433*613*937*858164002128703934431))

Well surely this should result in the starting number again, right? There is no reason why this shouldn't be 97964999429910939982995739699617.

Well that was my train of thought until I got the answer -8628928582186374751.

I have absolutely no clue why this command would return a so obviously wrong answer. How could it possibly even be negative? Is this a glitch in the native math functions? The factor command was correct, I know that for certain because when I tried to use a real, physical calculator (TI-84) it did return the value I factored originally.

I attempted this command on my laptop at first (running Kali Linux. The command "uname -rvo" tells me "4.3.0-kali1-amd64 #1 SMP Debian 4.3.3-5kali4 (2016-01-13) GNU/Linux"). Then I remote connected into my highschool's Gentoo servers and ran the same command. Same, obviously invalid answer. Uname says "4.1.15-gentoo-r1 #2 SMP Fri Mar 11 15:12:48 CST 2016 GNU/Linux"

What is this?

Answer 1

You've simply overflowed the shell's integer arithmetic:

echo $(( 65536 * 65536 * 65536 * 32768 - 1 ))
9223372036854775807
echo $(( 65536 * 65536 * 65536 * 32768 ))
-9223372036854775808

You could use an arbitrary precision tool such as bc for this

bc
3*3*3*17*433*613*937*858164002128703934431
97964999429910939982995739699617

Or

echo '3*3*3*17*433*613*937*858164002128703934431' | bc
97964999429910939982995739699617