3
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ If this is only information, the simple answer is no? But, in general, the public keys are 3, 5, 17, 257, and 65537 $\endgroup$ – kelalaka Oct 5 '18 at 21:03
  • 1
    $\begingroup$ @kelalaka: the public key in generally taken to be the pair $(N,e)$. $\endgroup$ – fgrieu Oct 5 '18 at 21:51
  • $\begingroup$ @fgrieu So, there is no way to find $N$ here, you say. $\endgroup$ – kelalaka Oct 5 '18 at 21:55
  • $\begingroup$ 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$. $\endgroup$ – rikhavshah Oct 5 '18 at 22:03
  • 2
    $\begingroup$ Could my question here be considered a dupe? $\endgroup$ – Maarten Bodewes Oct 6 '18 at 0:11
3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ – B.Li Oct 5 '18 at 22:19
  • $\begingroup$ @B.Li could you update the quesion as pairs etc, so that one can deduce that you have multiples. $\endgroup$ – kelalaka Oct 5 '18 at 22:25
  • $\begingroup$ @B.Li interchangeable means you can swap them in the beginning. nothing special, but the pk must be random, too. $\endgroup$ – kelalaka Oct 5 '18 at 22:31
  • $\begingroup$ @fgrieu is there a code example for this around somewhere? $\endgroup$ – kelalaka Oct 5 '18 at 22:37
  • $\begingroup$ Is there a particular reason why a Fermat prime is normally used for $e$? $\endgroup$ – B.Li Oct 6 '18 at 16:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.