Volga CTF Quals 2013 - Crypto 200 - [Team xbios]

Description:
You've managed to intercept two transmissions from other space ships Ð each contains a password-protected archive and a ciphertext. They look like packages from the server that corrects autopilot configuration settings to avoid space garbage. Unfortunately, you can't communicate with this server. Apparently, both ciphertexts are actually the same message encrypted with different RSA public keys. As for the message, it might be the key for archive. Knowing the source of both transmissions, you do have public keys that might be used to encrypt the archive key. Is it possible to get the content of the archive? You will get the space junk out of your way!

We have the following data:

Public Key 1 
(e1, n) = (599703852157208324988436697659896404638315905290324375700570316485421693, 108039548283467910018636019706918049787296862983920390620425680109149061265582938100265640505395436176923520902062289606379329490555998996693285930619495040456388113166495283026905991110314710632437395833112529488024010984327573108928719840003018232385552027586272040584786259207191357206321725581066222359269709853312236804681275337051689984480610347322381805920314518020927280061535012383180989715215061621017100281215170089223279840979641688194933238176625422507335413025975742216947757245112001827202742177202602339368271393570814426349)

Cipher text 1
64192679490201084919864109589711225051306895753052452251471181011935890793544442381990900483806859201269602393008215002967277584404244028747557515652983421402831933955031514949051711613799413945375516057965907322753883557356486350981432321137639633448144656731569958858836168965404795837648422955123798171558220417018614361054908596961274183141350877544714255973182298022152382603068819975693640211216195897799698027064327186095742305485491820097943409724898378023689276832524319007493796910829806469346146322827201567159126666629388322479

Public Key 2
(e2, n) = (2021187385200166516022746434619391941987919206967476592818217288363509, 108039548283467910018636019706918049787296862983920390620425680109149061265582938100265640505395436176923520902062289606379329490555998996693285930619495040456388113166495283026905991110314710632437395833112529488024010984327573108928719840003018232385552027586272040584786259207191357206321725581066222359269709853312236804681275337051689984480610347322381805920314518020927280061535012383180989715215061621017100281215170089223279840979641688194933238176625422507335413025975742216947757245112001827202742177202602339368271393570814426349)

Cipher text 2
59479689549560080704719346207028172045832447629676482962810835773815464251268645222410752554301728769639790100177113106905240622051153394111672911715955043318248120741697967901541458159847100613910368380426590912304442624789475183028091060736577136778183984119998489277854012692016578461901960239232919085733417338853775102362931632001858570236887517967863584958729992234586883928904928030598648389127230808653922583812124081813290524003879897252243176409322823308176329788244775196386356286749265723818517581499920415831945106137632995322

We can notice that same value of 'n' is used in both cases and the message is also the same. So we can break this using RSA common modulus attack. This is what the attack says:

[*] e1 and e2 are relatively prime ie. gcd(e1, e2) == 1
[*] By the Extended Euclidean Algorithm, a*e1 + b*e2 == gcd(e1, e2)
[*] Let C1 and C2 be the cipher texts of message m

C1 = m^e1 mod n
C2 = m^e2 mod n 

C1^a * C2^b == (m^e1)^a * (m^e2)^b mod n
C1^a * C2^b == m^(a*e1 + b*e2) mod n
C1^a * C2^b == m mod n

Since a is negative, we compute
(C1^-1)^a * C2^b == m mod n

Ok, now lets use sage to do these computations

