K3RN3L CTF 2021 WriteUps

發表於 2021-11-14

分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

For this CTF, I only solved some Crypto problems when I had free time. Since there were quite a few interesting problems, I decided to document them. The team name used this time was peko, and we ranked 31st.

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

It can be seen that it uses primes as binary representation, so we decompose it and restore the bits to get the 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}')

In this RSA problem, $d$ is obtained using the binary representation of the $p$ -th row of Pascal's triangle modulo 2. By looking up related information, we can find Sierpiński's triangle, and its sequence converted to numbers is also available on OEIS: A001317

So, using the general formula provided there to find $d$ , we can get the 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
#

This problem looks like RSA, except that $N$ is converted to a polynomial $f(x)$ in $\mathbb{F}_2$ , and subsequent operations are performed in $\mathbb{F}_2[x]/f(x)$ . The flag itself is also converted to a polynomial in that ring, encrypted by raising to the $e$ -th power, and then converted back to a number.

It can be found that $f(x)$ itself is factorable, so we need to find a way to determine its order and then obtain $d$ to decrypt. By looking up information, we can find the formula here.

For an irreducible polynomial $f(x)$ of degree $d$ over $\mathbb{F}_k$ ,

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

And for any polynomial,

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

With these two relationships, it is sufficient to calculate $\varphi(f(x))$ , and then find $d \equiv e^{-1} \pmod{\varphi(f(x))}$ to decrypt.

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)

It is clearly an AES-CTR nonce reuse, meaning all messages are encrypted by XORing with the same keystream. First, we can store about 100 ciphertexts for easier processing.

The leak function inserts the string *drip* at some arbitrary index in your flag, so there must be many occurrences of *drip* in the plaintext.

Assuming that at least one of the ciphertexts starts with flag{, we can recover the first five bytes of the keystream (there will be multiple candidates).

For the remaining part, we use the fact that *drip is followed by * and *dri is followed by p to recover the rest of the keystream byte by byte.

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()

In this problem, each character of the flag is multiplied by some noise to get the polynomial coefficients $a_i$ . You can input $r$ to get $f(r)$ , repeating this 8 times.

The first goal is to recover the polynomial coefficients. A simple method is to choose $r > \max(a_0, \cdots, a_{n-1})$ , then represent $f(r)$ in base $r$ to obtain $a_i$ .

However, I didn't think of this at the time and used a much more complicated method:

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}

By choosing a sufficiently large constant $K$ and using LLL, we can find a short vector $(0, \cdots, 0, a_0, \cdots, a_{n-1})$ to obtain the polynomial coefficients.

After obtaining the polynomial coefficients, we still can't directly get the flag. Since $a_i = n_i f_i$ , where $n_i$ and $f_i$ are noise and flag respectively, we can take multiple sets of $a_i$ and find the gcd to potentially get $f_i$ .

However, in practice, we can only get multiples of $f_i$ , making it very difficult to obtain the actual $f_i$ . Therefore, we need to guess the possible range of characters in the flag and then guess what the flag might be. Since the flag itself is in leetspeak, it is quite challenging to guess...

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
#

A strange RSA problem. Let D(C) be $k$ , then we know $k^e \equiv c \pmod{N}$ , but $k \neq m$ .

From the padding function, we can observe that $m \equiv 0 \pmod{p}$ , so from $\gcd(k, n)$ , we get $p^8$ , and then we can obtain $qr = n/p^8$ . By taking $k$ modulo $qr$ , we magically get the $m$ we need.

I'm not entirely sure what is going on with this problem... For a detailed explanation, you can refer to the author's 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')

This problem involves a Diffie-Hellman on a special group, and we need to solve the DLP on it to get the key to decrypt the flag.

Since this problem is within the writeup submission range, I can only disclose the solution around 11/17.

*MathyOracle

Didn't solve during the competition, but found the solution later and thought it was worth solving

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))

In short, there is an $n$ , and you can specify any $k, l > 0$ to calculate $\gcd(n + l, k)$ . The goal is to recover $n$ within 600 queries.

If $k = l = 0$ , we can get $n$ in one query because $\gcd(n, 0) = n$ .

The problem introduction mentions My friend told me I need LSB to solve this, but I don't do drugs! Can you solve it for me instead? The key lies in the LSB part.

When $k = 2$ , we can determine the parity of $n + l$ , which gives us the LSB of $n$ . With the LSB, we can modify $l$ to clear the known part of $n$ to $0$ , and then $k = 4$ to get the second bit, and so on.

However, this method encounters the problem of $l < 0$ , but we can slightly modify the method. Suppose we know the lower $i-1$ bits of $n$ as $n'$ , and we want to know the $i$ -th bit. By choosing $l = 2^i - n'$ , the $i$ -th bit of $n + l$ will be flipped.

If the original $i$ -th bit is $1$ , then the lowest $i$ bits of $n + l$ will be 0; otherwise, only the $i-1$ bits will be 0. So, when $k = 2^{i+1}$ , if $\gcd(n + l, k) = k$ , the $i$ -th bit is 1; otherwise, it is 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())

Alternative Solution

This is a different approach seen on Discord. Choose $k = 2 \cdot 3 \cdot 5 \cdots 599$ , and then calculate $\gcd(n + l, k)$ for $l = 1$ to $600$ . If $\gcd(n + l, k)$ is divisible by a prime $p$ , we know $n \equiv -l \pmod{p}$ . After collecting many such equations, use CRT to find the answer.

Pryby#

Pascal RSA#

Poly Expo go BRRRRR#

1-800-758-6237#

Poly-Proof#

Non-Square Freedom 1#

Tick Tock#

*MathyOracle#

Alternative Solution#