一、题目：DangerousRSA
题目代码
#n: 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e: 0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?
由c=pow（M,3,n）,c=M3%n,当M3<n时，M的c开3次方，当M3>n时，设M3%n的商为k，余数为c，M等于c+kn开3次方。循环爆破k即可
import gmpy2
from Crypto.Util.number import *
n = 47966708183289639962501363163761864399454241691014467172805658518368423135168025285144721028476297179341434450931955275325060173656301959484440112740411109153032840150659
c = 10968126341413081941567552025256642365567988931403833266852196599058668508079150528128483441934584299102782386592369069626088211004467782012298322278772376088171342152839
k = 0
while 1:
m = gmpy2.iroot(c + k*n,3)
print(m)
if (m[1] == True):
M = m[0]
print(M)
print(long_to_bytes(M))
break
k = k+1
二、题目：EasyRSA
题目代码
from Crypto.Util.number import *
from gmpy2 import *
from secret import *
assert(flag.startwith('flag{')) and (flag.endwith('}'))
assert(is_prime(beta) and len(bin(beta)[2:]) == 512)
assert(len(bin(x)[2:]) == len(bin(y)[2:]))
# This is tip!!!
assert(tip == 2*x*y*beta + x + y)
p = 2*x*beta + 1
q = 2*y*beta + 1
assert(is_prime(p) and is_prime(q))
n = p*q
e = 65537
m = bytes_to_long(flag)
enc = powmod(m,e,n)
#n = 17986052241518124152579698727005505088573670763293762110375836247355612011054569717338676781772224186355540833136105641118789391002684013237464006860953174190278718294774874590936823847040556879723368745745863499521381501281961534965719063185861101706333863256855553691578381034302217163536137697146370869852180388385732050177505306982196493799420954022912860262710497234529008765582379823928557307038782793649826879316617865012433973899266322533955187594070215597700782682186705964842947435512183808651329554499897644733096933800570431036589775974437965028894251544530715336418443795864241340792616415926241778326529055663
#beta = 11864389277042761216996641604675717452843530574016671576684180662096506094587545173005905433938758559675517932481818900399893444422743930613073261450555599
#e = 65537
#enc = 10760807485718247466823893305767047250503197383143218026814141719093776781403513881079114556890534223832352132446445237573389249010880862460738448945011264928270648357652595432015646424427464523486856294998582949173459779764873664665361437483861277508734208729366952221351049574873831620714889674755106545281174797387906705765430764314845841490492038801926675266705606453163826755694482549401843247482172026764635778484644547733877083368527255145572732954216461334217963127783632702980064435718785556011795841651015143521512315148320334442235923393757396733821710592667519724592789856065414299022191871582955584644441117223
分析：题目给了n、e、c和一个beta以及p、q和beta关系的式子和一个tip：assert(tip == 2xybeta + x + y)，毫无疑问我们的目标就是通过这两个和p、q相关的式子求出p和q。
推导过程：n=pq=4xybeta2+2beta(x+y)+1，通过对比n和tip，发现
n-1 // 2beta = tip
(p-1)(q-1)=4xybeta2
tip // beta = 2xybeta + x + y // beta，一定是大于2xy，
那么我们的思路是只要知道xy，根据(p-1)(q-1)=4xybeta^2就知道了phiN，就可以求解，而tip // beta一定是大于2xy，并且大的不多，我们可以从tip // 2beta开始遍历xy去寻找一个d使得加密成立
exp:
from Crypto.Util.number import *
from gmpy2 import invert
n=17986052241518124152579698727005505088573670763293762110375836247355612011054569717338676781772224186355540833136105641118789391002684013237464006860953174190278718294774874590936823847040556879723368745745863499521381501281961534965719063185861101706333863256855553691578381034302217163536137697146370869852180388385732050177505306982196493799420954022912860262710497234529008765582379823928557307038782793649826879316617865012433973899266322533955187594070215597700782682186705964842947435512183808651329554499897644733096933800570431036589775974437965028894251544530715336418443795864241340792616415926241778326529055663
e=65537
enc=10760807485718247466823893305767047250503197383143218026814141719093776781403513881079114556890534223832352132446445237573389249010880862460738448945011264928270648357652595432015646424427464523486856294998582949173459779764873664665361437483861277508734208729366952221351049574873831620714889674755106545281174797387906705765430764314845841490492038801926675266705606453163826755694482549401843247482172026764635778484644547733877083368527255145572732954216461334217963127783632702980064435718785556011795841651015143521512315148320334442235923393757396733821710592667519724592789856065414299022191871582955584644441117223
beta=11864389277042761216996641604675717452843530574016671576684180662096506094587545173005905433938758559675517932481818900399893444422743930613073261450555599
tip = (n-1)//(2*beta)
xy1=tip//(2*beta)
def attack(xy1):
while True:
try:
xy1 = xy1 - 1
d=invert(e,4*xy1*beta**2)
c=pow(3,e,n)
if pow(c,d,n)==3:
return d
else:
continue
except:
continue
d=attack(xy1)
print (long_to_bytes(pow(enc,d,n)))
三、题目feima.py
题目代码
import gmpy2
from Crypto.Util import number
FLAG = "************************************"
mybytes = FLAG.encode('utf-8')
flag = int.from_bytes(mybytes, 'little')
e = 65537
p = number.getPrime(2048)
q = number.getPrime(2048)
r = 663111019425944540514080507309
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
k = (p-r)*d
enc = gmpy2.powmod(flag, e, p * q)
print("n", p*q)
print("e", e)
print("k", k)
print("enc", enc)
#n = 764789710135699120066739558828098633577013306253421553430847195908034244362783426399681889172711929793563731863384139872322402736681090085666598621114324939409408964563306677742741428195863966989898498906831204752157005288028055139678360291316075877219030667685558110323821117721956754066208709423674599070852863328081495564626811408881020379619280834606394873439653313479059367387482717449792132890040814302415880441497255508283415162957128101398055871020323457216741679183472993371932538507867941404875130906965322325847739960927163953539809036794727803609900302282116111729856921452995125114084009947877974251520302979592670067613546606144401980991349553446645445805493512099309153534117016242573188431650384053169169037929526267038289233193459168030309932136331042640250813278140485915435024593329769782476261202489190771392735516338128092461124553594475652005536021219004598007475896848018535883345275525698202912140165492830229318458220859621536946916060728450732293426918231002157025978449298255884607961112874423611768107044113994666509578842156149561812558917421973274685922015605898024562717582262195308188734233843441532414373538708641762976079302448555298697105806160447760545580129674268456624678445339254341281619657391
#e = 65537
#k = 11376230879464757138290711299984908778464289005173308608189545435463525777268265977729128994228398091834020517958489408848527244519720030536561582611244172458641332639632981518360153087977263620583037286868169984156081495975325137150308201181821183705406433865681037783672009245951450744893423967519534524564872374719067025656950703655360275719627553370956932353637447232396991057691540662128565377895571740302756624004115592822652032877787683190174651306416910281916239819514603714322474683948222133746696116347630808594215555899448203106168014521796360515931362871133025281314243806320464177354177591228332335003551614106832308993911767231860241219942930903683175017203214440697826698228720134550320203010201162227480574211558033922830875117868895970801183417628548046732735178684031479465866770555097097049039401697156697973726498505003813383696303149763801522877588926847414588086172187481338569607545109010485980789181176815929895776940791230453092924387422291052184177606568352378605741988346025715326590594607822822612290794021218154340474272030636989456754518795702696600378337733961339618639033487933752890208434609460829539754273357617487166483257224739734126886305602260084115687043018921964438528469917594211427068125222889990486298031116975211308319185008573568652053973895884503801570264426091699176024805955546836991196229298757508243251307657063191639987383783941231455894746140575040062497070116929901714063774213552073013057990495816268901523247960107878691144148350592800965125699719038873342744331101838577313168280165305316417387319080806526792235761499758367535234473231638455540814177514642349235328627096125963532214440347089295557895745448430528014032156116184317483847359679936198373071447646642313893200567858353913090847963730766120387076016399374559419994285225024354973914324859198201290795827297428960819444555465333396
#enc = 34060123394885026852135895902114174741420905798709145293060330051120099446235081 75959937578250512247682431366914415542516188347989315926496861460097288681350613 62497513305566255974609490223522838895960638284623007834168557278161641696557120 00389498169436968104752869664000161313178540573443541400522104616752821040972932 73616440154366006459840893204293562528572479441219281056707330970932932294632175 76125348061286489771172237565953265811890771346162951530217309191335593471876470 38628166354931947477667451386964851651617505707218730288219372819548988437147581 43391261556855471531136031052154613166434906598219556045934969869265625391191673 45204235008891056258985058242481160261302148948149063732702363711144668099097835 19388260794480049310420315223517160170201336248525609185943580194555962563803150 02080874774865575956015168520269088790364811419775242493556070250118136993263843 15276262828177844727649328770809960027145982059502072773996922041811910780563036 37909218255891708167075272991629701955229696136017748809088320970570846463297390 69987069170803596414634398215051717036263970216112956111269513554371835506176344 16146503953634481941654417588166675739029356470862581387714547207849459593002786 105986536079890236933256809389161
分析：已知n、e、c和一个k、r与p和d关系的式子，那么很明显要通过要通过k = (p-r)*d去求p
过程：
feima1.png
import gmpy2
from Crypto.Util.number import *
r = 663111019425944540514080507309
n = 764789710135699120066739558828098633577013306253421553430847195908034244362783426399681889172711929793563731863384139872322402736681090085666598621114324939409408964563306677742741428195863966989898498906831204752157005288028055139678360291316075877219030667685558110323821117721956754066208709423674599070852863328081495564626811408881020379619280834606394873439653313479059367387482717449792132890040814302415880441497255508283415162957128101398055871020323457216741679183472993371932538507867941404875130906965322325847739960927163953539809036794727803609900302282116111729856921452995125114084009947877974251520302979592670067613546606144401980991349553446645445805493512099309153534117016242573188431650384053169169037929526267038289233193459168030309932136331042640250813278140485915435024593329769782476261202489190771392735516338128092461124553594475652005536021219004598007475896848018535883345275525698202912140165492830229318458220859621536946916060728450732293426918231002157025978449298255884607961112874423611768107044113994666509578842156149561812558917421973274685922015605898024562717582262195308188734233843441532414373538708641762976079302448555298697105806160447760545580129674268456624678445339254341281619657391
e = 65537
k = 11376230879464757138290711299984908778464289005173308608189545435463525777268265977729128994228398091834020517958489408848527244519720030536561582611244172458641332639632981518360153087977263620583037286868169984156081495975325137150308201181821183705406433865681037783672009245951450744893423967519534524564872374719067025656950703655360275719627553370956932353637447232396991057691540662128565377895571740302756624004115592822652032877787683190174651306416910281916239819514603714322474683948222133746696116347630808594215555899448203106168014521796360515931362871133025281314243806320464177354177591228332335003551614106832308993911767231860241219942930903683175017203214440697826698228720134550320203010201162227480574211558033922830875117868895970801183417628548046732735178684031479465866770555097097049039401697156697973726498505003813383696303149763801522877588926847414588086172187481338569607545109010485980789181176815929895776940791230453092924387422291052184177606568352378605741988346025715326590594607822822612290794021218154340474272030636989456754518795702696600378337733961339618639033487933752890208434609460829539754273357617487166483257224739734126886305602260084115687043018921964438528469917594211427068125222889990486298031116975211308319185008573568652053973895884503801570264426091699176024805955546836991196229298757508243251307657063191639987383783941231455894746140575040062497070116929901714063774213552073013057990495816268901523247960107878691144148350592800965125699719038873342744331101838577313168280165305316417387319080806526792235761499758367535234473231638455540814177514642349235328627096125963532214440347089295557895745448430528014032156116184317483847359679936198373071447646642313893200567858353913090847963730766120387076016399374559419994285225024354973914324859198201290795827297428960819444555465333396
enc = 340601233948850268521358959021141747414209057987091452930603300511200994462350817595993757825051224768243136691441554251618834798931592649686146009728868135061362497513305566255974609490223522838895960638284623007834168557278161641696557120003894981694369681047528696640001613131785405734435414005221046167528210409729327361644015436600645984089320429356252857247944121928105670733097093293229463217576125348061286489771172237565953265811890771346162951530217309191335593471876470386281663549319474776674513869648516516175057072187302882193728195489884371475814339126155685547153113603105215461316643490659821955604593496986926562539119167345204235008891056258985058242481160261302148948149063732702363711144668099097835193882607944800493104203152235171601702013362485256091859435801945559625638031500208087477486557595601516852026908879036481141977524249355607025011813699326384315276262828177844727649328770809960027145982059502072773996922041811910780563036379092182558917081670752729916297019552296961360177488090883209705708464632973906998706917080359641463439821505171703626397021611295611126951355437183550617634416146503953634481941654417588166675739029356470862581387714547207849459593002786105986536079890236933256809389161
aa = pow(2,e*k+r-1,n)%n - 1
p = gmpy2.gcd(aa,n)
print(p)
q = n // p
assert n % p == 0
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(enc,d,n)
print (long_to_bytes(m)[::-1])
