2022 DASCTF X CBCTF九月赛

DASCTF X CBCTF 2022九月挑战赛

LittleRSA

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
phi = (p-1)*(q-1)
e = 65537
n = p * q
c = pow(m, e, n)

s = getPrime(300)
N = getPrime(2048)
g = p * inverse(s,N)**2 % (N**2)
print(N)
print(g)
print(n)
print(c)
'''
N = 19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
g = 101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
n = 90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
c = 51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
'''

有如下公式
$$
g = p*s^{-2}\quad mod\ N^2\quad==>\quad g*s^2=p\quad mod\ N \tag{1}
$$
所以构造格如下
$$
M=\left[
\matrix{
1& g\\
0 & N
}
\right]
$$
稍微解释一下。根据公式(1)有
$$
g*s^2-k*N=p
$$
那么
$$
\left[
\matrix{
s^2&-k
}
\right]
*
\left[
\matrix{
1& g\\
0 & N
}
\right]
=
\left[
\matrix{
s^2&p
}
\right]
$$
也就是说可以通过对矩阵M进行格基规约得到含p的向量。

详细参考：从一道CTF题初探NTRU格密码 - 先知社区 (aliyun.com)（经典且详细，非常受用）

import gmpy2
from Crypto.Util.number import *

N = 19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
g = 101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
n = 90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
c = 51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980

'''sage
g = 101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
N = 19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
v1 = vector(ZZ, [1, g])
v2 = vector(ZZ, [0, N])
m = matrix([v1,v2])
shortest_vector = m.LLL()[0]
print(shortest_vector)
#(-1703096866219569817841710120722024801172129285713276062493657151527831376599274719653327578175460913670322546273486052217558990179451330534956630028900812517189053457400581665150009, -8640002811717397823892474058167788615113205903077061861590520377451867637348771860824972890020165996777729868251869232382053496274304375769436361474547973)
'''
p = 8640002811717397823892474058167788615113205903077061861590520377451867637348771860824972890020165996777729868251869232382053496274304375769436361474547973
assert n%p == 0
q = n//p
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

easySignIn

from Crypto.Util.number import *
import libnum
from random import randint
from secret import flag

p = getPrime(512)
d = getPrime(40)
m = libnum.s2n(flag)
a = randint(2,p)
b = randint(2,p)
c = randint(2,p)
g = d

for i in range(10):
    g = (c*d^2 + b*g + a)%p
    a = (a*b - c) % p
    b = (b*c - a) % p 
    c = (c*a - b) % p 

t = (m+d)^2 %p

print('p=',p)
print('a=',a)
print('b=',b)
print('c=',c)
print('g=',g)
print('t=',t)

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

根据
$$
t = (m+d)^2\quad mod\ p
$$
通过平方剩余可以求出m+d。然后是求d。

观察循环中的代码，很明显可以通过给出的a,b,c推出i=8这一轮的a,b,c，但并不能解出d，因为i=8这一轮的g未知，也就是说有两个未知数。因此我们需要消除掉一个未知数，根据最初的g=d可知，如果我们从最初开始推g的生成式，那么最终就只有未知数d，通过sage解这个方程就可以得到d。

代码如下：

#sage
from Crypto.Util.number import long_to_bytes,inverse

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

R.<x> = PolynomialRing(Zmod(p))
f = x^2 - t
result = f.roots()
print(result)
#[(7591656713055743077369340861541583433090841738590989539280316533529914669358031382351028958377643759269145794938649787861165963022699333466670422633862441, 1), (130661655927230795642760431379039778633673372572819159728043876332994399613135476225358, 1)]

m = 130661655927230795642760431379039778633673372572819159728043876332994399613135476225358

_a = [0 for i in range(10)]
_b = [0 for i in range(10)]
_c = [0 for i in range(10)]

for i in range(10):
    c = (c+b)*inverse(a,p) % p
    b = (b+a)*inverse(c,p) % p
    a = (a+c)*inverse(b,p) % p
    _a[i] = a
    _b[i] = b
    _c[i] = c

_a = _a[::-1]
_b = _b[::-1]
_c = _c[::-1]

