20220514-NSSCTF Round#3-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 13k Reading time ≈ 12 mins.

 

Secure_in_N

  • 考点：Unbalanced RSA with small $d_p$

题目如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from random import *

from secret import flag

p,q=getPrime(3152),getPrime(1848)
dp=getrandbits(49)|1
while True:
    d = (p-1)*randint(2**1600, 2**1601)+dp
    if GCD((p-1)*(q-1),d)==1:
        break
e=inverse(d,(p-1)*(q-1))
N=p*q
flag=bytes_to_long(flag)
c=pow(flag,e,N)
print(N)
print(e)
print(c)

"""
N=92284623415374411007644319911187454073302916220773084520687398568204575736103577587622077662739571560529359355177065258271068496365935493382545408516144063063049806652690881915097371144333087433501584087114228239197670807222644484253894764278496478161337997072967206470780221778774219335270911364550670519109964693815345153226555099828531599562623418123027778587314183687211776679323301867186995594357300626738665870121396947849232825876530546411681481549099794727910583034225481370104547602468198477742924117851585832141984400713673175114796407557306652309608022274516285414661511527797352730584005354656905934178717528837570490485144833580575700887974843938370488795782063598650599598276414598962913644318305185912440032914739378304647850986396314690288637870325638420444113019196006062250686047914712810844704797832202140610424829554069863447199793317415249328441428355504453381288543932040699415254084656117994994094339827219674532660717448652812298086526313240605954726572984100184354634936451863017312751058329540442848235825461211675869449259952063923383541897392875472456546527118638872481672653429149496186122384798221245996082487862264927546450734661477178793636908163119192791522533902648887196423095431575895368157982157876690338867418193194636492069189272182607374737756671276086131830691995956955426883182725215494218491302084230163753172002708313243324121178110497082650145504906671087063152911767269295252376104672475682067306166899754414224727211729596122052548449628054795217785054715033
e=8024358580527155334290877801674251879959506867714915253412668990984292235341767665786765488993359337702032275852395386286378942900511396887365780518478129272199554726853491689668741282563473284080650346455657566800004226956434591813749529773142001984587933102828092701230305436992554784864715635534419823255227823372893383270427435341908991564833313542721701123574388105681729962319844498573465225304231839691631988151233095612981147004681192788108110717393989029443598494915790685854734962433893923448360189978667704960829978867287603046024585958164820152075171932859941597691112191381889085909153077670421894121019542714705136554434373635872615948507594280113513171528038575849984396019312585375978684114197168562895181333744517460697443014906160568229295902765416163347299702369222260196155250940336178655660519090403024021887520617234693757199960651828022447343969647099780802273230389300813986084895623073273647754310912967929890941348778909670318887440443037394827110130373286115879434878442245675125910500584829331917016095599667772757926732231845368609048075463496653520745818603544801358877262633800601575926105391617050806604166467070684879462020009998101366355585704601197770758513663948754457374645839019878069074374544090327979180227853597077812774849991992873695730062298491319840110246164247337384996019316033261455760747781231531704714258018620270440727916264334780330695680302082137497778725648378006928146333731092977883476546371441438469936633142681354566485780510065061021388679239651
c=24368905075419807632187757894297346245856502932568423202202856680232483846993836746343145406920076731085948702936414522429672550063992990638111471751460789319352306281240355010664862129897945593355978560363733727108746092951707570814460091660210824135158115720739532997165697058741723987010633953619686414424830298640909976767043025925400612010821217777971650650311370681666765268918324395269648565293302503449380094898552170092866294731002099953696971201871294241449476031823128664048185710157989016372635635951688027341536254852048199708008879380496514315368925618887873373101893352584222049030981354132120633302729938481664860632868846880826219560154228345646418707030438407952209777209464787215474517245682785880252095053848254245109311836587947986430186027701770682151014814737155265507444830458328923154738731223161378747732281936591177393643746506986213705615114015497383336361210830220341072134772388402301883810356620711154954187230978444521027125290106213556230758493325201635251738639753927079761807115232874848700809571259912097052031318265421247753294475383541194848368593506946510747954823508492357240217637907669393374877664529737114047576893606289170127952791165204447504045167072934238020708131880147728232802615404750289313879051803116940401374721453030702995443517986935377578399419695559272897765440203175040557041771095258416863357916004509025912561708780279833666232786876466247451372495478621363554563777506459096140926278815984798230100485933393004878743838955666904065461978076252
"""

$N$的因子不平衡，$d_p$很小

