ec_montgomery.c File Reference

#include "precomp.h"

Include dependency graph for ec_montgomery.c:

Go to the source code of this file.

Functions
VOID SYMCRYPT_CALL	SymCryptMontgomeryFillScratchSpaces (_In_ PSYMCRYPT_ECURVE pCurve)
VOID SYMCRYPT_CALL	SymCryptMontgomerySetDistinguished (_In_ PCSYMCRYPT_ECURVE pCurve, _Out_ PSYMCRYPT_ECPOINT poDst, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)
UINT32 SYMCRYPT_CALL	SymCryptMontgomeryIsEqual (_In_ PCSYMCRYPT_ECURVE pCurve, _In_ PCSYMCRYPT_ECPOINT poSrc1, _In_ PCSYMCRYPT_ECPOINT poSrc2, UINT32 flags, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)
UINT32 SYMCRYPT_CALL	SymCryptMontgomeryIsZero (_In_ PCSYMCRYPT_ECURVE pCurve, _In_ PCSYMCRYPT_ECPOINT poSrc, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)
VOID	SymCryptMontgomeryDoubleAndAdd (_In_ PCSYMCRYPT_MODULUS pmMod, _In_ PCSYMCRYPT_MODELEMENT peX1, _In_opt_ PCSYMCRYPT_MODELEMENT peZ1, _In_ PCSYMCRYPT_MODELEMENT peA24, _Inout_ PSYMCRYPT_MODELEMENT peX2, _Inout_ PSYMCRYPT_MODELEMENT peZ2, _Inout_ PSYMCRYPT_MODELEMENT peX3, _Inout_ PSYMCRYPT_MODELEMENT peZ3, _Inout_ PSYMCRYPT_MODELEMENT peTemp1, _Inout_ PSYMCRYPT_MODELEMENT peTemp2, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)
SYMCRYPT_ERROR SYMCRYPT_CALL	SymCryptMontgomeryPointScalarMul (_In_ PCSYMCRYPT_ECURVE pCurve, _In_ PCSYMCRYPT_INT piScalar, _In_opt_ PCSYMCRYPT_ECPOINT poSrc, UINT32 flags, _Out_ PSYMCRYPT_ECPOINT poDst, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)

Function Documentation

SymCryptMontgomeryDoubleAndAdd()

