11

I'm playing around and trying to write an implementation of RSA. The problem is that I'm stuck on generating the massive prime numbers that are involved in generating a key pair. Could someone point me to a fast way to generate huge primes/probable primes?

5 Answers 5

20

You don't generate prime numbers exactly. You generate a large odd number randomly, then test if that number is prime, if not generate another one randomly. There are some laws of prime numbers that basically state that your odds of "hitting" a prime via random tries is (2/ln n)

For example, if you want a 512-bit random prime number, you will find one in 2/(512*ln(2)) So roughly 1 out of every 177 of the numbers you try will be prime.

There are multiple ways to test if a number is prime, one good one is the "Miller-Rabin test" as stated in another answer to this question.

Also, OpenSSL has a nice utility to test for primes:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
3
  • 1
    Thanks. This explains a lot of the problems I was having. Aug 3, 2009 at 15:55
  • 1
    you can generate primes in openssl as well: openssl prime -generate -bits 512
    – mykhal
    Aug 15, 2015 at 8:18
  • Largest 512 bit prime is 2**512-569, found using: python -c 'print("\n".join([str(2**512-(x*2+1)) for x in range(1000)]))' | xargs -n 1 openssl prime Aug 15, 2018 at 17:43
3

Take a look at how TrueCrypt does it. Also, take a look at Rabin-Miller for testing large pseudoprimes.

1
  • Why do you assume that TrueCrypt generates primes? As far as I know it only uses symmetric crypto. Jan 20, 2015 at 11:55
3

There is an algorithm due to U. Maurer that generates random provable (in contrast to statistically highly-probable) primes that are almost uniformly distributed over the set of all primes of a special size. I have a Python implementation of it that is fairly efficient at: http://s13.zetaboards.com/Crypto/topic/7234475/1/

2

You didn't mention what language you are using. Some have a method of doing this built in. For example, in java this is as easy as calling nextProbablePrime() on a BigInteger.

1
  • Depending on how that functionality is implemented, you may compromise your key choice if the search space is reduced.
    – Stephen
    Feb 15, 2012 at 19:33
1

Mono has a BigInteger class that's open source as does java. You could take a look at those. They're probably portable :) g'luck

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.