Cryptography趣题记录

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

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转换为b进制之后的数字之和，可以写成下面的形式$
$flag=a_{n}b^{n}+a_{n-1}b^{n-1}+a_{n-2}b^{n-2}+...+a_{0}b^{0}$
$sum=a_{n}+a_{n-1}+a_{n-2}+...+a_{1}+a_{0}$
$同时，不难看出有$
$sum_{i}\equiv flag(mod\ b_{i}-1)$
$可以通过不断地+1，增大b，最终通过crt求得flag$
$注意：这里使用的是sage自带的crt函数（可处理模数不互质的情况）$
$如果使用的是自定义的中国剩余定理函数，会出现逆元不存在的情况，因为这里的模数并不互质$

$因为不互质，所以需要进制间的最小公倍数比flag的值大，这样才能得到正解$
$当然，也可以通过拓展中国剩余定理解决$

$因为flag长度45，如果模数只取素数，最大是251，它们的乘积是不够flag的值大的$
$不过也可以选一些非素数，只要相互之间互质且最后乘积够大就行了$

def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    x, y, q = exgcd(b, a % b)
    x, y = y, (x - a // b * y)
    return x, y, q

def exCRT(a, m):
    for i in range(len(a)):
        x, y, d = exgcd(m[0], m[i])
        if (a[i] - a[0]) % d != 0:
            return -1
        t = m[i] // d
        x = (a[i] - a[0]) // d * x % t
        a[0] = x * m[0] + a[0]
        m[0] = m[0] * m[i] // d
        a[0] = (a[0] % m[0] + m[0]) % m[0]
    return a[0]

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

context(os='linux', arch='amd64', log_level='warning')
m = []
b = []
for i in range(2, 253):
    p = remote('basic-sums.chal-kalmarc.tf', 2256)
    p.sendlineafter(b'Give me a base! ', str(i).encode())
    p.recvuntil(b'go! ')
    m.append(int(p.recvline()))
    b.append(i-1)
    p.close()

flag = crt(m, b)
print(long_to_bytes(flag).decode())
# 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
'''

$x\equiv ax+b\%p$
$p'\equiv(x+k1)\%p$
$q'\equiv(ax+b+k2)\%p$
$p'*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与\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
'''

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

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

$2^{e*dp}\equiv 2(mod\ p)$
$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，但发现$d\approx N^{0.33}$，大于boneh durfee 0.292的上界，不适用

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

$d_{low}\equiv d\ mod\ M$
$d=k_{1}M+d_{low}$

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

$ed\equiv 1\ mod\ \phi(n)$

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

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

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

思路一

$e*d_{low}+e*k_{1}M-1=k_{2}*(N-p-q+1)$

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

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

$令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放到等式右边
$e*d_{low}-1+e*k_{1}*M-k_{2}*(N+1)=k_{2}*(p+q)$
可以得到

$$\left [ \begin{matrix} 1&k_1&-k_{2}\\ \end{matrix} \right ] * \left [ \begin{matrix} 1&0&e*d_{low}-1\\ 0&1&e*M\\ 0&0&N+1\\ \end{matrix} \right ] \ = \left [ \begin{matrix} 1&k_1&k_{2}(p+q)\\ \end{matrix} \right ]$$

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

$$\left [ \begin{matrix} 1&k_1&-k_{2}\\ \end{matrix} \right ] * \left [ \begin{matrix} 2^{1700}&0&e*d_{low}-1\\ 0&2^{1370}&e*M\\ 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的优化，或者说二元copper的small_roots是从boneh durfee算法中来的？
不清楚，反正我套的()

reference

• Crypto全解
• 出题人题解

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=d_{8}*10^{7}+x$
$(d_{8}*10^{7}+x)*y=d_{8}*10^{14}+multwo(x,y,14)$
$x*y-multwo(x,y,14)=d_{8}*10^{14}-d_{8}*10^{7}*y$
$x*y-multwo(x,y,14)=d_{8}*10^{7}*(10^{7}-y)$
$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，遂记录一下$

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

$$f(x)=c_{0}+c_{1}x+...+Sx^{index}+...+c_{t}x^{t}\pmod p$$

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

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

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

$其实还可以这样表示：f(x)=P_{t-1}(x)+C(x-x_{1})(x-x_{2})...(x-x_{t})$

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

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

$P_{t-1}(x)=R.lagrange\_polynomial(shares)=a_{t-1}x^{t-1}+...+a_{1}x+a_{0}$

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

$c_{t}=C$
$c_{t-1}=a_{t-1},...,c_{1}=a_{1}$
$c_{0}=a_{0}-C$

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

$注意g^{t}=1\pmod p，这样的g只有t个，直接找概率很低$
$我们构造h=base^{\frac{p-1}{t}}\pmod p$
$h^{t}=1\pmod p，ord(h)\ |\ t，if\ h\not = 1，ord(h)=t$
$这样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())

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

$$\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 ]$$

