1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/security/crypto/weakcryptospi/source/bigint/mont.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,243 @@
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 <euserext.h>
1.24 +#include "algorithms.h"
1.25 +#include "words.h"
1.26 +#include "windowslider.h"
1.27 +#include "mont.h"
1.28 +
1.29 +EXPORT_C CMontgomeryStructure* CMontgomeryStructure::NewLC(
1.30 + const TInteger& aModulus)
1.31 + {
1.32 + CMontgomeryStructure* self = new(ELeave) CMontgomeryStructure;
1.33 + CleanupStack::PushL(self);
1.34 + self->ConstructL(aModulus);
1.35 + return self;
1.36 + }
1.37 +
1.38 +CMontgomeryStructure::~CMontgomeryStructure()
1.39 + {
1.40 + iModulus.Close();
1.41 + iModulusInv.Close();
1.42 + iWorkspace.Close();
1.43 + iResult.Close();
1.44 + }
1.45 +
1.46 +void CMontgomeryStructure::ConstructL(const TInteger& aModulus)
1.47 + {
1.48 + User::LeaveIfError(aModulus.IsOdd() ? KErrNone : KErrArgument);
1.49 +
1.50 + iModulusInv = RInteger::NewEmptyL(aModulus.Size());
1.51 + iWorkspace = RInteger::NewEmptyL(5*aModulus.Size());
1.52 + iModulus = RInteger::NewL(aModulus);
1.53 + iResult = RInteger::NewEmptyL(aModulus.Size());
1.54 + RecursiveInverseModPower2(iModulusInv.Ptr(), iWorkspace.Ptr(),
1.55 + iModulus.Ptr(), iModulus.Size());
1.56 + }
1.57 +
1.58 +CMontgomeryStructure::CMontgomeryStructure()
1.59 + {
1.60 + }
1.61 +
1.62 +TInteger& CMontgomeryStructure::ConvertInL(TInteger& aInteger) const
1.63 + {
1.64 + aInteger <<= WordsToBits(iModulus.Size());
1.65 + aInteger %= iModulus;
1.66 + return aInteger;
1.67 + }
1.68 +
1.69 +TInteger& CMontgomeryStructure::ConvertOutL(TInteger& aInteger) const
1.70 + {
1.71 + TUint* const T = iWorkspace.Ptr();
1.72 + TUint* const R = aInteger.Ptr();
1.73 + const TUint N = iModulus.Size();
1.74 + User::LeaveIfError((aInteger.Size() <= N) ? KErrNone : KErrArgument);
1.75 +
1.76 + CopyWords(T, aInteger.Ptr(), aInteger.Size());
1.77 + SetWords(T + aInteger.Size(), 0, 2*N - aInteger.Size());
1.78 + MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);
1.79 + return aInteger;
1.80 + }
1.81 +
1.82 +void CMontgomeryStructure::DoMultiplyL(TInteger& aResult, const TInteger& aA,
1.83 + const TInteger& aB) const
1.84 + {
1.85 + User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument);
1.86 +
1.87 + TUint* const T = iWorkspace.Ptr();
1.88 + TUint* const R = aResult.Ptr();
1.89 + const TUint N = iModulus.Size();
1.90 + const TUint* const aReg = aA.Ptr();
1.91 + const TUint* const bReg = aB.Ptr();
1.92 + const TUint aSize = aA.Size();
1.93 + const TUint bSize = aB.Size();
1.94 + User::LeaveIfError((aSize <= N && bSize <= N) ? KErrNone : KErrArgument);
1.95 +
1.96 + AsymmetricMultiply(T, T+2*N, aReg, aSize, bReg, bSize);
1.97 + SetWords(T+aSize+bSize, 0, 2*N - aSize - bSize);
1.98 + MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);
1.99 + }
1.100 +
1.101 +const TInteger& CMontgomeryStructure::SquareL(const TInteger& aA) const
1.102 + {
1.103 + RInteger a = RInteger::NewL(aA);
1.104 + CleanupStack::PushL(a);
1.105 + DoSquareL(iResult, ConvertInL(a));
1.106 + ConvertOutL(iResult);
1.107 + CleanupStack::PopAndDestroy(&a);
1.108 + return iResult;
1.109 + }
1.110 +
1.111 +void CMontgomeryStructure::DoSquareL(TInteger& aResult, const TInteger& aA) const
1.112 + {
1.113 + User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument);
1.114 + TUint* const T = iWorkspace.Ptr();
1.115 + TUint* const R = aResult.Ptr();
1.116 + const TUint N = iModulus.Size();
1.117 + const TUint* const aReg = aA.Ptr();
1.118 + const TUint aSize = aA.Size();
1.119 +
1.120 + User::LeaveIfError((aSize <= N) ? KErrNone : KErrArgument);
1.121 +
1.122 + RecursiveSquare(T, T+2*N, aReg, aSize);
1.123 + SetWords(T+2*aSize, 0, 2*N-2*aSize);
1.124 + MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);
1.125 + }
1.126 +
1.127 +EXPORT_C const TInteger& CMontgomeryStructure::ExponentiateL(
1.128 + const TInteger& aBase, const TInteger& aExponent) const
1.129 + {
1.130 + //See HAC 14.85
1.131 + if ((iResult.Size() != iModulus.Size()) ||
1.132 + (aBase >= iModulus) ||
1.133 + (!aBase.IsPositive()) ||
1.134 + (!aExponent.IsPositive()))
1.135 + {
1.136 + User::Leave(KErrArgument);
1.137 + }
1.138 +
1.139 + // 1.1 Precomputation
1.140 + // g1 <- g
1.141 + // g2 <- g^2
1.142 + RInteger g2 = RInteger::NewL(aBase);
1.143 + CleanupStack::PushL(g2);
1.144 + ConvertInL(g2);
1.145 + //ConvertInL can shrink g2, because we call DoSquare on g2, g2 must be the same size as the modulus
1.146 + g2.CleanGrowL(iModulus.Size());
1.147 + RInteger g1 = RInteger::NewL(g2);
1.148 + CleanupStack::PushL(g1);
1.149 + DoSquareL(g2, g2);
1.150 +
1.151 + TWindowSlider slider(aExponent);
1.152 +
1.153 + // 1.2
1.154 + // For i from 1 to (2^(k-1) -1) do g2i+1 <- g2i-1 * g2
1.155 + TUint count = (1 << (slider.WindowSize()-1)) - 1; //2^(k-1) -1
1.156 + RRArray<RInteger> powerArray(count+1); //+1 because we append g1
1.157 + User::LeaveIfError(powerArray.Append(g1));
1.158 + CleanupStack::Pop(&g1);
1.159 + CleanupClosePushL(powerArray);
1.160 + for(TUint k=1; k <= count; k++)
1.161 + {
1.162 + RInteger gi = RInteger::NewEmptyL(iModulus.Size());
1.163 + DoMultiplyL(gi, g2, powerArray[k-1]);
1.164 + User::LeaveIfError(powerArray.Append(gi));
1.165 + }
1.166 +
1.167 + // 2 A <- 1, i <- t
1.168 + RInteger temp = RInteger::NewL(TInteger::One());
1.169 + CleanupStack::PushL(temp);
1.170 + ConvertInL(temp);
1.171 +
1.172 + RInteger& A = iResult;
1.173 + //Set A to one converted in for this modulus without changing the memory size of A (iResult)
1.174 + A.CopyL(temp, EFalse);
1.175 + CleanupStack::PopAndDestroy(&temp);
1.176 +
1.177 + TInt i = aExponent.BitCount() - 1;
1.178 +
1.179 + // 3 While i>=0 do:
1.180 + while( i>=0 )
1.181 + {
1.182 + // 3.1 If ei == 0 then A <- A^2
1.183 + if(!aExponent.Bit(i))
1.184 + {
1.185 + DoSquareL(A, A);
1.186 + i--;
1.187 + }
1.188 + // 3.2 Find longest bitstring ei,ei-1,...,el s.t. i-l+1<=k and el==1
1.189 + // and do:
1.190 + // A <- (A^2^(i-l+1)) * g[the index indicated by the bitstring value]
1.191 + else
1.192 + {
1.193 + slider.FindNextWindow(i);
1.194 + assert(slider.Length() >= 1);
1.195 + for(TUint j=0; j<slider.Length(); j++)
1.196 + {
1.197 + DoSquareL(A, A);
1.198 + }
1.199 + DoMultiplyL(A, A, powerArray[slider.Value()>>1]);
1.200 + i -= slider.Length();
1.201 + }
1.202 + }
1.203 + CleanupStack::PopAndDestroy(2, &g2); //powerArray, g2
1.204 + return ConvertOutL(A); // A == iResult
1.205 + }
1.206 +
1.207 +// Methods are excluded from coverage due to the problem with BullsEye on ONB.
1.208 +// Manually verified that these methods are functionally covered.
1.209 +#ifdef _BullseyeCoverage
1.210 +#pragma suppress_warnings on
1.211 +#pragma BullseyeCoverage off
1.212 +#pragma suppress_warnings off
1.213 +#endif
1.214 +
1.215 +const TInteger& CMontgomeryStructure::ReduceL(
1.216 + const TInteger& aInteger) const
1.217 + {
1.218 + RInteger temp = RInteger::NewL(aInteger);
1.219 + CleanupStack::PushL(temp);
1.220 + ConvertInL(temp);
1.221 + iResult.CopyL(ConvertOutL(temp), EFalse);
1.222 + CleanupStack::PopAndDestroy(&temp);
1.223 + return iResult;
1.224 + }
1.225 +
1.226 +CMontgomeryStructure* CMontgomeryStructure::NewL(
1.227 + const TInteger& aModulus)
1.228 + {
1.229 + CMontgomeryStructure* self = CMontgomeryStructure::NewLC(aModulus);
1.230 + CleanupStack::Pop(self);
1.231 + return self;
1.232 + }
1.233 +
1.234 +const TInteger& CMontgomeryStructure::MultiplyL(const TInteger& aA,
1.235 + const TInteger& aB) const
1.236 + {
1.237 + RInteger a = RInteger::NewL(aA);
1.238 + CleanupStack::PushL(a);
1.239 + RInteger b = RInteger::NewL(aB);
1.240 + CleanupStack::PushL(b);
1.241 + DoMultiplyL(iResult, ConvertInL(a), ConvertInL(b));
1.242 + ConvertOutL(iResult);
1.243 + CleanupStack::PopAndDestroy(&b);
1.244 + CleanupStack::PopAndDestroy(&a);
1.245 + return iResult;
1.246 + }