1 /*

     2 * Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of the License "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: 

    15 *

    16 */

    17 

    18 

    19 #include <bigint.h>

    20 #include <e32std.h>

    21 #include <securityerr.h>

    22 #include "words.h"

    23 #include "primes.h"

    24 #include "algorithms.h"

    25 #include "mont.h"

    26 #include "stackinteger.h"

    27 

    28 static TBool IsSmallPrime(TUint aK);

    29 

    30 static inline void EliminateComposites(TUint* aS, TUint aPrime, TUint aJ, 

    31 	TUint aMaxIndex)

    32 	{

    33 	for(; aJ<aMaxIndex; aJ+=aPrime)

    34 		ArraySetBit(aS, aJ);

    35 	}

    36 

    37 static inline TInt FindLeastSignificantZero(TUint aX)

    38 	{

    39 	aX = ~aX;

    40 	int i = 0;

    41 	if( aX << 16 == 0 ) aX>>=16, i+=16;

    42 	if( aX << 24 == 0 ) aX>>=8, i+=8;

    43 	if( aX << 28 == 0 ) aX>>=4, i+=4;

    44 	if( aX << 30 == 0 ) aX>>=2, i+=2;

    45 	if( aX << 31 == 0 ) ++i;

    46 	return i;

    47 	}

    48 

    49 static inline TInt FindFirstPrimeCandidate(TUint* aS, TUint aBitLength)

    50 	{

    51 	assert(aBitLength % WORD_BITS == 0);

    52 	TUint i=0;

    53 	//The empty statement at the end of this is stop warnings in all compilers

    54 	for(; aS[i] == KMaxTUint && i<BitsToWords(aBitLength); i++) {;}

    55 

    56 	if(i == BitsToWords(aBitLength))

    57 		return -1;

    58 	else

    59 		{

    60 		assert( FindLeastSignificantZero((TUint)(aS[i])) >= 0 );

    61 		assert( FindLeastSignificantZero((TUint)(aS[i])) <= 31 );

    62 		return i*WORD_BITS + FindLeastSignificantZero((TUint32)(aS[i]));

    63 		}

    64 	}

    65 

    66 static inline TUint FindSmallestIndex(TUint aPrime, TUint aRemainder)

    67 	{

    68 	TUint& j = aRemainder;

    69 	if(j)

    70 		{

    71 		j = aPrime - aRemainder;

    72 		if( j & 0x1L )

    73 			{

    74 			//if j is odd then this + j is even so we actually want 

    75 			//the next number for which (this + j % p == 0) st this + j is odd

    76 			//that is: this + j + p == 0 mod p

    77 			j += aPrime;

    78 			}

    79 		//Turn j into an index for a bit array representing odd numbers only

    80 		j>>=1;

    81 		}

    82 	return j;

    83 	}

    84 

    85 static inline TUint RabinMillerRounds(TUint aBits) 

    86 	{

    87 	//See HAC Table 4.4

    88 	if(aBits > 1300)

    89 		return 2;

    90 	if (aBits > 850)

    91 		return 3;

    92 	if (aBits > 650)

    93 		return 4;

    94 	if (aBits > 550)

    95 		return 5;

    96 	if (aBits > 450)

    97 		return 6;

    98 	if (aBits > 400)

    99 		return 7;

   100 	if (aBits > 350)

   101 		return 8;

   102 	if (aBits > 300)

   103 		return 9;

   104 	if (aBits > 250)

   105 		return 12;

   106 	if (aBits > 200)

   107 		return 15;

   108 	if (aBits > 150)

   109 		return 18;

   110 	if (aBits > 100)

   111 		return 27;

   112 	//All of the above are optimisations on the worst case.  The worst case

   113 	//chance of odd composite integers being declared prime by Rabin-Miller is

   114 	//(1/4)^t where t is the number of rounds.  Thus, t = 40 means that the

   115 	//chance of declaring a composite integer prime is less than 2^(-80).  See

   116 	//HAC Fact 4.25 and most of chapter 4 for more details.

   117 	return 40;

   118 	}

   119 

   120 static TBool HasSmallDivisorL(const TInteger& aPossiblePrime)

   121 	{

   122 	assert(aPossiblePrime.IsOdd());

   123 	//Start checking at the first odd prime, whether it is even should have

   124 	//already been checked

   125 	for( TUint i=1; i < KPrimeTableSize; i++ )

   126 		{

   127 		if( aPossiblePrime.ModuloL(KPrimeTable[i]) == 0 )

   128 			{

   129 			return ETrue;

   130 			}

   131 		}

   132 	return EFalse;

   133 	}

   134 

   135 static TBool RabinMillerIterationL(const CMontgomeryStructure& aMont, 

   136 	const TInteger& aProbablePrime, const TInteger& aBase)

   137 	{

   138 	//see HAC 4.24

   139 	const TInteger& n = aProbablePrime;

   140 	assert(n > KLastSmallPrimeSquared);

   141 	assert(n.IsOdd());

   142 	assert(aBase > TInteger::One());

   143 

   144 	RInteger nminus1 = n.MinusL(TInteger::One());

   145 	CleanupStack::PushL(nminus1);

   146 	assert(aBase < nminus1);

   147 

   148 	// 1) find (s | 2^s*r == n-1) where r is odd

   149 	// we want the largest power of 2 that divides n-1

   150 	TUint s=0;

   151 	for(;;s++)

   152 		{

   153 		if(nminus1.Bit(s))

   154 			{

   155 			break;

   156 			}

   157 		}

   158 	// (r = (n-1) / 2^s) which is equiv to (n-1 >>= s)

   159 	RInteger r = RInteger::NewL(nminus1);

   160 	CleanupStack::PushL(r);

   161 	r >>= s;

   162 

   163 	//At no point do we own y, aMont owns it

   164 	const TInteger* y = &(aMont.ExponentiateL(aBase, r));

   165 

   166 	TBool probablePrime = EFalse;

   167 	

   168 	TUint j=1;

   169 	if( *y == TInteger::One() || *y == nminus1 )

   170 		{

   171 		probablePrime = ETrue;

   172 		}

   173 	else

   174 		{

   175 		for(j=1; j<s; j++)

   176 			{

   177 			y = &(aMont.SquareL(*y));

   178 			if(*y == nminus1)

   179 				{

   180 				probablePrime = ETrue;

   181 				break;

   182 				}

   183 			}

   184 		}

   185 	CleanupStack::PopAndDestroy(&r);

   186 	CleanupStack::PopAndDestroy(&nminus1);//y,r,nminus1

   187 	return probablePrime;

   188 	}

   189 

   190 static TBool RabinMillerTestL(const CMontgomeryStructure& aMont, 

   191 	const TInteger& aProbablePrime, TUint aRounds) 

   192 	{

   193 	const TInteger& n = aProbablePrime;

   194 	assert(n > KLastSmallPrimeSquared);

   195 	

   196 	RInteger nminus2 = n.MinusL(TInteger::Two());

   197 	CleanupStack::PushL(nminus2);

   198 

   199 	for(TUint i=0; i<aRounds; i++)

   200 		{

   201 		RInteger base = RInteger::NewRandomL(TInteger::Two(), nminus2);

   202 		CleanupStack::PushL(base);

   203 		if(!RabinMillerIterationL(aMont, n, base))

   204 			{

   205 			CleanupStack::PopAndDestroy(2, &nminus2);//base, nminus2

   206 			return EFalse;

   207 			}

   208 		CleanupStack::PopAndDestroy(&base);

   209 		}

   210 	CleanupStack::PopAndDestroy(&nminus2);

   211 	return ETrue;

   212 	}

   213 

   214 static TBool IsStrongProbablePrimeL(const TInteger& aPrime) 

   215 	{

   216 	CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aPrime);

   217 	//This should be using short circuit evaluation

   218 	TBool probablePrime = RabinMillerIterationL(*mont, aPrime, TInteger::Two())

   219 		&& RabinMillerTestL(*mont, aPrime,RabinMillerRounds(aPrime.BitCount()));

   220 	CleanupStack::PopAndDestroy(mont);

   221 	return probablePrime;

   222 	}

   223 

   224 /* In the _vast_ majority of cases this simply checks that your chosen random

   225  * number is >= KLastSmallPrimeSquared and return EFalse and lets the normal

   226  * prime generation routines handle the situation.  In the case where it is

   227  * smaller, it generates a provable prime and returns ETrue.  The algorithm for

   228  * finding a provable prime < KLastPrimeSquared is not the most efficient in the

   229  * world, but two points come to mind

   230  * 1) The two if statements hardly _ever_ evaluate to ETrue in real life.

   231  * 2) Even when it is, the distribution of primes < KLastPrimeSquared is pretty

   232  * dense, so you aren't going to have check many.

   233  * This function is essentially here for two reasons:

   234  * 1) Ensures that it is possible to generate primes < KLastPrimeSquared (the

   235  * test code does this)

   236  * 2) Ensures that if you request a prime of a large bit size that there is an

   237  * even probability distribution across all integers < 2^aBits

   238  */

   239 TBool TInteger::SmallPrimeRandomizeL(void)

   240 	{

   241 	TBool foundPrime = EFalse;

   242 	//If the random number we've chosen is less than KLastSmallPrime,

   243 	//testing for primality is easy.

   244 	if(*this <= KLastSmallPrime)

   245 		{

   246 		//If Zero or One, or two, next prime number is two

   247 		if(IsZero() || *this == One() || *this == Two())

   248 			{

   249 			CopyL(TInteger::Two());

   250 			foundPrime = ETrue;

   251 			}

   252 		else

   253 			{

   254 			//Make sure any number we bother testing is at least odd

   255 			SetBit(0);

   256 			//Binary search the small primes.

   257 			while(!IsSmallPrime(ConvertToUnsignedLong()))

   258 				{

   259 				//If not prime, add two and try the next odd number.

   260 

   261 				//will never carry as the minimum size of an RInteger is 2

   262 				//words.  Much bigger than KLastSmallPrime on 32bit

   263 				//architectures.

   264 				IncrementNoCarry(Ptr(), Size(), 2);

   265 				}

   266 			assert(IsSmallPrime(ConvertToUnsignedLong()));

   267 			foundPrime = ETrue;

   268 			}

   269 		}

   270 	else if(*this <= KLastSmallPrimeSquared)

   271 		{

   272 		//Make sure any number we bother testing is at least odd

   273 		SetBit(0);

   274 

   275 		while(HasSmallDivisorL(*this) && *this <= KLastSmallPrimeSquared)

   276 			{

   277 			//If not prime, add two and try the next odd number.

   278 

   279 			//will never carry as the minimum size of an RInteger is 2

   280 			//words.  Much bigger than KLastSmallPrime on 32bit

   281 			//architectures.

   282 			IncrementNoCarry(Ptr(), Size(), 2);

   283 			}

   284 		//If we exited while loop because it had no small divisor then it is

   285 		//prime.  Otherwise, we've exceeded the limit of what we can provably

   286 		//generate.  Therefore the normal prime gen routines will be run on it

   287 		//now.

   288 		if(*this < KLastSmallPrimeSquared)

   289 			{

   290 			foundPrime = ETrue;

   291 			}

   292 		}

   293 	//This doesn't mean there is no such prime, simply means that the number

   294 	//wasn't less than KSmallPrimeSquared and needs to be handled by the normal

   295 	//prime generation routines.

   296 	return foundPrime;

   297 	}

   298 

   299 void TInteger::PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)

   300 	{

   301 	assert(aBits > 1); 

   302 	

   303 	//"this" is "empty" currently.  Consists of Size() words of 0's.  This is just

   304 	//checking that sign flag is positive as we don't set it later.

   305 	assert(NotNegative());

   306 

   307 	//Flag for the whole function saying if we've found a prime

   308 	TBool foundProbablePrime = EFalse;

   309 

   310 	//Find 2^aBits + 1 -- any prime we find must be less than this.

   311 	RInteger max = RInteger::NewEmptyL(BitsToWords(aBits)+1);

   312 	CleanupStack::PushL(max);

   313 	max.SetBit(aBits);

   314 	assert(max.BitCount()-1 == aBits);

   315 

   316 	// aBits 	| approx number of odd numbers you must try to have a 50% 

   317 	//			chance of finding a prime

   318 	//---------------------------------------------------------

   319 	// 512		| 122		

   320 	// 1024		| 245

   321 	// 2048		| 1023

   322 	//Therefore if we are generating larger than 1024 bit numbers we'll use a

   323 	//bigger bit array to have a better chance of avoiding re-generating it.

   324 	TUint sLength = aBits > 1024 ? 1024 : 512;

   325 	RInteger S = RInteger::NewEmptyL(BitsToWords(sLength));

   326 	CleanupStack::PushL(S);

   327 

   328 	while(!foundProbablePrime)

   329 		{

   330 		//Randomly choose aBits

   331 		RandomizeL(aBits, aAttr);

   332 

   333 		//If the random number chosen is less than KSmallPrimeSquared, we have a

   334 		//special set of routines.

   335 		if(SmallPrimeRandomizeL())

   336 			{

   337 			foundProbablePrime = ETrue;

   338 			}

   339 		else

   340 			{

   341 			//if it was <= KLastSmallPrimeSquared then it would have been

   342 			//handled by SmallPrimeRandomizeL()

   343 			assert(*this > KLastSmallPrimeSquared);

   344 

   345 			//Make sure any number we bother testing is at least odd

   346 			SetBit(0);

   347 

   348 			//Ensure that this + 2*sLength < max

   349 			RInteger temp = max.MinusL(*this);

   350 			CleanupStack::PushL(temp);

   351 			++temp;

   352 			temp >>=1;

   353 			if(temp < sLength)

   354 				{

   355 				//if this + 2*sLength >= max then we use a smaller sLength to

   356 				//ensure we don't find a number that is outside of our bounds

   357 				//(and bigger than our allocated memory for this)

   358 

   359 				//temp must be less than KMaxTUint as sLength is a TUint 

   360 				sLength = temp.ConvertToUnsignedLong();	

   361 				}

   362 			CleanupStack::PopAndDestroy(&temp);

   363 

   364 			//Start at 1 as no point in checking against 2 (all odd numbers)

   365 			for(TUint i=1; i<KPrimeTableSize; i++)

   366 				{

   367 				//no need to call ModuloL as we know KPrimeTable[i] is not 0

   368 				TUint remainder = Modulo(*this, KPrimeTable[i]);

   369 				TUint index = FindSmallestIndex(KPrimeTable[i], remainder);

   370 				EliminateComposites(S.Ptr(), KPrimeTable[i], index, sLength);

   371 				}

   372 			TInt j = FindFirstPrimeCandidate(S.Ptr(), sLength);

   373 			TInt prev = 0;

   374 			for(; j>=0; j=FindFirstPrimeCandidate(S.Ptr(), sLength))

   375 				{

   376 				ArraySetBit(S.Ptr(), j);

   377 

   378 				//should never carry as we earlier made sure that 2*j + this < max

   379 				//where max is 1 bit more than we asked for.

   380 				IncrementNoCarry(Ptr(), Size(), 2*(j-prev));

   381 

   382 				assert(*this < max);

   383 				assert(!HasSmallDivisorL(*this));

   384 

   385 				prev = j;

   386 

   387 				if( IsStrongProbablePrimeL(*this) )

   388 					{

   389 					foundProbablePrime = ETrue;

   390 					break;

   391 					}

   392 				}

   393 			//This clears the memory

   394 			S.CopyL(0, EFalse);

   395 			}

   396 		}

   397 	CleanupStack::PopAndDestroy(2, &max);

   398 	}

   399 

   400 EXPORT_C TBool TInteger::IsPrimeL(void) const

   401 	{

   402 	if( NotPositive() )

   403 		{

   404 		return EFalse;

   405 		}

   406 	else if( IsEven() )

   407 		{

   408 		return *this == Two();

   409 		}

   410 	else if( *this <= KLastSmallPrime )

   411 		{

   412 		assert(KLastSmallPrime < KMaxTUint);

   413 		return IsSmallPrime(this->ConvertToUnsignedLong());

   414 		}

   415 	else if( *this <= KLastSmallPrimeSquared )

   416 		{

   417 		return !HasSmallDivisorL(*this);

   418 		}

   419 	else 

   420 		{

   421 		return !HasSmallDivisorL(*this) && IsStrongProbablePrimeL(*this);

   422 		}

   423 	}

   424 

   425 // Method is excluded from coverage due to the problem with BullsEye on ONB.

   426 // Manually verified that this method is functionally covered.

   427 #ifdef _BullseyeCoverage

   428 #pragma suppress_warnings on

   429 #pragma BullseyeCoverage off

   430 #pragma suppress_warnings off

   431 #endif

   432 

   433 static TBool IsSmallPrime(TUint aK) 

   434 	{

   435 	//This is just a binary search of our small prime table.

   436 	TUint l = 0;

   437 	TUint u = KPrimeTableSize;

   438 	while( u > l )

   439 		{

   440 		TUint m = (l+u)>>1;

   441 		TUint p = KPrimeTable[m];

   442 		if(aK < p)

   443 			u = m;

   444 		else if (aK > p)

   445 			l = m + 1;

   446 		else

   447 			return ETrue;

   448 		}

   449 	return EFalse;

   450 	}