- Solved after the CTF ended :(
- I needed to see this post sooner…
- One of the answers includes an arithmetic version of left and right shift.
- I need to practice more crypto…
Using rewritten version that doesn’t read input from file.
x is a string (presumably).
This means that each unit of length of
x is a byte (char). However, to easily deal with integers, we can transform this constraint.
The below is pseudocode!
len(str((int) x)) <= 2**(50*8) = 2**400
assert(str(int.from_bytes(x, "utf-8"), byteorder='big') << 10000).endswith(...)
Assuming we already did the
(int) conversion to change
xint, we get
An interesting property about left shift is that
x*(2**y). Also, this is not relevant, but
This means that our assertion is:
Putting it together
Let’s call our given ending sequence
R. We will also call
We know that
(xint * 2**10000) % 10**L = R.
(xint * 2*10000) % 10**175 = R.
So, let’s try to reverse this!
To reverse this, we would generally multiply both sides by the inverse of
2**10000 % 10**175. However, it is not possible to find the inverse because the gcd of
10**175 is not 1! reasoning
But, we can massage the right hand terms of
Eq 1 a bit (find the gcd and divide, basically).
(xint * 2**10000)%10**175
= ((xint * 2**10000)%10**175)%5**175)
We can find the inverse of
2**10000 % 5**175!
Then, we multiply by the inverse:
(xint * 2**10000 * inverse = R * inverse) % 5**175
(xint = solution) % 5**175
Keep in mind that
5**175 > 2**400, meaning the solution we get will not be cut off in a weird way. After getting the solution, we can convert the integer to bytes, then to a string. Plug into the challenge and make sure that we pass both assertions!
I tried to use
Sage… but couldn’t wrap my head around it… I ended up just using
Python. The script is included in the write-up repository.