Tags: rsa 


Given a random plaintext and a fixed signature, generate a public RSA key which can verify the signature into the random plaintext.

We control `n` and `e`, have a fixed `signature` and are provided a `pin`.

We want to manipluate `n` and `e` such that:`pin = pow(signature, e, n)`. Since we only need to produce a public key (which does not even have to be valid!) we can find a naive value of `n` by fixing a small value of `e`. `e` larger than 3 will be accepted by the system. We can then calculate `n` as:

pin = pow(signature, e, n)
= pow(signature, e) - k * n # where k is a positive integer
= pow(signature, e) - n

n = pow(signature, e) - pin


Original writeup (https://github.com/4yn/slashbadctf/blob/master/fbctf19/keybaseish/solution.md).