如何用Modulus和Exponent/Public在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

正如你注意到的，Brute-强迫质数是相当慢的。

但还有更简单的方法。

1. 注意，您有两个模块，一个用于Bob，一个用于Alice。 一个简单的方法是计算这两种因子的最大公因子： BigInteger bobM =新BigInteger (“660560837854215449721185239”)；BigInteger aliceM =新BigInteger(“719946513324041157173195239”)；System.out.println(AliceM)； 这将输出535006138814359，这是Bob和Alice的一个因素。 这可能是纯粹的运气，这在这里工作，或它可能是由您的教练那样做。
2. 使用更快的因式分解方法。 其中之一是Pollard's Rho算法，它很容易实现。 专用静态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)；D=x.subtract(Y).abs().gcd(N)}返回d；} 使用它的起始值为x = BigInteger.TWO。这将在我的机器上运行1分钟，并输出爱丽丝的模块的134567897654321。

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

Bob:
p1: 535006138814359
p2: 123467898764321

Alice:
p1: 535006138814359
p2: 134567897654321

第二个质数看上去有点可疑，一点也不随机选择。