NepCTF2025

写在前面

放假来的第一场大型在线赛，来复现一下Crypto方向的三道题，感谢群里的随意师傅与Painting师傅给我相关指点

NepSign

题面

from gmssl import sm3
from random import SystemRandom
from ast import literal_eval
import os
flag = os.environ["FLAG"]
def SM3(data):
    d = [i for i in data]
    h = sm3.sm3_hash(d)
    return h
def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        data = bytes.fromhex(SM3(data))
    return data.hex()[:bits // 4]


class Nepsign():
    def __init__(self):
        self.n = 256
        self.hex_symbols = '0123456789abcdef'
        self.keygen()

    def keygen(self):
        rng = SystemRandom()
        self.sk = [rng.randbytes(32) for _ in range(48)]
        self.pk = [SM3_n(self.sk[_], 255, self.n) for _ in range(48)] 
        return self.sk, self.pk

    def sign(self, msg, sk=None): 
        sk = sk if sk else self.sk  
        m = SM3(msg) 
        m_bin = bin(int(m, 16))[2:].zfill(256) 
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)]
        step = [0] * 48;
        qq = [0] * 48 
        for i in range(32):
            step[i] = a[i] 
            qq[i] = SM3_n(sk[i], step[i])
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]:
                    sum[i] += j
            step[i + 32] = sum[i] % 255
            qq[i + 32] = SM3_n(sk[i + 32], step[i + 32]) 
        return [i for i in qq]

    def verify(self, msg, qq, pk=None):
        qq = [bytes.fromhex(i) for i in qq]
        pk = pk if pk else self.pk
        m = SM3(msg)
        m_bin = bin(int(m, 16))[2:].zfill(256)
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)]
        step = [0] * 48;
        pk_ = [0] * 48
        for i in range(32):
            step[i] = a[i]
            pk_[i] = SM3_n(qq[i], 255 - step[i])
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]:
                    sum[i] += j
            step[i + 32] = sum[i] % 255
            pk_[i + 32] = SM3_n(qq[i + 32], 255 - step[i + 32]) 
        return True if pk_ == pk else False


print('initializing...')
Sign = Nepsign()
while 1:
    match int(input('> ')):
        case 1:
            msg = bytes.fromhex(input('msg: ')) 
            if msg != b'happy for NepCTF 2025': 
                print(Sign.sign(msg))
            else:
                print("You can't do that")
        case 2:
            qq = literal_eval(input('give me a qq: '))
            if Sign.verify(b'happy for NepCTF 2025', qq): 
                print(flag)

题面给了我们一个SM3的签名系统

密钥生成

先生成一组48个32位的私钥，然后进行255次SM3哈希得到公钥，即

签名

根据我们传入的明文计算它的哈希,转换出一个48整数的Step数组，根据这个来计算我们的签名 可知这里的会是一个含有48个元素的数组

验签

传入明文和签名,先计算,然后去验证是否有

漏洞

注意我们生成签名的过程，是完全可控的，我们可以随机生成，来让某一个位的取到0，那么我们的 就获得了这里的私钥，我们如法炮制即可获得48个私钥 然后就随便签名了，

exp

from pwn import *
from gmssl import sm3
from ast import literal_eval
import pickle
import os
from collections import defaultdict

# --- 配置 ---
CACHE_FILE = "sm3_cache.pkl"
HOST = "nepctf31-d4fq-qii4-jfwh-dk9fj2dqi154.nepctf.com"
PORT = 443

# --- 缓存系统 ---
class SM3Cache:
    def __init__(self):
        self.step_cache = defaultdict(dict)  # {step_index: {step_value: msg}}
        self.sum_cache = defaultdict(dict)   # {hex_char: {sum_mod: msg}}
        
        if os.path.exists(CACHE_FILE):
            with open(CACHE_FILE, 'rb') as f:
                self.step_cache, self.sum_cache = pickle.load(f)
    
    def save(self):
        with open(CACHE_FILE, 'wb') as f:
            pickle.dump((self.step_cache, self.sum_cache), f)
    
    def get_step_msg(self, index, value):
        return self.step_cache[index].get(value)
    
    def add_step_msg(self, index, value, msg):
        self.step_cache[index][value] = msg
        self.save()
    
    def get_sum_msg(self, char, mod):
        return self.sum_cache[char].get(mod)
    
    def add_sum_msg(self, char, mod, msg):
        self.sum_cache[char][mod] = msg
        self.save()