只要能求出$d_p$，根据$ed_p\equiv ed\equiv 1\ (mod\ p-1)$就能求出$p$，即$ed=k(p-1)(q-1)+1$两边同模$p-1$

参考下方Paper，参数满足引理7的条件（$q<N^{\beta},\ d_p\le N^{\delta}$）

image-20220518135941436

关于题目这种情况的攻击，Paper的主要思路是

image-20220518170515187

其中$n$表示格的维度，$m$表示格子中模数$N$的最大次幂

image-20220518140932697

用上面这个结论求出$n$和$m$

1
2
3
4
5
for n in range(100):
    for m in range(100):
        if m * (m + 1) / 2 + (2 * delta + beta) * n * (n - 1) / 2 - (1 - beta) * m * n <= 0 and\
                m == int((1 - beta) * n):
            print(n, m)

这里用了$n=28,\ m=17$

然后按照这个构造格

image-20220518164330895

其中$i$和$j$作为幂指数对应关系如下

image-20220518165105764

这个多项式$f_p$为

image-20220518164701740

重新写一下就是

1
2
3
for i in range(n):
    for j in range(n):
		M[i][j] = x

$x=N^{max(0,m-i)}x^j\times(ex-y)^i$展开式的第$j$项

到此就得到了Paper的格了

用LLL算出最短向量后，构造多项式（Paper里有构造的方案，但我没找到），并分解，找到$ax+by$项，其中$k=a,d_p=b$

image-20220518201035605

偷来的exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
N = 92284623415374411007644319911187454073302916220773084520687398568204575736103577587622077662739571560529359355177065258271068496365935493382545408516144063063049806652690881915097371144333087433501584087114228239197670807222644484253894764278496478161337997072967206470780221778774219335270911364550670519109964693815345153226555099828531599562623418123027778587314183687211776679323301867186995594357300626738665870121396947849232825876530546411681481549099794727910583034225481370104547602468198477742924117851585832141984400713673175114796407557306652309608022274516285414661511527797352730584005354656905934178717528837570490485144833580575700887974843938370488795782063598650599598276414598962913644318305185912440032914739378304647850986396314690288637870325638420444113019196006062250686047914712810844704797832202140610424829554069863447199793317415249328441428355504453381288543932040699415254084656117994994094339827219674532660717448652812298086526313240605954726572984100184354634936451863017312751058329540442848235825461211675869449259952063923383541897392875472456546527118638872481672653429149496186122384798221245996082487862264927546450734661477178793636908163119192791522533902648887196423095431575895368157982157876690338867418193194636492069189272182607374737756671276086131830691995956955426883182725215494218491302084230163753172002708313243324121178110497082650145504906671087063152911767269295252376104672475682067306166899754414224727211729596122052548449628054795217785054715033
e = 8024358580527155334290877801674251879959506867714915253412668990984292235341767665786765488993359337702032275852395386286378942900511396887365780518478129272199554726853491689668741282563473284080650346455657566800004226956434591813749529773142001984587933102828092701230305436992554784864715635534419823255227823372893383270427435341908991564833313542721701123574388105681729962319844498573465225304231839691631988151233095612981147004681192788108110717393989029443598494915790685854734962433893923448360189978667704960829978867287603046024585958164820152075171932859941597691112191381889085909153077670421894121019542714705136554434373635872615948507594280113513171528038575849984396019312585375978684114197168562895181333744517460697443014906160568229295902765416163347299702369222260196155250940336178655660519090403024021887520617234693757199960651828022447343969647099780802273230389300813986084895623073273647754310912967929890941348778909670318887440443037394827110130373286115879434878442245675125910500584829331917016095599667772757926732231845368609048075463496653520745818603544801358877262633800601575926105391617050806604166467070684879462020009998101366355585704601197770758513663948754457374645839019878069074374544090327979180227853597077812774849991992873695730062298491319840110246164247337384996019316033261455760747781231531704714258018620270440727916264334780330695680302082137497778725648378006928146333731092977883476546371441438469936633142681354566485780510065061021388679239651
c = 24368905075419807632187757894297346245856502932568423202202856680232483846993836746343145406920076731085948702936414522429672550063992990638111471751460789319352306281240355010664862129897945593355978560363733727108746092951707570814460091660210824135158115720739532997165697058741723987010633953619686414424830298640909976767043025925400612010821217777971650650311370681666765268918324395269648565293302503449380094898552170092866294731002099953696971201871294241449476031823128664048185710157989016372635635951688027341536254852048199708008879380496514315368925618887873373101893352584222049030981354132120633302729938481664860632868846880826219560154228345646418707030438407952209777209464787215474517245682785880252095053848254245109311836587947986430186027701770682151014814737155265507444830458328923154738731223161378747732281936591177393643746506986213705615114015497383336361210830220341072134772388402301883810356620711154954187230978444521027125290106213556230758493325201635251738639753927079761807115232874848700809571259912097052031318265421247753294475383541194848368593506946510747954823508492357240217637907669393374877664529737114047576893606289170127952791165204447504045167072934238020708131880147728232802615404750289313879051803116940401374721453030702995443517986935377578399419695559272897765440203175040557041771095258416863357916004509025912561708780279833666232786876466247451372495478621363554563777506459096140926278815984798230100485933393004878743838955666904065461978076252

