9
$\begingroup$

I am looking at why certain public keys in RSA can't be used, such as:

  • 2 and all other even numbers (since $\gcd(\phi,e)$ must equal 1)
  • 1 (since the cipher text would equal the message)
  • 0 (since the cipher text would be 1. Also because 0 has no multiplicative inverse)

Let's say we have a message $m = 10, e = -3, N = 55$ then encrypting the cipher text would be: $m^{-3} = \frac 1 {1000} \mod 55$. Can we only use integers when writing in terms of a modulus? Why can the public key exponent not be negative?

(Perhaps this is more of a maths question....Sorry)

Edit: Also, why can’t the public key exponent be greater than $\phi(N)$?

$\endgroup$
1

4 Answers 4

12
$\begingroup$

Why can the public key exponent not be negative?

Technically, it can be. There's just no point to using such negative exponents in general, since for every valid negative RSA exponent, there is an equivalent positive one that is easier to calculate with.

Specifically, for any exponent $e$, message $m$ and modulus $n = pq$, changing $e$ by any integer multiple of $\lambda(n)$ $=$ $\operatorname{lcm}(p-1, q-1)$ does not affect the ciphertext $c = m^e \bmod n$. This is because $\lambda(n)$ is the exponent of the multiplicative group of integers modulo $n$, and therefore $m^{\lambda(n)} \equiv 1 \pmod n$ for all $m$ coprime to $n$. Thus, $$m^{e+\lambda(n)} = m^e \cdot m^{\lambda(n)} \equiv m^e \cdot 1 = m^e \pmod n.$$

(If $m$ happens to share a factor with $n$, then $m^{\lambda(n)} \not\equiv 1 \pmod n$. However, since RSA moduli are squarefree, it is true that $m^{\lambda(n)+1} \equiv m \pmod n$ for all $m$, and so the conclusion $m^{e+\lambda(n)} \equiv m^e \pmod n$ still holds. In any case, as noted below, having $m$ share a factor with $n$ is incredibly unlikely for RSA moduli of practical size.)

Let's say we have a message $m = 10, e = -3, N = 55$ then encrypting the cipher text would be: $m^{-3} = \frac 1 {1000} \mod 55$. Can we only use integers when writing in terms of a modulus?

Yes, we only use integers in modular arithmetic.

But that turns out not to be much of a loss, since we can still calculate modular inverses, i.e. solutions $x$ to the equation $x \cdot m \equiv 1 \pmod n$. For example, for $m = 8$ and $n = 55$, we have $7 \cdot 8 = 56 \equiv 1 \pmod{55}$, so $7$ is the inverse of $8$ modulo $55$. Finding such modular inverses can be efficiently done using the extended Euclidean algorithm.

Alas, this doesn't quite work for all numbers. For example, $10$ has no inverse modulo $55$, since $10$ and $55$ are not coprime; they both share the factor $5$. But for real-world RSA moduli, which are products of two very large primes, it's extremely unlikely that you'll ever randomly stumble across another number that shares a factor with the modulus. (And if you do, you've just factored the modulus by pure luck!)

Thus, if we really wanted to use RSA with negative exponents $e < 0$, we could just assume that any messages will almost surely be invertible modulo $n$, and calculate $$m^e = m^{-1 \cdot -e} \equiv (m^{-1})^{-e} \pmod n,$$ where $m^{-1}$ denotes the inverse of $m$ modulo $n$. As long as $e$ is otherwise a valid RSA exponent (i.e. coprime to $\lambda(n)$, and not equivalent to $1$ modulo $\lambda(n)$), the math would work out just fine.

But there's still no point in using such negative exponents, since we can always convert any negative (or over-large) exponents into equivalent positive ones in the range $2 < e < \lambda(n)$ just by adding a suitable integer multiple of $\lambda(n)$ to them. This does require knowing $\lambda(n)$, which implies knowledge of the factors of $n$, and thus of the private key. But the code that generates the key will know that anyway, and can thus ensure that the exponents lie in the proper range.

In particular, while it would be mathematically possible to work with negative RSA exponents, I'm not aware of any practical RSA implementations that would include the extra complexity needed to support them.

Also, why can't the public key exponent be greater than $\phi(N)$?

Technically, it can be, but again, there's no point in using exponents larger than $\lambda(n) < \phi(n)$, since using an over-large exponent would just waste CPU time for no good reason, compared to using an equivalent smaller exponent.

In particular, some RSA key generation standards require the exponents to be positive and less than $\lambda(n)$, and most RSA implementations will only accept positive exponents (and may require them to be less than $n$). See this related question for more information.

$\endgroup$
2
  • 1
    $\begingroup$ $m^{\lambda(n)} \equiv 1 \pmod n$ for all $m$ is not correct. This is correct when $gcd(m,n)=1$.For example: $10^{20} \equiv 45 \pmod 55$. $\endgroup$ Jan 9, 2016 at 12:11
  • $\begingroup$ Good point, @Meysam. I've edited my answer to correct that. $\endgroup$ Jan 9, 2016 at 13:23
4
$\begingroup$

If $gcd(m,N)=1$ then $m^{\phi(N)}=1\bmod N$. So $m^{t\phi(N)+k}=m^k\bmod N$.

this is a reason that exponent is not greater than $\phi(N)$. Now suppose that $e$ is a negative integer number and $gcd(m,N)\neq1$:

$m^e={(m^{-1})}^{|e|} \bmod N$ but we can't compute $m^{-1}$.

For computing $m^e$ we can compute $m^{e+\phi(N)}$ which exponent is positive.

Also if $gcd(m,N)\neq 1$ we can factor $N$.

$\endgroup$
2
  • $\begingroup$ $\gcd(m,N) > 1$ is never allowed in RSA, everything relating to that isn't relevant. $\endgroup$ Jan 9, 2016 at 14:38
  • 1
    $\begingroup$ $m$ is an arbitrary message so $gcd(m,N)>1$ is allowed. But since $p,q$ are very big, this happen with a very very small probability that approximately is $0$. $\endgroup$ Jan 9, 2016 at 14:59
3
$\begingroup$

Having exponent equal to $e+k\phi(N)$ where $k$ is an integer is equivalent to having it equal to $e$ so you'd be duplicating a modulus, thus duplicating a key.

And in your equation, strictly speaking you should write $m^{-3}=1000^{-1}\bmod55.$

$\endgroup$
3
  • $\begingroup$ No, strictly speaking he should write $\;\;\; m^{\hspace{.02 in}-3}\hspace{-0.04 in} \equiv 1000^{\hspace{.03 in}-1} \: \pmod{55} \:\:\:\:$. $\;\;\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Jan 9, 2016 at 2:12
  • $\begingroup$ @RickyDemer Thank you, but why can $e$ not be negative? $\endgroup$ Jan 9, 2016 at 2:42
  • 1
    $\begingroup$ For your example, e.g., $e=-7$ and $e=48$ are equivalent since $-7+55=48.$ For simplicity positive $e$ is used since every negative $e$ has a corresponding positive $e$ and wouldn't add a "new key". $\endgroup$
    – kodlu
    Jan 9, 2016 at 4:31
3
$\begingroup$

Theoretically, you could actually have RSA with negative public exponents, because it is perfectly possible to compute $m^{-1} \bmod N$ for composite moduli $N$, using the Extended Euclidian Algorithm.

In practice, it would however be completely pointless, since it would make the public key operation significantly less efficient, without any security benefits at all. For the same reason, having public exponents greater than $\phi(N)$ would just make the public key operation less efficient, without any benefits.

$\endgroup$

Your Answer

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

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