# --- 核心函数 ---
def SM3_hash(data):
    d = bytearray(data)
    return sm3.sm3_hash(d)

def SM3_n(data, n=1, bits=256):
    if not isinstance(data, bytes):
        data = bytes.fromhex(data)
    for _ in range(n):
        data = bytes.fromhex(SM3_hash(data))
    return data.hex()[:bits//4]

def calculate_steps(msg):
    m = SM3_hash(msg)
    m_bin = bin(int(m, 16))[2:].zfill(256)
    a = [int(m_bin[8*i:8*i+8], 2) for i in range(32)]
    
    step = [0]*48
    for i in range(32):
        step[i] = a[i]
    
    hex_symbols = '0123456789abcdef'
    for i in range(16):
        sum_val = sum(j+1 for j in range(64) if m[j] == hex_symbols[i])
        step[i+32] = sum_val % 255
    
    return step, m

# --- 攻击逻辑 ---
def get_pk(p):
    log.info("Recovering public key...")
    p.sendlineafter(b'> ', b'1')
    p.sendlineafter(b'msg: ', b'get_pk'.hex().encode())
    qq = literal_eval(p.recvline().decode())
    step, _ = calculate_steps(b'get_pk')
    return [SM3_n(bytes.fromhex(qq[i]), 255-step[i]) for i in range(48)]

def recover_sk(p, pk, cache):
    sk = {}
    hex_symbols = '0123456789abcdef'
    
    # 恢复sk[0..31] (基于step值)
    for i in range(32):
        if cached_msg := cache.get_step_msg(i, 0):
            log.info(f"Using cached message for sk[{i}]")
            msg = cached_msg
        else:
            log.info(f"Finding message for sk[{i}] (step[{i}]=0)...")
            msg = find_msg_with_condition(
                p, 
                condition=lambda m: calculate_steps(m)[0][i] == 0,
                desc=f"step[{i}]=0"
            )
            cache.add_step_msg(i, 0, msg)
        
        sk[i] = get_sk_element(p, i, msg)
        log.success(f"Recovered sk[{i}][:16]: {sk[i][:16]}...")
    
    # 恢复sk[32..47] (基于sum值)
    for i in range(16):
        target = i+32
        char = hex_symbols[i]
        
        if cached_msg := cache.get_sum_msg(char, 0):
            log.info(f"Using cached message for sk[{target}]")
            msg = cached_msg
        else:
            log.info(f"Finding message for sk[{target}] (sum[{char}]%255=0)...")
            msg = find_msg_with_condition(
                p,
                condition=lambda m: check_sum_condition(m, char, 0),
                desc=f"sum[{char}]%255=0"
            )
            cache.add_sum_msg(char, 0, msg)
        
        sk[target] = get_sk_element(p, target, msg)
        log.success(f"Recovered sk[{target}][:16]: {sk[target][:16]}...")
    
    return sk

def find_msg_with_condition(p, condition, desc="", max_tries=100000):
    nonce = 0
    while nonce < max_tries:
        msg = str(nonce).encode()
        if condition(msg):
            return msg
        nonce += 1
        if nonce % 1000 == 0:
            log.info(f"Tried {nonce} messages for {desc}")
    raise Exception(f"Failed to find message for {desc} after {max_tries} tries")

def check_sum_condition(msg, char, target_mod):
    m = SM3_hash(msg)
    sum_val = sum(i+1 for i in range(64) if m[i] == char)
    return sum_val % 255 == target_mod

def get_sk_element(p, index, msg):
    p.sendlineafter(b'> ', b'1')
    p.sendlineafter(b'msg: ', msg.hex().encode())
    return literal_eval(p.recvline().decode())[index]

def verify_and_submit(p, pk, sk):
    log.info("Verifying and submitting signature...")
    target_msg = b'happy for NepCTF 2025'
    step, _ = calculate_steps(target_msg)
    
    # 生成签名
    qq = [SM3_n(bytes.fromhex(sk[i]), step[i]) for i in range(48)]
    
    # 本地验证
    pk_ = [SM3_n(bytes.fromhex(qq[i]), 255-step[i]) for i in range(48)]
    if pk_ != pk:
        log.error("Verification failed! Mismatches:")
        for i in range(48):
            if pk_[i] != pk[i]:
                log.error(f"Index {i}: {pk_[i]} vs {pk[i]}")
        return False
    
    # 提交签名
    p.sendlineafter(b'> ', b'2')
    p.sendlineafter(b'give me a qq: ', str(qq).encode())
    
    try:
        flag = p.recvall(timeout=10).decode().strip()
        if "NepCTF" in flag:
            log.success(f"Flag: {flag}")
            return True
        log.error(f"Unexpected response: {flag}")
    except:
        log.error("Timeout while waiting for flag")
    return False

def main():
    context.log_level = 'info'
    cache = SM3Cache()
    
    try:
        p = remote(HOST, PORT, ssl=True)
        p.recvuntil(b'initializing...\n')
        
        pk = get_pk(p)
        sk = recover_sk(p, pk, cache)
        
        if not verify_and_submit(p, pk, sk):
            log.error("Attack failed")
        
    except Exception as e:
        log.error(f"Error: {e}")
    finally:
        p.close()
        cache.save()

if __name__ == "__main__":
    main()

成功签到

LatticeBros

题干

# 已知α的极小多项式为三次多项式f(x),即f(α)=0,且α≈54236.606188881754809671280151541781895183337725393
# 上述极小多项式的常数项为a0

from secret import a0,alpha
import gmpy2
from Crypto.Util.number import long_to_bytes
import random
from math import sqrt,log2

d=981020902672546902438782010902608140583199504862558032616415
p = d - a0

k=sqrt(log2(p))+log2(log2(p))
B = 2**30
assert B < p/2**k

m = 30
assert m > 2*sqrt(log2(p))

samples = []
betas = []

f = open("samples.txt",'w')
for _ in range(m):
    t = random.randint(1, p-1)
    beta = random.randint(-B + 1, B - 1)
    a = (t * alpha - beta) % p
    samples.append((t, a))
    betas.append(beta)

f.write(str(samples))

for i in range(0,30):
    assert (betas[i]-samples[i][0]*alpha+samples[i][1])%p == 0

#flag = long_to_bytes(alpha)

1. 第一部分

根据已有的根来恢复极小多项式，我们想求 可以构造格 这边可以给格子的最后一列乘一个常数来消去小数点的影响，测试取即可

exp

# Part1 求a0

alpha_str = "54236.606188881754809671280151541781895183337725393"
alpha = 54236.606188881754809671280151541781895183337725393
C = 10^6
M = Matrix(ZZ, [
    [1, 0, 0, round(alpha^3 * C)],
    [0, 1, 0, round(alpha^2 * C)],
    [0, 0, 1, round(alpha * C)],
    [0, 0, 0, round(C)]
])

L = M.BKZ()
print(L)
v = list(L[0])
v = [-(i) for i in v]
print(v)
a2 = v[1]
a1 = v[2]
R = RealField(300)
alpha = R(alpha)
a0 = - (alpha^3 + a2 * alpha^2 + a1 * alpha)
print(a0)
# -1.59534088683654000000000000000000000000000000000005293081713352531164797502219789969605504e14
a0=-159534088683654
R.<x> = PolynomialRing(R)
f = x^3 + a2*x^2 + a1 * x + a0
res = f.roots()
print(res)
# [(54236.6061888817548096712801515417818951833377253924001835852143806250916798292087977394045, 1)]

2. 第二部分

LHNP问题

给出30个式子 其中是30比特小量，我们要恢复出

可以把方程写成 构造有理格 有 取 ，是的上界

的行列式大致是 最小向量上界为 大约能有200比特，足够规约找到这里最小的向量

exp如下

# Part2
from Crypto.Util.number import *
import ast
a0=-159534088683654
d=981020902672546902438782010902608140583199504862558032616415
p = d - a0
k=sqrt(log(p,2))+log(log(p,2),2)
B = 2**30
assert B < p/2**k

m = 30
assert m > 2*sqrt(log(p,2))

t = []
a = []
with open("samples.txt", "r") as f:
    samples = f.read()
    samples = ast.literal_eval(samples)
for i in samples:
    i = list(i)
    t.append(i[0])
    a.append(i[1])

# ----------------------------HNP-----------------------------------------------
length = len(t)
K = 2^30
R = 2^30

M = Matrix(QQ, length + 2, length + 2)
for i in range(length):
    M[i, i] = p
    M[length, i] = t[i]
    M[length + 1, i] = a[i]
M[length, length] = QQ(1 / p)
M[length + 1, length + 1] = R
L = M.LLL()
print(L)

# ---------------------------Verify-------------------------------------------
v = list(L[1])
beta = v[:-2]
P = QQ(p)
xx = v[-2]
alpha = ((P * xx // K % p))
print(beta)
print(alpha)
for i in range(30):
    assert -B + 1 < beta[i] < B - 1
    assert (a[i] + beta[i] - t[i] * alpha) % p == 0

print(f"Verified")
print(alpha)
print(long_to_bytes(alpha))
# NepCTF{c0ngr4tv!at1Ons!!}

这一步的LLL操作我们可以找出正确的,特别注意我们这边规约出的值是负数，那就直接计算后对取模，而不要取绝对值！

ezRSA2

题面

from Crypto.Util.number import getStrongPrime, getRandomNBitInteger, GCD, inverse, long_to_bytes, bytes_to_long, sieve_base
from flag import flag


def gen_parameters(gamma=0.33, beta=0.33):
    p = getStrongPrime(1024)
    q = getStrongPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)
    while True:
        d = getRandomNBitInteger(int(2048*beta))
        if GCD(d, phi) == 1:
            break
    e = inverse(d, phi)
    
    hints = []
    M = 1
    for i in range(1, len(sieve_base)):
        li = sieve_base[i]
        hints.append(d%li)
        M *= li
        if M.bit_length() >= 1024*gamma:
            break
    
    return e, N, hints



def main():
    e,N,hints = gen_parameters()
    print(f'e={hex(e)}')
    print(f'N={hex(N)}\n')
    print(f'hints={hints}\n')
    
    flag_prefix = b'NepCTF{'
    assert flag.startswith(flag_prefix)
    assert flag.endswith(b'}')
    
    pt = bytes_to_long(flag[len(flag_prefix):-1])
    ct = pow(pt, e, N)
    print(f'ct={hex(ct)}')
    
main()


"""
e=
N=
hints=[]
ct=
"""

我们生成的大约是,和经典的Boneh-Durfee的攻击界限有点差距，但是给了模一系列小素数的结果，也就是说我们还能恢复一些的比特

我们设所有的小素数的积是,我们由hint能恢复出 写成等式 我们再带入这里的私钥式子 也有 令 这里有三个未知数 ,我们可以左右模一个，就能得到 这里我们要解的大致1025位，大约300位，相对2300位的都相当小

打一发二元coppersmith即可，

exp

#sage

import itertools

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	if isinstance(f, Polynomial):
		x, = polygens(f.base_ring(), f.variable_name(), 1)
		f = f(x)

	R = f.base_ring()
	N = R.cardinality()
	
	# f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)

	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)

	B, monomials = G.coefficient_matrix()
	monomials = vector(monomials)

	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)

	B = B.dense_matrix().LLL()

	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)

	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots

	return []


