K3RN3L CTF 2021 WriteUps

發表於 2021-11-14

分類於 CTF

這個 CTF 我是只有在有空的時候才去解點 Crypto 題目的，因為有不少有趣的題目所以還是紀錄一下。這次用的隊伍名是 peko，31 名。

Pryby

from Crypto.Util.number import bytes_to_long 
def f(n):
    q=[True]*(n + 1)
    r=2
    while r**2<=n:
        if q[r]:
            for i in range(r**2,n+1,r):q[i] = False
        r += 1
    return [p for p in range(2,n+1) if q[p]]
class G:
    def __init__(self, f):
        self.f = f
        self.state = 1
    def move(self):
        q=1
        for p in self.f:
            if self.state%p!=0:
                self.state=self.state*p//q
                return
            q*=p
flag = open('flag.txt','r').read().strip().encode()
flag=bytes_to_long(flag)
gen = G(f(pow(10,6)))
for _ in range(flag):gen.move()
print('enc =',gen.state)
# enc = 31101348141812078335833805605789286074261282187811930228543150731391596197753398457711668323158766354340973336627910072170464704090430596544129356812212375629361633100544710283538309695623654512578122336072914796577236081667423970014267246553110800667267853616970529812738203125516169205531952973978205310

可以看出它是拿質數作為 binary 表示，所以就分解開然後恢復 bits 得到 flag:

fs = [
    a
    for a, b in factor(
        31101348141812078335833805605789286074261282187811930228543150731391596197753398457711668323158766354340973336627910072170464704090430596544129356812212375629361633100544710283538309695623654512578122336072914796577236081667423970014267246553110800667267853616970529812738203125516169205531952973978205310
    )
]
ps = list(primes(1500))
print(int(sum([1 << ps.index(x) for x in fs])).to_bytes(100, "big"))

Pascal RSA

triangle =[[1]]
flag = open('flag.txt','rb').read()

from Crypto.Util.number import getPrime,bytes_to_long
from math import gcd
p = getPrime(20)
while len(triangle[-1]) <= p:
    r = [1]
    for i in range(len(triangle[-1]) - 1):
        r.append(triangle[-1][i] + triangle[-1][i+1])
    r.append(1)
    triangle.append(r)
code = ''
for x in triangle[-1]:
    code+=str(x%2)
d = int(code,2)
while True:
    P = getPrime(512)
    Q = getPrime(512)
    if gcd(d, (P-1)*(Q-1)) == 1:
        N = P*Q
        e = pow(d,-1,(P-1)*(Q-1))
        break
enc = pow(bytes_to_long(flag), e, N)
file = open('challenge.txt','w')
file.write(f'p = {p}\nenc = {enc}\nN = {N}')

這題 RSA 的 $d$ 是使用一個帕斯卡三角形的第 $p$ 層模 2 之後的 binary representation 所得到的，查一下相關資訊可以找到 Sierpiński's triangle，而它轉換為數字的數列在 OEIS 上也有: A001317

所以用它裡面給的通項公式求出 $d$ 之後就有 flag 了:

# https://oeis.org/A001317
p = 751921
d = 1
for _ in range(p):
    d ^= 2 * d

c = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
n = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447
m = pow(c, d, n)
print(m.to_bytes(128, "big"))

Poly Expo go BRRRRR

#!/usr/bin/env sage
#
# Polymero
#

from Crypto.Util.number import getPrime

with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

n = getPrime(512) * getPrime(512)
e = 0x10001

P.<x> = PolynomialRing(GF(2))
N = sum([int(j)*x**i for i,j in enumerate('{:0{bl}b}'.format(n,bl=n.bit_length()))])
Q.<x> = P.quotient(N)

def encrypt(msg):
    if type(msg) == bytes:
        msg = int.from_bytes(msg,'big')
    msg = sum([int(j)*x**i for i,j in enumerate('{:0{bl}b}'.format(msg,bl=n.bit_length()-1))])
    cip = Q(msg)**e
    cip = int(''.join([str(i) for i in list(cip)]),2)
    return cip

c = encrypt(FLAG)

print('n =',n)
print('e =',e)
print('c =',c)

assert solve()

#
# n = 119688104315557021890936576297322528053073582644938225605833562855944546643311189725353580415278613605803528999976536949698525581164157480218289586687945087549976509446759942778609918817975151644563678567137671925049937536315926169828583738712154203276012477308556625213229949900385215601055758028238785190211
# e = 65537
#
# c = 59180475538014020769986137847579404920412136380976726613826924727288568855214946199702335444771145318394201684142700441287649150098774979773106915707593238156979003572684188994666984941867671144226245449471326607224512384706414018555885923177955268177207582929765645093722741174664225408159262482249199006862
#

