//

// primes.c

// Primality tests and prime number generation

//

// Copyright (c) Microsoft Corporation. Licensed under the MIT license.

//

#include "precomp.h"

UINT32

SYMCRYPT_CALL

SymCryptIntMillerRabinPrimalityTest(

    _In_                            PCSYMCRYPT_INT      piSrc,

                                    UINT32              nBitsSrc,

                                    UINT32              nIterations,

                                    UINT32              flags,

    _Out_writes_bytes_( cbScratch ) PBYTE               pbScratch,

                                    SIZE_T              cbScratch )

{

    BOOLEAN     innerLoop = TRUE;

    UINT32      borrow = 0;

    UINT32      nDigitsSrc = 0;

    UINT32                  R = 1;

    PSYMCRYPT_INT           piD = NULL;

    UINT32                  cbD = 0;

    PSYMCRYPT_MODULUS       pmModulus = NULL;

    UINT32                  cbModulus = 0;

    PSYMCRYPT_MODELEMENT    peX = NULL;

    UINT32                  cbX = 0;

    PSYMCRYPT_MODELEMENT    peOne = NULL;

    PSYMCRYPT_MODELEMENT    peMinOne = NULL;

    nDigitsSrc = SymCryptIntDigitsizeOfObject( piSrc );

    cbD = SymCryptSizeofIntFromDigits( nDigitsSrc );

    cbModulus = SymCryptSizeofModulusFromDigits( nDigitsSrc );

    SYMCRYPT_ASSERT( nBitsSrc >= SymCryptIntBitsizeOfValue( piSrc ) );

    SYMCRYPT_ASSERT( cbScratch >= cbModulus + SYMCRYPT_SCRATCH_BYTES_FOR_INT_TO_MODULUS(nDigitsSrc) );

    // Allocate the modulus

    pmModulus = SymCryptModulusCreate( pbScratch, cbModulus, nDigitsSrc );

    SYMCRYPT_ASSERT( pmModulus != NULL );

    pbScratch += cbModulus;

    cbScratch -= cbModulus;

    // Set the modulus

    SymCryptIntToModulus(

            piSrc,

            pmModulus,

            nBitsSrc,       // Average number of expected operations

            SYMCRYPT_FLAG_MODULUS_PARITY_PUBLIC,

            pbScratch,

            cbScratch );

    // Modelement size

    cbX = SymCryptSizeofModElementFromModulus( pmModulus );

    SYMCRYPT_ASSERT( cbScratch >=   3*cbX + cbD +

                                    SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( nDigitsSrc ) );

    peX = SymCryptModElementCreate( pbScratch, cbX, pmModulus );

    SYMCRYPT_ASSERT( peX != NULL );

    pbScratch += cbX;

    cbScratch -= cbX;

    peOne = SymCryptModElementCreate( pbScratch, cbX, pmModulus );

    SYMCRYPT_ASSERT( peOne != NULL );

    pbScratch += cbX;

    cbScratch -= cbX;

    peMinOne = SymCryptModElementCreate( pbScratch, cbX, pmModulus );

    SYMCRYPT_ASSERT( peMinOne != NULL );

    pbScratch += cbX;

    cbScratch -= cbX;

    // Allocate D

    piD = SymCryptIntCreate( pbScratch, cbD, nDigitsSrc );

    SYMCRYPT_ASSERT( piD != NULL );

    pbScratch += cbD;

    cbScratch -= cbD;

    // Calculate (piSrc - 1)

    // Note: We should never get a borrow here because the requirement

    // is that Src > 3.

    SymCryptIntCopy( piSrc, piD );

    borrow = SymCryptIntSubUint32( piD, 1, piD );

    SYMCRYPT_ASSERT( borrow==0 );

    SYMCRYPT_ASSERT( SymCryptIntGetBit( piD, 0 ) == 0 );

    // Check the 3 mod 4 requirement when side-channel safe

    SYMCRYPT_ASSERT(

            ((flags & SYMCRYPT_FLAG_DATA_PUBLIC) != 0) ||

            (SymCryptIntGetBit( piD, 1 )!=0) );

    UNREFERENCED_PARAMETER( flags );

    // Calculate R and D such that Src - 1 = D*2^R

    //      Notice that the loop executes only if

    //      the SYMCRYPT_FLAG_DATA_PUBLIC is

    //      specified (and Src != 3 mod 4)

    R = 1;

    while( SymCryptIntGetBit( piD, R )==0 )

    {

        R++;

    }

    SymCryptIntDivPow2( piD, R, piD );

    // Set peOne and peMinOne

    SymCryptModElementSetValueUint32( 1, pmModulus, peOne, pbScratch, cbScratch );

    SymCryptModElementSetValueNegUint32( 1, pmModulus, peMinOne, pbScratch, cbScratch );

    for (UINT32 i=0; i<nIterations; i++)

    {

        // Pick a random X in [2, piSrc-2]

        // Therefore the flags parameter is 0 (default: not allowed 0, 1, -1 when modulus > 3)

        SymCryptModSetRandom( pmModulus, peX, 0, pbScratch, cbScratch );

        // X^D mod piSrc

        // Notice that nBitsSrc is public in the call of SymCryptModExp

        SymCryptModExp( pmModulus, peX, piD, nBitsSrc, 0, peX, pbScratch, cbScratch );

        // Check for 1 or -1

        if ( SymCryptModElementIsEqual( pmModulus, peX, peOne ) |

             SymCryptModElementIsEqual( pmModulus, peX, peMinOne ) )

        {

            continue;

        }

        // repeat R-1 times

        //      Notice that the inner loop executes only if

        //      the SYMCRYPT_FLAG_DATA_PUBLIC is

        //      specified (and Src != 3 mod 4)

        innerLoop = TRUE;

        for (UINT32 j=0; (j<R-1)&&(innerLoop); j++)

        {

            // Square X

            SymCryptModSquare( pmModulus, peX, peX, pbScratch, cbScratch );

            // Check if it is 1

            if (SymCryptModElementIsEqual( pmModulus, peX, peOne ))

            {

                return 0x0;

            }

            // Check if it is -1

            if (SymCryptModElementIsEqual( pmModulus, peX, peMinOne ))

            {

                innerLoop = FALSE;

                break;

            }

        }

        if (innerLoop)

        {

            return 0x0;

        }

    }

    return  0xffffffff;     // Prime

}

