2
$\begingroup$

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?
$\endgroup$
4
  • $\begingroup$ You find the inverse of $e$ according to $\phi(n)$ not according to $n$. The inverse can be calculated with ext-GCD. $\endgroup$
    – kelalaka
    Nov 15, 2019 at 18:50
  • $\begingroup$ $7^{-1} = 43 \bmod 60$ see at Wolfram. You cannot choose 3 since the setup will not be a permutation. An example here $\endgroup$
    – kelalaka
    Nov 15, 2019 at 19:16
  • $\begingroup$ is this homework? $\endgroup$
    – kelalaka
    Nov 16, 2019 at 8:18
  • $\begingroup$ 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 $\endgroup$
    – theantomc
    Nov 16, 2019 at 9:01

2 Answers 2

2
$\begingroup$

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

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

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.

$\endgroup$
1
  • $\begingroup$ What is the max integer that can be encrypted? is m<n (in my case 77)? $\endgroup$
    – theantomc
    Nov 16, 2019 at 13:25

Your Answer

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

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