java - 如何使用模数和指数/公钥快速破解 Java 中大量数字的 RSA 加密

Question

我接到一个任务，要编写一个程序，用双方的模数和公钥以及密文来破解 RSA 加密。我找到了一些解决方案，可以强力找到与模数相乘的素值。然而，考虑到我必须使用的数字的大小，它似乎甚至无法完成处理。(模数长约 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

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

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

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

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

   这可能在这里起作用纯粹是运气，或者它可能是由你的老师设计的。

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

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

最后，这是 Alice 和 Bob 模数的因式分解:

Bob:
p1: 535006138814359
p2: 123467898764321

Alice:
p1: 535006138814359
p2: 134567897654321

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