4
$\begingroup$

The PKCS #1 v2.0 specifications suggest using $\lambda(n) = \mathrm{lcm}(p-1,q-1)$. What is the benefit of choosing $\lambda(n)$ over $\varphi(n) = (p-1)(q-1)$ in RSA key generation?

$\endgroup$
7
$\begingroup$

Choosing $\lambda(n)$ rather than $\varphi(n)$ may result in a smaller private exponent.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ ... and as there are attacks against RSA with (too) small exponent, one couldn't detect that the exponent is too small if one just looks at the exponent one gets using $\varphi$ instead of $\lambda$. $\endgroup$ – j.p. Jul 7 '15 at 8:45
  • 4
    $\begingroup$ @fgrieu You're wrong about the "always": The calculation of the modular inverse is done with a smaller exponent by a factor of at least 2. But that does not necessarily imply, that the product $ed$ is smaller (it usually is). Small number example: $n=7\cdot 11 \Rightarrow \varphi=60; \lambda=30$. For $e=11$, we get that $d=11$ in both cases ($11 \cdot 11 = 1$ for both moduli). $\endgroup$ – tylo Jul 7 '15 at 14:09
  • 1
    $\begingroup$ @tylo: very right. My mistake. I wish I could edit (rather than delete) wrong comments. $\endgroup$ – fgrieu Jul 7 '15 at 16:55
  • 1
    $\begingroup$ @YehudaLindell : $\;\;\;$ (I don't know anything about that attack, but) I got the impression from j.p.'s comment that the attack works whenever the smallest $d$ is (too) small. $\:$ Using $\phi(n)$ instead of $\lambda(n)$ wouldn't let the key generation algorithm detect that. $\;\;\;\;\;\;\;\;$ $\endgroup$ – user991 Jul 8 '15 at 21:09
  • 1
    $\begingroup$ @RickyDremer I wasn't being precise. I wanted to focus on the fact that e=3 is fine security wise. $\endgroup$ – Yehuda Lindell Jul 9 '15 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.