e = 0x73915608ed64c9cf1a2279684cab4f4a78fba229d45d4f860971a241481363470a19cb0dc0d00f816b5befdaca017cf71483e96ef17b36179012f5194a0e6bf481bb06c2644f74c6812efb65d05c00631f282d6aa55c0bc140a1830b95a1cf4b6024cb0db53f2c2189897c41f22e2eec773723f531ec4bfa537fae6de5fe480cf46fe17850f7eb47df08194d95db3d26ac923b26e110ee645239ab586bbc546ddc5906f280a106edbb727ccb05536b5a3f5c0ebcf865c95ce58be54f7f3547aa53baa218b0dfa98e42d925fa341e45f94a3b16b0c83802660c7f34de3336cb21f219073cf8e9f5e39d47f0a9a9ee7c255f09a6add9a2f7a47960f4a853183d29
N = 0xba8956e81394f3f1265ca5d9c4ad1ab0078bb43c4b80a231ab2cc62246ae45f66a562252622aed2cbbfc08647ef2fec0f97a632bf2242845f4b3af0c427cec3d90f42e90278a5a0feeed0922a8cd2278074ac54e9cfc0e96ff68f8d8f266dd87dc1cc59c2895ec884de2022311767f6a9a7e0bd288c79620e28b83bb3c8d8ad1047c839d6ccf5544eaf434a5f00b951769ab3121298d04b63a162757beb3d49917cd0c9e02ee1ac29398c8130961d5a2f2833aba1e538edb7bb97071f40fae543d1622f0c9206c6d4d8abb2ac1b93ebfb603c2f3a909ede357ade4043550fe540d13a4e87db8d731fe130f15a43a1a00364f5da2d87f7b660c3a04e734218a11
hints = [1, 3, 0, 3, 9, 16, 10, 14, 5, 11, 21, 18, 30, 30, 38, 2, 20, 62, 66, 1, 22, 56, 41, 13, 78, 59, 51, 6, 57, 117, 73, 75, 96, 112, 50, 93, 158, 97, 146, 8, 65, 96, 186, 161, 90, 131, 46, 32, 140, 133, 50, 43, 151, 234]
ct = 0x101b284ad196b5bbd3d3df00a7d3577caeb29c681bdd122582b705afc671febf45d4f3786640e55aadd6a31ecc49175f97b772720f1735f8555f768b137a4643cd6958f80a3dfca4d0270ad463d6dde93429940bd2abb5ad8408b0906fa8d776544a1c50cc0d95939bef4c3fb64d0b52dca81ff0f244fc265bfc0bc147435d05f8f1a146e963a1403b3c123b4d6e73d1fd897109995009be1673212607f0ea7ae33d23f3158448b05c28ea6636382eee9436c4a6c09023ead7182ecd55ac73a68d458d726e1abc208810468591e63f4b4c2c1f3ce27c4800b52f7421ccab432c03e88b3b255740d719e40e0226eabb7633d97ed210e32071e2ac36ed17ef442e

