1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/security/crypto/weakcryptospi/source/bigint/bigint.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,1173 @@
1.4 +/*
1.5 +* Copyright (c) 2003-2010 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 <random.h>
1.23 +#include <bigint.h>
1.24 +#include <e32std.h>
1.25 +#include <euserext.h>
1.26 +#include <securityerr.h>
1.27 +#include "words.h"
1.28 +#include "algorithms.h"
1.29 +#include "windowslider.h"
1.30 +#include "stackinteger.h"
1.31 +#include "mont.h"
1.32 +
1.33 +
1.34 +/**
1.35 +* Creates a new buffer containing the big-endian binary representation of this
1.36 +* integer.
1.37 +*
1.38 +* Note that it does not support the exporting of negative integers.
1.39 +*
1.40 +* @return The new buffer.
1.41 +*
1.42 +* @leave KErrNegativeExportNotSupported If this instance is a negative integer.
1.43 +*
1.44 +*/
1.45 +EXPORT_C HBufC8* TInteger::BufferLC() const
1.46 + {
1.47 + if(IsNegative())
1.48 + {
1.49 + User::Leave(KErrNegativeExportNotSupported);
1.50 + }
1.51 + TUint bytes = ByteCount();
1.52 + HBufC8* buf = HBufC8::NewMaxLC(bytes);
1.53 + TUint8* bufPtr = (TUint8*)(buf->Ptr());
1.54 + TUint8* regPtr = (TUint8*)Ptr();
1.55 +
1.56 + // we internally store the number little endian, as a string we want it big
1.57 + // endian
1.58 + for(TUint i=0,j=bytes-1; i<bytes; )
1.59 + {
1.60 + bufPtr[i++] = regPtr[j--];
1.61 + }
1.62 + return buf;
1.63 + }
1.64 +
1.65 +EXPORT_C HBufC8* TInteger::BufferWithNoTruncationLC() const
1.66 + {
1.67 + if(IsNegative())
1.68 + {
1.69 + User::Leave(KErrNegativeExportNotSupported);
1.70 + }
1.71 +
1.72 + TUint wordCount = Size();
1.73 + TUint bytes = (wordCount)*WORD_SIZE;
1.74 +
1.75 + HBufC8* buf = HBufC8::NewMaxLC(bytes);
1.76 + TUint8* bufPtr = (TUint8*)(buf->Ptr());
1.77 + TUint8* regPtr = (TUint8*)Ptr();
1.78 + for(TUint i=0,j=bytes-1; i<bytes; )
1.79 + {
1.80 + bufPtr[i++] = regPtr[j--];
1.81 + }
1.82 +
1.83 + return buf;
1.84 + }
1.85 +
1.86 +/**
1.87 +* Gets the number of words required to represent this RInteger.
1.88 +*
1.89 +* @return The size of the integer in words.
1.90 +*
1.91 +*/
1.92 +EXPORT_C TUint TInteger::WordCount() const
1.93 + {
1.94 + return CountWords(Ptr(), Size());
1.95 + }
1.96 +
1.97 +/**
1.98 +* Gets the number of bytes required to represent this RInteger.
1.99 +*
1.100 +* @return The size of the integer in bytes.
1.101 +*
1.102 +*/
1.103 +EXPORT_C TUint TInteger::ByteCount() const
1.104 + {
1.105 + TUint wordCount = WordCount();
1.106 + if(wordCount)
1.107 + {
1.108 + return (wordCount-1)*WORD_SIZE + BytePrecision((Ptr())[wordCount-1]);
1.109 + }
1.110 + else
1.111 + {
1.112 + return 0;
1.113 + }
1.114 + }
1.115 +
1.116 +/**
1.117 +* Get the number of bits required to represent this RInteger.
1.118 +*
1.119 +* @return The size of the integer in bits.
1.120 +*
1.121 +*/
1.122 +EXPORT_C TUint TInteger::BitCount() const
1.123 + {
1.124 + TUint wordCount = WordCount();
1.125 + if(wordCount)
1.126 + {
1.127 + return (wordCount-1)*WORD_BITS + BitPrecision(Ptr()[wordCount-1]);
1.128 + }
1.129 + else
1.130 + {
1.131 + return 0;
1.132 + }
1.133 + }
1.134 +
1.135 +
1.136 +//These 3 declarations instantiate a constant 0, 1, 2 for ease of use and
1.137 +//quick construction elsewhere in the code. Note that the functions
1.138 +//returning references to this static data return const references as you can't
1.139 +//modify the ROM ;)
1.140 +//word 0: Size of storage in words
1.141 +//word 1: Pointer to storage
1.142 +//word 2: LSW of storage
1.143 +//word 3: MSW of storage
1.144 +//Note that the flag bits in word 1 (Ptr()) are zero in the case of a positive
1.145 +//stack based integer (SignBit == 0, IsHeapBasedBit == 0)
1.146 +const TUint KBigintZero[4] = {2, (TUint)(KBigintZero+2), 0, 0};
1.147 +const TUint KBigintOne[4] = {2, (TUint)(KBigintOne+2), 1, 0};
1.148 +const TUint KBigintTwo[4] = {2, (TUint)(KBigintTwo+2), 2, 0};
1.149 +
1.150 +/**
1.151 + * Gets the TInteger that represents zero
1.152 + *
1.153 + * @return The TInteger representing zero
1.154 + */
1.155 +EXPORT_C const TInteger& TInteger::Zero(void)
1.156 + {
1.157 + return *reinterpret_cast<const TStackInteger64*>(KBigintZero);
1.158 + }
1.159 +
1.160 +/**
1.161 + * Gets the TInteger that represents one
1.162 + *
1.163 + * @return The TInteger representing one
1.164 + */
1.165 +EXPORT_C const TInteger& TInteger::One(void)
1.166 + {
1.167 + return *reinterpret_cast<const TStackInteger64*>(KBigintOne);
1.168 + }
1.169 +
1.170 +/**
1.171 + * Gets the TInteger that represents two
1.172 + *
1.173 + * @return The TInteger representing two
1.174 + */
1.175 +EXPORT_C const TInteger& TInteger::Two(void)
1.176 + {
1.177 + return *reinterpret_cast<const TStackInteger64*>(KBigintTwo);
1.178 + }
1.179 +
1.180 +EXPORT_C RInteger TInteger::PlusL(const TInteger& aOperand) const
1.181 + {
1.182 + RInteger sum;
1.183 + if (NotNegative())
1.184 + {
1.185 + if (aOperand.NotNegative())
1.186 + sum = PositiveAddL(*this, aOperand);
1.187 + else
1.188 + sum = PositiveSubtractL(*this, aOperand);
1.189 + }
1.190 + else
1.191 + {
1.192 + if (aOperand.NotNegative())
1.193 + sum = PositiveSubtractL(aOperand, *this);
1.194 + else
1.195 + {
1.196 + sum = PositiveAddL(*this, aOperand);
1.197 + sum.SetSign(TInteger::ENegative);
1.198 + }
1.199 + }
1.200 + return sum;
1.201 + }
1.202 +
1.203 +EXPORT_C RInteger TInteger::MinusL(const TInteger& aOperand) const
1.204 + {
1.205 + RInteger diff;
1.206 + if (NotNegative())
1.207 + {
1.208 + if (aOperand.NotNegative())
1.209 + diff = PositiveSubtractL(*this, aOperand);
1.210 + else
1.211 + diff = PositiveAddL(*this, aOperand);
1.212 + }
1.213 + else
1.214 + {
1.215 + if (aOperand.NotNegative())
1.216 + {
1.217 + diff = PositiveAddL(*this, aOperand);
1.218 + diff.SetSign(TInteger::ENegative);
1.219 + }
1.220 + else
1.221 + diff = PositiveSubtractL(aOperand, *this);
1.222 + }
1.223 + return diff;
1.224 + }
1.225 +
1.226 +EXPORT_C RInteger TInteger::TimesL(const TInteger& aOperand) const
1.227 + {
1.228 + RInteger product = PositiveMultiplyL(*this, aOperand);
1.229 +
1.230 + if (NotNegative() != aOperand.NotNegative())
1.231 + {
1.232 + product.Negate();
1.233 + }
1.234 + return product;
1.235 + }
1.236 +
1.237 +EXPORT_C RInteger TInteger::DividedByL(const TInteger& aOperand) const
1.238 + {
1.239 + RInteger quotient;
1.240 + RInteger remainder;
1.241 + DivideL(remainder, quotient, *this, aOperand);
1.242 + remainder.Close();
1.243 + return quotient;
1.244 + }
1.245 +
1.246 +EXPORT_C RInteger TInteger::ModuloL(const TInteger& aOperand) const
1.247 + {
1.248 + RInteger remainder;
1.249 + RInteger quotient;
1.250 + DivideL(remainder, quotient, *this, aOperand);
1.251 + quotient.Close();
1.252 + return remainder;
1.253 + }
1.254 +
1.255 +EXPORT_C TUint TInteger::ModuloL(TUint aOperand) const
1.256 + {
1.257 + if(!aOperand)
1.258 + {
1.259 + User::Leave(KErrDivideByZero);
1.260 + }
1.261 + return Modulo(*this, aOperand);
1.262 + }
1.263 +
1.264 +EXPORT_C RInteger TInteger::ModularMultiplyL(const TInteger& aA, const TInteger& aB,
1.265 + const TInteger& aMod)
1.266 + {
1.267 + RInteger product = aA.TimesL(aB);
1.268 + CleanupStack::PushL(product);
1.269 + RInteger reduced = product.ModuloL(aMod);
1.270 + CleanupStack::PopAndDestroy(&product);
1.271 + return reduced;
1.272 + }
1.273 +
1.274 +EXPORT_C RInteger TInteger::ModularExponentiateL(const TInteger& aBase,
1.275 + const TInteger& aExp, const TInteger& aMod)
1.276 + {
1.277 + CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aMod);
1.278 + RInteger result = RInteger::NewL(mont->ExponentiateL(aBase, aExp));
1.279 + CleanupStack::PopAndDestroy(mont);
1.280 + return result;
1.281 + }
1.282 +
1.283 +EXPORT_C RInteger TInteger::GCDL(const TInteger& aOperand) const
1.284 + {
1.285 + //Binary GCD algorithm -- see HAC 14.4.1
1.286 + //with a slight variation -- our g counts shifts rather than actually
1.287 + //shifting. We then do one shift at the end.
1.288 + assert(NotNegative());
1.289 + assert(aOperand.NotNegative());
1.290 +
1.291 + RInteger x = RInteger::NewL(*this);
1.292 + CleanupStack::PushL(x);
1.293 + RInteger y = RInteger::NewL(aOperand);
1.294 + CleanupStack::PushL(y);
1.295 +
1.296 + // 1 Ensure x >= y
1.297 + if( x < y )
1.298 + {
1.299 + TClassSwap(x, y);
1.300 + }
1.301 +
1.302 + TUint g = 0;
1.303 + // 2 while x and y even x <- x/2, y <- y/2
1.304 + while( x.IsEven() && y.IsEven() )
1.305 + {
1.306 + x >>= 1;
1.307 + y >>= 1;
1.308 + ++g;
1.309 + }
1.310 + // 3 while x != 0
1.311 + while( x.NotZero() )
1.312 + {
1.313 + // 3.1 while x even x <- x/2
1.314 + while( x.IsEven() )
1.315 + {
1.316 + x >>= 1;
1.317 + }
1.318 + // 3.2 while y even y <- y/2
1.319 + while( y.IsEven() )
1.320 + {
1.321 + y >>= 1;
1.322 + }
1.323 + // 3.3 t <- abs(x-y)/2
1.324 + RInteger t = x.MinusL(y);
1.325 + t >>= 1;
1.326 + t.SetSign(TInteger::EPositive);
1.327 +
1.328 + // 3.4 If x>=y then x <- t else y <- t
1.329 + if( x >= y )
1.330 + {
1.331 + x.Set(t);
1.332 + }
1.333 + else
1.334 + {
1.335 + y.Set(t);
1.336 + }
1.337 + }
1.338 +
1.339 + // 4 Return (g*y) (equiv to y<<=g as our g was counting shifts not actually
1.340 + //shifting)
1.341 + y <<= g;
1.342 + CleanupStack::Pop(&y);
1.343 + CleanupStack::PopAndDestroy(&x);
1.344 + return y;
1.345 + }
1.346 +
1.347 +EXPORT_C RInteger TInteger::InverseModL(const TInteger& aMod) const
1.348 + {
1.349 + assert(aMod.NotNegative());
1.350 +
1.351 + RInteger result;
1.352 + if(IsNegative() || *this>=aMod)
1.353 + {
1.354 + RInteger temp = ModuloL(aMod);
1.355 + CleanupClosePushL(temp);
1.356 + result = temp.InverseModL(aMod);
1.357 + CleanupStack::PopAndDestroy(&temp);
1.358 + return result;
1.359 + }
1.360 +
1.361 + if(aMod.IsEven())
1.362 + {
1.363 + if( !aMod || IsEven() )
1.364 + {
1.365 + return RInteger::NewL(Zero());
1.366 + }
1.367 + if( *this == One() )
1.368 + {
1.369 + return RInteger::NewL(One());
1.370 + }
1.371 + RInteger u = aMod.InverseModL(*this);
1.372 + CleanupClosePushL(u);
1.373 + if(!u)
1.374 + {
1.375 + result = RInteger::NewL(Zero());
1.376 + }
1.377 + else
1.378 + {
1.379 + //calculates (aMod*(*this-u)+1)/(*this)
1.380 + result = MinusL(u);
1.381 + CleanupClosePushL(result);
1.382 + result *= aMod;
1.383 + ++result;
1.384 + result /= *this;
1.385 + CleanupStack::Pop(&result);
1.386 + }
1.387 + CleanupStack::PopAndDestroy(&u);
1.388 + return result;
1.389 + }
1.390 +
1.391 + result = RInteger::NewEmptyL(aMod.Size());
1.392 + CleanupClosePushL(result);
1.393 + RInteger workspace = RInteger::NewEmptyL(aMod.Size() * 4);
1.394 + TUint k = AlmostInverse(result.Ptr(), workspace.Ptr(), Ptr(), Size(),
1.395 + aMod.Ptr(), aMod.Size());
1.396 + DivideByPower2Mod(result.Ptr(), result.Ptr(), k, aMod.Ptr(), aMod.Size());
1.397 + workspace.Close();
1.398 + CleanupStack::Pop(&result);
1.399 +
1.400 + return result;
1.401 + }
1.402 +
1.403 +EXPORT_C TInteger& TInteger::operator+=(const TInteger& aOperand)
1.404 + {
1.405 + this->Set(PlusL(aOperand));
1.406 + return *this;
1.407 + }
1.408 +
1.409 +EXPORT_C TInteger& TInteger::operator-=(const TInteger& aOperand)
1.410 + {
1.411 + this->Set(MinusL(aOperand));
1.412 + return *this;
1.413 + }
1.414 +
1.415 +EXPORT_C TInteger& TInteger::operator*=(const TInteger& aOperand)
1.416 + {
1.417 + this->Set(TimesL(aOperand));
1.418 + return *this;
1.419 + }
1.420 +
1.421 +EXPORT_C TInteger& TInteger::operator/=(const TInteger& aOperand)
1.422 + {
1.423 + this->Set(DividedByL(aOperand));
1.424 + return *this;
1.425 + }
1.426 +
1.427 +EXPORT_C TInteger& TInteger::operator%=(const TInteger& aOperand)
1.428 + {
1.429 + this->Set(ModuloL(aOperand));
1.430 + return *this;
1.431 + }
1.432 +
1.433 +EXPORT_C TInteger& TInteger::operator+=(TInt aOperand)
1.434 + {
1.435 + TStackInteger64 operand(aOperand);
1.436 + *this += operand;
1.437 + return *this;
1.438 + }
1.439 +
1.440 +EXPORT_C TInteger& TInteger::operator-=(TInt aOperand)
1.441 + {
1.442 + TStackInteger64 operand(aOperand);
1.443 + *this -= operand;
1.444 + return *this;
1.445 + }
1.446 +
1.447 +EXPORT_C TInteger& TInteger::operator*=(TInt aOperand)
1.448 + {
1.449 + TStackInteger64 operand(aOperand);
1.450 + *this *= operand;
1.451 + return *this;
1.452 + }
1.453 +
1.454 +EXPORT_C TInteger& TInteger::operator--()
1.455 + {
1.456 + if (IsNegative())
1.457 + {
1.458 + if (Increment(Ptr(), Size()))
1.459 + {
1.460 + CleanGrowL(2*Size());
1.461 + (Ptr())[Size()/2]=1;
1.462 + }
1.463 + }
1.464 + else
1.465 + {
1.466 + if (Decrement(Ptr(), Size()))
1.467 + {
1.468 + this->CopyL(-1);
1.469 + }
1.470 + }
1.471 + return *this;
1.472 + }
1.473 +
1.474 +EXPORT_C TInteger& TInteger::operator++()
1.475 + {
1.476 + if(NotNegative())
1.477 + {
1.478 + if(Increment(Ptr(), Size()))
1.479 + {
1.480 + CleanGrowL(2*Size());
1.481 + (Ptr())[Size()/2]=1;
1.482 + }
1.483 + }
1.484 + else
1.485 + {
1.486 + DecrementNoCarry(Ptr(), Size());
1.487 + if(WordCount()==0)
1.488 + {
1.489 + this->CopyL(Zero());
1.490 + }
1.491 + }
1.492 + return *this;
1.493 + }
1.494 +
1.495 +EXPORT_C TInteger& TInteger::operator <<=(TUint aBits)
1.496 + {
1.497 + const TUint wordCount = WordCount();
1.498 + const TUint shiftWords = aBits / WORD_BITS;
1.499 + const TUint shiftBits = aBits % WORD_BITS;
1.500 +
1.501 + CleanGrowL(wordCount+BitsToWords(aBits));
1.502 + ShiftWordsLeftByWords(Ptr(), wordCount + shiftWords, shiftWords);
1.503 + ShiftWordsLeftByBits(Ptr()+shiftWords, wordCount + BitsToWords(shiftBits),
1.504 + shiftBits);
1.505 + return *this;
1.506 + }
1.507 +
1.508 +EXPORT_C TInteger& TInteger::operator >>=(TUint aBits)
1.509 + {
1.510 + const TUint wordCount = WordCount();
1.511 + const TUint shiftWords = aBits / WORD_BITS;
1.512 + const TUint shiftBits = aBits % WORD_BITS;
1.513 +
1.514 + ShiftWordsRightByWords(Ptr(), wordCount, shiftWords);
1.515 + if(wordCount > shiftWords)
1.516 + {
1.517 + ShiftWordsRightByBits(Ptr(), wordCount - shiftWords, shiftBits);
1.518 + }
1.519 + if(IsNegative() && WordCount()==0) // avoid negative 0
1.520 + {
1.521 + SetSign(EPositive);
1.522 + }
1.523 + return *this;
1.524 + }
1.525 +
1.526 +EXPORT_C TInt TInteger::UnsignedCompare(const TInteger& aThat) const
1.527 + {
1.528 + TUint size = WordCount();
1.529 + TUint thatSize = aThat.WordCount();
1.530 +
1.531 + if( size == thatSize )
1.532 + return Compare(Ptr(), aThat.Ptr(), size);
1.533 + else
1.534 + return size > thatSize ? 1 : -1;
1.535 + }
1.536 +
1.537 +EXPORT_C TInt TInteger::SignedCompare(const TInteger& aThat) const
1.538 + {
1.539 + if (NotNegative())
1.540 + {
1.541 + if (aThat.NotNegative())
1.542 + return UnsignedCompare(aThat);
1.543 + else
1.544 + return 1;
1.545 + }
1.546 + else
1.547 + {
1.548 + if (aThat.NotNegative())
1.549 + return -1;
1.550 + else
1.551 + return -UnsignedCompare(aThat);
1.552 + }
1.553 + }
1.554 +
1.555 +EXPORT_C TBool TInteger::operator!() const
1.556 + {
1.557 + //Ptr()[0] is just a quick way of weeding out non-zero numbers without
1.558 + //doing a full WordCount() == 0. Very good odds that a non-zero number
1.559 + //will have a bit set in the least significant word
1.560 + return IsNegative() ? EFalse : (Ptr()[0]==0 && WordCount()==0);
1.561 + }
1.562 +
1.563 +EXPORT_C TInt TInteger::SignedCompare(TInt aInteger) const
1.564 + {
1.565 + TStackInteger64 temp(aInteger);
1.566 + return SignedCompare(temp);
1.567 + }
1.568 +
1.569 +/* TBool IsPrimeL(void) const
1.570 + * and all primality related functions are implemented in primes.cpp */
1.571 +
1.572 +EXPORT_C TBool TInteger::Bit(TUint aBitPos) const
1.573 + {
1.574 + if( aBitPos/WORD_BITS >= Size() )
1.575 + {
1.576 + return 0;
1.577 + }
1.578 + else
1.579 + {
1.580 + return (((Ptr())[aBitPos/WORD_BITS] >> (aBitPos % WORD_BITS)) & 1);
1.581 + }
1.582 + }
1.583 +
1.584 +EXPORT_C void TInteger::SetBit(TUint aBitPos)
1.585 + {
1.586 + if( aBitPos/WORD_BITS < Size() )
1.587 + {
1.588 + ArraySetBit(Ptr(), aBitPos);
1.589 + }
1.590 + }
1.591 +
1.592 +EXPORT_C void TInteger::Negate()
1.593 + {
1.594 + if(!!(*this)) //don't flip sign if *this==0
1.595 + {
1.596 + SetSign(TSign((~Sign())&KSignMask));
1.597 + }
1.598 + }
1.599 +
1.600 +EXPORT_C void TInteger::CopyL(const TInteger& aInteger, TBool aAllowShrink)
1.601 + {
1.602 + if(aAllowShrink)
1.603 + {
1.604 + CleanResizeL(aInteger.Size());
1.605 + }
1.606 + else
1.607 + {
1.608 + CleanGrowL(aInteger.Size());
1.609 + }
1.610 + Construct(aInteger);
1.611 + }
1.612 +
1.613 +EXPORT_C void TInteger::CopyL(TInt aInteger, TBool aAllowShrink)
1.614 + {
1.615 + if(aAllowShrink)
1.616 + {
1.617 + CleanResizeL(2);
1.618 + }
1.619 + else
1.620 + {
1.621 + CleanGrowL(2);
1.622 + }
1.623 + Construct(aInteger);
1.624 + }
1.625 +
1.626 +EXPORT_C void TInteger::Set(const RInteger& aInteger)
1.627 + {
1.628 + assert(IsHeapBased());
1.629 + Mem::FillZ(Ptr(), WordsToBytes(Size()));
1.630 + User::Free(Ptr());
1.631 + iPtr = aInteger.iPtr;
1.632 + iSize = aInteger.iSize;
1.633 + }
1.634 +
1.635 +RInteger TInteger::PositiveAddL(const TInteger &aA, const TInteger& aB) const
1.636 + {
1.637 + RInteger sum = RInteger::NewEmptyL(CryptoMax(aA.Size(), aB.Size()));
1.638 + const word aSize = aA.Size();
1.639 + const word bSize = aB.Size();
1.640 + const word* const aReg = aA.Ptr();
1.641 + const word* const bReg = aB.Ptr();
1.642 + word* const sumReg = sum.Ptr();
1.643 +
1.644 + word carry;
1.645 + if (aSize == bSize)
1.646 + carry = Add(sumReg, aReg, bReg, aSize);
1.647 + else if (aSize > bSize)
1.648 + {
1.649 + carry = Add(sumReg, aReg, bReg, bSize);
1.650 + CopyWords(sumReg+bSize, aReg+bSize, aSize-bSize);
1.651 + carry = Increment(sumReg+bSize, aSize-bSize, carry);
1.652 + }
1.653 + else
1.654 + {
1.655 + carry = Add(sumReg, aReg, bReg, aSize);
1.656 + CopyWords(sumReg+aSize, bReg+aSize, bSize-aSize);
1.657 + carry = Increment(sumReg+aSize, bSize-aSize, carry);
1.658 + }
1.659 +
1.660 + if (carry)
1.661 + {
1.662 + CleanupStack::PushL(sum);
1.663 + sum.CleanGrowL(2*sum.Size());
1.664 + CleanupStack::Pop(&sum);
1.665 + sum.Ptr()[sum.Size()/2] = 1;
1.666 + }
1.667 + sum.SetSign(TInteger::EPositive);
1.668 + return sum;
1.669 + }
1.670 +
1.671 +RInteger TInteger::PositiveSubtractL(const TInteger &aA, const TInteger& aB) const
1.672 + {
1.673 + RInteger diff = RInteger::NewEmptyL(CryptoMax(aA.Size(), aB.Size()));
1.674 + unsigned aSize = aA.WordCount();
1.675 + aSize += aSize%2;
1.676 + unsigned bSize = aB.WordCount();
1.677 + bSize += bSize%2;
1.678 + const word* const aReg = aA.Ptr();
1.679 + const word* const bReg = aB.Ptr();
1.680 + word* const diffReg = diff.Ptr();
1.681 +
1.682 + if (aSize == bSize)
1.683 + {
1.684 + if (Compare(aReg, bReg, aSize) >= 0)
1.685 + {
1.686 + Subtract(diffReg, aReg, bReg, aSize);
1.687 + diff.SetSign(TInteger::EPositive);
1.688 + }
1.689 + else
1.690 + {
1.691 + Subtract(diffReg, bReg, aReg, aSize);
1.692 + diff.SetSign(TInteger::ENegative);
1.693 + }
1.694 + }
1.695 + else if (aSize > bSize)
1.696 + {
1.697 + word borrow = Subtract(diffReg, aReg, bReg, bSize);
1.698 + CopyWords(diffReg+bSize, aReg+bSize, aSize-bSize);
1.699 + borrow = Decrement(diffReg+bSize, aSize-bSize, borrow);
1.700 + assert(!borrow);
1.701 + diff.SetSign(TInteger::EPositive);
1.702 + }
1.703 + else
1.704 + {
1.705 + word borrow = Subtract(diffReg, bReg, aReg, aSize);
1.706 + CopyWords(diffReg+aSize, bReg+aSize, bSize-aSize);
1.707 + borrow = Decrement(diffReg+aSize, bSize-aSize, borrow);
1.708 + assert(!borrow);
1.709 + diff.SetSign(TInteger::ENegative);
1.710 + }
1.711 + return diff;
1.712 + }
1.713 +
1.714 +RInteger TInteger::PositiveMultiplyL(const TInteger &aA, const TInteger &aB) const
1.715 + {
1.716 + unsigned aSize = RoundupSize(aA.WordCount());
1.717 + unsigned bSize = RoundupSize(aB.WordCount());
1.718 +
1.719 + RInteger product = RInteger::NewEmptyL(aSize+bSize);
1.720 + CleanupClosePushL(product);
1.721 +
1.722 + RInteger workspace = RInteger::NewEmptyL(aSize + bSize);
1.723 + AsymmetricMultiply(product.Ptr(), workspace.Ptr(), aA.Ptr(), aSize, aB.Ptr(),
1.724 + bSize);
1.725 + workspace.Close();
1.726 + CleanupStack::Pop(&product);
1.727 + return product;
1.728 + }
1.729 +
1.730 +TUint TInteger::Modulo(const TInteger& aDividend, TUint aDivisor) const
1.731 + {
1.732 + assert(aDivisor);
1.733 + TUint i = aDividend.WordCount();
1.734 + TUint remainder = 0;
1.735 + while(i--)
1.736 + {
1.737 + remainder = TUint(MAKE_DWORD(aDividend.Ptr()[i], remainder) % aDivisor);
1.738 + }
1.739 + return remainder;
1.740 + }
1.741 +
1.742 +void TInteger::PositiveDivideL(RInteger &aRemainder, RInteger &aQuotient,
1.743 + const TInteger &aDividend, const TInteger &aDivisor) const
1.744 + {
1.745 + unsigned dividendSize = aDividend.WordCount();
1.746 + unsigned divisorSize = aDivisor.WordCount();
1.747 +
1.748 + if (!divisorSize)
1.749 + {
1.750 + User::Leave(KErrDivideByZero);
1.751 + }
1.752 +
1.753 + if (aDividend.UnsignedCompare(aDivisor) == -1)
1.754 + {
1.755 + aRemainder.CreateNewL(aDividend.Size());
1.756 + CleanupStack::PushL(aRemainder);
1.757 + aRemainder.CopyL(aDividend); //set remainder to a
1.758 + aRemainder.SetSign(TInteger::EPositive);
1.759 + aQuotient.CleanNewL(2); //Set quotient to zero
1.760 + CleanupStack::Pop(&aRemainder);
1.761 + return;
1.762 + }
1.763 +
1.764 + dividendSize += dividendSize%2; // round up to next even number
1.765 + divisorSize += divisorSize%2;
1.766 +
1.767 + aRemainder.CleanNewL(divisorSize);
1.768 + CleanupStack::PushL(aRemainder);
1.769 + aQuotient.CleanNewL(dividendSize-divisorSize+2);
1.770 + CleanupStack::PushL(aQuotient);
1.771 +
1.772 + RInteger T = RInteger::NewEmptyL(dividendSize+2*divisorSize+4);
1.773 + Divide(aRemainder.Ptr(), aQuotient.Ptr(), T.Ptr(), aDividend.Ptr(),
1.774 + dividendSize, aDivisor.Ptr(), divisorSize);
1.775 + T.Close();
1.776 + CleanupStack::Pop(2, &aRemainder); //aQuotient, aRemainder
1.777 + }
1.778 +
1.779 +void TInteger::DivideL(RInteger& aRemainder, RInteger& aQuotient,
1.780 + const TInteger& aDividend, const TInteger& aDivisor) const
1.781 + {
1.782 + PositiveDivideL(aRemainder, aQuotient, aDividend, aDivisor);
1.783 +
1.784 + if (aDividend.IsNegative())
1.785 + {
1.786 + aQuotient.Negate();
1.787 + if (aRemainder.NotZero())
1.788 + {
1.789 + --aQuotient;
1.790 + assert(aRemainder.Size() <= aDivisor.Size());
1.791 + Subtract(aRemainder.Ptr(), aDivisor.Ptr(), aRemainder.Ptr(),
1.792 + aRemainder.Size());
1.793 + }
1.794 + }
1.795 +
1.796 + if (aDivisor.IsNegative())
1.797 + aQuotient.Negate();
1.798 + }
1.799 +
1.800 +void TInteger::RandomizeL(TUint aBits, TRandomAttribute aAttr)
1.801 + {
1.802 + if(!aBits)
1.803 + {
1.804 + return;
1.805 + }
1.806 + const TUint bytes = BitsToBytes(aBits);
1.807 + const TUint words = BitsToWords(aBits);
1.808 + CleanGrowL(words);
1.809 + TPtr8 buf((TUint8*)(Ptr()), bytes, WordsToBytes(Size()));
1.810 + TUint bitpos = aBits % BYTE_BITS;
1.811 + TRAPD(err, GenerateRandomBytesL(buf));
1.812 + if((err != KErrNone) && (err != KErrNotSecure))
1.813 + User::Leave(err);
1.814 + //mask with 0 all bits above the num requested in the most significant byte
1.815 + if(bitpos)
1.816 + {
1.817 + buf[bytes-1] = TUint8( buf[bytes-1] & ((1L << bitpos) - 1) );
1.818 + }
1.819 + //set most significant (top) bit
1.820 + if(aAttr == ETopBitSet || aAttr == ETop2BitsSet)
1.821 + {
1.822 + SetBit(aBits-1); //Set bit counts from 0
1.823 + assert(BitCount() == aBits);
1.824 + assert(Bit(aBits-1));
1.825 + }
1.826 + //set 2nd bit from top
1.827 + if(aAttr == ETop2BitsSet)
1.828 + {
1.829 + SetBit(aBits-2); //Set bit counts from 0
1.830 + assert(BitCount() == aBits);
1.831 + assert(Bit(aBits-1));
1.832 + assert(Bit(aBits-2));
1.833 + }
1.834 + }
1.835 +
1.836 +void TInteger::RandomizeL(const TInteger& aMin, const TInteger& aMax)
1.837 + {
1.838 + assert(aMax > aMin);
1.839 + assert(aMin.NotNegative());
1.840 + RInteger range = RInteger::NewL(aMax);
1.841 + CleanupStack::PushL(range);
1.842 + range -= aMin;
1.843 + const TUint bits = range.BitCount();
1.844 +
1.845 + //if we find a number < range then aMin+range < aMax
1.846 + do
1.847 + {
1.848 + RandomizeL(bits, EAllBitsRandom);
1.849 + }
1.850 + while(*this > range);
1.851 +
1.852 + *this += aMin;
1.853 + CleanupStack::PopAndDestroy(&range);
1.854 + }
1.855 +
1.856 +/* void PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)
1.857 + * and all primality related functions are implemented in primes.cpp */
1.858 +
1.859 +void TInteger::CreateNewL(TUint aNewSize)
1.860 + {
1.861 + //should only be called on construction
1.862 + assert(!iPtr);
1.863 +
1.864 + TUint newSize = RoundupSize(aNewSize);
1.865 + SetPtr((TUint*)User::AllocL(WordsToBytes(newSize)));
1.866 + SetSize(newSize);
1.867 + SetHeapBased();
1.868 + }
1.869 +
1.870 +void TInteger::CleanNewL(TUint aNewSize)
1.871 + {
1.872 + CreateNewL(aNewSize);
1.873 + Mem::FillZ(Ptr(), WordsToBytes(Size())); //clear integer storage
1.874 + }
1.875 +
1.876 +void TInteger::CleanGrowL(TUint aNewSize)
1.877 + {
1.878 + assert(IsHeapBased());
1.879 + TUint newSize = RoundupSize(aNewSize);
1.880 + TUint oldSize = Size();
1.881 + if(newSize > oldSize)
1.882 + {
1.883 + TUint* oldPtr = Ptr();
1.884 + //1) allocate new memory and set ptr and size
1.885 + SetPtr((TUint*)User::AllocL(WordsToBytes(newSize)));
1.886 + SetSize(newSize);
1.887 + //2) copy old mem to new mem
1.888 + Mem::Copy(Ptr(), oldPtr, WordsToBytes(oldSize));
1.889 + //3) zero all old memory
1.890 + Mem::FillZ(oldPtr, WordsToBytes(oldSize));
1.891 + //4) give back old memory
1.892 + User::Free(oldPtr);
1.893 + //5) zero new memory from end of copy to end of growth
1.894 + Mem::FillZ(Ptr() + oldSize, WordsToBytes(newSize-oldSize));
1.895 + }
1.896 + }
1.897 +
1.898 +void TInteger::CleanResizeL(TUint aNewSize)
1.899 + {
1.900 + assert(IsHeapBased());
1.901 + TUint newSize = RoundupSize(aNewSize);
1.902 + TUint oldSize = Size();
1.903 + if(newSize > oldSize)
1.904 + {
1.905 + CleanGrowL(aNewSize);
1.906 + }
1.907 + else if(newSize < oldSize)
1.908 + {
1.909 + TUint* oldPtr = Ptr();
1.910 + //1) zero memory above newsize
1.911 + Mem::FillZ(oldPtr+WordsToBytes(aNewSize),WordsToBytes(oldSize-newSize));
1.912 + //2) ReAlloc cell. Since our newsize is less than oldsize, it is
1.913 + //guarenteed not to move. Thus this is just freeing part of our old
1.914 + //cell to the heap for other uses.
1.915 + SetPtr((TUint*)User::ReAllocL(Ptr(), WordsToBytes(newSize)));
1.916 + SetSize(newSize);
1.917 + }
1.918 + }
1.919 +
1.920 +EXPORT_C TInteger::TInteger() : iSize(0), iPtr(0)
1.921 + {
1.922 + }
1.923 +
1.924 +void TInteger::Construct(const TDesC8& aValue)
1.925 + {
1.926 + assert(Size() >= BytesToWords(aValue.Size()));
1.927 + if(aValue.Size() > 0)
1.928 + {
1.929 + //People write numbers with the most significant digits first (big
1.930 + //endian) but we store our numbers in little endian. Hence we need to
1.931 + //reverse the string by bytes.
1.932 +
1.933 + TUint bytes = aValue.Size();
1.934 + TUint8* i = (TUint8*)Ptr();
1.935 + TUint8* j = (TUint8*)aValue.Ptr() + bytes;
1.936 +
1.937 + //Swap the endianess of the number itself
1.938 + // (msb) 01 02 03 04 05 06 (lsb) becomes ->
1.939 + // (lsb) 06 05 04 03 02 01 (msb)
1.940 + while( j != (TUint8*)aValue.Ptr() )
1.941 + {
1.942 + *i++ = *--j;
1.943 + }
1.944 + Mem::FillZ((TUint8*)Ptr() + bytes, WordsToBytes(Size()) - bytes);
1.945 + }
1.946 + else
1.947 + {
1.948 + //if size is zero, we zero the whole register
1.949 + Mem::FillZ((TUint8*)Ptr(), WordsToBytes(Size()));
1.950 + }
1.951 + SetSign(EPositive);
1.952 + }
1.953 +
1.954 +void TInteger::Construct(const TInteger& aInteger)
1.955 + {
1.956 + assert(Size() >= aInteger.Size());
1.957 + CopyWords(Ptr(), aInteger.Ptr(), aInteger.Size());
1.958 + if(Size() > aInteger.Size())
1.959 + {
1.960 + Mem::FillZ(Ptr()+aInteger.Size(), WordsToBytes(Size()-aInteger.Size()));
1.961 + }
1.962 + SetSign(aInteger.Sign());
1.963 + }
1.964 +
1.965 +void TInteger::Construct(TInt aInteger)
1.966 + {
1.967 + Construct((TUint)aInteger);
1.968 + if(aInteger < 0)
1.969 + {
1.970 + SetSign(ENegative);
1.971 + Ptr()[0] = -aInteger;
1.972 + }
1.973 + }
1.974 +
1.975 +void TInteger::Construct(TUint aInteger)
1.976 + {
1.977 + assert(Size() >= 2);
1.978 + SetSign(EPositive);
1.979 + Ptr()[0] = aInteger;
1.980 + Mem::FillZ(Ptr()+1, WordsToBytes(Size()-1));
1.981 + }
1.982 +
1.983 +void TInteger::ConstructStack(TUint aWords, TUint aInteger)
1.984 + {
1.985 + SetPtr((TUint*)(this)+2);
1.986 + //SetStackBased(); //Not strictly needed as stackbased is a 0 at bit 1
1.987 + SetSize(aWords);
1.988 + assert(Size() >= 2);
1.989 + Ptr()[0] = aInteger;
1.990 + Mem::FillZ(&(Ptr()[1]), WordsToBytes(Size()-1));
1.991 + }
1.992 +
1.993 +void TInteger::ConstructStack(TUint aWords, const TInteger& aInteger)
1.994 + {
1.995 + SetPtr((TUint*)(this)+2);
1.996 + //SetStackBased(); //Not strictly needed as stackbased is a 0 at bit 1
1.997 + SetSize(aWords);
1.998 + assert( Size() >= RoundupSize(aInteger.WordCount()) );
1.999 + CopyWords(Ptr(), aInteger.Ptr(), aInteger.Size());
1.1000 + Mem::FillZ(Ptr()+aInteger.Size(), WordsToBytes(Size()-aInteger.Size()));
1.1001 + }
1.1002 +
1.1003 +// Methods are excluded from coverage due to the problem with BullsEye on ONB.
1.1004 +// Manually verified that these methods are functionally covered.
1.1005 +#ifdef _BullseyeCoverage
1.1006 +#pragma suppress_warnings on
1.1007 +#pragma BullseyeCoverage off
1.1008 +#pragma suppress_warnings off
1.1009 +#endif
1.1010 +
1.1011 +EXPORT_C TInteger& TInteger::operator/=(TInt aOperand)
1.1012 + {
1.1013 + TStackInteger64 operand(aOperand);
1.1014 + *this /= operand;
1.1015 + return *this;
1.1016 + }
1.1017 +
1.1018 +EXPORT_C TInteger& TInteger::operator%=(TInt aOperand)
1.1019 + {
1.1020 + TStackInteger64 operand(aOperand);
1.1021 + assert(operand.NotNegative());
1.1022 + *this %= operand;
1.1023 + return *this;
1.1024 + }
1.1025 +
1.1026 +EXPORT_C TInt TInteger::ConvertToLongL(void) const
1.1027 + {
1.1028 + if(!IsConvertableToLong())
1.1029 + {
1.1030 + User::Leave(KErrTotalLossOfPrecision);
1.1031 + }
1.1032 + return ConvertToLong();
1.1033 + }
1.1034 +
1.1035 +TInt TInteger::ConvertToLong(void) const
1.1036 + {
1.1037 + TUint value = ConvertToUnsignedLong();
1.1038 + return Sign() == EPositive ? value : -(static_cast<TInt>(value));
1.1039 + }
1.1040 +
1.1041 +TBool TInteger::IsConvertableToLong(void) const
1.1042 + {
1.1043 + if(WordCount() > 1)
1.1044 + {
1.1045 + return EFalse;
1.1046 + }
1.1047 + TUint value = (Ptr())[0];
1.1048 + if(Sign() == EPositive)
1.1049 + {
1.1050 + return static_cast<TInt>(value) >= 0;
1.1051 + }
1.1052 + else
1.1053 + {
1.1054 + return -(static_cast<TInt>(value)) < 0;
1.1055 + }
1.1056 + }
1.1057 +
1.1058 +EXPORT_C RInteger TInteger::SquaredL() const
1.1059 + {
1.1060 + //PositiveMultiplyL optimises for the squaring case already
1.1061 + //Any number squared is positive, no need for negative handling in TimesL
1.1062 + return PositiveMultiplyL(*this, *this);
1.1063 + }
1.1064 +
1.1065 +EXPORT_C RInteger TInteger::DividedByL(TUint aOperand) const
1.1066 + {
1.1067 + TUint remainder;
1.1068 + RInteger quotient;
1.1069 + DivideL(remainder, quotient, *this, aOperand);
1.1070 + return quotient;
1.1071 + }
1.1072 +
1.1073 +EXPORT_C RInteger TInteger::ExponentiateL(const TInteger& aExponent) const
1.1074 + {
1.1075 + //See HAC 14.85
1.1076 +
1.1077 + // 1.1 Precomputation
1.1078 + // g1 <- g
1.1079 + // g2 <- g^2
1.1080 + RInteger g2 = SquaredL();
1.1081 + CleanupStack::PushL(g2);
1.1082 + RInteger g1 = RInteger::NewL(*this);
1.1083 + CleanupStack::PushL(g1);
1.1084 + TWindowSlider slider(aExponent);
1.1085 +
1.1086 + // 1.2
1.1087 + // For i from 1 to (2^(k-1) -1) do g2i+1 <- g2i-1 * g2
1.1088 + TUint count = (1 << (slider.WindowSize()-1)) - 1; //2^(k-1) -1
1.1089 + RRArray<RInteger> powerArray(count+1); //+1 because we append g1
1.1090 + powerArray.AppendL(g1);
1.1091 + CleanupStack::Pop(); //g1
1.1092 + CleanupClosePushL(powerArray);
1.1093 + for(TUint k=1; k <= count; k++)
1.1094 + {
1.1095 + RInteger g2iplus1 = g2.TimesL(powerArray[k-1]);
1.1096 + powerArray.AppendL(g2iplus1);
1.1097 + }
1.1098 +
1.1099 + // 2 A <- 1, i <- t
1.1100 + RInteger A = RInteger::NewL(One());
1.1101 + CleanupStack::PushL(A);
1.1102 + TInt i = aExponent.BitCount() - 1;
1.1103 +
1.1104 + // 3 While i>=0 do:
1.1105 + while( i>=0 )
1.1106 + {
1.1107 + // 3.1 If ei == 0 then A <- A^2
1.1108 + if(!aExponent.Bit(i))
1.1109 + {
1.1110 + A *= A;
1.1111 + i--;
1.1112 + }
1.1113 + // 3.2 Find longest bitstring ei,ei-1,...,el s.t. i-l+1<=k and el==1
1.1114 + // and do:
1.1115 + // A <- (A^2^(i-l+1)) * g[the index indicated by the bitstring value]
1.1116 + else
1.1117 + {
1.1118 + slider.FindNextWindow(i);
1.1119 + assert(slider.Length() >= 1);
1.1120 + for(TUint j=0; j<slider.Length(); j++)
1.1121 + {
1.1122 + A *= A;
1.1123 + }
1.1124 + A *= powerArray[slider.Value()>>1];
1.1125 + i -= slider.Length();
1.1126 + }
1.1127 + }
1.1128 + CleanupStack::Pop(&A);
1.1129 + CleanupStack::PopAndDestroy(2, &g2); //powerArray, g2
1.1130 + return A;
1.1131 + }
1.1132 +
1.1133 +void TInteger::DivideL(TUint& aRemainder, RInteger& aQuotient,
1.1134 + const TInteger& aDividend, TUint aDivisor) const
1.1135 + {
1.1136 + if(!aDivisor)
1.1137 + {
1.1138 + User::Leave(KErrDivideByZero);
1.1139 + }
1.1140 +
1.1141 + TUint i = aDividend.WordCount();
1.1142 + aQuotient.CleanNewL(RoundupSize(i));
1.1143 + PositiveDivide(aRemainder, aQuotient, aDividend, aDivisor);
1.1144 +
1.1145 + if(aDividend.NotNegative())
1.1146 + {
1.1147 + aQuotient.SetSign(TInteger::EPositive);
1.1148 + }
1.1149 + else
1.1150 + {
1.1151 + aQuotient.SetSign(TInteger::ENegative);
1.1152 + if(aRemainder)
1.1153 + {
1.1154 + --aQuotient;
1.1155 + aRemainder = aDivisor = aRemainder;
1.1156 + }
1.1157 + }
1.1158 + }
1.1159 +
1.1160 +void TInteger::PositiveDivide(TUint& aRemainder, TInteger& aQuotient,
1.1161 + const TInteger& aDividend, TUint aDivisor) const
1.1162 + {
1.1163 + assert(aDivisor);
1.1164 +
1.1165 + TUint i = aDividend.WordCount();
1.1166 + assert(aQuotient.Size() >= RoundupSize(i));
1.1167 + assert(aQuotient.Sign() == TInteger::EPositive);
1.1168 + aRemainder = 0;
1.1169 + while(i--)
1.1170 + {
1.1171 + aQuotient.Ptr()[i] =
1.1172 + TUint(MAKE_DWORD(aDividend.Ptr()[i], aRemainder) / aDivisor);
1.1173 + aRemainder =
1.1174 + TUint(MAKE_DWORD(aDividend.Ptr()[i], aRemainder) % aDivisor);
1.1175 + }
1.1176 + }