2024-bi0sCTF-wp-crypto

昨天中午赶回了学校，收拾了下东西后看见余师傅在喊来打国际赛，就报了个名打打。最后是做出了四个题目，就简单写下wp。

赛中没有做出的前面会带*。

lalala

题目描述：

Just a few equations

题目：

from random import randint
from re import search

flag = "bi0sctf{%s}" % f"{randint(2**39, 2**40):x}"

p = random_prime(2**1024)
unknowns = [randint(0, 2**32) for _ in range(10)]
unknowns = [f + i - (i%1000)  for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())]

output = []
for _ in range(100):
    aa = [randint(0, 2**1024) for _ in range(1000)]
    bb = [randint(0, 9) for _ in range(1000)]
    cc = [randint(0, 9) for _ in range(1000)]
    output.append(aa)
    output.append(bb)
    output.append(cc)
    output.append(sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p)

print(f"{p = }")
print(f"{output = }")

output有30多M就不放在这里，有兴趣的师傅可以找我要。简单叙述一下题目内容就是：

• 生成一个39-40bit的随机数，并转化为十六进制(十个字符)，作为flag
• 随机生成一个1024bit的素数p，以及长度为10的列表unknowns，其中元素都在0-2^32之间
• 把unknowns里的每个值的低位，换成刚才的十六进制串的对应位置字符的ascii码
• 生成一百组等式，每组等式的形式如下，并且给出aj、bj、cj的值：

$$sum_i = \sum_{j=1}^{1000}(a_j + unk[b_j]^2unk[c_j]^3) \quad(mod\;p)$$

我的第一反应是，aj肯定是没有用的，所以可以直接把aj的累加和都去掉，得到式子：

$$temp = \sum_{j=1}^{1000}(unk[b_j]^2unk[c_j]^3) \quad(mod\;p)$$

然后会发现，这样处理之后，右边的式子本身不过是5个32bit内的数字相乘 ，所以数量级远小于p，就可以把p脱掉：

$$temp = \sum_{j=1}^{1000}unk[b_j]^2unk[c_j]^3$$

由于unknowns长度仅有10，也就是只有10个变量，所以把这一百个多项式全部写出来groebner也许能行(因为度并不大，方程本身也很规整，利于groebner)，然后我就实现了一下发现的确可以。

exp：

import ast
from tqdm import *

p = 22164857548872153350792863287126662739346790382724883568469825455088689119474784066358095106688985128245096556482593315395509994112330842037731896432716074587916002372658113733392392830971642878227300074751441475110802528284293674049241201403401496426351459462195992798867652944173025546970871261462401766951
with open(r"D:\CTF_challs\py\crypto\2024\Bi0sCTF 2024\lalala_output1.py","r") as f:
    output = ast.literal_eval(f.read())

#part1 groebner
P = PolynomialRing(ZZ, [f"x{i}"  for i in range(10)])
unknowns = P.gens()

F = []
for i in trange(100):
    aa,bb,cc,sum1 = output[4*i+0],output[4*i+1],output[4*i+2],output[4*i+3]
    temp1 = (sum1 - sum(aa)) % p
    temp1 = temp1
    
    t = 0
    for j in range(1000):
        t += unknowns[bb[j]]^2*unknowns[cc[j]]^3
    F.append(t-temp1)

f1 = unknowns[9] - 957068055
res = Ideal(F).groebner_basis()
for i in res:
    if(len(list(i)) < 4):
        print(i)

#part2 solve item by item
x9 = 957068055
x8 = 1828210097
x0 = 3775734056
x1 = 4016567100
x2 = 4131014053
x3 = 2073862050
x4 = 3322165050
x5 = 1087853097
x6 = 974553101
x7 = 2564674049
x8 = 1828210097
x9 = 957068055
for i in [x0,x1,x2,x3,x4,x5,x6,x7,x8,x9]:
    print(chr(i%1000),end = "")
    
#bi0sctf{8d522ae1a7}

做完后又想了想为什么偏偏就是100组等式，然后就明白了一点：如果把$t = unk[b_j]^2unk[c_j]^3$这一个整体看作一个变量的话，由于unknowns一共只有10个数，就刚好会对应100个变量t。那么整个题目就变成了一个100个方程、100个变量的线性方程组，就可以直接用矩阵来解。解出过后直接找5次幂对应的变量来开五次方根就能得到所有结果了。