VOID SymCryptMontgomeryDoubleAndAdd	(	_In_ PCSYMCRYPT_MODULUS	pmMod,
		_In_ PCSYMCRYPT_MODELEMENT	peX1,
		_In_opt_ PCSYMCRYPT_MODELEMENT	peZ1,
		_In_ PCSYMCRYPT_MODELEMENT	peA24,
		_Inout_ PSYMCRYPT_MODELEMENT	peX2,
		_Inout_ PSYMCRYPT_MODELEMENT	peZ2,
		_Inout_ PSYMCRYPT_MODELEMENT	peX3,
		_Inout_ PSYMCRYPT_MODELEMENT	peZ3,
		_Inout_ PSYMCRYPT_MODELEMENT	peTemp1,
		_Inout_ PSYMCRYPT_MODELEMENT	peTemp2,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 151 of file ec_montgomery.c.

{
    // Temp1 =          A = X2 + Z2
    SymCryptModAdd( pmMod, peX2, peZ2, peTemp1, pbScratch, cbScratch );
 
    // Z2 =             B = X2 - Z2
    SymCryptModSub( pmMod, peX2, peZ2, peZ2, pbScratch, cbScratch );
 
    // Temp2 =          C = X3 + Z3
    SymCryptModAdd( pmMod, peX3, peZ3, peTemp2, pbScratch, cbScratch );
 
    // Z3 =             D = X3 - Z3
    SymCryptModSub( pmMod, peX3, peZ3, peZ3, pbScratch, cbScratch );
 
    // X3 =             CB = C * B      = Temp2 * Z2
    SymCryptModMul( pmMod, peTemp2, peZ2, peX3, pbScratch, cbScratch );
 
    // Z3 =             DA = D * A      = Z3 * Temp1
    SymCryptModMul( pmMod, peZ3, peTemp1, peZ3, pbScratch, cbScratch );
 
    // From this point on, the outputs (X5,Z5) depend only on (X3,Z3) and (X1,Z1)
    // and the outputs (X4,Z4) only on (Temp1,Z2) and A24
    // We'll do the (X4,Z4) first
 
    // X2 =             AA = A * A      = Temp1 * Temp1
    SymCryptModSquare( pmMod, peTemp1, peX2, pbScratch, cbScratch );
 
    // Temp1 =          BB = B * B      = Z2 * Z2
    SymCryptModSquare( pmMod, peZ2, peTemp1, pbScratch, cbScratch );
 
    // Temp2 =          E = AA - BB     = X2 - Temp1
    SymCryptModSub( pmMod, peX2, peTemp1, peTemp2, pbScratch, cbScratch );
 
    // X2 =             X4 = AA * BB    = X2 * Temp1
    SymCryptModMul( pmMod, peX2, peTemp1, peX2, pbScratch, cbScratch );
 
    // Z2 =             A24E = A24 * E    = A24 * Temp2
    SymCryptModMul( pmMod, peA24, peTemp2, peZ2, pbScratch, cbScratch );
 
    // Z2 =             BAE = (BB + a24 * E) = BB + A24E = Temp1 + Z2
    SymCryptModAdd( pmMod, peTemp1, peZ2, peZ2, pbScratch, cbScratch );
 
    // Z2 =             Z4 = E * BAE        = Temp2 + Z2
    SymCryptModMul( pmMod, peTemp2, peZ2, peZ2, pbScratch, cbScratch );
 
    // Now we compute (X5, Z5)
 
    // Temp1 =          DApCB = DA + CB     = Z3 + X3
    SymCryptModAdd( pmMod, peZ3, peX3, peTemp1, pbScratch, cbScratch );
 
    // Z3 =             DAmCB = DA - CB     = Z3 - X3
    SymCryptModSub( pmMod, peZ3, peX3, peZ3, pbScratch, cbScratch );
 
    // X3 =             DApCB^2 = Temp1 ^ 2 ( = X5 when (peZ1 == NULL) => Z1 == 1)
    SymCryptModSquare( pmMod, peTemp1, peX3, pbScratch, cbScratch );
 
    if (peZ1 != NULL) // source point is not normalized
    {
    // X3 =             X5 = Z1 * DApCB^2   = Z1 * X3
    SymCryptModMul( pmMod, peZ1, peX3, peX3, pbScratch, cbScratch );
    }
 
    // Z3 =             DAmCB2 = DAmCB ^ 2  = Z3 ^ 2
    SymCryptModSquare( pmMod, peZ3, peZ3, pbScratch, cbScratch );
 
    // Z3 =             Z5 = X1 * DAmCB2        = X1 * Z3
    SymCryptModMul( pmMod, peX1, peZ3, peZ3, pbScratch, cbScratch );
}

Referenced by SymCryptMontgomeryPointScalarMul().

SymCryptMontgomeryFillScratchSpaces()

VOID SYMCRYPT_CALL SymCryptMontgomeryFillScratchSpaces

(

_In_ PSYMCRYPT_ECURVE

pCurve

)

Definition at line 11 of file ec_montgomery.c.

{
    UINT32 nDigits = SymCryptDigitsFromBits( pCurve->FModBitsize );
    UINT32 nBytes = SymCryptSizeofModElementFromModulus( pCurve->FMod );
    UINT32 nCommon = SYMCRYPT_MAX( SymCryptSizeofIntFromDigits( nDigits ), SYMCRYPT_MAX( SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( nDigits ), SYMCRYPT_SCRATCH_BYTES_FOR_MODINV( nDigits ) ) );
    UINT32 cbModElement = pCurve->cbModElement;
    UINT32 nDigitsFieldLength = pCurve->FModDigits;
 
    //
    // All the scratch space computations are upper bounded by the SizeofXXX bound (2^19) and
    // the SCRATCH_BYTES_FOR_XXX bound (2^24) (see symcrypt_internal.h).
    //
    // One caveat is SymCryptSizeofEcpointFromCurve and SymCryptSizeofEcpointEx which calculate the
    // size of EcPoint with 4 coordinates (each one a modelement of max size 2^17). Thus upper
    // bounded by 2^20.
    //
 
    pCurve->cbScratchCommon = nCommon;
    pCurve->cbScratchScalar =
        SymCryptSizeofIntFromDigits(nDigits) +
        6 * nBytes +
        nCommon;
 
    pCurve->cbScratchScalarMulti = 0;
    pCurve->cbScratchGetSetValue =
        SymCryptSizeofEcpointEx( cbModElement, SYMCRYPT_ECPOINT_FORMAT_MAX_LENGTH ) +
        2 * cbModElement +
        SYMCRYPT_MAX( SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( nDigitsFieldLength ),
             SYMCRYPT_SCRATCH_BYTES_FOR_MODINV( nDigitsFieldLength ) );
 
    pCurve->cbScratchGetSetValue = SYMCRYPT_MAX( pCurve->cbScratchGetSetValue, SymCryptSizeofIntFromDigits( nDigits ) );
 
    pCurve->cbScratchEckey =
        SYMCRYPT_MAX( cbModElement + SymCryptSizeofIntFromDigits(SymCryptEcurveDigitsofScalarMultiplier(pCurve)),
            SymCryptSizeofEcpointFromCurve( pCurve ) ) +
        SYMCRYPT_MAX( pCurve->cbScratchScalar, pCurve->cbScratchGetSetValue );
}

SymCryptMontgomeryIsEqual()

UINT32 SYMCRYPT_CALL SymCryptMontgomeryIsEqual	(	_In_ PCSYMCRYPT_ECURVE	pCurve,
		_In_ PCSYMCRYPT_ECPOINT	poSrc1,
		_In_ PCSYMCRYPT_ECPOINT	poSrc2,
		UINT32	flags,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 78 of file ec_montgomery.c.

{
    PSYMCRYPT_MODELEMENT  peTemp[2];
    PSYMCRYPT_MODELEMENT  peSrc1X, peSrc1Z;
    PSYMCRYPT_MODELEMENT  peSrc2X, peSrc2Z;
    PSYMCRYPT_MODULUS     pmMod = pCurve->FMod;
    SIZE_T nBytes;
 
    SYMCRYPT_ASSERT( (flags & ~(SYMCRYPT_FLAG_ECPOINT_EQUAL|SYMCRYPT_FLAG_ECPOINT_NEG_EQUAL)) == 0 );
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_MONTGOMERY_TYPE(pCurve) );
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc1->pCurve) && SymCryptEcurveIsSame(pCurve, poSrc2->pCurve) );
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_INTERNAL_SCRATCH_BYTES_FOR_COMMON_ECURVE_OPERATIONS( pCurve ) );
 
    UNREFERENCED_PARAMETER( flags );
 
    nBytes = SymCryptSizeofModElementFromModulus( pmMod );
 
    SYMCRYPT_ASSERT( cbScratch >= 2 * nBytes );
 
    for (UINT32 i = 0; i < 2; ++i)
    {
        peTemp[i] = SymCryptModElementCreate( pbScratch, nBytes, pmMod );
        pbScratch += nBytes;
        cbScratch -= nBytes;
    }
 
    peSrc1X = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc1 );
    peSrc1Z = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc1 );
 
    peSrc2X = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc2 );
    peSrc2Z = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc2 );
 
    // peTemp[0] = X1 * Z2
    SymCryptModMul( pmMod, peSrc1X, peSrc2Z, peTemp[0], pbScratch, cbScratch );
 
    // peTemp[1] = X2 * Z1
    SymCryptModMul( pmMod, peSrc2X, peSrc1Z, peTemp[1], pbScratch, cbScratch );
 
    return SymCryptModElementIsEqual( pmMod, peTemp[0], peTemp[1] );
}

