We are given the following code for this task:```#!/usr/bin/sagefrom sage.all import random_primefrom Crypto.Util.number import *
flag = "CENSORED!!!"m = bytes_to_long(flag)e = 65537ROUND = 4
p_0 = Integer(getPrime(2048))print "p_0 = ", p_0print "p_0.nbits() =", p_0.nbits()# p_0.nbits() = 2048
for i in range(ROUND):    p = random_prime(p_0 + 2 ** 669, False, p_0)    q = random_prime(2 ** 1024, False, 2 ** 1023)    n = p * q    c = pow(m, e, n)    print((e, n, c))```and the results of that code. In other words, we have 4 unbalanced RSA modules (one of primes is 2048-bit, another is 1024-bit) where 2048-669 = 1379 most significant bits of the larger prime are the same for all modules but unknown to us.
The literature calls this sort of problem as "implicit factoring", everybody cites the paper _Alexander May and Maike Ritzenhofen. Implicit factoring: On polynomial time factoring given only an implicit hint. In Stanislaw Jarecki and Gene Tsudik, editors, Public Key Cryptography, volume 5443 of Lecture Notes in Computer Science, pages 1–14. Springer, 2009_ as the one who has started all this. It analyzes the case when the _least_ significant bits are shared, so it isn't relevant to our case. For our case, the answer is directly given by _Faugère JC., Marinier R., Renault G. (2010) Implicit Factoring with Shared Most Significant and Middle Bits. In: Nguyen P.Q., Pointcheval D. (eds) Public Key Cryptography – PKC 2010. PKC 2010. Lecture Notes in Computer Science, vol 6056. Springer, Berlin, Heidelberg_. The math is actually not that hard as long as the LLL algorithm is taken as granted: n1=p1\*q1, n2=p2\*q2, where p1-p2 is small; so n1\*q2-n2\*q1=q1\*q2\*(p1-p2) is small (1024+1024+669 bits) relative to n1\*q2 and n2\*q1 (3072+1024 bits each); we need to find q1,q2,q3,q4 such that 6 expressions ni\*qj-nj\*qi (for every i,j) are relatively small and qi themselves are relatively small (otherwise setting qi=ni would trivially make those differences very small); the products of qi and K=2\*\*(1024+669) should have the same order as ni\*qj-nj\*qi, so the final target is a (relatively) short vector (q1\*K,q2\*K,q3\*K,q4\*K,... ni\*qj-nj\*qi ...) which is linear in qi; the LLL algorithm does exactly that.
```# this listing is from SageMath interactive notebookn1=2973274209501776201691519888042319471199570472002963581448442038174303775105245314381574957363420798823459109272033582880093544342097416632789301922536002306527567182062581755622427896176805222031127741901295996406407655159580761870799686589902586048531977772470949726487847609592273113113509360393565486981495691414280115488377036658862455270185918144232474278411028478744709705654418813265142448659819518373755286746077156428562009550423949053466765672350304371480685305236056948120315511581481937808877476017304234481709539887420959566635934196020993167440107233603930680205275988663922482219038154002189670456657490447904915677803635085896488516276652038398387670281017889578744546845516879561935267220220496067322815871953476187719320544305216370338724577613427031660334003670927940108336778128777129814482506102904120782261936405200583575045525662493621014910391546113422892875342648897533678582176837917306298616481373n2=3251902782032245789047244373568418513398699501042390125582854604850409980025770075450715911787445447521622218140215334557095399706072352867343808784990523236458770502408745674483759470273023405191394278952651887691658796200123075893310880484047881686981490079465719251437675137685366637455718736167852758693446054836510298483278836803321808484256895651671009286866206609106195207341954297584749240651733183589964137622276798390574442735236357896976689865537006076691770565982325476739464122514349746931384285281663137634844542581653666782790132692715898744258444677647182810520302200972112293388358388223088570201049829327536931873736003576119203091174357031887835756398363014044213876462726121357257124857714844995939275360401292114685493742117741807725904271233047819844418317309151563996814147674222205025657406854179970261054167763553714096062720190375110424034962653825267605345186966196242170924880263420113533093715233n3=3319581693166965854156546341702871085866516484417065133102957669783301767124305139148241445171965157251584901630940509466918383746093571883915961138469590579904855662075039603814193052482648861790005837152499623628933003722223942748425087238428768644059616855971746263587030015997518015844693570238168960001236591860478015490454825814441652717357954231754190147707664516755381474477091485840498429348559495172163679635558297040958809235154959039890002943586754687708419307944576976342602536633100445400214666233092453616500867884214942494273581939754962360296519390972480570607826327574222675233233204129014053970935585649161741415313714333739158739575683840949478335750767497914631684789124737756077755619214595149000678108003092984694154462094053762230044505613861154667951960453842346217765321466714384322427236290201201749533875696605496322060048560493782437879730028566779588369102443815552624843364723864437585102785841n4=3623027672825570027751905799087856250704364673219621733695608778498876374831468190295671406108813898622110856070362351202666715910157337713651450563139743656276618574488571861325300807768638051262028939850502191925048933459640263459899860587432858065361150546224650437409072567077419033994230255886523594885378258120983525249076049297579507914373981430056882696563001548545648806920587530226042146743848583834214566739577582905827450902524112644006302123901273189894141533305574615678484147600815608055941349174922284976582534946728583640560253903585715415485123700103842858923437775229668552580692343997833070023359560455050458268772296895514484239824212138823140238571743690643212480973800020565951870579891389546329093851128538448181474331412847283334553031842616446827659687270890242373017860663315628129723352199179773131554695072711474852201115894168202572204470148970446464032655855883263323237191326685502550928150611K = 2**(1024+669)M=matrix(ZZ,[    [K,0,0,0,n2,n3,n4,0,0,0],    [0,K,0,0,-n1,0,0,n3,n4,0],    [0,0,K,0,0,-n1,0,-n2,0,n4],    [0,0,0,K,0,0,-n1,0,-n2,-n3]])m=M.LLL()# m[0] should be [q1*K,q2*K,q3*K,q4*K,... qi*qj*(pj-pi) ...], validate[n1%(m[0,0]//K),n2%(m[0,1]//K),n3%(m[0,2]//K),n4%(m[0,3]//K)]# prints [0,0,0,0]p1=abs(m[0,0]//K)q1=n1//p1c1=1916345795411046972738375754819683681926423961399114792801269957801977163440602821055072484406992244815036855918088798499938879791907505191972460922704580149221312157070181525428881682778778310135284898956613383004949065300186549316143621436988329137694532615825599098702201181789276122598515513994795338977977995789035323656172979381490017651005294884962515131736627554492930527900022854579639316928920418329929263046559349572706217880922083227295928053260088769281560143630321922294473582768062401570120887222514628086875048086383584075269304995537313637821427082672614650052048489417189826582021790156211244215713287597531449357470185779377001362125826126061066645860764220869216915972902761526341461419527244572704333420781898107551051196349501951094294927899571823039077487599286047323754104166237131284435653841620198169983977387345450646656267145362264437160529566744868352738337614347580596445231221837741213899194343d1=(65537).inverse_mod((p1-1)*(q1-1))('%x' % pow(c1,d1,n1)).decode('hex')# prints 'IJCTF{I_h4v3_t0_s4y_Im_r34lly_impr3ss3d_w1th_c0mm0n_b1ts!!!!}'```