# 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 '20 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 '20 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 '20 at 4:52
• Thanks, I think I have an idea of where to go. I'll get back to you when I crack it!
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...)