# RSA Buffet (crypto)
###ENG[PL](#pl-version)
In the task we get a set of 10 4096 bit RSA public keys and 5 ciphertexts processed with some `secretsharing` python module.The goal is to break the public keys and decode ciphertexts.Sadly we got only 5 of the keys, and only 4 of the encrypted the ciphertexts so we got only the first flag (there were two).
The first key we broke was the most obvious one, key number 3:
```e = 228667357288918039245378693853585657521675864952652022596906774862933762099300789254749604425410946822615083373857144528433260602296227303503891476899519658402024054958055003935382417495158976039669297102085384069060239103495133686397751308534862740272246002793830176686556622100583797028989159199545629609021240950860918369384255679720982737996963877876422696229673990362117541638946439467137750365479594663480748942805548680674029992842755607231111749435902398183446860414264511210472086370327093252168733191324465379223167108867795127182838092986436559312004954839317032041477453391803727162991479936070518984824373880381139279500094875244634092093215146125326800209962084766610206048422344237134106891516381979347888453395909395872511361844386280383251556028219600028715738105327585286564058975370316649206938752448895524147428799966328319661372247669163998623995646371176483786757036960204837994662752770358964913870689131473714797550537422931003343433377469029232185552979648755665051117443571002017829146470221483652014417043043920340602378994630507647460734411326405049128160906832664174206633659153486878241903912874200129515570971220983561054906106575556061388168231915057339795246395626504771079756241685975773086049021119L
n = 625370676793301609007636145380331611237919351425496690404114180302249419719867435237342547950459491394834137179033102621573611784738388518952362848787237787440594300323769334356435131992521522997795029079251912507591819194229112877831181987001350385569134107880067429777572352378951587000987749447829255561035861423897841083194636994924140527822677164175006590642236546332030533920247393734145161727026178314748349757632676858997648848951518713836001935694487214337663667186794458714595706552931844195313593265852623091839910783970211228963728395962479544383117833611165858148867888664339695901377282163112482988096747232893295750676690941568494463290730116247822838421828649339437010788165430710512903632914670529270528098439859718986580569781164710102583602429563649626238817198851752150256839194761250249327990903746851390967504209752042479527523791824857674302720147951681393130861129469956962513163744166621211214770096232423058352324863327706013479610785632814580681502127018494520155709115651059545236646813027941576086510607434365502848385373510684649855795155224752033959337914546058251330474025320961186763814554194220596151399428277009154211720727770696506865214610059620204055226083684833160528072571967096188932684068843L```
It was obvious because with such high `e` we can run Wiener attack and recover the private key:
```sagec_fracs = continued_fraction(e/n).convergents()test_message = 42test_message_encrypted = pow(test_message,e,n)d = 0for i in xrange(len(c_fracs)):	if pow(test_message_encrypted,c_fracs[i].denom(),n) == test_message:		d = c_fracs[i].denom()		breakprint(d)```
The next key we got was directly from factordb:  http://factordb.com/index.php?query=549100898763808112064590568096509639806005267015788479836998648112330729762142760306265813195181231930171220686827142359040315653020182064933039077953579528749272321744478656324986362155106653831095037724728643255316641716947998245610175805278242802144980117927688674393383290354985820646326870614197414534217177211618710501438340081867982883181358830449072661742417246835970022211465130756382481343160426921258769780282358703413114522476037306476452786236456339806564839822630841425055758411765631749632457527073092742671445828538125416154242015006557099276782924659662805070769995499831691512789480191593818008294274869515824359702140052678892212293539574359134092465336347101950176544334845468112561615253963771393076343090247719105323352711194948081670662350809687853687199699436636944300210595489981211181100443706510898137733979941302306471697516217631493070094434891637922047009630278889176140288479340611479190580909389486067761958499091506601085734094801729179308537628951345012578144960250844126260353636619225347430788141190654302935255862518781845236444151680147886477815759103864509989480675169631226254252762579781553994364555800120817100328166428687776427164098803076677481602221304265962340500651339469391627432175447
This instantly gives us `p` and `q`.
Another two keys gets broken with `common factor` approach - two modulus share the same prime so by calculating `gcd(n1,n2)` for each moduli pair we can get the common factor.
```pythonfor n1 in moduli:  for n2 in moduli:      p = gcd(n1,n2)      if n1!=n2 and p!=1:	      print(n1,n2,p)```
The last key we got was from Fermat Fatorization - the primes `p` and `q` were both very close to `sqrt(n)`:
```pythondef fermat_factors(n):    assert n % 2 != 0    a = gmpy2.isqrt(n)    b2 = gmpy2.square(a) - n    while not gmpy2.is_square(b2):        a += 1        b2 = gmpy2.square(a) - n    factor1 = a + gmpy2.isqrt(b2)    factor2 = a - gmpy2.isqrt(b2)    print(n, factor1, factor2)    return int(factor1), int(factor2)```
Now with those recovered private keys we can proceed with decrypting the ciphertexts:
```pythondef decrypt(private_key, ciphertext):    """Decrypt a message with a given private key.     Takes in a private_key generated by Crypto.PublicKey.RSA, which must be of    size exactly 4096     If the ciphertext is invalid, return None    """    if len(ciphertext) < 512 + 16:        return None    msg_header = ciphertext[:512]    msg_iv = ciphertext[512:512 + 16]    msg_body = ciphertext[512 + 16:]    try:        symmetric_key = PKCS1_OAEP.new(private_key).decrypt(msg_header)    except ValueError as e:        print(e)        return None    if len(symmetric_key) != 32:        return None    return AES.new(symmetric_key, mode=AES.MODE_CFB, IV=msg_iv).decrypt(msg_body)
 def get_d(n, p, e):    from crypto_commons.rsa.rsa_commons import modinv, get_fi_distinct_primes    phi = get_fi_distinct_primes([p, n / p])    return modinv(e, phi)
 def decode_i(d, e, n, i):    private_key = RSA.construct((n, e, d))    with codecs.open("ct/ciphertext-" + str(i) + ".bin") as ct_file:        data = ct_file.read()        decrypted = decrypt(private_key, data)        print(decrypted)```
