[Python] inconsistency in RSA algorithm when using pycryptodome

I am using python3-pycryptodome version 3.9.0-150200.9.1 on openSUSE Leap version 15.6.

While using Crypto.PublicKey.RSA class, I noticed that generated RSA keys have some algorithmic inconsistency.

First, let me show you snippet of my code,

from Crypto.PublicKey import RSA
import gmpy2 as gm

zero = gm.mpz(0)
one = gm.mpz(1)

key = RSA.generate(1024)
p = gm.mpz(key.p)
q = gm.mpz(key.q)
n = gm.mpz(key.n)
d = gm.mpz(key.d)
e = gm.mpz(key.e)
f = gm.mul(gm.sub(p, one), gm.sub(q, one))
t, r = gm.t_divmod(gm.sub(gm.mul(e, d), one), f)

print("T:", t, "\nR:", r, "\n")
assert(r == zero)


Since e and d are multiplicative inverse of each other with respect to f, so the value of r should always be zero, but this assert randomly fails when I generate multiple keys this way. Any idea why?

Do note that however, the generated keys correctly encrypt and decrypt even if the above assert fails.

Here is an example output,

N: 148502774403628390194611500709682347814667593710263804255157829583856187369359709690285563468375111786415727941281838364540498319732753028415238432642064018564768129734406037062641477861055248558990411663521667242748082850681361695820916286468764801272766079977549468298872839357850688001921905070150870021617

F: 148502774403628390194611500709682347814667593710263804255157829583856187369359709690285563468375111786415727941281838364540498319732753028415238432642063994175826236354417984972173597931150214536367983662042569355961801875348542016817518199738121181705454851577038738077546432331820850702935944555788782117440

D: 3786287874221628833060271941142911125529353972159943582788217876798211113616120434328141578912323768742993739941575982481376680422409348089969728845438894796344787140928803863554860738865651625260009135296914439478294793149354932137846389802769093381050561713735488167704149676139058582518170514697039795113

P: 12644301210276125955062852673893145078336308093529189288020587426377781795770169081395069044878276629331783016359362180011337579202434183256912567514342137

Q: 11744640683103862097027615206036759955686314334472289809866198854597551023908834316691661598741290681896617494370859146395688450634864802703601794573562041

E: 65537

T: 1670

R: 142315158803477207269836021513445583322389777305669479077859586684528846228969721786523664990526148795315072610395095099351310889743888318897936831281977994418500143172983902264999698017352288930685984342790795632796726797209019432783454941415699465801060899427995457324315330984661648590313613532630916195880

Traceback (most recent call last):
File "./utils.py", line 226, in <module>
(n, f, d, p, q, s, k, u, e, g, h) = generate_rsa(1024, TYPE_CRYPTODOME, debug=True)
File "./utils.py", line 83, in generate_rsa
assert(r == zero)
AssertionError


I am expecting the assert in code snippet to be always true but it randomly fails.

Continue reading...