CODEWITHSUNDEEP
javaalgorithmencryptionrsa
Dan
Dan

Reputation: 13

RSA Encryption - Finding P and Q

I'm trying to figure out an RSA Encryption (using Java) by finding out P and Q. Here is what I have to do:

I have to generate two random numbers (P and Q) and following the guidelines:

  1. P & Q has to be at the most 7 bits long
  2. P & Q cannot be 0 or 1 (Using the Math.random() function is what I'm doing for this step)
  3. P & Q must be primes
  4. P & Q cannot be the same number (Already have this figured out)
  5. (PQ) must be at least 256 (Already have this figured out)

So, basically I'm starting out with this:

    double p = Math.random();
    double q = Math.random();

... and then trying to follow the 5 guidelines above. Can anyone give me a hint on how to figure out #1 and #3?

Thanks!

Upvotes: 0

Views: 1476

Answers (2)

Stefano Sanfilippo
Stefano Sanfilippo

Reputation: 33076

P and Q must be greater than 1 and at most 7 bits, that is to say, smaller than 2^7 = 128. Simply, generate a number between 2 and 127 inclusive.

For this purpose, you should use Random.nextInt, since it already gives you a random integer in a specified interval. Decide an upper bound for the random integers and you are set:

final Random rand = new Random();
int p = rand.nextInt(127 - 2 + 1) + 2;

Then, back to the core: the primality test. There are a few strategies for testing if a number is prime, but since your numbers are small we won't overcomplicate the thing and use a trial division. That is, try each (odd) number smaller than P and see if it evenly divides P:

public boolean isPrime(int p) {
    if (p == 2) return true;
    if (p % 2 == 0) return false;

    for (int d = 3; d < p; d += 2) {
        if (p % d == 0) return false;
    }

    return true;
}

there are a few optimizations possible here, like if there is a divisor of P, then it can't be larger than Math.sqrt(p), but, I'll let you figure out the details.

So now you can put the two pieces together and get a prime number generator:

class PrimeGenerator {
    private final Random rand = new Random();

    public int next() {
        int p = nextInt();
        while (!isPrime(p)) {
            p = nextInt();
        }
        return p;
    }

    private int nextInt() {
        return rand.nextInt(127 - 2 + 1) + 2;
    }

    private boolean isPrime(int p) {
        // As above...
    }
}

The key point is generating a random number in the given range, testing if it is prime or not and repeating until a prime is generated.

Upvotes: 1

John Bupit
John Bupit

Reputation: 10618

You could use the Seive of Eratosthenes, to check if a number is prime.

What you can do is, generate a list of all prime numbers (which the seive helps build easily) less than 2^7 - so that condition #1 is maintained. Then pick 2 numbers, p and q, at random from the list.

Here's how to build a list of primes using the seive:

List<Integer> getPrimeList(final int MAX_PRIME) {
    // Initialize a boolean array and set all values to true.
    bool[] isPrime = new bool[MAX_PRIME + 1];
    Arrays.fill(isPrime, true);

    List<Integer> primes = new ArrayList<>();

    // Start from 2. 0 and 1 are not prime.
    for(int i = 2; i * i <= MAX_PRIME; i++) {
        // If we've found a prime, set all it's multiples as composite,
        // and add this prime number to the list.
        if(isPrime[i]) {
            for(int j = i * i; j <= MAX_PRIME; j += i) isPrime[j] = false;
            primes.add(i);
        }
    }

    return primes;
}

You can generate this list once, and use it every time you need to get a random prime number.

int getRandomPrime() {
    int randIndex = (int)(Math.random() * primes.size());
    return primes.get(randIndex);
}

Upvotes: 1

Related Questions