# RSA: deduce the public key from message & signed message [duplicate]

In RSA, is deducing the public key from the (message, signed message) pair possible? If so, how can it be done?

• If this is only information, the simple answer is no? But, in general, the public keys are 3, 5, 17, 257, and 65537 – kelalaka Oct 5 '18 at 21:03
• @kelalaka: the public key in generally taken to be the pair $(N,e)$. – fgrieu Oct 5 '18 at 21:51
• @fgrieu So, there is no way to find $N$ here, you say. – kelalaka Oct 5 '18 at 21:55
• One idea: of you're able to observe many signed messages, then you could take the maximum of them get a lower bound on $N$. – rikhavshah Oct 5 '18 at 22:03
• Could my question here be considered a dupe? – Maarten Bodewes Oct 6 '18 at 0:11

With only one (message, signature) pair $$(M,S)$$, it is not known how to recover the public key $$(N,e)$$. However, that can be done

• with two distinct pairs $$(M_0,S_0)$$ and $$(M_1,S_1)$$,
• and 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).

In a deterministic RSA signature padding schemes, the signature of message $$M$$ is computed by transforming it into a padded message representative $$\widetilde M$$, then computing the signature $$S={\widetilde M}^d\bmod N$$. The signature verification step verifying alleged $$M'$$ against $$S$$ computes $$\widetilde{M'}$$ and checks $$S^e\bmod N=M'$$. Computation of the padded message representative typically involves hashing. Textbook RSA has $$\widetilde M=M$$, while hash-then-textbook-RSA has $$\widetilde M=H(M)$$ for some hash function (the fist is unsafe, and the second is only safe for very wide hash).

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 $$\widetilde{M_i}$$ (for RSASSA-PKCS1-V1_5, we need the size of $$N$$ in octets, which is the same as that of the $$S_i$$ if expressed as fixed-size octet strings, or typically given by the highest $$S_i$$ otherwise).

We are now trying to solve a system of two equations with only unknown $$N$$: $$S_i^e\bmod N=\widetilde{M_i}$$. In each, if we got $$e$$ right, $$N$$ is a divisor of $$(S_i^e-\widetilde{M_i})$$.

$$N$$ can often be found by computing the Greatest Common Divisor of the two $$(S_i^e-\widetilde{M_i})$$. In most of the remaining cases, pulling out a few small factors from this GCD by trial division of small primes will reveal $$N$$. For random parameters, this almost always works. The only implementation difficulty stems from the size of $$S_i^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 GCD), we can detect that and try another $$e$$.

Note: at least for textbook RSA, it is possible to intentionally pick messages making pulling out small factors difficult. In that case, Pollard's rho or ECM (as in GMP-ECM) could come to the rescue.

Note: I have included a small demo in Java as invisible text at the end of the source of the present answer.

• thanks you, this was what I was looking for. Addressing the comment from @kelalaka, if the public key and the private key are interchangeable, would this be a viable attack to find the private key as well? – B.Li Oct 5 '18 at 22:19
• @B.Li could you update the quesion as pairs etc, so that one can deduce that you have multiples. – kelalaka Oct 5 '18 at 22:25
• @B.Li interchangeable means you can swap them in the beginning. nothing special, but the pk must be random, too. – kelalaka Oct 5 '18 at 22:31
• @fgrieu is there a code example for this around somewhere? – kelalaka Oct 5 '18 at 22:37
• Is there a particular reason why a Fermat prime is normally used for $e$? – B.Li Oct 6 '18 at 16:56