2023CBCTF

之前和 N1CTF 撞了，但是比赛题目质量很高，当时浅看了一下，现在补一下。

CB_Curve

利用 Grobner 基解 P 点，后续复现才知道这是HUFF曲线，根据论文方法得到曲线的定义和映射方法，这样就可得到维尔斯特拉斯形式，后续通过光滑阶求解离散对数即可。

关于 Grobner 基的应用，想到暑假0x401师傅出的一道题，后续写在这道题后面，加深一下印象。

曲线形式

\[ x(a^2y-1)≡y(bx^2-1) mod \quad p \]

曲线映射

\[ (x,y)→(\frac{bx-ay}{y-x},\frac{b-a}{y-x}) \]

目标曲线

\[ y^2≡x^3+(a+b)x^2+abx \quad mod \quad p \]

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

class CB_curve:
    def __init__(self):
        self.p = 1141741939958844590498346884870015122543626602665954681008204697160652371664923
        self.a = 727131475903635498678013730344448225340496007388151739960305539398192321065043
        self.b = 840714623434321649308065401328602364673881568379142278640950034404861312007307

    def add(self, P, Q):
        if P == -1:
            return Q
        (x1, y1) = P
        (x2, y2) = Q
        x3 = (x1+x2)*(1+self.a*y1*y2)*inverse((1+self.b*x1*x2)
                                              * (1-self.a*y1*y2), self.p) % self.p
        y3 = (y1+y2)*(1+self.b*x1*x2)*inverse((1-self.b*x1*x2)
                                              * (1+self.a*y1*y2), self.p) % self.p
        return (x3, y3)

    def mul(self, x, P):
        Q = -1
        while x > 0:
            if x & 1:
                Q = self.add(Q, P)
            P = self.add(P, P)
            x = x >> 1
        return Q

    # def negG(self, G):
    #     return self.mul(order-1, G)


# pl = [908996880816674413953945844149350915331956247471480600840221415119794882139724, 971918808384910355828135603762747020183688585728289421786279444571287619529246, 1285550352531583269956802123237391199017403081800977678246201935580429758051904, 1551774945769448705387900437472951015954157193946719575845523359198154668857591, 676185408751480221545400062950292727848016906516506232986883519673765317932582,
#       1250300209784131850574858927023046353058343552115735540789593580037130054384362, 1298409778422699298367007023890818793557023853717180295526932023194697263501748, 1332552452292482549702793642987623159617988974910321945878093492007278710993114, 1030239404875082841481045525469865919289388171602293245905162820968158543176773, 1154148024180033719999293176590867264297899817449945744942661351655533433871621]
# ph = [584297112520340495757457954416165393828472756298945167299482077258411155766756, 886432149227960827335266910774569034430464592640209168563805700117347063152246, 613528590036968449893421430816319461615130635882647544978722093413694101540550, 576162106332135829961234799085370038425761945928004579456101802617485243023987, 627570890346195626159365118862437334953500165050236216404858019114288681512171,
#       1015503424232985454098149884321288932492551183126601131968495641510550575005042, 1532737675157046782602115678180407262847166210963507805526455422934164759886583, 1540047002602145805476906585925538790245968214992837106009502002588479779602195, 505097517314409449404205152068185149808364887623922221197462411159844816865696, 873498218680784138428154510303205366133389839886911286745954821800632158315951]
ecc = CB_curve()
# G = (586066762126624229327260483658353973556531595840920560414263113786807168248797,
#      66727759687879628160487324122999265926655929132333860726404158613654375336028)
# # P = (ecc.mul(bytes_to_long(flag),G)[0],randint(1,ecc.p))
# Q = (460843895959181097343292934009653542386784127282375019764638432240505304648101,
#      739422832583403823403837831802136107593509589942947902014204968923412689379907)
a = ecc.a
b = ecc.b
p = ecc.p
# R.< x1, y1, e >= PolynomialRing(Zmod(p))
# R = PolynomialRing(Zmod(p), ['x1', 'y1', 'e'])

# F = []
# r = []
# for i in range(10):
#     r.append(ecc.mul(10-i, Q))
# for i in range(10):
#     x2, y2 = r[i]
#     f = (ph[i] - e)*(1+b*x1*x2)*(1-a*y1*y2)-(x1+x2)*(1+a*y1*y2)
#     F.append(f)
# res = Ideal(F).groebner_basis()
# [x1 + 239643535167901657800210470774814532510308869595840873642845564328410464397042, y1 + 146109242247186884695587727086539555907710369392694609972293964300672819401615, e + 716700711017198421972376297958894204723153539777056104579499803899129208364755]


E = EllipticCurve(GF(p), [0, a+b, 0, a*b, 0])
x1 = -239643535167901657800210470774814532510308869595840873642845564328410464397042 % p


G = (586066762126624229327260483658353973556531595840920560414263113786807168248797,
     66727759687879628160487324122999265926655929132333860726404158613654375336028)

# R.<y1> = PolynomialRing(GF(p))
# f = x1*(a*y1^2-1)-y1*(b*x1^2-1)
# y1 = int(f.roots()[1][0])

y1 = 672929595307990944197873882889709005621738844588134711458648048321447534353147
P = (int(x1), int(y1))
G = E((b*G[0] - a*G[1]) * inverse_mod(G[1]-G[0], p) %
      p, (b-a)*inverse_mod(G[1]-G[0], p) % p)
