Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 ($<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.
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.
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<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.
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$.
Note: This is a late answer, and uses the same principle as methods 2 and 3 in that other answer. The only difference is use of just two (message, signature) pairs, and demo code in Java within the answer's text to illustrate that this is enough for practical parameters.
With only one (message, signature) pair $(m,\sigma)$, it is not known how to recover the public key $(N,e)$. However, that can be done in practice with just two distinct pairs $(m_1,\sigma_1)$ and $(m_2,\sigma_2)$, assuming a known deterministic RSA signature padding scheme with appendix, including textbook RSA, hash-then-textbook-RSA, RSASSA-PKCS1-V1_5 (which is believed safe), and a few others (but not standard RSASSA-PSS, because the random padding gets in the way).
In a deterministic RSA signature padding scheme, the signature of message $m$ is computed by transforming it into a padded message representative $\text{Pad}(m)$, then computing the signature $\sigma={(\text{Pad}(m))}^d\bmod N$. The verification of alleged $m'$ against $\sigma$ computes $\text{Pad}(m')$ and checks $\sigma^e\bmod N=\text{Pad}(m')$. Textbook RSA has $\text{Pad}(m)=m$, secure padding scheme typically involve hashing.
The attack needs to guess $e$, but that's typically a small integer, often $e=F_i=2^{(2^i)}+1$ with $0\le i\le4$, or $e=37$, with $e=F_4=65537$ common in practice. We need to pad the two messages $m_i$ into their message representatives per the padding algorithm used by the signature scheme, giving $\text{Pad}(m_i)$ (for RSASSA-PKCS1-V1_5, we need the size of $N$ in octets, which is the same as that of the $\sigma_i$ if expressed as fixed-size octet strings, or typically given by the highest $\sigma_i$ otherwise).
We are now trying to solve a system of two equations $\sigma_i^e\bmod N=\text{Pad}(m_i)$ with only unknown $N$. In each, if we got $e$ right, $N$ is a divisor of $\sigma_i^e-\text{Pad}(m_i)$. It follows that $N$ divides the quantity $x$, that we can compute $$x=\gcd(\sigma_1^e-\text{Pad}(m_1),\sigma_2^e-\text{Pad}(m_2))$$
$N$ is $x$ with probability about $\frac6{\pi^2}\approx0.61$, by the argument on probability of coprimality of large random integers.
And in most of the remaining cases, pulling out a few small factors from $x$ by trial division of small primes will reveal $N$. It seems that for $k$ much less wide than $N$, we'd have to pull a factor larger than $k$ with probability about $$1-\frac6{\pi^2\displaystyle\prod_{\mathrm{primes}\ p\le k}\left(1-\frac1{p^2}\right)}$$ and that probability is only $\approx2^{-13.0}$ (resp. $\approx2^{-23.9}$) if we test divisibility by the 172 (resp. 82025) primes at most 10-bit (resp. 20-bit). Even better options pull the small factors using Pollard's rho or ECM (as in GMP-ECM).
For practical parameters, this almost always works. The only implementation difficulty stems from the size of $\sigma^e$, especially for $e=F_4=65537$ (Java's BigInteger gets impractically slow; GMP shines). Much larger $e$ would make the attack difficult.
If we make a wrong guess of $e$, the method fails (typically yielding a much too small $x$), we can detect that and try another $e$.
