攻防世界Crypto-babyFibo

分析

附件内容：

import os
import libnum
from secret import flag

def fibo(n):
    assert n >= 0
    if n < 2:
        return n
    return fibo(n-1) + fibo(n-2)

s = fibo(1000)
m = libnum.s2n(flag+os.urandom((len(bin(s))-2)//8-len(flag)))
c = m^s
print(c)

• s是斐波那契数的第1000个数
• m=flag+随机数字然后再(String to Number)转为一个超大数字
• c=m^s

那解题思路就是将其中设计的步骤反着来一遍

开搞

计算fibo(1000)

以下由三种方法计算fibo(1000)

由于直接递归1000不可行

方法一：动态规划：

def fibo(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
s = fibo(1000)

方法二：直接调用库函数

import gmpy2
s = gmpy2.fib(1000)

Exploit

import libnum

def fibonacci(n):
    if n <= 0:
        return "Input should be a positive integer."
    fib_seq = [0, 1]
    while len(fib_seq) < n:
        fib_seq.append(fib_seq[-1] + fib_seq[-2])
    return fib_seq[n - 1]

# 这里是附件中给的字符串
c = 43104378128345818181217961835377190975779804452524643191544804229536124095677294719566215359919831933542699064892141754715180028183150724886016542388159082125737677224886528142312511700711365919689756090950704

# Compute the 1001st Fibonacci number
s = fibonacci(1001)

# XOR the ciphertext with the Fibonacci number to get the message
m = c ^ s

# Convert the message to a string
b = libnum.n2s(m)

print(b)