$A\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()

SECCON CTF 14 - yukari

#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime, isPrime

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

for _ in range(32):
    p = getPrime(1024)
    print("p =", p)

    q = int(input("q: "))
    assert p != q
    assert q.bit_length() >= 1024
    assert isPrime(q)

    n = p * q
    e = getPrime(64)
    d = pow(e, -1, (p - 1) * (q - 1))

    try:
        cipher = RSA.construct((n, e, d))
    except:
        print("error!")
        continue
    print("key setup successful")
    exit()

print(FLAG)

这题有点绷不住，居然是要触发RSA.construct((n, e, d))的异常才能过，然后要坚持32轮

vscode跟进函数

def construct(rsa_components, consistency_check=True):
    r"""Construct an RSA key from a tuple of valid RSA components.

    The modulus **n** must be the product of two primes.
    The public exponent **e** must be odd and larger than 1.

    In case of a private key, the following equations must apply:

    .. math::

        \begin{align}
        p*q &= n \\
        e*d &\equiv 1 ( \text{mod lcm} [(p-1)(q-1)]) \\
        p*u &\equiv 1 ( \text{mod } q)
        \end{align}

    Args:
        rsa_components (tuple):
            A tuple of integers, with at least 2 and no
            more than 6 items. The items come in the following order:

            1. RSA modulus *n*.
            2. Public exponent *e*.
            3. Private exponent *d*.
               Only required if the key is private.
            4. First factor of *n* (*p*).
               Optional, but the other factor *q* must also be present.
            5. Second factor of *n* (*q*). Optional.
            6. CRT coefficient *q*, that is :math:`p^{-1} \text{mod }q`. Optional.

        consistency_check (boolean):
            If ``True``, the library will verify that the provided components
            fulfil the main RSA properties.

    Raises:
        ValueError: when the key being imported fails the most basic RSA validity checks.

    Returns: An RSA key object (:class:`RsaKey`).
    """

    class InputComps(object):
        pass

    input_comps = InputComps()
    for (comp, value) in zip(('n', 'e', 'd', 'p', 'q', 'u'), rsa_components):
        setattr(input_comps, comp, Integer(value))

    n = input_comps.n
    e = input_comps.e
    if not hasattr(input_comps, 'd'):
        key = RsaKey(n=n, e=e)
    else:
        d = input_comps.d
        if hasattr(input_comps, 'q'):
            p = input_comps.p
            q = input_comps.q
        else:
            # Compute factors p and q from the private exponent d.
            # We assume that n has no more than two factors.
            # See 8.2.2(i) in Handbook of Applied Cryptography.
            ktot = d * e - 1
            # The quantity d*e-1 is a multiple of phi(n), even,
            # and can be represented as t*2^s.
            t = ktot
            while t % 2 == 0:
                t //= 2
            # Cycle through all multiplicative inverses in Zn.
            # The algorithm is non-deterministic, but there is a 50% chance
            # any candidate a leads to successful factoring.
            # See "Digitalized Signatures and Public Key Functions as Intractable
            # as Factorization", M. Rabin, 1979
            spotted = False
            a = Integer(2)
            while not spotted and a < 100:
                k = Integer(t)
                # Cycle through all values a^{t*2^i}=a^k
                while k < ktot:
                    cand = pow(a, k, n)
                    # Check if a^k is a non-trivial root of unity (mod n)
                    if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:
                        # We have found a number such that (cand-1)(cand+1)=0 (mod n).
                        # Either of the terms divides n.
                        p = Integer(n).gcd(cand + 1)
                        spotted = True
                        break
                    k *= 2
                # This value was not any good... let's try another!
                a += 2
            if not spotted:
                raise ValueError("Unable to compute factors p and q from exponent d.")
            # Found !
            assert ((n % p) == 0)
            q = n // p

        if hasattr(input_comps, 'u'):
            u = input_comps.u
        else:
            u = p.inverse(q)

        # Build key object
        key = RsaKey(n=n, e=e, d=d, p=p, q=q, u=u)

    # Verify consistency of the key
    if consistency_check:

        # Modulus and public exponent must be coprime
        if e <= 1 or e >= n:
            raise ValueError("Invalid RSA public exponent")
        if Integer(n).gcd(e) != 1:
            raise ValueError("RSA public exponent is not coprime to modulus")

        # For RSA, modulus must be odd
        if not n & 1:
            raise ValueError("RSA modulus is not odd")

        if key.has_private():
            # Modulus and private exponent must be coprime
            if d <= 1 or d >= n:
                raise ValueError("Invalid RSA private exponent")
            if Integer(n).gcd(d) != 1:
                raise ValueError("RSA private exponent is not coprime to modulus")
            # Modulus must be product of 2 primes
            if p * q != n:
                raise ValueError("RSA factors do not match modulus")
            if test_probable_prime(p) == COMPOSITE:
                raise ValueError("RSA factor p is composite")
            if test_probable_prime(q) == COMPOSITE:
                raise ValueError("RSA factor q is composite")
            # See Carmichael theorem
            phi = (p - 1) * (q - 1)
            lcm = phi // (p - 1).gcd(q - 1)
            if (e * d % int(lcm)) != 1:
                raise ValueError("Invalid RSA condition")
            if hasattr(key, 'u'):
                # CRT coefficient
                if u <= 1 or u >= q:
                    raise ValueError("Invalid RSA component u")
                if (p * u % q) != 1:
                    raise ValueError("Invalid RSA component u with p")

    return key

