Factoring with MSB of p

| 2023-09-06 |

Intro

自從在 SEETF Shard 和 b6aCTF babyRSA 死亡之後我開始發現自己其實很不擅長 small_roots 相關的技巧。而最近的 WACON qual 又出現了一個需要小爆搜 + 優化的題目，所以我打算把稍微整理過的資料丟著。

Challenge

from Crypto.Util.number import bytes_to_long, getStrongPrime

with open("flag.txt", "rb") as f:
    m = bytes_to_long(f.read())

SIZE = 1024
p = getStrongPrime(SIZE)
q = getStrongPrime(SIZE)
n = p * q
e = 0x10001
c = pow(m, e, n)

p_msb = p - p % (2 ** (SIZE // 2))

print(f"{n = }")
print(f"{c = }")
print(f"{p_msb = }")

Solution

第一步可以從 maple 偷 flatter 優化版的 small_roots，我雖然沒有實際比較過差多少，但真的差很多。

接下來不論要爆搜多少，都需要面臨決定參數的問題。過去的我非常糾結參數的正確性，看到隊友搞了 \(\beta=0.38\) 之後快中風了，但實際上能找到roots的都是好參數。後來學習了 ConnorM's blog 之後覺得很有道理 – 不論怎麼調 \(\beta, \epsilon\)，最後有影響的都是決定矩陣大小的 \(m, t\)，既然沒有要追求理論值乾脆直接調 \(m\) 就行了。於是我照著跑 ConnorM的script，我家MBP 2017得到了差不多的數字：

事情似乎到這裡就結束了，加速small_roots，找到好參數，還有什麼可以做的？然而...

Final optimization

比起真的爆搜 bits ，其實質數還是有點結構可以拿來利用。最常見的操作是利用質數是奇數把 \(f = p_msb + x\) 改成 \(f = p_msb + 2 * x + 1\) ，減少1 bit的負擔。同樣的道理，我們能說 \(p\) 不是 \(3\) 的倍數，但因為有兩種可能所以不是很能列成式子，只能各自跑。然而這件事提醒了我，比起爆搜bit不如去爆搜 \(p%c\) ，其中\(c\) 是小質數的積。實際測試之後的結果是：

\(c = 210\) 的狀況下只有48種餘數需要處理，也就相當於大概四到五倍的加速，實際用的多項式是f = constant + 210 * x + i，其中 constant 刻意改成 210 的倍數會讓世界美好許多。其他細節留給讀者做練習。