easyRSA

N1N2−q1q2=(p12−p22)q1p22q2\cfrac{N1}{N2}- \cfrac{q1}{q2} = \cfrac{(p_1^2-p_2^2)q_1}{p_2^2q_2}

差值大概在2^-2047，可以连分数展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *
from tqdm import tqdm
from gmpy2 import iroot
e = 65537
N1 = 3289746385054724131365721020639496300945479666755005407239362220435929471663971559131973068094267242759747682915202602265269024546168034070348080432976135403371083936361236868186476392365554734516698695915807318328547349333450125215426536032220967810893464208090339137598724593917266763998037725309967496052803477931961681761135080900299333158097292389350335121611775110493009954911832572636099153354952171029044016319029661601727739828271424563980850243898202779669776639104067478441675153857040164775196713586656673764171877161326751846236980454659960530174960321852298270258312146241360929350418220172331956030775384681767932014061291168620965347842124549316096247113770711834360498936747471888481237404034471246978342020816271785925362208839937490625070051801028223342083281773366267363149243726101075926327550718757413133631119649782144511080448476370411156544146278468602957599519708203511203435394861053372096309444985117323976240925612725880016576029876493825989064619463226166401883310383733295274652092903872304933657343307118616812213637906513530016004460475073291823916649597185291734261926576108675712303422832460766980003743958182130150811173621769221262799069912858162405156365709344847558244669016188305691537672753134766406649385330682157984720023661279153645005631349488537261911860571171672813544726579872640486753312665928030263533489558821140031095492111373847722540582741061909831250761476687
N2 = 2292263744571677490370198515319050673022350367021940229132415885393214523108231545410288799524823682686607005535541881885794949322622162858593875970155712564868530006799557973311000615581843236548539733075504282834631939435260232339940338468890310925405870533590386398071667718507612723307978025099102004513584485422609923041107028535400446355591432930994813185411831860201820145983435091523773691560011687528125877698679841462745728326159525372061320952493949821495222248383893254880735838359120880431072244214361010867779059178282739912365087421904643477215607290679708352033106358356290644004853543174075195107627794359272018100648168661860452919746052205404895413998960327066611970768862624073581670828267510841602161728589913841163473811894218339948715205301321356774629578043062238684103507006315521103670400509643518854842374093509082331379305822049420033746124157212615698602544129110388591266923967512746018551734391176602223771675279723873630468099034521371667295520830509224068753383327420799595674898227670628881521095495898465890256628288779785408613688721508315026743250146090703141554141208186588758560579281631449476819201739513661261100456398775274335050320480934180632543242116316388750179657345282978014879818574111951053767465935985181195234991374892341383106554664200986728169474150302232887629401491764905429656980077385228539526682528035467486946883267941678859904770170914569949948781798383
cipher1 = 758346536265430423952822486066685295768780904671958564513706915003627653309986327906604310025557676880130150973194443591153899441660221125085406078577489990064034099758898680250346992154199616929381594288918352701155172644054184374384778201304104144436102359709180739955762513436889301607686277088230852661148556440251553059814853050711377102806879036793210874472411397851504602916797481132018776755416068149801594219844674499351889997208649442043923826505239289470153001663639688739092310857881616013610569511757767780350165048282465256454770748877584119349207769812826840607665168961680724232789109312681055375411182858820698025923104994832566402422884359019460479145829812817446509615552819113705033128233093081687704471007797878802184788802106948491309583791881593217988561342681568377126606055476508381741342859362339824940846336741346126512500348868154174463810299929429409815515908136711497765026252563374327541491024303290989175383501994515761077240391195396083766760326143468930305986070405962303571534654392917816088220966950447926277802817335097304148972911332832248113849846752219065263639980629213197260594242031101803801865240157341309018859709063723920616432168289755151080828619642932516426139982777613526680161145782566883722320235485389839997229666979487071672091138823743231576011381309205283462045931376953038071401274899229258796970036565931730655471667545203734032609058125128632555918726761
cipher2 = 2281163375114595112593683220870779643793045914138930809669934728297504812745368657964524831965320392164027435706363680996214578180045485041532876049868691323690200562004954003143194397255512951717400899604307009993030792644670830602941543918898535970779253703220162651022293286208338299826844988619345629892007235258389532666376623514170628541968337364745860334903754371727427376399211310359996960626733244649671665175464666807399652951289553389561033148215888827057495743582318390507639029065358587166019110069479019692411629179363742708597061223484237748437654542910240974030049076975739481960903748359283570086571360417832776823264202688497555419017227144724790205424467059280453940666789219388347170532415234759731375390229140544207931837445265744016932142504371200121886182154284965893665022781184321216382767703694597553489507371271887593799060901908513758134472760311502510753557029741715193386673389466599068008750012915225818076301655694045130332321314233483042503950958442501013310465239137942770667655164906193219286435485452257047415797293472629254376873962168035382262951696816840667369861437088409243033239980128747965838367176274122593955221422537124546203553941387134587884149412499272660959871746858550851448840531698152805786123875121854564754397297726121984646669253047201515221545545683432754661774694401343486893270795112334494874407955432598253951220055000392855162417030953645428808146502304

