BigInteger .isProbablePrime() Part 2 RSA Concepts Tutorial

In this tutorial I am going to build on concepts from the Part 1 Tutorial. I am going to go over how we can have some fun trying to crack the underlying foundation of RSA encryption and learn why it is considered to be so secure in the process. The foundation of RSA encryption depends upon the mathematical difficulty of finding exactly two large prime factors in a given composite number. There is more to RSA than what I am going to cover in this tutorial, I am just interested in demonstrating an example of using the isProbablePrime() method to find the factors.

RSA and Integer Factorization

The first step in the RSA generation process is to create two large prime numbers - that is super easy to do using the BigInteger constructor designed to create random large prime numbers of a desired bit length.

p1 = 610184092910438723870287020969117173007702369691170383253362521045606490795
26102941690576566424699900385467279395448158298461356798494450870415033224971310
70272446968062952822674710508032415130547517786885185147855289564444165118850319
6728957803660467710146567320332080723683827260074268026455947726660400347

p2 = 395521560328079411412360976093535698058299804642091677831929226013049199060
32233849789733443576160556077974606833287472073920619831127847590456720285055401
72596005285051239942145613473603498610577810744661724629229502581799173048149782
60325285717050555578171289205933928626205627297283625833885578525424105709

Now we take p1 and multiply it by p2 to obtain the product, or modulus in RSA terminology. Don't confuse the RSA modulus with the modulo operator (%, mod or remainder).

p1 * p2 = 2864237921979891712099863160060134475451742248854585586708377609707779
75773757014103591259413550619132728160681398172162041848283529670778811098227219
84061137269784646223351711154002493433842564893898323695966676770030866646988065
35016830223430739408762410003412031472932250871081363248334976841564609965500731
26091083301625713367516601247265749421033841197113720251299381157600172813251370
34091656099605816461244208488955836711702439604944356848787895674903544367082891
38469948530036827395356615842988790119420063007260589596271507718815288846364070
8634756771862897030421398428575473538476977837047800037169019372333

Incidentally, the modulus happens to be 2048 bits in length (2048-bit encryption). The p1 and p2 prime numbers shoud not be very close in value, p1 happens to be 1023 bits and p2 happens to be 1026 bits. Let's get started...



Open the command prompt (CMD - see the Getting Started ) and type in the following commands.

C:\Windows\System32>cd \
C:\>md Java
C:\>cd Java
C:\Java>
C:\Java>md PrimeTwo
C:\Java>cd PrimeTwo
C:\Java\PrimeTwo>Notepad PrimeTwo.java

Copy and Paste, or type the following code into Notepad and be sure to save the file when you are done.


import java.math.*;
import java.util.*;

class PrimeTwo {
    private static final int BIT_LENGTH = 32;

    public static void main(String args[]) {
		
        int bits1 = new Random().nextInt(BIT_LENGTH-3)+ 2; // create a random int between 2 and BIT_LENGTH-2
        int bits2 = BIT_LENGTH - bits1;
		
        BigInteger p1 = new BigInteger(bits1, 80, new Random());
        BigInteger p2 = new BigInteger(bits2, 80, new Random());
        BigInteger largeComposite = p1.multiply(p2);
		
        System.out.println(p1 + ", " + bits1 + " bits");
        System.out.println(p2 + ", " + bits2 + " bits");
        System.out.println("largeComposite= " + largeComposite + ", " + largeComposite.bitLength() + " bits");
        BigInteger square = bigSQRT(largeComposite);
        System.out.println("Square root= " + square);
        System.out.println("Square root squared= " + square.multiply(square)+"\n");
		
        primeFactors(largeComposite, square);
		
    }
	
    public static void primeFactors(BigInteger largeComposite, BigInteger end) {
		
        final BigInteger TWO = new BigInteger("2");
        if (largeComposite.mod(TWO).compareTo(BigInteger.ZERO) == 0) {
            System.out.println("First prime factor is 2" );
            System.out.println("Second prime factor is " + largeComposite.divide(TWO));
            return ;
        }
		
        long startTime = System.currentTimeMillis();
        BigInteger factor = new BigInteger("3"); 
        while(true) {
            if (factor.isProbablePrime(5)) {
                if (largeComposite.mod(factor).bitLength() == 0) {
                    System.out.println("First prime factor is " + factor );
                    System.out.println("Second prime factor is " + largeComposite.divide(factor) );
                    System.out.println("Time to find factors: " + (System.currentTimeMillis() - startTime) + " milliseconds");
                    break;
                }								
            }
            factor = factor.add(TWO);			
        }
    }
	
    public static BigInteger bigSQRT(BigInteger x) {
        BigInteger two = new BigInteger("2"), y;
        int i = 0;
        for (y = x.divide(two); y.compareTo(x.divide(y)) > 0; y = ((x.divide(y)).add(y)).divide(two), i++);
        if (x.compareTo(y.multiply(y)) == 0) {
            return y;
        } else {
            return y.add(BigInteger.ONE);
        }
    }
}


Now switch back to the command prompt (CMD) and type in javac PrimeTwo.java and press Enter.
Now type in java PrimeTwo and press Enter.


C:\Java\PrimeTwo>javac PrimeTwo.java
C:\Java\PrimeTwo>java PrimeTwo
See video for results and more...


Final thoughts

Stay tuned for my next tutorial where I will demonstrate how we can tap into the power of multi-threading to greatly speed up the process of prime factorization.


Tutorials