37.3.4.11 Integral (Euclidean) Division

Purpose

The purpose of this service is to compute the Euclidean Division of two multiple precision numbers in GF(p) or polynomial in GF(2n). The Numerator is divided by the Denominator giving the Quotient “Quo” and the Remainder “R”.

The following options are available:

  • Work in the GF(2n) field or in the standard integer arithmetic field GF(p)

How to Use the Service

Description

This service processes the calculus corresponding to:

N u m = M o d × Q u o + R ⁢ ⁢     w i t h ⁢           0 ≤ R ⁢ < M o d ⁢           a n d ⁢           Q u o = [ N u m M o d ]

The Numerator is Num.

The Divisior (Modulus) is Mod.

The Quotient is Quo.

The Remainder is R.

The Inputs are, the Numerator Num, and the Denominator Mod. The service calculates the Quotient and the Remainder. The Remainder overwrites the Numerator and is copied to the R area.

If the parameter nu1QuoBase equals zero, the Quotient is not stored in memory.

If nu1QuoBase is different from zero, the Quotient length is (<Numerator Length> - <Denominator Length>) + 4 bytes.

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

  • Num (pointed by {nu1NumBase,u2NumLength}) filled with the Numerator (with MSB word to zero).
  • Mod (pointed by {nu1ModBase,u2ModLength}) filled with the Denominator.
  • Workspace (pointed by {nu1CnsBase,64 or68}).
  • Quo (pointed by {nu1QuoBase,u2NumLength - u2ModLength + 4}) to contain calculated Quotient.
    • When the quotient is not needed, the nu1QuoBase pointer can be provided as NULL. In that case, only the remainder will be provided as a result.
  • R (pointed by {nu1RBase,u2ModLength}) to contain the calculated Remainder.

The service name for this operation is Div.

Parameters Definition

Table 37-35. Div Service Parameters
Parameter Type Dir. Location Data Length Before Executing the Service After Executing the Service
Specific/Gf2n Bit I – – GF(2n) Bit –
nu1NumBase nu1 I Crypto RAM u2NumLength

Base of Num

Filled with the Numerator

Base of Num

Filled with the Remainder
u2NumLength u2 I – – Length of the Numerator Length of the Numerator
nu1ModBase nu1 I Crypto RAM

u2ModLengt

Base of the Divisor

 Base of the Divisor untouched
u2ModLength u2 I – – Length of the Divisor Length of the Divisor
nu1QuoBase (see Note 1) nu1 I Crypto RAM u2NumLength - u2ModLength + 4 Base of the Quotient Base of the Quotient
nu1WorkSpace nu1 I Crypto RAM

GF(p): 64

GF(2n): 68

 Base of the WorkSpace Base of the WorkSpace corrupted
nu1RBase ( see Note 2) nu1 I Crypto RAM u2ModLength Base of the Remainder Base of the Remainder
Note:
  1. If the quotient is not needed, set nu1QuoBase to zero and the quotient will not be written to memory. If the quotient is needed, set the nu1QuoBase to the beginning of an area of size (u2NumLength - u2ModLength + 4) to write the whole quotient.
  2. The Remainder is present in the area {nu1NumBase, u2NumLength} at the end of the calculus. The nu1RBase parameter makes it possible to copy this result in the other area {nu1RBase, u2ModLength}, if this copy is not needed, set nu1RBase to the same value as nu1NumBase and the copy will not be done.
Note: The parameter Num must have its most significant 32-bit word cleared to zero. The length u2NumLength is the length of Num including this zero word.

One additional word is used on the LSB side of the Num parameter, this word is restored at the end of the calculus. As a consequence the parameter nu1NumBase must never been at the beginning of the Crypto RAM, i.e., ensure that nu1NumBase ≥ <Crypto RAM Base> + 4 bytes.

One additional word is used on the MSB side of the Num parameter, this word is not corrupted. As a consequence the Area {nu1NumBase, u2NumLength} must not be at the end of the Crypto RAM, i.e., en sure that nu1NumBase+u2NumLength ≤ <Crypto RAM End> - 4.

u2ModLength must be the true length of the Modulus, i.e., the MSB word of the area {nu1ModBase, u2ModLength} must be different from zero.

The minimum value for u2ModLength is 8 bytes, so the significant length of Num must be at least 8 bytes. To divide by a 32-bit value, the divider and numerator shall be multiplied by 232. The resulting remainder will have to be divided by 232, the quotient will be exact.

Code Example

PUKCL_PARAM PUKCLParam;
PPUKCL_PARAM pvPUKCLParam = &PUKCLParam;

// Fill all the fields
// In that case, the quotient will be computed
// If it was not needed, set nu1QuoBase to NULL 
PUKCL_Div(nu1NumBase) = <Base of the ram location of Num>; 
PUKCL_Div(nu1ModBase) = <Base of the ram location of Mod>; 
PUKCL_Div(nu1QuoBase) = <Base of the ram location of Quo>; 
PUKCL_Div(nu1WorkSpace) = <Base of the workspace>; 
PUKCL_Div(nu1RBase) = <Base of the ram location of R>; 
PUKCL_Div(u2NumLength) = <Length of Num>; 
PUKCL_Div(u2ModLength) = <Length of Mod>;

// vPUKCL_Process() is a macro command, which populates the service name
// and then calls the library... 
vPUKCL_Process(Div,pvPUKCLParam); 
if (PUKCL(u2Status) == PUKCL_OK)
            {
            // The Division has been executed correctly
            ...
            }
else // Manage the error

Constraints

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

  • nu1ModBase, nu1RBase, nu1QuoBase, nu1WorkSpace or nu1NumBase are not aligned on 32-bit boundaries
  • {nu1ModBase, u2ModLength}, {nu1RBase, u2ModLength}, {nu1WorkSpace, 64} or{nu1NumBase, u2NumLength} are not in Crypto RAM
  • u2ModLength, u2NumLength is either: < 4, > 0xffc or not a 32-bit length
  • One or more overlaps exist between two of the areas: {nu1ModBase,u2ModLength},{nu1RBase, u2ModLength} {nu1NumBase, u2NumLength}(1) or {nu1WorkSpace,64}
  • If nu1QuoBase is different from zero and: {nu1QuoBase, u2NumLength - u2ModLength + 4} are not in Crypto RAM
  • If nu1QuoBase is different from zero and one or more overlaps exist between two of the areas:

    {nu1QuoBase, u2NumLength - u2ModLength + 4}, {nu1ModBase, u2ModLength}, {nu1RBase, u2ModLength}, {nu1NumBase, u2NumLength} or {nu1WorkSpace, 64}

Overlaps between {nu1RBase, u2ModLength} and {nu1NumBase, u2NumLength} are forbidden, but the equality between nu1RBase and nu1NumBase is authorized

Status Returned Values

Table 37-36. Div Service Return Codes
Returned Status Importance Meaning
PUKCL_OK – Service functioned correctly.
PUKCL_DIVISION_BY_ZERO Severe The operation was not performed because the Denominator value is zero.