37.3.5.2 Modular Exponentiation (Without CRT)

This service is used to perform the Modular Exponentiation computation. 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 in Crypto RAM
• Exponent window size

This service processes the following operation:

The service name for this operation is ExpMod.

R = X^Expmod(N)

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

• X: input number (pointed by {nu1XBase,u2ModLength +16})
• N: modulus (pointed by {nu1ModBase,u2ModLength +4}).
• Exp: exponent (pointed by {pfu1ExpBase,u2ExpLength +4})
• Cns: Fast Modular Constant (pointed by {nu1CnsBase,u2ModLength +8})
• Precomp: precomputation workspace (pointed by{nu1PrecompBase,PrecompLen})
• Blinding: exponent blinding value (provided inu1Blinding)

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

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

• the mandatory Calculus Mode Option described in Table 37-51
• the mandatory Window Size Option described in Table 37-52
• 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:Fast Modular Exponentiation with the window size equal to 1 and with no part of the Exponent in the Crypto RAM

  PUKCL(u2Options) = PUKCL_EXPMOD_FASTRSA | PUKCL_EXPMOD_WINDOWSIZE_1;

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

  PUKCL(u2Options) = PUKCL_EXPMOD_REGULARRSA | PUKCL_EXPMOD_WINDOWSIZE_2 | PUKCL_EXPMOD_EXPINPUKCCRAM;

There is no difference on the final result when using any of the options for this service. The choice has to be made according to the available resources (RAM, Time) and also taking into account the expected security level.

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

For this service, four window sizes 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 following table details the size of the precomputation workspace, depending on the chosen window size option.

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

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_ExpMod(nu1ModBase) = <Base of the ram location of N>; 
PUKCL_ExpMod(u2ModLength) = <Length of N>;
PUKCL_ExpMod(nu1CnsBase) = <Base of the ram location of Cns>; 
PUKCL_ExpMod(nu1XBase) = <Base of the ram location of X>; 
PUKCL_ExpMod(nu1PrecompBase) = <Base of the ram location of Precomp>; 
PUKCL_ExpMod(pfu1ExpBase) = <Base of the location of Exp>; 
PUKCL_ExpMod(u2ExpLength) = <Length of Exp>;
...

// vPUKCL_Process() is a macro command, which populates the service name
// and then calls the library... 
vPUKCL_Process(ExpMod, pvPUKCLParam);
if (PUKCL_Param.Status == PUKCL_OK)
            {
            // operation has been performed correctly
            ...
            }
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 command:

• nu1ModBase,nu1CnsBase, nu1XBase,nu1PrecompBase,nu1ExpBase are not aligned on 32-bit boundaries
• {nu1ModBase, u2ModLength + 4}, {nu1CnsBase, u2ModLength + 8}, {nu1XBase, u2ModLength +16},{nu1PrecompBase, <PrecompLength>} are not in Crypto RAM
• {nu1ExpBase,u2ExpLength + 4} has no part 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.
• {nu1PrecompBase,<PrecompLength>} overlaps with either: {nu1ModBase, u2ModLength +4},{nu1CnsBase, u2ModLength + 8} {nu1XBase, u2ModLength + 16} or {nu1ExpBase, u2ExpLength + 4}
• {nu1XBase,u2ModLength + 16} overlaps with either: {nu1ModBase, u2ModLength + 4},{nu1CnsBase, u2ModLength + 8} or {nu1ExpBase, u2ExpLength + 4}
• {nu1ModBase, u2ModLength + 4} overlaps {nu1CnsBase, u2ModLength +8}

The following table provides the maximum sizes for the Modular Exponentiation, depending on the window size and the presence of the exponent in Crypto RAM.

• The figures below are calculated supposing that u2ExpLength =u2ModLength.
• 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 is equal to the Modulus one.
• Otherwise, the Exponent is entirely out of the Crypto RAM and so the computation do not depend on its length.