From this we get list of messages for secretsharing:
```pythondef recover_flag(msgs):    print(PlaintextToHexSecretSharer.recover_secret(msgs))
def print_results():    msgs = [        '1-32a1cd9f414f14cff6685879444acbe41e5dba6574a072cace6e8d0eb338ad64910897369b7589e6a408c861c8e708f60fbbbe91953d4a73bcf1df11e1ecaa2885bed1e5a772bfed42d776a9',        '1-e0c113fa1ebea9318dd413bf28308707fd660a5d1417fbc7da72416c8baaa5bf628f11c660dcee518134353e6ff8d37c',        '1-1b8b6c4e3145a96b1b0031f63521c8df58713c4d6d737039b0f1c0750e16e1579340cfc5dadef4e96d6b95ecf89f52b8136ae657c9c32e96bf4384e18bd8190546ff5102cd006be5e1580053',        '1-c332b8b93a914532a2dab045ea52b86d4d3950a990b5fc5e041dce9be1fd3912f9978cad009320e18f4383ca71d9d79114c9816b5f950305a6dd19c9f458695d52',        '3-17e568ddc3ed3e6fe330ca47a2b27a2707edd0e0839df59fe9114fe6c08c6fc1ac1c3c8d9ab3cf7860dac103dff464d4c215e197b54f0cb46993912c3d0220a3eb1b80adf33ee2cc59b0372c',        '3-b69efb4f9c5205175a4c9afb9d3c7bef728d9fb6c9cc1241411b31d4bd18744660391a330cefa8a86af8d2b80c881cfa',        '3-572e70c5acfbe8b4c2cbd47217477d217da88c256ff2586af6a18391972c258bbea6143e7cd2ff6d39393efeb64d51d9318a2c337e50e2d764a42173bc3a1d5c7c8f24b64043daf5d2a8e9f4',        '3-e9e6850880eb0a44d36fe9f2e5a458c6da3977b7fcd285afa27e9bfc116b1408570991504116b81864b03a7060bfd5d3fb6e007bb346f276d749befd545d1489c4',        '4-4a87367d053c533fd995032ed1e651487cb5dc1e0b1cb70a7662b152c73650f039a60f391a52f2413f43bd54eb7b12c41b42f31ac557edd4bfe46a396a8cdbe19dc9d8121924f43be51c976d',        '4-abbbcee71f140198ff8c50f51069465075979c31d32b052e7ae82ec7f6783aef7b41a597f9504d3340967b8d70cbe5a3',        '4-35fbbe40058e20463547b363d1f164c0bbbb97cfd9ffe7619bce31a59392f0e9625a2cd035276e09c4df3c0932f22bd322f16e375c7c7fd88da0f972832707eb549ff1e776db37649019ebce',        '4-12b466934911986bda845d8d26710a12250d210546f46716c78d7a17b1f2c893b95b934c8c7beafcf81a3123eb2ea05ca89101b23349e455794a8d56608c8ee49dd',        '5-7d29041c468b680fcff93c16011a2869f17de75b929b787503b412becde0321ec72fe1e499f2150a1dacb9a5f701c0b37470049dd560cef5163543469817971f50782f763f0b05ab7088f7ae',        '5-a7a1e271cf263279cece532b540545fa539b0f3650e2929163b02ee5459debdc53c1e07149eb2153015bb5c88e6270e8',        '5-149480c5c75cbe320564adfa432ac8ea241e048ed39c8bc6be14ca80c392487f43a7882075d785d62cb314ea6c89a6b5f28adfa56ec481e124567b88241de2a6cabcc7ec9de3acac8be5375b',        '5-7285289084282d559573f68eef10191091d76d6670014202670651f867cd2bc8640a86eef1c1e482affc7ae801fa446956c2186972fb6b7bac88c91d050c9d3cca'    ]    recover_flag(msgs[::4])    recover_flag(msgs[1::4])    recover_flag(msgs[2::4])    recover_flag(msgs[3::4])    recover_flag(msgs[4::4])```
And from this code we get:
```And another one's down, and another one's down, and another one bites the dust!
Three's the magic number!  FLAG{ndQzjRpnSP60NgWET6jX}
Pssst--- can you keep a secret?  If you get all five plaintexts, there's another flag :)
1./2J6|M{g!;L	oJx''`z.uOzEM	)g1'-:tUx%<HE7jWoi	9#q_ZUq_:+u9?]]y/*|5ch>Ee!mGj*MAnd another one's down, and another one's down, and another one bites the dust!```
So sadly only 4 out of 5 plaintexts and only one flag `FLAG{ndQzjRpnSP60NgWET6jX}`
###PL version
W zadaniu dostajemy 10 4096 bitowych kluczy publicznych RSA oraz 5 szyfrogramów przetworzonych dodatkowo przez specjalną bibliotekę `secretsharing`.Celem jest złamanie kluczy publicznych i odzyskanie wiadomości.Niestety udało nam się złamać tylko 5 kluczy i odszyfrować 4 teksty, więc zdobyliśmy tylko jedną flagę (były dwie).Pierwszy złamany klucz był najbardziej oczywisty:
```e = 228667357288918039245378693853585657521675864952652022596906774862933762099300789254749604425410946822615083373857144528433260602296227303503891476899519658402024054958055003935382417495158976039669297102085384069060239103495133686397751308534862740272246002793830176686556622100583797028989159199545629609021240950860918369384255679720982737996963877876422696229673990362117541638946439467137750365479594663480748942805548680674029992842755607231111749435902398183446860414264511210472086370327093252168733191324465379223167108867795127182838092986436559312004954839317032041477453391803727162991479936070518984824373880381139279500094875244634092093215146125326800209962084766610206048422344237134106891516381979347888453395909395872511361844386280383251556028219600028715738105327585286564058975370316649206938752448895524147428799966328319661372247669163998623995646371176483786757036960204837994662752770358964913870689131473714797550537422931003343433377469029232185552979648755665051117443571002017829146470221483652014417043043920340602378994630507647460734411326405049128160906832664174206633659153486878241903912874200129515570971220983561054906106575556061388168231915057339795246395626504771079756241685975773086049021119L
n = 625370676793301609007636145380331611237919351425496690404114180302249419719867435237342547950459491394834137179033102621573611784738388518952362848787237787440594300323769334356435131992521522997795029079251912507591819194229112877831181987001350385569134107880067429777572352378951587000987749447829255561035861423897841083194636994924140527822677164175006590642236546332030533920247393734145161727026178314748349757632676858997648848951518713836001935694487214337663667186794458714595706552931844195313593265852623091839910783970211228963728395962479544383117833611165858148867888664339695901377282163112482988096747232893295750676690941568494463290730116247822838421828649339437010788165430710512903632914670529270528098439859718986580569781164710102583602429563649626238817198851752150256839194761250249327990903746851390967504209752042479527523791824857674302720147951681393130861129469956962513163744166621211214770096232423058352324863327706013479610785632814580681502127018494520155709115651059545236646813027941576086510607434365502848385373510684649855795155224752033959337914546058251330474025320961186763814554194220596151399428277009154211720727770696506865214610059620204055226083684833160528072571967096188932684068843L```
Przy tak dużym `e` jasnym było, ze można użyć ataku Wienera:
```sagec_fracs = continued_fraction(e/n).convergents()test_message = 42test_message_encrypted = pow(test_message,e,n)d = 0for i in xrange(len(c_fracs)):	if pow(test_message_encrypted,c_fracs[i].denom(),n) == test_message:		d = c_fracs[i].denom()		breakprint(d)```
Kolejny klucz dostajemy bezpośrednio z factordb: http://factordb.com/index.php?query=549100898763808112064590568096509639806005267015788479836998648112330729762142760306265813195181231930171220686827142359040315653020182064933039077953579528749272321744478656324986362155106653831095037724728643255316641716947998245610175805278242802144980117927688674393383290354985820646326870614197414534217177211618710501438340081867982883181358830449072661742417246835970022211465130756382481343160426921258769780282358703413114522476037306476452786236456339806564839822630841425055758411765631749632457527073092742671445828538125416154242015006557099276782924659662805070769995499831691512789480191593818008294274869515824359702140052678892212293539574359134092465336347101950176544334845468112561615253963771393076343090247719105323352711194948081670662350809687853687199699436636944300210595489981211181100443706510898137733979941302306471697516217631493070094434891637922047009630278889176140288479340611479190580909389486067761958499091506601085734094801729179308537628951345012578144960250844126260353636619225347430788141190654302935255862518781845236444151680147886477815759103864509989480675169631226254252762579781553994364555800120817100328166428687776427164098803076677481602221304265962340500651339469391627432175447
Co od razu daje nam `p` oraz `q`.
Kolejne dwa klucze zostają złamane ponieważ współdzielą czynnik pierwszy i można go odzyskać wylicząc gcd dla każdej pary modulusów.
```pythonfor n1 in moduli:  for n2 in moduli:      p = gcd(n1,n2)      if n1!=n2 and p!=1:	      print(n1,n2,p)```
Ostatni klucz padł przez faktoryzacje Fermata - liczby `p` oraz `q` były bardzo blisko `sqrt(n)`.
```pythondef fermat_factors(n):    assert n % 2 != 0    a = gmpy2.isqrt(n)    b2 = gmpy2.square(a) - n    while not gmpy2.is_square(b2):        a += 1        b2 = gmpy2.square(a) - n    factor1 = a + gmpy2.isqrt(b2)    factor2 = a - gmpy2.isqrt(b2)    print(n, factor1, factor2)    return int(factor1), int(factor2)```
Z tak odzyskanymi kluczami możemy zdekodować szyfrogramy:
```pythondef decrypt(private_key, ciphertext):    """Decrypt a message with a given private key.     Takes in a private_key generated by Crypto.PublicKey.RSA, which must be of    size exactly 4096     If the ciphertext is invalid, return None    """    if len(ciphertext) < 512 + 16:        return None    msg_header = ciphertext[:512]    msg_iv = ciphertext[512:512 + 16]    msg_body = ciphertext[512 + 16:]    try:        symmetric_key = PKCS1_OAEP.new(private_key).decrypt(msg_header)    except ValueError as e:        print(e)        return None    if len(symmetric_key) != 32:        return None    return AES.new(symmetric_key, mode=AES.MODE_CFB, IV=msg_iv).decrypt(msg_body)
 def get_d(n, p, e):    from crypto_commons.rsa.rsa_commons import modinv, get_fi_distinct_primes    phi = get_fi_distinct_primes([p, n / p])    return modinv(e, phi)
 def decode_i(d, e, n, i):    private_key = RSA.construct((n, e, d))    with codecs.open("ct/ciphertext-" + str(i) + ".bin") as ct_file:        data = ct_file.read()        decrypted = decrypt(private_key, data)        print(decrypted)```
