Unbalanced RSA with Small CRT-Exponent

small dp的问题在ctf的赛题中出了几次了，而且也确实是个值得深入研究的问题，觉得还是有必要详细记录一下

Question

对于N=pq，，，，N，e已知，尝试分解N(θ较小)

首先这个问题其实在实际上的加密算法中均有应用，由于RSA的解密需要的复杂度，在N，d很大时解密的消耗是较大的，为了降低解密消耗就有了dp，dq的出现，但是其大小控制仍然是需要商榷的，question即为对其中dp较小情况下的一种攻击方式

最早期May提供的启发式算法能解决时的情况

论文中有提到两种不同的构造方案

An Approach Modulo e

由已知有

模e可得

记含有根

构造

其中m为shift位数(即需要找的解所在域)

An Approach Modulo p

记含有根

构造

为方便格的构造我们取j=n-1-i，对这种方式的大小进行一下估计

为了使最终规约后的系数满足howgrave约束需要有

论文中有提到时是一个较优的取值

最终给出结论只需系数满足即可利用上述方式求解

Comparison of the Methods

只能说两种方案各有优势，但是从图上数据来看，模p的方案在实际应用中是更加有效的，在更进一步的优化下β能达到0.382的效果，在最新的论文里已经能优化到0.468，但其采用的是第一种想法，这个程度的β已经很接近正常rsa公钥的取值了，但是时间开销对于较大的N还是过大，但是对于1024bits的N还是具有不错的效果

总的来说也就是模p的情况适用于β较大θ较小的情况，而模e适用于β和θ较为平均的情况

Example

1.Strange_CRT

21年mr的一道题，简单地进行一下实验，稍微修改了一下原题的系数

from Crypto.Util.number import *
m=b'Unbalanced RSA with Small CRT-Exponent'
nbits=2048
beta=0.330
delta=0.03
p=getPrime(int(nbits*(1-beta)))
q=getPrime(int(nbits*beta))
n=p*q
dp=getRandomInteger(int(nbits*delta))|1
phi=(p-1)*(q-1)
while True:
    d=(p-1)*getRandomInteger(int(1024*beta-40))+dp
    if GCD(d,phi)==1:
        break

e=inverse(d,phi)
m=bytes_to_long(m)
c=pow(m,e,n)
print('e=',e)
print('N=',n)
print('c=',c)
'''
e= 7416229890364012096238738128277321301908842037351918926321669172812949802970954320807051730418429640930294163194178722409412050396900823825176971085953727729972188588741350220965748255471642119854209098682490581574621930301283606567360162839806265935540833630905902641341470793620440769987234366602545942796435229968444073251908843752603301579408254898919643221680719248752583171594268904067361138241600198855519961139751211416248924734817620731364316215891131479082190491193603603945078681058641276135261422530384401040331992745170946846542893368433128335474640997451603271123266496509538320810962993580794342130613
N= 8221635024713054585304053539021905136743205412187291398885312502399146054201409559822858046345415108219532665593701220184175280226302483758204213943938619030311190539750692907088281851435337042403928414387445811611057535114894557687354207543271029179468281847184642639824707923783483687056843044358418219098480533592879954565812937773603277605901559304277542919322287339549794597102400876949557186130060858645071617461414535802227114649852327725102536671000824327009691209080753758211062334549803396217773495637438719737932782711473526185314327429706123721184018526164843912357084299581282557834163087608711523332347
c= 5828665400659662200481257930448613556912466910028956416895009188678100386909653995901581798487196584505517205949477328949345164785085371759915602140665709476035759574131593907109076145868032864371280370522203844144419776437591517664380473995578020314238965796218842644269796377723374581784493311777190447527242501253991041432494385703487691181794563818370500886751504929179220588826849420285343147821037482564796404164142663325747444406331049194310027524244880507475966635549298077469138065853223611959428410417167179003219721139011717726446618184075004185716283850052481127065919476796414949852415947884586083184078
'''

