DASCTF九月赛2022

2022-09-29

以后大型比赛中的难题更新到blog2.

easyRSA

直接记录一下官方wp就好，因为感觉这个解法没啥意义，就是小范围的搜索：

#sage
c = 262857004135341325365954795119195630698138090729973647118817900621693212191529885499646534515610526918027363734446577563494752228693708806585707918542489830672358210151020370518277425565514835701391091303404848540885538503732425887366285924392127448359616405690101810030200914619945580943356783421516140571033192987307744023953015589089516394737132984255621681367783910322351237287242642322145388520883300325056201966188529192590458358240120864932085960411656176
e = 543692319895782434793586873362429927694979810701836714789970907812484502410531778466160541800747280593649956771388714635910591027174563094783670038038010184716677689452322851994224499684261265932205144517234930255520680863639225944193081925826378155392210125821339725503707170148367775432197885080200905199759978521133059068268880934032358791127722994561887633750878103807550657534488433148655178897962564751738161286704558463757099712005140968975623690058829135
n = 836627566032090527121140632018409744681773229395209292887236112065366141357802504651617810307617423900626216577416313395633967979093729729146808472187283672097414226162248255028374822667730942095319401316780150886857701380015637144123656111055773881542557503200322153966380830297951374202391216434278247679934469711771381749572937777892991364186158273504206025260342916835148914378411684678800808038832601224951586507845486535271925600310647409016210737881912119

def plus(e, n):
    m = 2
    c = pow(m, e, n)
    q0 = 1

    list1 = continued_fraction(Integer(e)/Integer(n))
    conv = list1.convergents()
    for i in conv:
        k = i.numerator()
        #print(k)
        q1 = i.denominator()
        #print(q1)

        for r in range(20):
            for s in range(20):
                d = r*q1 + s*q0
                m1 = pow(c, d, n)
                if m1 == m:
                    print(r,s)
                    return d
     
        q0 = q1
d = plus(e, n)
print(d)
print(libnum.n2s(int(pow(c,d,n))))

easySignin

队内师傅的思路，挺好的，避免用到二次剩余。首先通过逆推10次可以得到初始的a，b，c；然后把d放在mod p的多项式环下当作未知数，用init_g = d这一关系带入d，正向推10次建立环下的方程，解出d以后再用一次类似的解方程处理$t = (m+d)^2 %p$即可。

from Crypto.Util.number import *

p= 7591656713055743077369340861541583433090841738590989539280316533530045331013958613146671718809022799047779468311222607020894006899032327866283558110087799
a= 4392865163304254999527172406061971162689920565151840813033448791785156740502864894051809689255751412382468345217962713758808061870635744521996229554057672
b= 2119856022628544669301306700581535843188073099896481101405665476192582614655960576092254118367775147735092457551317887281026710342124525625026559538165667
c= 3370586754351688470908526079815435343732016329743637661764947106415792049906966624513736208696137655804912688128186282852926377345819134856707156640355705
g= 2221154642536617375933147254663757148609834736621720750750043572054496685087600339999953459509198087870095805651320901316659013390557077204194753685935362
t= 6426975621182152052236088849377616252912408340750729257254509090637526282051064469268808395760737262115678691330037039061905028548054911000486882481093832


for i in range(10):
    c = (b+c)*inverse(a,p) % p
    b = (a+b)*inverse(c,p) % p
    a = (a+c)*inverse(b,p) % p
print(a, b, c)


PR.<d> = PolynomialRing(Zmod(p))
g = d
for i in range(10):
    g = c*d^2 + b*g + a
    a = (a*b - c) % p
    b = (b*c - a) % p
    c = (c*a - b) % p


f = g-2221154642536617375933147254663757148609834736621720750750043572054496685087600339999953459509198087870095805651320901316659013390557077204194753685935362 
roots = f.roots()
d = roots[1][0]
print()
print(d)
PR.<x> = PolynomialRing(Zmod(p))
f = x^2-t
roots = f.roots()
print(roots) 
m = (roots[1][0] - d) % p
print(long_to_bytes(int(m)))
# CBCTF{cjx_H0pe_that_love_1s_forever}

LittleRSA

又是简单的二维造格…
令$t$为$t$模$N$的逆，则有$st=rN+1$，又$pt^2=kN^2+g$，两边同时乘$s^2$，得到$p(rN+1)^2=(kN^2+g)s^2$
两边同时展开，整理得到：$(pr^2-ks^2)N^2-s^2g=p(-1-2rN)$
可以构造格：$L=\left[\begin{matrix}g&N^2\1&0\end{matrix}\right]$，$(p(-1-2rN),-s^2)$是格上相对非常小的向量，于是用LLL解出即可得到$s^2$，通过$s$还原$p$分解n解rsa。
exp：

# sagemath
from sage.all import *
N = 
g = 

P = 
Q = 
matA = [[1,g],[0,N^2]]
L=Matrix(ZZ,matA)
tmp=vector(ZZ,L.LLL()[0])
print(tmp)

from Crypto.Util.number import *
from gmpy2 import *

N = 
g = 
n = 90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
c = 51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
s2 = 23756396393524410973039412877936556416335367237261779783924004759865696259188736323082185637403078187089064276667791460539863612406770767864482025455611854606913447649576317562797728150679868472915628766095898787995243685529456492434450372583995
s3 = 1703096866219569817841710120722024801172129285713276062493657151527831376599274719653327578175460913670322546273486052217558990179451330534956630028900812517189053457400581665150009

s2 = int(iroot(s2,2)[0])
s3 = int(iroot(s3,2)[0])
print(s3.bit_length())

tmp1 = inverse(s3,N)**2
p = g*inverse(tmp1,N**2)%(N**2)
q = n//p
e = 65537
phi = (p-1)*(q-1)
d = invert(e,phi)
print(long_to_bytes(pow(c,d,n)))