P = E((b*P[0] - a*P[1]) * inverse_mod(P[1]-P[0], p) %
      p, (b-a)*inverse_mod(P[1]-P[0], p) % p)
order = G.order()
order = 570870969979422295249173442435007561272085504844186092739816337605942962972880
primes = [3, 5, 16, 37, 271, 4297, 6983,
          9679, 52631, 139571, 84666937, 558977989]
logs = []
for fac in primes:
    t = int(order)//int(fac)
    log = discrete_log(t*P, t*G, operation='+')
    logs += [log]
m = crt(logs, primes)

print(long_to_bytes(m))
# b'DASCTF{goodathuff}'

ezAlgebra(DASCTF 2023 & 0X401)

题目描述

from Crypto.Util.number import getPrime, bytes_to_long


def encrypt(Wo, Xue, Hui, Le, Kai):
    Qi = 1997
    Che = Wo+Hui if Le == 1 else Wo*Hui
    while (Xue):
        Qi += (pow(Che, Xue, Kai)) % Kai
        Xue -= 1
    return Qi


l = 512
m = bytes_to_long(flag)
p = getPrime(l)
q = getPrime(l//2)
r = getPrime(l//2)
n = p * q * r
t = getrandbits(32)
c1 = encrypt(t, 4, p, 1, n)
c2 = encrypt(m, 19, t, 0, q)
c3 = encrypt(m, 19, t, 1, q)
print(f"n = {n}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")

一元 coppersimth 用 c1 求 t，从而获得 p

PR.<t>= PolynomialRing(Zmod(n))
f = t ^ 4+t ^ 3+t ^ 2+t+1997-c1
root = f.small_roots(X=2^32,beta=0.4)
print(root)
t=2915836867
kp = t ^ 4+t ^ 3+t ^ 2+t+1997-c1
p = GCD(kp, n)

根据 c2、c3 建立两个多项式

P.<m,t> = PolynomialRing(Zmod(n))
f1 = 1997 - c3
f2 = 1997 - c2
f3 = t-2915836867
for i in range(1,20):
    f1 += (m + t)^i
    f2 += (m * t)^i

虽然只有 m 未知，但使用 Grobner 基需要至少二元多项式，所以引入 t，同理引入f3 = t-2915836867，接下来采用 Grobner 获得理想基即可。

G = [f1,f2,f3]
B = Ideal(G).groebner_basis()

for x in B:
    print(x)

最终解 flag

q = 87038069032840052005520908272237788908169043580221040711149494083975743478969
m = -21158731716376226090392498841915660119151249151578293634082749989659307225047065454562556490794720241251831294269248252992828782428316834166828404876181491874871787144664849984606114249820338190252050491223066273953777506705536480844475141933848618113343415375867066617512805575869013694523034573111259114274 % q
for i in range(10000000):
    flag = i*q+m
    flag = long_to_bytes(flag)
    if b'dasctf' in flag:
        print(flag)
        # break

CB_RSA

from gmpy2 import *
from Crypto.Util.number import *
from libnum import *
import random
n1 = 65634094430927080732256164808833233563732628654160389042977689628512527168256899310662239009610512772020503283842588142453533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554634493581962527475555869292091755676130810562421465063412235309
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802940810851806104430306195931179902098180199167945649526235613636163362672777298968943319216325949503045377100235181706964846408396946496139224344270391027205106691880999410424150216806861393
(e1, noise1, c1) = (1743, 44560588075773853612820227436439937514195680734214431948441190347878274184937952381785302837541202705212687700521129385632776241537669208088777729355349833215443048466316517110778502508209433792603420158786772339233397583637570006255153020675167597396958251208681121668808253767520416175569161674463861719776, 65643009354198075182587766550521107063140340983433852821580802983736094225036497335607400197479623208915379722646955329855681601551282788854644359967909570360251550766970054185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853621152905983)
(e2, noise2, c2) = (1325, 35282006599813744140721262875292395887558561517759721467291789696459426702600397172655624765281531167221787036009507833425145071265739486735993631460189629709591456017092661028839951392247601628468621576100035700437892164435424035004463142959219067199451575338270613300215815894328788753564798153516122567683, 50327632090778183759544755226710110702046850880299488259739672542025916422119065179822210884622225945376465802069464782311211031263046593145733701591371950349735709553105217501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773715759733714)
c = 124349762993424531697403299350944207725577290992189948388824124986066269514204313888980321088629462472088631052329128042837153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177197863522573410860341245613331398610013697803459403446614221369
e = 0x10001
f = open('enc.txt','r').read().strip().split('n')
cipher = [i for i in f]
cipher = cipher[:-1]
cipher = [int(i) for i in cipher]
flag = ""
for i in cipher:
    if jacobi(i,n1)==-1:
        flag += '0'
    else:
        flag += '1'

p = int(flag[::-1],2)
print('p = '+str(p))
def attack(c1, c2, noise1, noise2,  e1, e2 , n):

    PR.<x>=PolynomialRing(Zmod(n))
    g1 = (x + noise1)^e1 - c1
    g2 = (x + noise2)^e2 - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    print(gcd(g1, g2))
    return -gcd(g1, g2)[0]

q = int(attack(c1, c2, noise1, noise2,  e1, e2 , n2))
print('q = ' +str(q))
n = p*q
phi = (p-1)*(q-1)
d = inverse_mod(e,phi)
m = power_mod(c,d,n)
print(long_to_bytes(m))