challengename

题目描述：

challenge description

题目：

from ecdsa.ecdsa import Public_key, Private_key
from ecdsa import ellipticcurve
from hashlib import md5
import random
import os
import json

flag = open("flag", "rb").read()[:-1]

magic = os.urandom(16)

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = ###REDACTED###
b = ###REDACTED###
G = ###REDACTED###

q = G.order()

def bigsur(a,b):
    a,b = [[a,b],[b,a]][len(a) < len(b)]
    return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:]))[:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])][i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])

def bytes_to_long(s):
    return int.from_bytes(s, 'big')

def genkeys():
    d = random.randint(1,q-1)
    pubkey = Public_key(G, d*G)
    return pubkey, Private_key(pubkey, d)

def sign(msg,nonce,privkey):
    hsh = md5(msg).digest()
    nunce = md5(bigsur(nonce,magic)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce))
    return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)})

def enc(privkey):
    x = int(flag.hex(),16)
    y = pow((x**3 + a*x + b) % p, (p+3)//4, p)
    F = ellipticcurve.Point('--REDACTED--', x, y)
    Q = F * privkey.secret_multiplier
    return (int(Q.x()), int(Q.y()))

pubkey, privkey = genkeys()
print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y())))
print("Encrypted flag:",enc(privkey))

nonces = set()

for _ in '01':
    try:
        msg = bytes.fromhex(input("Message: "))
        nonce = bytes.fromhex(input("Nonce: "))
        if nonce in nonces:
            print("Nonce already used")
            continue
        nonces.add(nonce)
        print(sign(msg,nonce,privkey))
    except ValueError:
        print("No hex?")
        exit()

题目基于ECDSA，他会先发送作为公钥的dG点，以及被按如下方式加密的flag密文：

$$F = encode(flag)$$ $$Q = dF$$

也就是把flag编码到ECC上再求其d倍点。

那么要求得flag，就要恢复ECC的所有参数，以及求出私钥d。为此靶机提供了两次交互机会，可以输入msg和nonce进行签名，并且nonce不能重复。

首先是恢复ECC的参数，这里其实看这个p，然后去搜一搜就能找到一条标准曲线，验证一下点dG确实在曲线上，这就完了。退一步来说，即使是他自定义的曲线，由于a、b这种写法肯定是静态的，所以可以多交互几次，取每一次的dG点来做groebner也能恢复所有参数。

下一步就是怎么求解d，先把ECDSA的签名式写一下：

$$s = k^{-1}(H(msg) + dr) \quad(mod\;q)$$

其中，q是ECC的order，k是由输入的nonce产生的临时密钥。然后题目里用了一个很冗长的函数来用nonce计算k：

def bigsur(a,b):
    a,b = [[a,b],[b,a]][len(a) < len(b)]
    return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:]))[:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])][i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])

所以其实主要任务是找到一个碰撞，即：

bigsur(nonce1,magic) == bigsur(nonce2,magic)

magic是未知的16个随机字节，所以只能在输入的nonce上想办法动动手脚。而注意到输入其实是用bytes.fromhex()实现的，所以也不用仔细读这个函数了，测试一下”00”和”0000”就能满足要求。

exp：

from Pwn4Sage.pwn import *
from hashlib import md5
from Crypto.Util.number import *

#part1 guess number(or use get more points for times and use groebner--since a,b is static)
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
q = E.order()

sh = remote("13.201.224.182",30773)

#part2 forge
nonce1 = b"00"
nonce2 = b"0000"

sh.recvuntil(b"Public key: ")
dG = eval(sh.recvline().strip().decode())
sh.recvuntil(b"ncrypted flag: ")
flag_enc = eval(sh.recvline().strip().decode())


msg11 = b"11"
hsh1 = md5(msg11).digest()
hsh1 = bytes_to_long(hsh1)
sh.sendline(msg11.hex().encode())
sh.sendline(b"00")
sh.recvuntil(b"Message: Nonce: ")
sig1 = eval(sh.recvline().strip().decode())
r1,s1 = eval(sig1["r"]),eval(sig1["s"])


