Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
2  
While not precisely a duplicate, at least my answer to this related question also answers yours. – Ilmari Karonen Jan 9 at 10:45
    
@IlmariKaronen thanks, this was really helpful! – Evelyn Jan 9 at 11:03
up vote 10 down vote accepted

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.

share|improve this answer
1  
$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$. – Meysam Ghahramani Jan 9 at 12:11
    
Good point, @Meysam. I've edited my answer to correct that. – Ilmari Karonen Jan 9 at 13:23

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

share|improve this answer
    
$\gcd(m,N) > 1$ is never allowed in RSA, everything relating to that isn't relevant. – Chris Peikert Jan 9 at 14:38
1  
$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$. – Meysam Ghahramani Jan 9 at 14:59

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

share|improve this answer
    
No, strictly speaking he should write $\;\;\; m^{\hspace{.02 in}-3}\hspace{-0.04 in} \equiv 1000^{\hspace{.03 in}-1} \: \pmod{55} \:\:\:\:$. $\;\;\;\;\;\;\;\;\;$ – Ricky Demer Jan 9 at 2:12
    
@RickyDemer Thank you, but why can $e$ not be negative? – Evelyn Jan 9 at 2:42
1  
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". – kodlu Jan 9 at 4:31

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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