Tokyo Westerns CTF 2017 Crypto91: BabyRSA Writeup

題目給定了一組 RSA 公鑰 \((n, e)\) 和用其加密的一個密文 \(c\)。同時,作者也提供了加密的 ruby script。明眼人一看就知道那段 script 才是重點:

這裡生成的質數 \(p, q\) 有一點特別:\(p < 2^{1024}\),\(q < 19p + 2^{512}\)。

如果設 \(q = 19p + r\) (\(r<2^{512}\)),則 \(n = p(19p + r)\)。這是 \(p\) 的二次方程;它的解是 $$\frac{-r \pm \sqrt{r^2 + 76n}}{38}$$

那 \(r\) 是什麼?不知道,但是 \(r^2 + 76n\) 會是一個平方數。

因此我們再設 \(m^2 = r^2 + 76n\),由於 \(76n < m^2 < 76n + 2^{1024}\),我們可以找到 \(m\) 的值,繼而找到 \(r\),再得到 \(p\)。

利用上述代碼,得出 flag: TWCTF{secretly_cherry-blossom-viewing}


發表迴響