recoding.c

Go to the documentation of this file.

//
// recoding.c   Algorithms for recoding the factors / exponents in various implementations
//
// Copyright (c) Microsoft Corporation. Licensed under the MIT license.
//
//
 
#include "precomp.h"
 
//
// The following is an adaptation of algorithm 6: "Protected
// odd-only recoding algorithm for the fixed-window representation"
// from the paper
//      "Selecting Elliptic Curves for Cryptography: An Efficiency and
//       Security Analysis" by Bos, Costello, Longa, and Naehrig
//
// Input:   odd integer k \in [1,GOrd], window width w>=2, and
//          t = ceil( GOrdBitsize / w-1 )
//
// Output:  (k_t, ... , k_0) where k_i \in {+-1, +-3, ..., +-(2^(w-1) -1)}
//
// Algorithm:
//          for i=0 to (t-1) do
//              k_i = (k mod 2^w) - 2^(w-1)
//              k = (k-k_i)/2^(w-1)
//          k_t = k mod 2^(w-1)
//          return (k_t, ..., k_0)
//
// Remarks:
//          1. An invariant of the main loop is that (k > 0 and k odd). This means
//             that all k_i's are odd and that k_t > 0.
//          2. We will store the values of k_i's as absolute values and signs in
//             absofKIs and sigofKIs arrays, resp. The sigofKIs[i] is 0xffffffff if
//             k_i < 0, otherwise it is 0.
//          3. In the multiplication algorithm we always access the precomputed point
//             P[(|k_i|-1)/2]. Therefore here we just shift the |k_i| value left by
//             one bit before storing it in absofKIs table.
//          4. Caller should check k in range [1,GOrd] to ensure use of recoding will
//             give correct results. This algorithm always recodes the t * (w-1) least
//             significant bits of the provided k, interpreted as an unsigned integer.
//
VOID
SYMCRYPT_CALL
SymCryptFixedWindowRecoding(
            UINT32          W,
    _Inout_ PSYMCRYPT_INT   piK,
    _Inout_ PSYMCRYPT_INT   piTmp,
    _Out_writes_( nRecodedDigits )
            PUINT32         absofKIs,
    _Out_writes_( nRecodedDigits )
            PUINT32         sigofKIs,
            UINT32          nRecodedDigits )
{
    UINT32 T1 = 0;
    UINT32 T2 = 0;
    UINT32 mask = ~(0xffffffff << W);       // Window mask = 2^w - 1 (e.g. 0x0000003f for w = 6)
    UINT32 smask = 0x1 << (W-1);            // Sign mask   = 2^(w-1) (e.g. 0x00000020 for w = 6)
 
    SYMCRYPT_ASSERT( W < 32 );
 
    for (UINT32 i=0; i < nRecodedDigits - 1; i++)
    {
        T1 = SymCryptIntGetValueLsbits32( piK ) & mask;         // T1 = k mod 2^W
 
        // At this point if the w-th bit of T1 is 1 then we know that T1 > 2^(w-1)
        // (Since k = odd is a loop invariant).
        //
        // In this case, (case A), T1 & ~smask is equal to (k mod 2^w) - 2^(w-1) = k_i = |k_i|.
        //
        // Otherwise, (case B), we know that T1 < 2^(w-1). Therefore 2^(w-1) - T1 = |k_i|.
 
        sigofKIs[i] = SYMCRYPT_MASK32_ZERO( T1 & smask );       // If the sign of k_i is - this mask is set to 0xffffffff. (Case B)
 
        T2 = T1 & ~smask;                                       // |k_i| in case A
        T1 = smask - T1;                                        // |k_i| in case B
 
        absofKIs[i] = ((T1 & sigofKIs[i]) | (T2 & ~sigofKIs[i])) >> 1; // Setting (masked) the absolute value of k_i in absofKIs (divided by 2)
 
        SymCryptIntSubUint32( piK, T2, piTmp );                 // This gives k - k_i in case (A)
        SymCryptIntAddUint32( piK, T1, piK );                   // This gives k - k_i in case (B)
 
        SymCryptIntMaskedCopy( piTmp, piK, ~sigofKIs[i] );      // Copy the result to piK in case (B)
 
        SymCryptIntDivPow2( piK, W-1, piK );                    // k := k / 2^(w-1)
    }
 
    // The last sign is positive given k < GOrd => k_t < 2^w
    sigofKIs[nRecodedDigits - 1] = 0;
    // Belts and braces, select only the bottom w-1 bits (ensure all absofKIs represent odd values in range [1,2^(w-1)-1])
    absofKIs[nRecodedDigits - 1] = (SymCryptIntGetValueLsbits32( piK ) & mask & ~smask) >> 1;
}
 
