easyRSA

简单的gcd()运用，找到公共因数

from gmpy2 import gcd
import gmpy2
import binascii
c1=1355386572112372850611036490966188175538987863527927779960990786002452575170634054152212358933763547055422759756027415133273832918485098947876171096276729416374754375351954023434636784414452074632079620319919916399472952978595188578240886468294826420444304995599277105894055963835188287235635124702371763798280974345092661352727696147636416880598697984896058201794475838054061012604762913331122089815538163372055678041274333240141855434364313862079318613288609268694638414313107742788496861764919534572555564813096923547764022387270411562081525314199522682854725378344260430282649981271048334528928379571310731841486
n1=12825100771257456077149964910605574628379912849150485275974020467902117235464130742121032530579724237866564791769251587583725631441489760720100057002948256344359458323465989937328959412299485905695960531657748731414339028199922429650835662666221800190685881209740102840495258149699357507420871994133381553002962266178100932214532054094696463627129336711033963381097413539659886146489405551742843204180033734977810683480542088934851102406520152543021307892757619684557961750000731528948222632469628321045924617868708870938946037379106714397519120005629351078109442687651029509686361054127744053158563626266699075075737
n2=12106667820155092651005980788681668939257714995685173260910711516508690589738399069362876916118479326569560356438772026406627666696459488677154928623481898279221763592991189674063719945636491539578401643457393148592966590912378623321315886510941581133207379498943442783133771909578755977685155060485627632310832382151388077346940192798438100540619466956848168872919742741008418429745589887364045046983841365071962255428055166475284027313634844775738922659401945163832045277387473402653688033772789419513303256030578783069827187965792213613558772834195874813704269442102682045669656446050452299378335318477524181485253
p = gcd(n1,n2)
q1 = n1//p
phi1=(p-1)*(q1-1)
e = 65537
d1 = gmpy2.invert(e,phi1)
m1 = pow(c1,d1,n1)
print(binascii.unhexlify(hex(m1)[2:]))

easy_rsa

e与phi不互素，导致不能一般求解逆元
通过求解得到e与phi的最大公因数为4

import binascii
import gmpy2

