### 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`.
```pythonfrom Crypto.Util.number import long_to_bytes
N = 57996511214023134147551927572747727074259762800050285360155793732008227782157e = 17cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971# factor with cado-nfsp, 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())```