AIS3 2019 - RSA101 (Crypto, 290)

Challenge

連線過去會拿到 RSA pubkey (N,e),與一個 Phi oracle

你可以輸入任意數字,他會回傳 ((你傳的數字 n) % phi ) % 64


Solution

如果輸入比 phiphi 大的一個 2 的 nn 次方,會回傳一個 (2n mod phi ) mod 64(2^{n}\ mod\ phi\ ) \ mod\ 64 的數(不為零)

如果輸入了比 phiphi 小的一個 2 的 nn 次方,則會被 64 整除,並回傳 0

因此我們可以用類似 binary search 的方法,找出 phi 來解開 Flag 的 RSA 加密。

AIS3{RSA_L0L_01100110011101010110001101101011}

Server : task.py

solve.py