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
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).