Simple RSA Encryption using Java's built in library

Question

The requirements are:

1. The prime numbers p and q should be at least 1024-bit

2. The difference of two primes should be bigger than 2^512 (for security)

Question: What I am wondering is that I specified the bit length of p and q, and also SecureRandom instance to generate them randomly, But what I am told is that the difference may not be larger than 2^512. Then how can I specify the difference such that such that it is larger than 2^512? Then I think I would no longer be able to generate p and q randomly ?

Here is the documentation of constructor for BigInteger class which show I have to use bye array byte[] if I want to specify it manually and if I do so then there is no way to generate it randomly.

Any hint would be great.

Thank you.

Here is the method I am having issue with:

public RSA(int bits) {
    bitlen = bits;
    SecureRandom random = new SecureRandom();
    BigInteger p = new BigInteger(bitlen, 100, random);
    BigInteger q = new BigInteger(bitlen, 100, random);
    n = p.multiply(q);
    BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q
            .subtract(BigInteger.ONE));
    e = new BigInteger(Integer.toString(eValue));
    while (m.gcd(e).intValue() > 1) {
        e = e.add(new BigInteger("2"));
    }
    d = e.modInverse(m);
}

Here is the complete source code:

import java.math.BigInteger;
import java.security.SecureRandom;

public class RSA {

    public static double runningTime;
    private BigInteger n, d, e;
    private int bitlen = 1024;
    static int eValue = 65537;

    /** Create an instance that can encrypt using someone provided public key. */
    public RSA(BigInteger newn, BigInteger newe) {
        n = newn;
        e = newe;
    }

    /** Create an instance that can both encrypt and decrypt. */
    public RSA(int bits) {
        bitlen = bits;
        SecureRandom random = new SecureRandom();
        BigInteger p = new BigInteger(bitlen, 100, random);
        BigInteger q = new BigInteger(bitlen, 100, random);
        n = p.multiply(q);
        BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q
                .subtract(BigInteger.ONE));
        e = new BigInteger(Integer.toString(eValue));
        while (m.gcd(e).intValue() > 1) {
            e = e.add(new BigInteger("2"));
        }
        d = e.modInverse(m);
    }

    /** Encrypt the given plain-text message. */
    public String encrypt(String message) {
        return (new BigInteger(message.getBytes())).modPow(e, n).toString();
    }

    /** Encrypt the given plain-text message. */
    public BigInteger encrypt(BigInteger message) {
        return message.modPow(e, n);
    }

    /** Decrypt the given cipher-text message. */
    public String decrypt(String message) {
        return new String((new BigInteger(message)).modPow(d, n).toByteArray());
    }

    /** Decrypt the given cipher-text message. */
    public BigInteger decrypt(BigInteger message) {
        return message.modPow(d, n);
    }

    /** Generate a new public and private key set. */
    public void generateKeys() {
        SecureRandom random = new SecureRandom();
        BigInteger p = new BigInteger(bitlen, 100, random);
        BigInteger q = new BigInteger(bitlen, 100, random);
        n = p.multiply(q);
        BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q
                .subtract(BigInteger.ONE));
        e = new BigInteger(Integer.toString(eValue));
        while (m.gcd(e).intValue() > 1) {
            e = e.add(new BigInteger("2"));
        }
        d = e.modInverse(m);
    }

    /** Return the modulus. */
    public BigInteger getN() {
        return n;
    }

    /** Return the public key. */
    public BigInteger getE() {
        return e;
    }

    /** Test program. */
    public static void main(String[] args) {
        runningTime = System.nanoTime();
        RSA rsa = new RSA(1024);

        String text1 = "RSA-Encryption Practice";
        System.out.println("Plaintext: " + text1);
        BigInteger plaintext = new BigInteger(text1.getBytes());

        BigInteger ciphertext = rsa.encrypt(plaintext);
        System.out.println("cipher-text: " + ciphertext);
        plaintext = rsa.decrypt(ciphertext);

        String text2 = new String(plaintext.toByteArray());
        System.out.println("Plaintext: " + text2);
        System.out.println("RunningTime: "
                + (runningTime = System.nanoTime() - runningTime) / 1000000
                + " ms");
    }
}

Answer 1

It is quite hard to randomly generate two 1024-bit primes which are less than 2⁵¹² apart. The probability is <2^-509 (this is quite impossible). So generally you shouldn't have a problem. On the off chance that this still happens, you can try again when checkDiff returns false in a while loop. This makes it a very fast converging las vegas algorithm.

final static BigInteger targetDiff = new BigInteger("2").pow(512);

public boolean checkDiff(BigInteger p, BigInteger q){
    BigInteger pDiff = p.subtract(q);
    pDiff = pDiff.abs();

    BigInteger diff = pDiff.subtract(targetDiff);

    return diff.compareTo(BigInteger.ZERO) == 1;
}