如何使用模数和 Exponent/Public 密钥快速破解 Java 中非常大的数字的 RSA 加密

Question

我接到了一个任务，要编写一个程序来破解 RSA 加密，使用双方的模数和 public 密钥以及密文。我找到了蛮力解决方案，以找到与模数相乘的素数。然而，由于我必须使用的数字的大小，它似乎甚至无法完成处理。（模数长约 30 位）

这是我们得到的示例数据：

{
"alice": {
"modulus": "66056083785421544972111685239",
"publicKey": "38933338385103628492607145193"
},
"bob": {
"modulus": "71994651332404115788173195239",
"publicKey": "28763302913765661132800185637"
},
"cipherText": "5b8sot9g2168mp3nw51"
}

这是我目前正在尝试的解决方案，使用 Fermat 算法尝试更快地找到素数：

import java.math.BigInteger;
public class ferr
{

    static BigInteger r1;
    static BigInteger r2;
    static BigInteger aliceModulus = new BigInteger("107182711767121947041078387099");

    public static void main (){
        System.out.println("running");
        ferr x = new ferr();
     x.fermat(aliceModulus);
    }


    public void fermat(BigInteger N)
    {
        BigInteger a = calcSQR(N);
        BigInteger b2 = (a.multiply(a).subtract(N));
        while(Square(b2) == false) {
            a = a.add(BigInteger.valueOf(1));
            b2 = (a.multiply(a).subtract(N));
        } // end while
        r1 = a.subtract(calcSQR(b2));
        r2 = N.divide(r1);
        System.out.println("Roots = ("+ r1 +") , ("+ r2 +")");
    }

    public boolean Square(BigInteger N)
    {
        BigInteger sqRoot = calcSQR(N);
        if(sqRoot.multiply(sqRoot).equals(N)) {
            return true;
        } // end if
        else {
            return false;
        } // end else
    }

    public BigInteger calcSQR(BigInteger N)
    {
        if(N == BigInteger.ZERO || N == BigInteger.ONE) {
            return N; 
        } // end if
        BigInteger two = BigInteger.valueOf(2L);
        BigInteger x;
        // Starting with x = N/2 avoids magnitude issues with x squared
        for(x = N.divide(two); x.compareTo(N.divide(x)) > 0; x = ((N.divide(x)).add(x)).divide(two)) {
            if(N.compareTo(x.multiply(x)) == 0) {
                return x;
            } // end if
            else { 
                return x.add(BigInteger.ONE); 
            } // end else
        } // end for-loop
        return null;
    }
}

有没有更快的破解加密的方法？我已经离开这个程序运行几个小时了，但它还没有接近尾声。

Answer 1

如您所见，暴力破解素数非常慢。
但还有更简单的方法。

注意你有两个模数，一个给 Bob，一个给 Alice。
一个简单的镜头是计算两者的最大公约数：
```
BigInteger bobM = new BigInteger("66056083785421544972111685239");
BigInteger aliceM = new BigInteger("71994651332404115788173195239");
System.out.println(bobM.gcd(aliceM));
```
这将输出 535006138814359，这是 Bob 和 Alice 的一个因素。

这在这里起作用可能是纯粹的运气，或者它可能是由您的导师以这种方式制作的。

使用更快的分解方法。

其中之一是 Pollard's Rho algorithm，它很容易实现。

private static BigInteger pollardroh(BigInteger n, BigInteger x) {
    BigInteger y = x;
    BigInteger d = BigInteger.ONE;
    while (d.equals(BigInteger.ONE)) {
        x = x.modPow(BigInteger.TWO, n).add(BigInteger.ONE);
        y = y.modPow(BigInteger.TWO, n).add(BigInteger.ONE);
        y = y.modPow(BigInteger.TWO, n).add(BigInteger.ONE);
        d = x.subtract(y).abs().gcd(n);
    }
    return d;
}

以 x = BigInteger.TWO 的起始值使用它。这将在我的机器上运行约 1 分钟，并输出 134567897654321 作为爱丽丝的模数。

最后，这里是 Alice 和 Bob 模的因式分解：

Bob:
p1: 535006138814359
p2: 123467898764321

Alice:
p1: 535006138814359
p2: 134567897654321

第二个素数看起来有点可疑，根本不是随机抽取的

如何使用模数和 Exponent/Public 密钥快速破解 Java 中非常大的数字的 RSA 加密

How to quickly break RSA encryption with very large numbers in Java with the Modulus and Exponent/Public Key

java

encryption

rsa