java - Implementing RSA algorithm

Question

I had the task to implement RSA algorithm, I read about it in Cormen's book and got most of information from there. I thought it worked good until I faced large p and q primes. For numbers about 250 and lower encryption and decryption works good, however if they are larger, modular exponentation returns negative numbers, which doesn't make sense.

I know that encrypted number can't be larger than n. I read that I can also compute inverse modulo by using extended GCD algorithm and taking x as that value, but when I tried calling extendedEuclid(phi, e)[1] it returned different values than function in RSA class. How can I fix it ?

Here is code for all needed components to compute keys.

Euclid Algorithm

public class Euclid {    
    public static int euclid(int a, int b) {
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        if (b == 0) {
            return a;
        } else {
            return euclid(b, a % b);
        }
    }

    public static int[] extendedEuclid(int a, int b) {
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        if (b == 0) {
            return new int[]{a, 1, 0};
        } else {
            int vals[] = extendedEuclid(b, a % b);
            int d = vals[0];
            int x = vals[2];
            int y = vals[1] - (int) Math.floor(a / b) * vals[2];
            return new int[]{d, x, y};
        }
    }
}

Modular Exponentation

public class Modular {
    public static int modularExponentation(int a, int b, int n) {
        int c = 0;
        int d = 1;
        String binaryString = Integer.toBinaryString(b);
        for (int i = 0; i < binaryString.length(); i++) {
            c = 2 * c;
            d = (d * d) % n;
            if (binaryString.charAt(i) == '1') {
                c = c + 1;
                d = (d * a) % n;
            }
        }          
        return d;
    }
}

RSA generator

public class RsaKeyGenerator {
    int d;
    int e;
    int n;
    public RsaKeyGenerator() {
        int p = 827;
        int q = 907;

        n = p * q;
        int phi = (p - 1) * (q - 1);
        e = computeCoPrime(phi);
        d = invMod(e, phi);
        System.out.println("Public: " + e);
        System.out.println("Private: " + d);
    }

    private static int computeCoPrime(int phi) {
        int e = 2;
        while (Euclid.euclid(e, phi) != 1) {
            e++;
        }
        return e;
    }

    private int invMod(int a, int n) {
        int a0, n0, p0, p1, q, r, t;
        p0 = 0;
        p1 = 1;
        a0 = a;
        n0 = n;
        q = n0 / a0;
        r = n0 % a0;
        while (r > 0) {
            t = p0 - q * p1;
            if (t >= 0) {
                t = t % n;
            } else {
                t = n - ((-t) % n);
            }
            p0 = p1;
            p1 = t;
            n0 = a0;
            a0 = r;
            q = n0 / a0;
            r = n0 % a0;
        }
        return p1;
    }

    public int encrypt(int num) {
        return Modular.modularExponentation(num, e, n);
    }

    public int decrypt(int cipher) {
        return Modular.modularExponentation(cipher, d, n);
    }

    public static void main(String[] args) {
        RsaKeyGenerator rsa = new RsaKeyGenerator();
        int cip = rsa.encrypt(1343);
        System.out.println(cip);
        System.out.println(rsa.decrypt(cip));
    }
}

Answer 1

The problem you're facing is integer overflow so if you're trying to store a number higher than 2^31 -1 in a signed integer which just isn't possible. So what ends up happening when you hit that limit is that the number wraps around to -2^31 -1.

What you want to do is look into the BigInteger class which will let you store much bigger numbers and should work fine.

The integer overflow happens at this line in the ModularExponentiation class:

d = (d * a) % n;