RSA exercises example

Question

I have doubts about this question

Consider the following textbook RSA example. Let be p = 7, q = 11 and e = 3. Give a general algorithm for calculating d and run such algorithm with the above inputs. What is the max integer that can be encrypted? Is there any changes in the answers, if we swap the values of p and q?

I tried to apply RSA in this way:

$p=7$ and $q = 11$ so $n=(pq)$ and $n=77$, therefore $$\phi(pq) = (p-1)(q-1) = (7-1)(11-1)= 60$$

Pick $e$ that is $<60$ and isn't coprime (which means I can't use $2,3$ and $5$)

So after that, I'm blocked, and my solution is to choose another coprime, for example $e=7$ in order to have public-key: $(n,e)= (77,7)$

But I'm wrong somewhere, because if I use $7$ (or another coprime like $11$) I can't compute $d$. In fact, for all numbers that I used, for example with $e=7$, if I pick $d=9$ I have $63$ that if I divided for $60$ I have $1$ with rest $3$.

So my questions are these :

• Am I wronging? (where?)
• As a request , can I pick 3, even if it isn't coprime? (because as I saw on theory, I need at least a coprime).
• pick $e= p$ or $q$ seams wrong.right?

Answer 1

Am I wrong? (where?)

Yes, there is a small mistake in the way you are computing $d$: you need to compute $d$ as being the inverse of $e$ modulo $\phi(n) = (p-1)(q-1) = 60$. So, if you pick $e= 7$ (since you cannot pick $e = 3$ because it would be coprime with $\phi(n)$), you need to compute its inverse modulo (which is typically done using Euclid's algorithm). As said in the comment, the modular inverse of $7 \bmod{60}$ is $7^{-1} = 43 \bmod{60}$.

As a request , can I pick 3, even if it isn't coprime? (because as I saw on theory, I need at least a coprime).

No, picking a value $e$ that is not coprime with $\phi(n)$ does not allow to guarantee unique decryption of ciphertexts.

Since this is not desirable, it is required that $e$ is coprime with $\phi(n)$, which in turn implies that $\gcd(e,p-1)=1=\gcd(e, q-1)$ when using RSA with $n=pq$ for $p,q$ two primes.

Picking $e=p$ or $q$ seems wrong, right?

Yes, because then you are literally giving away your private key, since anybody can see that $n \bmod e \equiv 0$, which means that $e$ divides $n$! And, let's say you set $e=p$, then it is easy to recover $q$ as well by computing $\frac{n}{e}=q$ and so anybody knowing your public key $(n,e)$ would be able to recover your private key $(p,q,d)$.

Answer 2

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, the necessary and sufficient condition for $d$ to work in RSA is: $e\;d\equiv1\pmod{\lambda(n)}$ (where $\lambda$ is the Carmichael function). That simplifies computation of $d$, and typically leads to a smaller one. $d=e^{-1}\bmod\lambda(n)$ 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 $$\begin{align}\lambda(n)&=\operatorname{lcm}(p-1,q-1)\\&=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}\end{align}$$

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.

What is the largest integer that can be encrypted?

In textbook RSA, plaintext and ciphertext space is the integer interval $[0,n)$. The largest integer that can be encrypted (and decrypts correctly) is thus $n-1$. Notice that it is always encrypted to itself, thus trivial to decipher. More generally, textbook RSA is insecure when directly used to encipher data. It is conjectured secure when $p$ and $q$ are large random secret primes, and a random $x$ in the plaintext space $[0,n)$ is enciphered.