[NSSCTF 2022 Spring Recruit]rrrsssaaa

1.题目

from Crypto.Util.number import *
import gmpy2
from functools import reduce
from secret import flagp = getPrime(1024)
i = 0
while True:r = p * 5 + iif isPrime(r):i = 0breakelse:i += 1
while True:q = p * 10 + iif isPrime(q):breakelse:i += 1n = p * q * r
e = 65537
c = pow(bytes_to_long(flag.encode()), e, n)
print('c=' + str(c))
print('p3=' + str(pow(p, 3, n)))
print('q3=' + str(pow(q, 3, n)))
print('r3=' + str(pow(r, 3, n)))
# n = 44571911854174527304485400947383944661319242813524818888269963870884859557542264803774212076803157466539443358890313286282067621989609252352994203884813364011659788234277369629312571477760818634118449563652776213438461157699447304292906151410018017960605868035069246651843561595572415595568705784173761441087845248621463389786351743200696279604003824362262237505386409700329605140703782099240992158439201646344692107831931849079888757310523663310273856448713786678014221779214444879454790399990056124051739535141631564534546955444505648933134838799753362350266884682987713823886338789502396879543498267617432600351655901149380496067582237899323865338094444822339890783781705936546257971766978222763417870606459677496796373799679580683317833001077683871698246143179166277232084089913202832193540581401453311842960318036078745448783370048914350299341586452159634173821890439194014264891549345881324015485910286021846721593668473
# c = 11212699652154912414419576042130573737460880175860430868241856564678915039929479534373946033032215673944727767507831028500814261134142245577246925294110977629353584372842303558820509861245550773062016272543030477733653059813274587939179134498599049035104941393508776333632172797303569396612594631646093552388772109708942113683783815011735472088985078464550997064595366458370527490791625688389950370254858619018250060982532954113416688720602160768503752410505420577683484807166966007396618297253478916176712265476128018816694458551219452105277131141962052020824990732525958682439071443399050470856132519918853636638476540689226313542250551212688215822543717035669764276377536087788514506366740244284790716170847347643593400673746020474777085815046098314460862593936684624708574116108322520985637474375038848494466480630236867228454838428542365166285156741433845949358227546683144341695680712263215773807461091898003011630162481
# p3 = 891438237083490546089708018947678893226384856270496377765399277417697191150845296075484241536063149330788867177806265725641352439792185047059884077696267280233195764685547392586251429555216372682368991273055524268769223153988946085858123028200360359212117360701384933036871231911448311911374115683475228820531478240539549424647154342506853356292956506486091063660095505979187297020928573605860329881982122478494944846700224611808246427660214535971723459345029873385956677292979041143593821672034573140001092625650099257402018634684516092489263998517027205660003413512870074652126328536906790020794659204007921147300771594986038917179253827432120018857213350120695302091483756021206199805521083496979628811676116525321724267588515105188480380865374667274442027086789352802613365511142499668793725505110436809024171752137883546327359935102833441492430652019931999144063825010678766130335038975376834579129516127516820037383067
# q3 = 44571911854174527304485400947383944661319242813524818888269963870884859557542264803774212076803157466539443358890313286282067621989609252352994203884813364011659788234277369629312571477760818634118449563652776213438461157699447304292906151410018017960605868035069246651843561595572415595568705784173761440671033435053531971051698504592848580356684103015611323747688216493729331061402058160819388999663041629882482138465124920580049057123360829897432472221079140360215664537272316836767039948368780837985855835419681893347839311156887660438769948501100287062738217966360434291369179859862550767272985972263442512061098317471708987686120577904202391381040801620069987103931326500146536990700234262413595295698193570184681785854277656410199477649697026112650581343325348837547631237627207304757407395388155701341044939408589591213693329516396531103489233367665983149963665364824119870832353269655933102900004362236232825539480774
# r3 = 22285955927087263652242700473691972330659621406762409444134981935442429778771132401887106038401578733269721679445156643141033810994804626176497101942406682005829894117138684814656285738880409317059224781826388106719230578849723652146453075705009008980302934017534623325921780797786207797784352892086880720749202442492937918619992591614713131681306874944356693778359565004415437554407990089293135634916859631279984463829118336826115430997439527110961309956466956650522900331263720500751112297418506140413317489683875995326726992533904683800042127871963320754241310699432792081707870167598822650064976439270556418985242630368723264289700246406905189810458354474959276748887369363592834205660349184660073395182450526542246354364903399132116153732074081050985584216815493617906868615192465631416955706457835185743023758573279838341229835613609332206338401219168119635681832981552328638132500079074010106995297184587143613134093145

