廢文集中區

Cryptoverse CTF 2023 WriteUps

發表於
分類於 CTF
English

這次自己在 nyahello 隊伍中稍微解了幾題，主要包含了 crypto 中幾個相對難的題目。

Crypto

LFSR Explorer

from Crypto.Util.number import *
from secret import flag

assert flag.startswith("cvctf{")
assert flag.endswith("}")

flag = flag[6:-1].encode()
assert len(flag) == 8

def explore(state, mask):
    curr = (state << 1) & 0xffffffff
    i = state & mask & 0xffffffff
    last = 0
    while i != 0:
        last ^= (i & 1)
        i >>= 1
    curr ^= last
    return (curr, last)

states = [bytes_to_long(flag[4:]), bytes_to_long(flag[:4])]
mask = 0b10000100010010001000100000010101

output = []
for i in range(8):
    tmp = 0
    for j in range(8):
        (states[i // 4], out) = explore(states[i // 4], mask)
        tmp = (tmp << 1) ^ out
    output.append(tmp)

with open("output.txt", "wb") as f:
    f.write(bytes(output))

有兩個 LFSR，直接逆回去即可。

with open("output.txt", "rb") as f:
    ct = f.read()


def rev(state, mask):
    curr = state >> 1
    b = state & 1
    state >>= 1
    while mask:
        if mask & 1:
            b ^= state & 1
        state >>= 1
        mask >>= 1
    return curr | (b << 31)


mask = 0b10000100010010001000100000010101
s0 = int.from_bytes(ct[:4], "big")
s1 = int.from_bytes(ct[4:], "big")
for _ in range(32):
    s0 = rev(s0, mask)
    s1 = rev(s1, mask)
print(s1.to_bytes(4, "big") + s0.to_bytes(4, "big"))
# cvctf{G@@d_j0b}

Knapsack vs. Backpack

from Crypto.Util.number import *
from math import gcd
from secret import flag
import random

NBITS = 32

print("=== Knapsack vs. Backpack ===")

class Knapsack:
    def __init__(self, nbits):
        W, P = [], []
        for _ in range(nbits):
            W.append(random.randint(1, 10))
            P.append(random.randint(1, 100))
        
        self.W, self.P = W, P

    def fill(self, nbits):
        r = getRandomNBitInteger(nbits)
        pt = [int(i) for i in bin(r)[2:].zfill(nbits)]
        self.A = sum([x * y for x, y in zip(pt, self.W)])
        self.B = sum([x * y for x, y in zip(pt, self.P)])

try:
    for _ in range(10):
        challenge1 = Knapsack(NBITS*4)
        challenge1.fill(NBITS*4)
        print(challenge1.W)
        print(challenge1.P)
        print(f"Knapsack Capacity: {challenge1.A}")

        inp = list(map(int, input("Items: ").strip().split()))
        for i in inp:
            if i < 0 or i >= len(challenge1.W):
                print("Nope.")
                exit(1)
        if len(inp) != len(set(inp)):
            print("Nope.")
            exit(1)
        weight = sum([challenge1.W[i] for i in inp])
        profit = sum([challenge1.P[i] for i in inp])
        if weight <= challenge1.A and profit >= challenge1.B:
            print("Correct!")
        else:
            print("Nope.")
            exit(1)
except:
    exit(1)

print(flag[:len(flag)//2])

class Backpack:
    def __init__(self, nbits):
        r = [42]
        for _ in range(nbits - 1):
            r.append(random.randint(2*r[-1], 4*r[-1]))
        
        B = random.randint(3*r[-1] + 1, 4*r[-1])
        A = random.randint(2*r[-1] + 1, B - 1)
        while gcd(A, B) != 1:
            A = random.randint(2*r[-1] + 1, B - 1)

        self.M = [A * _ % B for _ in r]

    def fill(self, inp):
        return sum([x * y for x, y in zip(inp, self.M)])

try:
    for _ in range(10):
        challenge2 = Backpack(NBITS)
        r = getRandomNBitInteger(NBITS)
        pt = [int(i) for i in bin(r)[2:].zfill(NBITS)]
        ct = challenge2.fill(pt)
        print(challenge2.M)
        print(f"In your Knapsack: {ct}")

        inp = int(input("Secret: ").strip())
        if inp == r:
            print("Correct!")
        else:
            print("Nope.")
            exit(1)
except:
    exit(1)

print(flag[len(flag)//2:])

前半是 0/1 背包，讓 copilot 直接幫我寫。後半是 merkle-hellman backpack，直接用 LLL 解 subset sum 出答案。

from sage.all import *
from pwn import process, remote
import ast


def solve_01_knapsack(W, P, A):
    # thanks copilot!
    # W: weight of items
    # P: profit of items
    # A: capacity of knapsack
    n = len(W)

    # dp[i][j]: maximum profit of items 0..i with capacity j
    dp = [[0 for _ in range(A + 1)] for _ in range(n)]
    for i in range(n):
        for j in range(A + 1):
            if j >= W[i]:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + P[i])
            else:
                dp[i][j] = dp[i - 1][j]

    # reconstruct solution
    i, j = n - 1, A
    items = []
    while i >= 0 and j >= 0:
        if i == 0:
            if dp[i][j] == P[i]:
                items.append(i)
            break
        if dp[i][j] != dp[i - 1][j]:
            items.append(i)
            j -= W[i]
        i -= 1

    return items


def solve_ssp(w, t):
    L = block_matrix([[matrix(w).T, ZZ(1), ZZ(0)], [matrix([-t]), ZZ(0), ZZ(1)]])
    for row in L.LLL():
        if row[-1] != 0:
            if row[-1] < 0:
                row = -row
            if all([0 <= x and x <= 1 for x in row[1:-1]]):
                if vector(row[1:-1]) * vector(w) == t:
                    return row[1:-1]


# io = process(["python", "challenge.py"])
io = remote("67.205.179.135", 7272)
io.recvline()
for _ in range(10):
    W = ast.literal_eval(io.recvlineS().strip())
    P = ast.literal_eval(io.recvlineS().strip())
    io.recvuntil(b"Knapsack Capacity: ")
    A = int(io.recvlineS().strip())
    items = solve_01_knapsack(W, P, A)
    io.sendline(" ".join(map(str, items)).encode())
    io.recvline()
flag1 = io.recvlineS().strip()
for _ in range(10):
    W = ast.literal_eval(io.recvlineS().strip())
    io.recvuntil(b"In your Knapsack: ")
    t = int(io.recvlineS().strip())
    sol = solve_ssp(W, t)
    secret = int("".join(map(str, sol)), 2)
    io.sendline(str(secret).encode())
    io.recvline()
flag2 = io.recvlineS().strip()
print(flag1 + flag2)
# cvctf{knap5ack_0/1_15_for_the_noob5_BUT_backp@ck_M3rkl3_h3llm4n_15_for_the_pro5}

Fractional Flag

from Crypto.Util.number import getPrime, inverse, bytes_to_long
from secret import flag

assert len(flag) == 99
assert flag.startswith(b"cvctf{") and flag.endswith(b"}")

class MyRSA:
    def __init__(self, n = 2, nbits = 512):
        self.p = getPrime(nbits)
        self.q = getPrime(nbits)
        self.N = self.p * self.q
        self.d = getPrime(nbits//2 - 1)
        self.my_phi = self.gen_phi(n)
        self.e = inverse(self.d, self.my_phi)

    def gen_phi(self, n):
        return sum([self.p**i for i in range(n)]) * sum([self.q**i for i in range(n)])

    def encrypt(self, m):
        print("I am not going to encrypt anything...")
        return m

    def get_public(self):
        print(f"N = {self.N}")
        print(f"e = {self.e}\n")
    
    def get_private(self):
        # print(f"d = {self.d}")
        return self.d

NPARTS = 3
fractions = [bytes_to_long(flag[len(flag)//NPARTS*i:len(flag)//NPARTS*(i+1)]) for i in range(NPARTS)]

print("[+] Here are my public keys:")
ns = [2, 3, 6]
rsas = [MyRSA(n) for n in ns]
private_exponents = [rsa.get_private() for rsa in rsas]

for rsa in rsas:
    rsa.get_public()

print("[+] Here are my flag fractions:")
for i in range(NPARTS):
    f = sum(fractions[j] * private_exponents[i]**(NPARTS-1-j) for j in range(NPARTS))
    print(f"[!] Fraction {i+1}: {f}")

有三個類 RSA public key，對於 n∈{2,3,6}n \in \{2,3,6\} 有 endn≡1(modφi′)e_n d_n \equiv 1 \pmod{\varphi_i'}，其中 φn′=(∑j=0n−1pnj)∑j=0n−1qnj\varphi_n'=(\sum_{j=0}^{n-1}p_n^j)\sum_{j=0}^{n-1}q_n^j。

以 n=2n=2 來說 φ′=(1+p)(1+q)≈N=pq\varphi'=(1+p)(1+q) \approx N = pq。

以 n=3n=3 來說 φ′=(1+p+p2)(1+q+q2)≈N2=p2q2\varphi'=(1+p+p^2)(1+q+q^2) \approx N^2 = p^2q^2。

所以可以得到 φn′≈Nn−1\varphi_n' \approx N^{n-1} 的近似關係。

而拿 ed≡1(modφ′)ed \equiv 1 \pmod{\varphi'} 可得 ed=kφ′+1ed = k\varphi' + 1，其中 k≈dk \approx d，因為 dd 不大所以可以用類似 wiener attack 的方法解出 dd。

eφ′≈kd\frac{e}{\varphi'} \approx \frac{k}{d}

所以拿 Nn−1N^{n-1} 去近似 φ′\varphi'，就可以求出 dd，解出來之後再插值一下就出來了。

from sage.all import *
from Crypto.Util.number import isPrime, long_to_bytes

pubs = [
    (
        2,
        97612005002255328088089410975523983681740354800179039894937915732930244664586629120094932234362725524185511994009850035922533559839893979074939037832668549750255468381192887812469917667115839541015495242839376266431038121426628287675447989631207259597586333251571969522037989427555616133183042678577218636039,
        76116130167787561359953887266200869082448529331107937460219287530308978477708991999616543343406382355689250048669403437942401267295685636067522489421767819007148067769751457394505797110602169754511939818788483430730012575308299189299157812591392734160576417069436538119185074252625496946207312639052459476691,
    ),
    (
        3,
        82898492840033848499679066573599199466262845944574446435099699953454086638324386416129279494828609729766998439132172194894188387716844097335523066318666261933348513791114624155336437054163128912934864480178839237943154511986161169068625070999701692457965233641625122455113801192492673037347038351956273261209,
        4209437149177720414392052396995336370571472638739290885909782621676928212352728218779571626530884770305850882606520062302514835362331092897621059096111410844919671863579044484955054277159466422627065939698416080746679841734383574957303171143150437215717944527004524163060734647488552780385109395365103554265493136383680197786179491825415327877829363932241445886199163804911851983235568877189260370900147226881457732043676609664875472514523869518158935427849891304397052900751093562294098001282747462255107311383605819243052786444806092296448159814920695343700003324553167747140120222023780385726663202175975632841101,
    ),
    (
        6,
        74994178474501705271671940639744064973727732038326591115828216310018498822567967944888584927591599150655580137956560356301728244890598527629795727836492659456865084635190916504902969902122979161893704294891200235692036639700141954229504462610034653592940594511895628524050995435988759181763969824436031245313,
        1489343297993123282242703585767862889532966168614466114229659752495521741344828171911376172581419167249138037648594483979411817592040147160238477726426615905245322859547191851844862266610905034585090032979459885344332508376146458008432418485138745167332564668471655885462387844870978937353124271354756749987557641173034038037138552554286596191926276854019397533360181392329678995160770713221738607291949604788483647158238145885370267789175042383720834228546234687195524802723091258548142868749009819341250311783811669486498714774091479332840123020791916467567722826634424992913028930995948675696110790085249624326162007313472329046629836566951986389110657545671708876118803228632059850860536273457909861781873059134865932188230401277356396602494704882757454481213539839098539947582560234411030973307998825870210215033177749651750411682404527804606701340350999128273688467096980925538961234964285918052638858734125375270072587641505250814286217419987349217586276836222849825473745401814287955844160842207855608228330415022147681694596413651097936005515497301045029721788331269208281455180641244748905469345705931987679143863830321305138722585532495234826613572876602582994268211475793765951624522296606385747914811802020368502982841323574845193182348705392733364068634167943152196883988138300398486795444947317920558342244022638552596544997423504070874736567161433560622253197613565603458736833008516912312579020461040855359316882678726669756450813443842584222951463074601799430267187315529031340358497011459213690622999701314023178557960651,
    ),
]

ds = []
for n, N, e in pubs:
    cf = continued_fraction(ZZ(e) / ZZ(N ** (n - 1)))
    for c in cf.convergents():
        d = c.denominator()
        if d.bit_length() == 255 and isPrime(d):
            print(d)
            ds.append(d)
            break

fs = [
    12885959655953139374785717692048211268233398655222955130228721746869891559409080848367142483157517829612928194235174347299097615553919212787225377729454255371358309685093996459461793296183459238094074717707949401000365552082820354011,
    23144924364202496361036242964551729244108242071387074122924446048219898057065538815277890013860024253422666710259842325295228086904295846675276536535237894072110755426259617054492417613772645109337095876879440959135444974146373938103,
    10216090816848970230135050433869173852319169856151418349231810820430643701522230150158652915588855848669985626642166987135416343716291162149831827545892183798838168834007800941773301995075510960084628367588300016798178754792796044603,
]
ms = map(int, QQ['x'].lagrange_polynomial(zip(ds, fs)))
print(b"".join([long_to_bytes(m) for m in ms][::-1]))
# cvctf{th15_fam1Ly_0f_RSA-like_crypt0syst3m_c4n_b3_4tt4ck3d_wh3n_E_15_cL053_t0_N^(n-1)_4nd_d<N^0.25}

PicoChip 1

from itertools import groupby
from Crypto.Util.number import *
from enum import Enum
from base64 import b64encode
from secret import flag

import plotly.express as px
import random


class State(Enum):
    # PicoChip power states for hardware simulation.
    FALLBACK = 0x0
    SUCCESS = 0x1
    ERROR = 0x2


class PicoChip:
    def __init__(self, k: int, N: int, t: int):
        self.states = []
        self.k = k
        self.N = N
        self.t = t
        self.r = self.gen_op()

    def rec(self, s: State):
        self.states.append(s)

    def gen_op(self) -> list:
        rs = []
        i = 3
        while len(rs) < self.N:
            if isPrime(i):
                self.rec(State.SUCCESS)
                rs.append(i)
            i += 2
        return rs
    
    def gen_secure_prime(self) -> int:
        # More secure than getPrime() as indicated from my latest paper.
        while True:
            v0 = random.randint(2**(self.k-1), 2**self.k)
            v = v0 + 1 - v0 % 2
            while True:
                is_prime = True
                i = 0
                while i < self.N:
                    if v % self.r[i] == 0:
                        v = v + 2
                        self.rec(State.FALLBACK)
                        break
                    i += 1
                    self.rec(State.SUCCESS)

                if i == self.N:
                    for m in range(1, self.t+1):
                        if not miller_rabin(v):
                            is_prime = False
                            v = v + 2
                            self.rec(State.FALLBACK)
                            break
                        self.rec(State.SUCCESS)
                    if is_prime:
                        return v
    
    def plot(self):
        # For transparency, I will show you the internals of PicoChip.
        power_states(self.states)


def power_states(states: list):
    if State.ERROR in states:
        raise Exception("PicoChip is broken!")
    
    power = []
    for k, g in groupby(states):
        if k != State.FALLBACK:
            power.append(sum(1 for _ in g))
        else:
            power.extend([0 for _ in g])

    gx, gy = [], []
    for i in range(len(power)):
        gx.append(i)
        gy.append(power[i])
        gx.append(i + 1)
        gy.append(power[i])

    fig = px.line(x=gx, y=gy, title="PicoChip Power States")
    fig.write_html("power_states.html")


def miller_rabin(n: int) -> bool:
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True
    
    d = n - 1
    while d % 2 == 0:
        d //= 2
    a = 2 + random.randint(1, n - 4)
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return True
    
    while d != n-1:
        x = (x * x) % n
        d *= 2
        if x == 1:
            return False
        if x == n - 1:
            return True
    return False


if __name__ == "__main__":
    pico = PicoChip(36, 60, 1)
    p = pico.gen_secure_prime()
    q = pico.gen_secure_prime()
    assert p != q and isPrime(p) and isPrime(q)

    assert flag.startswith(b"cvctf{") and flag.endswith(b"}")
    flag = flag[6:-1]
    
    N = p * q
    e = 0x10001
    m = bytes_to_long(flag)
    ct = pow(m, e, N)

    print("[+] PicoChip Encryption Parameters:")
    # print(f"N = {N}")
    print(f"e = {e}")
    print(f"ct = {ct}")

    pico.plot()
    print("[+] PicoChip Power States saved.")

這題有個 prime generator 會 leak side channel 的資訊，可以透過它生出的 html 回推 power，而 power 又能回推 states，因此可以透過什麼時候在 FALLBACK 來判斷一些 p−kp-k mod 一些小質數的資訊，然後 crt 復原即可。

還原 qq 也是一樣的概念。

from sage.all import crt, lcm, reduce
from Crypto.Util.number import *

# fmt: off
pico_r = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283]
# fmt: on


def solve_eqs(eqs):
    if len(eqs) < 2:
        return 0, 0
    ms = [-k for k, _ in eqs]
    ps = [p for _, p in eqs]
    L = reduce(lcm, ps)
    res = crt(ms, ps)
    return L, res


def solve(st, N, t):
    eqs = []
    k = 0
    idx = 0
    while idx < len(st):
        for i, s in enumerate(st[idx : idx + N]):
            idx += 1
            if s == 0:
                eqs.append((k, pico_r[i]))
                # assert (vp + k) % pico.r[i] == 0
                k += 2
                break
        else:
            L, cur_vv = solve_eqs(eqs)
            print(f"{L = }")
            print(f"{cur_vv = }")
            for s in st[idx : idx + t]:
                idx += 1
                if s == 0:
                    k += 2
                    break
                if isPrime(cur_vv + k):
                    print("FOUND1", cur_vv + k)
                    return cur_vv + k, st[idx:]
                if L and (2**37 // L) < 10000:
                    for u in range(2**37 // L):
                        if isPrime(cur_vv + k + u * L):
                            print("FOUND2", cur_vv + k + u * L)
                            return cur_vv + k + u * L, st[idx:]


# fmt: off
gy = [66,66,0,0,10,10,0,0,0,0,1,1,0,0,60,60,0,0,0,0,2,2,0,0,3,3,0,0,0,0,17,17,0,0,60,60,0,0,0,0,12,12,0,0,1,1,0,0,0,0,4,4,0,0,41,41,0,0,0,0,1,1,0,0,6,6,0,0,0,0,65,65,0,0,0,0,2,2,0,0,1,1,0,0,0,0,3,3,0,0,48,48,0,0,0,0,1,1,0,0,2,2,0,0,0,0,29,29,0,0,28,28,0,0,0,0,60,60,0,0,5,5,0,0,0,0,16,16,0,0,1,1,0,0,0,0,25,25,0,0,61,61]
# fmt: on
power = gy[::2]

st = sum([[0] if v == 0 else [1] * v for v in power], [])
print(st)
st = st[60:]
p, stt = solve(st, 60, 1)
print(stt)
q, _ = solve(stt, 60, 1)

e = 65537
ct = 3059648962482294740345
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(ct, d, p * q)
print(int(m).to_bytes(100, "big").strip(b"\x00"))
# cvctf{p1C@-_}

PicoChip 2

from Crypto.Util.number import *
from enum import Enum
from base64 import b64encode
from secret import flag

import random
import csv


class State(Enum):
    # PicoChip power states for hardware simulation.
    FALLBACK = 0x0
    SUCCESS = 0x1
    ERROR = 0x2


class PicoChip:
    def __init__(self, k: int, N: int, t: int):
        self.states = []
        self.k = k
        self.N = N
        self.t = t
        self.r = self.gen_op()

    def rec(self, s: State):
        self.states.append(s)

    def gen_op(self) -> list:
        rs = []
        i = 3
        while len(rs) < self.N:
            if isPrime(i):
                self.rec(State.SUCCESS)
                rs.append(i)
            i += 2
        return rs
    
    def gen_secure_prime(self) -> int:
        # More secure than getPrime() as indicated from my latest paper.
        while True:
            v0 = random.randint(2**(self.k-1), 2**self.k)
            v = v0 + 1 - v0 % 2
            
            while True:
                is_prime = True
                i = 0
                while i < self.N:
                    if v % self.r[i] == 0:
                        v = v + 2
                        self.rec(State.FALLBACK)
                        break
                    i += 1
                    self.rec(State.SUCCESS)

                if i == self.N:
                    for m in range(1, self.t+1):
                        if not miller_rabin(v):
                            is_prime = False
                            v = v + 2
                            self.rec(State.FALLBACK)
                            break
                        self.rec(State.SUCCESS)
                    if is_prime:
                        return v
    
    def save(self):
        # For transparency, I will show you the internals of PicoChip.
        power_states(self.states)


def power_states(states: list):
    if State.ERROR in states:
        raise Exception("PicoChip is broken!")
    
    states = [s.value for s in states] 
    fields = ['Time', 'Signal']
    rows = [[i, s] for i, s in enumerate(states)]
  
    with open('power_states.csv', 'w') as f:
        write = csv.writer(f)
        write.writerow(fields)
        write.writerows(rows)


def miller_rabin(n: int) -> bool:
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True
    
    d = n - 1
    while d % 2 == 0:
        d //= 2
    a = 2 + random.randint(1, n - 4)
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return True
    
    while d != n-1:
        x = (x * x) % n
        d *= 2
        if x == 1:
            return False
        if x == n - 1:
            return True
    return False


if __name__ == "__main__":
    pico = PicoChip(512, 100, 10)
    p = pico.gen_secure_prime()
    q = pico.gen_secure_prime()
    assert p != q and isPrime(p) and isPrime(q)

    assert flag.startswith(b"cvctf{") and flag.endswith(b"}")
    flag = flag[6:-1]
    
    N = p * q
    e = 0x10001
    m = bytes_to_long(flag)
    ct = pow(m, e, N)
    
    print("[+] PicoChip Encryption Parameters:")
    print(f"N = {N}")
    print(f"e = {e}")
    print(f"ct = {ct}")

    pico.save()
    print("[+] PicoChip Power States saved.")

和前面幾乎一樣，不過這次 N 已知且 p,q 都是 512 bits 的，所以大概是用一樣的方法還原然後 coppersmith 之類的。

我拿實際參數來側發現我能得到 p−kp mod Lpp-k_p \bmod{L_p} 和 q−kq mod Lqq-k_q \bmod{L_q}，其中 log⁡2Lp=220\log_2 L_p = 220 和 log⁡2Lq=256\log_2 L_q = 256。不過我這樣還有個幾個問題要處理

  1. 256 bits 對於 coppersmith 有點緊
  2. 因為我的方法無法判斷 power trace 中哪段是 p 哪段是 q，所以 crt 送進去的參數是對所以還要想辦法去 error
  3. 類似上面的原因，我也不能確定 kp,kqk_p, k_q

主要是要先注意到 Lp,LqL_p, L_q 都是一些小質數的乘積，所以取 L=gcd⁡(Lp,Lq)L=\gcd(L_p,L_q) 之後用 small_roots 解 (p′+x)(q′+y)≡N(modL)(p'+x)(q'+y) \equiv N \pmod{L} 可得 kp,kqk_p, k_q。

再來是 Lp/L,Lq/LL_p/L, L_q/L 都非 1，所以其實還有些額外的資訊可以用，稍微算一下之後用 CRT 就能算出 pp 或 qq 在 mod  lcm⁡(Lp,Lq)\mod{\operatorname{lcm}(L_p, L_q)} 之下的值了，大概 340 bits 左右。

最後 error 的部分我是透過把 lcm⁡(Lp,Lq)\operatorname{lcm}(L_p, L_q) 分解然後隨機移除幾個 prime，然後用 coppersmith 解解看直到有解為止。

from Crypto.Util.number import *
from tqdm import tqdm
import random
from lbc_toolkit import small_roots

N = 130242563655857624894400945577596726349342500250110028576899185041437457270571385988775800707021082684571500938230335838572343683077030043170929464612371476956037213483889197399888953059037490955052374761877827022364642118001281744384383425614733953384975007872647643383223846078326219496054222658506664194809
e = 65537
ct = 105907761990378066226415220707780642346253492128869807523331608442629667283774856771483475721417798409391047173653877895381454531056957845466445503946203117753779878926970882151071816334395199925843076844258607834225532144320120475312185170491128333893223806872578843356036259570319998389877610989110147615590

# get this with `get_mod.py`
Lq = 110771048542294008655567252323407263021635384906342218910220956868946703113415
qmLq = 46507139167438726023448101260439823591848326066022505845258905249241953906242
Lp = 1487051625896473568251626796657514782188841738792655155038905673165
pmLp = 72663085590708489175312897469020819802613550944383864132672454215

L = gcd(Lq, Lp)
qL = qmLq % L
pL = pmLp % L

# qmLq, pmLq is not actually q (mod Lq) and p (mod Lp)
# instead, it is the initial output of `v0 = random.randint(2**(self.k-1), 2**self.k); v = v0 + 1 - v0 % 2`
# I am not sure the `k` value found in `get_mod.py` is correct
# so just test it with coppermsith
x, y = Zmod(L)["x,y"].gens()
f = (qL + x) * (pL + y) - N
x, y = small_roots(f, (2**10, 2**10))[0]
qmLq += x
pmLp += y

# unfortunately, neither Lp and Lq are big enough to apply coppersmith here
# but we can use the fact that n=pq to get more bits of q (mod Lq/gcd(Lq,Lp)) and p (mod Lp/gcd(Lq,Lp))
L2 = Lp // L
qmL2 = N / pmLp % L2
L3 = Lq // L
pmL3 = N / qmLq % L3
LL = Lq * L2
qmLL = crt([qmLq, qmL2], [Lq, L2])
pmLL = crt([pmLp, pmL3], [Lp, L3])
assert qmLL * pmLL % LL == N % LL

# let's coppersmith
x = Zmod(N)["x"].gen()
for _ in range(100):
    ps = [p for p, _ in factor(LL)]
    # we are not sure it is always correct
    # try remove some primes and apply coppersmith until it works
    pps = set(ps) - set(random.sample(ps, 8))
    Lsub = prod(pps)
    print("trying", Lsub, Lsub.bit_length())
    qmLsub = qmLL % Lsub
    f = (qmLsub + x * Lsub).monic()
    rs = f.small_roots(X=2 ** (512 - Lsub.bit_length()), beta=0.49, epsilon=0.1)
    if rs:
        sol = rs[0]
        print("yay", sol)
        break

q = ZZ(qmLsub + sol * Lsub)
p = ZZ(N // q)
assert p * q == N
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(ct, d, N)
print(long_to_bytes(m))
# cvctf{jU57_4_s1MpL3_s1d3_ch4nn3L_ch1p@_@}

Misc

OJail

ocaml 的 jail (?)，連上去直接 Sys.command "sh";; 就拿 shell 了。

*Minecraft’s Deadly Dilemma

賽中沒能解掉這題

from io import BytesIO
from PIL import Image
import base64
import numpy as np

def load_image(img: str):
    with open(img, 'rb') as f:
        img = Image.open(f)
        img = img.convert('L')
        return np.asarray(img)

def load_image_b64(img: str):
    img = Image.open(BytesIO(base64.b64decode(img)))
    img = img.convert('L')
    return np.asarray(img)

def distance(x, y):
    return np.linalg.norm(x - y)

def is_close(inp, x):
    if inp.shape != x.shape:
        return False
    return np.sqrt(np.sum(np.abs(inp - x))) < 474


if __name__ == '__main__':
    sword = load_image("./sword.png")
    pickaxe = load_image("./pickaxe.png")
    try:
        test = load_image_b64(input().strip())
        if is_close(test, pickaxe) and distance(test, pickaxe) > distance(test, sword):
            from secret import flag
            print(flag)
        else:
            print("Nope!")
    except:
        exit(0)

簡單來說他有兩張 64x64 的圖片 pickaxe 和 sword，然後要找到一張圖讓 L2Norm(img - pickaxe) > L2Norm(img - sword)，並且 sqrt(L1Norm(img - pickaxe)) < 474。

我的作法是直接上 pytorch 用 backpropagation 來找，loss 部分亂弄一下就出來了。

from io import BytesIO
from PIL import Image
import base64
import numpy as np
import torch


def load_image(img: str):
    with open(img, "rb") as f:
        img = Image.open(f)
        img = img.convert("L")
        return np.asarray(img)


def load_image_b64(img: str):
    img = Image.open(BytesIO(base64.b64decode(img)))
    img = img.convert("L")
    return np.asarray(img)


def distance(x, y):
    return np.linalg.norm(x - y)


def is_close(inp, x):
    if inp.shape != x.shape:
        return False

    return np.sqrt(np.sum(np.abs(inp - x))) < 474


sword = load_image("./sword.png")
pickaxe = load_image("./pickaxe.png")

sword_tensor = torch.tensor(sword).float()
pickaxe_tensor = torch.tensor(pickaxe).float()
x = torch.nn.Parameter(torch.rand((1, 1, 64, 64)), requires_grad=True)
optim = torch.optim.SGD([x], lr=3e-1)


def loss_fn(x):
    dist = torch.sqrt(torch.sum(torch.abs(x - pickaxe_tensor)))
    cond2 = torch.norm(x - pickaxe_tensor) - torch.norm(x - sword_tensor)
    total_loss = dist - cond2 * 2
    return total_loss, dist, -cond2 * 2


i = 0
while True:
    optim.zero_grad()
    loss, a, b = loss_fn(torch.clamp(x, 0, 254))
    if i % 1000 == 0:
        print(i, loss, a, b)
    if a < 474 and b < 0:
        xxx = torch.clamp(x, 0, 254).detach().numpy().reshape(64, 64).round()
        img = Image.fromarray(xxx)
        img = img.convert("L")
        img.save("result.png")
        yyy = load_image("result.png")
        c1 = is_close(yyy, pickaxe)
        c2 = distance(yyy, pickaxe) > distance(yyy, sword)
        print(
            c1,
            c2,
            distance(yyy, pickaxe),
            distance(yyy, sword),
            np.sqrt(np.sum(np.abs(yyy - pickaxe))),
            np.sqrt(np.sum(np.abs(xxx - pickaxe))),
        )
        if c1 and c2:
            break
    loss.backward()
    optim.step()
    i += 1

with open("result.png", "rb") as f:
    print(base64.b64encode(f.read()))

"""
iVBORw0KGgoAAAANSUhEUgAAAEAAAABACAAAAACPAi4CAAAGzUlEQVR4nI1W2ZbbuA4EwV27lzi5//9zSXfbkrVR3O/DTJJu2Z0JHiFWsQACdUQYiZTq/nzNhyjejjNQqjZUmzQzcs+5czXhMNez9CwtF+MEncRallcSNAs2YYBUy/Hrm2gkXLtBkbgFzox5VbSK+jA3Ik9sI1ek0kTIrEESKkhDXTHGmSDky7aiF0nrFwH1cHg73riQ/dcwVES8tmEqAkb/zbLXLoQYaFBZix7aKWextPSOLKmgV1bETRBIx5ECT7Gv4iRMEOeXEhTpi8rLqxwYMAsf40IkIQoXmYkMkUmyBbXqtODxtZBkiYQ3fap7ZROpaL7D5fuOQKkRM/FCuYJJi+kaYK0nVuutkHxivKY/WgbZAWZG5gvdCwBuKNZrAZlRWM4m1FmLKZNtY2ufkmR0OvQynXnddv0UJ032BDFFIrPyhjUpJrnYb+GtYZs93NHWca0nAE35QKBQ+Xp++QeE6TdBqzwrcypNwa/oaDx9BzlKIZDZJhHw9JTo1Ld5QTaL+V/QOzwUI8Vox/RtsadYTcX67Wsl7OSTT6O3XzcaFtiUlSlOgm97/QDg8kxq30z1lGOXLKOeX4/U+8qshGgvDLTk5mW7OReewAGK1qD0o4zoJN1Kxv2olz7baSTeCZateIkHWiyUyad40NeRiMwRPW7UXQKhMYheaRNEYYXrTzPLxdyZxNz0lACLhqgNSjoeCbmr6XLVxdvhWtCZ+ZPP2sT6hRT5ORgA4BhmpNU3U+h+HcVyuTJBRH9JWpHKFEUf6pVx+qx7/wbbBOlWru548LefyQb0vHwd7CU5i9xGzodfitOeAAURrvWZZDA/k19GFclGGOWLr+n8h/sB5GnARqetcrr4lVwslRxKamw62hv73TB8JKjmhmWjBAm338kVbtCUS8ESc7SWv4Xv9QMASM+80g9rDkYha6bGDp8BAeCcM+a5Qqnpdt9/PKpiArN82L49zy1S79VEsKJ2faCvDaRual8+Zj+8AktQoEPSio3hdYe/zAHFenD9Z+gTiC1PNJOOTcCBvReICQB4uWb3EfyhBBNEtNVSCcMO2eTxodYvKRT73Pto+lRHoVZncKGB5IceTNv6AfRhBk7leYQNJLGlRwIsk+7t9x0P4/qxEACAs6vupYtr6S0i+2L18n4OPsf/+jSVizNdQQUEJfAGb/D4jJ9pAACA9m4bug4q2DYnpihJ5fgfuJ93J4BSkMjjpF2G4ZDjSo7jYbYJ0p+Kfx9HmslIHDARfeLHhDe+aPa+wp3efagbzSEUAFCkixxfWSl6Ldyzo08UVaGOLCwNzkgCh9V6jjU/e/VX4gFA+8BIT2cWWKxSrSvNcA5vj3P0WQ0zg6lrzQEap310hpcFzng2T8CPNXxl/2t1SsXEa288sEmFeAsBy4HUz9u1i6mebS4J1cSNAVqpqSD14Bg2o3xwpGfReQL3Kogb1pgJiwbIVkuOxiTCAfCDZz5I0gx77vNZR4TkDbUzAuhiySOKouEPr/g4Eweg34nMScRS1dVGupuGqFxRoFlvOzw+UVAsrCqpD1HQUieWqi2Wmxo493gwhFfnwzv/3LsPAACmclXzYrKzlg0pi6CQhJKQgtB64S7+s0740RU+bgeTsUux1+DKzV3uDQGyKieZNlyrrdyVnh47kQy8QAOZtdk1DmHjV5Z4Rt9sceA/9po/2aWxzTzF84x4m8e6WOGVMFLtTf15IAAAy1LRsUA7nx1mvgFlTX66ip+xFODv1BN2WMXEecyGSLr+nZP8Kun81mVitK8s9ZCwZn9C7cEAwAcg9yAmdfc+jTOy+BcM7zXWQvcEIE4bzLm6MEPLv6rgVywHwx3lwR6oJT4RAL5bxk/c9WcZLJzy7WSgst6JwFG2e0P6j56KU+TtPfCX7LmSHMu0/4v9D3vxkb1KUm0CSD0hxduDoyYAQHz2TwUAAOXg0ygDb+Yu+DhicT/8+cZ9THKCNoxyLF+ycAKTpo+H/lBFp5t0hnzCKDt0UrCmbx/O8E9ZvtDvaq5urDQxO7IwMuHw0ETIn/k8wLrKkm11RhsPgWUSGSvdwySaoPnajsrF1lql8wCHbU5lXll77ap7N02JKrk2Y/eDANr6bU9w5MGS2S+kGQMu/T3QFI6gkcO1RkMTXJRbbsGZHwIiaQxHp6XN2cpJgzlmmKptKxCjvqcus5fa1ldo0KTjNXTDKQ8FOhUjrIJYFOhQmI5uOEuI5yqxtZ/ryfGgLF4FGYd4tt1QojJSQzyPBU1is4g5UlRUVw1ulsRxUah8oOsgk6J+U7zRiRFNWFATIaMoOqiW8UcTkngZWFnElICJscEp/B98MNFTPsG0qAAAAABJRU5ErkJggg==
"""
# cvctf{chatGPT_isn't_wrong_but_u_n33d_more_s@mples}