q_bits = 1848
dp_bits = 64
beta = q_bits/N.bit_length()
# assert q < N ^ beta
# delta = 0.01
delta = dp_bits/N.bit_length()

# for n in range(100):
#     for m in range(100):
#         if m * (m + 1) / 2 + (2 * delta + beta) * n * (n - 1) / 2 - (1 - beta) * m * n <= 0 and\
#                 m == int((1 - beta) * n):
#             print(n, m)
# 0 0
# 1 0
# 28 17
# 29 18
# 30 18

# yanghui triangle
def getC(Scale):
    C=[[0 for __ in range(Scale)] for _ in range(Scale)]
    for i in range(Scale):
        for j in range(Scale):
            if i==j or j==0:
                C[i][j]=1
            else:
                C[i][j]=C[i-1][j-1]+C[i-1][j]
    return C


def getMatrix(Scale,Mvalue,N,E,Del,Bet):
    M=[[0 for __ in range(Scale)] for _ in range(Scale)]
    C=getC(Scale)
    X,Y=int(pow(N,Del)*(Scale+1)/2),int(pow(N,(Del+Bet))*(Scale+1)/2)
    for i in range(Scale):
        for j in range(Scale):
            M[i][j]=N**max(Mvalue-i,0)*E**(max(i-j,0))*X**(Scale-1-j)*Y**j*C[i][j]*(-1)**j
    return M


delta=0.01
beta=0.37
Scale=28
Mvalue=17
M=getMatrix(Scale,Mvalue,N,e,delta,beta)
M=matrix(ZZ,M)
A=M.LLL()[0]

p = []
X = int(pow(N,delta)*(Scale+1)/2)
Y = int(pow(N,(delta+beta))*(Scale+1)/2)
for i in range(Scale):
    p.append(A[i]//(X**(Scale-1-i)*Y**i))
PR.<x,y>=PolynomialRing(ZZ)
f=0
for i in range(Scale):
    f+=p[i]*x^(Scale-1-i)*y^i
#f=p[0]*x^4+p[1]*x^3*y+p[2]*x^2*y^2+p[3]*x*y^3+p[4]*y^4
print(f.factor())
# extract from the factorization
# 250292684853109062422762009014838507801551186915547622107878320666544145201717444945784117574013634648728418170888678372382969831884303023315772302709090507191757138602583610493148685517900050634640052359194739453651365670210389175816456648757912801502148161310253045805242385579273328097132325492951208346192211822359196413689211194817256850128186995353937605375764130172330297712002569983583733402837208773205105656440965472507453570535761283587220457272091647022578072425029498450582587734914013823649569433668969336501513097537762722144022089485388366353557603284514
# *x + 194454984906921*y
dp = 194454984906921
k = 250292684853109062422762009014838507801551186915547622107878320666544145201717444945784117574013634648728418170888678372382969831884303023315772302709090507191757138602583610493148685517900050634640052359194739453651365670210389175816456648757912801502148161310253045805242385579273328097132325492951208346192211822359196413689211194817256850128186995353937605375764130172330297712002569983583733402837208773205105656440965472507453570535761283587220457272091647022578072425029498450582587734914013823649569433668969336501513097537762722144022089485388366353557603284514
p = (e * dp - 1) // (k + 1) + 1
q = N // p
assert p * q == N
print(bytes.fromhex(hex(pow(c, pow(e, -1, N-p-q+1), N))[2:]))
# b'NSSCTF{4522da80-15f9-4922-9010-9abd6d3f7241}'

最后这里不知道Paper这个2是不是写错了，如果是1那说得过去

image-20220518195348041

BTW，这篇Paper只给到$p<N^{0.382}$，其他还有给到$p<N^{0.468}$的

image-20220518192054791

Reference

  1. https://lordriot.live/2021/01/06/Way-to-CopperSmith/
  2. Cryptanalysis of Unbalanced RSA with Small CRT-Exponent
  3. 官方wp