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.