Rating: 5.0

### crypto/baby-rsa

256-bit RSA where $e^2 | p-1, q-1$.

Intended solution = factor $N$ with cado-nfs, then use sage's `nth_root()` function to get all candidate decryptions. Finally, combine using Chinese Remainder Theorem.

The `nth_root()` algorithm is [described in this paper](https://dl.acm.org/doi/abs/10.5555/314500.315094). It's simple for $e | p-1$, but for higher-powers of $e$ involves solving a (small) discrete logarithm problem. Fortunately, sage has it implemented as a built-in.

Many resources online describe how to proceed if `e | p-1`, but they don't describe the general case for higher powers of `e`.

```python

from Crypto.Util.number import long_to_bytes

N = 57996511214023134147551927572747727074259762800050285360155793732008227782157

e = 17

cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971

# factor with cado-nfs

p, q = 172036442175296373253148927105725488217, 337117592532677714973555912658569668821

assert p * q == N

p_roots = mod(cipher, p).nth_root(e, all=True)

q_roots = mod(cipher, q).nth_root(e, all=True)

for xp in p_roots:

for xq in q_roots:

x = crt([Integer(xp), Integer(xq)], [p,q])

x = int(x)

flag = long_to_bytes(x)

if flag.startswith(b"dice"):

print(flag.decode())

```

Original writeup (https://hackmd.io/fmdfFQ2iS6yoVpbR3KCiqQ?view#cryptobaby-rsa).