# RSA numerical questions

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?

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

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.

• 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$? – Leonardo Jan 30 '16 at 22:23
• @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. – poncho Jan 30 '16 at 22:26

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