//
// The following is an algorithm for computing the width-w NAF of a positive integer.
//
// Input:   integer k \in [1,GOrd), window width w>=2, and nRecodedDigits = GOrdBitsize + 1
//
// Output:  (k_(nRecodedDigits-1), ... , k_0) where k_i \in {0, +-1, +-3, ..., +-(2^(w-1) -1)}
//
// Algorithm:
//          for i = 0 to (nRecodedDigits-1)
//              if (k is odd)
//                  k_i = (k mods 2^w)
//                  k = k - k_i
//              else
//                  k_i = 0
//              k = k/2
//          return (k_(nRecodedDigits-1), ..., k_0)
//
// Note: k mods 2^w is the integer u with (u == k mod 2^w) and (-2^(w-1) <= u < 2^(w-1) ).
//
// Remarks:
//          1. The above algorithm and the implementation are NOT SIDE-CHANNEL SAFE.
//             Therefore, it should only be used when the SYMCRYPT_FLAG_DATA_PUBLIC is
//             specified.
//          2. The multiplication algorithm uses |k_i|/2 as indexes. Therefore we will shift left
//             the absolute value of k_i by 1 bit and store only |k_i|/2.
//          3. Since now the k_i's can be zero we will store the following in sigofKIs:
//                  sigofKIs[i] = 0x00000001    if k_i > 0
//                  sigofKIs[i] = 0x00000000    if k_i = 0
//                  sigofKIs[i] = 0xffffffff    if k_i < 0
//
VOID
SYMCRYPT_CALL
SymCryptWidthNafRecoding(
            UINT32          W,
    _Inout_ PSYMCRYPT_INT   piK,
    _Out_writes_( nRecodedDigits )
            PUINT32         absofKIs,
    _Out_writes_( nRecodedDigits )
            PUINT32         sigofKIs,
            UINT32          nRecodedDigits )
{
    UINT32 T1 = 0;
    UINT32 mask = ~(0xffffffff << W);       // Window mask = 2^w - 1 (e.g. 0x0000003f for w = 6)
    UINT32 modulus = mask + 1;              // 2^w
    UINT32 smask = 0x1 << (W-1);            // Sign mask   = 2^(w-1) (e.g. 0x00000020 for w = 6)
 
    SYMCRYPT_ASSERT( W < 32 );
 
    for (UINT32 i=0; i < nRecodedDigits; i++)
    {
        T1 = SymCryptIntGetValueLsbits32( piK ) & mask;         // T1 = k mod 2^W
 
        if (T1 & 0x1)
        {
            if (T1 > smask)
            {
                sigofKIs[i] = 0xffffffff;
                absofKIs[i] = modulus - T1;                         // 2^W - T1 = |T1 - 2^W|
                SymCryptIntAddUint32( piK, absofKIs[i], piK );      // k-k_i
            }
            else
            {
                // Here (k mod 2^W) is already in the specified range
                sigofKIs[i] = 0x00000001;
                absofKIs[i] = T1;
                SymCryptIntSubUint32( piK, absofKIs[i], piK );      // k-k_i
            }
        }
        else
        {
            absofKIs[i] = 0;
            sigofKIs[i] = 0;
        }
 
        SymCryptIntDivPow2( piK, 1, piK );                      // k := k / 2
    }
}
 
//
// The following is an algorithm similar to the above
// but the output is only non-negative (odd) digits.
//
// Requirements:
//      nRecodedDigits == nBitsExp
//
VOID
SYMCRYPT_CALL
SymCryptPositiveWidthNafRecoding(
            UINT32          W,
    _In_    PCSYMCRYPT_INT  piK,
            UINT32          nBitsExp,
    _Out_writes_( nRecodedDigits )
            PUINT32         absofKIs,
            UINT32          nRecodedDigits )
{
    UINT32 T1 = 0;
    UINT32 cntrZ = W;       // Counter that specifies when we filled the last non-zero NAF digit
 
    SYMCRYPT_ASSERT( nRecodedDigits <= SymCryptIntBitsizeOfObject( piK ) );
 
    for (UINT32 i=0; i < nRecodedDigits; i++)
    {
        T1 = SymCryptIntGetBits( piK, i, SYMCRYPT_MIN(W, nBitsExp-i) );   // Get a batch of W bits (but don't go over nBitsExp)
 
        if ((cntrZ>=W) && ((T1 & 0x01) > 0))    // Only store odd digits
        {
            absofKIs[i] = T1;
            cntrZ = 0;
        }
        else
        {
            absofKIs[i] = 0;
        }
 
        cntrZ++;        // Prepare the counter for the next iteration
    }
}