2.思路

本题主要还是考察低指数加密攻击算法

（转低指数加密攻击（低指数广播攻击）_低加密指数分解脚本-CSDN博客）

我们观察p,q,r的取值

 r = 5*p + i，其中 i从0开始递增，直到 r为素数

q = 10*p + i，其中 i从当前值开始递增，直到 q为素数

n=pqr

那么由p3=pow(p,3,n),p^3明显是小于n的,那么根据小明文攻击， p=(p3)^3

后面就是求r和q了，r要么直接r = sympy.nextprime(p * 5)根据题目意思来求，要么还是利用低指数加密脚本，r^3明显是小于n的,那么根据小明文攻击,直接套脚本了

剩下的自然就迎刃而解了

3.脚本

求p

c = 11212699652154912414419576042130573737460880175860430868241856564678915039929479534373946033032215673944727767507831028500814261134142245577246925294110977629353584372842303558820509861245550773062016272543030477733653059813274587939179134498599049035104941393508776333632172797303569396612594631646093552388772109708942113683783815011735472088985078464550997064595366458370527490791625688389950370254858619018250060982532954113416688720602160768503752410505420577683484807166966007396618297253478916176712265476128018816694458551219452105277131141962052020824990732525958682439071443399050470856132519918853636638476540689226313542250551212688215822543717035669764276377536087788514506366740244284790716170847347643593400673746020474777085815046098314460862593936684624708574116108322520985637474375038848494466480630236867228454838428542365166285156741433845949358227546683144341695680712263215773807461091898003011630162481
e1 = 3
p3 = 891438237083490546089708018947678893226384856270496377765399277417697191150845296075484241536063149330788867177806265725641352439792185047059884077696267280233195764685547392586251429555216372682368991273055524268769223153988946085858123028200360359212117360701384933036871231911448311911374115683475228820531478240539549424647154342506853356292956506486091063660095505979187297020928573605860329881982122478494944846700224611808246427660214535971723459345029873385956677292979041143593821672034573140001092625650099257402018634684516092489263998517027205660003413512870074652126328536906790020794659204007921147300771594986038917179253827432120018857213350120695302091483756021206199805521083496979628811676116525321724267588515105188480380865374667274442027086789352802613365511142499668793725505110436809024171752137883546327359935102833441492430652019931999144063825010678766130335038975376834579129516127516820037383067
import gmpy2
from Crypto.Util.number import *
p=gmpy2.iroot(p3,3)[0]
print(p)
#p=96241803526087516516438618680574139229212699224895199026126947479609515703069904259770933066463243844738712136916991719874179296797623802919752542053959297743706931240798992583332970879091497936378700193716012227086531507335444090574605921869576355704757589370608232721639204280020820678250787751406162350723

求r