num_hints = len(hints)
sieve_base = list(sieve_base)
primes = sieve_base[1 : num_hints + 1]
M = product(primes)
d0 = crt(hints, primes)

R.<k,s> = PolynomialRing(Zmod(e*M))
f = e*d0 - 1 - k * (N - s + 1)
res = small_roots(f,(2^676,2^1025),m=1,d=2)
# print(res)
# res = list(res)
k = 81654615013062315740859648077669041820032254119133930508020259262868139640323751053386808815603259330292010187040327207703579843971426978151927033372711655537974461264685966709101578503364634863703748863
s = 307418535695879466735463624869957924354358665052136409248678026715718383427120772212039629998693207855281708171850879171131527744317839878812415135610115774273232848128353184128891514282686549164628675031032302196224590402569695631086177519084924289711604045185861705566454491785664136393955640722211793934882
# print(s.bit_length())

# p = var('p')
# eq = p + N / p - s
# result = solve(eq, p)
# print(result)
p = 162568707874348757830017981324054244343649185213197403637567049635272523397583872953595028729502893337750180312800896062635050332212128836106889628645625189460561837738620947057144783601425723834152966458923355830383900722816802076822113540755216842480068493842631250088527236409536028527544211599757688872629
assert N % p== 0
q = N // p
phi = (p-1)*(q-1)
d = inverse_mod(e,phi)
print(b"NepCTF{" + long_to_bytes(pow(ct,d,N)) + b"}")#sage