msg22 = b"21"
hsh2 = md5(msg22).digest()
hsh2 = bytes_to_long(hsh2)
sh.sendline(msg22.hex().encode())
sh.sendline(b"0000")
sh.recvuntil(b"Message: Nonce: ")
sig2 = eval(sh.recvline().strip().decode())
r2,s2 = eval(sig2["r"]),eval(sig2["s"])

#part3 get secret key and get flag
d = (s1*hsh2-s2*hsh1)*(inverse(r2*s1-r1*s2,q)) % q
e = inverse(d,q)
flag = e*E(flag_enc)


print(long_to_bytes(int(flag[0])))

#bi0sctf{https://bit.ly/3I0zwtG}

rr

题目描述：

Down the rabbithole...

题目：

from Crypto.Util.number import *
from FLAG import flag
from random import randint

flag = bytes_to_long(flag)
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
ks = [randint(0, rr**(i+1)) for i in range(20)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), (1<<7)-1, n)
c2 = pow(flag, (1<<16)+1, n)
ks = [pow(69, k, rr**(i+2)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")

输出内容也很长，就不放了。

简单来说，题目给出了以下几个式子：

$$c_1 = (\sum_{i=0}^{19}k_i\times flag^i)^{127} \quad(mod\;n)$$ $$c_2 = flag^{65537} \quad(mod\;n)$$ $$ks_i = 69^{k_i} \quad(mod\;rr^{i+2})$$

求的思路也很明确，先根据最后一组等式把ks全部求出来，然后前面两个等式做gcd即可。

要用最后一个等式求出ks就要求解dlp，但是rr这个数字是2t+1形的素数，t是难以分解的大合数，所以Pohlig之类的方法就不用考虑了。

但是有个显著的问题是模数至少都是二次幂，对这种模数来说可以用p-adic的discrete_log去计算出模p^(i-1)下的值，只有一次幂下难以求解。因此这个题目里求dlp这个问题就搞定了。

这种做法看maple博客里有介绍，既可以理解为一种二项式定理的延申；也可以理解为其实是找到了一种从$Z_{p^i}^*$到$Z_{p^{i-1}}^+$的同态，因为对于后者的加法群来说求dlp其实就是求逆

其实原理的话要说明白也并不算难事，这里就简单展开一下。比如对于一个模p^2下的等式：

$$y = g^x \quad(mod\;p^2)$$

要求dlp，由于p是素数，所以对于模p^2下的任意一个数a都有：

$$a^{(p-1)p} = 1 \quad(mod\;p^2)$$

有了这个过后，给原式的两侧都再求p-1次幂就得到：

$$y^{p-1} = (g^{p-1})^x \quad(mod\;p^2)$$

这样做的好处是，两边的元素的阶由原来的$(p-1)p$的因子，变成了$p$的因子。同时，由费马小定理知道：

$$a^{p-1} = 1 \quad(mod\;p)$$

所以上面的两个元素都可以写成：

$$y^{p-1} = 1 + k_1p$$ $$g^{p-1} = 1+ k_2p$$

那么对于模p^2下的g^(p-1)^x来说，就可以由二项式定理展开变成：

$$(g^{p-1})^x = (1+k_2p)^x = 1 + xk_2p \quad(mod\;p^2)$$

所以最终就有：

$$1 + xk_2p = 1 + k_1p \quad(mod\;p^2)$$

也就得到了(注意两边消去p的同时，模数也要消)：

$$x = k_1k_2^{-1} \quad(mod\;p)$$

就解决了DLP，更高次幂道理是基本一致的。

求出k后就是两个明文做gcd，由于度比较大所以选择HGCD，同时由于两个多项式根相同，所以可以将f2先模f1后再做HGCD能更节省时间。

exp：

from Crypto.Util.number import *
from random import randint
from tqdm import *

n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 
ks = 
c1 = 
c2 = 
final = []

#part1 dlog by p-adic
for i in trange(20):
    R = Zp(rr, prec=i+2)
    x = (R(ks[i]).log() / R(69).log()).lift()
    final.append(x)



#part2 HGCD
def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

PR.<x> = PolynomialRing(Zmod(n))
f1 = sum(k*x**i for i, k in enumerate(final))^((1<<7)-1) - c1
f2 = x^((1<<16)+1) - c2
f2 = f2 % f1
res = GCD(f1,f2)

m = -res.monic().coefficients()[0]
flag = long_to_bytes(int(m))
print(flag)

#bi0sctf{https://www.youtube.com/watch?v=soDR-BctVeE___1e9c4e8dba79812bd81ec4c2}

daisy_bell

题目描述：

I can't afford a carriage

题目：

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

p = getPrime(1024)
q = getPrime(1024)
n = p*q
c = pow(bytes_to_long(flag), 65537, n)

print(f"{n = }")
print(f"{c = }")
print(f"{p>>545 = }")
print(f"{pow(q, -1, p) % 2**955 = }")


"""
n = 13588728652719624755959883276683763133718032506385075564663911572182122683301137849695983901955409352570565954387309667773401321714456342417045969608223003274884588192404087467681912193490842964059556524020070120310323930195454952260589778875740130941386109889075203869687321923491643408665507068588775784988078288075734265698139186318796736818313573197531378070122258446846208696332202140441601055183195303569747035132295102566133393090514109468599210157777972423137199252708312341156832737997619441957665736148319038440282486060886586224131974679312528053652031230440066166198113855072834035367567388441662394921517
c = 7060838742565811829053558838657804279560845154018091084158194272242803343929257245220709122923033772911542382343773476464462744720309804214665483545776864536554160598105614284148492704321209780195710704395654076907393829026429576058565918764797151566768444714762765178980092544794628672937881382544636805227077720169176946129920142293086900071813356620614543192022828873063643117868270870962617888384354361974190741650616048081060091900625145189833527870538922263654770794491259583457490475874562534779132633901804342550348074225239826562480855270209799871618945586788242205776542517623475113537574232969491066289349
p>>545 = 914008410449727213564879221428424249291351166169082040257173225209300987827116859791069006794049057028194309080727806930559540622366140212043574
pow(q, -1, p) % 2**955 = 233711553660002890828408402929574055694919789676036615130193612611783600781851865414087175789069599573385415793271613481055557735270487304894489126945877209821010875514064660591650207399293638328583774864637538897214896592130226433845320032466980448406433179399820207629371214346685408858
"""

题目内容很简短，基于RSA加密并且给了几个额外信息：

• p的部分高位(1024-545bit)
• q关于p的逆元的低位(955bit)

首先由p的高位可以得到q的高位，这部分用整除就能轻松做到：

qh = (n //(ph << bit)) >> (bit+1)

少取一位的原因是可能会存在进位误差。

那么接下来就是利用第二个额外信息，记这个值是t，就有：

$$t = 2^{955}t_h + t_l$$

其中th未知，tl已知。代回第二个式子就有：

$$(2^{955}t_h + t_l)q = 1 +kp$$

两边同时乘q：

$$(2^{955}t_h + t_l)q^2 - q = kn$$

那么在模n下就有：

$$(2^{955}t_h + t_l)q^2 - q =0 \quad(mod\;n)$$

由于有q的部分高位，所以可以进一步写成：

$$(2^{955}t_h + t_l)(2^{546}q_h+q_l)^2 - (2^{546}q_h+q_l) =0 \quad(mod\;n)$$

那么整个式子就可以看成是关于th和ql两个小量的二元copper了。

但是这样出不来结果，开始以为是界的问题，就对ql做了点小优化：因为q是素数所以LSB肯定是1。然后式子就变成：

$$(2^{955}t_h + t_l)(2^{546}q_h+2q_l+1)^2 - (2^{546}q_h+2q_l+1) =0 \quad(mod\;n)$$

但是这样做还是得不到结果。换了下以前用过的bivariate也不太行。

然后突发奇想去搜了搜出题人的id，居然真的有发现他2022年写的某个wp里的一个板子：

CTF/bi0sctf2022/insane-key.md at main · victim1307/CTF (github.com)

然后用这个板子跑就出了。

exp：

from Crypto.Util.number import *
from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence
from tqdm import tqdm
import itertools

def solve_system_with_jacobian(H, f, bounds, iters=100, prec=1000):
    vs = list(f.variables())
    n = f.nvariables()
    x = f.parent().objgens()[1]
    x_ = [var(str(vs[i])) for i in range(n)]
    for ii in tqdm(Combinations(range(len(H)), k=n)):
        f = symbolic_expression([H[i](x) for i in ii]).function(x_)
        jac = jacobian(f, x_)
        v = vector([t // 2 for t in bounds])
        for _ in range(iters):
            kwargs = {str(vs[i]): v[i] for i in range(n)}
            try:
                tmp = v - jac(**kwargs).inverse() * f(**kwargs)
            except ZeroDivisionError:
                return None
            v = vector((numerical_approx(d, prec=prec) for d in tmp))
        v = [int(_.round()) for _ in v]
        if H[0](v) == 0:
            return tuple(v)
    return None


def coppersmith(f, bounds, m=1, d=None):
    # https://github.com/josephsurin/lattice-based-cryptanalysis/blob/main/lbc_toolkit/problems/small_roots.sage

    if d is None:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    f_ = (f // f.lc()).change_ring(ZZ)
    f = f.change_ring(ZZ)
    l = f.lm()

    M = []
    for k in range(m+1):
        M_k = set()
        T = set((f ^ (m-k)).monomials())
        for mon in (f^m).monomials():
            if mon//l^k in T:
                for extra in itertools.product(range(d), repeat=f.nvariables()):
                    g = mon * prod(map(power, f.variables(), extra))
                    M_k.add(g)
        M.append(M_k)
    M.append(set())

    shifts = PolynomialSequence([], f.parent())
    for k in range(m+1):
        for mon in M[k] - M[k+1]:
            g = mon//l^k * f_^k * N^(m-k)
            shifts.append(g)

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

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

    print("LLL...")
    B = B.dense_matrix().LLL()
    print("Done")

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

    H = PolynomialSequence([h for h in B*monomials if not h.is_zero()])
    return solve_system_with_jacobian(H, f, bounds)


bit = 545
bit2 = 955
n = 13588728652719624755959883276683763133718032506385075564663911572182122683301137849695983901955409352570565954387309667773401321714456342417045969608223003274884588192404087467681912193490842964059556524020070120310323930195454952260589778875740130941386109889075203869687321923491643408665507068588775784988078288075734265698139186318796736818313573197531378070122258446846208696332202140441601055183195303569747035132295102566133393090514109468599210157777972423137199252708312341156832737997619441957665736148319038440282486060886586224131974679312528053652031230440066166198113855072834035367567388441662394921517
c = 7060838742565811829053558838657804279560845154018091084158194272242803343929257245220709122923033772911542382343773476464462744720309804214665483545776864536554160598105614284148492704321209780195710704395654076907393829026429576058565918764797151566768444714762765178980092544794628672937881382544636805227077720169176946129920142293086900071813356620614543192022828873063643117868270870962617888384354361974190741650616048081060091900625145189833527870538922263654770794491259583457490475874562534779132633901804342550348074225239826562480855270209799871618945586788242205776542517623475113537574232969491066289349
ph = 914008410449727213564879221428424249291351166169082040257173225209300987827116859791069006794049057028194309080727806930559540622366140212043574
tl = 233711553660002890828408402929574055694919789676036615130193612611783600781851865414087175789069599573385415793271613481055557735270487304894489126945877209821010875514064660591650207399293638328583774864637538897214896592130226433845320032466980448406433179399820207629371214346685408858

qh = (n //(ph << bit)) >> (bit+1)

PR.<x,y> = PolynomialRing(Zmod(n))
f = (2^bit2*y + tl)*(qh*2^(bit+1) + 2*x + 1)^2 - (qh*2^(bit+1) + 2*x + 1)

ql,th = coppersmith(f, bounds=(2^bit, 2^(1024-bit2)), m=3, d=2)
qh = (n //(ph << bit)) >> (bit+1)
q = qh*2**(bit+1) + 2*ql + 1
p = n // q

d = inverse(65537,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

#bi0sctf{https://www.youtube.com/watch?v=uerNtYhgzSw___f4e2788de0dbce918e411f35}

*Katyusha’s Campervan

题目描述：

daisy shall be avenged

题目：

from Crypto.Util.number import *
from random import randint
from FLAG import flag

p = getPrime(1024)
q = getPrime(1024)
e = getPrime(132)
n = p*q
hint = pow(e, -1, (p-1)*(q-1))
hint %= p-1
hint %= 2**892
c = pow(3, int.from_bytes(flag), n**5) * pow(randint(0, n**5), n**4, n**5) % n**5

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

"""
n = 9722343735487336242847355367175705096672092545117029199851527087227001665095112331406581010290318957921703096325328326862768861459201224096506317060919486835667369908780262880850949861734346363939614200227301344831209845565227637590016962469165064818450385339408084789219460490771570003649248250098125549751883777385917121014908647963900636814694225913533250242569263841750262192296795919177720443516042006972193940464844059718044438878017817432336475087436031866077325402373438547950481634275773767410248698596974769981162966656910136575149455523084473445761780201089182021418781347413453726696240548842411960178397
e = 5323153428600607366474827268153522064873
c = 9128106076400211790302891811252824557365859263295914819806672313027356017879597156259276057232557597614548050742418485365280305524694004426832069896531486671692562462063184624416012268348059935087037828161901243824582067161433586878141008884976330185561348052441637304755454643398179479215116505856245944555306345757777557395022121796068140566220391012921030768420736902592726104037200041403396506760483386523374366225161516294778224985920562226457769686733422726488624795847474711454397538514349555958637417188665977095558680525349235100286527905789576869572972662715040982208185436819557790062517857608731996417066519220133987864808243896151962316613504271341630230274953625158957103434031391582637694278277176886221304131078005240692954168656292222792833722555464070627220306776632641544334188357810067577550784029449834217848676080193960627138929032912578951880151284003878323853182114030012207949896373695734783631698004600675811512726913649141626146115066425891236975554237158682938964099745220780884079884347052906073216530490633243676915134831324804418410566989306886192743687590855529757605789691981493863292029273401139254934543448966341439303948513266699261650278938684067402860913507689842621595391519090227639907684629841162983852454124546030986411283762938101536264676221777904450717178547838152674410566294280937400196290368544481636850750666313771438253636667634601122561235018292316232335633111595474772273810349284893171480302604833719250453453781210093266339454843926482821341993360016434693250661347303203216948599305102121353574445652764255573536572077762409837628479280331295047290459975370026620838169978316921035609492162085052786943829915442906137063599836720584533200385074702683101049336194258783047318183521466098437420153628598968954236332678203275614402446435216223033804260963642393142002417568855964535316709986640977596845897721671783670070696907220894520837335160816494605130683705587464386202643385688263935088026204614056121745160246499509455752793089324629215884008499726564579763845757062068182946721730306128755414268910929410742220199282343421146810430121947827801171056425435942640932150535954546458772114121498557119913825127286832860975814307160175273154886250581960709573672488119996389986116735407178214281982766051391618187878672106737928646489671994503814871652107136752677107398141842179907758909246276653861569864776043204134345135427118784118473462309509988521112691717301811627018054555866015966545532047340607162395739241626423495285835953128906640802690450118128515355353064004001500408400502946613169130088974076348640048144323898309719773358195921400217897006053213222160549929081452233342133235896129215938411225808985658983546168950790935530147276940650250749733176085747359261765601961315474656996860052862883712183817510581189564814317141703276878435707070103680294131643312657511316154324112431403040644741385541670392956841467233434250239028068493523495064777560338358557481051862932373791428839612299758545173203569689546354726917373906408317003812591905738578665930636367780742749804408217333909091324486584514813293
hint = 27203100406560381632094006926903753857553395157680133688133088561775139188704414077278965969307544535945156850786509365882724900390893075998971604081115196824585813017775953048912421386424701714952968924065123981186929525951094688699758239739587719869990140385720389865
"""

可以看出依然是个copper题目，这次他给了dp的低892位，并且把flag做如下加密：

$$c = 3^ma^{n^4} \quad(mod\;n^5)$$

a是个未知的随机数，要求还原m。

肯定还是先要找出式子来copper才行，既然给的是dp高位，那就要从以下式子出发：

$$ed_p = 1 \quad(mod\;p-1)$$

展开一下有：

$$e(2^{892}d_{ph}+d_{pl}) = 1 +k(p-1)$$

按以往的套路来说，由于k小于e所以可以遍历k来copper求dph。但是这里的e是个132bit的素数，虽然还是比较小，但是爆破显然不可能了，因此思路就放在了多元copper上。

可以发现这个式子在模p下有：

$$e(2^{892}d_{ph}+d_{pl}) + k -1 = 0 \quad(mod\;p)$$

dph和k都是132bit的小量，按理来说也许有机会去二元copper出来。但是遗憾的是确实不行。

然后我先是莽试了一下这样做：

$$p(e(2^{892}d_{ph}+d_{pl}) + k -1) = 0 \quad(mod\;n)$$

也就是两边同乘p，变成模n下的三元copper。然后用上一题提到的板子打，发现这个板子确实很猛，对于110bit以下的可以直接把p都给copper出来。但是110bit以上他也没什么办法了。

然后其实谈到这个问题的论文也有，不过看了一下他用的办法就是遍历k而已：

(PDF) New RSA vulnerabilities using lattice reduction methods / (researchgate.net)

然后也搜到了个类似的题目：

dp_high ISITDTU CTF 2022 - Connor M (connor-mccartney.github.io)

这个题目泄露的是dp的高位，感觉上来说区别好像不大。但是其实的确有很大区别，因为对于dp的高位泄露来说，拆出的式子可以把dpl与k的和看成是一个小量，就可以直接用模p下的一元copper来求解，但对于do低位泄露来说，由于前面有2^t，这个方法就不行了。然后我就放弃了。

然后就是今早起来看见discord在讨论，发现有个师傅给出了一个两个题都能通用的板子：

kionactf/coppersmith at dc5c4a7ef204a452a6eec152f17f8b2be784b709 (github.com)

多项式就用模p那个就行了。但是这个东西库好像有点多，改天再配配看。

然后就是dbt师傅提到了有一篇相关论文里的coppersmith的shift多项式构造也可以跑出这个题目的结果：

55717.pdf (scitepress.org)

不过我最后是看另一位师傅说的来解的：

一直以为d是copper造的多项式的度，现在看来并不是这样，感觉要重新学习一下这个函数的用法。

得到了p、q之后面对的问题就是怎么通过下面这个式子还原m：

$$c = 3^ma^{n^4} \quad(mod\;n^5)$$

由于a未知，所以肯定要消掉，这一部分这一部分我是这样处理：先把式子转到模p^5下得到(转到模p^5下也好用rr里的方法求dlp)：

$$c = 3^ma^{p^4q^4} \quad(mod\;p^5)$$

然后消去a就只需要：

$$c^{p-1} = 3^{m(p-1)}a^{(p-1)p^4q^4} = 3^{m(p-1)}\quad(mod\;p^5)$$

也就有：

$$c^{p-1} = (3^{p-1})^m \quad(mod\;p^5)$$

然后依然是利用p-adic求dlp就得到m模p^4下的值，但是求完发现不对，想了很久才发觉估计是m很长所以还要crt。求出flag发现是：

b'bi0sctf{https://www.youtube.com/watch?v=ugaq46wedOk__________09f05ff4f5d5b6c2f}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            '

果然填充了很多，没道理的。

exp：

from Crypto.Util.number import *
import itertools
from sympy.ntheory.modular import crt

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 []

#part1 copper to get dph and k
L = 132
n = 9722343735487336242847355367175705096672092545117029199851527087227001665095112331406581010290318957921703096325328326862768861459201224096506317060919486835667369908780262880850949861734346363939614200227301344831209845565227637590016962469165064818450385339408084789219460490771570003649248250098125549751883777385917121014908647963900636814694225913533250242569263841750262192296795919177720443516042006972193940464844059718044438878017817432336475087436031866077325402373438547950481634275773767410248698596974769981162966656910136575149455523084473445761780201089182021418781347413453726696240548842411960178397
e = 5323153428600607366474827268153522064873
c = 9128106076400211790302891811252824557365859263295914819806672313027356017879597156259276057232557597614548050742418485365280305524694004426832069896531486671692562462063184624416012268348059935087037828161901243824582067161433586878141008884976330185561348052441637304755454643398179479215116505856245944555306345757777557395022121796068140566220391012921030768420736902592726104037200041403396506760483386523374366225161516294778224985920562226457769686733422726488624795847474711454397538514349555958637417188665977095558680525349235100286527905789576869572972662715040982208185436819557790062517857608731996417066519220133987864808243896151962316613504271341630230274953625158957103434031391582637694278277176886221304131078005240692954168656292222792833722555464070627220306776632641544334188357810067577550784029449834217848676080193960627138929032912578951880151284003878323853182114030012207949896373695734783631698004600675811512726913649141626146115066425891236975554237158682938964099745220780884079884347052906073216530490633243676915134831324804418410566989306886192743687590855529757605789691981493863292029273401139254934543448966341439303948513266699261650278938684067402860913507689842621595391519090227639907684629841162983852454124546030986411283762938101536264676221777904450717178547838152674410566294280937400196290368544481636850750666313771438253636667634601122561235018292316232335633111595474772273810349284893171480302604833719250453453781210093266339454843926482821341993360016434693250661347303203216948599305102121353574445652764255573536572077762409837628479280331295047290459975370026620838169978316921035609492162085052786943829915442906137063599836720584533200385074702683101049336194258783047318183521466098437420153628598968954236332678203275614402446435216223033804260963642393142002417568855964535316709986640977596845897721671783670070696907220894520837335160816494605130683705587464386202643385688263935088026204614056121745160246499509455752793089324629215884008499726564579763845757062068182946721730306128755414268910929410742220199282343421146810430121947827801171056425435942640932150535954546458772114121498557119913825127286832860975814307160175273154886250581960709573672488119996389986116735407178214281982766051391618187878672106737928646489671994503814871652107136752677107398141842179907758909246276653861569864776043204134345135427118784118473462309509988521112691717301811627018054555866015966545532047340607162395739241626423495285835953128906640802690450118128515355353064004001500408400502946613169130088974076348640048144323898309719773358195921400217897006053213222160549929081452233342133235896129215938411225808985658983546168950790935530147276940650250749733176085747359261765601961315474656996860052862883712183817510581189564814317141703276878435707070103680294131643312657511316154324112431403040644741385541670392956841467233434250239028068493523495064777560338358557481051862932373791428839612299758545173203569689546354726917373906408317003812591905738578665930636367780742749804408217333909091324486584514813293
hint = 27203100406560381632094006926903753857553395157680133688133088561775139188704414077278965969307544535945156850786509365882724900390893075998971604081115196824585813017775953048912421386424701714952968924065123981186929525951094688699758239739587719869990140385720389865


PR.<x,y> = PolynomialRing(Zmod(n))
f = e*(2^(1024-L))*x + y - 1 + e*hint
res = small_roots(f,bounds=(2^L,2^L),m=1,d=8)[0]
dph,k = res
dp = (2^(1024-L))*dph + hint
p = int((e*dp-1) // k + 1)
q = int(n // p)


#part2 get m on p-adic and q-adic
ccp = pow(c,p-1,p**5)
R = Zp(p, prec=5)
xp = (R(ccp).log() / R(pow(3,p-1,p^5)).log()).lift()

ccq = pow(c,q-1,q**5)
R = Zp(q, prec=5)
xq = (R(ccq).log() / R(pow(3,q-1,q^5)).log()).lift()


#part3 crt and get flag
m = crt([p^4,q^4],[xp,xq])[0]
print(long_to_bytes(int(m)))

#bi0sctf{https://www.youtube.com/watch?v=ugaq46wedOk__________09f05ff4f5d5b6c2f}

*Predictable

题目描述：

Can you help me test out this PRNG I implemented? I'm inserting a backdoor, but I'm sure you can't find it. Oh btw, I did some optimizing, so version 2 is faster. You can still try out version 1 though. They're the same anyway.

题目没有附件，花一段时间连上靶机过后发现会给两个点，然后可以生成随机数和预测随机数，应该是预测成功就给flag。

因为有两个点，结合提示的backdoor，盲猜了一下可能是Dual EC，但是这两个点都求不出P=dQ或是Q=dP这种关系，也没对上其他脑电波，没所以就放弃了。

今早看discord听说是有关点加和点乘的时间侧信道攻击，后来又问了问rec师傅，rec师傅又问了问他们做出这题的SUS的队员，发现其实前面的加载时间是用来求出d的，具体来说，进度每跳一次，就是快速幂计算点乘的一个bit。慢的对应1，快的对应0，如此就可以还原出后门需要的d，然后就是个基础的Dual EC预测了。