crt.c File Reference

#include "precomp.h"

Include dependency graph for crt.c:

Go to the source code of this file.

Functions
SYMCRYPT_ERROR SYMCRYPT_CALL	SymCryptCrtGenerateForTwoCoprimes (_In_ PCSYMCRYPT_MODULUS pmP, _In_ PCSYMCRYPT_MODULUS pmQ, UINT32 flags, _Out_ PSYMCRYPT_MODELEMENT peInvQModP, _Out_ PSYMCRYPT_MODELEMENT peInvPModQ, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)
SYMCRYPT_ERROR SYMCRYPT_CALL	SymCryptCrtGenerateInverses (UINT32 nCoprimes, _In_reads_(nCoprimes) PCSYMCRYPT_MODULUS *ppmCoprimes, UINT32 flags, _Out_writes_(nCoprimes) PSYMCRYPT_MODELEMENT *ppeCrtInverses, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)
SYMCRYPT_ERROR SYMCRYPT_CALL	SymCryptCrtSolve (UINT32 nCoprimes, _In_reads_(nCoprimes) PCSYMCRYPT_MODULUS *ppmCoprimes, _In_reads_(nCoprimes) PCSYMCRYPT_MODELEMENT *ppeCrtInverses, _In_reads_(nCoprimes) PCSYMCRYPT_MODELEMENT *ppeCrtRemainders, UINT32 flags, _Out_ PSYMCRYPT_INT piSolution, _Out_writes_bytes_(cbScratch) PBYTE pbScratch, SIZE_T cbScratch)

Function Documentation

SymCryptCrtGenerateForTwoCoprimes()

