# Why can an RSA signature be authenticated ONLY with the signer's public key?

I'm an undergraduate Math student currently taking a cryptology course. I have a question about the RSA signature authentication mechanism.

An RSA signature can be authenticated with the public key of the signer. However, I'm wondering why it can ONLY be authenticated with the signer's public key. Why can't it be mistakenly authenticated with someone else's public key?

Let me clarify with an example. Suppose two people use random texts $p_1$ and $p_2$ for their signatures. Their private keys are $d_1$ and $d_2$ respectively, and their public keys are $(e_1,n_1)$ and $(e_2,n_2)$ respectively. So, the signature of the first person is

$s_1 = {p_1}^{d_1} \mod n_1$

Now, I understand the Math that this signature can be authenticated with the first person's public key i.e.

${s_1}^{e_1} \mod n_1 = p_1$

However, how can we claim that the following is never true?

${s_1}^{e_2} \mod n_2 = p_2$

The probability of such a "collision" occurring randomly, with honestly-generated RSA keys, is extremely low. Mathematically justifying that assertion can be tiresome, but the idea is the following:

Let $s$ be a RSA signature, i.e. an integer of size $k$ bits for some $k$ (e.g. $k = 2048$). We consider RSA keys $(n,e)$ where $n$ is the modulus (of size $k$ bits) and $e$ is the public exponent, of size $r$ bits (in practice most people use $e = 65537$, i.e. $r = 17$; Windows' CryptoAPI cannot tolerate public exponents longer than 32 bits anyway). We want to estimate the probability that $s^e = m \pmod n$.

If $s^e = m \pmod n$ then $n$ divides $s^e-m$. $s^e - m$, as an integer, has size roughly $k2^r$ bits. That integer cannot admit more than $2^{r+1}$ distinct prime divisors of size $k/2$ bits. Even if $s^e-m$ is indeed the product of $2^{r+1}$ distinct prime integers of size $k/2$ bits, then there are only about $2^{2r+1}$ distinct products of two such primes which divide $s^e-m$. In other words, with $k = 2048$ and a given 32-bit exponent $e$, then there can be at most about $2^{65}$ (and in practice much fewer) modulus values $n$ such that $s^e = m \pmod n$. However, there are roughly $2^{2048-20} = 2^{2028}$ possible 2048-bit RSA moduli (products of two 1024-bit primes), a vastly bigger value. Thus, probability of collision is very low.

If we allow the public exponent to be large ($r = 2048$) then the answer is not as simple, because the computation above will yield a maximum number of matching moduli of about $2^{4097}$, which is completely exaggerated and not actually possible. In fact, for a given $e$, the integer $s^e-m$ will be large and may be assumed to be "typical", in that its factorization in prime factors will use factors of various sizes. The Hardy-Ramanujan theorem tells us that an integer of size $k2^r$ bits will be the product of, on average, $\log r$ distinct primes, yielding $(\log r)^2$ possible matching moduli. This leads to the same conclusion as before, albeit with an assumption of $s^e-m$ to be "typical" as far as factorization is concerned.

The above is for a random collision. However, we can ask ourselves whether such an occurrence could be forced. It turns out that it can be done. That is, consider a message $m$ (padded hash value) and a signature $s$ produced with a key pair $(n,d,e)$. We have $s^e = m \pmod n$ and $s = m^d \pmod n$.

Now, take $m'$ (another message, or the same as $m$, it works in both cases). Then one can compute a new RSA key pair $(n',d',e')$ such that $s^{e'} = m' \pmod {n'}$, and this can be done with $s$ and $m'$ alone (without knowing anything about the original key pair). The idea is the following: select random small prime integers $p_i$; for each small prime, compute $e_i$ such that $s^{e_i} = m' \pmod {p_i}$. This is a discrete logarithm which is very easy if $p_i$ is small. Once you have enough $p_i$, compute $n'$ as their product. The public exponent $e'$ is then such that $e' = e_i \pmod {p_i-1}$ for all $i$, so $e'$ is easily recomputed with the Chinese remainder theorem. At that point, you have $n'$ and $e'$, and you know the prime factorization of $n'$, so computing the private key $d'$ is straightforward.

Of course, this yields a rather weird RSA key: $n'$ is the product of small primes (but this won't be seen until someone actually tries to factor $n'$), and $e'$ is large (much larger than 32 bits). Whether a similar construction can work while keeping $e'$ small is not known. The discussion on random collisions above tells us that, "morally speaking", targeting a small $e'$ ought to be hard. Indeed, if we target a fixed $e'$, then $n'$ will have to be one of the $(\log r)^2$ (at most) possible values; since we should end up with $(n',d',e')$, then this means that this reconstruction yields a partial factorization of $s^{e'}-m'$, and we know that integer factorization is hard (indeed, RSA relies on it).

One alternate way to see it is the following: when trying to build $(n',d',e')$, we are actually trying to find factors of $s^{e'}-m'$ such that their product has the right size for a RSA modulus; we can do that if we are allowed to alter $e'$ and/or $m'$ so that $s^{e'}-m'$ is easy to factor. The more $e'$ and $m'$ are constrained, the harder the problem becomes. If $e'$ and $m'$ are fixed, then the problem seems as hard as breaking RSA. At which point the problem reaches the "infeasibility threshold" is not known.

See this article for a longer treatment of this subject. Bottom-line: digital signatures yield guarantees about a message for a given public key, not the other way round.

I can't remember anyone claiming that:

$s_1^{e2} \bmod n_2 = p_2$

is never true. However, there is a single value $s_2 = p_2^{d_2} \bmod n_2$; it would be a rather strange coincidence if that value just happens to be the value $s_1 = p_1^{d_1} \bmod n_1$

We don't say this can't happen, we just say it won't happen.

The only value that will decrypt to $p_2$ under $(e_2,n_2)$ is $p_2^{d_2}$, which we can call $s_2$. So, your problem comes down to asking what is the probability that $s_1=s_2$?

If we assume that they're random, and that the moduli are similar enough sizes that this is even a realistic possibility, then this is roughly $1/n$, which will be about $2^{-2048}$ for 2048-bit RSA: very small indeed.

However, as noted by CiC in the comments, the situation is rather different if the "attack" is deliberate. Since they possess the public/private keys, the signer can explicitly define $p_2=s_1^{e_2}$. This means that by choosing the appropriate public key, they can 'prove' that the signature is of either message $p_1$ or $p_2$. Now, constructing one in this way will not necessarily lead to a message $p_2$ that is sensible, allowing the recipient to spot the bad message, but with [significantly] more work, the signer may be able to construct two triples $(p_1,e_1,n_1)$ and $(p_2,e_2,n_2)$ such that each $p_i$ is a valid message and $$p_1^{e_1} \mod n_1 = p_2^{e_2} \mod n_2$$

• It doesn't come down to probability if the match is deliberate. For example to claim "I wrote this message, there is my signature on it". – CodesInChaos Dec 3 '13 at 19:37
• Good point - I hadn't seen that interpretation of the question. Will update my answer accordingly later today. – Cryptographeur Dec 4 '13 at 9:24
• – xagawa Dec 4 '13 at 14:56