Given enough RSA signature values, is it possible to determine the public key value? Given enough RSA signature values, is it possible to determine which public key is required to verify the values?

Could there be enough information to establish which key is required? Is there anything in the RSA scheme to retrieve the modulus, assuming the public exponent can be guessed?

Only padded RSA for signature generation with PKCS#1 v1.5 padding or PSS padding may be considered, not raw/textbook RSA.



This question is related to this one asking about the same question for RSA encryption.
First, assuming any padding, the answer given by fgrieu to your related question still holds. You can associate public keys with signatures by looking at which signatures are consistenly (minimally) smaller than the modulus.



The second method, as suggested by poncho in the comments of your related question and the comments of this post cleverly uses small prime factoring to find $N$. I put this here, so it doesn't look "tagged-on" at the end of the post. The idea is the same as in the third method below, but with a clever twist. Where I collect enough samples to get a decent probability that there's on coprime pair of $t_i$ values, he suggested to take much less pairs and calculate the GCD of all $t_i$. This is $\gcd(t_1,...,t_k)=\gcd(r_1N,...,r_kN)=N*\gcd(r_1,...,r_k)$, where $\gcd(r_1,...,r_k)$ is likely to be a factor which is small enough ($&lt;2^{128}$) to be factored out by methods which can find small primes efficiently, like ECM, yielding the desired $N$, as the largest factor.



The third method is a bit more specialized. It's basically a re-statement of my previous answer to a similar question and goes into a little more detail than poncho's answer to your related question, while standing on similar feet.

Assumptions

It needs to be assumed that you have a set of message-signature pairs, it needs to be assumed that the padding is deterministic (i.e. something like PKCS#1 v1.5) and that the public exponent is known or can be brute-forced easily.

Method

Assume you're given the public RSA exponent $e$, the set of message-signature pairs $\mathcal S = \{(m_1,\sigma_1),...,(m_k,\sigma_k)\}$ with $|\mathcal S|=k$ and the padding function $\operatorname{Pad}(m)$. Note that knowledge of the padding function implies knowledge or a good estimate of the size of the modulus.

The first step is to reduce this problem from one with a complex padding scheme to one of simple raw RSA signatures. For this, we apply $\operatorname{Pad}(m)$ to each message $m_i$ in $\mathcal S$ and and replace the unpadded $m_i$ with the padded $m_i'$ for the set $\mathcal S'$.

Now observe, that as per the normal verification process, $(m_i')^e \equiv \sigma_i \pmod N \forall 0&lt;i\leq k$. This can be rewritten as $(m_i')^e = \sigma_i + r_i * N$. As we know $m_i', e, \sigma_i$, we can calculate $t_i=(m_i')^e-\sigma_i=r_i * N$. Now we observe that all $t_i$ share one common factor: $N$, which we can recover (with a given probability) by calculating the pair-wise greatest common divisor of all $t_i$. The smallest result is likely our $N$. The fancy writing for this would be: $N=\gcd(t_1,...,t_k)$. Once we have a guess for $N$, we can confirm it by checking if all signatures are valid, i.e. if all equations $(m_i')^e\equiv \sigma_i\pmod N$ hold.

Success Probability

The first thing to observe or assume is that the values of $r_i$ are random non-zero integers. Due to their large size (beyond $2^{100,000,000}$), we will model them as randomly distributed numbers. Next, we observe that we found the modulus, if $\gcd(r_1,...,r_k)=1$ holds, i.e. if the set is co-prime. As we modeled the integers randomly, we can use the standard approximation for the probability that $k$ random integers are co-prime which is $1/\zeta(k)$ where $\zeta(x)$ is the riemann zeta function. So the probability that our guess $N'$ for $N$ is correct, is equal to the probability that all $r_i$ are co-prime and thereby:

$$\Pr[N'=N]=1/\zeta(k)$$

This formula can be used to retrieve the number of pairs neccessary to get a good probability for finding the correct $N$. The probability is at $99.99%$ with $k\geq 14$.