1
$\begingroup$

Let $n$ be the modular arithmetic, $p$ and $q$ the two large primes such that $n=p*q$ and $e$ the public exponent. Here they are two "simple" numerical questions:

  1. If $p = 13$ and $q = 17$, what is the range for exponent e?
  2. Let be $p = 7$, $q = 11$ and $e = 3$. What is the max integer that can be encrypted?

About 1), I know that $e$ needs to be relatively prime to $φ(n)=(p-1)*(q-1)$, but how can I determine the range?

About 2), is there really a threshold on the maximum integer I can encrypt with RSA?

$\endgroup$
  • 2
    $\begingroup$ Note about your example 2: if $p=7$, then $e$ can't be 3. $\endgroup$ – poncho Jan 30 '16 at 22:38
0
$\begingroup$

As explained on this page you have:

  1. $1 < e < \phi(n)$ so with the specific values you mentioned we have: $\phi(n) = \phi(p \times q) = \phi(p) \times \phi(q) = (p-1) \times (q-1) = 12 \times 16 = 192$ (see Euler's totient function definition)

  2. The threshold on the maximum integer you can encrypt is $n-1$ which is $76$ if $p=7$ and $q=11$. Note that if the integer in question is greater than $n-1$ you will not be able to decrypt your message.

$\endgroup$
  • $\begingroup$ About 2), encrypting $m$ means to compute $m^{d} modn$. So if $n=77$, and e.g. $m=77$, I can't encrypt $m$ because $77 mod77=0$ and so implicitly I am not encrypting $77$ but $0$? $\endgroup$ – Leonardo Jan 30 '16 at 22:23
  • $\begingroup$ @Leonardo: actually, the decryptor can't tell the difference between an encryption of $0$ and an encryption of $77$, so he can't tell which you meant. $\endgroup$ – poncho Jan 30 '16 at 22:26
3
$\begingroup$

what is the range for exponent e?

Actually, there is no required upper bound for $e$ (except that some implementations may reject ridiculously large values). The math behind RSA states that any $e$ that is relatively prime to both $p-1$ and $q-1$ will work, no matter how large it is. There might not appear to be a need for an $e > lcm(p-1, q-1)$ (as for any such $e$ larger than that, there is a smaller $e$ that acts equivalently). However, there are obscure cases where such $e$ arise; one possibility is some shared computation of the RSA key pair (where no one entity knows the factorization) could possibly generate such a huge $e$ (depending on how that shared computation works).

What is the max integer that can be encrypted?

Well, if you omit the padding, the largest value that can be encrypted is $N-1$, as Raoul722 states. However, it is rarely a good idea to omit the padding in RSA (and if you have to ask, you don't know enough to safely omit it).

$\endgroup$

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.