inconsistency in RSA algorithm when using pycryptodome

Question

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.

President James K. Polk · Accepted Answer · 2025-08-03 20:55:35Z

The error is in your belief that ...

... Since e and d are multiplicative inverses of each other with respect to f, ...

This is a common misconception with RSA. In fact, in PyCryptodome, d is the inverse of e with respect to Carmichael's lambda function of n, not Euler's totient function of n. You can, if you want, take d to be the inverse of e with respect to Euler's totient function of n, and it will work just fine in RSA. But by using Carmichael's lambda function, the value of d is a few bits smaller and thus a tiny bit more efficient to use, so this is what PyCryptodome and many other implementations of RSA use.

For RSA, Carmichael's lambda function is almost as easy to compute as Euler's phi function. Here is some Python code showing these calculations.

import math


N = 148502774403628390194611500709682347814667593710263804255157829583856187369359709690285563468375111786415727941281838364540498319732753028415238432642064018564768129734406037062641477861055248558990411663521667242748082850681361695820916286468764801272766079977549468298872839357850688001921905070150870021617

F = 148502774403628390194611500709682347814667593710263804255157829583856187369359709690285563468375111786415727941281838364540498319732753028415238432642063994175826236354417984972173597931150214536367983662042569355961801875348542016817518199738121181705454851577038738077546432331820850702935944555788782117440

D = 3786287874221628833060271941142911125529353972159943582788217876798211113616120434328141578912323768742993739941575982481376680422409348089969728845438894796344787140928803863554860738865651625260009135296914439478294793149354932137846389802769093381050561713735488167704149676139058582518170514697039795113

P = 12644301210276125955062852673893145078336308093529189288020587426377781795770169081395069044878276629331783016359362180011337579202434183256912567514342137

Q = 11744640683103862097027615206036759955686314334472289809866198854597551023908834316691661598741290681896617494370859146395688450634864802703601794573562041

E = 65537

car_lam = math.lcm(P - 1, Q - 1)  #  Carmichael's lambda function

assert (E * D) % car_lam == 1

If you prefer, you can perform this arithmetic with gmpy2 methods instead of native Python arithmetic.

Collectives™ on Stack Overflow

inconsistency in RSA algorithm when using pycryptodome

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related