这里也记录一下,各种比赛零零散散的题目(觉得比较有意思的)

KalmarCTF2025 - basic sums

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

# I found this super cool function on stack overflow \o/ https://stackoverflow.com/questions/2267362/how-to-convert-an-integer-to-a-string-in-any-base
def numberToBase(n, b):
if n == 0:
return [0]
digits = []
while n:
digits.append(int(n % b))
n //= b
return digits[::-1]

assert len(flag) <= 45

flag = int.from_bytes(flag, 'big')

base = int(input("Give me a base! "))

if base < 2:
print("Base is too small")
quit()
if base > 256:
print("Base is too big")
quit()

print(f'Here you go! {sum(numberToBase(flag, base))}')

题目代码非常简单,我们会得到flag转换为n进制之后的数字之和,可以写成下面的形式

flag=anbn+an1bn1+an2bn2+...+a0b0flag=a_{n}b^{n}+a_{n-1}b^{n-1}+a_{n-2}b^{n-2}+...+a_{0}b^{0}
同时,不难看出有同时,不难看出有
flagsumsan+an1+an2+...+a1+a1(mod b1)flag\equiv sums\equiv a_{n}+a_{n-1}+a_{n-2}+...+a_{1}+a_{1}(mod\ b-1)

上面是我们选择的进制之间的最小公倍数,下面是flag的近似大小(肯定要比这个大)

所以,当模数足够大的时候,flag模它才能得到本身,同时我们也有

flagsums mod (b1)flag\equiv sums\ mod\ (b-1)

flagm mod lcm(n,b1)flag\equiv m\ mod\ lcm(n,b-1)

在b不断增大的情况下,对m不断地进行crt结果的合并,当最小公倍数增大到模数大于flag的值时,我们才能获取到flag的唯一解

flag=crt([m,sums],[lcm(n,b1),b1])flag=crt([m,sums],[lcm(n,b-1),b-1])

# sage
from pwn import *
from tqdm import trange

context(os='linux', arch='amd64', log_level='debug')
m = 0
n = 1
for i in trange(2,256):
p = remote('basic-sums.chal-kalmarc.tf', 2256)
p.sendlineafter(b'Give me a base! ',str(i).encode())
p.recvuntil(b'go! ')
m0 = int(p.recvline())
n0 = i-1
m = crt([m,m0],[n,n0])
n = lcm(n,n0)
p.close()
print(long_to_bytes(int(m)))
# b'kalmar{At_least_it_wasnt_lattices_right???!?}'


这图片起到了一定的迷惑作用,我还以为要构造格才做的出来,我寻思着我这格构造的好像也不怎么行啊,而且这么多组数据,要怎么整呢,然后就看到春哥做出来了,牛批!!!

所以上面其实是我看了春哥写的文档之后,思考了一番(过程应该没问题),觉得挺有意思的记录一下OvO

TPCTF2025 - randomized random(待专研)

# FROM python:3
import random
with open("flag.txt","rb") as f:
flag=f.read()
for i in range(2**64):
print(random.getrandbits(32)+flag[random.getrandbits(32)%len(flag)])
input()

看到getrandbits,可以立马想到MT19937,这里的话因为两个随机数“加”起来了,我们不好处理,但是可以看做是我们可以得到不连续的随机数中的高24位,但看了师傅们的wp都说了实际测试发现影响到了低20位,所以取得是高12位

然后就是不连续的MT19937

待我有空再钻研钻研

2024第四届长城杯 - RandomRSA(未完待续)

题目描述:A特工从敌方服务器获取到了一份带有hint的机密文件,请协助破解加密。

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


class LCG:
def __init__(self, p, a, b):
self.p = p
self.a = a
self.b = b
self.x = random.randint(0, p-1)
print(self.p, self.a, self.b)

def next(self):
self.x = (self.a*self.x+self.b) % self.p
return self.x


def getPrimes(bits, k):
p = getPrime(bits)
a = random.randint(0, p-1)
b = random.randint(0, p-1)
l = LCG(p, a, b)
return [gmpy2.next_prime(l.next()) for _ in range(k)]


