Tags: rsa crypto 

Rating:

This is an unintended solution that does not utilize sig1 or sig2.
First note that we are given that $e=65537$. Since signing a message simply raises it to the power of $d$, any message that is sent raised to the power of $e$ will be decrypted. So, first sign a message, denoted as $m$, and receive $m^{d} \bmod {n}$ as the signature. Then sign $m (2^{(8e)})$, which is equivalent to signing $m$ with $e$ null bytes appended to it, and receive $(m^{d})(2^{8ed}) \equiv (m^{d})(2^8) \bmod {n}$ as the signature. Let's call this signature $s$. We do some algebra to rearrange these congruences into a more useful form:
$$(m^{d})(2^8) = kn + s$$
$$(m^{d})(2^8) = kpq + s$$
$$(m^{d})(2^8)-s = kpq$$
$$\frac{(m^{d})(2^8)-s}{p} = kq$$
Evaluating the left side gives us a number which is a multiple of $q$. Assume that $k \ll q$, and therefore that $q$ will be the largest prime factor of this number. Since essentially any $m$ can be used, we find one that gives a multiple which is easy to factor. This should not take many attempts since $k$ is generally small. After finding $q$, we can find the totient and therefore $d$, and sign the message.

Flag: `flag{random_flags_are_secure-2504b7e69c65676367aef1d9658821030011f8968a640b504d320846ab5d5029b}`