PolarSSL is now part of ARM Official announcement and rebranded as mbed TLS.

Expected performance when generating prime


Aug 17, 2017 20:40
ashoti naikapa

Hello from Australia,

I'm new here on this forum, but have been interested in your technology for some time now.

I have a question regarding the performance of the prime generation using polarssl..

Running the test program dh_genprime.c with a generator of "4" and a DH_P_SIZE of 256,512 and 1024 what should be expecting in apx milliseconds on a old (pentium class laptop)...

Is more than a minute normal for a size of 1024 ? Is 1000ms normal for a size of 256 ?

The configuration I am using is pure C ( no asm,sse etc ) running on a 32bit windows computer ?

The results I am getting are very strange at times , and the results vary considerably with each run....

Ash

 
Aug 20, 2017 08:43
Hanno Becker

Hi Ashoti,

thanks for your interest in mbed TLS!

The example program dh_genprime searches for so-called safe primes, which are primes P such that P - 1 = 2Q for another prime Q (these are called "safe" as the presence of many prime factors in the factorization of P - 1 ease attacking the discrete logarithm problem for numbers modulo P, and the factorization 2Q is the smallest you can hope for).

The search for safe primes is equivalent to the search of primes Q such that 2Q+1 is also prime, and such a prime is called a Sophie Germain prime. It is conjectured that the density of Sophie Germain primes is 1 / ln(N)^2, so very roughly, in the range of k-bit numbers you expect a Sophie Germain primes every k^2 numbers. In contrast, ordinary primes have density 1 / ln(N), so you'd expect to find a k-bit prime after k tries (up to some constant).

So if you're looking for a 1024 bit prime, the density is around 1 in 1.000.000, and for each candidate, you have to check whether both Q and 2Q+1 are indeed primes, which involves expensive arithmetic operations.

It is therefore not surprising that DH prime generation takes a very long time, especially on older systems, and that's why dh_genprime warns ! Generating large primes may take minutes!.

The fact that the generation times vary heavily is also understandable, as the algorithm employed by dh_genprime is manifestly probabilistic: Both the number to begin the search with, as well as the primality tests for Q and 2Q+1 for a candidate Q, are non-deterministic.

Note that the above are just some heuristics and not are thorough analysis, but hopefully give you some insight on why safe prime generation is a very computation-intensive task.

Regards,

mbed TLS team member,

Hanno

 
Aug 21, 2017 14:20
ashoti naikapa

Hi,

Thank you for the response..

I did notice it uses the safe prime method - the confusion for me is that on some occasion generating a prime of 1024 bits sometimes takes 5 seconds, sometimes it takes 60 seconds, again is this strange ?

If you called the dh_gen_prime function over and over again with a 1024 bit key, should the average time be around 30secs per generation ?

I'm running an old laptop pentium running windows 10 ( 64bit )../

Ash

 
Aug 22, 2017 10:56
Ron Eldor

Hi ashoti,
As the generated primes are random values, and each value needs to be verified it is actually a prime number, the operation is not deterministic in time, and the time it takes to finish varies. The result you are experiencing is expected, hence the warning.
Note that prime generation is not a common operation, so in the overall progress, it shouldn't consume much of the total operation. Meaning, when you need to exchange keys, you generate the prime, but this is done little on every peer during the TLS session.
I hope this \clears up things for you.
Regards,
Mbed TLS Team member
Ron