sl@0: /*
sl@0: * Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: * All rights reserved.
sl@0: * This component and the accompanying materials are made available
sl@0: * under the terms of the License "Eclipse Public License v1.0"
sl@0: * which accompanies this distribution, and is available
sl@0: * at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: *
sl@0: * Initial Contributors:
sl@0: * Nokia Corporation - initial contribution.
sl@0: *
sl@0: * Contributors:
sl@0: *
sl@0: * Description: 
sl@0: *
sl@0: */
sl@0: 
sl@0: 
sl@0: #include <bigint.h>
sl@0: #include <euserext.h>
sl@0: #include "algorithms.h"
sl@0: #include "words.h"
sl@0: #include "windowslider.h"
sl@0: #include "mont.h"
sl@0: 
sl@0: EXPORT_C CMontgomeryStructure* CMontgomeryStructure::NewLC(
sl@0: 	const TInteger& aModulus)
sl@0: 	{
sl@0: 	CMontgomeryStructure* self = new(ELeave) CMontgomeryStructure;
sl@0: 	CleanupStack::PushL(self);
sl@0: 	self->ConstructL(aModulus);
sl@0: 	return self;
sl@0: 	}
sl@0: 
sl@0: CMontgomeryStructure::~CMontgomeryStructure()
sl@0: 	{
sl@0: 	iModulus.Close();
sl@0: 	iModulusInv.Close();
sl@0: 	iWorkspace.Close();
sl@0: 	iResult.Close();
sl@0: 	}
sl@0: 
sl@0: void CMontgomeryStructure::ConstructL(const TInteger& aModulus)
sl@0: 	{
sl@0: 	User::LeaveIfError(aModulus.IsOdd() ? KErrNone : KErrArgument);
sl@0: 	
sl@0: 	iModulusInv = RInteger::NewEmptyL(aModulus.Size());
sl@0: 	iWorkspace = RInteger::NewEmptyL(5*aModulus.Size());
sl@0: 	iModulus = RInteger::NewL(aModulus);
sl@0: 	iResult = RInteger::NewEmptyL(aModulus.Size());
sl@0: 	RecursiveInverseModPower2(iModulusInv.Ptr(), iWorkspace.Ptr(), 
sl@0: 		iModulus.Ptr(), iModulus.Size());
sl@0: 	}
sl@0: 
sl@0: CMontgomeryStructure::CMontgomeryStructure()
sl@0: 	{
sl@0: 	}
sl@0: 
sl@0: TInteger& CMontgomeryStructure::ConvertInL(TInteger& aInteger) const
sl@0: 	{
sl@0: 	aInteger <<= WordsToBits(iModulus.Size());
sl@0: 	aInteger %= iModulus;
sl@0: 	return aInteger;
sl@0: 	}
sl@0: 
sl@0: TInteger& CMontgomeryStructure::ConvertOutL(TInteger& aInteger) const
sl@0: 	{
sl@0: 	TUint* const T = iWorkspace.Ptr();
sl@0: 	TUint* const R = aInteger.Ptr();
sl@0: 	const TUint N = iModulus.Size();
sl@0: 	User::LeaveIfError((aInteger.Size() <= N) ? KErrNone : KErrArgument);
sl@0: 
sl@0: 	CopyWords(T, aInteger.Ptr(), aInteger.Size());
sl@0: 	SetWords(T + aInteger.Size(), 0, 2*N - aInteger.Size());
sl@0: 	MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);
sl@0: 	return aInteger;
sl@0: 	}
sl@0: 
sl@0: void CMontgomeryStructure::DoMultiplyL(TInteger& aResult, const TInteger& aA,
sl@0: 	const TInteger& aB) const
sl@0: 	{
sl@0: 	User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument);
sl@0: 					   
sl@0: 	TUint* const T = iWorkspace.Ptr();
sl@0: 	TUint* const R = aResult.Ptr();
sl@0: 	const TUint N = iModulus.Size();
sl@0: 	const TUint* const aReg = aA.Ptr();
sl@0: 	const TUint* const bReg = aB.Ptr();
sl@0: 	const TUint aSize = aA.Size();
sl@0: 	const TUint bSize = aB.Size();
sl@0: 	User::LeaveIfError((aSize <= N && bSize <= N) ? KErrNone : KErrArgument);
sl@0: 
sl@0: 	AsymmetricMultiply(T, T+2*N, aReg, aSize, bReg, bSize);
sl@0: 	SetWords(T+aSize+bSize, 0, 2*N - aSize - bSize);
sl@0: 	MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);
sl@0: 	}
sl@0: 
sl@0: const TInteger& CMontgomeryStructure::SquareL(const TInteger& aA) const
sl@0: 	{
sl@0: 	RInteger a = RInteger::NewL(aA);
sl@0: 	CleanupStack::PushL(a);
sl@0: 	DoSquareL(iResult, ConvertInL(a));
sl@0: 	ConvertOutL(iResult);
sl@0: 	CleanupStack::PopAndDestroy(&a);
sl@0: 	return iResult;
sl@0: 	}
sl@0: 
sl@0: void CMontgomeryStructure::DoSquareL(TInteger& aResult, const TInteger& aA) const
sl@0: 	{
sl@0: 	User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument);
sl@0: 	TUint* const T = iWorkspace.Ptr();
sl@0: 	TUint* const R = aResult.Ptr();
sl@0: 	const TUint N = iModulus.Size();
sl@0: 	const TUint* const aReg = aA.Ptr();
sl@0: 	const TUint aSize = aA.Size();
sl@0: 
sl@0: 	User::LeaveIfError((aSize <= N) ? KErrNone : KErrArgument);
sl@0: 
sl@0: 	RecursiveSquare(T, T+2*N, aReg, aSize);
sl@0: 	SetWords(T+2*aSize, 0, 2*N-2*aSize);
sl@0: 	MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);
sl@0: 	}
sl@0: 
sl@0: EXPORT_C const TInteger& CMontgomeryStructure::ExponentiateL(
sl@0: 	const TInteger& aBase, const TInteger& aExponent) const
sl@0: 	{
sl@0: 	//See HAC 14.85
sl@0: 	if ((iResult.Size() != iModulus.Size()) ||
sl@0: 		(aBase >= iModulus) ||
sl@0: 		(!aBase.IsPositive()) ||
sl@0: 		(!aExponent.IsPositive()))
sl@0: 		{
sl@0: 		User::Leave(KErrArgument);
sl@0: 		}
sl@0: 
sl@0: 	// 1.1 Precomputation
sl@0: 	// g1 <- g
sl@0: 	// g2 <- g^2
sl@0: 	RInteger g2 = RInteger::NewL(aBase);
sl@0: 	CleanupStack::PushL(g2);
sl@0: 	ConvertInL(g2);
sl@0: 	//ConvertInL can shrink g2, because we call DoSquare on g2, g2 must be the same size as the modulus
sl@0: 	g2.CleanGrowL(iModulus.Size());
sl@0: 	RInteger g1 = RInteger::NewL(g2);
sl@0: 	CleanupStack::PushL(g1);
sl@0: 	DoSquareL(g2, g2);
sl@0: 
sl@0: 	TWindowSlider slider(aExponent);
sl@0: 
sl@0: 	// 1.2 
sl@0: 	// For i from 1 to (2^(k-1) -1) do g2i+1 <- g2i-1 * g2
sl@0: 	TUint count = (1 << (slider.WindowSize()-1)) - 1; //2^(k-1) -1
sl@0: 	RRArray<RInteger> powerArray(count+1); //+1 because we append g1
sl@0: 	User::LeaveIfError(powerArray.Append(g1));
sl@0: 	CleanupStack::Pop(&g1); 
sl@0: 	CleanupClosePushL(powerArray);
sl@0: 	for(TUint k=1; k <= count; k++)
sl@0: 		{
sl@0: 		RInteger gi = RInteger::NewEmptyL(iModulus.Size());
sl@0: 		DoMultiplyL(gi, g2, powerArray[k-1]);
sl@0: 		User::LeaveIfError(powerArray.Append(gi));
sl@0: 		}
sl@0: 	
sl@0: 	// 2 A <- 1, i <- t
sl@0: 	RInteger temp = RInteger::NewL(TInteger::One());
sl@0: 	CleanupStack::PushL(temp);
sl@0: 	ConvertInL(temp);
sl@0: 
sl@0: 	RInteger& A = iResult;
sl@0: 	//Set A to one converted in for this modulus without changing the memory size of A (iResult)
sl@0: 	A.CopyL(temp, EFalse); 
sl@0: 	CleanupStack::PopAndDestroy(&temp);
sl@0: 
sl@0: 	TInt i = aExponent.BitCount() - 1;
sl@0: 
sl@0: 	// 3 While i>=0 do:
sl@0: 	while( i>=0 )
sl@0: 		{
sl@0: 		// 3.1 If ei == 0 then A <- A^2
sl@0: 		if(!aExponent.Bit(i))
sl@0: 			{
sl@0: 			DoSquareL(A, A);
sl@0: 			i--;
sl@0: 			}
sl@0: 		// 3.2 Find longest bitstring ei,ei-1,...,el s.t. i-l+1<=k and el==1
sl@0: 		// and do:
sl@0: 		// A <- (A^2^(i-l+1)) * g[the index indicated by the bitstring value]
sl@0: 		else
sl@0: 			{
sl@0: 			slider.FindNextWindow(i);
sl@0: 			assert(slider.Length() >= 1);
sl@0: 			for(TUint j=0; j<slider.Length(); j++)
sl@0: 				{
sl@0: 				DoSquareL(A, A);
sl@0: 				}
sl@0: 			DoMultiplyL(A, A, powerArray[slider.Value()>>1]);
sl@0: 			i -= slider.Length();
sl@0: 			}
sl@0: 		}
sl@0: 	CleanupStack::PopAndDestroy(2, &g2); //powerArray, g2
sl@0: 	return ConvertOutL(A); // A == iResult
sl@0: 	}
sl@0: 
sl@0: // Methods are excluded from coverage due to the problem with BullsEye on ONB.
sl@0: // Manually verified that these methods are functionally covered.
sl@0: #ifdef _BullseyeCoverage
sl@0: #pragma suppress_warnings on
sl@0: #pragma BullseyeCoverage off
sl@0: #pragma suppress_warnings off
sl@0: #endif
sl@0: 
sl@0: const TInteger& CMontgomeryStructure::ReduceL(
sl@0: 	const TInteger& aInteger) const
sl@0: 	{
sl@0: 	RInteger temp = RInteger::NewL(aInteger);
sl@0: 	CleanupStack::PushL(temp);
sl@0: 	ConvertInL(temp);
sl@0: 	iResult.CopyL(ConvertOutL(temp), EFalse);
sl@0: 	CleanupStack::PopAndDestroy(&temp);
sl@0: 	return iResult;
sl@0: 	}
sl@0: 
sl@0: CMontgomeryStructure* CMontgomeryStructure::NewL(
sl@0: 	const TInteger& aModulus)
sl@0: 	{
sl@0: 	CMontgomeryStructure* self = CMontgomeryStructure::NewLC(aModulus);
sl@0: 	CleanupStack::Pop(self);
sl@0: 	return self;
sl@0: 	}
sl@0: 
sl@0: const TInteger& CMontgomeryStructure::MultiplyL(const TInteger& aA, 
sl@0: 	const TInteger& aB) const
sl@0: 	{
sl@0: 	RInteger a = RInteger::NewL(aA);
sl@0: 	CleanupStack::PushL(a);
sl@0: 	RInteger b = RInteger::NewL(aB);
sl@0: 	CleanupStack::PushL(b);
sl@0: 	DoMultiplyL(iResult, ConvertInL(a), ConvertInL(b));
sl@0: 	ConvertOutL(iResult);
sl@0: 	CleanupStack::PopAndDestroy(&b); 
sl@0: 	CleanupStack::PopAndDestroy(&a); 
sl@0: 	return iResult;
sl@0: 	}