import itertools

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	if isinstance(f, Polynomial):
		x, = polygens(f.base_ring(), f.variable_name(), 1)
		f = f(x)

	R = f.base_ring()
	N = R.cardinality()
	
	# f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)

	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)

	B, monomials = G.coefficient_matrix()
	monomials = vector(monomials)

	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)

	B = B.dense_matrix().LLL()

	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)

	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots

	return []


e = 0x73915608ed64c9cf1a2279684cab4f4a78fba229d45d4f860971a241481363470a19cb0dc0d00f816b5befdaca017cf71483e96ef17b36179012f5194a0e6bf481bb06c2644f74c6812efb65d05c00631f282d6aa55c0bc140a1830b95a1cf4b6024cb0db53f2c2189897c41f22e2eec773723f531ec4bfa537fae6de5fe480cf46fe17850f7eb47df08194d95db3d26ac923b26e110ee645239ab586bbc546ddc5906f280a106edbb727ccb05536b5a3f5c0ebcf865c95ce58be54f7f3547aa53baa218b0dfa98e42d925fa341e45f94a3b16b0c83802660c7f34de3336cb21f219073cf8e9f5e39d47f0a9a9ee7c255f09a6add9a2f7a47960f4a853183d29
N = 0xba8956e81394f3f1265ca5d9c4ad1ab0078bb43c4b80a231ab2cc62246ae45f66a562252622aed2cbbfc08647ef2fec0f97a632bf2242845f4b3af0c427cec3d90f42e90278a5a0feeed0922a8cd2278074ac54e9cfc0e96ff68f8d8f266dd87dc1cc59c2895ec884de2022311767f6a9a7e0bd288c79620e28b83bb3c8d8ad1047c839d6ccf5544eaf434a5f00b951769ab3121298d04b63a162757beb3d49917cd0c9e02ee1ac29398c8130961d5a2f2833aba1e538edb7bb97071f40fae543d1622f0c9206c6d4d8abb2ac1b93ebfb603c2f3a909ede357ade4043550fe540d13a4e87db8d731fe130f15a43a1a00364f5da2d87f7b660c3a04e734218a11
hints = [1, 3, 0, 3, 9, 16, 10, 14, 5, 11, 21, 18, 30, 30, 38, 2, 20, 62, 66, 1, 22, 56, 41, 13, 78, 59, 51, 6, 57, 117, 73, 75, 96, 112, 50, 93, 158, 97, 146, 8, 65, 96, 186, 161, 90, 131, 46, 32, 140, 133, 50, 43, 151, 234]
ct = 0x101b284ad196b5bbd3d3df00a7d3577caeb29c681bdd122582b705afc671febf45d4f3786640e55aadd6a31ecc49175f97b772720f1735f8555f768b137a4643cd6958f80a3dfca4d0270ad463d6dde93429940bd2abb5ad8408b0906fa8d776544a1c50cc0d95939bef4c3fb64d0b52dca81ff0f244fc265bfc0bc147435d05f8f1a146e963a1403b3c123b4d6e73d1fd897109995009be1673212607f0ea7ae33d23f3158448b05c28ea6636382eee9436c4a6c09023ead7182ecd55ac73a68d458d726e1abc208810468591e63f4b4c2c1f3ce27c4800b52f7421ccab432c03e88b3b255740d719e40e0226eabb7633d97ed210e32071e2ac36ed17ef442e

