--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/crypto/weakcryptospi/source/bigint/primes.cpp Fri Nov 06 13:21:00 2009 +0200
@@ -0,0 +1,450 @@
+/*
+* Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
+* All rights reserved.
+* This component and the accompanying materials are made available
+* under the terms of the License "Eclipse Public License v1.0"
+* which accompanies this distribution, and is available
+* at the URL "http://www.eclipse.org/legal/epl-v10.html".
+*
+* Initial Contributors:
+* Nokia Corporation - initial contribution.
+*
+* Contributors:
+*
+* Description:
+*
+*/
+
+
+#include <bigint.h>
+#include <e32std.h>
+#include <securityerr.h>
+#include "words.h"
+#include "primes.h"
+#include "algorithms.h"
+#include "mont.h"
+#include "stackinteger.h"
+
+static TBool IsSmallPrime(TUint aK);
+
+static inline void EliminateComposites(TUint* aS, TUint aPrime, TUint aJ,
+ TUint aMaxIndex)
+ {
+ for(; aJ<aMaxIndex; aJ+=aPrime)
+ ArraySetBit(aS, aJ);
+ }
+
+static inline TInt FindLeastSignificantZero(TUint aX)
+ {
+ aX = ~aX;
+ int i = 0;
+ if( aX << 16 == 0 ) aX>>=16, i+=16;
+ if( aX << 24 == 0 ) aX>>=8, i+=8;
+ if( aX << 28 == 0 ) aX>>=4, i+=4;
+ if( aX << 30 == 0 ) aX>>=2, i+=2;
+ if( aX << 31 == 0 ) ++i;
+ return i;
+ }
+
+static inline TInt FindFirstPrimeCandidate(TUint* aS, TUint aBitLength)
+ {
+ assert(aBitLength % WORD_BITS == 0);
+ TUint i=0;
+ //The empty statement at the end of this is stop warnings in all compilers
+ for(; aS[i] == KMaxTUint && i<BitsToWords(aBitLength); i++) {;}
+
+ if(i == BitsToWords(aBitLength))
+ return -1;
+ else
+ {
+ assert( FindLeastSignificantZero((TUint)(aS[i])) >= 0 );
+ assert( FindLeastSignificantZero((TUint)(aS[i])) <= 31 );
+ return i*WORD_BITS + FindLeastSignificantZero((TUint32)(aS[i]));
+ }
+ }
+
+static inline TUint FindSmallestIndex(TUint aPrime, TUint aRemainder)
+ {
+ TUint& j = aRemainder;
+ if(j)
+ {
+ j = aPrime - aRemainder;
+ if( j & 0x1L )
+ {
+ //if j is odd then this + j is even so we actually want
+ //the next number for which (this + j % p == 0) st this + j is odd
+ //that is: this + j + p == 0 mod p
+ j += aPrime;
+ }
+ //Turn j into an index for a bit array representing odd numbers only
+ j>>=1;
+ }
+ return j;
+ }
+
+static inline TUint RabinMillerRounds(TUint aBits)
+ {
+ //See HAC Table 4.4
+ if(aBits > 1300)
+ return 2;
+ if (aBits > 850)
+ return 3;
+ if (aBits > 650)
+ return 4;
+ if (aBits > 550)
+ return 5;
+ if (aBits > 450)
+ return 6;
+ if (aBits > 400)
+ return 7;
+ if (aBits > 350)
+ return 8;
+ if (aBits > 300)
+ return 9;
+ if (aBits > 250)
+ return 12;
+ if (aBits > 200)
+ return 15;
+ if (aBits > 150)
+ return 18;
+ if (aBits > 100)
+ return 27;
+ //All of the above are optimisations on the worst case. The worst case
+ //chance of odd composite integers being declared prime by Rabin-Miller is
+ //(1/4)^t where t is the number of rounds. Thus, t = 40 means that the
+ //chance of declaring a composite integer prime is less than 2^(-80). See
+ //HAC Fact 4.25 and most of chapter 4 for more details.
+ return 40;
+ }
+
+static TBool HasSmallDivisorL(const TInteger& aPossiblePrime)
+ {
+ assert(aPossiblePrime.IsOdd());
+ //Start checking at the first odd prime, whether it is even should have
+ //already been checked
+ for( TUint i=1; i < KPrimeTableSize; i++ )
+ {
+ if( aPossiblePrime.ModuloL(KPrimeTable[i]) == 0 )
+ {
+ return ETrue;
+ }
+ }
+ return EFalse;
+ }
+
+static TBool RabinMillerIterationL(const CMontgomeryStructure& aMont,
+ const TInteger& aProbablePrime, const TInteger& aBase)
+ {
+ //see HAC 4.24
+ const TInteger& n = aProbablePrime;
+ assert(n > KLastSmallPrimeSquared);
+ assert(n.IsOdd());
+ assert(aBase > TInteger::One());
+
+ RInteger nminus1 = n.MinusL(TInteger::One());
+ CleanupStack::PushL(nminus1);
+ assert(aBase < nminus1);
+
+ // 1) find (s | 2^s*r == n-1) where r is odd
+ // we want the largest power of 2 that divides n-1
+ TUint s=0;
+ for(;;s++)
+ {
+ if(nminus1.Bit(s))
+ {
+ break;
+ }
+ }
+ // (r = (n-1) / 2^s) which is equiv to (n-1 >>= s)
+ RInteger r = RInteger::NewL(nminus1);
+ CleanupStack::PushL(r);
+ r >>= s;
+
+ //At no point do we own y, aMont owns it
+ const TInteger* y = &(aMont.ExponentiateL(aBase, r));
+
+ TBool probablePrime = EFalse;
+
+ TUint j=1;
+ if( *y == TInteger::One() || *y == nminus1 )
+ {
+ probablePrime = ETrue;
+ }
+ else
+ {
+ for(j=1; j<s; j++)
+ {
+ y = &(aMont.SquareL(*y));
+ if(*y == nminus1)
+ {
+ probablePrime = ETrue;
+ break;
+ }
+ }
+ }
+ CleanupStack::PopAndDestroy(&r);
+ CleanupStack::PopAndDestroy(&nminus1);//y,r,nminus1
+ return probablePrime;
+ }
+
+static TBool RabinMillerTestL(const CMontgomeryStructure& aMont,
+ const TInteger& aProbablePrime, TUint aRounds)
+ {
+ const TInteger& n = aProbablePrime;
+ assert(n > KLastSmallPrimeSquared);
+
+ RInteger nminus2 = n.MinusL(TInteger::Two());
+ CleanupStack::PushL(nminus2);
+
+ for(TUint i=0; i<aRounds; i++)
+ {
+ RInteger base = RInteger::NewRandomL(TInteger::Two(), nminus2);
+ CleanupStack::PushL(base);
+ if(!RabinMillerIterationL(aMont, n, base))
+ {
+ CleanupStack::PopAndDestroy(2, &nminus2);//base, nminus2
+ return EFalse;
+ }
+ CleanupStack::PopAndDestroy(&base);
+ }
+ CleanupStack::PopAndDestroy(&nminus2);
+ return ETrue;
+ }
+
+static TBool IsStrongProbablePrimeL(const TInteger& aPrime)
+ {
+ CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aPrime);
+ //This should be using short circuit evaluation
+ TBool probablePrime = RabinMillerIterationL(*mont, aPrime, TInteger::Two())
+ && RabinMillerTestL(*mont, aPrime,RabinMillerRounds(aPrime.BitCount()));
+ CleanupStack::PopAndDestroy(mont);
+ return probablePrime;
+ }
+
+/* In the _vast_ majority of cases this simply checks that your chosen random
+ * number is >= KLastSmallPrimeSquared and return EFalse and lets the normal
+ * prime generation routines handle the situation. In the case where it is
+ * smaller, it generates a provable prime and returns ETrue. The algorithm for
+ * finding a provable prime < KLastPrimeSquared is not the most efficient in the
+ * world, but two points come to mind
+ * 1) The two if statements hardly _ever_ evaluate to ETrue in real life.
+ * 2) Even when it is, the distribution of primes < KLastPrimeSquared is pretty
+ * dense, so you aren't going to have check many.
+ * This function is essentially here for two reasons:
+ * 1) Ensures that it is possible to generate primes < KLastPrimeSquared (the
+ * test code does this)
+ * 2) Ensures that if you request a prime of a large bit size that there is an
+ * even probability distribution across all integers < 2^aBits
+ */
+TBool TInteger::SmallPrimeRandomizeL(void)
+ {
+ TBool foundPrime = EFalse;
+ //If the random number we've chosen is less than KLastSmallPrime,
+ //testing for primality is easy.
+ if(*this <= KLastSmallPrime)
+ {
+ //If Zero or One, or two, next prime number is two
+ if(IsZero() || *this == One() || *this == Two())
+ {
+ CopyL(TInteger::Two());
+ foundPrime = ETrue;
+ }
+ else
+ {
+ //Make sure any number we bother testing is at least odd
+ SetBit(0);
+ //Binary search the small primes.
+ while(!IsSmallPrime(ConvertToUnsignedLong()))
+ {
+ //If not prime, add two and try the next odd number.
+
+ //will never carry as the minimum size of an RInteger is 2
+ //words. Much bigger than KLastSmallPrime on 32bit
+ //architectures.
+ IncrementNoCarry(Ptr(), Size(), 2);
+ }
+ assert(IsSmallPrime(ConvertToUnsignedLong()));
+ foundPrime = ETrue;
+ }
+ }
+ else if(*this <= KLastSmallPrimeSquared)
+ {
+ //Make sure any number we bother testing is at least odd
+ SetBit(0);
+
+ while(HasSmallDivisorL(*this) && *this <= KLastSmallPrimeSquared)
+ {
+ //If not prime, add two and try the next odd number.
+
+ //will never carry as the minimum size of an RInteger is 2
+ //words. Much bigger than KLastSmallPrime on 32bit
+ //architectures.
+ IncrementNoCarry(Ptr(), Size(), 2);
+ }
+ //If we exited while loop because it had no small divisor then it is
+ //prime. Otherwise, we've exceeded the limit of what we can provably
+ //generate. Therefore the normal prime gen routines will be run on it
+ //now.
+ if(*this < KLastSmallPrimeSquared)
+ {
+ foundPrime = ETrue;
+ }
+ }
+ //This doesn't mean there is no such prime, simply means that the number
+ //wasn't less than KSmallPrimeSquared and needs to be handled by the normal
+ //prime generation routines.
+ return foundPrime;
+ }
+
+void TInteger::PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)
+ {
+ assert(aBits > 1);
+
+ //"this" is "empty" currently. Consists of Size() words of 0's. This is just
+ //checking that sign flag is positive as we don't set it later.
+ assert(NotNegative());
+
+ //Flag for the whole function saying if we've found a prime
+ TBool foundProbablePrime = EFalse;
+
+ //Find 2^aBits + 1 -- any prime we find must be less than this.
+ RInteger max = RInteger::NewEmptyL(BitsToWords(aBits)+1);
+ CleanupStack::PushL(max);
+ max.SetBit(aBits);
+ assert(max.BitCount()-1 == aBits);
+
+ // aBits | approx number of odd numbers you must try to have a 50%
+ // chance of finding a prime
+ //---------------------------------------------------------
+ // 512 | 122
+ // 1024 | 245
+ // 2048 | 1023
+ //Therefore if we are generating larger than 1024 bit numbers we'll use a
+ //bigger bit array to have a better chance of avoiding re-generating it.
+ TUint sLength = aBits > 1024 ? 1024 : 512;
+ RInteger S = RInteger::NewEmptyL(BitsToWords(sLength));
+ CleanupStack::PushL(S);
+
+ while(!foundProbablePrime)
+ {
+ //Randomly choose aBits
+ RandomizeL(aBits, aAttr);
+
+ //If the random number chosen is less than KSmallPrimeSquared, we have a
+ //special set of routines.
+ if(SmallPrimeRandomizeL())
+ {
+ foundProbablePrime = ETrue;
+ }
+ else
+ {
+ //if it was <= KLastSmallPrimeSquared then it would have been
+ //handled by SmallPrimeRandomizeL()
+ assert(*this > KLastSmallPrimeSquared);
+
+ //Make sure any number we bother testing is at least odd
+ SetBit(0);
+
+ //Ensure that this + 2*sLength < max
+ RInteger temp = max.MinusL(*this);
+ CleanupStack::PushL(temp);
+ ++temp;
+ temp >>=1;
+ if(temp < sLength)
+ {
+ //if this + 2*sLength >= max then we use a smaller sLength to
+ //ensure we don't find a number that is outside of our bounds
+ //(and bigger than our allocated memory for this)
+
+ //temp must be less than KMaxTUint as sLength is a TUint
+ sLength = temp.ConvertToUnsignedLong();
+ }
+ CleanupStack::PopAndDestroy(&temp);
+
+ //Start at 1 as no point in checking against 2 (all odd numbers)
+ for(TUint i=1; i<KPrimeTableSize; i++)
+ {
+ //no need to call ModuloL as we know KPrimeTable[i] is not 0
+ TUint remainder = Modulo(*this, KPrimeTable[i]);
+ TUint index = FindSmallestIndex(KPrimeTable[i], remainder);
+ EliminateComposites(S.Ptr(), KPrimeTable[i], index, sLength);
+ }
+ TInt j = FindFirstPrimeCandidate(S.Ptr(), sLength);
+ TInt prev = 0;
+ for(; j>=0; j=FindFirstPrimeCandidate(S.Ptr(), sLength))
+ {
+ ArraySetBit(S.Ptr(), j);
+
+ //should never carry as we earlier made sure that 2*j + this < max
+ //where max is 1 bit more than we asked for.
+ IncrementNoCarry(Ptr(), Size(), 2*(j-prev));
+
+ assert(*this < max);
+ assert(!HasSmallDivisorL(*this));
+
+ prev = j;
+
+ if( IsStrongProbablePrimeL(*this) )
+ {
+ foundProbablePrime = ETrue;
+ break;
+ }
+ }
+ //This clears the memory
+ S.CopyL(0, EFalse);
+ }
+ }
+ CleanupStack::PopAndDestroy(2, &max);
+ }
+
+EXPORT_C TBool TInteger::IsPrimeL(void) const
+ {
+ if( NotPositive() )
+ {
+ return EFalse;
+ }
+ else if( IsEven() )
+ {
+ return *this == Two();
+ }
+ else if( *this <= KLastSmallPrime )
+ {
+ assert(KLastSmallPrime < KMaxTUint);
+ return IsSmallPrime(this->ConvertToUnsignedLong());
+ }
+ else if( *this <= KLastSmallPrimeSquared )
+ {
+ return !HasSmallDivisorL(*this);
+ }
+ else
+ {
+ return !HasSmallDivisorL(*this) && IsStrongProbablePrimeL(*this);
+ }
+ }
+
+// Method is excluded from coverage due to the problem with BullsEye on ONB.
+// Manually verified that this method is functionally covered.
+#ifdef _BullseyeCoverage
+#pragma suppress_warnings on
+#pragma BullseyeCoverage off
+#pragma suppress_warnings off
+#endif
+
+static TBool IsSmallPrime(TUint aK)
+ {
+ //This is just a binary search of our small prime table.
+ TUint l = 0;
+ TUint u = KPrimeTableSize;
+ while( u > l )
+ {
+ TUint m = (l+u)>>1;
+ TUint p = KPrimeTable[m];
+ if(aK < p)
+ u = m;
+ else if (aK > p)
+ l = m + 1;
+ else
+ return ETrue;
+ }
+ return EFalse;
+ }