Coding RSA Algorithm Java

Question

So, I am attempting to create an RSA algorithm from scratch.

So far, I have successfully created the ability to select two primes (which I have as 11 and 13 in my current example. Then, I calculate N by doing p x q. Which gets me 143.

Then, I move on to my public BigInteger findZ() method which calculates ϕ which is (p-1)(q-1).

Using this newly calculated ϕ, I want to find a number, or rather create an e variable that follows 1<(e)<ϕ, or simple gcd(e,ϕ) = 1 Thus, I initially set temp to equal my constant ONE (which is equal to one) + 1 to satisfy the range. However, after continuous debugging attempts, the loop never finds a value that has a GCD that is equal to one, which i've created a constant to represent since I am required to use BigInteger. Is there a reason for this?

Here is my code.

import java.math.BigInteger;

public class RSA 
{
//Intialize the variables.

private BigInteger p;
private BigInteger q;
private BigInteger n;
private BigInteger z;

final private BigInteger ONE = BigInteger.valueOf(1);


public BigInteger getP()
{
    return p;
}

public BigInteger getQ()
{
    return q;
}

//Computes N, which is just p*q.
public BigInteger findN()
{

    n = p.multiply(q);


    return p.multiply(q);
}


public BigInteger findZ()
{
    long pMinusOne = p.intValue() - 1;
    long qMinusOne = q.intValue() - 1;


    z = BigInteger.valueOf(pMinusOne * qMinusOne);

    return z;
}


public BigInteger getE()
{
     int temp = ONE.intValue() + 1;

     BigInteger GCD = BigInteger.valueOf(temp);

     while (GCD.gcd(z).compareTo(ONE) != 0)
     {
         temp++;
     }



    e = BigInteger.valueOf(temp);

    return e;
}

}

Any help is greatly appreciated.

Thanks!

Answer 1

Since you asked for any help, I'll answer your question and give other tips.

How to get e

One tip is to use equals() instead of compareTo() when you're just checking for equality. Sometimes that can reduce the amount of work being done, and it's easier to read as well.

The biggest error in your code is that temp is used to set the original value of GCD, but that doesn't link temp to GCD. They stay disconnected. If you change temp later, GCD won't know about it and won't change. You need to add one to GCD directly. Here's some example code:

BigInteger e = BigInteger.valueOf(3);
while (! phi.gcd(e).equals(BigInteger.ONE)) {
    e = e.add(BigInteger.ONE);
}

Look over BigInteger's methods

Get a sense of what you can easily do with BigInteger's by using your favorite search engine and searching for BigInteger 8 API. The 8 is for the version of Java you're using, so that might change. The API is for a list of methods.

Early on in the search results, you should find this API page. BigInteger has a lot of nice and convenient methods, so check them out. It even has a constructor that'll give you a BigInteger of whatever size you want that's very likely to be a prime, which is nice for generating the primes for a new random RSA key.

Use BigInteger's built-in constants

Don't recreate the following constants (which show up in the API page above):

• BigInteger.ZERO
• BigInteger.ONE
• BigInteger.TEN

Never convert BigInteger to long unless you're sure it'll fit

You're converting BigIntegers to long, which is a bad idea, since there are a lot of BigIntegers that won't fit in a long, giving you incorrect results. For correctness (which is more important than speed), do arithmetic directly with BigIntegers.

You also use intValue() a lot when you're getting a long. Use longValueExact(). For that matter, use intValueExact() when you're getting an int.

So, to calculate ϕ:

BigInteger pMinusOne = p.subtract(BigInteger.ONE);
BigInteger qMinusOne = q.subtract(BigInteger.ONE);

BigInteger phi = pMinusOne.multiply(qMinusOne);

Now you know that it will give correct results, even for larger BigIntegers. It's also not that hard to read, which is good for maintaining the code later.

What to store

You should also store just n and e (and d but only if it's a private key) Never store p, q, or ϕ with RSA because those allow you to easily figure out the private key from the public key.

In general, don't calculate in getZZZ methods

You should figure out n and e (and d but only if it's a private key) in the constructor method(s) and store only those in instance variables. Then, you can have a getN() and getE() method to get the precomputed instance variables. For example (and you don't have to use this code, it's just to give an idea):

public class RSA {
    private final BigInteger n;
    private final BigInteger e;
    private final BigInteger d;

    public RSA(final BigInteger p, final BigInteger q) {
        this.n = p.multiply(q);

        // Calculate phi
        final BigInteger pMinusOne = p.subtract(BigInteger.ONE);
        final BigInteger qMinusOne = q.subtract(BigInteger.ONE);
        final BigInteger phi = pMinusOne.multiply(qMinusOne);

        // Calculate e
        BigInteger e = BigInteger.valueOf(3L);
        while (! phi.gcd(e).equals(BigInteger.ONE)) {
            e = e.add(BigInteger.ONE);
        }
        this.e = e;

        // Calculate d
        this.d = e.modInverse(phi);
    }

    public BigInteger getN() {
        return n;
    }

    public BigInteger getE() {
        return e;
    }

    public BigInteger getD() {
        return d;
    }
}