RSA 中根据 (N, e, d) 求 (p, q)
January 7, 2017 •
Comment
湖湘杯有一道题是知道 $(N, e, d)$ 求 $(p, q)$，当时用了 $ e\cdot d - 1 = h \cdot \varphi (n) $ 这个公式，爆破 $h$，考虑 $ \varphi (n) $ 与 $ N $ 相差不大，可以认为位数相同，求出 $ \varphi (n) $ 之后再根据 $ N = p\cdot q $ 和 $ \varphi(n) = (p - 1)(q - 1) $ 联立一个方程。