這題看起來像是 RSA，只是 $N$ 被轉換到 $\mathbb{F}_2$ 的一個多項式 $f(x)$ ，之後的運算都在 $\mathbb{F}_2[x]/f(x)$ 下運算。flag 本身也是轉換到那個 ring 之下的多項式之後開 $e$ 次方加密後再轉回數字。

可以發現 $f(x)$ 本身是可以分解的，所以要找個方法求出它的 order 後拿到 $d$ 解密即可。查一下資料可以在這邊找到公式。

對於 $\mathbb{F}_k$ 底下 degree $d$ 的 irreducible polynomial $f(x)$ 來說

\varphi(f(x)^n)=k^{dn}-k^{d(n-1)}

然後還有對於任意多項式都有

\varphi(f(x) \cdot g(x))=\varphi(f(x)) \cdot \varphi(g(x))

有兩個關係之後就足夠計算出 $\varphi(f(x))$ ，之後再求 $d \equiv e^{-1} \pmod{\varphi(f(x))}$ 即可解密。

n = 119688104315557021890936576297322528053073582644938225605833562855944546643311189725353580415278613605803528999976536949698525581164157480218289586687945087549976509446759942778609918817975151644563678567137671925049937536315926169828583738712154203276012477308556625213229949900385215601055758028238785190211
e = 65537
c = 59180475538014020769986137847579404920412136380976726613826924727288568855214946199702335444771145318394201684142700441287649150098774979773106915707593238156979003572684188994666984941867671144226245449471326607224512384706414018555885923177955268177207582929765645093722741174664225408159262482249199006862

P.<x> = PolynomialRing(GF(2))
N = sum(
    [
        int(j) * x ** i
        for i, j in enumerate("{:0{bl}b}".format(n, bl=int(n).bit_length()))
    ]
)
Q.<x> = P.quotient(N)

# https://pointloma.whdl.org/sites/default/files/Freed-RSA%20Encryption%20Using%20Polynomial%20Rings-HP.pdf
# 4.5
# For a irreducible polynomial f(x) over F_p
# phi(f(x)^n)=p^((deg f(x))*n)-p^((deg(f(x)))*(n-1))
# phi(f(x)*g(x))=phi(f(x))*phi(g(x)) holds too
phi = product(
    [2 ** (poly.degree() * n) - 2 ** (poly.degree() * (n - 1)) for poly, n in N.factor()]
)
d = inverse_mod(e, phi)
c = sum(int(a) * x ^ i for i, a in enumerate(bin(c)[2:]))
m = c ^ d
print(int("".join([str(i) for i in list(m)]), 2).to_bytes(100, "big"))

1-800-758-6237

#!/usr/bin/env python3
#
# Polymero
#

# Imports
from Crypto.Cipher import AES
import os, time, random

# Local imports
with open('flag.txt', 'rb') as f:
	FLAG = f.read()
	f.close()


def leak(drip):
	rinds = sorted(random.sample(range(len(drip)+1), 16))

	for i in range(len(rinds)):
		ind  = rinds[i] + i*len(b'*drip*')
		drip = drip[:ind] + b'*drip*' + drip[ind:]

	aes = AES.new(key=server_key, mode=AES.MODE_CTR, nonce=b'NEEDaPLUMBER')
	return aes.encrypt(drip).hex()


server_key = os.urandom(16)

while True:

	print(leak(FLAG))

	time.sleep(1)

很明顯的是 AES-CTR nonce reuse，代表所有的 message 都是 xor 某個相同的 key stream 加密的。首先可以先存個大概 100 筆 ciphertext 下來比較好處理。

leak 函數就是在你的 flag 的一些任意 index 插入 *drip* 這個字串，所以明文中肯定也有許多的 *drip* 出現。

