Decrypting message with purposefully weak private key hangs indefinitely

I'm having issues when generating a public key from a private key, which has been weakened deliberately, and attempting to encrypt/decrypt a message when using PyCryptoDome. The decrypt just seems to hang indefinitely.

Note: obviously this isn't my real private key. The following key is weakened, on purpose:

The following snippet is used to read the private key, derive a public key, encrypt a message and then decrypt it again:

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import Crypto.Util
from base64 import *

def encryptMsg(rsakey, message):
    cipher = PKCS1_OAEP.new(rsakey)
    ct = cipher.encrypt(message)
    return ct

def decryptMsg(rsakey, message):
    cipher = PKCS1_OAEP.new(rsakey)
    pt = cipher.decrypt(message)
    return pt

key = RSA.importKey(open('private.key').read())
testpk = key.publickey()
message = b64encode(encryptMsg(testpk, b"test message"))
print(message)
print(decryptMsg(key, b64decode(message)))

This seems to hang when calling decryptMsg().

Solution

You are giving PyCryptodome a private key with hugely disproportionate prime numbers, and the security of this key is essentially broken because of this. You note this in your question, but it is important here because PyCryptodome seems to make assumptions about the magnitude of the prime numbers.

To be secure, RSA public key encryption normally requires the use of two prime numbers that are close in magnitude:

For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but differ in length by a few digits to make factoring harder.

You appear to have weakened the key by making the second prime a single-digit value:

$ openssl rsa -in private.key -text -noout | sed '/prime1:/,/prime2:/!d;/prime2:/q'
prime1:
    29:2b:9a:28:ee:ef:80:1f:0c:86:56:1b:30:c5:06:
    a0:88:08:80:b3:c9:cd:56:18:6a:da:a4:26:99:77:
    19:f4:22:a0:a7:4c:1e:28:d1:20:01:88:5d:23:59:
    5e:7f:0a:b3:cf:38:3a:6a:5b:2a:a6:c7:fd:c4:a1:
    46:7e:3d:10:07:c8:18:79:d1:d1:a1:79:8d:95:fa:
    34:14:b2:36:96:e3:90:ac:d6:5d:01:10:6c:7a:1d:
    8e:94:e5:e5:96:85:c4:a6:54:5b:4f:a4:2d:7a:97:
    dc:7c:50:2f:03:76:72:2b:ee:5c:3a:22:4d:11:b5:
    f8:a3:cd:92:26:85:56:58:40:3d:86:ec:61:28:33:
    81:b2:3f:e5:5e:6a:65:47:a6:78:bd:a0:db:5e:33:
    1c:2f:64:aa:2e:7c:fa:3f:c9:7f:09:44:e5:68:ac:
    83:97:7b:6b:8e:47:3a:64:62:8e:ab:0b:dc:3b:ba:
    81:9d:5f:96:bd:7d:37:0d:f9:48:ce:e4:96:39:b2:
    65:d2:04:19:7c:1c:a7:0e:95:6d:42:ce:74:76:2c:
    7d:13:6a:0e:ce:4d:8a:34:8a:fd:22:f5:ee:5a:4e:
    0c:15:7c:7b:14:bc:c6:a0:cf:a6:74:92:45:a9:d4:
    e5:b4:f3:e3:d0:78:59:38:c4:3f:a0:ac:77:4f:de:
    07
prime2: 5 (0x5)

The prime1 (the p value) is a 'proper' large prime using 617 digits, while the second q prime is a single digit value, so p is about 10 ^ 616 times larger. Using this key then triggers a worst-case scenario in the way PyCryptodome handles RSA decryption.

During decryption the implementation is trying to make a negative number positive by repeatedly adding the second prime number:

m1 = pow(cp, self._d % (self._p - 1), self._p)
m2 = pow(cp, self._d % (self._q - 1), self._q)
h = m2 - m1
while h < 0:
    h += self._q

In the above code, the _p and _q attributes are the two prime numbers, and _d is the private key exponent

Because your given private key is using two prime number of such hugely disproportionate prime numbers (1 digit vs 616 digits), the value for m2 is 3, while m1 is a 616 digits short. As a consequence, trying to add q (5) to a negative integer 616 digits long will take a very long time. On my aging Macbook Pro laptop, the GMP wrapper used by PyCryptodome can add a small integer to that large integer 1 million times in about 6 seconds:

timeit("a + b", "from Crypto.Math._IntegerGMP import IntegerGMP as H; a = H(-529888206800322351142280698970509553244088870105926093960960600839997948364537263924658051221855219286822834908160253952313431263065035892252247530580840707934254014192645042780064071400938165792458671917549294961637063901428635522475550885330295366860440266592481901428697979715456902249133738633092402578072834537512045684962133176512203248846326955899359525113708331947304401283815041620003402445741404924361709787545141518988924507726836779489762118740731196007268258996956015186886831392340919980371282865371496239488099989353283964607756716132847721450221986689589881754517900556993453537792486255692015472770); b = H(5)")
5.970772444999966

To complete that while loop would have to iterate another 10 ^ 609 times and the total amount of time my laptop would take, would require 603 digits just to express the number of millions of years required. I don't expect the universe to even last that long, let alone my laptop.

It should just use a modulus operation; you can replace the while h < 0: h += self._q loop with a modulus operation here:

if h < 0:
    h %= self._q

This is Crypto/PublicKey/RSA.py, in def _decrypt(self, cyphertext):, line 162 in version 3.9.3. With that change decryption is again almost instant.

I've filed this as a bug with the PyCryptodome project (now closed as fixed) and the project released version 3.9.4 with the loop replaced by a modulus operation.

If you don't want to alter your installed copy of PyCryptodome and are blocked on this, you could switch to using the cryptography project, as it doesn't have this problem. PyCryptodome implements the RSA algorithms itself, while cryptography delegates decryption to the openssl library.