RSA 已知 e，d 和 n，分解 N

这次的密码学实验有一个已知 e ， d 和 N ，分解 N 的问题，想了很久（其实没想多久，试了一下就放弃了），然后就到网上找资料。找到了一个很好用的网站，DI Management Home，都是关于密码学的，里面就有关于这个问题的算法¹。

Initially we compute k = de − 1 . We then choose a random integer g in the range 1 < g < N . Now k is an even number, where k = 2^tr with r odd and t ≥ 1 , so we can compute x = g^k/2, g^k/4, …, g^k/2t (mod  N) until x > 1 and y = gcd (x−1,N) > 1 . If so, then one of our factors, say p , is equal to y , and the other is q = N/y and we are done. If we don’t find a solution, then we choose another random g .

DI Management - RSA: how to factorize N given d

简单翻译一下：

首先我们计算 k = de − 1 。然后选择一个随机数 g ，满足 1 < g < N 。 k 是偶数，所以 k = 2^tr ，其中 r 是奇数且 t ≥ 1 ，然后计算 x = g^k/2, g^k/4, …, g^k/2t (mod  N)，直到 x > 1 且 y = gcd (x−1,N) > 1 。 如果这样的 y 存在，那么其中一个因子 p 等于 y ，并且 q = N/y ，这样就完成了。如果这样的 y 不存在，就重新生成随机数 g 。

下面是我的代码，对原算法稍微进行了一点改动。原算法是先计算出 t 和 r ，然后依次计算 x = g^k/2i 。这里我不计算 t 和 r ，而是只要 k 是偶数，就将其除以 2，然后计算 x = g^k 并判断是否满足条件。这样可以减少一些计算，但是由于 t 并不大，所以减少的计算有限。

完整代码见MeanZhang/RSA: RSA-Java。

/**
 * 已知e，d，n，分解n
 *
 * @param e 公钥e
 * @param d 私钥d
 * @param n 模数n
 * @return p，q
 */
public static BigInteger[] attack(BigInteger e, BigInteger d, BigInteger n) {
    // p,q
    BigInteger[] result = new BigInteger[2];
    // k=de-1
    BigInteger k = d.multiply(e).subtract(BigInteger.ONE);
    Random random = new Random();
    while (true) {
        BigInteger g = new BigInteger(n.bitLength(), random);
        // 选择随机数g，1<g<n
        while (g.compareTo(BigInteger.ONE) <= 0 || g.compareTo(n) >= 0)
            g = new BigInteger(n.bitLength(), random);
        BigInteger k1 = k;
        // 计算t和g^(k/2^i)的过程合在一起
        while (k1.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            // 如果k为偶数，就除以2
            k1 = k1.shiftRight(1);
            // 此时g^(k/2^i)=g^k1
            BigInteger x = g.modPow(k1, n);
            // 计算y=gcd(x−1,n)，直接赋值给p(result[0])
            result[0] = x.subtract(BigInteger.ONE).gcd(n);
            // 如果x>1且y=gcd(x−1,n)>1
            if (x.compareTo(BigInteger.ONE) > 0 && result[0].compareTo(BigInteger.ONE) > 0) {
                result[1] = n.divide(result[0]);
                return result;
            }
        }
    }
}

测试数据：

e:
65537
d:
13085102850405329895940153649208766646679432053055210927814587187939575969334380946175257120108607885616731724467899991987963542311668962802613624160423864736904359544115910805381019345850330276964971412664144174157825068713331109139842487999112829255389047329358923488846912437792391102853729375052922599258215311601018992134762683570752403675370812499995354701024990414541327012769030147878934713424171374951602988478984432403148854042370903764361797455965930292322795814453835335323397068237664481359506461188857661605832041501219728374514303209642746672993156029099655958158717907546664548938973389857200804582177
n:
21378032245774894186324720788457768851857953294637267751313371903474996018902810092972224806315945430514626988743400353365786674788848003569698586194388463460699531620948408197942261177369324808332585418351947368544183614904162658914539989430070735676083960582943505227316151479174351490943931346982185481068889458087344890907035731467000101100009111593455801160870652558847164438348031498067369123608755518383163346962891967964682970251625764813457371461595048927486942272152822570449609158417324070867001419543608370026546341531367233199832189762919523227554947408242727690461831545997600374969434706782376320559561
p:
134015724574231629415725856596339106132655429815809390083191653420751276014515665041469448212111089978027787330894345961709429696830117657137052704491606694791519141111894965847240833879740293408266251425861598011543042632576624378597158795956174622709934079034648552634466265913328434606944071200422868130573
q:
159518834925475861956097917917341301031640418209579419960447972340833353891477422457476074816300423813142613130845835933143395284444599641612757310435466623981281701817688676270876235464147642571713805328342460087461430626730047957682558277868352127107752854583156354513612089006699159193484825862868615965357

参考资料

---

1. RSA: how to factorize N given d↩︎