Crypto - SSP

Sometimes it requires GPU to compute huge amount of operation... like O(2^100)..? Nah, you'll use better algorithm, O(2^50) seems fair huh? - __readfsqword

Full Implementation

Challenge

MAX_N = 100
RAND_MAX = 10 ** 200 # You can't even solve with knapsack method
from random import randrange
for n in range(1, MAX_N + 1):
    print(f"Stage {n}")
    arr = [ randrange(0, RAND_MAX) for _ in range(n) ]
    counts = randrange(0, n + 1)
    used = set()
    while True:
        idx = randrange(0, n)
        used.add(idx)
        if len(used) >= counts:
            break
    s = 0
    for idx in used:
        s += arr[idx]
    for a in arr:
        print(a, end=' ')
    print(s)
    answer = list(map(int, input().split()))
    user_sum = 0
    for i in answer:
        user_sum += arr[i]

Another knapsack question, although the question states that it is exponential in time, we use a lattice reduction method that solves it in polynomial time

To do this, we refer to this paper

752KB

cjloss.pdf

pdf

Pg 18, A Gentle Tutorial for Lattice-Based Cryptanalysis

Exploit

To speed up the lattice reduction for large lattices, we use flatter. Unfortunately, flatter doesn't work for very short lattices so we use sage's built in LLL method as a fallback and the knapsack solve code from here

from pwn import *
load(flatter.sage)
def solve(arr,s):
    M = identity_matrix(QQ, len(arr))
    M = M.augment(vector(arr))
    M = M.stack(vector([-1/2 for _ in range(len(arr))] + [-s]))
    try:
        M1= flatter(M)
        row = M1[0][:-1]
        ans=[]
        for cnt,i in enumerate(row):
            if i==1:
                ans.append(cnt)
        return ans
    except:
        M1 = M.LLL()
        for row in M.LLL():
         for row in (row, -row):
            if row[-1] == 0:
                subset = [i for i, x in enumerate(row[:-1]) if x+1/2==1]
                return subset
r.close()
r = remote("35.224.11.111",32054)
r.sendline("0")
r.recv()
r.recvline()
for i in range(99):
 arr=r.recvuntil(b"\n")[:-1].decode()
 arr = arr.split(" ")
 arr = [int(i) for i in arr]
 s= arr[-1]
 arr = arr[:-1]
 ans=solve(arr,s)
 a1=str(ans)[1:-1].replace(','," ")
 r.sendline(a1)
r.recvline()
b'DEAD{T00_B1g_Number_Causes_Pr0blem...}\n'