Cracking short RSA keys

A few days ago I had an interesting home assignment at my university related to this topic. So I thought I could write a piece of software that's easy to use and share the code with you. You can read more about RSA on wikipedia.

By definition in every RSA cryptosystem you have two things: public key (denoted as n and e pair) and a cipher (denoted as C). The algorithm states that you cannot easily determine private key (denoted as d), which is required for decryption, knowing only above mentioned values (n, e, C).

They got it right, but this rule works only for very large numbers used as keys (more than 1024 bit). If you have small values for n and e, then you can decrypt (or crack) the message. This could be done because factorization becomes possible for the small n. Actually for very small numbers you can do it automatically using one of the algorithms as I'll show here. For larger numbers there are many factorization databases you can find on the Internet.

The first step you should do is to determine a pair of numbers (factors) p and q that were originally used from given n. There is an algorithm for doing so.

// code of this method was taken from this article:
// http://programmingpraxis.files.wordpress.com/2012/09/primenumbers.pdf
public List factorize(BigInteger n)
{
    BigInteger two = BigInteger.valueOf(2);
    List factorList = new LinkedList();

    if (n.compareTo(two) < 0) {
        throw new IllegalArgumentException("must be greater than one");
    }

    while (n.mod(two).equals(BigInteger.ZERO)) {
        factorList.add(two);
        n = n.divide(two);
    }

    if (n.compareTo(BigInteger.ONE) > 0) {
        BigInteger factor = BigInteger.valueOf(3);
        while (factor.multiply(factor).compareTo(n) <= 0) {
            if (n.mod(factor).equals(BigInteger.ZERO)) {
                factorList.add(factor);
                n = n.divide(factor);
            }
            else {
                factor = factor.add(two);
            }
        }
        factorList.add(n);
    }

    return factorList;
}

Then you need to decrypt the message with a private key d. You can get it from the equation (e*d) mod ((p-1)*(q-1)) = 1. Fortunately you do not have to solve it manually. It can be solved by your favorite programming language tools. For this assignment I chose Java so I could use e.modInverse((p-1)(q-1)) method that is available for BigInteger numbers.

I also wrapped all the things in a clean API to abstract things out for the clients that shouldn't dive deep into all these math formulas.

public static void main(String[] args) {
    BigInteger e = BigInteger.valueOf(12371);
    BigInteger n = new BigInteger("517815623413379");
    BigInteger cipher = new BigInteger("127881381553746");
    RsaCracker cracker = new RsaCracker(e, n , cipher);
    try {
        BigInteger crackedMessage = cracker.crack();
        System.out.println("The original message in numeric format was: " + crackedMessage + ".");
    } catch (RsaCrackerException ex) {
        ex.printStackTrace();
    }
}

Even if you know nothing about RSA internals you can use the API to crack things.

Source Code

Thanks for you time.