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

Question

我的任务是制作一个程序，用双方的模数和公钥以及密文来破解 RSA 加密。我找到了用蛮力找到乘以模数的素数的解决方案。但是对于我必须使用的数字的大小，它似乎甚至无法完成处理。（模数为 30 位左右）

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

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

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

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

正如您所注意到的，对质数进行暴力破解非常慢。
但还有更简单的方法。

1. 请注意，您有两个模，一个用于 Bob，一个用于 Alice。
   一个简单的镜头是计算两者的最大公约数：

   BigInteger bobM = new BigInteger("66056083785421544972111685239");
   BigInteger aliceM = new BigInteger("71994651332404115788173195239");
   System.out.println(bobM.gcd(aliceM));
   

   这将输出535006138814359，这是 Bob 和 Alice 的一个因子。

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

2. 使用更快的分解方法。

   其中之一是Pollard 的 Rho 算法，它很容易实现。

   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 分钟，并输出134567897654321Alice 的模数。

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

Bob:
p1: 535006138814359
p2: 123467898764321

Alice:
p1: 535006138814359
p2: 134567897654321

第二个素数看起来有点怀疑，根本不是随机选择的。