所以先假設說其中至少有一筆 ciphertext 的明文是 flag{ 開頭，由此可以還原出 key stream 的前面五個 bytes。(會有多個 candidates)

之後對於剩下的部分就利用 *drip 後面一定是 * 和 *dri 後面是 p 這兩個去一個一個把剩下的 key stream 還原即可。

from itertools import combinations
import string


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


data = []
with open("output.txt") as f:
    for line in f:
        data.append(bytes.fromhex(line))

good = set(map(ord, string.ascii_letters + string.digits + " {}_*:!"))

kss = set()
flag = b"flag{"
dt = {}
for a, b in combinations(data, r=2):
    tmp = xor(xor(a, b), flag)
    if all(x in good for x in tmp) and xor(a, flag) == xor(b, flag):
        kss.add(xor(a, flag))

for k in kss:
    for _ in range(200):
        for i, ct in enumerate(data):
            pt = xor(k, ct)
            r = pt.replace(b"*drip*", b"")
            if pt.endswith(b"*drip"):
                k = xor(pt + b"*", ct)
                break
            if pt.endswith(b"*dri"):
                k = xor(pt + b"p", ct)
                break
        else:
            break
        if not all(x in good for x in r):
            break
        print(r)

# flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}

Poly-Proof

#!/usr/bin/env python3
#
# Polymero
#

# Imports
import os

# Local imports
with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

HDR = r"""|
|    ________  ________  ___           ___    ___      ________  ________  ________  ________  ________ 
|   |\   __  \|\   __  \|\  \         |\  \  /  /|    |\   __  \|\   __  \|\   __  \|\   __  \|\  _____\
|   \ \  \|\  \ \  \|\  \ \  \        \ \  \/  / /    \ \  \|\  \ \  \|\  \ \  \|\  \ \  \|\  \ \  \__/ 
|    \ \   ____\ \  \\\  \ \  \        \ \    / /      \ \   ____\ \   _  _\ \  \\\  \ \  \\\  \ \   __\
|     \ \  \___|\ \  \\\  \ \  \____    \/  /  /        \ \  \___|\ \  \\  \\ \  \\\  \ \  \\\  \ \  \_|
|      \ \__\    \ \_______\ \_______\__/  / /           \ \__\    \ \__\\ _\\ \_______\ \_______\ \__\ 
|       \|__|     \|_______|\|_______|\___/ /             \|__|     \|__|\|__|\|_______|\|_______|\|__| 
|                                    \|___|/                                
|"""

class Server:
    def __init__(self, difficulty):
        self.difficulty = difficulty
        self.coefficients = None
        self.limit = 8
        self.i = 0
        self.set_up()
        
    def _eval_poly(self, x):
        return sum([ self.coefficients[i] * x**i for i in range(len(self.coefficients)) ])
    
    def _prod(self, intlst):
        ret = 1
        for i in intlst:
            ret *= i
        return ret
        
    def set_up(self, verbose=False):
        print(HDR)
        print("|  To prove to you that I own the flag, I used it to make a polynomial. Challenge me all you want!")
        noise = [ self._prod(list(os.urandom(self.difficulty))) for i in range(len(FLAG)) ]
        self.coefficients = [ noise[i] * FLAG[i] for i in range(len(FLAG)) ]
        
    def accept_challenge(self):
        print("|\n|  Name your challenge (as ASCII string):")
        try:
            user_input = int.from_bytes(str(input("|   >> ")).encode(),'big')
        except ValueError:
            print("|\n|  ERROR - That ain't working... s m h ")
            return
        if user_input == 0:
            print("|\n|  ERROR - You clearly don't know what ZERO-KNOWLEDGE means eh?")
            return
        if user_input <= 0:
            print("|\n|  ERROR - Your clever tricks will not work here, understood?")
            return
        print("|\n|  Here's my commitment: {}".format(self._eval_poly(user_input)))
        self.i += 1
        
    def run(self):
        while self.i < self.limit:
            try:
                self.accept_challenge()
            except:
                break
        if self.i >= self.limit:
            print("|\n|   Are you trying to steal my polynomial or something?")
            print("|   I think I have proven enough to you...")
        print("|\n|\n|  ~ See you back in polynomial time! o/ \n|")


S = Server(15)
S.run()

這題會先把 flag 的每個字元乘上一些 noise 得到多項式係數 $a_i$ 。然後你可以輸入 $r$ 去得到 $f(r)$ ，重複 8 次。

第一個目標是要還原出多項式係數，一個最簡單的做法就是取 $r>\max(a_0,\cdots,a_{n-1})$ ，然後把 $f(r)$ 以 $r$ 進位表示出來就能拿到 $a_i$ 。

不過我當時卻沒想到這個，反而用了一個複雜很多的作法:

B= \begin{bmatrix} -K f(r_1) & \cdots & -K f(r_8) \\ K r_1 & \cdots & K r_8 & 1 \\ K r_1^2 & \cdots & K r_8^2 & 0 & 1 \\ K r_1^3 & \cdots & K r_8^3 & 0 & 0 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{bmatrix}

取一個夠大的常數 $K$ 之後做 LLL 可以找到一個短向量 $(0,\cdots,0,a_0,\cdots,a_{n-1})$ 獲得多項式的係數。

取得多項式係數後也沒辦法直接拿到 flag，但是因為 $a_i=n_i f_i$ ，其中的 $n_i$ 和 $f_i$ 分別是 noise 和 flag。所以就拿多組的 $a_i$ 之後取 gcd 就有機會拿到 $f_i$ 。

不過實際上只能拿到 $f_i$ 的倍數，非常難以得到真正的 $f_i$ ，所以這邊需要利用 flag 本身可能的字元範圍去猜可能的 $f_i$ ，之後再 guess flag 是什麼東西。因為 flag 本身是 leetspeak 所以有點難猜...

from pwn import remote, process
import string
import random


def get_pair(io):
    r = "".join(random.sample(string.ascii_letters, 16)).encode()
    io.sendlineafter(b"|   >> ", r)
    r = int.from_bytes(r, "big")
    io.recvuntil(b"commitment: ")
    fr = int(io.recvlineS().strip())
    return r, fr


def get_params():
    io = remote("ctf.k3rn3l4rmy.com", 2232)
    pairs = [get_pair(io) for _ in range(8)]
    io.close()
    rs, frs = zip(*pairs)
    return rs, frs


def solve_coefs(rs, frs, n):
    assert len(rs) == 8
    M = matrix([[r ^ i for i in range(n)] for r in rs]).T
    M = M.augment(matrix.identity(n))
    M = matrix([-fr for fr in frs] + [0] * n).stack(M)
    M[:, :8] *= 2 ^ 128

    for row in M.LLL():
        if all(x == 0 for x in row[:8]):
            return row[8:]


def find_possible(x):
    flagchrs = ("{_}" + string.ascii_lowercase + string.digits).encode()
    return [y for y in flagchrs if x % y == 0]


n = 101  # flag length
# flag = [0] * n
# fmt: off
flag = [408, 648, 776, 206, 984, 872, 416, 484, 1176, 204, 1520, 792, 968, 396, 432, 204, 380, 968, 192, 234, 2736, 190, 460, 408, 1584, 456, 204, 232, 920, 380, 104, 220, 800, 190, 920, 52, 220, 196, 464, 588, 488, 408, 1140, 484, 96, 234, 1368, 760, 196, 220, 448, 936, 464, 920, 190, 96, 5472, 2280, 832, 832, 460, 380, 464, 832, 196, 460, 380, 448, 2496, 1320, 800, 204, 436, 196, 396, 760, 880, 192, 928, 760, 464, 208, 936, 412, 416, 464, 190, 968, 192, 936, 380, 208, 440, 242, 1392, 2496, 294, 880, 2472, 500, 240]
# fmt: on
while True:
    rs, frs = get_params()
    noiseflag = solve_coefs(rs, frs, n)
    for i in range(n):
        flag[i] = gcd(flag[i], noiseflag[i])
    print(flag)
    fflag = [
        "".join(map(chr, p)) if len((p := find_possible(x))) <= 5 else x for x in flag
    ]
    print(fflag)
    if all(0 <= x < 256 for x in flag):
        print(bytes(flag))
        break

# by guessing leetspeak...
# flag{m4yb3_cycl3_y0ur_s3cr3ts_4nd_s4n1t1z3_y0ur_1nputs_0r_h4s_th1s_p4nd3m1c_n0t_t4ught_y0u_4nyth1ng}

Non-Square Freedom 1

#!/usr/bin/env python3
#
# Polymero
#

# Imports
from Crypto.Util.number import getPrime
import os

# Local imports
with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

# Key gen
P = getPrime(512//8)
Q = getPrime(256)
R = getPrime(256)
N = P**8 * Q * R
E = 0x10001

def pad_easy(m):
    m <<= (512//8)
    m += (-(m % (P**2)) % P)
    return m

# Pad FLAG
M = pad_easy(int.from_bytes(FLAG,'big'))
print('M < N    :',M < N)
print('M < P**8 :',M < (P**8))
print('M < Q*R  :',M < (Q*R))

# Encrypt FLAG
C = pow(M,E,N)
print('\nn =',N)
print('e =',E)
print('c =',C)

# Hint
F = P**7 * (P-1) * (Q-1) * (R-1)
D = inverse(E,F)
print('\nD(C) =',pow(C,D,N))

#----------------------------------------------------
#                       Output
#----------------------------------------------------
# M < N    : True
# M < P**8 : True
# M < Q*R  : True
#
# n = 68410735253478047532669195609897926895002715632943461448660159313126496660033080937734557748701577020593482441014012783126085444004682764336220752851098517881202476417639649807333810261708210761333918442034275018088771547499619393557995773550772279857842207065696251926349053195423917250334982174308578108707
# e = 65537
# c = 4776006201999857533937746330553026200220638488579394063956998522022062232921285860886801454955588545654394710104334517021340109545003304904641820637316671869512340501549190724859489875329025743780939742424765825407663239591228764211985406490810832049380427145964590612241379808722737688823830921988891019862
#
# D(C) = 58324527381741086207181449678831242444903897671571344216578285287377618832939516678686212825798172668450906644065483369735063383237979049248667084304630968896854046853486000780081390375682767386163384705607552367796490630893227401487357088304270489873369870382871693215188248166759293149916320915248800905458
#

一個奇怪的 RSA，令 D(C) 為 $k$ 之後可以知道 $k^e \equiv c \pmod{N}$ ，但是 $k \neq m$ 。

可以從 padding 函數觀察到 $m \equiv 0 \pmod{p}$ ，所以從 $\gcd(k,n)$ 會拿到 $p^8$ ，之後可以拿到 $qr=n/p^8$ 。把 $k$ 模 $qr$ 之後就很神奇的得到的我們要的 $m$ 。

其實我也不太清楚這題究竟是怎麼回事...。詳細的解釋可以看作者的 WriteUp。

Tick Tock

#!/usr/bin/env python3
#
# Polymero
#

# Imports
from Crypto.Util.number import getPrime, isPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from random import randint
from hashlib import sha256


# Local imports
with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

assert len(FLAG) % 8 == 0


# Helper functions
def legendre_symbol(a, p):
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

def modular_sqrt(a, p):
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return p
    elif p % 4 == 3:
        return pow(a, (p + 1) // 4, p)
    s = p - 1
    e = 0
    while s % 2 == 0:
        s //= 2
        e += 1
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1
    x = pow(a, (s + 1) // 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e
    while True:
        t = b
        m = 0
        for m in range(r):
            if t == 1:
                break
            t = pow(t, 2, p)
        if m == 0:
            return x
        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m


# TickTock class
class TickTock:
    def __init__(self, x, y, P):
        self.x = x
        self.y = y
        self.P = P
        assert self.is_on_curve()
        
    def __repr__(self):
        return '({}, {}) over {}'.format(self.x, self.y, self.P)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.P == other.P
        
    def is_on_curve(self):
        return (self.x*self.x + self.y*self.y) % self.P == 1
    
    def add(self, other):
        assert self.P == other.P
        x3 = (self.x * other.y + self.y * other.x) % self.P
        y3 = (self.y * other.y - self.x * other.x) % self.P
        return self.__class__(x3, y3, self.P)
    
    def mult(self, k):
        ret = self.__class__(0, 1, self.P)
        base = self.__class__(self.x, self.y, self.P)
        while k:
            if k & 1:
                ret = ret.add(base)
            base = base.add(base)
            k >>= 1
        return ret

def lift_x(x, P, ybit=0):
    y = modular_sqrt((1 - x*x) % P, P)
    if ybit:
        y = (-y) % P
    return TickTock(x, y, P)

def domain_gen(bits):
    while True:
        q = getPrime(bits)
        if isPrime(4*q + 1):
            P = 4*q + 1
            break
    while True:
        i = randint(2, P)
        try:
            G = lift_x(i, P)
            G = G.mult(4)
            break
        except: continue
    return P, G

def key_gen():
    sk = randint(2, P-1)
    pk = G.mult(sk)
    return sk, pk

def key_derivation(point):
    dig1 = sha256(b'x::' + str(point).encode()).digest() 
    dig2 = sha256(b'y::' + str(point).encode()).digest() 
    return sha256(dig1 + dig2 + b'::key_derivation').digest()


# Challenge
flagbits = [FLAG[i:i+len(FLAG)//8] for i in range(0,len(FLAG),len(FLAG)//8)]

for i in range(8):

    print('# Exchange {}:'.format(i+1))

    P, G = domain_gen(48)

    print('\nP =', P)
    print('G = ({}, {})'.format(G.x, G.y))

    alice_sk, alice_pk = key_gen()
    bobby_sk, bobby_pk = key_gen()

    assert alice_pk.mult(bobby_sk) == bobby_pk.mult(alice_sk)

    print('\nA_pk = ({}, {})'.format(alice_pk.x, alice_pk.y))
    print('B_pk = ({}, {})'.format(bobby_pk.x, bobby_pk.y))

    key = key_derivation(alice_pk.mult(bobby_sk))
    cip = AES.new(key=key, mode=AES.MODE_CBC)
    enc = cip.iv + cip.encrypt(pad(flagbits[i], 16))

    print('\nflagbit_{} = "{}"'.format(i+1, enc.hex()))
    print('\n\n\n')

這題有個在一個特殊 group 上的 diffie hellman，需要解開上面的 DLP 才能拿到 key 去解密 flag。

此題因為是在 writeup submission 的範圍中，大概 11/17 的時候我才能公開這題的解法。

*MathyOracle

比賽中沒解，後來看到解法覺得值得解

print('Find my number N, and I will give you the flag.')
def f(N,k):
    while min(N,k)>0:
        if k>N: N,k = k,N
        N%=k
    return max(N,k)
import random
N = random.getrandbits(512)
for i in range(600):
    print(f"Try #{i+1}: ")
    k = input(f'Enter k: ')
    l = input(f'Enter l: ')
    try:
        k= int(k)
        assert 0<k<pow(10,500)
        l= int(l)
        assert 0<l<pow(10,500)
    except:
        print('Invalid input. Exiting...')
        quit()
    print(f'f(N+l,k) = {f(int(N+l),k)}\n')
guess = input('What is N?')
if str(N)==guess:
    print(open('flag.txt').read().strip())
else:
    print('Wrong answer. The number was '+str(N))

簡單來說有個 $n$ ，然後你可以指定任意 $k,l>0$ 讓它計算 $\gcd(n+l,k)$ ，目標要在 600 次的 query 內把 $n$ 還原才行。

如果可以 $k=l=0$ 的話那麼一次就能取得 $n$ ，因為 $\gcd(n,0)=n$ 。

這題的題目介紹有說 My friend told me I need LSB to solve this, but I don't do drugs! Can you solve it for me instead?，關鍵在於 LSB 的部份。

$k=2$ 的時候可以知道 $n+l$ 的 parity，也就是能拿到 $n$ 的 LSB。有 LSB 的時候可以透過改 $l$ 把 $n$ 的已知部分都清成 $0$ ，然後 $k=4$ 就能取得第二個 bit，這樣以此類推即可。

只是這個方法會遇到的問題是 $l<0$ ，不過只要把方法稍微小改一下即可。假設目前已知 $n$ 的底下 $i-1$ 個 bits $n'$ ，目前想知道的是第 $i$ bits，那取 $l=2^i-n'$ 的話 $n+l$ 的第 $i$ 就會被 flip。

假設原本第 $i$ 個 bits 是 $1$ ，那麼 $n+l$ 的 lowest $i$ bits 都會是 0，反之只有 $i-1$ bits 是 0。所以取 $k=2^{i+1}$ 時如果 $\gcd(n+l,k)=k$ 就代表 bit $i$ 是 1，反之為 0。

from pwn import process

io = process(["python", "main.py"])


def get(k, l):
    io.sendlineafter(b"k: ", str(k).encode())
    io.sendlineafter(b"l: ", str(l).encode())
    io.recvuntil(b"= ")
    return int(io.recvlineS().strip())


n = 0
for i in range(600):
    l = (1 << i) - n
    k = 1 << (i + 1)
    if get(k, l) == k:
        n += 1 << i
    print(n)

io.sendlineafter(b"N?", str(n).encode())
print(io.recvlineS())

另解

這個是在 Discord 中看到的不同作法，取 $k=2 \cdot 3 \cdot 5 \cdots 599$ ，然後對於 $l=1$ 到 $600$ 都計算 $\gcd(n+l,k)$ 。如果 $\gcd(n+l,k)$ 可以被某個質數 $p$ 整除的話就知道 $n \equiv -l \pmod{p}$ ，蒐集到很多的等式之後 CRT 求出答案。

Pryby#

Pascal RSA#

Poly Expo go BRRRRR#

1-800-758-6237#

Poly-Proof#

Non-Square Freedom 1#

Tick Tock#

*MathyOracle#

另解#