RSA key generation: why use lcm(p-1, q-1) instead of the totient ϕ(n)?

Élise Navennec

2/12/23, 6:58 PM

As far as I can see, generating a private key from two prime numbers p and q, having calculated n = pq, starts with calculating λ(n) = lcm(p-1, q-1). This is the detailed explanation given in the wikipedia article for RSA, it's also the implementation I've found in most Python cryptography libraries, and, searching through the openssl source code, it's also how they seem to do it, so I'd say this looks like the standard.

So my question is, why do some implementations appear to use ϕ(n) instead, which is simply (p-1)(q-1)? I understand that you can calculate λ(n) = ϕ(n) / gcd(p-1, q-1), so I suppose these two can be equal if p-1 and q-1 are coprime, but what's with the two different implementations?

This way to generate the "private modulo" is used for example in the somewhat popular python program rsatool, it's also mentioned in this popular article detailing how RSA keys are generated, but my problem is, taking the two same prime numbers p and q, these two methods will not generate the same private key, so assuming the former is the proper, standard way, where did this other one come from?

258

0 + 0

rsa

public-key

key-generation

kelalaka

2/12/23, 7:01 PM

You can have [more than one private key for RSA](https://crypto.stackexchange.com/q/87583/18298) and $\lambda$ always provides the smallest $d$ since $\lambda(n)| \phi(n)$ by definition. Smallest = less calculation.

fgrieu

2/12/23, 7:11 PM

@kelalaka: it's doubtful that "less calculation" is the true reason. When performance matters, $d$ is not used at all. And when $d$ is used, the average difference is I think <0.2% for 2048-bit keys , and (unless special precautions are taken) much less than the random variation from one key to the other. My bets are on: $d\equiv e^{-1}\pmod{\lambda(n)}$ is necessary and sufficient for $d$ to work; and defining $d=e^{-1}\bmod\lambda(n)$ uniquely defines $d$ as the smallest positive working $d$, which is mathematically satisfying, and simplifies conformance testing.

kelalaka

2/12/23, 7:16 PM

Yes, very small, and still can produce little time advantage. Your bet is a good one.

dave_thompson_085

2/13/23, 1:09 AM

Dupe https://crypto.stackexchange.com/questions/1789 https://crypto.stackexchange.com/questions/12710 https://crypto.stackexchange.com/questions/29591 https://crypto.stackexchange.com/questions/33676/ https://crypto.stackexchange.com/questions/54280/ https://crypto.stackexchange.com/questions/68873/ https://crypto.stackexchange.com/questions/70624/ and a side issue or comment in many more. Note for RSA p and q must both be odd so p-1,q-1 cannot be coprime and lambda cannot equal phi.

Score:3

Crypto

Élise Navennec

2/12/23, 7:12 PM

So after searching, turns out the 2nd version is the one given in the original RSA paper, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems".

I assume the 1st method is simply the standard since. As pointed out by a comment $\lambda(n)$ will always be smaller or equal to $\phi(n)$. In RSA, as pointed by Dave Thompsons, $\lambda(n) \neq \phi(n)$. $\lambda(n)$ possibly leads to faster calculations(?) but what interested me was where that 2nd version came from, and it comes from the original RSA paper, turns out.

0 + 0

fgrieu

2/12/23, 7:20 PM

Yes, your second version (with $\varphi$ or $\Phi$ or $\phi$) is the chronologically first published. Notice the other (with $\lambda$) subdivides into $e\,d\equiv1\pmod{\lambda(n)}$ with $0<d<n$ ([PKCS#1](https://pkcs1.grieu.fr/#page=7)), or $d=e^{-1}\bmod{\lambda(n)}$ ([FIPS 186-4](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=62)).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: RSA key generation: why use lcm(p-1, q-1) instead of the totient ϕ(n)?

TH: RSA key generation: why use lcm(p-1, q-1) instead of the totient Ï(n)?

RO: RSA key generation: why use lcm(p-1, q-1) instead of the totient Ï(n)?

RU: RSA key generation: why use lcm(p-1, q-1) instead of the totient Ï(n)?

VI: RSA key generation: why use lcm(p-1, q-1) instead of the totient Ï(n)?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.