RSA blind signature attack but without public exponents

Question

I been trying to solve a particular challenge where we have to sign an admin message.

At first it seems a classic RSA blind signature attack but eventually they didnt give out the public exponents(e,n) and e is of prime(128) length.

The server offers to encrypt anything n number of times but not the admin message and there's is a option for verification,if we verify the admin message we get the flag!

But im completely stuck here any help would be appreciated.

Thanks.

Answer 1

But im completely stuck here any help would be appreciated.

Well, this appears to be a CTF challenge (or similar), and so I won't spell out the full answer; I will give hints to the two subproblems involved.

The first problem is to recover the modulus $n$; how can we do that? If we ask for the encryption of both $c$ and $c^2$ (for some $c < \sqrt{n}$; we can get an estimate of the size of $n$ by asking for the signature of an arbitrary value), how can we get a multiple of $n$ from those two values $c^e \bmod n$ and $c^{2e} \bmod n$? What if we did that with a different pair $d, d^2$? How can that be used?

The second problem is deducing the value $m^e \bmod n$, where we know the value $n$ (but not $e$) and where $m$ is the admin message. Hint: $a^e \times b^e \equiv (ab)^e \pmod n$, even if we don't know what $e$ is...

Answer 2

Spoiler Alert:

If server allows to sign negative integer you can sign negative of admin message. You will get a positive value. Send negative of that as verification and you will get it. If you still want positive signature sign -1 value you will get is n-1. Just add 1 in it to get n. And for RSA sum of positive and negative of a same message is equal to n. Just subtract encryption of negative message from n and you will get encryption of positive admin message.