它会利用probabilistic algorithm（基于Miller-Rabin素性测试原理的逆过程）来分解n，然后检查参数是否满足条件

一开始，我和Gemini的想法是构造一个q，让它找不到非平凡平方根，然后成功率非常低，最高能坚持到11轮，而且往往只能坚持几轮

• 构造逻辑：利用差分构造法 q = p + step，其中 step 是 lowest_bit * 2 的倍数。保证 $q-1$ 和 $p-1$ 在二进制表示下，最低位的 1 处于完全相同的位置。结果： $v_2(q-1) = v_2(p-1)$
• 漏洞机理：PyCryptodome 内部试图寻找一个数 $x$，使得它在模 $p$ 下是 $1$，而在模 $q$ 下是 $-1$（从而区分 $p$ 和 $q$）。当 $v_2$ 相等时，算法中的平方序列在模 $p$ 和模 $q$ 下 完全同步（同时变成 1 或同时变成 -1）。后果： 算法找不到差异，无法分解 $n$，最终抛出 ValueError

if not spotted:
    raise ValueError("Unable to compute factors p and q from exponent d.")

后面优化细节，通过扩大搜索空间、本地验证，成功率也是提不上去……

赛后，去discord看了一下讨论，大佬提供了一个思路u = p.inverse(q)，然后琢磨了一下，搞出来了

if u <= 1 or u >= q:
    raise ValueError("Invalid RSA component u")

• 构造逻辑：利用乘法构造法 step = p * (1 << (s_p + 1))，然后 q = step + 1。这保证了 $q = k \cdot p + 1$，且 $k$ 包含的因子 2 比 $p-1$ 多。结果： $v_2(q-1) > v_2(p-1)$ 且 $q \equiv 1 \pmod p$
• 漏洞机理：
  • 控制分解顺序：PyCryptodome 倾向于把 $v_2$ 更大的那个因子识别为第一个因子（赋值给代码中的 p 变量）。因为我们构造了 $v_2(q-1) > v_2(p-1)$，所以库内部变量 p 实际上被赋值为我们的 $q$
  • 触发异常：代码计算 u = p.inverse(q)。由于变量互换，实际计算的是 $q^{-1} \pmod p$
  • 数学必然：因为我们构造了 $q \equiv 1 \pmod p$，所以 $u = 1^{-1} \pmod p = 1$
  • 后果：触发源码中的 if u <= 1: raise ValueError

