gen_int.c File Reference

#include "precomp.h"

Include dependency graph for gen_int.c:

Go to the source code of this file.

Functions
UINT64 SYMCRYPT_CALL	SymCryptUint64Gcd (UINT64 a, UINT64 b, UINT32 flags)
VOID SYMCRYPT_CALL	SymCryptIntExtendedGcd (_In_ PCSYMCRYPT_INT piSrc1, _In_ PCSYMCRYPT_INT piSrc2, UINT32 flags, _Out_opt_ PSYMCRYPT_INT piGcd, _Out_opt_ PSYMCRYPT_INT piLcm, _Out_opt_ PSYMCRYPT_INT piInvSrc1ModSrc2, _Out_opt_ PSYMCRYPT_INT piInvSrc2ModSrc1, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)

Function Documentation

SymCryptIntExtendedGcd()

VOID SYMCRYPT_CALL SymCryptIntExtendedGcd	(	_In_ PCSYMCRYPT_INT	piSrc1,
		_In_ PCSYMCRYPT_INT	piSrc2,
		UINT32	flags,
		_Out_opt_ PSYMCRYPT_INT	piGcd,
		_Out_opt_ PSYMCRYPT_INT	piLcm,
		_Out_opt_ PSYMCRYPT_INT	piInvSrc1ModSrc2,
		_Out_opt_ PSYMCRYPT_INT	piInvSrc2ModSrc1,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 176 of file gen_int.c.

{
    UINT32 nDigits  = SYMCRYPT_MAX( SymCryptIntDigitsizeOfObject( piSrc1 ), SymCryptIntDigitsizeOfObject( piSrc2 ));
    PSYMCRYPT_INT       piA;        // size nDigits
    PSYMCRYPT_INT       piB;        // size nDigits, NOT ALLOCATED (part of the pdGcd divisor)
    PSYMCRYPT_INT       piTmp;      // size nDigits
    PSYMCRYPT_INT       piA1;       // size nDigits
    PSYMCRYPT_INT       piB1;       // size nDigits
    PSYMCRYPT_INT       piTmpDbl;   // size 2*nDigits
    PSYMCRYPT_DIVISOR   pdGcd;      // size nDigits
    PSYMCRYPT_DIVISOR   pdTmp;      // size nDigits
    UINT32              cbInt;
    UINT32              cbWideInt;
    UINT32              cbDivisor;
    SIZE_T              cbFnScratch;
    UINT32              t;
    UINT32              c;
    UINT32              d;
 
    UNREFERENCED_PARAMETER( flags );    // Currently not used to improve performance.
 
    // Compute how much scratch space we need for the functions we call
    cbFnScratch = SYMCRYPT_SCRATCH_BYTES_FOR_INT_DIVMOD( 2 * nDigits, nDigits );
    cbFnScratch = SYMCRYPT_MAX( cbFnScratch, SYMCRYPT_SCRATCH_BYTES_FOR_INT_MUL( 2*nDigits ) );
    cbFnScratch = SYMCRYPT_MAX( cbFnScratch, SYMCRYPT_SCRATCH_BYTES_FOR_INT_TO_DIVISOR( nDigits ) );
 
    cbInt = SymCryptSizeofIntFromDigits( nDigits );
    cbWideInt = SymCryptSizeofIntFromDigits( 2*nDigits );
    cbDivisor = SymCryptSizeofDivisorFromDigits( nDigits );
 
    SYMCRYPT_ASSERT( cbWideInt != 0 );
    SYMCRYPT_ASSERT( cbScratch >=   4 * cbInt +
                                    1 * cbWideInt +
                                    2 * cbDivisor +
                                    cbFnScratch );
 
    piA = SymCryptIntCreate( pbScratch, cbInt, nDigits );
    pbScratch += cbInt; cbScratch -= cbInt;
    // piB is stored inside the pdGcd object created later
    piTmp = SymCryptIntCreate( pbScratch, cbInt, nDigits );
    pbScratch += cbInt; cbScratch -= cbInt;
    piA1 = SymCryptIntCreate( pbScratch, cbInt, nDigits );
    pbScratch += cbInt; cbScratch -= cbInt;
    piB1 = SymCryptIntCreate( pbScratch, cbInt, nDigits );
    pbScratch += cbInt; cbScratch -= cbInt;
 
    piTmpDbl = SymCryptIntCreate( pbScratch, cbWideInt, 2 * nDigits );
    pbScratch += cbWideInt; cbScratch -= cbWideInt;
 
    pdGcd = SymCryptDivisorCreate( pbScratch, cbDivisor, nDigits );
    pbScratch += cbDivisor; cbScratch -= cbDivisor;
    piB = SymCryptIntFromDivisor( pdGcd );
 
    pdTmp = SymCryptDivisorCreate( pbScratch, cbDivisor, nDigits );
    pbScratch += cbDivisor; cbScratch -= cbDivisor;
 
    SymCryptIntCopyMixedSize( piSrc1, piA );    // Ignore the error return value here as we know
    SymCryptIntCopyMixedSize( piSrc2, piB );    // that the destination integers are large enough.
 
    SymCryptIntSetValueUint32( 1, piA1 );
    SymCryptIntSetValueUint32( 0, piB1 );
 
    // Currently not supported: Src1 to be 0 or Src2 to be even
    SYMCRYPT_ASSERT( !SymCryptIntIsEqualUint32( piA, 0 ) );
    SYMCRYPT_ASSERT( (SymCryptIntGetValueLsbits32( piB ) & 1) != 0 );
    if ( SymCryptIntIsEqualUint32( piA, 0 ) ||
        ((SymCryptIntGetValueLsbits32( piB ) & 1) == 0) )
    {
        goto cleanup;
    }
 
    // Currently not supported: piInvSrc2ModSrc1 != NULL and max( Src1.nDigits, Src2.nDigits ) * 2 > SymCryptDigitsFromBits(SYMCRYPT_INT_MAX_BITS)
    if( (piInvSrc2ModSrc1 != NULL) && (piTmpDbl == NULL) )
    {
        goto cleanup;
    }
 
    t = SymCryptIntBitsizeOfObject( piSrc1 ) + SymCryptIntBitsizeOfObject( piSrc2 ) - 1;
    while( t > 0 )
    {
        t--;
 
        //if A odd and A < B:
        //    Swap (A, A1) with (B, B1)
        c = 1 & (SymCryptIntGetValueLsbits32( piA ) & SymCryptIntSubSameSize( piA, piB, piTmp ) );
        SymCryptIntConditionalSwap( piA, piB, c );
        SymCryptIntConditionalSwap( piA1, piB1, c );
 
        //if A odd:
        //    A -= B;     A1 -= B1 (mod S2);
        c = 1 & SymCryptIntGetValueLsbits32( piA );
        SymCryptIntSubSameSize( piA, piB, piTmp );          // Never a carry due to the previous conditional swap
        SymCryptIntConditionalCopy( piTmp, piA, c );
 
        d = SymCryptIntSubSameSize( piA1, piB1, piTmp );
        SymCryptIntConditionalCopy( piTmp, piA1, c );
        SymCryptIntAddMixedSize( piA1, piSrc2, piTmp );
        SymCryptIntConditionalCopy( piTmp, piA1, c & d );
 
        // A /= 2;      A1 /= 2 (mod S2);
        SYMCRYPT_ASSERT( (SymCryptIntGetValueLsbits32( piA ) & 1) == 0 );
        SymCryptIntShr1( 0, piA, piA );
        c = SymCryptIntGetValueLsbits32( piA1 ) & 1;
        d = SymCryptIntAddMixedSize( piA1, piSrc2, piTmp );
        SymCryptIntConditionalCopy( piTmp, piA1, c );
        SymCryptIntShr1( c & d, piA1, piA1 );
 
    }
 
    // B = GCD, B1 * S1 = GCD (mod S2)
    // A = 0, A1 is scratch
    //
    // Algorithm from here:
    // GCD as divisor
    // LCM = S1 * S2 / GCD.
    // P2 = S2 / GCD, as divisor (only for InvS1ModS2)
    // InvS1ModS2 = B1 mod P2
    // InvS2ModS1 = -((B1*S1 - GCD) div S2) mod S1
 
    if( piGcd != NULL )
    {
        SymCryptIntCopyMixedSize( piB, piGcd );
    }
 
    if( piLcm == NULL && piInvSrc1ModSrc2 == NULL && piInvSrc2ModSrc1 == NULL )
    {
        // Only GCD needed; don't do the other work
        goto cleanup;
    }
 
    SymCryptIntCopyMixedSize( piB, SymCryptIntFromDivisor( pdGcd ) );                // copy into INT of the right size
 
    // IntToDivisor requirement:
    //      Gcd !=0
    SymCryptIntToDivisor( SymCryptIntFromDivisor( pdGcd ), pdGcd, 3, 0, pbScratch, cbScratch );
 
    if( piLcm != NULL )
    {
        // LCM = S1 * S2 / GCD
        SymCryptIntMulMixedSize( piSrc1, piSrc2, piLcm, pbScratch, cbScratch );
        SymCryptIntDivMod( piLcm, pdGcd, piLcm, NULL, pbScratch, cbScratch );
    }
 
    if( piInvSrc1ModSrc2 != NULL )
    {
        // Future optimization: if GCD == 1 then we can just copy B1.
        SymCryptIntDivMod( piSrc2, pdGcd, SymCryptIntFromDivisor( pdTmp ), NULL, pbScratch, cbScratch );
 
        // IntToDivisor requirement:
        //      Src2 / pdGcd > 0
        SymCryptIntToDivisor( SymCryptIntFromDivisor( pdTmp ), pdTmp, 1, 0, pbScratch, cbScratch );
        SymCryptIntDivMod( piB1, pdTmp, NULL, piInvSrc1ModSrc2, pbScratch, cbScratch );
    }
 
    if( piInvSrc2ModSrc1 != NULL )
    {
        //  InvS2ModS1 = - ( (B1*S1 - GCD)/S2 ) mod S1
 
        // S2 as divisor
        SymCryptIntCopyMixedSize( piSrc2, SymCryptIntFromDivisor( pdTmp ) );
 
        // IntToDivisor requirement:
        //      Src2 is odd --> Src2 != 0
        SymCryptIntToDivisor( SymCryptIntFromDivisor( pdTmp ), pdTmp, 1, 0, pbScratch, cbScratch );
 
        SymCryptIntMulMixedSize( piB1, piSrc1, piTmpDbl, pbScratch, cbScratch );
        SymCryptIntSubMixedSize( piTmpDbl, piB, piTmpDbl );     // Never a borrow if B1 >= 1
        SymCryptIntDivMod( piTmpDbl, pdTmp, piTmpDbl, NULL, pbScratch, cbScratch );
 
        // and reduce modulo S1
        SymCryptIntCopyMixedSize( piSrc1, SymCryptIntFromDivisor( pdTmp ) );
 
        // IntToDivisor requirement:
        //      Src1 > 0
        SymCryptIntToDivisor( SymCryptIntFromDivisor( pdTmp ), pdTmp, 1, 0, pbScratch, cbScratch );
        SymCryptIntDivMod( piTmpDbl, pdTmp, NULL, piInvSrc2ModSrc1, pbScratch, cbScratch );
 
        // Negative modulo S1
        SymCryptIntSubMixedSize( SymCryptIntFromDivisor( pdTmp ), piInvSrc2ModSrc1, piInvSrc2ModSrc1 );   // Never a borrow as piInvSrc2ModSrc1 < S1
    }
 
cleanup:
    return; // Need a statement after a label...
}

Referenced by SymCryptCrtGenerateForTwoCoprimes(), SymCryptRsakeyCalculatePrimesFromPrivateExponent(), and SymCryptRsakeyCalculatePrivateFields().

SymCryptUint64Gcd()

UINT64 SYMCRYPT_CALL SymCryptUint64Gcd	(	UINT64	a,
		UINT64	b,
		UINT32	flags
	)

Definition at line 12 of file gen_int.c.

{
    UINT64 swap;
    UINT64 tmp;
    UINT64 a2;
    UINT64 b2;
    UINT32 i;
 
/*
    Algorithm outline:
 
    if( b even )
        swap (a,b)
 
 loop:
    { invariant: b is odd }
    if( a even )
        a = a/2
    else
        if a < b
            swap (a,b)
        a = (a - b) / 2
 
    We ignore the data_public flag as we currently always use a side-channel safe implementation
 
    to compute (a < b) on 64-bit values is hard if we want to avoid
*/
    SYMCRYPT_ASSERT( (flags & SYMCRYPT_FLAG_GCD_INPUTS_NOT_BOTH_EVEN) != 0 && ((a | b) & 1) != 0 );
    UNREFERENCED_PARAMETER( flags );
 
    // First we make sure that b is odd
    // If b even: swap (a,b)
    swap = ~(0 - (b & 1));
    tmp = (a ^ b) & swap;
    a ^= tmp;
    b ^= tmp;
 
    // Each loop iteration reduces len(a) + len(b) by at least 1, so looping 127 times is enough.
    // For inputs (2^63, 2^63 + 1) we get 63 iterations to reduce a to 1, and then another 63 to get
    // the other value to 1, plus one more to make it 0.
    for( i=0; i < 127; i++ )
    {
        // Compute the result of the 'else' part of the if( a even ) into (a2, b2)
        // First we evaluate (a < b), which is a bit tricky without access to the carry flag.
        // a < b =      (b>>63) if ((a^b) >> 63) == 1
        //              (a - b) >> 63 otherwise
        tmp = a ^ b;
        tmp = (tmp & b) | (~tmp & (a-b));
        swap = 0 - (tmp >> 63);
 
        // Now swap if a < b into (a2, b2)
        tmp = (a ^ b) & swap;
        a2 = a ^ tmp;
        b2 = b ^ tmp;
 
        //
        a2 = (a2 - b2) / 2;
 
        // Compute the (a is odd) condition
        tmp = 0 - (a & 1);
 
        // Assemble the final result
        a = (tmp & a2) | (~tmp & a/2);
        b = (tmp & b2) | (~tmp & b);
    }
 
    SYMCRYPT_ASSERT( a == 0 );
    return b;
}

Referenced by SymCryptIntGenerateRandomPrime().