SymCryptMontgomeryIsZero()

UINT32 SYMCRYPT_CALL SymCryptMontgomeryIsZero	(	_In_ PCSYMCRYPT_ECURVE	pCurve,
		_In_ PCSYMCRYPT_ECPOINT	poSrc,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 128 of file ec_montgomery.c.

{
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
    PSYMCRYPT_MODELEMENT peZ = NULL;    // Pointer to Z
 
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_MONTGOMERY_TYPE(pCurve) );
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc->pCurve) );
 
    UNREFERENCED_PARAMETER( pbScratch );
    UNREFERENCED_PARAMETER( cbScratch );
 
    // Getting pointer to Z of the source point
    peZ = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1,  pCurve, poSrc );
 
    return SymCryptModElementIsZero( FMod, peZ );
}

SymCryptMontgomeryPointScalarMul()

SYMCRYPT_ERROR SYMCRYPT_CALL SymCryptMontgomeryPointScalarMul	(	_In_ PCSYMCRYPT_ECURVE	pCurve,
		_In_ PCSYMCRYPT_INT	piScalar,
		_In_opt_ PCSYMCRYPT_ECPOINT	poSrc,
		UINT32	flags,
		_Out_ PSYMCRYPT_ECPOINT	poDst,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 297 of file ec_montgomery.c.

{
    SYMCRYPT_ERROR        scError = SYMCRYPT_NO_ERROR;
 
    PSYMCRYPT_MODULUS     pmMod;
    PSYMCRYPT_MODELEMENT  peX1, peZ1, peA24, peX2, peZ2, peX3, peZ3, peTemp1, peTemp2, peResult;
    UINT32                i, nBytes, nDigits, cond, newcond, nCommon;
    PBYTE                 pBegin;
    SIZE_T                cbAllScratch;
 
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_MONTGOMERY_TYPE(pCurve) );
    SYMCRYPT_ASSERT( (poSrc == NULL || SymCryptEcurveIsSame(pCurve, poSrc->pCurve)) && SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
 
    // Make sure we only specify the correct flags
    if ((flags & ~SYMCRYPT_FLAG_ECC_LL_COFACTOR_MUL) != 0)
    {
        scError = SYMCRYPT_INVALID_ARGUMENT;
        goto cleanup;
    }
 
    if (poSrc == NULL)
    {
        poSrc = pCurve->G;
    }
 
    //
    // Set up structure for X2, Z2, X3, Z3, Temp1, and Temp2, and the scratch space.
    //
    pmMod = pCurve->FMod;
 
    nDigits = SymCryptDigitsFromBits( pCurve->FModBitsize );
    nBytes = SymCryptSizeofModElementFromModulus( pmMod );
    nCommon = SYMCRYPT_MAX( SymCryptSizeofIntFromDigits(nDigits), SYMCRYPT_MAX(SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS(nDigits), SYMCRYPT_SCRATCH_BYTES_FOR_MODINV(nDigits)));
 
    SYMCRYPT_ASSERT( cbScratch >= 6 * nBytes + nCommon );
 
    cbAllScratch = cbScratch;
    pBegin = pbScratch;
 
    //
    // Create mod elements
    //
    peX2 = SymCryptModElementCreate( pbScratch, nBytes, pmMod );
    pbScratch += nBytes;
 
    peZ2 = SymCryptModElementCreate( pbScratch, nBytes, pmMod );
    pbScratch += nBytes;
 
    peX3 = SymCryptModElementCreate( pbScratch, nBytes, pmMod );
    pbScratch += nBytes;
 
    peZ3 = SymCryptModElementCreate( pbScratch, nBytes, pmMod );
    pbScratch += nBytes;
 
    peTemp1 = SymCryptModElementCreate( pbScratch, nBytes, pmMod );
    pbScratch += nBytes;
 
    peTemp2 = SymCryptModElementCreate( pbScratch, nBytes, pmMod );
    pbScratch += nBytes;
 
    cbScratch = nCommon;
 
    //
    // Set up values
    //
 
    peA24 = pCurve->A;
 
    // X1 = X, Z1 = Z
    peX1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc);
    peZ1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc);
 
    // X2 = 1, Z2 = 0, X3 = X, Z3 = Z
    SymCryptModElementSetValueUint32( 1, pmMod, peX2, pbScratch, cbScratch );
    SymCryptModElementSetValueUint32( 0, pmMod, peZ2, pbScratch, cbScratch );
    SymCryptModElementCopy( pmMod, peX1, peX3 );
    SymCryptModElementCopy( pmMod, peZ1, peZ3 );
 
    if ( poSrc->normalized )
    {
        // Set peZ1 to NULL to avoid redundant multiplications in SymCryptMontgomeryDoubleAndAdd
        peZ1 = NULL;
    }
 
    //
    //  Montgomery ladder scalar multiplication
    //
 
    i = (pCurve->GOrdBitsize + pCurve->coFactorPower);
    cond = 0;
    while ( i != 0 )
    {
        // If cond = 0, we have (X2, Z2, X3, Z3)
        // if cond = 1, we have (X3, Z3, X2, Z2)
        i--;
        newcond = SymCryptIntGetBit( piScalar, i );
        cond ^= newcond;
 
        SymCryptModElementConditionalSwap( pmMod, peX2, peX3, cond);
        SymCryptModElementConditionalSwap( pmMod, peZ2, peZ3, cond);
 
        cond = newcond;
 
        SymCryptMontgomeryDoubleAndAdd( pmMod, peX1, peZ1, peA24, peX2, peZ2, peX3, peZ3, peTemp1, peTemp2, pbScratch, cbScratch );
    }
 
    // Now put them back in the normal order
    SymCryptModElementConditionalSwap( pmMod, peX2, peX3, cond);
    SymCryptModElementConditionalSwap( pmMod, peZ2, peZ3, cond);
 
    // Multiply by the cofactor (if needed) by continuing the doubling
    if ((flags & SYMCRYPT_FLAG_ECC_LL_COFACTOR_MUL) != 0)
    {
        i = pCurve->coFactorPower;
        while (i!=0)
        {
            i--;
            // We only use the doubling output here, so we definitely don't need to provide Z1
            // We could refactor to have a separate SymCryptMontgomeryDouble function but for Curve25519 this loop is ~1% of runtime
            SymCryptMontgomeryDoubleAndAdd( pmMod, peX1, NULL, peA24, peX2, peZ2, peX3, peZ3, peTemp1, peTemp2, pbScratch, cbScratch );
        }
    }
 
    // Set X coordinate
    peResult = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poDst);
    SymCryptModElementCopy( pCurve->FMod, peX2, peResult );
 
    // Set Z coordinate
    peResult = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poDst);
    SymCryptModElementCopy( pCurve->FMod, peZ2, peResult );
 
    poDst->normalized = FALSE;
 
    scError = SYMCRYPT_NO_ERROR;
 
cleanup:
    return scError;
}

SymCryptMontgomerySetDistinguished()

VOID SYMCRYPT_CALL SymCryptMontgomerySetDistinguished	(	_In_ PCSYMCRYPT_ECURVE	pCurve,
		_Out_ PSYMCRYPT_ECPOINT	poDst,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 51 of file ec_montgomery.c.

{
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_MONTGOMERY_TYPE(pCurve) );
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
 
    UNREFERENCED_PARAMETER( pbScratch );
    UNREFERENCED_PARAMETER( cbScratch );
 
    SymCryptEcpointCopy( pCurve, pCurve->G, poDst );
}