采取第二种格构造

import gmpy2
e= 7416229890364012096238738128277321301908842037351918926321669172812949802970954320807051730418429640930294163194178722409412050396900823825176971085953727729972188588741350220965748255471642119854209098682490581574621930301283606567360162839806265935540833630905902641341470793620440769987234366602545942796435229968444073251908843752603301579408254898919643221680719248752583171594268904067361138241600198855519961139751211416248924734817620731364316215891131479082190491193603603945078681058641276135261422530384401040331992745170946846542893368433128335474640997451603271123266496509538320810962993580794342130613
N= 8221635024713054585304053539021905136743205412187291398885312502399146054201409559822858046345415108219532665593701220184175280226302483758204213943938619030311190539750692907088281851435337042403928414387445811611057535114894557687354207543271029179468281847184642639824707923783483687056843044358418219098480533592879954565812937773603277605901559304277542919322287339549794597102400876949557186130060858645071617461414535802227114649852327725102536671000824327009691209080753758211062334549803396217773495637438719737932782711473526185314327429706123721184018526164843912357084299581282557834163087608711523332347
c= 5828665400659662200481257930448613556912466910028956416895009188678100386909653995901581798487196584505517205949477328949345164785085371759915602140665709476035759574131593907109076145868032864371280370522203844144419776437591517664380473995578020314238965796218842644269796377723374581784493311777190447527242501253991041432494385703487691181794563818370500886751504929179220588826849420285343147821037482564796404164142663325747444406331049194310027524244880507475966635549298077469138065853223611959428410417167179003219721139011717726446618184075004185716283850052481127065919476796414949852415947884586083184078
beta=0.33
delta=0.03
X=int(pow(N,delta))
Y=int(pow(N,delta+beta))
L=[]
L.append([N^2*X^3,0,0,0])
L.append([N*e*X^3,-N*X^2*Y,0,0])
L.append([e^2*X^3,-2*e*X^2*Y,X*Y^2,0])
L.append([e^3*X^3,-3*e^2*X^2*Y,3*e*X*Y^2,-Y^3])
L=Matrix(ZZ,L)
L=L.LLL()[0]
coeff=[]
coeff.append(L[0]//X^3)
coeff.append(L[1]//(X^2*Y))
coeff.append(L[2]//(X*Y^2))
coeff.append(L[3]//Y^3)
Z.<x,y>=ZZ[]
f=x^3*coeff[0]+x^2*y*coeff[1]+x*y^2*coeff[2]+y^3*coeff[3]
print(f.factor())
k=122758960842955082490723707195925090944931549808439871677978126142734379357232922577358494346844311129023301388856174022612131514572616596105520320029003691525127390354450939979945892746499060657659903732377453304871599184
dp=1558903319255880605
p=(e*dp-1)//k+1
q=N//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,N)
print(bytes.fromhex(hex(m)[2:]))

2.secure_in_N

对于选取系数的不同所取格的维数也不一样，这里拿NSSround3的一道题作为例子

这道题的beta相比上文所举的例子较高并且较接近may提出的算法相应β的界限

这里我们需要采取更高维度的格进行规约，令，系数选取需要利用上文提到的两个不等式约束

beta=0.3696
delta=0.01
n=round((1-2*beta-2*delta)/((1-beta)^2-2*delta-beta),6)
print(n)
#30.855339

于是我们考虑构造31维的格

由于维数较高写了个自动化一点的脚本，不然求系数过于麻烦

N=92284623415374411007644319911187454073302916220773084520687398568204575736103577587622077662739571560529359355177065258271068496365935493382545408516144063063049806652690881915097371144333087433501584087114228239197670807222644484253894764278496478161337997072967206470780221778774219335270911364550670519109964693815345153226555099828531599562623418123027778587314183687211776679323301867186995594357300626738665870121396947849232825876530546411681481549099794727910583034225481370104547602468198477742924117851585832141984400713673175114796407557306652309608022274516285414661511527797352730584005354656905934178717528837570490485144833580575700887974843938370488795782063598650599598276414598962913644318305185912440032914739378304647850986396314690288637870325638420444113019196006062250686047914712810844704797832202140610424829554069863447199793317415249328441428355504453381288543932040699415254084656117994994094339827219674532660717448652812298086526313240605954726572984100184354634936451863017312751058329540442848235825461211675869449259952063923383541897392875472456546527118638872481672653429149496186122384798221245996082487862264927546450734661477178793636908163119192791522533902648887196423095431575895368157982157876690338867418193194636492069189272182607374737756671276086131830691995956955426883182725215494218491302084230163753172002708313243324121178110497082650145504906671087063152911767269295252376104672475682067306166899754414224727211729596122052548449628054795217785054715033
e=8024358580527155334290877801674251879959506867714915253412668990984292235341767665786765488993359337702032275852395386286378942900511396887365780518478129272199554726853491689668741282563473284080650346455657566800004226956434591813749529773142001984587933102828092701230305436992554784864715635534419823255227823372893383270427435341908991564833313542721701123574388105681729962319844498573465225304231839691631988151233095612981147004681192788108110717393989029443598494915790685854734962433893923448360189978667704960829978867287603046024585958164820152075171932859941597691112191381889085909153077670421894121019542714705136554434373635872615948507594280113513171528038575849984396019312585375978684114197168562895181333744517460697443014906160568229295902765416163347299702369222260196155250940336178655660519090403024021887520617234693757199960651828022447343969647099780802273230389300813986084895623073273647754310912967929890941348778909670318887440443037394827110130373286115879434878442245675125910500584829331917016095599667772757926732231845368609048075463496653520745818603544801358877262633800601575926105391617050806604166467070684879462020009998101366355585704601197770758513663948754457374645839019878069074374544090327979180227853597077812774849991992873695730062298491319840110246164247337384996019316033261455760747781231531704714258018620270440727916264334780330695680302082137497778725648378006928146333731092977883476546371441438469936633142681354566485780510065061021388679239651
c= 5828665400659662200481257930448613556912466910028956416895009188678100386909653995901581798487196584505517205949477328949345164785085371759915602140665709476035759574131593907109076145868032864371280370522203844144419776437591517664380473995578020314238965796218842644269796377723374581784493311777190447527242501253991041432494385703487691181794563818370500886751504929179220588826849420285343147821037482564796404164142663325747444406331049194310027524244880507475966635549298077469138065853223611959428410417167179003219721139011717726446618184075004185716283850052481127065919476796414949852415947884586083184078

beta=0.3696
delta=0.01
n=31
m=int(n*(1-beta))
X=int(pow(N,delta))
Y=int(pow(N,delta+beta))
Z.<x,y>=ZZ[]
L=Matrix(ZZ,n,n)
f=e*x-y
for i in range(n):
    g=list(N^max(0,m-i)*x^(n-1-i)*f^i)
    for j in range(len(g)):
        L[i,j]=g[j][0]*X^(n-1-j)*Y^j
L=L.LLL()[0]
coeff=[]
for i in range(n):
    coeff.append((L[i]//(X^(n-1-i)*Y^i),'x'+'**'+str(n-1-i)+'*y'+'**'+str(i)))
s=''
for i in range(len(coeff)):
    s+=str(coeff[i][0])+'*'+coeff[i][1]+'+'

f=eval(s[:-1])
f.factor()

LLL需要跑一段时间大概一二十分钟，最后分解f得到k-1以及dp的取值

import gmpy2
N=92284623415374411007644319911187454073302916220773084520687398568204575736103577587622077662739571560529359355177065258271068496365935493382545408516144063063049806652690881915097371144333087433501584087114228239197670807222644484253894764278496478161337997072967206470780221778774219335270911364550670519109964693815345153226555099828531599562623418123027778587314183687211776679323301867186995594357300626738665870121396947849232825876530546411681481549099794727910583034225481370104547602468198477742924117851585832141984400713673175114796407557306652309608022274516285414661511527797352730584005354656905934178717528837570490485144833580575700887974843938370488795782063598650599598276414598962913644318305185912440032914739378304647850986396314690288637870325638420444113019196006062250686047914712810844704797832202140610424829554069863447199793317415249328441428355504453381288543932040699415254084656117994994094339827219674532660717448652812298086526313240605954726572984100184354634936451863017312751058329540442848235825461211675869449259952063923383541897392875472456546527118638872481672653429149496186122384798221245996082487862264927546450734661477178793636908163119192791522533902648887196423095431575895368157982157876690338867418193194636492069189272182607374737756671276086131830691995956955426883182725215494218491302084230163753172002708313243324121178110497082650145504906671087063152911767269295252376104672475682067306166899754414224727211729596122052548449628054795217785054715033
e=8024358580527155334290877801674251879959506867714915253412668990984292235341767665786765488993359337702032275852395386286378942900511396887365780518478129272199554726853491689668741282563473284080650346455657566800004226956434591813749529773142001984587933102828092701230305436992554784864715635534419823255227823372893383270427435341908991564833313542721701123574388105681729962319844498573465225304231839691631988151233095612981147004681192788108110717393989029443598494915790685854734962433893923448360189978667704960829978867287603046024585958164820152075171932859941597691112191381889085909153077670421894121019542714705136554434373635872615948507594280113513171528038575849984396019312585375978684114197168562895181333744517460697443014906160568229295902765416163347299702369222260196155250940336178655660519090403024021887520617234693757199960651828022447343969647099780802273230389300813986084895623073273647754310912967929890941348778909670318887440443037394827110130373286115879434878442245675125910500584829331917016095599667772757926732231845368609048075463496653520745818603544801358877262633800601575926105391617050806604166467070684879462020009998101366355585704601197770758513663948754457374645839019878069074374544090327979180227853597077812774849991992873695730062298491319840110246164247337384996019316033261455760747781231531704714258018620270440727916264334780330695680302082137497778725648378006928146333731092977883476546371441438469936633142681354566485780510065061021388679239651
c= 5828665400659662200481257930448613556912466910028956416895009188678100386909653995901581798487196584505517205949477328949345164785085371759915602140665709476035759574131593907109076145868032864371280370522203844144419776437591517664380473995578020314238965796218842644269796377723374581784493311777190447527242501253991041432494385703487691181794563818370500886751504929179220588826849420285343147821037482564796404164142663325747444406331049194310027524244880507475966635549298077469138065853223611959428410417167179003219721139011717726446618184075004185716283850052481127065919476796414949852415947884586083184078

k=250292684853109062422762009014838507801551186915547622107878320666544145201717444945784117574013634648728418170888678372382969831884303023315772302709090507191757138602583610493148685517900050634640052359194739453651365670210389175816456648757912801502148161310253045805242385579273328097132325492951208346192211822359196413689211194817256850128186995353937605375764130172330297712002569983583733402837208773205105656440965472507453570535761283587220457272091647022578072425029498450582587734914013823649569433668969336501513097537762722144022089485388366353557603284515
dp=194454984906921
p=(e*dp-1)//k+1
q=N//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,N)
print(bytes.fromhex(hex(m)[2:]))

3.hard_RSA

附件

之前tqlctf的一道题，计算系数间的关系会发现给的参数不满足模p方案的约束，而且看那张对比的图可以看出相对于模p，模e更适合这种β和θ均不算太大的情况

可是不是很明白最后那个m和t的取值是怎么回事，而且给的系数也没有满足paper中的不等式，比较懵，等以后复现吧(．． )…

更进一步的优化可以看看paper1，里面提供了一种额外增加系数z的方案，所达到的系数已经较为接近正常的rsa取值，最后也有测试的相关结果，但是在n取值较大时似乎不是很可观