37.3.4.12 GCD, Modular Inverse

The purpose of this command is to compute the Greatest Common Divisor (GCD) and the Modular Inverse. The algorithm used is the Extended Euclidean Algorithm for the GCD.

This command accepts as input two multiple precision numbers in GF(p) or two polynomials in GF(2ⁿ) X and Y and computes their GCD (D), if D equals one, the command also supplies the inverse of X modulo Y.

The available options are as follows:

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

This command calculates:

D = GCD(X,Y).

and parameter A in the Bezout equation:

A × X + B × Y = D.

The first input, or input to inverse is X.

The second input, or modulus is Y.

The GCD is output in D.

The modular inverse if X and Y are co-primes is output A:

A = X^–1mod(Y)

The command calculates the GCD and the value A. The value A is the multiplicative inverse of X, only if X and Y are co-prime. As a supplemental result, Z is given back, being the quotient of Y divided by D only if D is different from zero:

At the end of the command: X is overwritten by D.

Y is cleared.

The value of A is calculated and stored.

The value of Z is calculated and stored if D is different from zero.

The service name for this operation is GCD.

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

• X (pointed by {nu1XBase,u2Length}) filled with X (with MSB word to zero)
• Y (pointed by {nu1YBase,u2Length}) filled with Y (with MSB word to zero)
• A (pointed by {nu1ABase,u2Length}) to contain calculated A
• Z (pointed by {nu1ZBase,u2Length}) to contain calculated Z
• The workspace (pointed by {nu1WorkSpace,32})

The parameters X and Y must have their most significant 32-bit word cleared to zero. The length u2Length is the length of the longer of the parameters X and Y including this zero word.

To clarify here is an example:

• X is an 8 bytes number.
• Y is a 12 bytes number.

This example is processed this way before the use of the GCD service:

• The longer number is Y so its length is taken and increased by 4 bytes for the 32-bit word cleared to zero, this gives u2Length = 16 bytes. Therefore, X, Y, A and Z areas have a length of 16 bytes.
• Y is padded with 4 bytes cleared to zero on the MSB side and the u2Length = 16 bytes are written in memory (LSB first).
• X is padded with 8 bytes cleared to zero on the MSB side and the u2Length = 16 bytes are written in memory (LSB first).
• The areas A and Z are mapped in memory with a size of u2Length = 16 bytes.
• The workspace is mapped in memory with its constant size of 32 bytes

PUKCL_PARAM PUKCLParam;
PPUKCL_PARAM pvPUKCLParam = &PUKCLParam;
// Fill all the fields
PUKCL(u2Option) = 0;
PUKCL_GCD(nu1XBase) = <Base of the ram location of X>;
PUKCL_GCD(nu1YBase) = <Base of the ram location of Y>;
PUKCL_GCD(nu1ABase) = <Base of the ram location of A>;
PUKCL_GCD(nu1ZBase) = <Base of the ram location of Z>;
PUKCL_GCD(nu1WorkSpace) = <Base of the workspace>;
PUKCL_GCD(u2Length) = <Length of X, Y, A and Z>;
// vPUKCL_Process() is a macro command, which populates the service name
// and then calls the library...
vPUKCL_Process(GCD, pvPUKCLParam);
if (PUKCL_Param.Status == PUKCL_OK)
               {
               // The GCD has been executed correctly
               ...
               }
else // Manage the error

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

• nu1XBase, nu1YBase, nu1ABase or nu1ZBase are not aligned on 32-bit boundaries
• {nu1XBase, u2Length}, {nu1YBase, u2Length}, {nu1ABase, u2Length} or {nu1ZBase, u2Length} are not in Crypto RAM
• u2Length is either: < 4, > 0xffc or not a 32-bit length
• {nu1XBase, u2Length} overlaps {nu1YBase, u2Length} or {nu1XBase, u2Length} overlaps {nu1ABase, u2Length} or {nu1XBase, u2Length} overlaps {nu1ZBase, u2Length} or {nu1YBase, u2Length}overlaps

{nu1ABase, u2Length} or {nu1YBase, u2Length} overlaps {nu1ZBase, u2Length} or {nu1ABase, u2Length} overlaps {nu1ZBase, u2Length}