# RSA exercises example

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?
• You find the inverse of $e$ according to $\phi(n)$ not according to $n$. The inverse can be calculated with ext-GCD. – kelalaka Nov 15 '19 at 18:50
• $7^{-1} = 43 \bmod 60$ see at Wolfram. You cannot choose 3 since the setup will not be a permutation. An example here – kelalaka Nov 15 '19 at 19:16
• is this homework? – kelalaka Nov 16 '19 at 8:18
• I'm studying computer security, I have an exam in a few months and I want to understand these topics before the exam (so I'm studying now). This question has already been asked in an old exam task (in 2015). @kelalaka – theantomc Nov 16 '19 at 9:01

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.

• What is the max integer that can be encrypted? is m<n (in my case 77)? – theantomc Nov 16 '19 at 13:25

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)$$.

• My problem continues to be that calculation of d ... I'm trying to understand The Euclidean Algorithm – theantomc Nov 16 '19 at 9:09
• @theantomc: you want to understand the Extended Euclidean Algorithm. See there for a more efficient and easier to implement variant. – fgrieu Nov 16 '19 at 9:19
• @fgrieu Ups, indeed, missing a "not". – Lery Nov 18 '19 at 15:14