sage: e1 = 599703852157208324988436697659896404638315905290324375700570316485421693
sage: e2 = 2021187385200166516022746434619391941987919206967476592818217288363509
sage: n = 108039548283467910018636019706918049787296862983920390620425680109149061265582938100265640505395436176923520902062289606379329490555998996693285930619495040456388113166495283026905991110314710632437395833112529488024010984327573108928719840003018232385552027586272040584786259207191357206321725581066222359269709853312236804681275337051689984480610347322381805920314518020927280061535012383180989715215061621017100281215170089223279840979641688194933238176625422507335413025975742216947757245112001827202742177202602339368271393570814426349
sage: cipher1 = 64192679490201084919864109589711225051306895753052452251471181011935890793544442381990900483806859201269602393008215002967277584404244028747557515652983421402831933955031514949051711613799413945375516057965907322753883557356486350981432321137639633448144656731569958858836168965404795837648422955123798171558220417018614361054908596961274183141350877544714255973182298022152382603068819975693640211216195897799698027064327186095742305485491820097943409724898378023689276832524319007493796910829806469346146322827201567159126666629388322479
sage: cipher2 = 59479689549560080704719346207028172045832447629676482962810835773815464251268645222410752554301728769639790100177113106905240622051153394111672911715955043318248120741697967901541458159847100613910368380426590912304442624789475183028091060736577136778183984119998489277854012692016578461901960239232919085733417338853775102362931632001858570236887517967863584958729992234586883928904928030598648389127230808653922583812124081813290524003879897252243176409322823308176329788244775196386356286749265723818517581499920415831945106137632995322

sage: gcd(e1, e2)  # Relatively prime
1
sage: val = xgcd(e1, e2) # Extended Euclidean Algorithm
sage: val
(1, -3047508293327982779161516622450839163404526801300587435875399397355, 904222179681195587324531859318948099549580203141997568283661184044224)
sage: a = -val[1]
sage: a
3047508293327982779161516622450839163404526801300587435875399397355
sage: b = val[2]
sage: b
904222179681195587324531859318948099549580203141997568283661184044224
sage: cipher1_inv = inverse_mod(cipher1, n) # Multiplicative inverse
sage: cipher1_inv
49882118660580323132467117552276128300614229858832013404741331714334503133649474000400824741560286993474795185146741270220095396126691006446586108884217265900328937680293201118674476028108395000917327921867599979692111002779827647440384347225473157540218799037461665550199440995365907179136646940841772015473789593113023235321359849036424451006123980720306616883939654926239630666201750535887553205856794969495851564203306735787871522626375210178147364523182997655961822887981171722156045438928862532799694071412437194525903453048230129583

sage: c1a = Mod(cipher1_inv, n) ^ a # Square and Multiply algorithm
sage: c1a
41469201017671525980368839429837195396084994817924814990774939845326361705647744310093150006053943147640059339296841399913504561282912441493855262177235335163582510545748763113210275652403002725065333196077070355270576200547613273450470814161561912356462838553050343438059422947380358064075951153983513248335264919975924161127571537532543369398463333064729421949754686699997006195940667044423272156385649336229018660142717513039952955141634801106594451630692732900999746770594155899945113543988204102612492489906092084186526076794329828855
sage: c2b = Mod(cipher2, n) ^ b
sage: c2b
28572464787303927433139480688120103799450333993942770377763568953906568621027391472843696689996459445428095360778023546317751548897270315411496636052798098326232273297351844385991588487531221292119364884784693807035802310520348076486338510106043448492709653411110192210391119474114040490261049642643699360158053381341387211041514755333117982148513726627125367488864516664957365575090594728178808919916448298474482486390692427228381759924160007325779183789864908736476522756356374167807501269961385802206964229596780285088364964068284094380
sage: (c1a * c2b) % n
4561387865153841354984687512687489546516849543684654468465495143548954351686168165161

So the message is:
4561387865153841354984687512687489546516849543684654468465495143548954351686168165161

Using the message as password, open the compressed 7z file. We get the corrections.json file, which reads

{
   "server": "AN4-SEE23",
   "clientid": "1WSS-431222-2334-5666",
   "config": {
       "j-base": "+56.661",
       "values": "12889.557; 1333.127; LW; E21; -12.178"
   }
}

The flag for the challenge is : 12889.557; 1333.127; LW; E21; -12.178