p, q = getPrimes(1024, 2)
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(n, c)
'''
p = 170302223332374952785269454020752010235000449292324018706323228421794605831609342383813680059406887437726391567716617403068082252456126724116360291722050578106527815908837796377811535800753042840119867579793401648981916062128752925574017615120362457848369672169913701701169754804744410516724429370808383640129
a = 95647398016998994323232737206171888899957187357027939982909965407086383339418183844601496450055752805846840966207033179756334909869395071918100649183599056695688702272113280126999439574017728476367307673524762493771576155949866442317616306832252931038932232342396406623324967479959770751756551238647385191314
b = 122891504335833588148026640678812283515533067572514249355105863367413556242876686249628488512479399795117688641973272470884323873621143234628351006002398994272892177228185516130875243250912554684234982558913267007466946601210297176541861279902930860851219732696973412096603548467720104727887907369470758901838
n = 5593134172275186875590245131682192688778392004699750710462210806902340747682378400226605648011816039948262008066066650657006955703136928662067931212033472838067050429624395919771757949640517085036958623280188133965150285410609475158882527926240531113060812228408346482328419754802280082212250908375099979058307437751229421708615341486221424596128137575042934928922615832987202762651904056934292682021963290271144473446994958975487980146329697970484311863524622696562094720833240915154181032649358743041246023013296745195478603299127094103448698060367648192905729866897074234681844252549934531893172709301411995941527
c = 2185680728108057860427602387168654320024588536620246138642042133525937248576850574716324994222027251548743663286125769988360677327713281974075574656905916643746842819251899233266706138267250441832133068661277187507427787343897863339824140927640373352305007520681800240743854093190786046280731148485148774188448658663250731076739737801267702682463265663725900621375689684459894544169879873344003810307496162858318574830487480360419897453892053456993436452783099460908947258094434884954726862549670168954554640433833484822078996925040310316609425805351183165668893199137911145057639657709936762866208635582348932189646
'''

xax+b%px\equiv ax+b\%p
p(x+k1)%pp'\equiv(x+k1)\%p
q(ax+b+k2)%pq'\equiv(ax+b+k2)\%p
pqnax2+(b+k2+ak1)x+bk1+k1k2n0%pp'*q'-n\equiv ax^{2}+(b+k2+ak1)x+bk1+k1k2-n\equiv0\%p
abpn已知,k1k2是小数可爆破,那就解x的一元二次方程即可

这里得开多线程搞一手……

reference

https://tover.xyz/p/2024-ccb-RandomRSA/
http://www.andynoel.xyz/?p=904
https://blog.csdn.net/Jayjay___/article/details/142059111

TGCTF2025 - EZRSA

from secrets import flag, get_random_emojiiiiii
from Crypto.Util.number import *