这个exp也比较看脸(但成功概率大了很多很多)，只要题目生成的$v_2(p)$是大的，就要重来了

运气最好的一次是攻击6次，114s拿到flag，目前只攻击成功四次，第一次没计时，第二次22/240s，第四次16/218s

from pwn import *
from Crypto.Util.number import *
from time import time


HOST = 'yukari.seccon.games'
PORT = 15809
context.log_level = 'info'


def get_v2(n):
    """计算 n 的二进制末尾有多少个 0"""
    c = 0
    while n > 0 and n % 2 == 0:
        c += 1
        n //= 2
    return c


def solve():
    print("[*] 启动 u=1 攻击")
    io = remote(HOST, PORT)
    for i in range(32):
        io.recvuntil(b"p = ")
        p = int(io.recvline().strip())
        # 分析 p 的 v2 特征
        s_p = get_v2(p - 1)

        # 构造 q
        # ----------------------------------------------------
        # 目标 A: q = k * p + 1  (保证 u = 1 mod p)
        # 目标 B: v2(q-1) > v2(p-1) (保证库函数先分解出 q)
        # ----------------------------------------------------
        # 因为 q - 1 = k * p，且 p 是奇数
        # 所以 v2(q - 1) = v2(k)
        # 我们只需要让 k 包含比 s_p 更多的因子 2 即可

        # 让 k 是 2^(s_p + 1) 的倍数
        target_v2_k = s_p + 1
        step = p * (1 << target_v2_k)

        # 搜索素数 q
        # q = step * m + 1
        # 只要 q 是素数，v2(q-1) 就至少是 s_p + 1，肯定比 s_p 大
        q = step + 1
        while True:
            if isPrime(q):
                break
            q += step

        print(f"[*] Round {i+1}/32: s_p={s_p}, 构造 q (v2={get_v2(q-1)})")

        # 发送 payload
        io.recvuntil(b"q: ")
        io.sendline(str(q).encode())
        resp = io.recvline()
        if b"error!" in resp:
            print(f"    [+] 攻击成功！触发了 u=1 异常。")
        else:
            print(f"    [-] 意外失败：{resp}")
            io.close()
            return

    print(io.recvall().decode().strip())
    io.close()
    print(f"[*] 总计 {count} 次攻击，耗时 {time() - start:.2f} 秒\n")
    exit()


if __name__ == "__main__":
    start = time()
    count = 0
    while 1:
        solve()
        count += 1

后面有时间再找wp学学吧，润去写毕设了……

N1CTF Junior 2026 1/2 - LargeErrors

There are something wrong on LWE

from Crypto.Util.number import *
from sage.all import *
from random import choices
from secret import flag
assert len(flag) == 23
m = 23
n = 28
p = getPrime(64)
q = getPrime(64)
N = p * q
S = vector(Zmod(N), list(flag))
e = vector(Zmod(N), choices([p, q], k=n))
B = []
A = random_matrix(Zmod(N), n, m)
M = random_matrix(ZZ, n, n)
C = random_matrix(Zmod(N), n, m)
for _ in range(3):
    A = M*A+C
    b = A*S + e
    B.append(b)
save((A,B,M), "output")

$b\equiv A*S+e\pmod n$
$e_{i}\in \{p,q\}$
$b\equiv A*S+e\pmod p$

$b\equiv A*S+\delta*q\pmod p,\delta\in\{0,1\}^{n}$
$S_{i}\in [0,255]，显然直接规约出\delta是更方便的$

$b*q^{-1}\equiv A*S*q^{-1}+\delta\pmod p$
$b'\equiv A'*S+\delta\pmod p$

剩下的过程就不写了，直接套板子，primal attack

from sage.all import *

A, B, M = load('./n1junior/LargeErrors/output.sobj')
N = A.base_ring().order()
factors = list(factor(N))
p = factors[0][0]
q = factors[1][0]
Fp = GF(p)
q_inv = inverse_mod(q, p)
A_prime = matrix(Fp, A) * q_inv
b_prime = vector(Fp, b) * q_inv
b = B[2]
m, n, esz = 28, 23, 2**0

