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}
```
