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

发表于 更新于 分类于 ， 阅读次数： 本文字数： 658 阅读时长 ≈ 2 分钟

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

Initially we compute \(k = de-1\) . We then choose a random integer \(g\) in the range \(1 \lt g \lt N\) . Now \(k\) is an even number, where \(k = 2^tr\) with \(r\) odd and \(t\geqslant1\) , so we can compute \(x = g^{k/2}, g^{k/4}, \ldots, g^{k/2^t} \pmod N\) until \(x \gt 1\) and \(y = \gcd(x-1, N) \gt 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 \lt g \lt N\) 。 \(k\) 是偶数，所以 \(k = 2^tr\) ，其中 \(r\) 是奇数且 \(t\geqslant1\) ，然后计算 \(x = g^{k/2}, g^{k/4}, \ldots, g^{k/2^t} \pmod N\)，直到 \(x \gt 1\) 且 \(y = \gcd(x-1, N) \gt 1\) 。 如果这样的 \(y\) 存在，那么其中一个因子 \(p\) 等于 \(y\) ，并且 \(q=N/y\) ，这样就完成了。如果这样的 \(y\) 不存在，就重新生成随机数 \(g\) 。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 已知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;
            }
        }
    }
}

测试数据：

1
2
3
4
5
6
7
8
9
10
e:
65537
d:
13085102850405329895940153649208766646679432053055210927814587187939575969334380946175257120108607885616731724467899991987963542311668962802613624160423864736904359544115910805381019345850330276964971412664144174157825068713331109139842487999112829255389047329358923488846912437792391102853729375052922599258215311601018992134762683570752403675370812499995354701024990414541327012769030147878934713424171374951602988478984432403148854042370903764361797455965930292322795814453835335323397068237664481359506461188857661605832041501219728374514303209642746672993156029099655958158717907546664548938973389857200804582177
n:
21378032245774894186324720788457768851857953294637267751313371903474996018902810092972224806315945430514626988743400353365786674788848003569698586194388463460699531620948408197942261177369324808332585418351947368544183614904162658914539989430070735676083960582943505227316151479174351490943931346982185481068889458087344890907035731467000101100009111593455801160870652558847164438348031498067369123608755518383163346962891967964682970251625764813457371461595048927486942272152822570449609158417324070867001419543608370026546341531367233199832189762919523227554947408242727690461831545997600374969434706782376320559561
p:
134015724574231629415725856596339106132655429815809390083191653420751276014515665041469448212111089978027787330894345961709429696830117657137052704491606694791519141111894965847240833879740293408266251425861598011543042632576624378597158795956174622709934079034648552634466265913328434606944071200422868130573
q:
159518834925475861956097917917341301031640418209579419960447972340833353891477422457476074816300423813142613130845835933143395284444599641612757310435466623981281701817688676270876235464147642571713805328342460087461430626730047957682558277868352127107752854583156354513612089006699159193484825862868615965357

参考资料

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