Floating point exception in Crypto.PublicKey.RSA

[Frank]

I've just stumbled on a discrepancy in Crypto.PublicKey.RSA. The code below will trigger a floating point exception, from which the process is terminated by SIGFPE. (I can't guarantee that this modulus is valid, but it should probably not crash'n'burn in any case).

----
import random
from Crypto.PublicKey import RSA
from binascii import hexlify,unhexlify

n='9f4de0edf3718981e891e58160a30bc864edf3f48793bf4b8c4b60bd39836a2e899cc907e33be21e389610365ac49e440ad98ef39543b953810ad74a849a5b96887a2fcbf7096ce4e015fee6ab12a05198f29d3ce224ab76103ad9cfafa48efd641537cacafe4e351561508096ab3a385b8534fca96a2e68256fdaffc84bf078860edec56cd2c236b561fd4732e59c74f722fbd1dc9bde22e2c7c0b91d314810bc4482a08f8199fdb833c6ba51f2cf472cd5c618499a36126d8b56f49a1712e1c5765b1df320c0293438ea77abf8fe0d9f3376558b3d17724a64ade69d2dfcbd9bccd05d40d98ac3d988fec399e4e671b7fefe36515cc67d31d20f8351f378'
e='010001'

msg='00f5d3b54158a22f1c57cb7337c7a515a3c08a396bf7b159694807da117dc3c970d48e233847eacadf7c8c57bae5dc1d46100a41906e17ded6463cc96fb47c2e60b95c342df70d04d116ca1bbcdbfd50417b70760064ba763d16bc2d6f6e5952674c1d6af4b9358ea18d1082d8d727a30f97752a1f72ef239d1b5e69ff69b2d486e67a39df2457439c2f9fff3240645ab6b0fd339e8e200c2e1d443457f5e1d1da6ef2a25aaa7c3a624707338b5501fac19c2f91d5a66a13fa2ba50649d664dbe27db02285906c74391b8a12210227be4b9a27b2a551b230841b56ae7b29be675606d2016b7682031b11972306267721df3d1bf6aed7b50e87d5564332deb0'

def generateRandomBinary(bytes):
    """
    Will SIGFPE before this is called
    """
    val = ''
    for i in range(bytes):
        val += '%02x'%random.randint(0,255)
    return unhexlify(val)

rsa=RSA.construct([long(n, 16), long(e, 16)])
rsa.encrypt(unhexlify(msg), generateRandomBinary)
----

gdb backtrace:
----
$ gdb python
GNU gdb (Ubuntu/Linaro 7.4-2012.04-0ubuntu2.1) 7.4-2012.04
Copyright (C) 2012 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "i686-linux-gnu".
For bug reporting instructions, please see:
<http://bugs.launchpad.net/gdb-linaro/>...
Reading symbols from /usr/bin/python...(no debugging symbols found)...done.
(gdb) run
Starting program: /usr/bin/python
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/i386-linux-gnu/libthread_db.so.1".
Python 2.7.3 (default, Aug 1 2012, 05:16:07)
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import bug

Program received signal SIGFPE, Arithmetic exception.
0xb77c9bfb in __gmp_exception () from /usr/lib/i386-linux-gnu/libgmp.so.10
(gdb) backtrace
#0 0xb77c9bfb in __gmp_exception () from /usr/lib/i386-linux-gnu/libgmp.so.10
#1 0xb77c9c4b in __gmp_divide_by_zero () from /usr/lib/i386-linux-gnu/libgmp.so.10
#2 0xb77deb33 in __gmpz_powm_sec () from /usr/lib/i386-linux-gnu/libgmp.so.10
#3 0xb78bbc3b in ?? () from /usr/lib/python2.7/dist-packages/Crypto/PublicKey/_fastmath.so
#4 0x081949c1 in PyEval_EvalFrameEx ()
#5 0x08194eec in PyEval_EvalFrameEx ()
#6 0x08194eec in PyEval_EvalFrameEx ()
#7 0x0819af70 in PyEval_EvalCodeEx ()
#8 0x0819bb03 in PyImport_ExecCodeModuleEx ()
#9 0x0814bd40 in ?? ()
#10 0x0814c6d4 in ?? ()
#11 0x08103146 in ?? ()
#12 0x0814cfe6 in ?? ()
#13 0x08096a0e in ?? ()
#14 0x081287ef in PyObject_Call ()
#15 0x08128c59 in PyEval_CallObjectWithKeywords ()
#16 0x08196e17 in PyEval_EvalFrameEx ()
#17 0x0819af70 in PyEval_EvalCodeEx ()
#18 0x0819c401 in PyRun_InteractiveOneFlags ()
#19 0x0819c735 in PyRun_InteractiveLoopFlags ()
#20 0x080a916e in PyRun_AnyFileExFlags ()
#21 0x080a9949 in Py_Main ()
#22 0x0805ea5b in main ()
(gdb)
----

[Legrandin (gooksankoo)]

It turns out your RSA modulus is even (so totally invalid) but mpz_powm_sec() really requires it to be odd:

http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation

If the modulus even, the gmp routine crashes (??).

I have some patches out already for making RSA import/construct more robust.
I added a small check in the Python code to catch the even modulus condition as early as possible:

https://github.com/Legrandin/pycrypto/commit/3b26fe526aef21512ab3a63f87d9c9983b767f2b

In that way, it is not necessary to modify the C mode.

The other patch already checks that the following components are prime and that automatically covers the even modulus condition:
 * p,q component in RSA (private key)
 * p modulus in DSA
 * p modulus in ElGamal

[Frank (frank-aune)]

Yes, you are correct. The RSA keypair was generated by a smartcard, and apparently due to optimization the card uses negative modulus values. Somehow this was fubar'ed on the client side, triggering the above behavior. I've leftpadded the modulus with zero now, in order to always get a positive number and it seems to have fixed the problem.

Good job on the latest pycrypto activities btw! :-)