Tags: crypto boneh-durfee rsa 

Rating:

# Bon Appetit
```
Wow, look at the size of that! There is just so much to eat!

Download the file below.
```
[prompt.txt](prompt.txt)

Look in the `prompt.txt` is obviously a **RSA crypto challenge**
```py
n = 86431753033855985150102208955150746586984567379198773779001331665367046453352820308880271669822455250275431988006538670370772552305524017849991185913742092236107854495476674896994207609393292792117921602704960758666683584350417558805524933062668049116636465650763347823718120563639928978056322149710777096619

e = 43593315545590924566741189956390609253174017258933397294791907025439424425774036889638411588405163282027748339397612059157433970580764560513322386317250465583343254411506953895016705520492303066099891805233630388103484393657354623514864187319578938539051552967682959449373268200012558801313113531016410903723

c = 6017385445033775122298094219645257172271491520435372858165807340335108272067850311951631832540055908237902072239439990174700038153658826905580623598761388867106266417340542206012950531616502674237610428277052393911078615817819668756516229271606749753721145798023983027473008670407713937202613809743778378902
```
Look at the size of public key (e) is very large, and the challenge title

It seems like vulnerable to **Boneh Durfee Attack**

The script for Boneh Durfee I use is in this [github](https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage)

Because the sage uses Python3 so I need to edit some print statement

And I run it at this [Sage online website](https://sagecell.sagemath.org/)

Then I change the `N` and `e` variable:
```py
# the modulus
N = 86431753033855985150102208955150746586984567379198773779001331665367046453352820308880271669822455250275431988006538670370772552305524017849991185913742092236107854495476674896994207609393292792117921602704960758666683584350417558805524933062668049116636465650763347823718120563639928978056322149710777096619
# the public exponent
e = 43593315545590924566741189956390609253174017258933397294791907025439424425774036889638411588405163282027748339397612059157433970580764560513322386317250465583343254411506953895016705520492303066099891805233630388103484393657354623514864187319578938539051552967682959449373268200012558801313113531016410903723
```
Then click the `Evaluate` Button

Unfortunately, no solution found:
```
Share
=== checking values ===
* delta: 0.180000000000000
* delta < 0.292 True
* size of e: 1021
* size of N: 1022
* m: 4 , t: 2
=== running algorithm ===
* removing unhelpful vector 0
6 / 18 vectors are not helpful
det(L) < e^(m*n) (good! If a solution exists < N^delta, it )will be found
...
...
optimizing basis of the lattice via LLL, this can take a long time
LLL is done!
looking for independent vectors in the lattice
found them, using vectors 0 and 1
Your prediction (delta) is too small
=== no solution was found ===
=== 0.2721996307373047 seconds ===
```

Then I try increase the value of `delta` and `m`

And I get a solution!

When `delta = .23` and `m = 7`:
```
Share
=== checking values ===
* delta: 0.230000000000000
* delta < 0.292 True
* size of e: 1021
* size of N: 1022
* m: 7 , t: 3
=== running algorithm ===
* removing unhelpful vector 0
16 / 47 vectors are not helpful
det(L) < e^(m*n) (good! If a solution exists < N^delta, it )will be found
...
...
optimizing basis of the lattice via LLL, this can take a long time
LLL is done!
looking for independent vectors in the lattice
found them, using vectors 0 and 1
=== solution found ===
private key found: 5448511435693918250863484721514292687178096328572373396537572878464059764348289027
=== 8.640573978424072 seconds ===
```
Then I can calculate the plaintext using private key (d):
```py
from Crypto.Util.number import *
n = 86431753033855985150102208955150746586984567379198773779001331665367046453352820308880271669822455250275431988006538670370772552305524017849991185913742092236107854495476674896994207609393292792117921602704960758666683584350417558805524933062668049116636465650763347823718120563639928978056322149710777096619
e = 43593315545590924566741189956390609253174017258933397294791907025439424425774036889638411588405163282027748339397612059157433970580764560513322386317250465583343254411506953895016705520492303066099891805233630388103484393657354623514864187319578938539051552967682959449373268200012558801313113531016410903723
c = 6017385445033775122298094219645257172271491520435372858165807340335108272067850311951631832540055908237902072239439990174700038153658826905580623598761388867106266417340542206012950531616502674237610428277052393911078615817819668756516229271606749753721145798023983027473008670407713937202613809743778378902
d = 5448511435693918250863484721514292687178096328572373396537572878464059764348289027

print(long_to_bytes(pow(c,d,n)))
```
[Sage script](solve.sage)

[Python script](solve.sage)

Thats the flag!!!

## Flag
```
flag{bon_appetit_that_was_one_big_meal}
```

Original writeup (https://github.com/Hong5489/HacktivityCTF/tree/master/bon_appetit).