W ten sposób dostajemy listę danych dla `secretsharing`:
```pythondef recover_flag(msgs):    print(PlaintextToHexSecretSharer.recover_secret(msgs))
def print_results():    msgs = [        '1-32a1cd9f414f14cff6685879444acbe41e5dba6574a072cace6e8d0eb338ad64910897369b7589e6a408c861c8e708f60fbbbe91953d4a73bcf1df11e1ecaa2885bed1e5a772bfed42d776a9',        '1-e0c113fa1ebea9318dd413bf28308707fd660a5d1417fbc7da72416c8baaa5bf628f11c660dcee518134353e6ff8d37c',        '1-1b8b6c4e3145a96b1b0031f63521c8df58713c4d6d737039b0f1c0750e16e1579340cfc5dadef4e96d6b95ecf89f52b8136ae657c9c32e96bf4384e18bd8190546ff5102cd006be5e1580053',        '1-c332b8b93a914532a2dab045ea52b86d4d3950a990b5fc5e041dce9be1fd3912f9978cad009320e18f4383ca71d9d79114c9816b5f950305a6dd19c9f458695d52',        '3-17e568ddc3ed3e6fe330ca47a2b27a2707edd0e0839df59fe9114fe6c08c6fc1ac1c3c8d9ab3cf7860dac103dff464d4c215e197b54f0cb46993912c3d0220a3eb1b80adf33ee2cc59b0372c',        '3-b69efb4f9c5205175a4c9afb9d3c7bef728d9fb6c9cc1241411b31d4bd18744660391a330cefa8a86af8d2b80c881cfa',        '3-572e70c5acfbe8b4c2cbd47217477d217da88c256ff2586af6a18391972c258bbea6143e7cd2ff6d39393efeb64d51d9318a2c337e50e2d764a42173bc3a1d5c7c8f24b64043daf5d2a8e9f4',        '3-e9e6850880eb0a44d36fe9f2e5a458c6da3977b7fcd285afa27e9bfc116b1408570991504116b81864b03a7060bfd5d3fb6e007bb346f276d749befd545d1489c4',        '4-4a87367d053c533fd995032ed1e651487cb5dc1e0b1cb70a7662b152c73650f039a60f391a52f2413f43bd54eb7b12c41b42f31ac557edd4bfe46a396a8cdbe19dc9d8121924f43be51c976d',        '4-abbbcee71f140198ff8c50f51069465075979c31d32b052e7ae82ec7f6783aef7b41a597f9504d3340967b8d70cbe5a3',        '4-35fbbe40058e20463547b363d1f164c0bbbb97cfd9ffe7619bce31a59392f0e9625a2cd035276e09c4df3c0932f22bd322f16e375c7c7fd88da0f972832707eb549ff1e776db37649019ebce',        '4-12b466934911986bda845d8d26710a12250d210546f46716c78d7a17b1f2c893b95b934c8c7beafcf81a3123eb2ea05ca89101b23349e455794a8d56608c8ee49dd',        '5-7d29041c468b680fcff93c16011a2869f17de75b929b787503b412becde0321ec72fe1e499f2150a1dacb9a5f701c0b37470049dd560cef5163543469817971f50782f763f0b05ab7088f7ae',        '5-a7a1e271cf263279cece532b540545fa539b0f3650e2929163b02ee5459debdc53c1e07149eb2153015bb5c88e6270e8',        '5-149480c5c75cbe320564adfa432ac8ea241e048ed39c8bc6be14ca80c392487f43a7882075d785d62cb314ea6c89a6b5f28adfa56ec481e124567b88241de2a6cabcc7ec9de3acac8be5375b',        '5-7285289084282d559573f68eef10191091d76d6670014202670651f867cd2bc8640a86eef1c1e482affc7ae801fa446956c2186972fb6b7bac88c91d050c9d3cca'    ]    recover_flag(msgs[::4])    recover_flag(msgs[1::4])    recover_flag(msgs[2::4])    recover_flag(msgs[3::4])    recover_flag(msgs[4::4])```
A za pomocą tego kodu dostajemy:
```And another one's down, and another one's down, and another one bites the dust!
Three's the magic number!  FLAG{ndQzjRpnSP60NgWET6jX}
Pssst--- can you keep a secret?  If you get all five plaintexts, there's another flag :)
1./2J6|M{g!;L	oJx''`z.uOzEM	)g1'-:tUx%<HE7jWoi	9#q_ZUq_:+u9?]]y/*|5ch>Ee!mGj*MAnd another one's down, and another one's down, and another one bites the dust!```
Więc niestety tylko 4 z 5 tekstów i tylko jedna flaga `FLAG{ndQzjRpnSP60NgWET6jX}`