Recovering The Public Key From RSA

In a blockchain world, we often use ECDSA for the signature. With this, we can perform a PKR (Public Key Recovery) from the signature, of which we can then take a hash of this to reveal the digital wallet identity:

Recovering a public key from an ECDSA signature in Python

But, can we do this with RSA, and where we want to recover the public modulus (N)? To recover it, we need two signatures (S1 and S2) and two messages (M1 and M2). The signatures are generated with:

Overall, Bob generates two random prime numbers (p and q), and creates a public modulus of:

Next Bob computes φ:

Bob then picks a public exponent of e and which does not share a factor with φ, and computes the private exponent as:

Bob will then use a private exponent (d) to create a signature from a message (M) with:

To verify the signature, we use the public exponent (e) with:

and where V should equal the message. If we have M^d=S (mod N), then:

This is difficult to factorise kN to determine k. But we can recover the modulus (N), if we have…