Rsa
這個 2048 位數是如何快速分解的？
我正在研究CTF。挑戰是在給定密文和 2048 位 RSA 公鑰的情況下獲取加密消息的內容。幾個小時後，我終於拿到了旗幟，但我仍然不確定為什麼第一步會奏效。
第一步 - 將n分解為它的兩個主要因素是據我所知，這不應該是可行的，但它在這個網站上大約 1 秒內完成。為什麼這麼容易？
n =
e = 65537
這個數字很快就被分解了，因為它的因子非常接近，即它的因子為 $ \left(\lfloor\sqrt{n}\rfloor + 70\right)\left(\lfloor\sqrt{n}\rfloor - 68\right) $ .
一些算法，例如Fermat算法，在因子之間越接近效果越好，會立即找到這種分解。