37.3.5.4 Modular Exponentiation (With CRT)

The purpose of this service is to perform the Modular Exponentiation with the Chinese Remainders Theorem (CRT). This service processes integers in GF(p) only.

The options available for this service are:

• Fast implementation
• Regular implementation
• Exponent is located in Crypto RAM or not
• Exponent window size

This service processes a Modular Exponentiation with the Chinese Remainder Theorem:

R = X^Dmod(N) with N = P *Q

This service requires that the modulus N is the product of two co-primes P and Q and that the decryption exponents D is co-prime with the product ((P-1)*(Q-1)).

The Input data are P, Q, EP, EQ, Rvalue, and X. P and Q are the co-primes so that N = P*Q.

X is the number to exponentiate.

EP, EQ and Rval are calculated as follows:

EP = Dmod(P – 1) EQ = Dmod(Q – 1) Rval = P^–1mod(Q)

In some cases, the decryption exponent D may not be available and the encryption exponent E may be available instead. The possibilities to calculate the parameters are:

• Calculate D from E with the formula:

  D = E^–1mod((P – 1) × (Q – 1))

• Calculate the parameters from E:

  EP = E^–1mod(P – 1) EQ = E^–1mod(Q – 1) Rval = P^–1mod(Q)

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

• X the input number (pointed by {nu1XBase,2*u2ModLength +16})
• P and Q the primes (pointed by {nu1ModBase,2*u2ModLength +8}).
• EP and EQ the reduced exponents (pointed by {pfu1ExpBase,2*u2ExpLength +8})
• Rval and Precomp (pointed by{nu1PrecompBase,RAndPrecompLen})
• Blinding the exponent blinding value (provided inu1Blinding)

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

The service for this operation is CRT.

The following table shows the parameter block for the CRT service.

Many parameters have complex placement in memory; therefore, detailed figures are provided in CRT Service Placement below.

Most of the CRT options configure the Modular Exponentiation steps of the CRT and so are very similar to the Fast Modular Exponentiation options.

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

• the mandatory Calculus Mode Option described in Table 37-63
• the mandatory Window Size Option described in Table 37-64
• the indication of the presence of the exponent in Crypto RAM

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

• Operation: CRT using the Fast Modular Exponentiation with the window size equal to 1 and with no part of the Exponent area in the Crypto RAM

  PUKCL(u2Options) = PUKCL_EXPMOD_FASTRSA | PUKCL_EXPMOD_WINDOWSIZE_1;

• Operation:CRT using the Regular Modular Exponentiation with the window size equal to 2 and with one part the Exponent area in the Crypto RAM

  PUKCL(u2Options) = PUKCL_EXPMOD_REGULARRSA | PUKCL_EXPMOD_WINDOWSIZE_2 | PUKCL_EXPMOD_EXPINPUKCCRAM;

For this service, two exclusive Calculus Modes for the Modular Exponentiation steps of the CRT are possible. The following table describes the Calculus Mode Options.

For this service, four window sizes for the Modular Exponentiation Steps are possible. The window size in bits is those of the windowing method used for the exponent.

The choice of the window size is a balance between the size of the parameters and the computation time:

• Increasing the window size increases the precomputation workspace.
• Increasing the window size reduces the computation time (may not be relevant for very small exponents). The length of the Rval and Precomp area depends on the window size W and u2ModLength.

The Rval and Precomp area length is:

RandPrecompLen = 4 * (u2ModLength + 4) + max(64 , 2^(W-1) * (u2ModLength + 4)) + 8

The following table shows the size of the Rval and Precomp area, depending on the chosen window size option.

The exponent area can be located in RAM or in the data space. If one part of the exponent area is in Crypto RAM this must be mandatory signaled by using the PUKCL_EXPMOD_EXPINPUKCCRAM option.

The following table describes this option.

PUKCL_PARAM PUKCLParam;
PPUKCL_PARAM pvPUKCLParam = &PUKCLParam;


PUKCL(u2Option) =...;

// Depending on the option specified, not all fields must be filled PUKCL_CRT(nu1ModBase) = <Base of the ram location of P and Q>; PUKCL_CRT(u2ModLength) = <Length of P or Q>;
PUKCL_CRT(nu1XBase) = <Base of the ram location of X>; 
PUKCL_CRT(nu1PrecompBase) = <Base of the ram location of RVal and Precomp>; 
PUKCL_CRT(pfu1ExpBase) = <Base of the ram location of EP and EQ>; 
PUKCL_CRT(u2ExpLength) = <Length of EP or EQ>;
PUKCL_CRT(u1Blinding) = <Blinding value>;
...

// vPUKCL_Process() is a macro command, which populates the service name
// and then calls the library... 
vPUKCL_Process(CRT, pvPUKCLParam);
if (PUKCL_Param.Status == PUKCL_OK)
            {
            // operation has been performed correctly
            ...
            }
else // Manage the error

The following conditions must be avoided to ensure that the service works correctly:

• nu1ModBase, nu1XBase, nu1PrecompBase, pfu1ExpBase are not aligned on 32-bit boundaries
• {nu1XBase, 2*u2ModLength + 16}, {nu1ModBase, 2*u2ModLength + 8},{nu1PrecompBase,<PrecompLength>} are not in Crypto RAM
• {nu1ExpBase,2*u2ExpLength + 8} is not in Crypto RAM and PUKCL_EXPMOD_EXPINPUKCCRAM is specified
• u2ModLength or u2ExpLength are either: < 4, > 0xffc or not a 32-bit length
• None or both PUKCL_EXPMOD_REGULARRSA and PUKCL_EXPMOD_FASTRSA are specified.
• {nu1XBase,2*u2ModLength + 16} overlaps with either: {nu1ModBase, 2*u2ModLength +8},{nu1PrecompBase, <PrecompLength>} or {pfu1ExpBase, 2*u2ExpLength + 8}
• {nu1ModBase,2*u2ModLength + 8} overlaps with either: {nu1PrecompBase, <PrecompLength>} or {pfu1ExpBase, 2*u2ExpLength + 8}
• {nu1PrecompBase, <PrecompLength>} overlaps {pfu1ExpBase, 2*u2ExpLength +8}

The parameters’ placements are described in detail in the following figures.

The following table details the maximum size in bits of P or Q, of N and of EP or EQ.

• The maximum size in bits of P or Q equals:

  <Max Size Bits P> = <Max Size Bits Q> = 8 * <Max u2ModLength bytes>

• The maximum size in bits of N=P*Q equals:

  <Max Size Bits N> = 2 * <Max Size Bits P>

• The maximum size in bits of EP or EQ equals:

  <Max Size Bits EP> = <Max Size Bits EQ> = 8 * <Max u2ExpLength bytes>

• In case of the PUKCL_EXPMOD_EXPINPUKCCRAM option is specified, for the computation of the maximum acceptable size, it is assumed the Exponent is entirely in the Crypto RAM and its length equal the Modulus one.
• Otherwise, the Exponent is entirely out of the Crypto RAM and so the computation do not depend on its length.