Rating:
hmm, fibonacci is fun, right?
nc extended-fibonacci-sequence.hsc.tf 1337
P.S: This chall was made by an anonymous CS Club member :)
Extended Fibonacci Sequence New.pdf
Despite few solves, I had an easier time with this than not-really-math.
I wrote a basic python function fib(n) that gives me the Fibonacci number in the sequence F<sub>n</sub> using recursion:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
I did the same thing for the Extended Fibonacci sequence S<sub>n</sub> again with recursion:
def exFib(n):
if n <= 0:
return "0" + str(fib(n))
return exFib(n - 1) + str(fib(n))
At this point I could find the summation of the series using a for loop and a list. I used a string slice to grab the last 11 digits of the number and sent it to the nc server with pwntools.
After attempting I realised my fib calculations were way to slow. I used a library called functools to easily cache previously calculated fibs to speed up the program and it did the trick.
Final script:
from pwn import *
import functools
import re
@functools.lru_cache(None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
@functools.lru_cache(None)
def exFib(n):
if n <= 0:
return "0" + str(fib(n))
return exFib(n - 1) + str(fib(n))
def addList(list):
total = 0
for num in list:
total += num
return total
io = process(['nc', 'extended-fibonacci-sequence.hsc.tf', '1337'])
io.recvline()
while True:
try:
data = io.recvuntil(":").decode()
except EOFError:
print(io.recvline().decode())
quit()
n = int(re.search("(\d{1,})\n", data).group(0))
print("[RECIEVE]: " + str(n))
summ = []
for i in range(1, n + 1):
summ.append(int(exFib(i).lstrip('0')))
final = str(addList(summ))
final = final[len(final) - 11:]
io.sendline(final)
print("[SEND]: " + final)
Run the script and out pops the flag!
flag{nacco_ordinary_fib}
