The Problem
-----------
we're given a text file with three numbers labeled n, e, and c. This looks like an RSA problem where we need to crack the ciphertext c. e is only 5, which looks like this may be a small exponent attack. Normally, e would be something like 65537 = 0x10001
The Small Exponent Attack
-------------------------
Most documentation online about small exponent attacks talk about e=3, but it should be the same for e=5. Note that this doesn't necessarily mean c will be easy to crack, just that it might be. Because of this, when my original attempt during the competition didn't work, I assumed it must be something else and just moved on. After seeing writeups say that it was, in fact, a small exponent attack, I assumed that I must have made a typo or mistake somewhere in the math and went back to solve it after the fact.
The idea behind a small exponent attack is that our ciphertext c is calculated from plaintext p with exponent e and modulo n
c = (p**e)%n
which would mean that
(p**e) = c + (k * n)
for some k. Obviously we don't know what that k is, and it could be very large if p was big enough. A higher e makes it much more likely that k would be extremely large, but since e is so small, there is a chance that we can find (p**e) with only a few iterations trying increasing values for k.
That alone isn't enough, though, as we have no way to know directly if the (p**e) we calculate for a given k is the correct one. For that, we need to calculate the e-th root of (p**e) to get p and check if a) that root even exists and b) if that p is our flag or some other random value that happens to work. For my attack, I only ever actually checked if the root existed as I figured if I found a false positive I could just fix the code then.
e-th Root In Python
-------------------
Now the hard part is calculating the e-th root of (p**e). There are a number of math tools that can do this for us, but I didn't feel like relearning sagemath or NumPy, so I was trying to just deal with it myself in pure python. As it turns out, there are tons of little hiccups that make this pretty annoying.
First, for a t = (p**e), p = t**(1/e) will try to convert t into a float and fail because the int is too large. So we can't just do that.
Instead, I decided to write a binary search over range(0,t) which would calculate i**e and check it against t. This is a pretty decently fast way to search for an e-th root.
I wrote a generic binary search function which I figured I could reuse later for something else. I did it recursively originally, but python had a fit when my numbers were too large and it hit the recursion limit. So I had to rewrite it as a loop instead.
I also ran into various issues with keeping it generic and dealing with large numbers. For instance, len(range(0,really_big_number)) throws an exception that that int would be too large for a C ssize_t. So I had to add the ability to define custom start and end points in the iterable.
The final code looks like this:
```
#binary search
#searches for an s in i that satisfies x == f(i[s])
#i = iterable
#f = function to call on each element of i
#x = value to search for
#start = offset into iterable to start
#end = offset into iterable to end
#if it finds a match, it returns a tuple of (s,i[s],f(i[s]))
#if it does not find a match, it returns (-1,None,None)
def bsearch(i,f,x,start=0,end=-1):
if end == -1:
end = len(i)-1
#s = _bsearch(i,f,start,end,x)
s = _bsearch2(i,f,start,end,x)
return (s,i[s],f(i[s])) if s != -1 else (s,None,None)
#recursive
def _bsearch(i,f,lo,hi,x):
if hi >= lo:
md = (hi+lo)//2
a = f(i[md])
if a == x:
return md
elif a > x:
return _bsearch(i,f,lo,md-1,x)
else:
return _bsearch(i,f,md+1,hi,x)
else:
return -1
#loop
def _bsearch2(i,f,lo,hi,x):
while True:
if hi >= lo:
md = (hi+lo)//2
a = f(i[md])
if a == x:
return md
elif a > x:
hi = md-1
else:
lo = md+1
else:
return -1
def small_e_attack(c,e,n,kend=100):
for k in range(1,kend):
t = c + (k*n)
p = bsearch(range(1,t),lambda p: p**e,t,end=t-2)[1]
if p != None:
print(p.to_bytes(40,'big').decode())
break;
```
and then we can just call
small_e_attack(c,e,n)
and it prints the flag