def genarate_emojiiiiii_prime(nbits, base=0):
while True:
p = getPrime(base // 32 * 32) if base >= 3 else 0
for i in range(nbits // 8 // 4 - base // 32):
p = (p << 32) + get_random_emojiiiiii() # 猜一猜
if isPrime(p):
return p


m = bytes_to_long(flag.encode(
) + "".join([long_to_bytes(get_random_emojiiiiii()).decode() for _ in range(5)]).encode())
p = genarate_emojiiiiii_prime(512, 224)
q = genarate_emojiiiiii_prime(512)

n = p * q
e = "💯"
c = pow(m, bytes_to_long(e.encode()), n)

print("p0 =", long_to_bytes(p % 2 ** 256).decode())
print("n =", n)
print("c =", c)
# p0 = 😘😾😂😋😶😾😳😷
# n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
# c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401

可以看到p相当于一个224位的素数拼接9个emoji符号而来,而get_random_emojiiiiii()这个函数我们未知

这里是p的低位泄露攻击,我们知道了p一半的位数,尝试后我们可以发现256位似乎不够我们进行攻击

(部分情况下,1024位需要知道576比特位,512位需要知道288比特位,有的又是需要256位再多一个字节,d的泄露需要知道至少1/4的比特位,视情况而定吧)

可以看到p低8字节已经给出,而我们还可以再爆破出高一个字节,查阅emoji符号的范围,我们得到以下脚本

# sage
from Crypto.Util.number import *
from tqdm import trange

e = bytes_to_long("💯".encode())
p0 = bytes_to_long("😘😾😂😋😶😾😳😷".encode())
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
PR.<x> = PolynomialRing(Zmod(n))
for i in trange(0xf09f9880,0xf09f998f):
p00 = i*2^256 + p0
f = x*2^288+p00
f = f.monic()
roots = f.small_roots(X = 2**224,beta=0.4,epsilon=0.02)
if roots:
p = int(roots[0])*2^288 + p00
q = n // p
print(f"{p = }")
print(f"{q = }")
break

然后就是eϕ不互素e与\phi 不互素,上板子即可

# sage
from sage.all import *
from sage.parallel.multiprocessing_sage import parallel_iter # TODO
import itertools
from tqdm import tqdm
from Crypto.Util.number import *
import string

def nth_p(y, n, p, k=1):
assert is_pseudoprime(p)
print('[LOG] Solving pi = %s^%d' % (hex(p), k))
try:
xs = Zmod(p**k)(y).nth_root(n, all=True)
except:
xs = GF(p**k)(y).nth_root(n, all=True)
xs = list(set(xs))
xs = [Integer(x) for x in xs]
return xs

def nthRSA_p(c, e, p, k=1):
assert is_pseudoprime(p)
P = Integer(pow(p, k))
phi = euler_phi(P)

rs = []
ei = e
while True:
r = gcd(phi, ei)
if r == 1:
break
rs += [r]
ei //= r
r = product(rs)
dr = (e // r).inverse_mod(phi)
cr = pow(c, dr, P)
return nth_p(cr, r, p, k)

def nthRSA_n(c, e, ps, ks=None, checker=None, ret1=False):
# ps: p, q, ...
assert isinstance(ps, list)
if ks == None:
ks = [1] * len(ps)
else:
assert len(ps) == len(ks)
ms = []
for i in range(len(ps)):
mp = nthRSA_p(c, e, ps[i], ks[i])
ms += [mp]
total = product([len(x) for x in ms])
print('[Log] Doing crt.\nComplexity = %d: %s' % (total, str([len(x) for x in ms])))

res = []
Ps = [ps[i]**ks[i] for i in range(len(ps))]
for msi in tqdm(itertools.product(*ms), total=total):
m = crt(list(msi), Ps)
if checker == None:
res += [m]
continue
if checker(m):
if not ret1:
res += [m]
continue
return m
return res

def genHeaderChecker(hd):
if isinstance(hd, str):
hd = hd.encode()
assert isinstance(hd, bytes)
def checkHeader(m):
try:
flag = long_to_bytes(int(m))
if hd in flag:
print(flag)
return True
return False
except:
return False
return checkHeader

def genStrChecker(dict, n=65537):
def checkStr(m):
try:
flag = long_to_bytes(int(m)).decode()
for fi in flag[:n]:
if not fi in dict:
return False
print(flag)
return True
except:
return False
return checkStr

p = 12424840247075830662687097292458444573014198016321428995092662043898159667123240573630892907827505266982898641483333170032514244713840745287869771915696311
q = 12602471198163266643743702664647336358595911975665358584258749238146841559843060594842063473155049870396568542257767865369797827796765830093256146584311989
e = bytes_to_long("💯".encode())
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401

ps = [p, q]
checker = genHeaderChecker('TGCTF')
res = nthRSA_n(c, e, ps, checker=checker)
for r in res:
flag = long_to_bytes(int(r))
print(flag.decode())
# TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢

LitCTF2025 - leak(dp高位泄露广义解法)

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

m = bytes_to_long(flag)
p,q,e = getPrime(1024),getPrime(1024),getPrime(101)
n = p*q
temp = gmpy2.invert(e,p-1)
c = pow(m,e,n)
hint = temp>>180
print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")
print(f"hint = {hint}")
'''
e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
'''

edp1(mod p1)e*dp\equiv 1(mod\ p-1)
e(dp_high+x)=k(p1)+1e*(dp\_high+x)=k*(p-1)+1
e(dp_high+x)+k10(mod p)e*(dp\_high+x)+k-1\equiv 0(mod\ p)
因为这里e太大了,我们打不了一元copper,那就直接打二元copper

奇怪的是,m代表移位位数,d代表多项式的最高次幂,但这里只能为3才能跑出flag(已经默认跑13了)

2edp2(mod p)2^{e*dp}\equiv 2(mod\ p)
p=GCD(2edp2,n)p=GCD(2^{e*dp}-2,n)

# sage
from sage.all import *
from Crypto.Util.number import *
import itertools

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

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 = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
leak = hint << 180
PR.<x,y>=PolynomialRing(Zmod(n))
f = e*(leak + x) + y -1
res = small_roots(f, (2^180,2^e.bit_length()),m=1,d=3)
for root in res:
dp = leak + root[0]
p = GCD(pow(2, e*dp, n) -2, n)
q = n // p
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m).decode())

NepCTF2025 - ezRSA2

Easy RSA, easy strategy. No need to brute force.
Perhaps it’s easier than ezRSA in NepCTF 2024.

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=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
"""

这里一下子就可以看到e很大并且接近N,但发现dN0.33d\approx N^{0.33},大于boneh durfee 0.292上界,不适用

然,本题的hints.append(d%li)可以通过中国剩余定理CRT求解出d低位

dlowd mod Md_{low}\equiv d\ mod\ M
d=k1M+dlowd=k_{1}M+d_{low}

正常做这种d相关的题目的思路都可以借助下面这条公式,进行展开,尝试copper或者构造格

ed1 mod ϕ(n)ed\equiv 1\ mod\ \phi(n)

ed=k(Npq+1)+1ed=k*(N-p-q+1)+1

因为周末也要值班。。。还是夜班,加上又不是很想碰CTF,所以当时就想着能不能找到boneh durfee的优化算法,把上界调高,偷个懒,直接梭()
很可惜没找到(但赛后群友有说找到的,orz),然后困了,不想做,等赛后再看看

到上面这一步,有两种思路

思路一

edlow+ek1M1=k2(Npq+1)e*d_{low}+e*k_{1}M-1=k_{2}*(N-p-q+1)

这里是k1,k2未知(p q暂时不管),很明显我们可以尝试一下二元copper,不过形式得稍微变换一下

edlow1k(Npq+1)0 mod (eM)e*d_{low}-1-k*(N-p-q+1)\equiv 0\ mod\ (e*M)

X=k,Y=p+q令X = k,Y=p+q

k可以借助题目脚本多跑几下,大概位数在676位p+q很明显1024位

# sage
from sage.all import *
from Crypto.Util.number import *
import itertools

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

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
primes = list(sieve_base[1:len(hints)+1])
M = prod(primes)
d_low = crt(hints,primes)
PR.<x,y> = PolynomialRing(Zmod(e*M))
f = e*d_low -1 - x*(N - y + 1)
res = small_roots(f, (2^676,2^1024),m=1,d=3)
for root in res:
print(f'p_q = {root[1]}')

这里Sage不知道发什么癫,解方程有问题,换Python解一下吧,Python还得注意一下大整数才能运行起来

from Crypto.Util.number import *
from sympy import *

e = 0x73915608ed64c9cf1a2279684cab4f4a78fba229d45d4f860971a241481363470a19cb0dc0d00f816b5befdaca017cf71483e96ef17b36179012f5194a0e6bf481bb06c2644f74c6812efb65d05c00631f282d6aa55c0bc140a1830b95a1cf4b6024cb0db53f2c2189897c41f22e2eec773723f531ec4bfa537fae6de5fe480cf46fe17850f7eb47df08194d95db3d26ac923b26e110ee645239ab586bbc546ddc5906f280a106edbb727ccb05536b5a3f5c0ebcf865c95ce58be54f7f3547aa53baa218b0dfa98e42d925fa341e45f94a3b16b0c83802660c7f34de3336cb21f219073cf8e9f5e39d47f0a9a9ee7c255f09a6add9a2f7a47960f4a853183d29
N = 0xba8956e81394f3f1265ca5d9c4ad1ab0078bb43c4b80a231ab2cc62246ae45f66a562252622aed2cbbfc08647ef2fec0f97a632bf2242845f4b3af0c427cec3d90f42e90278a5a0feeed0922a8cd2278074ac54e9cfc0e96ff68f8d8f266dd87dc1cc59c2895ec884de2022311767f6a9a7e0bd288c79620e28b83bb3c8d8ad1047c839d6ccf5544eaf434a5f00b951769ab3121298d04b63a162757beb3d49917cd0c9e02ee1ac29398c8130961d5a2f2833aba1e538edb7bb97071f40fae543d1622f0c9206c6d4d8abb2ac1b93ebfb603c2f3a909ede357ade4043550fe540d13a4e87db8d731fe130f15a43a1a00364f5da2d87f7b660c3a04e734218a11
ct = 0x101b284ad196b5bbd3d3df00a7d3577caeb29c681bdd122582b705afc671febf45d4f3786640e55aadd6a31ecc49175f97b772720f1735f8555f768b137a4643cd6958f80a3dfca4d0270ad463d6dde93429940bd2abb5ad8408b0906fa8d776544a1c50cc0d95939bef4c3fb64d0b52dca81ff0f244fc265bfc0bc147435d05f8f1a146e963a1403b3c123b4d6e73d1fd897109995009be1673212607f0ea7ae33d23f3158448b05c28ea6636382eee9436c4a6c09023ead7182ecd55ac73a68d458d726e1abc208810468591e63f4b4c2c1f3ce27c4800b52f7421ccab432c03e88b3b255740d719e40e0226eabb7633d97ed210e32071e2ac36ed17ef442e


pq = 307418535695879466735463624869957924354358665052136409248678026715718383427120772212039629998693207855281708171850879171131527744317839878812415135610115774273232848128353184128891514282686549164628675031032302196224590402569695631086177519084924289711604045185861705566454491785664136393955640722211793934882

p, q = symbols('p q')
res = solve([p*q-N, pq - (p+q)], [p, q])
p, q = res[1]
print(p*q == N)
e = Integer(e)
p = Integer(p)
d = inverse(e, p-1)
ct = Integer(ct)
flag = long_to_bytes(pow(ct, d, p)).decode()
print('NepCTF{'+flag+'}')
# NepCTF{larg3r_M0du1u5_1nf0_g1ves_b3773r_b0und5}

这就是一个简单的二元copper的应用

思路二

这里也可以尝试构造格

我们把需要求解的p+q放到等式右边
edlow1+ek1Mk2(N+1)=k2(p+q)e*d_{low}-1+e*k_{1}*M-k_{2}*(N+1)=k_{2}*(p+q)
可以得到

[1k1k2][10edlow101eM00N+1] =[1k1k2(p+q)]\left [ \begin{matrix} 1&k_1&-k_{2}\\ \end{matrix} \right ] * \left [ \begin{matrix} 1&0&ed_{low}-1\\ 0&1&eM\\ 0&0&N+1\\ \end{matrix} \right ] \ = \left [ \begin{matrix} 1&k_1&k_{2}(p+q)\\ \end{matrix} \right ]

配平一下目标向量,k1大概在333位这样,k2675位这样,k2(p+q)大概会在1700位,所以有

[1k1k2][217000edlow1021370eM00N+1] =[21700k121370k2(p+q)]\left [ \begin{matrix} 1&k_1&-k_{2}\\ \end{matrix} \right ] * \left [ \begin{matrix} 2^{1700}&0&ed_{low}-1\\ 0&2^{1370}&eM\\ 0&0&N+1\\ \end{matrix} \right ] \ = \left [ \begin{matrix} 2^{1700}&k_1*2^{1370}&k_{2}(p+q)\\ \end{matrix} \right ]

# sage
from sage.all import *
from Crypto.Util.number import *

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
primes = list(sieve_base[1:len(hints)+1])
M = prod(primes)
d_low = crt(hints,primes)

mat = [[2^1700, 0, e*d_low-1], [0, 2^1370, e*M], [0, 0, N + 1]]
L = Matrix(ZZ, mat)
for res in L.LLL():
k, K1, _ = res
if k == 2^1700:
d = (K1//2^1370)*M + d_low
flag = long_to_bytes(pow(ct,d,N)).decode()
print('NepCTF{' + flag + '}')

这样看的话,貌似格更方便一些……

思路三

boneh durfee通过LSBs拔高上界 P30 Section 5
具体怎么实现不了了之,但感觉是二元copper的优化,或者说二元coppersmall_roots是从boneh durfee算法中来的?
不清楚,反正我套的()

reference

NepCTF2025 - latticebros(待补ing)

#已知α的极小多项式为三次多项式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)
""""
[(541847931463604073209188621415697353813245102261880389530448, 293760933113243563398917466885108625646262447370201484418246), (235213326900086489464935804156966465366154623411555613791270, 660823982268225103178763707015491421784294988488272636270997), (826464884761457937459245903152143755707241416981488127320435, 428521663319038461250005113612781686761766888058391496085911), (589542000504317435156560078533519448295689695687499354390208, 155284353896000150766154807679279597476176668344402166959399), (968823371588600973965757332601758200815345862153455338808286, 870008943690791009196027169525956126827736285614393106689402), (621636099728440147413990266662022925118216803638588918660041, 265635912066749696542909843111997941904342442664219734956888), (426696569424050102229606043215592727790577655338668728275370, 279313121876980354011480010042682666651614765507190502627689), (89450479064580125731654556963306718472532905610952012502649, 465933125964565419295325650759566635253450915499965633327941), (480355476500393865742379469913983270769356894135485925662119, 894041172171871806404285309781862268351135623868845025443422), (842436524669577199024236805258573090764419350786291073287889, 345478552143958037534551648319293899442551000874041707820740), (650054674429185550652935714084022116516082323269321462104664, 441999979283903658157822753439653947343822546158589507765994), (46289431385578693366971976442426853079852982529357847290686, 625618376463384339878849844467050454204685252824782609369180), (71444185449163133531919043374545893927347050624346741281881, 955925578289311966288639224625142299309823207245807788495453), (192579726169321656812883068526498248523814846320328766176253, 626481822474054336470183912297952839011392733501646931370367), (736527635648804640774976580747540045854351230084566721853611, 276626211757586963928788091386096607703513204646314683038338), (177922521867185878959621840269164617147915792720210315529733, 541058782621716573816245900423919799500476442285991532228641), (40610451174818168154306630612571678739921107216052349044576, 727642592899858828601137105077611015328512898368636299587376), (385012983728389322601149562441674995471397288632464238356283, 353921151307105661267278594470212933060655245893209524497156), (750447975601038834764379841158092390933760641866111445401426, 391626416964965737035878375834907580903143512300198923948189), (115058604943298010958881205548782439407592353731185670266593, 491630592857258949793489206081490523001249620510479961058022), (327389234395954477946639629629085910688793716425320663599360, 24975272330009592102362429346350824580378490147041708568130), (115595274689129534885608766476695918464309130165432995990883, 757961876891952019297626599379744405302595090402128271144165), (950804723308776351161744501221236453742418549093165078282534, 20307246759635231945223392614290397512873344480184942904518), (724537610412063699714461780160573528810830178440136810747811, 149681928388378582933943374524511804362928290938917573644613), (340891278018589324130004945217960336392205386747747011263373, 683307718413135477104477081812052183267507312278283317237187), (104379682905784169840335131193505192063050242530811180817410, 715010230598797717533306270232399781090458356371977748416491), (644160326926600986730919713173510327120201404569141824224075, 127877985489410167008195578625004740882394608402141169695352), (549253388716005399852261816416312267100135940382820676807345, 210560134643237517255193955173709174155305784935427470113433), (968265711632086435506163736279856957220961064226797549228006, 273174723915971720522674140326199419265943707917542063022561), (704367622558261900937184683100177434487519780290678439135652, 959106497548134540301589019840013331842784496835379005298630)]
""""

SekaiCTF2025 - I Dream of Genni

I had the strangest dream last night.

from hashlib import sha256
from Crypto.Cipher import AES

x = int(input('Enter an 8-digit multiplicand: '))
y = int(input('Enter a 7-digit multiplier: '))
assert 1e6 <= y < 1e7 <= x < 1e8, "Incorrect lengths"
assert x * y != 3_81_40_42_24_40_28_42, "Insufficient ntr-opy"

def dream_multiply(x, y):
x, y = str(x), str(y)
assert len(x) == len(y) + 1
digits = x[0]
for a, b in zip(x[1:], y):
digits += str(int(a) * int(b))
return int(digits)
assert dream_multiply(x, y) == x * y, "More like a nightmare"

ct = '75bd1089b2248540e3406aa014dc2b5add4fb83ffdc54d09beb878bbb0d42717e9cc6114311767dd9f3b8b070b359a1ac2eb695cd31f435680ea885e85690f89'
print(AES.new(sha256(str((x, y)).encode()).digest(), AES.MODE_ECB).decrypt(bytes.fromhex(ct)).decode())

这题密码打的标签是misc,确实哈

题目的意思一目了然,看一下图片就知道了,需要找到另外一组满足条件的八位数和七位数

自己写不大会,AI不靠谱,春哥写的多线程学不来(我的电脑要跑九个小时),最后学习一下官方wp

八位乘七位,八位的第一位可以直接写下来暂不做考虑,剩下的乘出来都是两位数,所以我们快速一点,可以建立一个元组,储存起来,方便运算调用,也省搜索空间

pairs = [(x, y) for x in range(1, 10) for y in range(1, 10) if x*y >= 10]

然后是完成题目算法的构建,模十可以得到各个位置的数字,再扩大相应位数,这里相乘了,是以百为基数,最终将数字拼接起来

def multwo(i, j, digits):
s, mul = 0, 1
for z in range((digits+1)//2):
s += (i % 10) * (j % 10) * mul
i, j, mul = i // 10, j // 10, mul * 100
return s

处理函数process,先看这一部分代码,是从低位向高位构建拼接的一个过程,只有每一次的低两位、低三四位、低五六位…是假设目标解的一部分,才会进入下一个递归,然后继续从pairs里面取对,继续判断是否是正解的一部分(这就是剪枝的工作过程)

mul = 10**digits
for a, b in pairs:
x2 = a*mul + x
y2 = b*mul + y
if (multwo(x2, y2, digits+1) - x2*y2) % (10*mul) == 0:
process(x2, y2, digits+1)

但这样的话,最终只能得到拼接结果的后七位与相乘的后七位一样(N=7)的结果,所以才会是八位和七位相乘,不然是找不到这样的两个数的

七位与七位相乘的结果会比拼接的大,此时,根据二者的差值以及y可以构建出第八位,从而得到目标解

用数学来表示就是:用数学来表示就是:
X=d8107+xX=d_{8}*10^{7}+x
(d8107+x)y=d81014+multwo(x,y,14)(d_{8}*10^{7}+x)*y=d_{8}*10^{14}+multwo(x,y,14)
xymultwo(x,y,14)=d81014d8107yx*y-multwo(x,y,14)=d_{8}*10^{14}-d_{8}*10^{7}*y
xymultwo(x,y,14)=d8107(107y)x*y-multwo(x,y,14)=d_{8}*10^{7}*(10^{7}-y)
n1需要整除n2才能得到正确的d8,同时确保比10倍小n1需要整除n2才能得到正确的d_{8},同时确保比10倍小

if digits == N:
n1 = x*y - multwo(x, y, N*2)
n2 = 10**N * (10**N - y)
if n1 < 10 * n2 and n1 % n2 == 0:
print(f'{n1//n2}{x}, {y}')
return

完整代码

pairs = [(x, y) for x in range(1, 10) for y in range(1, 10) if x*y >= 10]

def multwo(i, j, digits):
s, mul = 0, 1
for z in range((digits+1)//2):
s += (i % 10) * (j % 10) * mul
i, j, mul = i // 10, j // 10, mul * 100
return s

def process(x, y, digits, N=7):
if digits == N:
n1 = x*y - multwo(x, y, N*2)
n2 = 10**N * (10**N - y)
if n1 < 10 * n2 and n1 % n2 == 0:
print(f'{n1//n2}{x}, {y}')
return
mul = 10**digits
for a, b in pairs:
x2 = a*mul + x
y2 = b*mul + y
if (multwo(x2, y2, digits+1) - x2*y2) % (10*mul) == 0:
process(x2, y2, digits+1)

process(0, 0, 0)

真的是很有意思的一道题目oVo

SekaiCTF2025 - SSSS

Shamir SendS the Secret to everyone

import random, os

p = 2 ** 256 - 189
FLAG = os.getenv("FLAG", "SEKAI{}")

def challenge(secret):
t = int(input())
assert 20 <= t <= 50, "Number of parties not in range"

f = gen(t, secret)

for i in range(t):
x = int(input())
assert 0 < x < p, "Bad input"
print(poly_eval(f, x))

if int(input()) == secret:
print(FLAG)
exit(0)
else:
print(":<")

def gen(degree, secret):
poly = [random.randrange(0, p) for _ in range(degree + 1)]
index = random.randint(0, degree)

poly[index] = secret
return poly

def poly_eval(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p

if __name__ == "__main__":
secret = random.randrange(0, p)
for _ in range(2):
challenge(secret)

不怎么接触Shamir,遂记录一下不怎么接触Shamir,遂记录一下

根据题目,得到t+1项的t次多项式根据题目,得到t+1项的t次多项式

f(x)=c0+c1x+...+Sxindex+...+ctxt(modp)f(x)=c_{0}+c_{1}x+...+Sx^{index}+...+c_{t}x^{t}\pmod p

循环t次,输入得到t个点(xi,f(xi)),调用两次challenge()循环t次,输入得到t个点(x_{i},f(x_{i})),调用两次challenge()
每次的多项式的系数和位置会不一样,但secret数值固定每次的多项式的系数和位置会不一样,但secret数值固定

正常来说,借助拉格朗日差值公式恢复多项式的所有系数我们需要t+1个不同的点,但此处最多只能获得t个不同的点正常来说,借助拉格朗日差值公式恢复多项式的所有系数我们需要t+1个不同的点,但此处最多只能获得t个不同的点

下面参考官方wp脚本,写了一下自己的思考下面参考官方wp脚本,写了一下自己的思考

其实还可以这样表示:f(x)=Pt1(x)+C(xx1)(xx2)...(xxt)其实还可以这样表示:f(x)=P_{t-1}(x)+C(x-x_{1})(x-x_{2})...(x-x_{t})

ord(Zp)=p1t  p1t=29t[20,50]ord(Z_p^{*})=p-1,t\ |\ p-1,t=29,t\in [20,50]
可以找到生成元g生成的循环子群<g>={g0,g1,...,gt1}可以找到生成元g生成的循环子群<g>=\{g^{0},g^{1},...,g^{t-1}\}
gt1(modp)g^{t}\equiv 1\pmod p
xi=gi(modp)t次单位根,得到下面的式子取x_{i}=g^{i}\pmod p,t次单位根,得到下面的式子

f(x)=Pt1(x)+C(xt1)f(x)=P_{t-1}(x)+C(x^{t}-1)

Pt1(x)=R.lagrange_polynomial(shares)=at1xt1+...+a1x+a0P_{t-1}(x)=R.lagrange\_polynomial(shares)=a_{t-1}x^{t-1}+...+a_{1}x+a_{0}

ctxt+...+c1x+c0=Cxt+at1xt1+...+a1x+(a0C)c_{t}x^{t}+...+c_{1}x+c_{0}=C\cdot x^{t}+a_{t-1}x^{t-1}+...+a_{1}x+(a_{0}-C)

ct=Cc_{t}=C
ct1=at1,...,c1=a1c_{t-1}=a_{t-1},...,c_{1}=a_{1}
c0=a0Cc_{0}=a_{0}-C

借助sage自带的拉格朗日差值公式,取两次多项式系数的交集就可以得到secret(两次secret都要落在[c1ct1])借助sage自带的拉格朗日差值公式,取两次多项式系数的交集就可以得到secret(两次secret都要落在[c_{1}-c_{t-1}])

注意gt=1(modp),这样的g只有t个,直接找概率很低注意g^{t}=1\pmod p,这样的g只有t个,直接找概率很低
我们构造h=basep1t(modp)我们构造h=base^{\frac{p-1}{t}}\pmod p
ht=1(modp)ord(h)  tif h1ord(h)=th^{t}=1\pmod p,ord(h)\ |\ t,if\ h\not = 1,ord(h)=t
这样P(h1)=1(p1)/tp1=28/29这样P(h\not =1)=1-\frac{(p-1)/t}{p-1}=28/29

# sage
from pwn import *

p = 2 ** 256 - 189
R.<x0> = GF(p)[]
t = 29

# conn = process(["python3", "../dist/chall.py"])
conn = remote('ssss.chals.sekai.team', 1337, ssl=True)

def query():
conn.sendline(str(t).encode())
g = 2
while pow(g, (p-1)//t, p) == 1:
g += 1

g = pow(g, (p-1)//t, p)
assert pow(g, t, p) == 1

shares = []
for i in range(t):
x = pow(g, i, p)
conn.sendline(str(x).encode())
y = int(conn.recvline())
shares.append((x, y))

return list(R.lagrange_polynomial(shares))

A = query()
conn.sendline(b"1")
conn.recvline() # :<

B = query()

for secret in A:
if secret in B:
conn.sendline(str(secret).encode())
print(conn.recvline().decode().strip())

这个是春哥的思路,直接到了底层这个是春哥的思路,直接到了底层

[x10x11x1t1x20x21x2t1xt0xt1xtt1][c0c1ct1] =[y1y2yt]\left [ \begin{matrix} x_1^0 & x_1^1 & \dots & x_1^{t-1} \\ x_2^0 & x_2^1 & \dots & x_2^{t-1} \\ \vdots & \vdots & \ddots & \vdots \\ x_t^0 & x_t^1 & \dots & x_t^{t-1} \end{matrix} \right ] \cdot \left [ \begin{matrix} c_0 \\ c_1 \\ \vdots \\ c_{t-1} \end{matrix} \right ] \ = \left [ \begin{matrix} y_1 \\ y_2 \\ \vdots \\ y_t \end{matrix} \right ]

Ac=bA称为范德蒙德矩阵,只要所有的xj互不相同,这个矩阵就是可逆的,方程就有唯一解cA\cdot c=b,A称为范德蒙德矩阵,只要所有的x_{j}互不相同,这个矩阵就是可逆的,方程就有唯一解c
范德蒙德矩阵是拉格朗日差值公式的基础,又从春哥那学到知识了范德蒙德矩阵是拉格朗日差值公式的基础,又从春哥那学到知识了

# sage
from pwn import *
from sage.all import *

class Gao:
def __init__(self):
# self.conn = process(['python3', 'another.py'])
self.conn = remote('ssss.chals.sekai.team', '1337', ssl=True)
self.p = 2 ** 256 - 189
self.Zp = Zmod(self.p)
self.g = 68182365146192563136101852599586284510469631280758214998024143739738246750499

def gao_1(self):
Zp = self.Zp
g = Zp(self.g)

t = 29
self.conn.sendline(str(t))
A, b = [], []
for j in range(t):
x = g ** j
self.conn.sendline(str(x))
y = int(self.conn.recvline())
A.append([Zp(x) ** i for i in range(t)])
b.append(Zp(y))
A = matrix(Zp, A)
b = vector(Zp, b)
x = A.solve_right(b)
return set(x.list())

def gao(self):
a = self.gao_1()
self.conn.sendline('0')
self.conn.recvline()
b = self.gao_1()
num = a & b
print(num)
assert len(num) == 1, "Multiple secrets found"
secret = num.pop()
self.conn.sendline(str(secret))
self.conn.interactive()

if __name__ == "__main__":
g = Gao()
g.gao()