43.3.5.1 Modular Reduction

This service is used to perform the various steps necessary to perform a modular reduction and accepts as input numbers in GF(p) or polynomials in GF(2ⁿ) .

The available options for this service are:

• Work in the GF(2ⁿ) or in the standard integer arithmetic field GF(p)
• Operation is the generation of the reduction constant.
• Operation is a Modular Reduction.
• Operation is a Normalization.

This service performs one of the following operations:

• Setup of the Fast or Normalize functions: generation of the reduction constant
• Fast Modular Reduction
• Big Modular Reduction (using Euclide’s division)
• Normalization

The service name for this operation is RedMod.

This service calculates the constant Cns, computed from the modulus and used to speed up the modular reduction:

Cns = SetupConstant(N)

This service must be processed before the use of the Fast or Normalize functions. In the Setup computations, the following data must be provided:

• N the modulus (pointed by {nu1ModBase,u2ModLength +4}).
• Cns the Setup Constant Result (pointed by {nu1CnsBase,u2ModLength +12}).
• X used as a workspace (pointed by {nu1XBase,2 * u2ModLength + 8}) (include the supplementary bytes; see Note 2 in Table 43-44
• R used as a workspace (pointed by {nu1RBase,64 or 68bytes}).
• u2ModLength is the Aligned Significant Length of the modulus and is not the byte Significant Length (see Aligned Significant Length).

These commands calculate an approximated or exact Modular Reduction, that is, the result may be greater than the modulus, but is always congruent to the true result.

Input and Result significant values verify:

• For the Fast Modular Reduction:

• For the Normalize:

In these Fast Modular Reduction and Normalize computations, the following data have to be provided:

• X (pointed by {nu1XBase,2 * u2ModLength +8})
  • The Normalize computation accept as entry a value whose length is lower or equal to u2ModLength + 4 (that is, for example, a value yet reduced but not normalized.). The u2ModLength + 4 MSB bytes are cleared at the beginning of the computation.
  • in case of Fast RedMod computations, the value X mayverify: X < (N²) *(2³²).
  • include the supplementary bytes; see Note 3 in Table 43-45)
• R (pointed by {nu1RBase,u2Modlength +4})
• N (pointed by {nu1ModBase,u2ModLength +4})
• Cns (pointed by {nu1CnsBase,u2ModLength +12})
• u2ModLength is the Aligned Significant Length of the modulus and is not the byte Significant Length (see Aligned Significant Length).

The Fast Modular Reduction is able to reduce inputs up to <2*u2ModLength + 4> bytes. The input can come from a multiplication of 2 <u2ModLength + 4> bytes numbers. The input X is considered as a <2*u2ModLength + 8> bytes number.

The Fast Modular Reduction returns a <u2ModLength + 4> bytes number, but this number is in fact a <u2ModLength + 2> significant bytes number. When using the Fast Modular Reduction, the two MSB bytes of the <u2ModLength + 2> can have a maximum of two lsb bits set (depending on the reduced number and the modulo).

The Normalize computation accepts as entry a resulting value of Fast Modular Reduction and computes an exact result. It can not be applied to the result of the product of two numbers of size NLength: a Fast Modular Reduction must be applied before.

For the Normalize computation, the X value is limited by the preceding formula but the area in memory is bigger as described in Table 43-45.

As input, the Normalize sub-service only accept values, which length is lower or equal to u2ModLength + 4. The Most Significant u2ModLength + 4 bytes are firstly cleared by this service.

This command calculates:

In this Big Modular Reduction computations, the following data must be provided:

• X (pointed by {nu1XBase,2 * u2ModLength + 8}) (include the supplementary bytes; see Note 1 in Table 43-46)
• R (pointed by {nu1RBase,u2Modlength +4})
• N (pointed by {nu1ModBase,u2ModLength +4})
• u2ModLength is the Aligned Significant Length of the modulus and is not the byte Significant Length (see Aligned Significant Length)
• Workspace (pointed by {nu1CnsBase,64 or 68}).

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

• the mandatory Operation Option described in Table 43-47
• if the Operation Option is PUKCL_REDMOD_REDUCTION, the Modular Reduction Sub-Option described in Table 43-48

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

• Operation: Setup for the ModularReductions.

  PUKCL(u2Options) = PUKCL_ REDMOD_SETUP;

• Operation: Fast ModularReduction.

  PUKCL(u2Options) = PUKCL_REDMOD_REDUCTION | PUKCL_REDMOD_USING_FASTRED;

For this command three exclusive options can be specified. The following table lists the operations that can be performed.

When selecting the PUKCL_REDMOD_REDUCTION option, one of the two sub-options listed in the following table must be selected.

PUKCL_PARAM PUKCLParam;
PPUKCL_PARAM pvPUKCLParam = &PUKCLParam;

PUKCL(Specific).CarryIn = 0; 
PUKCL(Specific).GF2n = ...;

PUKCL(u2Option) =...;

// Depending on the option specified, not all fields should be filled 
PUKCL_RedMod(nu1ModBase) = <Base of the ram location of N>; 
PUKCL_RedMod(u2ModLength) = <Length of N>;
PUKCL_RedMod(nu1CnsBase) = <Base of the ram location of Cns>;
...

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

Depending on the options chosen the lengths of the R area and Cns area differ:

• For the Setup:
  • RLength = 64bytes
  • CnsLength = u2ModLength +12
• For the Fast Reduction and Normalize:
  • RLength = u2ModLength +4
  • CnsLength = u2ModLength +8
• For the BigRedMod:
  • RLength = u2ModLength +4
  • CnsLength =64

The following combinations of input values should 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, nu1RBase, nu1XBase are not aligned on 32-bit boundaries
• {nu1ModBase, u2ModLength + 4}, {nu1CnsBase, u2CnsLength}, {nu1XBase, 2*u2XLength + 8 + s} or {nu1RBase, u2RLength} are not in Crypto RAM
• u2ModLength is either: < 4, > 0xffc or not a 32-bit length
• Overlaps exist between two or more of the areas: {nu1ModBase, u2ModLength + 4},{nu1CnsBase, u2CnsLength}, {nu1XBase, 2*u2XLength + 8 + s} or {nu1RBase, u2RLength}