def primal_attack2(A,b,m,n,p,esz):
    L = block_matrix(
        [
            [matrix(Zmod(p), A).T.echelon_form().change_ring(ZZ), 0],
            [matrix.zero(m - n, n).augment(matrix.identity(m - n) * p), 0],
            [matrix(ZZ, b), 1],
        ]
    )
    #print(L.dimensions())
    Q = diagonal_matrix([1]*m + [esz])
    L *= Q
    L = L.LLL()
    L /= Q
    res = L[0]
    if(res[-1] == 1):
        e = vector(GF(p), res[:m])
    elif(res[-1] == -1):
        e = -vector(GF(p), res[:m])
    s = matrix(Zmod(p), A).solve_right((vector(Zmod(p), b)-e))
    return s

s = primal_attack2(A_prime, b_prime, m, n, p, esz)
flag = ''
for i in s:
    flag += chr(i)
print(flag)
# flag{1W3_W@$_v3rY_34sy}

LilacCTF2026 - myRSA

Secrets in this RSA are congruential
The polynomial and the beautiful
Make up relations in this world
Hey
Just pick up your Sagemath, Python
And be colourful
Because this RSA is wonderful

import gmpy2
from Crypto.Util.number import isPrime, bytes_to_long
from sympy.ntheory import sqrt_mod
from sympy.ntheory.modular import crt
from secret import p, q, r, pp
import os


def oracle(x):
  root_p = sqrt_mod(x, p)
  root_q = sqrt_mod(x, q)
  root_r = sqrt_mod(x, r)
  if root_p is None or root_q is None or root_r is None:
    return "🤐"
  ans, _ = crt([p, q, r], [root_p, root_q, root_r])
  return int(ans)


assert p == pp**2 + 3 * pp + 3 and q == pp**2 + 5 * pp + 7
assert isPrime(p) and isPrime(q) and isPrime(r)

m = bytes_to_long(os.getenv("FLAG", "LilacCTF{fake_flag}").encode().strip())
n = p * q * r
e = 65537
c = pow(m, e, n)

print(f"{n = }")
print(f"{c = }")

while True:
  x = int(input("🧭 > "))
  _, is_psq = gmpy2.iroot(x, 2)
  assert not is_psq, "👿"
  assert 80 < x < 100
  print(oracle(x))
"""
n = 320463398964822335046388577512598439169912412662663009494347432623554394203670803089065987779128504277420596228400774827331351610218400792101575854579340551173392220602541203502751384517150046009415263351743602382113258267162420601780488075168957353780597674878144369327869964465070900596283281886408183175554478081038993938477659926361457163384937565266894839330377063520304463379213493662243218514993889537829099698656597997161855278297938355255410088350528543369288722795261835727770017939399082258134647208444374973242138569356754462210049877096486232693547694891534331539434254781094641373606991238019101335437
c = 80140760654462267017719473677495407945806989083076205994692983838456863987736401342704400427420046369099889997909749061368480651101102957366243793278412775082041015336890704820532767466703387606369163429880159007880606865852075573350086563934479736264492605192640115037085361523151744341819385022516548746015224651520456608321954049996777342018093920514055242719341522462068436565236490888149658105227332969276825894486219704822623333003530407496629970767624179771340249861283624439879882322915841180645525481839850978628245753026288794265196088121281665948230166544293876326256961232824906231788653397049122767633
(96, 34484956620179866074070847926139804359063142072294116788718557980902699327115656987124274229028140189100320603969008330866286764246306228523522742687628880235600852992498136916120692433600681811756379032521946702982740835213837602607673998432757011503342362501420917079002053526006602493983327263888542981905944223306284758287900181549380023600320809126518577943982963226746085664799480543700126384554756984361274849594593385089122492057335848048936127343198814676002820177792439241938851191156589839212021554296197426022622140915752674220260151964958964867477793087927995204920387657229909976501960074230485827919)
"""

$p=pp^{2}+3*pp+3$
$q=pp^{2}+5*pp+7$
$ans^{2}\equiv x\mod n$

