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

user_13156206 0
Viewed 1113

I was given a task to make a program to break the RSA encryption with the modulus and public keys of both parties and the cipher text. I have found solutions that brute force to find the prime values that are multiplied for the modulus. However with the size of the numbers that I have to use, it doesn't seem like it can even finish processing.(the modulus is 30 digits long or so)

This is the example data we were given:

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

This is the solution I'm currently trying, using the Fermat algorithm to try and find the primes faster:

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;
    }
}

Is there any faster solution to break the encryption? I've left this program running for a few hours and it's still no where near the end.

rsa encryption java
1 Answers

As you noticed, Brute-Forcing the prime numbers is quite slow.
But there are easier ways.

  1. Notice that you have two modulo, one for Bob, one for Alice.
    A trivial shot is to calculate the greatest common divisor of both:

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

    This will output 535006138814359, which is one factor of both Bob and Alice.

    It might be pure luck that this works here, or it could be crafted that way by your instructor.

  2. Use a faster factorization method.

    One of those is Pollard's Rho algorithm, which is quite easy to implement.

    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;
}

    Use it with a starting value of x = BigInteger.TWO. This will run for ~ 1 minute on my machine, and output 134567897654321 for Alice's modulo.

In the end, here are the factorization of both Alice & Bob's modulo:

Bob:
p1: 535006138814359
p2: 123467898764321

Alice:
p1: 535006138814359
p2: 134567897654321

The second primes look a bit suspicions, and not randomly selected at all.

user_8454140
Related