MENU

rsa

RSA 中根据 (N, e, d) 求 (p, q)

湖湘杯有一道题是知道 $(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) $ 联立一个方程。

Read More