1
$\begingroup$

There's a great cryptography based ctf site that I've been going through. There's this one question around RSA that has been puzzling me for over a week now.

Please don't tell me the answer, I'm only looking for guidance. I really want to work it out myself, but I'm not sure where to start.

Problem Statement

You're given a public key $(e, N)$, where $e=3$ and $N$ is large. To recover the flag, you must pass the following test. Note: I've changed some of the values from the problem

test(hex_msg):
    m = int(hex_msg, 16)
    v = long_to_bytes(pow(m, e, N))

    vote = v.split(b'\00')[-1]
    if vote == b'foobar':
        # Hooray (:     
    else:
        # Not hooray ):

My initial idea was that maybe $v = (foobar)_{10}$ is a cube, so $v = m^3 = m^3 (N) $. Unfortunately no such luck.

My second idea was to try and exploit the padding, to try and find some value $p$ such that $(p || 00 || v)$ is a cube, and then submit that. I have no idea how I'd go about finding a value, enumerating through possible values of $p$ was not very fruitful.

Am I on the right track, or is there something obvious I'm missing?

$\endgroup$
  • $\begingroup$ Hint: what is the mathematical condition tested about v? $\endgroup$ – fgrieu Apr 20 at 19:57
  • $\begingroup$ Hint 2: per big-endian convention, the rightmost $k$ bits of the bitstring encoding integer $x$ encode the integer $x\bmod 2^k$. $\endgroup$ – fgrieu Apr 20 at 20:53
  • $\begingroup$ Hint 3: far all non-negative integers x, k and e, it holds ((pow(x,e)^pow(x^(1<<k),e))&((1<<k)-1))==0 and that comes in handy to find an appropriate value bit by bit. $\endgroup$ – fgrieu Apr 21 at 4:52
  • $\begingroup$ Thanks, I think I have an idea of where to go. I'll get back to you when I crack it! $\endgroup$ – adp Apr 21 at 8:57
1
$\begingroup$

Am I on the right track, or is there something obvious I'm missing?

Assuming that the text is not actually 'foobar', but something else, then yes, you're (likely) on the right track, in the sense that you want to exploit the padding (except the strategy isn't to look for $p$, but for something else...)

| improve this answer | |
$\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.