num_hints = len(hints)
sieve_base = list(sieve_base)
primes = sieve_base[1 : num_hints + 1]
M = product(primes)
d0 = crt(hints, primes)

R.<k,s> = PolynomialRing(Zmod(e*M))
f = e*d0 - 1 - k * (N - s + 1)
res = small_roots(f,(2^676,2^1025),m=1,d=2)
# print(res)
# res = list(res)
k = 81654615013062315740859648077669041820032254119133930508020259262868139640323751053386808815603259330292010187040327207703579843971426978151927033372711655537974461264685966709101578503364634863703748863
s = 307418535695879466735463624869957924354358665052136409248678026715718383427120772212039629998693207855281708171850879171131527744317839878812415135610115774273232848128353184128891514282686549164628675031032302196224590402569695631086177519084924289711604045185861705566454491785664136393955640722211793934882
# print(s.bit_length())

# p = var('p')
# eq = p + N / p - s
# result = solve(eq, p)
# print(result)
p = 162568707874348757830017981324054244343649185213197403637567049635272523397583872953595028729502893337750180312800896062635050332212128836106889628645625189460561837738620947057144783601425723834152966458923355830383900722816802076822113540755216842480068493842631250088527236409536028527544211599757688872629
assert N % p== 0
q = N // p
phi = (p-1)*(q-1)
d = inverse_mod(e,phi)
print(b"NepCTF{" + long_to_bytes(pow(ct,d,N)) + b"}")

# b'NepCTF{larg3r_M0du1u5_1nf0_g1ves_b3773r_b0und5}'