1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/security/crypto/weakcryptospi/source/bigint/primes.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,450 @@
1.4 +/*
1.5 +* Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
1.6 +* All rights reserved.
1.7 +* This component and the accompanying materials are made available
1.8 +* under the terms of the License "Eclipse Public License v1.0"
1.9 +* which accompanies this distribution, and is available
1.10 +* at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.11 +*
1.12 +* Initial Contributors:
1.13 +* Nokia Corporation - initial contribution.
1.14 +*
1.15 +* Contributors:
1.16 +*
1.17 +* Description:
1.18 +*
1.19 +*/
1.20 +
1.21 +
1.22 +#include <bigint.h>
1.23 +#include <e32std.h>
1.24 +#include <securityerr.h>
1.25 +#include "words.h"
1.26 +#include "primes.h"
1.27 +#include "algorithms.h"
1.28 +#include "mont.h"
1.29 +#include "stackinteger.h"
1.30 +
1.31 +static TBool IsSmallPrime(TUint aK);
1.32 +
1.33 +static inline void EliminateComposites(TUint* aS, TUint aPrime, TUint aJ,
1.34 + TUint aMaxIndex)
1.35 + {
1.36 + for(; aJ<aMaxIndex; aJ+=aPrime)
1.37 + ArraySetBit(aS, aJ);
1.38 + }
1.39 +
1.40 +static inline TInt FindLeastSignificantZero(TUint aX)
1.41 + {
1.42 + aX = ~aX;
1.43 + int i = 0;
1.44 + if( aX << 16 == 0 ) aX>>=16, i+=16;
1.45 + if( aX << 24 == 0 ) aX>>=8, i+=8;
1.46 + if( aX << 28 == 0 ) aX>>=4, i+=4;
1.47 + if( aX << 30 == 0 ) aX>>=2, i+=2;
1.48 + if( aX << 31 == 0 ) ++i;
1.49 + return i;
1.50 + }
1.51 +
1.52 +static inline TInt FindFirstPrimeCandidate(TUint* aS, TUint aBitLength)
1.53 + {
1.54 + assert(aBitLength % WORD_BITS == 0);
1.55 + TUint i=0;
1.56 + //The empty statement at the end of this is stop warnings in all compilers
1.57 + for(; aS[i] == KMaxTUint && i<BitsToWords(aBitLength); i++) {;}
1.58 +
1.59 + if(i == BitsToWords(aBitLength))
1.60 + return -1;
1.61 + else
1.62 + {
1.63 + assert( FindLeastSignificantZero((TUint)(aS[i])) >= 0 );
1.64 + assert( FindLeastSignificantZero((TUint)(aS[i])) <= 31 );
1.65 + return i*WORD_BITS + FindLeastSignificantZero((TUint32)(aS[i]));
1.66 + }
1.67 + }
1.68 +
1.69 +static inline TUint FindSmallestIndex(TUint aPrime, TUint aRemainder)
1.70 + {
1.71 + TUint& j = aRemainder;
1.72 + if(j)
1.73 + {
1.74 + j = aPrime - aRemainder;
1.75 + if( j & 0x1L )
1.76 + {
1.77 + //if j is odd then this + j is even so we actually want
1.78 + //the next number for which (this + j % p == 0) st this + j is odd
1.79 + //that is: this + j + p == 0 mod p
1.80 + j += aPrime;
1.81 + }
1.82 + //Turn j into an index for a bit array representing odd numbers only
1.83 + j>>=1;
1.84 + }
1.85 + return j;
1.86 + }
1.87 +
1.88 +static inline TUint RabinMillerRounds(TUint aBits)
1.89 + {
1.90 + //See HAC Table 4.4
1.91 + if(aBits > 1300)
1.92 + return 2;
1.93 + if (aBits > 850)
1.94 + return 3;
1.95 + if (aBits > 650)
1.96 + return 4;
1.97 + if (aBits > 550)
1.98 + return 5;
1.99 + if (aBits > 450)
1.100 + return 6;
1.101 + if (aBits > 400)
1.102 + return 7;
1.103 + if (aBits > 350)
1.104 + return 8;
1.105 + if (aBits > 300)
1.106 + return 9;
1.107 + if (aBits > 250)
1.108 + return 12;
1.109 + if (aBits > 200)
1.110 + return 15;
1.111 + if (aBits > 150)
1.112 + return 18;
1.113 + if (aBits > 100)
1.114 + return 27;
1.115 + //All of the above are optimisations on the worst case. The worst case
1.116 + //chance of odd composite integers being declared prime by Rabin-Miller is
1.117 + //(1/4)^t where t is the number of rounds. Thus, t = 40 means that the
1.118 + //chance of declaring a composite integer prime is less than 2^(-80). See
1.119 + //HAC Fact 4.25 and most of chapter 4 for more details.
1.120 + return 40;
1.121 + }
1.122 +
1.123 +static TBool HasSmallDivisorL(const TInteger& aPossiblePrime)
1.124 + {
1.125 + assert(aPossiblePrime.IsOdd());
1.126 + //Start checking at the first odd prime, whether it is even should have
1.127 + //already been checked
1.128 + for( TUint i=1; i < KPrimeTableSize; i++ )
1.129 + {
1.130 + if( aPossiblePrime.ModuloL(KPrimeTable[i]) == 0 )
1.131 + {
1.132 + return ETrue;
1.133 + }
1.134 + }
1.135 + return EFalse;
1.136 + }
1.137 +
1.138 +static TBool RabinMillerIterationL(const CMontgomeryStructure& aMont,
1.139 + const TInteger& aProbablePrime, const TInteger& aBase)
1.140 + {
1.141 + //see HAC 4.24
1.142 + const TInteger& n = aProbablePrime;
1.143 + assert(n > KLastSmallPrimeSquared);
1.144 + assert(n.IsOdd());
1.145 + assert(aBase > TInteger::One());
1.146 +
1.147 + RInteger nminus1 = n.MinusL(TInteger::One());
1.148 + CleanupStack::PushL(nminus1);
1.149 + assert(aBase < nminus1);
1.150 +
1.151 + // 1) find (s | 2^s*r == n-1) where r is odd
1.152 + // we want the largest power of 2 that divides n-1
1.153 + TUint s=0;
1.154 + for(;;s++)
1.155 + {
1.156 + if(nminus1.Bit(s))
1.157 + {
1.158 + break;
1.159 + }
1.160 + }
1.161 + // (r = (n-1) / 2^s) which is equiv to (n-1 >>= s)
1.162 + RInteger r = RInteger::NewL(nminus1);
1.163 + CleanupStack::PushL(r);
1.164 + r >>= s;
1.165 +
1.166 + //At no point do we own y, aMont owns it
1.167 + const TInteger* y = &(aMont.ExponentiateL(aBase, r));
1.168 +
1.169 + TBool probablePrime = EFalse;
1.170 +
1.171 + TUint j=1;
1.172 + if( *y == TInteger::One() || *y == nminus1 )
1.173 + {
1.174 + probablePrime = ETrue;
1.175 + }
1.176 + else
1.177 + {
1.178 + for(j=1; j<s; j++)
1.179 + {
1.180 + y = &(aMont.SquareL(*y));
1.181 + if(*y == nminus1)
1.182 + {
1.183 + probablePrime = ETrue;
1.184 + break;
1.185 + }
1.186 + }
1.187 + }
1.188 + CleanupStack::PopAndDestroy(&r);
1.189 + CleanupStack::PopAndDestroy(&nminus1);//y,r,nminus1
1.190 + return probablePrime;
1.191 + }
1.192 +
1.193 +static TBool RabinMillerTestL(const CMontgomeryStructure& aMont,
1.194 + const TInteger& aProbablePrime, TUint aRounds)
1.195 + {
1.196 + const TInteger& n = aProbablePrime;
1.197 + assert(n > KLastSmallPrimeSquared);
1.198 +
1.199 + RInteger nminus2 = n.MinusL(TInteger::Two());
1.200 + CleanupStack::PushL(nminus2);
1.201 +
1.202 + for(TUint i=0; i<aRounds; i++)
1.203 + {
1.204 + RInteger base = RInteger::NewRandomL(TInteger::Two(), nminus2);
1.205 + CleanupStack::PushL(base);
1.206 + if(!RabinMillerIterationL(aMont, n, base))
1.207 + {
1.208 + CleanupStack::PopAndDestroy(2, &nminus2);//base, nminus2
1.209 + return EFalse;
1.210 + }
1.211 + CleanupStack::PopAndDestroy(&base);
1.212 + }
1.213 + CleanupStack::PopAndDestroy(&nminus2);
1.214 + return ETrue;
1.215 + }
1.216 +
1.217 +static TBool IsStrongProbablePrimeL(const TInteger& aPrime)
1.218 + {
1.219 + CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aPrime);
1.220 + //This should be using short circuit evaluation
1.221 + TBool probablePrime = RabinMillerIterationL(*mont, aPrime, TInteger::Two())
1.222 + && RabinMillerTestL(*mont, aPrime,RabinMillerRounds(aPrime.BitCount()));
1.223 + CleanupStack::PopAndDestroy(mont);
1.224 + return probablePrime;
1.225 + }
1.226 +
1.227 +/* In the _vast_ majority of cases this simply checks that your chosen random
1.228 + * number is >= KLastSmallPrimeSquared and return EFalse and lets the normal
1.229 + * prime generation routines handle the situation. In the case where it is
1.230 + * smaller, it generates a provable prime and returns ETrue. The algorithm for
1.231 + * finding a provable prime < KLastPrimeSquared is not the most efficient in the
1.232 + * world, but two points come to mind
1.233 + * 1) The two if statements hardly _ever_ evaluate to ETrue in real life.
1.234 + * 2) Even when it is, the distribution of primes < KLastPrimeSquared is pretty
1.235 + * dense, so you aren't going to have check many.
1.236 + * This function is essentially here for two reasons:
1.237 + * 1) Ensures that it is possible to generate primes < KLastPrimeSquared (the
1.238 + * test code does this)
1.239 + * 2) Ensures that if you request a prime of a large bit size that there is an
1.240 + * even probability distribution across all integers < 2^aBits
1.241 + */
1.242 +TBool TInteger::SmallPrimeRandomizeL(void)
1.243 + {
1.244 + TBool foundPrime = EFalse;
1.245 + //If the random number we've chosen is less than KLastSmallPrime,
1.246 + //testing for primality is easy.
1.247 + if(*this <= KLastSmallPrime)
1.248 + {
1.249 + //If Zero or One, or two, next prime number is two
1.250 + if(IsZero() || *this == One() || *this == Two())
1.251 + {
1.252 + CopyL(TInteger::Two());
1.253 + foundPrime = ETrue;
1.254 + }
1.255 + else
1.256 + {
1.257 + //Make sure any number we bother testing is at least odd
1.258 + SetBit(0);
1.259 + //Binary search the small primes.
1.260 + while(!IsSmallPrime(ConvertToUnsignedLong()))
1.261 + {
1.262 + //If not prime, add two and try the next odd number.
1.263 +
1.264 + //will never carry as the minimum size of an RInteger is 2
1.265 + //words. Much bigger than KLastSmallPrime on 32bit
1.266 + //architectures.
1.267 + IncrementNoCarry(Ptr(), Size(), 2);
1.268 + }
1.269 + assert(IsSmallPrime(ConvertToUnsignedLong()));
1.270 + foundPrime = ETrue;
1.271 + }
1.272 + }
1.273 + else if(*this <= KLastSmallPrimeSquared)
1.274 + {
1.275 + //Make sure any number we bother testing is at least odd
1.276 + SetBit(0);
1.277 +
1.278 + while(HasSmallDivisorL(*this) && *this <= KLastSmallPrimeSquared)
1.279 + {
1.280 + //If not prime, add two and try the next odd number.
1.281 +
1.282 + //will never carry as the minimum size of an RInteger is 2
1.283 + //words. Much bigger than KLastSmallPrime on 32bit
1.284 + //architectures.
1.285 + IncrementNoCarry(Ptr(), Size(), 2);
1.286 + }
1.287 + //If we exited while loop because it had no small divisor then it is
1.288 + //prime. Otherwise, we've exceeded the limit of what we can provably
1.289 + //generate. Therefore the normal prime gen routines will be run on it
1.290 + //now.
1.291 + if(*this < KLastSmallPrimeSquared)
1.292 + {
1.293 + foundPrime = ETrue;
1.294 + }
1.295 + }
1.296 + //This doesn't mean there is no such prime, simply means that the number
1.297 + //wasn't less than KSmallPrimeSquared and needs to be handled by the normal
1.298 + //prime generation routines.
1.299 + return foundPrime;
1.300 + }
1.301 +
1.302 +void TInteger::PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)
1.303 + {
1.304 + assert(aBits > 1);
1.305 +
1.306 + //"this" is "empty" currently. Consists of Size() words of 0's. This is just
1.307 + //checking that sign flag is positive as we don't set it later.
1.308 + assert(NotNegative());
1.309 +
1.310 + //Flag for the whole function saying if we've found a prime
1.311 + TBool foundProbablePrime = EFalse;
1.312 +
1.313 + //Find 2^aBits + 1 -- any prime we find must be less than this.
1.314 + RInteger max = RInteger::NewEmptyL(BitsToWords(aBits)+1);
1.315 + CleanupStack::PushL(max);
1.316 + max.SetBit(aBits);
1.317 + assert(max.BitCount()-1 == aBits);
1.318 +
1.319 + // aBits | approx number of odd numbers you must try to have a 50%
1.320 + // chance of finding a prime
1.321 + //---------------------------------------------------------
1.322 + // 512 | 122
1.323 + // 1024 | 245
1.324 + // 2048 | 1023
1.325 + //Therefore if we are generating larger than 1024 bit numbers we'll use a
1.326 + //bigger bit array to have a better chance of avoiding re-generating it.
1.327 + TUint sLength = aBits > 1024 ? 1024 : 512;
1.328 + RInteger S = RInteger::NewEmptyL(BitsToWords(sLength));
1.329 + CleanupStack::PushL(S);
1.330 +
1.331 + while(!foundProbablePrime)
1.332 + {
1.333 + //Randomly choose aBits
1.334 + RandomizeL(aBits, aAttr);
1.335 +
1.336 + //If the random number chosen is less than KSmallPrimeSquared, we have a
1.337 + //special set of routines.
1.338 + if(SmallPrimeRandomizeL())
1.339 + {
1.340 + foundProbablePrime = ETrue;
1.341 + }
1.342 + else
1.343 + {
1.344 + //if it was <= KLastSmallPrimeSquared then it would have been
1.345 + //handled by SmallPrimeRandomizeL()
1.346 + assert(*this > KLastSmallPrimeSquared);
1.347 +
1.348 + //Make sure any number we bother testing is at least odd
1.349 + SetBit(0);
1.350 +
1.351 + //Ensure that this + 2*sLength < max
1.352 + RInteger temp = max.MinusL(*this);
1.353 + CleanupStack::PushL(temp);
1.354 + ++temp;
1.355 + temp >>=1;
1.356 + if(temp < sLength)
1.357 + {
1.358 + //if this + 2*sLength >= max then we use a smaller sLength to
1.359 + //ensure we don't find a number that is outside of our bounds
1.360 + //(and bigger than our allocated memory for this)
1.361 +
1.362 + //temp must be less than KMaxTUint as sLength is a TUint
1.363 + sLength = temp.ConvertToUnsignedLong();
1.364 + }
1.365 + CleanupStack::PopAndDestroy(&temp);
1.366 +
1.367 + //Start at 1 as no point in checking against 2 (all odd numbers)
1.368 + for(TUint i=1; i<KPrimeTableSize; i++)
1.369 + {
1.370 + //no need to call ModuloL as we know KPrimeTable[i] is not 0
1.371 + TUint remainder = Modulo(*this, KPrimeTable[i]);
1.372 + TUint index = FindSmallestIndex(KPrimeTable[i], remainder);
1.373 + EliminateComposites(S.Ptr(), KPrimeTable[i], index, sLength);
1.374 + }
1.375 + TInt j = FindFirstPrimeCandidate(S.Ptr(), sLength);
1.376 + TInt prev = 0;
1.377 + for(; j>=0; j=FindFirstPrimeCandidate(S.Ptr(), sLength))
1.378 + {
1.379 + ArraySetBit(S.Ptr(), j);
1.380 +
1.381 + //should never carry as we earlier made sure that 2*j + this < max
1.382 + //where max is 1 bit more than we asked for.
1.383 + IncrementNoCarry(Ptr(), Size(), 2*(j-prev));
1.384 +
1.385 + assert(*this < max);
1.386 + assert(!HasSmallDivisorL(*this));
1.387 +
1.388 + prev = j;
1.389 +
1.390 + if( IsStrongProbablePrimeL(*this) )
1.391 + {
1.392 + foundProbablePrime = ETrue;
1.393 + break;
1.394 + }
1.395 + }
1.396 + //This clears the memory
1.397 + S.CopyL(0, EFalse);
1.398 + }
1.399 + }
1.400 + CleanupStack::PopAndDestroy(2, &max);
1.401 + }
1.402 +
1.403 +EXPORT_C TBool TInteger::IsPrimeL(void) const
1.404 + {
1.405 + if( NotPositive() )
1.406 + {
1.407 + return EFalse;
1.408 + }
1.409 + else if( IsEven() )
1.410 + {
1.411 + return *this == Two();
1.412 + }
1.413 + else if( *this <= KLastSmallPrime )
1.414 + {
1.415 + assert(KLastSmallPrime < KMaxTUint);
1.416 + return IsSmallPrime(this->ConvertToUnsignedLong());
1.417 + }
1.418 + else if( *this <= KLastSmallPrimeSquared )
1.419 + {
1.420 + return !HasSmallDivisorL(*this);
1.421 + }
1.422 + else
1.423 + {
1.424 + return !HasSmallDivisorL(*this) && IsStrongProbablePrimeL(*this);
1.425 + }
1.426 + }
1.427 +
1.428 +// Method is excluded from coverage due to the problem with BullsEye on ONB.
1.429 +// Manually verified that this method is functionally covered.
1.430 +#ifdef _BullseyeCoverage
1.431 +#pragma suppress_warnings on
1.432 +#pragma BullseyeCoverage off
1.433 +#pragma suppress_warnings off
1.434 +#endif
1.435 +
1.436 +static TBool IsSmallPrime(TUint aK)
1.437 + {
1.438 + //This is just a binary search of our small prime table.
1.439 + TUint l = 0;
1.440 + TUint u = KPrimeTableSize;
1.441 + while( u > l )
1.442 + {
1.443 + TUint m = (l+u)>>1;
1.444 + TUint p = KPrimeTable[m];
1.445 + if(aK < p)
1.446 + u = m;
1.447 + else if (aK > p)
1.448 + l = m + 1;
1.449 + else
1.450 + return ETrue;
1.451 + }
1.452 + return EFalse;
1.453 + }