只能拿到1组(x, ans)，并不能分解n，感觉这个预言机是没有用的()
看来只能从关系式的结构下手了

可以令，$t = 2pp + 3$
$4p=t^{2}+3$

可惜后面我都没有往曲线方向思考

看到了官方wp，奇怪的知识又进脑子了，好痒

这样的代数结构，对于模 p 下的曲线具有CM（复乘）性质
$4p=t^{2}+D\cdot y^{2}，t 被称为 Frobenius 迹$

对于 D = 3的曲线标准方程为，$y^{2}=x^{3}+b$，拥有六阶自同态，对应六种不同的形态，这种现象被称为sextic twists

在有限域 $\mathbb{F}_p$ 上的椭圆曲线 $E(\mathbb{F}_p)$，其点的个数（阶）记为 $N$。根据 Hasse 定理：$$N = p + 1 - t$$

若取t = -(2pp + 3)，则$N_{p}=q$；若取t = 2pp + 5，则$N_{q}=p$
所以，对 b 取值，我们都有 1/6 的概率碰上阶为 n 的因子(p or q)的曲线

我们有$ans^{2}\equiv 96\pmod n$
那么我们可以构造这样的一条曲线，$y^{2}\equiv x^{3}+b\pmod n$

$b=1, G(95,ans)在曲线上;$
$...;$
$b=4, G(32,ans)在曲线上;$
$...$

在这个环 $\mathbb{Z}_n$ 上的运算，实际上是分别在 $\mathbb{F}_p, \mathbb{F}_q, \mathbb{F}_r$ 上同时进行的

$若Q_{p}:n\cdot G_{p}=(q\cdot pr)\cdot G_{p}=pr\cdot(q\cdot G_{p})=\mathcal{O}$
则点 Q 在 模p 下是无穷远点，在射影坐标 $(X:Y:Z)$ 中，无穷远点意味着 $X\equiv Z \equiv 0 \pmod p，Q_{p}.X=k*p$

模q也同理，也有 1/36 的概率都是无穷远点

这道题确实是在 模p 下是无穷远点，这里 b=95 / b=32 都可以 gcd 出 p

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

n = 320463398964822335046388577512598439169912412662663009494347432623554394203670803089065987779128504277420596228400774827331351610218400792101575854579340551173392220602541203502751384517150046009415263351743602382113258267162420601780488075168957353780597674878144369327869964465070900596283281886408183175554478081038993938477659926361457163384937565266894839330377063520304463379213493662243218514993889537829099698656597997161855278297938355255410088350528543369288722795261835727770017939399082258134647208444374973242138569356754462210049877096486232693547694891534331539434254781094641373606991238019101335437
c = 80140760654462267017719473677495407945806989083076205994692983838456863987736401342704400427420046369099889997909749061368480651101102957366243793278412775082041015336890704820532767466703387606369163429880159007880606865852075573350086563934479736264492605192640115037085361523151744341819385022516548746015224651520456608321954049996777342018093920514055242719341522462068436565236490888149658105227332969276825894486219704822623333003530407496629970767624179771340249861283624439879882322915841180645525481839850978628245753026288794265196088121281665948230166544293876326256961232824906231788653397049122767633
e = 65537
E = EllipticCurve(Zmod(n), [0, 95])
G = E(1, 34484956620179866074070847926139804359063142072294116788718557980902699327115656987124274229028140189100320603969008330866286764246306228523522742687628880235600852992498136916120692433600681811756379032521946702982740835213837602607673998432757011503342362501420917079002053526006602493983327263888542981905944223306284758287900181549380023600320809126518577943982963226746085664799480543700126384554756984361274849594593385089122492057335848048936127343198814676002820177792439241938851191156589839212021554296197426022622140915752674220260151964958964867477793087927995204920387657229909976501960074230485827919)

p = int(gcd((n*G)[2], n))
d = inverse(e, p-1)
flag = long_to_bytes(int(pow(c, d, p))).decode()
print(flag)
# LilacCTF{wHy_NoT_w4tch1ng_yOutub3_with_NPoYb4mbiOg}

这就是Lenstra elliptic-curve factorization么

reference

• 星盟
• lz雷泽
• Misay
• 密码出题人swizzer