p = 179339724246229843726779086497758086700767091942823382102884697671804799304652009167355556601254668595454468719362996895223198577570604382893112170906563827541309282210572274232294619880050319161575088535959209840362236242388298589816970890276440396102003032194498931444904045321511867770510618482963253444171 
q = 129452010891691830141409340110903415892699564803510819611230128697000018597328039023549940695442548949477197670554474296663476556526956844201703892277849111159918130079993188297874083230421826432704150193965881475251551569007803579575294635406881373500519242104699767331003255332253689242203833528581342849543
n = p*q
phi = (p-1)*(q-1)
e = 16
d = gmpy2.invert(e//4,phi//4)
c = 2808687352764477098395390294961819217315835766406235505320171029927556669353148216977881915171651466299509767224192462948015834874984486165348031860747483578335393807164134429328527196534260381656710151946245376450723534200936105517142950677477408381688538476698011647690160341234578738276252465419868981865480237722922378366606827835972506973590707313723621953535237744085453112422520046215491391634375583932984581117857542239086424415712847637926466842915619897955952838264553358372055862162937724305897337642251117481658246011399468928899099485021249046029674378841452856157322899643045650367542092683227867005292
m1 = pow(c,d,n)
m = gmpy2.iroot(m1,4)[0]
print(binascii.unhexlify(hex(m)[2:]))`

hardrsa

首先通过开根得到e1 e2

import binascii
import gmpy2

e1 = gmpy2.iroot(281487861809153,3)
e2 = gmpy2.iroot(49947026556362417,3)
n1 = 17963064878219297499926539755529525701375912229028373100173473134607394789664287607368340798794683194437682952690508928886652995386383146889003406172408614571972729531812623495934448286040540097840662578369651592616783708165933036306017892497833364373485432426417809013633924450913331047907013191887482793788688736422653892662900369700701081539738763728230752094073294005560908179016172875213907812943500460207818071050071895019325622709305548027158608131204996083137774696224909740835744016252811508782404134677682054379270633099277445509293373814980267901088167711756798567438727515561927878122737404945310578048219
n2 = 18724308600993680772040132476147443059937062865510694686877532603079614680086774925762072671394784787691065784432778464228230479469525602116950506124178922966302228834351364607333986401435253287986565305219407269279319145851605536263946222693062150972421981977212241191765587924831341467136660852112059970632881164690431105960074159318822853545203221878413076459098980779367764115932851271974512575031047448816911420663521305894273613218483567916755598148798190932027939210902403155767487515702073721374684377875350047635848757189883075996002319631998930528597791545501045272097478778892159675588840857142652895265911
z1 = 3227115480108687251143827858010802848948769835037303555920483802259214819344453925631294417806432714176524195861938002549436386343852098195596387592472144546437874859798830812267011643855867112448231876484774166379425286268881326798711769931848606930434512049291154720821129654830620829493843059059835800242333615312846190103494997079811557982251508839708002883778910917631553992619052626191828854730582898255670700858011426887487070944722267353577011178466697504947762804170585435684678698950363434075952461947607646966414518037049739527149945887998812316417005423702083018805606242882095334884780205891592816168103
z2 = 17139275485259110169718125211934888629708949924849742315041043571562307752055065297519271353044041441264892639110696891866965260187916302606640599942290472419225004160983308212078726494659784938191829066322525193057563553826485587827351089778042018829577434276292639964092632076137550347805354953807458891741631731341557365791973551073866525939105337652370251223107187937345980460911362790708353134912495192276504731259631723322913019046682545871283275754931576128656069033856416078373511440449107627433371949378696710812496517227289219196266427370667273925986284754478473526404645897976394395240810054198847661134728
print(e1,e2)

再次审题，下一步要通过两个c2求解大因数p
已知e1 e2 n2，想到了共模攻击

import sys
import binascii
sys.setrecursionlimit(1000000)
import gmpy2
def egcd(a, b):
    if a == 0:
      return (b, 0, 1)
    else:
      g, y, x = egcd(b % a, a)
      return (g, x - (b // a) * y, y)
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
      raise Exception('modular inverse does not exist')
    else:
      return x % m

c1=3227115480108687251143827858010802848948769835037303555920483802259214819344453925631294417806432714176524195861938002549436386343852098195596387592472144546437874859798830812267011643855867112448231876484774166379425286268881326798711769931848606930434512049291154720821129654830620829493843059059835800242333615312846190103494997079811557982251508839708002883778910917631553992619052626191828854730582898255670700858011426887487070944722267353577011178466697504947762804170585435684678698950363434075952461947607646966414518037049739527149945887998812316417005423702083018805606242882095334884780205891592816168103
n=18724308600993680772040132476147443059937062865510694686877532603079614680086774925762072671394784787691065784432778464228230479469525602116950506124178922966302228834351364607333986401435253287986565305219407269279319145851605536263946222693062150972421981977212241191765587924831341467136660852112059970632881164690431105960074159318822853545203221878413076459098980779367764115932851271974512575031047448816911420663521305894273613218483567916755598148798190932027939210902403155767487515702073721374684377875350047635848757189883075996002319631998930528597791545501045272097478778892159675588840857142652895265911
e1=65537
c2=17139275485259110169718125211934888629708949924849742315041043571562307752055065297519271353044041441264892639110696891866965260187916302606640599942290472419225004160983308212078726494659784938191829066322525193057563553826485587827351089778042018829577434276292639964092632076137550347805354953807458891741631731341557365791973551073866525939105337652370251223107187937345980460911362790708353134912495192276504731259631723322913019046682545871283275754931576128656069033856416078373511440449107627433371949378696710812496517227289219196266427370667273925986284754478473526404645897976394395240810054198847661134728
e2=368273

s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]

if s1<0:
   s1 = - s1
   c1 = modinv(c1, n)
elif s2<0:
   s2 = - s2
   c2 = modinv(c2, n)
p=(pow(c1,s1,n)*pow(c2,s2,n)) % n
c = 2519784075571363990355801446319896012899269885206109823774950526790963683990153738128746190638393784786596405506731840240589533349004496866914346264165223649729391271273556253486062775839454219993404367212857109756953767455690796208791355456292865648813147954137342631589248190059107210837405220320124078796283385382994717993598412926549647978190991179177838292156516142496656655553613583148209957002024913648233539568864514049304210818483385640653620994626277688420873819215255064048179977060710057344959786809400706849894340484144098989681668420576351191631435372353088813222856086210998354107613629733847782962190
n = 17963064878219297499926539755529525701375912229028373100173473134607394789664287607368340798794683194437682952690508928886652995386383146889003406172408614571972729531812623495934448286040540097840662578369651592616783708165933036306017892497833364373485432426417809013633924450913331047907013191887482793788688736422653892662900369700701081539738763728230752094073294005560908179016172875213907812943500460207818071050071895019325622709305548027158608131204996083137774696224909740835744016252811508782404134677682054379270633099277445509293373814980267901088167711756798567438727515561927878122737404945310578048219
q = n//p
phi = (p-1)*(q-1)
e = 65537
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(binascii.unhexlify(hex(m)[2:]))