import gmpy2
import libnumdef decrypt_low_exponent(c, e, n, max_k=1000):for k in range(max_k + 1):possible_m_cubed = c + n * km, is_exact_root = gmpy2.iroot(possible_m_cubed, e)if is_exact_root:return mraise ValueError("解密失败，可能 m^e >= n 或 e 不适用")# 题目给定的参数
n = 44571911854174527304485400947383944661319242813524818888269963870884859557542264803774212076803157466539443358890313286282067621989609252352994203884813364011659788234277369629312571477760818634118449563652776213438461157699447304292906151410018017960605868035069246651843561595572415595568705784173761441087845248621463389786351743200696279604003824362262237505386409700329605140703782099240992158439201646344692107831931849079888757310523663310273856448713786678014221779214444879454790399990056124051739535141631564534546955444505648933134838799753362350266884682987713823886338789502396879543498267617432600351655901149380496067582237899323865338094444822339890783781705936546257971766978222763417870606459677496796373799679580683317833001077683871698246143179166277232084089913202832193540581401453311842960318036078745448783370048914350299341586452159634173821890439194014264891549345881324015485910286021846721593668473
e = 3
c = 22285955927087263652242700473691972330659621406762409444134981935442429778771132401887106038401578733269721679445156643141033810994804626176497101942406682005829894117138684814656285738880409317059224781826388106719230578849723652146453075705009008980302934017534623325921780797786207797784352892086880720749202442492937918619992591614713131681306874944356693778359565004415437554407990089293135634916859631279984463829118336826115430997439527110961309956466956650522900331263720500751112297418506140413317489683875995326726992533904683800042127871963320754241310699432792081707870167598822650064976439270556418985242630368723264289700246406905189810458354474959276748887369363592834205660349184660073395182450526542246354364903399132116153732074081050985584216815493617906868615192465631416955706457835185743023758573279838341229835613609332206338401219168119635681832981552328638132500079074010106995297184587143613134093145
r = decrypt_low_exponent(c, e, n)
print("解密后的整数 r =", r)
#r=481209017630437582582193093402870696146063496124475995130634737398047578515349521298854665332316219223693560684584958599370896483988119014598762710269796488718534656203994962916664854395457489681893500968580061135432657536677220452873029609347881778523787946853041163608196021400104103391253938757030811754131

求flag

from Crypto.Util.number import *
import gmpy2
import sympy
p = 96241803526087516516438618680574139229212699224895199026126947479609515703069904259770933066463243844738712136916991719874179296797623802919752542053959297743706931240798992583332970879091497936378700193716012227086531507335444090574605921869576355704757589370608232721639204280020820678250787751406162350723
n = 44571911854174527304485400947383944661319242813524818888269963870884859557542264803774212076803157466539443358890313286282067621989609252352994203884813364011659788234277369629312571477760818634118449563652776213438461157699447304292906151410018017960605868035069246651843561595572415595568705784173761441087845248621463389786351743200696279604003824362262237505386409700329605140703782099240992158439201646344692107831931849079888757310523663310273856448713786678014221779214444879454790399990056124051739535141631564534546955444505648933134838799753362350266884682987713823886338789502396879543498267617432600351655901149380496067582237899323865338094444822339890783781705936546257971766978222763417870606459677496796373799679580683317833001077683871698246143179166277232084089913202832193540581401453311842960318036078745448783370048914350299341586452159634173821890439194014264891549345881324015485910286021846721593668473
r =481209017630437582582193093402870696146063496124475995130634737398047578515349521298854665332316219223693560684584958599370896483988119014598762710269796488718534656203994962916664854395457489681893500968580061135432657536677220452873029609347881778523787946853041163608196021400104103391253938757030811754131
c = 11212699652154912414419576042130573737460880175860430868241856564678915039929479534373946033032215673944727767507831028500814261134142245577246925294110977629353584372842303558820509861245550773062016272543030477733653059813274587939179134498599049035104941393508776333632172797303569396612594631646093552388772109708942113683783815011735472088985078464550997064595366458370527490791625688389950370254858619018250060982532954113416688720602160768503752410505420577683484807166966007396618297253478916176712265476128018816694458551219452105277131141962052020824990732525958682439071443399050470856132519918853636638476540689226313542250551212688215822543717035669764276377536087788514506366740244284790716170847347643593400673746020474777085815046098314460862593936684624708574116108322520985637474375038848494466480630236867228454838428542365166285156741433845949358227546683144341695680712263215773807461091898003011630162481
q = n // (p * r)
print(q)
print(r)
#
e=65537
phi=(p-1)*(q-1)*(r-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
flag=long_to_bytes(m)
print(flag)
#b'NSSCTF{cc10786a-cc59-a07d-5c9f-df1c55b18cd4}'

追求效率肯定就直接根据题目求p,q,r了，后面步骤一致

# 计算 p3 的立方根得到 p
p, _ = gmpy2.iroot(p3, 3)
# 找到比 p * 5 大的下一个素数 r
r = sympy.nextprime(p * 5)
# 找到比 p * 10 大的下一个素数 q
q = sympy.nextprime(p * 10)