#define SYMCRYPT_PRIME_GENERATION_MR_ITERATIONS (64)

SYMCRYPT_ERROR

SYMCRYPT_CALL

SymCryptIntGenerateRandomPrime(

    _In_                            PCSYMCRYPT_INT      piLow,

    _In_                            PCSYMCRYPT_INT      piHigh,

    _In_reads_opt_( nPubExp )       PCUINT64            pu64PubExp,

                                    UINT32              nPubExp,

                                    UINT32              nTries,

                                    UINT32              flags,

    _Inout_                         PSYMCRYPT_INT       piDst,

    _Out_writes_bytes_( cbScratch ) PBYTE               pbScratch,

                                    SIZE_T              cbScratch )

{

    SYMCRYPT_ERROR  scError = SYMCRYPT_EXTERNAL_FAILURE;

    PSYMCRYPT_DIVISOR pdPubExp[ SYMCRYPT_RSAKEY_MAX_NUMOF_PUBEXPS ];

    PSYMCRYPT_INT piTmp;

    UINT32 cnt = 0;

    UINT32 e;

    BOOLEAN reject;

    SIZE_T cbObj;

    UINT32 nBits = SymCryptIntBitsizeOfObject(piDst);

    UINT32 nBytes = (nBits + 7)/8;

    UINT32 nBitsHigh = SymCryptIntBitsizeOfValue( piHigh );

    PCSYMCRYPT_TRIALDIVISION_CONTEXT pTrialDivisionContext = SymCryptCreateTrialDivisionContext( SymCryptIntDigitsizeOfObject( piHigh ) );

    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_INT_PRIME_GEN( SymCryptIntDigitsizeOfObject( piDst ) ) );

    SYMCRYPT_ASSERT( nPubExp <= SYMCRYPT_RSAKEY_MAX_NUMOF_PUBEXPS );

    SYMCRYPT_ASSERT( SymCryptDigitsFromBits( 64 ) == 1 );

    UNREFERENCED_PARAMETER( flags );

    // Allocate divisor objects for each public exponent & initialize them

    cbObj = SymCryptSizeofDivisorFromDigits( 1 );

    for( e = 0; e < nPubExp; e++ )

    {

        SYMCRYPT_ASSERT( cbScratch >= cbObj );

        if( pu64PubExp[e] == 0 )

        {

            scError = SYMCRYPT_INVALID_ARGUMENT;

            goto exit;

        }

        pdPubExp[e] = SymCryptDivisorCreate( pbScratch, cbObj, 1 );

        pbScratch += cbObj;

        cbScratch -= cbObj;

        SymCryptIntSetValueUint64( pu64PubExp[e], SymCryptIntFromDivisor( pdPubExp[e] ) );

        SymCryptIntToDivisor( SymCryptIntFromDivisor( pdPubExp[e] ), pdPubExp[e], 1000, SYMCRYPT_FLAG_DATA_PUBLIC, pbScratch, cbScratch );

    }

    cbObj = SymCryptSizeofIntFromDigits( 1 );

    SYMCRYPT_ASSERT( cbScratch >= cbObj + nBytes );

    piTmp = SymCryptIntCreate( pbScratch, cbObj, 1 );

    pbScratch += cbObj;

    cbScratch -= cbObj;

    do

    {

        cnt++;

        scError = SymCryptCallbackRandom( pbScratch, nBytes );

        if (scError != SYMCRYPT_NO_ERROR)

        {

            goto exit;

        }

        scError = SymCryptIntSetValue( pbScratch, nBytes, SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, piDst );

        if (scError != SYMCRYPT_NO_ERROR)

        {

            goto exit;

        }

        // Set the integer to 3 mod 4

        SymCryptIntSetBits( piDst, 3, 0, 2 );

        // Zero out the top bits above the upper limit

        SymCryptIntModPow2( piDst, nBitsHigh, piDst );

        // Check if it is in the correct range

        if ( (SymCryptIntIsLessThan( piDst, piLow )) ||

             (!SymCryptIntIsLessThan( piDst, piHigh )) )

        {

            continue;

        }

        // Fast compositeness check

        if( SymCryptIntFindSmallDivisor( pTrialDivisionContext, piDst, NULL, 0 ) != 0 )

        {

            // We found a small divisor; it is not a prime

            continue;

        }

        // Check for compatibility with public exponents (if provided)

        reject = FALSE;

        for( e = 0; e < nPubExp; e++ )

        {

            SymCryptIntDivMod( piDst, pdPubExp[e], NULL, piTmp, pbScratch, cbScratch );

            // Check that e has a modular inverse mod P-1

            // If e and P-1 are coprime, or GCD( P-1, e ) == 1, then e^-1 exists

            // We have (P mod e) in piTmp.

            // If piTmp == 0 then P is divisible by e, and will fail primality test - we don't care about the result of the GCD

            // Otherwise, GCD( (P mod e)-1, e ) == GCD( P-1 mod e, e ) == GCD( P-1, e )

            //

            // Note that if P-1 is a multiple of e then (P mod e)-1 == 0, and GCD( 0, e ) == e

            if( SymCryptUint64Gcd( pu64PubExp[e], SymCryptIntGetValueLsbits64( piTmp ) - 1, SYMCRYPT_FLAG_GCD_INPUTS_NOT_BOTH_EVEN ) != 1 )

            {

                // We can't continue the big loop from here :-(

                reject = TRUE;

                break;

            }

        }

        if( reject )

        {

            continue;

        }

        // Primality check

        if (SymCryptIntMillerRabinPrimalityTest( piDst, nBitsHigh, SYMCRYPT_PRIME_GENERATION_MR_ITERATIONS, 0, pbScratch, cbScratch ))

        {

            scError = SYMCRYPT_NO_ERROR;

            break;

        }

    }

    while (cnt<nTries);

    if (cnt>=nTries)

    {

        scError = SYMCRYPT_INVALID_ARGUMENT;

    }

exit:

    SymCryptFreeTrialDivisionContext( pTrialDivisionContext );

    return scError;

}