# 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:

```sage
c_fracs = continued_fraction(e/n).convergents()
test_message = 42
test_message_encrypted = pow(test_message,e,n)
d = 0
for i in xrange(len(c_fracs)):
if pow(test_message_encrypted,c_fracs[i].denom(),n) == test_message:
d = c_fracs[i].denom()
break
print(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.

```python
for 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)`:

```python
def 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:

```python
def 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:

```python
def 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'-:t
Ux%<HE7jWoi 9#q_ZUq_:+u9?]]y/*|5ch>Ee!mGj*M
And 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:

```sage
c_fracs = continued_fraction(e/n).convergents()
test_message = 42
test_message_encrypted = pow(test_message,e,n)
d = 0
for i in xrange(len(c_fracs)):
if pow(test_message_encrypted,c_fracs[i].denom(),n) == test_message:
d = c_fracs[i].denom()
break
print(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.

```python
for 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)`.

```python
def 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:

```python
def 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`:

```python
def 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'-:t
Ux%<HE7jWoi 9#q_ZUq_:+u9?]]y/*|5ch>Ee!mGj*M
And 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}`

Original writeup (https://github.com/p4-team/ctf/tree/master/2017-02-25-bkp/rsa_buffet).