Given a private key with primes that differ by a large order of magnitude, RSA decryption effectively stalls

[mjpieters]

The author of this Stack Overflow question tried to experiment with weak private keys by using a very, very small value for one of the primes in the key. In the following private key, q has been set to 5:

-----BEGIN RSA PRIVATE KEY-----
MIIFJAIBAAKCAQEAzdoCzKqtgJs+n66H89khIqgqg4LxAq56FkU0wP9TgcStI0R8
lswVoAep0bC+2Hs1gwwZJBPH1UHn9NcmYHcxUCboemEZGCdfw+3jBGd7EPJx02Av
0QVSHmKTyOh9e/Cc1z+lyI4042T3Tm2Q6xFQOtunzSKrgViN2zMD2sCar7lBM6Kd
5ckBiHs/etgT+mZAW7QkSNb/jOz3Uuhw4z7vey5YewtekfVpGcdkI/XsyVc7TSqk
iBLd8bNyE0XebAp27yB7/RoUf2yPQ0jrIk4IRk7ecWESSgeDswa28a7Np8OGPGtu
Z2ev4SQOQEbbXFEofIjDcxJZvhvVPiNeVI9WIwIDAQABAoIBAQCRUVIHAbllJjLz
SKMY9Zl6sC4y+mdn3Gi7YZrek/oNJenD3j+ShMgCjOZiug8MuKdyHg9+QUIhvidT
1+TaCWRHXPAvVG4B3lBKLgLEKfkRLm93jlnmVYc/HZmOWItQYokvoVlIJEiALqQw
oKn2B+bg/6eM6bWBCu6f/q3xHP6v0ziM890O4vNK630VgrlRXCKBM/S/2jPVXIOZ
HhYMyXHUcUc56MpkgSAmeEF6HjKzGZP3fOvH7VAlphp/ZVduYrf+eRD0zOOjgK0y
DQvqaVCJS0WlBg3ozNBs7yFYdzpSY3XwuTZ0yrG4+I16ISTbt6W8V4Y1rPXfF7u8
Ssn3KXWpAoIBACkrmiju74AfDIZWGzDFBqCICICzyc1WGGrapCaZdxn0IqCnTB4o
0SABiF0jWV5/CrPPODpqWyqmx/3EoUZ+PRAHyBh50dGheY2V+jQUsjaW45Cs1l0B
EGx6HY6U5eWWhcSmVFtPpC16l9x8UC8DdnIr7lw6Ik0RtfijzZImhVZYQD2G7GEo
M4GyP+VeamVHpni9oNteMxwvZKoufPo/yX8JROVorIOXe2uORzpkYo6rC9w7uoGd
X5a9fTcN+UjO5JY5smXSBBl8HKcOlW1CznR2LH0Tag7OTYo0iv0i9e5aTgwVfHsU
vMagz6Z0kkWp1OW08+PQeFk4xD+grHdP3gcCAQUCggEAFc6DjDTq5MkNYEZRhqaF
mRgUsN8J/9ofetGuaseUv0mB4ehbOApUoohNS1AC8TuHVrBmzwIwocnPWooBBo6t
F0WX5eb4jPnjoWwUJ+vibWnExYfWz1JV+a9A4pnZn5734a5cNjVb977cmyu5aP2D
invceDtOmdXMthNFOqlurMp31F8X62pYxdS9ZWd6IYUvFvsSLb+agM5VmpKfHgoV
V1V4ia7E2bqt481ryvELBxhwYsm8QxUxYW2i2jtrk/YKO8v5w1bXVwxXPOFLoqDl
K+jALcvPvGHnzlGAYQ5Yh1SLzHjBA4x7ZRYehsNuCronCziqijuM021u/WjEkTnb
lwIBAQKCAQAg766HJYxmfz04ROKNamuzoAbNXKFxEa0iSINSFF9H9oIaH3AYIKdM
zgaw6RRLmNVcpcaVIeKIhWzLA7Q4ZP2mbKATlKfa55RxRMgpqigrq+lAikUXNA0j
lORyELfq3tFqHqniphzxLt/jlqaMAsUoIyUWlOg9p8TG6XFBuGqrecz+BYnnU1xn
wcy3fruEOVH6MU18S1wWjFCIJTDIMweY1Dcd7VbPrGK8cdKVHRulVaMWli7OF3+r
ysqScZQ6Px1E+vUeQZzhMBbsC6q9zwuQXon9qSGlcdehw6JkG/fx4dgJqsn8EJcF
TXLrkHUEh92EkMMcpsatxwNmGiOSpks5
-----END RSA PRIVATE KEY-----

The first prime (p) is a 617-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)

While this is otherwise a terrible idea, this key triggers a catastrophically slow while loop in the PyCryptodome implementation of step 3 of the RSA decryption algorithm:

pycryptodome/lib/Crypto/PublicKey/RSA.py

Lines 158 to 165 in efdb406

	# Step 3: Compute m' = c'**d mod n (ordinary RSA decryption)
	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
	h = (h * self._u) % self._q
	mp = h * self._p + m1

Because q is so small but p is a 617-digit prime number, m1 is a 616-digit integer, and m2 is 3, and so h is a negative 616-digit integer. The while h < 0: h += self._q loop is going to take a very, very, very long time (abs(h // self._q) is itself a 615 digit number). This is going to very long time. Adding a small IntegerGMP(5) value to a 616-digit IntegerGMP() value 1 million times already takes nearly 6 seconds on my aging MacBook Pro:

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

10 ^ 609 times that time results in a runtime that takes 607 digits just to express the number of centuries we'd have to wait.

The while h < 0: h += h loop could trivially be replaced with a modulus operation, however; Python's % operator produces the remainder with the same sign as the divisor. So when I replace the while h < 0: loop with a modulus operation the result is almost instantaneous:

if h < 0:
    h = h % self._q   # or h %= self._q

The cost of a single % operation is about the same as addition (timeit takes 6.428032868000173 seconds for a million repeats on the same aging laptop), but it only has to be executed once. The time taken when q is a large prime with comparable magnitude barely increases.

[mjpieters]

And to note the security implications: in a scenario where code using PyCryptodome accepts arbitrary private keys, this could be used to DOS that system.

[Legrandin]

Thanks, initial fix in 7187ffd.

[Legrandin]

Fixed in version 3.9.4.