# RSA CTF Guidance

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?

• Hint: what is the mathematical condition tested about v?
– fgrieu
Apr 20, 2020 at 19:57
• Hint 2: per big-endian convention, the rightmost $k$ bits of the bitstring encoding integer $x$ encode the integer $x\bmod 2^k$.
– fgrieu
Apr 20, 2020 at 20:53
• 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.
– fgrieu
Apr 21, 2020 at 4:52
• Thanks, I think I have an idea of where to go. I'll get back to you when I crack it!
Apr 21, 2020 at 8:57

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