Skip to main content
6 of 8
Polish
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

if I use $e=7$ (or another coprime like $11$) I can't compute $d$

You can use $e=7$. When $n$ is squarefree, a private exponent $d$ will work if (not: only if) $e\;d\equiv1\pmod{\phi(n)}$, that is by definition when $e\;d-1$ is divisible by $\phi(n)$. There are solutions to that if and only if $e$ is coprime with $\phi(n)$. The textbook systematic way to find such $d$ is the Extended Euclidean Algorithm. See there for a more efficient and easier to implement variant; or there for a "binary" variant.

Note: When $n$ is squarefree, $e\;d\equiv1\pmod{\lambda(n)}$ (where $\lambda$ is the Carmichael function) is the necessary and sufficient condition for $d$ to work in RSA. That simplifies computations of $d$, typically leads to a smaller $d$, and is required by some RSA standards including FIPS 186-4. When $n$ is the product of distinct primes $p$ and $q$, $\lambda(n)$ can be computed as$$\lambda(n)=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}$$

Can I pick $e=3$, even if it isn't coprime with $\phi(n)$?

No. It is required that $e$ is coprime with $\phi(n)$ [equivalently: that $\gcd(e,p-1)=1=\gcd(e,q-1)$ ] in order to insure unique decryption of ciphertexts. Otherwise, there will be multiple plaintexts $m\in[0,n)$ leading to the same ciphertext $m^e\bmod n$. In your case $(n,e)=(77,3)$, for example, $m=4$ and $m=15$ would lead to the same ciphertext $64$.

picking $e=p$ or $q$ seams wrong

For large $n$, it would be bad to choose $e$ equal to a factor of $n$ (or with any other approximate relation between $e$ and a factor of $n$) since that would allow factoring $n$. But when one deliberately illustrates RSA with a toy $n$ such as $n=77$ which is trivial to factor, choosing $e$ equal to one of the factors is a non-issue. Still, one could use $e=13$ to avoid that special case.

fgrieu
  • 145.6k
  • 12
  • 319
  • 611