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$
  • $\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 '19 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 '19 at 19:16
  • $\begingroup$ is this homework? $\endgroup$ – kelalaka Nov 16 '19 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 '19 at 9:01
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)$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ My problem continues to be that calculation of d ... I'm trying to understand The Euclidean Algorithm $\endgroup$ – theantomc Nov 16 '19 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 '19 at 9:19
  • 1
    $\begingroup$ @fgrieu Ups, indeed, missing a "not". $\endgroup$ – Lery Nov 18 '19 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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What is the max integer that can be encrypted? is m<n (in my case 77)? $\endgroup$ – theantomc Nov 16 '19 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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