5
$\begingroup$

Consider the standard RSA-algorithm: We have chosen two primes $p$ and $q $ such that $n:=p \cdot q$ and computed $\varphi(n)$. We now need to choose the public key $e$ such that

$$1<e<\varphi(n) \text{ and } gcd(e,\varphi(n)) = 1$$

If I am not mistaken there should be $\varphi(\varphi(n))-1$ many possible $e$'s ; we have to add $-1$ since we want to exclude $e \ne 1$.

Is there a "clever" algorithm to find all possible $e$'s other than to apply Euclid's algorithm on all numbers below $\varphi(n)$ and checks whether they are coprime to it?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ In practice people choose $e=3$ or $e=2^{16}+1$, which are prime and thus surely relatively prime to $\phi(n)=(p-1)(q-1)$. $\endgroup$
    – Henno Brandsma
    Nov 2, 2018 at 20:11
  • $\begingroup$ then $e^2$, too. $\endgroup$
    – kelalaka
    Nov 2, 2018 at 20:35
  • $\begingroup$ @HennoBrandsma: not necessarily; if p and q are only required to be primes, p-1 and q-1 could easily have factorization including 3 (fairly likely) or F4 (less likely but possible), or pretty much any other small prime. Instead RSA keygen normally fixes e first, and then searches for p,q primes of the desired size with the additional requirement that p-1 and q-1 are coprime to the given e; see e.g. B.3.3 in FIPS186-4 (or -3). $\endgroup$
    – dave_thompson_085
    Nov 3, 2018 at 8:19
  • $\begingroup$ @dave_thompson_085 $p$ and $q$ are usually chosen such that $p\pm 1$ and $ q\pm 1$ contain no small prime factors, either. $\endgroup$
    – Henno Brandsma
    Nov 3, 2018 at 8:56

1 Answer 1

Reset to default
4
$\begingroup$

We know that $\varphi(x) \ge\sqrt{\frac{x}{2}}$. The size of $\varphi(n)$ is roughly the same of $n$, so $\varphi(\varphi(n))-1$ is still a intractably large number. This means finding all possible e's is infeasible because there are too many. No matter what algorithm you use, there is no way you can find all of them in polynomial time (in the security parameter).

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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