37.3.5.3 Probable Prime Generation (Using Rabin-Miller)

This service is used to perform probable prime generation or test. This service processes integers in GF(p) only.

The options available for this service are:

• Choice of the number of iterations of the Rabin-Miller test
• Generation or Test of a probable prime number
• Fast Implementation
• Regular Implementation
• Exponent Window Size

The Rabin-Miller test is a probable-primality testing algorithm. As a consequence, the primality of the generated number is not guaranteed at 100%, however, numerous publications have been issued explaining how to estimate the probability of getting a composite number, giving the size of the number and the number of iterations (the T parameter).

Useful information can be found in the “Handbook of Applied Cryptography (Discrete Mathematics and Its Applications” by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, in the following sections:

• 4.2.3. “Rabin-Miller Test”
• 4.4. “Prime Number Generation”

This service processes a test for probable primality or a generation of a probable prime number.

This service processes one of the following operations: CheckProbablePrimality(N)

or

N = GenerateProbablePrimeFromSeed (NSeed)

In this computation, the following parameters need to be provided:

• N the input number (pointed by {nu1NBase,u2NLength +4})
  • If the requested operation is a test, it is untouched after the operation.
  • If the requested operation is a generation and a probable prime number was found before reaching the Maximum Increment, it contains the resulting probable prime after the operation.
  • If the requested operation was a generation and Maximum Increment was reached before a probable prime number was found, it contains no relevant information.
• Cns as a workspace (pointed by {nu1CnsBase,u2NLength +12})
• Rnd as a workspace (pointed by {nu1RndBase,u2NLength +16})
• Precomp the precomputation workspace (pointed by{nu1PrecompBase,PrecompLen})
• Exp as a workspace (pointed by {pfu1ExpBase,u2ExpLength +4})
• u1MillerRabinIterations the number of Miller Rabin Iterations requested
• u2MaxIncrement, maximum increment of the number in case of probable prime generation

The length PrecompLen depends on the lengths and options chosen; its calculus is detailed in Options below.

The service name for this operation is PrimeGen.

In case of probable prime generation, ensure that the addition of NSeed and Maximum Increment is not a number with more bytes than u2NLength, as this would produce an overflow.

Some of the Prime Generation options configure the Modular Exponentiation steps and so are very similar to the Modular Exponentiation options.

The options are set by the u2Options input parameter, which is composed of:

• the mandatory Operation Option described in Table 37-57
• the mandatory Calculus Mode Option described in Table 37-58
• the mandatory Window Size Option described in Table 37-59

The u2Options number is calculated by an “Inclusive OR” of the options. Some Examples in C language are:

• Operation: Probable Prime Testing with Fast Modular Exponentiation and the window size equal to 1

  PUKCL(u2Options) = PUKCL_PRIMEGEN_TEST | PUKCL_EXPMOD_FASTRSA | PUKCL_EXPMOD_WINDOWSIZE_1;

• Operation: Probable Prime Generate with Regular Modular Exponentiation and the window size equal to 2

  PUKCL(u2Options) = PUKCL_EXPMOD_REGULARRSA | PUKCL_EXPMOD_WINDOWSIZE_2;

The following table describes the PrimeGen service features available from the various options.

For this service, two exclusive Calculus Modes are possible. The following table describes the Calculus Mode Options.

The length of the Precomp area depends on the window size W and u2NLength. The Precomp area length is:

PrecompLen = max( 2*(u2NLength + 4) + 2W-1 * (u2NLength + 4), u2NLength + 8 + 64) + 8

The following table shows the size of the precomputation workspace (PrecompLen), depending on the chosen window size option.

The following table provides the maximum sizes for the Prime Generation depending on the window size.

PUKCL_PARAM PUKCLParam;
PPUKCL_PARAM pvPUKCLParam = &PUKCLParam;

// ! The Random Number Generator must be initialized and started
// ! following the directives given for the RNG on the chip PUKCL(u2Option) =...;
// Depending on the option specified, not all fields must be filled 
PUKCL_PrimeGen(nu1NBase) = <Base of the ram location of N>; 
PUKCL_PrimeGen(u2NLength)  =  <Length  of  N>; 
PUKCL_PrimeGen(nu1CnsBase) = <Base of the ram location of Cns>;
PUKCL_PrimeGen(nu1PrecompBase) = <Base of the ram location of Precomp>; 
PUKCL_PrimeGen(pfu1ExpBase) = <Base of the location of Exp>; 
PUKCL_PrimeGen(u2ExpLength) = <Length of Exp>; 
PUKCL_PrimeGen(u1MillerRabinIterations) = <Number of iterations>; 
PUKCL_PrimeGen(u2MaxIncrement) = <Maximum Increment>;
...

// vPUKCL_Process() is a macro command, which populates the service name
// and then calls the library... 
vPUKCL_Process(PrimeGen, pvPUKCLParam);
if (PUKCL_Param.Status == PUKCL_NUMBER_IS_PRIME)
            {
            // The number is probably prime
            ...
            }
else if (PUKCL_Param.Status == PUKCL_NUMBER_IS_NOT_PRIME)
            {
            // The number is not prime
            ...
            }
else // Manage the error

The following combinations of input values must be avoided in the case of a modular reduction ‘alone’, meaning that it has not been requested as an option of any other service:

• nu1NBase,nu1CnsBase, nu1RndBase,nu1PrecompBase,nu1ExpBase are not aligned on 32-bit boundaries
• {nu1NBase, u2NLength + 4}, {nu1CnsBase, u2NLength + 12}, {nu1RndBase, u2NLength +12},{nu1PrecompBase, <PrecompLength>} are not in Crypto RAM
• u2NLength is either: < 12, > 0xffc or not a 32-bit length
• Both PUKCL_EXPMOD_REGULARRSA and PUKCL_EXPMOD_FASTRSA are specified.
• {nu1PrecompBase,<PrecompLength>} overlaps with either: {nu1NBase, u2NLength + 4},{nu1CnsBase, u2NLength + 12} {nu1RndBase, u2NLength + 12} or {nu1ExpBase, u2ExpLength + 4}
• {nu1RndBase,3*u2NLength + 24} overlaps with either: {nu1NBase, u2NLength + 4},{nu1CnsBase, u2NLength + 12} {nu1XBase, u2NLength + 12} or {nu1ExpBase, u2ExpLength + 4}
• {nu1NBase, u2NLength + 4} overlaps {nu1CnsBase, u2NLength +12}