1
$\begingroup$

I've been reading on RSA for a while but there's something I still can't understand. When generating the key: once you find n = pq and φ(n), you choose a number d coprime with φ(n) and then you need to find e the inverse of d mod φ(n).

Don't you need to do that to know φ(φ(n)) and then use Fermat Little Theorem? If so you would need to find the factorisation of φ(n) = (p-1)(q-1) and therefore factorise (p-1)/2 and (q-1)/2. Isn't that potentially very long?

Thanks in advance

Gabriele

$\endgroup$
3
$\begingroup$

once you find $n = pq$ and $\phi(n)$, you choose a number $d$ coprime with $\phi(n)$ and then you need to find $e$ the inverse of $d \bmod \phi(n)$

Actually, what we usually do is: select $e$; then find primes $p$ and $q$ with $p-1, q-1$ coprime with $e$, and then find $d$ which is the inverse of $e \bmod \text{lcm}(p-1,q-1)$. But that doesn't answer your question.

Don't you need to do that to know $\phi(\phi(n))$ and then use Fermat Little Theorem?

I suppose we could select the primes $p$ and $q$ in a way so that we know the factorization of $p-1, q-1$.

However, we (typically) don't. Instead, we use the Extended Euclidean Method to find the needed inverse; that doesn't require us to know the factorization of $\phi(n)$ (or $\text{lcm}(p-1, q-1)$)

$\endgroup$
  • $\begingroup$ Perfect, that makes it much more clear! Thank you! $\endgroup$ – gcorso Apr 19 '17 at 21:42

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.