1
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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...

$\endgroup$
3
  • $\begingroup$ Thanks for the heads up! and the message seems to be a prime ==> assert isPrime(to_sign) So will be there any alternate workarounds? $\endgroup$
    – rengoku
    Feb 23 at 16:01
  • $\begingroup$ @rengoku: well, then you'd need to compute a modular inverse in step 2 to find $b$ given $a, m$; not that difficult, I suppose... $\endgroup$
    – poncho
    Feb 23 at 16:38
  • $\begingroup$ Thanks for the help ! I managed to solve it $\endgroup$
    – rengoku
    Feb 25 at 14:39
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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