一些关于分解n的常用手法：
1.最简单的就是直接使用yafu分解
2.费马分解
然后我们令p=a+b,q=a-b，此时n=\(a^{2}-b^{2}\),那么\(b^2=a^2-n\),那么\(b=\sqrt{a^2-n}\),我们就让a=\(\sqrt{n}\)开始然后慢慢加1开始遍历，直到找到能够使得\(a^2-n\)能够为一个平方数即可得到我们的b，那么我们就可以顺势得到我们需要的q和p了，这个算法的效率取决于\(\frac{q+p}{2}\)与\(\sqrt{n}\)之间的差距，也就是说当我们的q和p很接近的时候我们很快就能够得到结果了
from math import isqrt
def fermat(n):
a = isqrt(n)
b2 = a * a - n
b = isqrt(n)
count = 0
while b * b != b2:
a = a + 1
b2 = a * a - n
b = isqrt(b2)
count += 1
p = a + b
q = a - b
assert n == p * q
return p, q
3.p-1光滑攻击和p+1光滑攻击
https://blog.csdn.net/qq_73643549/article/details/133692704可以参考一下这个师傅写的很好我在这里就不多于解释了
4.已知phi和n来分解n
共享素数
就是给我们的2个n有相同的因子，那么就可以直接求解就是了
import gmpy2
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q1 = libnum.generate_prime(1024)
q2 = libnum.generate_prime(1024)
n1 = p * q1
n2 = p * q2
e = 65537
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
print("n1=", n1)
print("n2=", n2)
print("c1=", c1)
print("c2=", c2)
题解：
from Crypto.Util.number import long_to_bytes
import gmpy2
n1 =22036096414750333101406538757625812613248444424049684758772058140377463618250795867832853117902163257003301132932490853355450673043991381637053778653821758783435921283322439267628837074056789021611782010444749024512216306961829453158759193969454712080047205883631153040900193575534288719429526169135614695862857156639195562501217424283401364740789214390377624598500939079307163832197534297642842744345373413423859103414676878739674227554029537817890874031594311152843060524913028526429344172693584167398664817727426767686424415189580527939256633114120720308173788544194669684834369132677253418971615644691719536820433
n2 =17251653165250011947306159769694143433212298910745609670733920118632739529605426957617875166211610794383631191273183964010346725508667657137931394653419082978603166138439632713627832321960586938891805262605225424775586397813147240201440036009395991700175612039074317131837185920131565272816639771739150718839592250080325774556601865770352479323350280393818365902570673799584200153846520860657815432981116910233453207519365604533077996449249223280685559491369393277114405166293011856168173778428700718404816038991911974902005969923746846815798515831172402122367026339135245751136695128279659872423027539333024854133659
c1 =1408937404754902028814920445701404613476983383738408959873219805755187459225302977012340464647741276263048769176603562703588286152102079561897286480939341184453940846603761664643956274520695676061184610702912592321357240109665885587701906369214592438887065694062151546241739122722790261888290706296747328780758965559093085406877315628139811554345214347799361309288949307776501119359571116522001853935560023530705364795364624152061166945046882418058831567088890277747158775876953662285842999920594778445526224560016361787941610542255000514402493843548068271595134879195073239601085319795505131267697387692179944010772
c2 =12175155463891225370775786368564999885751076529394005420368968241428058465831204925081389807872272508968531564921996276054143112205083003561546962102395368677755381589762565680900651699885381615975236663522025080384481537727180649424984636506390139648492522347366656322729441290553251505232488994951243521740296115895651926783520321289129993169836271218322014443396220481361007479796234525990954874013729001502984583162486353287639655447340498584591591009224750835072707121652727119580764546240945763088815277130694950594020142961659318737857067755125666395542079926757603295535345281657293981259718286213812909191174
e = 65537
t = gmpy2.gcd(n1,n2)
if t != 1:
p = t
q = n1 // p
d = gmpy2.invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c1,d,n1)))
共模攻击
在对同一明文的加密过程中使用相同的模数n，对同一明文，用不同的密钥e进行加密，结果是得到两个不同的c。但是呢对于密钥e互素不互素也分为两种情况，第一种就就是gcd（e1,e2）=1,就是e1和e2互素，
这个是我们的推导过程，显而易见就是求出s1和s2即可，
import libnum
import gmpy2
n=103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313
e1=3247473589
e2=3698409173
c1=100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
c2=86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
def exp_def(e1,e2,c1,c2,n):
s,s1,s2 = gmpy2.gcdext(e1, e2) #这里就是求出的s是e1和e2的最大公约数也就是1
m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n 这里就是求解出来得公式
return int(m)
m=exp_def(e1,e2,c1,c2,n)
print(libnum.n2s(m))
那么第二种情况就是\(gcd(e1,e2)\neq1\),也就是他们不互素，对于这种情况无非就是在最后一步的时候是\(m^t\)这里我们就使用低加密指数的思想就是了
from Crypto.Util.number import *
import gmpy2
e1 = 578
e2 = 392
n = 21792499489446653209359648268647408248484077502636323240941263512972521642966446318685589383376089358615828479732487823375467576966410911798574546152698546172208644494120844910028661801069139412883722092087841337354582470102991346201250757430966278341015814968426027288609918021263801588485143246793300627932938615206724828284751003817198828431954277335825721403220979778254648036632075276172476930299390290573025768956364488376300510746252434716167769851984446036711610150897081622960442923737196929758209816434803424884970510663599653463189492521652184966337230394292288573277654840483815385709060428243829968709733
c1 = 1295899105546936416711955776176786556954959764395004520666273768220642845167647126115394711085928049897436984534359683209799926877399786065216458011526399070534983898250382591372240231327810785046739203554803467534631081973525005181861203752320250219830020069663762443152692331055158533035896110900630817135766754326408199206651276750278716441636585609321276880631239079781048185864263400051324827820941692502756433463495216541801444097560942509859140724554853380906157874504969878938634453309110942314571026225239704634981956565844426060346340677136929914119932647724346392582368980017754022031748246759437397697793
c2 = 6100251841868768392049795926373721745054594119167283623934416754665831830741776139556785242664295441966913393337547165974512844660057299278828165715333417692799802949938590574117892067491764731548261988101287152727657523152041485072722017224763458684855801781252103126948392647769522681887089175624603484575515518773338807587100984947122699045372679023951413797420560947466351031076552444459222063798664625809884979352261000568340687804017980769948161583294444251776973765636460565633962599948356942127522339715718463747197473475842874431177106692482361060930677857750098337273277996678196019443721319477484374253966
t = gmpy2.gcd(e1,e2)
s,x,y = gmpy2.gcdext(e1,e2)
m = gmpy2.iroot((pow(c1,x,n)*pow(c2,y,n))%n,t)#与第一种情况不同的地方就是这里
print(long_to_bytes(m[0]))
低加密指数攻击
这种情况一般适用于给我们的e这个指数很小，也分为俩种基本的情况
一就是\(m^e<n\)根据我们的加密公式 我们可以直接对c开e次方就可以得到我们的m了
二就是\(m^e>n\)这种情况的话就是\(m^e=k*n+c\)我们需要爆破出来k
广播攻击
原理
对相同的明文使用相同的密钥和不同的模数来进行加密得到不同的密文，就是会得到多组的n和c
一就是它的模数有不互素的
例题BUUCTF-RSA5
m = xxxxxxxx
e = 65537
========== n c ==========
n = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
c = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320
n = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759
c = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855
n = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491
c = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862
n = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751
c = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613
n = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067
c = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357
n = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369
c = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932
n = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137
c = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179
n = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191
c = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006
n = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941
c = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934
n = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491
c = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869
n = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019
c = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467
n = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299
c = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971
n = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551
c = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175
n = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987
c = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457
n = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837
c = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842
n = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451
c = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724
n = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499
c = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024
n = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973
c = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887
n = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603
c = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889
n = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659
c = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346
解题思路： 由于模数n只能分解为p和q，所以当n很多时，p或q有相同的风险因此不同的模数n中可能存在相同的p或者说q求出不同n之间的最大公约数 gcd()，如果大于1说明这里存在漏洞，可以继续攻击所得到的最大公约数就是p或q，然后可得d有私钥d就能得到明文
from Crypto.Util.number import *
import gmpy2
e = 65537
n = [n0,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19]
c = [c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19]
for i in range(len(n)):
for j in range(len(n)):
if (i!=j):
t = gmpy2.gcd(n[i],n[j])
if t != 1:
p = t
q = n[i] // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c[i],d,n[i])
print(long_to_bytes(m))
#flag{abdcbe5fd94e23b3de429223ab9c2fdf}
二就是模数俩俩不互素，那么就要使用到中国剩余定理（CRT）
什么是CRT 可以参考一下这个博主的博客https://blog.csdn.net/qq_41115702/article/details/105909120写的很详细 我就不多进行补充了
例题： 鹤城杯2021——Crazy_Tech_RSA
from Crypto.Util.number import *
from Crypto.Util.Padding import *
FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
p, q = getPrime(512), getPrime(512)
n = p*q
e = 9
while(GCD((p-1)*(q-1),e)!=1):
p, q = getPrime(512), getPrime(512)
n = p*q
d = inverse(e,(p-1)*(q-1))
return n,e,d
n_list=list()
c_list=list()
for i in range(9):
N,e,d=init_key()
n_list.append(N)
c=pow(FLAG,e,N)
c_list.append(pow(FLAG,e,N))
assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)
可以看到这个题目就是低加密广播攻击 直接使用中国剩余定理进行计算就可以得到结果。
from Crypto.Util.number import long_to_bytes
import gmpy2
def Get_Mi(m_list,m): #求衍数
M_list = []
for mi in m_list:
M_list.append(m // mi)
return M_list
def Get_resMi(M_list,m_list): #求乘率
resM_list = []
for i in range(len(M_list)):
resM_list.append(gmpy2.invert(M_list[i],m_list[i]))
return resM_list
def Get_result(a_list):
M_list = Get_Mi(m_list,m)
resM_list = Get_resMi(M_list,m_list)
result = 0
for i in range(len(M_list)):
result += M_list[i]*resM_list[i]*a_list[i]
result %= m
return result
m_list=[71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
a_list=[62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]
m = 1
for i in m_list:
m *= i
result = Get_result(a_list)
e = 9
m = gmpy2.iroot(result,e)
if m[1]:
print(long_to_bytes(m[0]))
维纳攻击
满足使用的条件就是\(d<\tfrac13N^{0.25}\)
推导的原理如下
\(ed\equiv1\mod \phi(n)\)
有：ed=k\(\phi(n)\)+1
因为\(\phi(n)\)=(q-1)(p-1)我们可以认为\(\phi(n)\approx n\)
俩边同时除以一个dn
有：\(\tfrac en\approx \tfrac kd + \tfrac 1 {dn}\)
有因为一般给我们的n的值很大 那么我们的\(\tfrac 1 {dn} \approx 0\)
则\(\tfrac en\approx \tfrac kd\) 满足这个式子我们就可以使用连分数来进行计算，就能够计算出私钥d了
import libnum
import random
import gmpy2
# 生成随机素数
p = libnum.generate_prime(512)
q = libnum.generate_prime(512)
m = "flag{20d6e2da95dcc1fa5f5432a436c4be18}"
# 字符串转数字
m = libnum.s2n(m)
n = p * q
phi_n = (p - 1) * (q - 1)
# 计算d
while True:
nbits = 1024
d = random.getrandbits(nbits // 4)
if (libnum.gcd(d, phi_n) == 1 and 36 * pow(d, 4) < n):
break
# 计算e
e = libnum.invmod(d, phi_n)
c = pow(m, e, n)
print("n=", n)
print("e=", e)
print("c=", c)
下面这个就是脚本
import gmpy2
import libnum
def continuedFra(x, y):
"""计算连分数
:param x: 分子
:param y: 分母
:return: 连分数列表
"""
cf = []
while y:
cf.append(x // y)
x, y = y, x % y
return cf
def gradualFra(cf):
"""计算传入列表最后的渐进分数
:param cf: 连分数列表
:return: 该列表最后的渐近分数
"""
numerator = 0
denominator = 1
for x in cf[::-1]:
# 这里的渐进分数分子分母要分开
numerator, denominator = denominator, x * denominator + numerator
return numerator, denominator
def solve_pq(a, b, c):
"""使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
:param a:x^2的系数
:param b:x的系数
:param c:pq
:return:p，q
"""
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
"""计算列表所有的渐近分数
:param cf: 连分数列表
:return: 该列表所有的渐近分数
"""
gf = []
for i in range(1, len(cf) + 1):
gf.append(gradualFra(cf[:i]))
return gf
def wienerAttack(e, n):
"""
:param e:
:param n:
:return: 私钥d
"""
cf = continuedFra(e, n)
gf = getGradualFra(cf)
for d, k in gf:
if k == 0: continue
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return d
n = 113881698992379349039968368927979997900777221951663104697020683691495129639829918739755194174063944178083527489820939138302751895652076620380510013941997706327553964127612610209509889011613768847759318892303231846117914554931459295347697888260576901354448014917692680573408654658384481284699735788978230690197
e = 39068960413447607023613035707248214114819409621234801785480423979473767995171860917209502861408393208940683687475760366491413173744775811644295874981290403938714121977201901942939425294427737703229098649131737380098596135730392902019429964095866394165971291108245774407908011073271822915371753470010435225545
c = 32897925577913728659288168937025744709859960639901500169867896018406263110205704273203287172003057450591000201857719871686024077615520906540631374442504017489026298422189715372129838501090730593164075113452055617571409044743698645392909829425374093273187125709095368164744188182156849031225036001381531504057
d = wienerAttack(e, n)
print(d)
m = pow(c, d, n)
print(libnum.n2s(m).decode())
dp泄露
原理：\(dp\equiv d \bmod(p-1)\)
左右俩边同时乘e
\(dp*e\equiv ed \bmod(p-1)\)
又有
\(ed \equiv 1\bmod \phi(n)\)
所以
\(ed=k_1(p-1)+dp*e\)
又因为\(\phi(n)=(p-1)(q-1)\)
\(ed=k_2(p-1)(q-1)+1\)
所以
\(k_1(p-1)+dp*e=k_2(p-1)(q-1)+1\)
\(dp*e=(p-1)*[k_2(q-1)-k_1]+1\)
此时得到这个式子之后
又因为我们的dp是小于(p-1)那么我们的的\(k_2(q-1)-k_1\)就是会小于e的 所以就是会在（0，e）这个范围之间，
第一种情况就是当我们的e很小的时候 我们能通过爆破得出
我们令\(x\in (0,e)\)如果找到一个x使得 (dp*e-1)\(\div\)(p-1)是一个整数 那么我们就可以得到（p-1）的值了 那么就得到我们的私钥了
第一种情况：
import gmpy2
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
print("d=",d)
dp = d % (p - 1)
c = pow(m, e, n)
print("n=", n)
print("e=", e)
print("c=", c)
print("dp=", dp)
这个题就是最基本的dp泄露的问题
exp:
from Crypto.Util.number import long_to_bytes
import gmpy2
n = 17954000555185130679232377513216924086370205717680723426279833171815673097846434355592747466782173529597978954062272371758852339605432963940809244445748900431763988392120156128524694217746804744076348205536430811607694098089294013508111154514184079159181563040241302764793111632189829652065825442796716027051750043654503172469553222784393034067341575558782690547449884992414106322578261286526556856377419622164651917718772498388922129465042492616904419638034789576380038341882418547113136903862482397767904921157094396562770484669239932933837196899640811033424030302285885080504355934919967693498648701839252087380477
c = 1808490145328726635638705291306162339133116115672167390186563455429486046847680827004544020052978814401354685508506555963361065725012891622174617670820924531959433674273579973778657669162210657120785539629874456938159379512635932223403818177582242406964621317531188027900758868453176575753681627336133481701182056262584118645398172089436811174776978418919803975809158758707062473122656821152108292060156091196577573172937093806159669057467094718771367509856968694209472630329096814023864642219783061245777457366202879949123915168571990229277326042767587009623951348541055835347386485900505749475571895673653225741649
dp =114993440308125678369350484461242628405806013372930792337329972720600942891053460367721272956155528263465552939386621554396883112994907299126303463171544968629898544811159986442249990975328659373544491636958873255689808151391606942912468529923159009459712396428051292828093059494024457367637991626193487727331
e =65537
for i in range(1,e):
t = (dp * e - 1) % i #这是p-1前面的系数
if t == 0:
p = (dp * e - 1) // i + 1
if n % p == 0:
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))
第二种情况就是e很大的时候当我们的e很大的时候我们通过爆破肯定就不太可行
例题：
import gmpy2
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
e = libnum.generate_prime(128)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
dp = d % (p - 1)
c = pow(m, e, n)
print("n=", n)
print("e=", e)
print("c=", c)
print("dp=", dp)
\(d_p*e\equiv 1\mod (p-1)\)
有我们的费马小定理我们可以选择一个与p互素的数a 那么
\(a^{d_p\times e}\equiv a^{k(p-1)+1} \equiv a \mod p\)
所以就可以得到
\(a^{d_p\times e}-a=kp\)
然后再和n求公因数就可以得到p了
exp:
from Crypto.Util.number import getPrime,long_to_bytes
import gmpy2
n= 18150086749964030204952772593650655354407282168407543480518017821905322058792108409169209539752974177937328703466169798097779231540410352308736251888449285307132274903811942187361234788236374036493935354342502760429195828731474432692281516115002087485890105917067613983079156790015275611914738187418424730456416770000646598861170179898016595068557049151791620868027603590052357726580431487083778514163249201637184318559165989454489485258667170883129099757366657203826319909509544670881866298317938263281638296241860739828567999093491297970389142395080780768892194380031018324855383292685388767246393785705551231780899
e= 278817530653170259039233683650169866189
c= 10813189255953686674328168562592345253502176950586624384555229875947895107088800774325110599057171743065073092283651992594106863499561887773348061509184951920329015539552207920010924284253109754443530283215130327152416667309504455641730629770856098336299767661535526880065006664806270833698497579073641076473649621250873969544362062393319711114090739414415757921473984666129110213417578310035188480139392986280529932137364474426391469019554935239234968517869914506321750458197587849623935306068749435995413807906558975073047215241796461878288003366415184144140612947217041288538376514085070670565572628317388808356563
dp= 25015362092988139281045705051525732988903355826221062953430054346210238749256645995431509510448988062597830708438496723137288693056422683942336451600173722142331077900759633024803467824277121463213906905346623305038031660927650043841899168305106293747254814365869018331032172781810238397508103692878400636333
a = getPrime(10)
p = gmpy2.gcd(pow(a,dp*e,n)-a,n) #pow(a,dp*e,n)-a 就是kp
m = pow(c,dp,p)
print(long_to_bytes(m))
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
第三就是dp高位泄露 详细请看一下这个大佬写的
[https://www.cnblogs.com/vconlln/p/17066500.html]
dp dq泄露
如果题目给了我们q,p,\(d_p,d_q\) 那么直接在模p和模q下求解即可，如果模不够大，再用中国剩余定理即可
import gmpy2
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)
p = libnum.generate_prime(256)
q = libnum.generate_prime(256)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
print("d=", d)
dp = d % (p - 1)
dq = d % (q - 1)
c = pow(m, e, n)
print("p=", p)
print("q=", q)
print("c=", c)
print("dp=", dp)
print("dq=", dq)
import gmpy2
from Crypto.Util.number import *
p = 112454994630978850005784651276022327545786198205744597431888680937657203192943
q = 111081771780978300442208201256251933100607227308819156491182881723714968913833
c = 7847140580627012782899798457736961376953768684667159008470556786390887805253326211691923724846808704462396746105331991924048819814322540306282164012066426
dp = 99016059099144522019375365089687785694029213535292918424815544402513220169503
dq = 79504900574184798493105575420403885224379864982754477219462523963780735261625
n = p*q
mp = pow(c,dp,p)
mq = pow(c,dq,q)
print(long_to_bytes(mp))
print(long_to_bytes(mq))
m = crt([mp,mq],[p,q])
print(long_to_bytes(m))
e以\(\phi(n)\)不互素的情况下的攻击
、当e与\(\phi(n)\)不互素时 我们就找不到\(\phi(n)\)的逆元使得\(ed\equiv 1\mod \phi (n)\) 当我们遇到这个情况的时候 那么我们有三种处理方式
1.