Puncte:1

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

drapel jm

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?

kelalaka avatar
drapel in
Puteți avea [mai mult de o cheie privată pentru RSA](https://crypto.stackexchange.com/q/87583/18298) și $\lambda$ oferă întotdeauna cel mai mic $d$ de la $\lambda(n)| \phi(n)$ prin definiție. Cel mai mic = mai puțin calcul.
fgrieu avatar
drapel ng
@kelalaka: este îndoielnic că „mai puțin calcul” este adevăratul motiv. Când performanța contează, $d$ nu este folosit deloc. Și când se folosește $d$, diferența medie este, cred
kelalaka avatar
drapel in
Da, foarte mic, și totuși poate produce puțin avantaj de timp. Pariul tău este unul bun.
dave_thompson_085 avatar
drapel cn
Dupe https://crypto.stackexchange.com/questions/1789 https://crypto.stackexchange.com/questions/12710 https://crypto.stackexchange.com/questions/29591 https://crypto.stackexchange.com/ întrebări/33676/ https://crypto.stackexchange.com/questions/54280/ https://crypto.stackexchange.com/questions/68873/ https://crypto.stackexchange.com/questions/70624/ și o problemă secundară sau comentați în multe altele. Notă pentru RSA p și q trebuie să fie ambele impare, astfel încât p-1,q-1 nu poate fi coprim și lambda nu poate fi egal cu phi.
Puncte:3
drapel jm

Deci, după căutare, se dovedește că a doua versiune este cea dată în lucrarea originală RSA, „A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”.

Presupun că prima metodă este pur și simplu standardul de atunci. După cum se arată într-un comentariu $\lambda(n)$ va fi întotdeauna mai mic sau egal cu $\phi(n)$. În RSA, după cum a subliniat Dave Thompsons, $\lambda(n) \neq \phi(n)$. $\lambda(n)$ poate duce la calcule mai rapide (?), dar ceea ce m-a interesat a fost de unde a venit a doua versiune și provine din documentul original RSA.

fgrieu avatar
drapel ng
Da, a doua versiune (cu $\varphi$ sau $\Phi$ sau $\phi$) este prima publicată cronologic. Observați cealaltă (cu $\lambda$) se subdivizează în $e\,d\equiv1\pmod{\lambda(n)}$ cu $0

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.