c = continued_fraction(Integer(N1) / Integer(N2))
for i in tqdm(range(1,2450)):

    q1 = c.numerator(i)
    q2 = c.denominator(i)
    if N1%q1==0 and q1 != 1:
        print(q1)
        print(q2)

q1 = 3788168030190090069154471054370749225548093825987159842333706566469336121868385043427479257673208773354909025311935846736083070037369292961252050424209181515338323210297317914339287
q2 = 2639559168876722909906543645899553778405999045274645138605776039734628009213435785374669992943878117591722111363642861521944203624869581784773179274165571465594949514464423586197447

p1 = int(iroot(N1//q1,2)[0])
p2 = int(iroot(N2//q2,2)[0])
phi1 = p1*(p1-1)*(q1-1)
phi2 = p2*(p2-1)*(q2-1)
d1= inverse(e,phi1)
d2 = inverse(e,phi2)
m1 = long_to_bytes(int(pow(cipher1,d1,N1)))
m2 = long_to_bytes(int(pow(cipher2, d2, N2)))
print(m1+m2)

lattice

{e1d=1+k1φ(N1)e2d=1+k2φ(N2)e3d=1+k3φ(N3)\begin{cases} e_1d=1+k_1\varphi(N_1) \newline e_2d=1+k_2\varphi(N_2) \newline e_3d=1+k_3\varphi(N_3) \end{cases}

不难发现是共私钥指数。

构造矩阵

Br=[Me1e2e30−N10000−N20000N3]B_r = \begin{bmatrix} M & e_1 & e_2 & e_3 \\\\ 0 & -N_1 & 0 & 0 \\\\ 0 & 0 &-N_2 & 0\\\\ 0 & 0 & 0 & N_3 \end{bmatrix}

其中

M=⌊Nr12⌋M=\lfloor N_r^{\frac{1}{2}} \rfloor 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import  iroot
e_0 = 37389635736858807810703086504264263440188928763651776502954117173983775626039037008534821321761858567723984257427640816113325770208734640385635663643682102780255726244659849205653007212192504491177021176624605722718152646889627480051142935241036578957272339153039961711802753021931124235464986935316295647379
n_0 = 87704526707772151782606625126900349506318713860335977395824997219721333991491994027303721441548488339412359519408127174109547119019245873976917916080340858937125736650376514406944094998893225164676363063781400756374403299951466867573215964360920244878373810391250391475087527409213204756990192602517961590163
c_0 = 78656123855003406993963573497876652287109947684890741747390020445306861422604130132525802389554149844489256622057009394678814584233565675702142297935509191018145970589418173328145004732595569847696022333024124469320873194195223535859964387627938665526123562969554622541694399263934496631337485091067073489148

e_1 = 28535169211141109871379321582501492434722235009040085167442370469971731780018594508141105234950857774463438226249819106596920677559656398153362076685288045484306156454558741088396794170762527953573082734587618137075161676392362016474076363311708889307420903699720319611668580377903356783222664068961626803615
n_1 = 134298877057487865189085342936485527664167450453080897084604607959501054859295769447683135156167266222961308751016451904929475702646252122360203167489936020076488657815646993920082535307414536854323149177250531362615850689341066360635074886835720438532107976530111551202845697404444502476862934946146194420313
c_1 = 3208711484494445700905074340207543865325589037128163311082565190422756093807236786011349707275838139469873445326457948489588753029946395247710197747538418278782966047404435385208682596795152082296050804126524129644617710791433973098499266439604632728957505961744280687343384601998774018570047292904007768763

e_2 = 27653153186459366670449283776658896188717513017934031993526241644501850206894800647711159987946276669184047769965182746812351757618147642060630769822810070480507035319320426666128599562714143342910248758055424582501972900763786232170145957578683616604737178839977216709381529813768748145393798635858691196687
n_2 = 82113192811251631639012300385672674439485256963081847790431181633372052788107703751257606763043873164706839243919206719171536710944060815484051324239120708906418093409305166299531826404505861042666985630956832163750255358332156122245372899824101210233079028706971698312018388678352739819636695333269309456613
c_2 = 79145689398302968140315554300835109898158799236562716569497147385375487041207363302776833573990584370222316102267792795080448018216133931915984139305260191001847394275311719986838969706049641052337337102739487620502723651258075501409442088938776353037366614208693030741599888985069155346722608948495955447606

print(max(n_1,n_2,n_0))
M = int(iroot(max(n_1,n_2,n_0),2)[0])
m  = matrix (ZZ,[[M,e_0,e_1,e_2],[0,-n_0,0,0],[0,0,-n_1,0],[0,0,0,-n_2]])
res = m.LLL()[0]
M_d = res[0]
d = M_d//M
print(long_to_bytes(int(pow(c_1,d,n_1))))

equiv

已知

g=n+1c≡gp⋅mnmod  n2hint≡mnmod  n2g = n+1\\\\ c \equiv g^p \cdot m^n \mod n^2 \\\\ hint \equiv m^n \mod n^2

两边同乘以hint的逆

c⋅hint−1≡gpmod  n2gp=(n+1)p=np+⋯+x2n2+x1n+1↓c⋅hint−1−1≡np+⋯+Cp2n2+Cp1nmod  n2c\cdot hint^{-1} \equiv g^p \mod n^2 \\\\ g^p = (n+1)^p = n^p + \cdots +x_2n^2 + x_1n+ 1 \\\\ \downarrow \\\\ c \cdot hint^{-1}-1 \equiv n^p + \cdots +C_p^2n^2 + C_p^1n \mod n^2 

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
c = 286605218507608279202129771918531271946671507626305024953248295895988333961618873954640005595372301341467413016908150677673635722256023730324681401428319225361363999142046537859459409916981367761561114799184280307872980415343132055088498803165594628548662583640326942437149149350520704205500295809038020422457717121048482596636502649958934136981194150511045479471586872164085401140285524759579050155909038507343038174154593337809311866087143093807467622362148641288458960895133762797579445793401378458722430674480127009593346348738518019040387116224822441941294329872991492625964232070720738157400687938977121855098226487473098692442323295021708959030333536870489486659860194145953876253749042832809475881890766076140590935127155677982927543806757574744622901559032730503753795989374828643752328153099868911862925159739950768217245728385503951198131505619930567967616843516131655086992550975654515595211265659201508391208585700785161068709702940719004537390468443797005684611185138008737656926216379855891053354777774384890718888338876478641463885204017543596283159433296917180579907613266788994571545756318342861847715142229441992506185551166325784680848595830171481522613646942120292994260729939968265593422608973270825916828492544664299871676604751187707446221684224968343723624943981363582225792593421766569640376969316119852229910483667108880295374651932751905724421983437967297322892828528208291702056480652221786839830262568767505519035071062740423997398239830057937950769564169367507095190384380175646264585757318362376188860991986875714282394980987037817330032973470671691475171707672675309570489936641877942899184832894395663802575381274953602946158272692789777918695950154965094417582231067265232619858157960243469666284173122639096579318616593605874089448119619113973085646895839523517297934650940122310756350873425553136101151056680013380349701958665772345098953165900722610809127676823000647427841767325888409726931226381361164384623030325151424771900338396699817726437235865324580847369458851938896661773262383710535161134695260264842668565585676477402587141089614009465734740933104864395815815866107368691860801028695310711832807570743906240517911125605062892502417473924306951203772024279670686683490940867837281041052393924435825038108528176083341913995964525020340161586283471200641978840288177413700957210478592481488417240174318458109749698554453042294256932670518004260392417551639031279570625713352666650829725059545911724343454378724048217717
n = 807015319355934202493987023954071180691442715127386148595986388449200843593631520891094615743979153168030088246970989257970036830621595372722242365935754658256884491780092468415223454813183783993676398553548069254772733314464970519010918034665966526528796992899249558868269932526117182999478334998932885861734625397840732588060222643615901190040044859475617233644470461774519430056964173319141176428279982155625854089736620082831368351761689571830301874832695990362570532635666326017747009171284239672618087159628607765587562193376017193347438630870608159409958221148632123956495171209184558432313370763480558881297591947038192493874327977262495215782290404380183097928019655572577604903972837177801283483400031024711029421262352141414871461084620507553601465688029708467032046862475340208057911685819261115507469643577162606815248137862214279429530547740324124486921982160947707402205034973628340358396473783227720251535337643065476806031014509411761770251347925323116560616029982148982791381015296923087790254420668173059307101471872380742666216759717937809906477693759607555341577401757478650571700950789000188537959839639388671274474953016136057290504518082949808954583094636647376750364072532051902803550808546945098876676227557
hint = 459532750394658725058686493080128050567485498823856528912688509796438516683579648745277337790262388672028593267711057916989111557640831058820062117741410593069599247104269636466857739785520028445660106197046918796478992266071240573950265139563799564944217905425555156433042771582428134603844091318831438334623757008672366939414369909308639890615062519731534386648858501674168354428651467824469195462402746921277675354290036653098369822502303799143118750946907039940063166099725237454657376961181554561215282499405930968624659263890131120861248085097028081687484461127813750979900661028213661676736971759082340660747363025795813241012781833110477791643127156253100284569085394772287384996718475275797428239739121684902889449792198311490153362120524401391632890806201025077874324412677620567166513935558833083343851758473486133030423105955359595037622690822082099691750493117919159232598806547754904365390377994617795365886648254587153723397195890181387625152966006790156685482819691532416866417412356137127150081275440943095868545557141372583794798685299639311988517045904231449383147740440319226546278473921805406800033435080809857181761532549753322509920611761856582845868402076990046385975304224881773810882180731755770245521358179684411375690430239118565947846568772212590285434049637476491844692006101639680478553542075252816557019053697313950216290199609188577176850154065359937047788252447606254444436070520230086490619885842829997010377548465166378711563093764692565488785639273342166235346016671168627059966251876683052164020211608550052766677598600491658396651263621639682640551490679617064350440284633798466168268896581397783696151268961607698039266791217122983891032083533786654924904178874531562138194760498109936470632230420389498757174589168611713306405167563248304326998414019122595766707535693246776240623411784820588113535814361065991535557936463316647569521825715949301222670200630918691525065347947877255499283731480427998312860318158543697110569428901661322105704353987895097231873743799575016268850173897276115136193017125407072665600636097187813176632056612018456104111513985713222469163588215669431222357047277130838385703044170854053268883086259844823489876821837415583926984806310612859849504698674215403070693011352981990448490253999232509414225952658279262964174679980213875167780161272931450269390225664108992794140258234522714166712914998667436687292859269092288686741302288065494219978985145670903229550449418226801260723780437472214267

gc = c*inverse(hint,n**2)%n**2
p = (gc-1)//n
q = n//p
phi = (p-1)*(q-1)
d = inverse(n,phi)
print(long_to_bytes(pow(hint,d,n)))

leakDES

不会，问问别的师傅