R.<x> = PolynomialRing(Zmod(p))
y = x
for i in range(10):
    y = _c[i]*x^2 + _b[i]*y + _a[i]

y = y - g
result = y.roots()
print(result)
for ans in result:
    if ans[0] < 2**40:
        flag = long_to_bytes(m-int(ans[0]))
        print(flag)

easyRSA

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

bitlen = 512
p = getPrime(bitlen)
q = getPrime(bitlen)
r = getPrime(bitlen)

assert p != q and q != r and p != r

n = p*q*r
phi = (p-1)*(q-1)*(r-1)

while 1:
    d = getPrime(256)
    try:
        e = int(gmpy2.invert(d,phi))
    except:
        continue
    if gmpy2.gcd(e,phi) == 1 :
        break

assert flag.startswith(b'CBCTF{')
m = bytes_to_long(flag)
c = pow(m,e,n)
print('c =',c)
print('e =',e)
print('n =',n)

'''
c = 262857004135341325365954795119195630698138090729973647118817900621693212191529885499646534515610526918027363734446577563494752228693708806585707918542489830672358210151020370518277425565514835701391091303404848540885538503732425887366285924392127448359616405690101810030200914619945580943356783421516140571033192987307744023953015589089516394737132984255621681367783910322351237287242642322145388520883300325056201966188529192590458358240120864932085960411656176
e = 543692319895782434793586873362429927694979810701836714789970907812484502410531778466160541800747280593649956771388714635910591027174563094783670038038010184716677689452322851994224499684261265932205144517234930255520680863639225944193081925826378155392210125821339725503707170148367775432197885080200905199759978521133059068268880934032358791127722994561887633750878103807550657534488433148655178897962564751738161286704558463757099712005140968975623690058829135
n = 836627566032090527121140632018409744681773229395209292887236112065366141357802504651617810307617423900626216577416313395633967979093729729146808472187283672097414226162248255028374822667730942095319401316780150886857701380015637144123656111055773881542557503200322153966380830297951374202391216434278247679934469711771381749572937777892991364186158273504206025260342916835148914378411684678800808038832601224951586507845486535271925600310647409016210737881912119
'''

$e$比$n$还大？可能是Wiener's Attack，不过三个素数的$n$用Wiener's Attack我还没见到过。

根据Wiener's Attack，对$\dfrac{e}{N}$进行连分数展开，可以近似得到$k，d*g$。

如果可以得到多个$d*g$，那么可以通过贝祖等式求出公约数$d$。因为是连分数的性质，所以如果存在多个$d*g$，那么这些是连续存在的。

（代码搬过来了）

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(f"q1={q1},q0={q0}")
                    print(r,s)
                    return d
     
        q0 = q1
        
c = 262857004135341325365954795119195630698138090729973647118817900621693212191529885499646534515610526918027363734446577563494752228693708806585707918542489830672358210151020370518277425565514835701391091303404848540885538503732425887366285924392127448359616405690101810030200914619945580943356783421516140571033192987307744023953015589089516394737132984255621681367783910322351237287242642322145388520883300325056201966188529192590458358240120864932085960411656176
e = 543692319895782434793586873362429927694979810701836714789970907812484502410531778466160541800747280593649956771388714635910591027174563094783670038038010184716677689452322851994224499684261265932205144517234930255520680863639225944193081925826378155392210125821339725503707170148367775432197885080200905199759978521133059068268880934032358791127722994561887633750878103807550657534488433148655178897962564751738161286704558463757099712005140968975623690058829135
n = 836627566032090527121140632018409744681773229395209292887236112065366141357802504651617810307617423900626216577416313395633967979093729729146808472187283672097414226162248255028374822667730942095319401316780150886857701380015637144123656111055773881542557503200322153966380830297951374202391216434278247679934469711771381749572937777892991364186158273504206025260342916835148914378411684678800808038832601224951586507845486535271925600310647409016210737881912119

d = plus(e, n)
print(d)
print(long_to_bytes(int(pow(c,d,n))))

---

参考：

DASCTF X CBCTF 2022｜ 九月挑战赛官方Write Up | CTF导航 (ctfiot.com)