Cryptography for Intel® Integrated Performance Primitives Developer Reference

Developer Reference

Contents

Montgomery Reduction Scheme Functions

This section describes Montgomery reduction scheme functions.
Montgomery reduction is a technique for efficient implementation of modular multiplication without explicitly carrying out the classical modular reduction step.
This section describes functions for Montgomery modular reduction, Montgomery modular multiplication, and Montgomery modular exponentiation.
Let
n
 be a positive integer, and let
R
 and
T
 be integers such that
R
>
n
,
gcd (
n
,
R
)= 1
, and
0 <
T
<
nR
. The Montgomery reduction of
T
 modulo
n
 with respect to
R
 is defined as
TR
- 1 mod
n
.
For better results, functions included in the cryptography package use
R
=
b
k
 where
b
=
 2
32
 and
k
 is the Montgomery index integer computed by the ceiling function of the bit length of the integer
n
 over 32.
All functions use employ the context
IppsMontState
 to serve as an operational vehicle to carry the Montgomery reduction index
k
, the integer big number modulus
n
, the least significant word
n
0
 of the multiplicative inverse of the modulus
n
 with respect to the Montgomery reduction factor
R
, and a sufficient working buffer reserved for various Montgomery modular operations.
Furthermore, two new terms are introduced in this section:
  • length of the context
    IppsMontState
     is defined as the data length of the modulus
    n
     carried by the structure
  • size of the context
    IppsMontState
     is therefore defined as the maximum data length of such an integer modulus
    n
     that could be carried by this operational vehicle.
The following example can briefly illustrate the procedure of using the primitives described in this section to compute a classical modular exponentiation
T
=
x
e
mod
n
. Consider computing
T
=
x
4
mod
n
, for some integer
x
 with
0 <
x
<
n
.
First get the buffer size required to configure the context
IppsMontState
 by calling
MontGetSize
 and then allocate the working buffer using OS service function, with allocated buffer to call
MontInit
 to initialize the context
IppsMontState
.
Set the modulus
n
 by calling
MontSet
 and then convert
x
 into its respective Montgomery form by calling
MontForm
, that is, computing
Then compute the Montgomery reduction of
using the function
MontMul
 to generate
The Montgomery reduction of
T
*
T
mod n
 with respect to
R
 is
Further applying
MontMul
 with this value and the value of 1 yields the desired result
T =
x
4
mod n
.
The classical modular exponentiation should be computed by performing the following sequence of operations:
  1. Get the buffer size required to configure the context
    IppsMontState
     by calling the function
    MontGetSize
    . For limited memory system, choose binary method, and otherwise, choose sliding window method. Using the binary method reduces the buffer size significantly while using sliding window method enhances the performance.
  2. Allocate working buffer through an operating system memory allocation function and configure the structure
    IppsMontState
     by calling the function
    MontInit
     with the allocated buffer and the choice made on the modular exponential method at time invoking
    MontGetSize
    .
  3. Call the function
    MontSet
     to set the integer big number module for
    IppsMontState
    .
  4. Call the function
    MontForm
     to convert the integer
    x
     to be its Montgomery form.
  5. Call the function
    MontExp
     to compute the Montgomery modular exponentiation.
  6. Call the function
    MontMul
     to compute the Montgomery modular multiplication of the above result with the integer 1 as to convert the above result back to the desired classical modular exponential result.
  7. Clean up secret data stored in the context.
  8. Free the memory using an operating system memory free function, if needed.

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.