SYMCRYPT_ERROR SYMCRYPT_CALL SymCryptCrtGenerateForTwoCoprimes	(	_In_ PCSYMCRYPT_MODULUS	pmP,
		_In_ PCSYMCRYPT_MODULUS	pmQ,
		UINT32	flags,
		_Out_ PSYMCRYPT_MODELEMENT	peInvQModP,
		_Out_ PSYMCRYPT_MODELEMENT	peInvPModQ,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 11 of file crt.c.

{
    SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR;
 
    PCSYMCRYPT_INT  piSrc1 = NULL;
    PCSYMCRYPT_INT  piSrc2 = NULL;
 
    PSYMCRYPT_INT   piInvSrc1ModSrc2 = NULL;
    PSYMCRYPT_INT   piInvSrc2ModSrc1 = NULL;
 
    UINT32 nDigits = 0;
    UINT32 cbInt = 0;
 
    BOOLEAN oddP = FALSE;
 
    SYMCRYPT_ASSERT( pmP != NULL );
    SYMCRYPT_ASSERT( pmQ != NULL );
 
    nDigits = SYMCRYPT_MAX( SymCryptModulusDigitsizeOfObject( pmP ), SymCryptModulusDigitsizeOfObject( pmQ ));
 
    // Create two temporary integers
    cbInt = SymCryptSizeofIntFromDigits( nDigits );
 
    SYMCRYPT_ASSERT( cbScratch >= 2*cbInt + SYMCRYPT_SCRATCH_BYTES_FOR_EXTENDED_GCD( nDigits ));
 
    piInvSrc1ModSrc2 = SymCryptIntCreate( pbScratch, cbInt, nDigits ); pbScratch += cbInt; cbScratch -= cbInt;
    piInvSrc2ModSrc1 = SymCryptIntCreate( pbScratch, cbInt, nDigits ); pbScratch += cbInt; cbScratch -= cbInt;
 
    oddP = ((SymCryptIntGetValueLsbits32(SymCryptIntFromModulus( (PSYMCRYPT_MODULUS) pmP )) & 1) == 1);
    if (oddP)
    {
        piSrc1 = SymCryptIntFromModulus( (PSYMCRYPT_MODULUS) pmQ );
        piSrc2 = SymCryptIntFromModulus( (PSYMCRYPT_MODULUS) pmP );
    }
    else
    {
        piSrc1 = SymCryptIntFromModulus( (PSYMCRYPT_MODULUS) pmP );
        piSrc2 = SymCryptIntFromModulus( (PSYMCRYPT_MODULUS) pmQ );
    }
 
    // IntExtendedGcd requirements:
    //      - First argument > 0
    //      - Second argument odd
    if( SymCryptIntIsEqualUint32(piSrc1, 0) ||
        ((SymCryptIntGetValueLsbits32(piSrc2) & 1) != 1) )
    {
        scError = SYMCRYPT_INVALID_ARGUMENT;
        goto cleanup;
    }
 
    // Extended GCD
    SymCryptIntExtendedGcd( piSrc1, piSrc2, flags, NULL, NULL, piInvSrc1ModSrc2, piInvSrc2ModSrc1, pbScratch, cbScratch );
 
    if (oddP)
    {
        SymCryptIntToModElement( piInvSrc2ModSrc1, pmQ, peInvPModQ, pbScratch, cbScratch );
        SymCryptIntToModElement( piInvSrc1ModSrc2, pmP, peInvQModP, pbScratch, cbScratch );
    }
    else
    {
        SymCryptIntToModElement( piInvSrc2ModSrc1, pmP, peInvQModP, pbScratch, cbScratch );
        SymCryptIntToModElement( piInvSrc1ModSrc2, pmQ, peInvPModQ, pbScratch, cbScratch );
    }
 
cleanup:
    return scError;
}

Referenced by SymCryptCrtGenerateInverses().

SymCryptCrtGenerateInverses()

SYMCRYPT_ERROR SYMCRYPT_CALL SymCryptCrtGenerateInverses	(	UINT32	nCoprimes,
		_In_reads_(nCoprimes) PCSYMCRYPT_MODULUS *	ppmCoprimes,
		UINT32	flags,
		_Out_writes_(nCoprimes) PSYMCRYPT_MODELEMENT *	ppeCrtInverses,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 90 of file crt.c.

{
    SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR;
 
    if (nCoprimes == 2)
    {
        SymCryptCrtGenerateForTwoCoprimes(
                ppmCoprimes[0],
                ppmCoprimes[1],
                flags,
                ppeCrtInverses[0],
                ppeCrtInverses[1],
                pbScratch,
                cbScratch );
    }
    else
    {
        scError = SYMCRYPT_INVALID_ARGUMENT;
        goto cleanup;
    }
 
cleanup:
    return scError;
}

Referenced by SymCryptRsakeyCalculatePrivateFields().

SymCryptCrtSolve()

SYMCRYPT_ERROR SYMCRYPT_CALL SymCryptCrtSolve	(	UINT32	nCoprimes,
		_In_reads_(nCoprimes) PCSYMCRYPT_MODULUS *	ppmCoprimes,
		_In_reads_(nCoprimes) PCSYMCRYPT_MODELEMENT *	ppeCrtInverses,
		_In_reads_(nCoprimes) PCSYMCRYPT_MODELEMENT *	ppeCrtRemainders,
		UINT32	flags,
		_Out_ PSYMCRYPT_INT	piSolution,
		_Out_writes_bytes_(cbScratch) PBYTE	pbScratch,
		SIZE_T	cbScratch
	)

Definition at line 123 of file crt.c.

{
    SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR;
 
    SYMCRYPT_ASSERT( nCoprimes >= 2 );
 
    PSYMCRYPT_INT  piTmp = NULL;
    PSYMCRYPT_MODELEMENT peTmp = NULL;
 
    PSYMCRYPT_INT  piDouble = NULL;
 
    UINT32 nDigitsMax = 0;
 
    UINT32 cbInt = 0;
    UINT32 cbModElement = 0;
    UINT32 cbDouble = 0;
 
    UINT32 carry = 0;
 
    UNREFERENCED_PARAMETER( flags );
 
    nDigitsMax = SYMCRYPT_MAX( SymCryptModulusDigitsizeOfObject( ppmCoprimes[0] ), SymCryptModulusDigitsizeOfObject( ppmCoprimes[1] ) );
 
    cbInt = SymCryptSizeofIntFromDigits( nDigitsMax );
    cbModElement = SymCryptSizeofModElementFromModulus( ppmCoprimes[0] );
    cbDouble = SymCryptSizeofIntFromDigits( 2*nDigitsMax );
 
    if( cbDouble == 0 )
    {
        // It is possible that cbDouble would not fit within the maximum integer
        scError = SYMCRYPT_INVALID_ARGUMENT;
        goto cleanup;
    }
 
    SYMCRYPT_ASSERT( cbScratch >= cbInt + cbModElement + cbDouble +
                                  SYMCRYPT_MAX( SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( nDigitsMax ),
                                       SYMCRYPT_SCRATCH_BYTES_FOR_INT_MUL( 2*nDigitsMax ) )
                    );
 
    // Create temporaries
    piTmp = SymCryptIntCreate( pbScratch, cbInt, nDigitsMax ); pbScratch += cbInt; cbScratch -= cbInt;
 
    peTmp = SymCryptModElementCreate( pbScratch, cbModElement, ppmCoprimes[0] ); pbScratch += cbModElement; cbScratch -= cbModElement;
 
    piDouble = SymCryptIntCreate( pbScratch, cbDouble, 2*nDigitsMax ); pbScratch += cbDouble; cbScratch -= cbDouble;
 
    if (nCoprimes == 2)
    {
        //
        // Let r0 and r1 be the two remainders modulo p and q respectively
        // Then we calculate (q^{-1}(r0 - r1) mod p)*q + r1
        //
        SymCryptModElementToInt( ppmCoprimes[1], ppeCrtRemainders[1], piTmp, pbScratch, cbScratch );               // Convert r1 to Int
        SymCryptIntToModElement( piTmp, ppmCoprimes[0], peTmp, pbScratch, cbScratch );                             // Convert it to r1 mod p
 
        SymCryptModSub( ppmCoprimes[0], ppeCrtRemainders[0], peTmp, peTmp, pbScratch, cbScratch );                 // (r0 - r1) mod p
        SymCryptModMul( ppmCoprimes[0], ppeCrtInverses[0], peTmp, peTmp, pbScratch, cbScratch );                   // q^{-1}*(r0 - r1) mod p
        SymCryptModElementToInt( ppmCoprimes[0], peTmp, piTmp, pbScratch, cbScratch );                             // Convert it to integer
 
        SymCryptIntMulMixedSize( piTmp, SymCryptIntFromModulus((PSYMCRYPT_MODULUS)ppmCoprimes[1]), piDouble, pbScratch, cbScratch );    // Multiply by q
        scError = SymCryptIntCopyMixedSize( piDouble, piSolution );                                                 // Copy it into the solution
        if (scError != SYMCRYPT_NO_ERROR)
        {
            goto cleanup;
        }
 
        SymCryptModElementToInt( ppmCoprimes[1], ppeCrtRemainders[1], piTmp, pbScratch, cbScratch );                // Convert r1 to integer
 
        carry = SymCryptIntAddMixedSize( piTmp, piSolution, piSolution );                                           // Add it to the solution
 
        if (carry>0)
        {
            scError = SYMCRYPT_INVALID_ARGUMENT;
            goto cleanup;
        }
    }
    else
    {
        scError = SYMCRYPT_INVALID_ARGUMENT;
        goto cleanup;
    }
 
cleanup:
    return scError;
}

Referenced by rsa_decrypt(), and SymCryptRsaCoreDecCrt().