Tags: crypto rsa 

Rating: 5.0


Because of the way the `p` and `q` are generated, we realize that possible values `p + q` are limited. This makes factorizing `N` into `p` and `q` feasible.

Since `e` is not known we have to guess it after getting `p` and `q`. Because of the assertion that `exp & (exp + 1) == 0`, the possible values of `e` are limited to the form `2**k - 1`

With limited search space for `p`, `q`, and `e`, we brute force to get the flag!

Full details and implementations are in the notebook on the link.

Original writeup (https://github.com/pberba/ctf-solutions/blob/master/20190810-crytoctf/crypto-159-roxen/roxen-solution.ipynb).