|
1 /* |
|
2 * Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of the License "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * |
|
16 */ |
|
17 |
|
18 |
|
19 #include <bigint.h> |
|
20 #include <euserext.h> |
|
21 #include "algorithms.h" |
|
22 #include "words.h" |
|
23 #include "windowslider.h" |
|
24 #include "mont.h" |
|
25 |
|
26 EXPORT_C CMontgomeryStructure* CMontgomeryStructure::NewLC( |
|
27 const TInteger& aModulus) |
|
28 { |
|
29 CMontgomeryStructure* self = new(ELeave) CMontgomeryStructure; |
|
30 CleanupStack::PushL(self); |
|
31 self->ConstructL(aModulus); |
|
32 return self; |
|
33 } |
|
34 |
|
35 CMontgomeryStructure::~CMontgomeryStructure() |
|
36 { |
|
37 iModulus.Close(); |
|
38 iModulusInv.Close(); |
|
39 iWorkspace.Close(); |
|
40 iResult.Close(); |
|
41 } |
|
42 |
|
43 void CMontgomeryStructure::ConstructL(const TInteger& aModulus) |
|
44 { |
|
45 User::LeaveIfError(aModulus.IsOdd() ? KErrNone : KErrArgument); |
|
46 |
|
47 iModulusInv = RInteger::NewEmptyL(aModulus.Size()); |
|
48 iWorkspace = RInteger::NewEmptyL(5*aModulus.Size()); |
|
49 iModulus = RInteger::NewL(aModulus); |
|
50 iResult = RInteger::NewEmptyL(aModulus.Size()); |
|
51 RecursiveInverseModPower2(iModulusInv.Ptr(), iWorkspace.Ptr(), |
|
52 iModulus.Ptr(), iModulus.Size()); |
|
53 } |
|
54 |
|
55 CMontgomeryStructure::CMontgomeryStructure() |
|
56 { |
|
57 } |
|
58 |
|
59 TInteger& CMontgomeryStructure::ConvertIn(TInteger& aInteger) const |
|
60 { |
|
61 aInteger <<= WordsToBits(iModulus.Size()); |
|
62 aInteger %= iModulus; |
|
63 return aInteger; |
|
64 } |
|
65 |
|
66 TInteger& CMontgomeryStructure::ConvertOutL(TInteger& aInteger) const |
|
67 { |
|
68 TUint* const T = iWorkspace.Ptr(); |
|
69 TUint* const R = aInteger.Ptr(); |
|
70 const TUint N = iModulus.Size(); |
|
71 User::LeaveIfError((aInteger.Size() <= N) ? KErrNone : KErrArgument); |
|
72 |
|
73 CopyWords(T, aInteger.Ptr(), aInteger.Size()); |
|
74 SetWords(T + aInteger.Size(), 0, 2*N - aInteger.Size()); |
|
75 MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N); |
|
76 return aInteger; |
|
77 } |
|
78 |
|
79 void CMontgomeryStructure::DoMultiplyL(TInteger& aResult, const TInteger& aA, |
|
80 const TInteger& aB) const |
|
81 { |
|
82 User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument); |
|
83 |
|
84 TUint* const T = iWorkspace.Ptr(); |
|
85 TUint* const R = aResult.Ptr(); |
|
86 const TUint N = iModulus.Size(); |
|
87 const TUint* const aReg = aA.Ptr(); |
|
88 const TUint* const bReg = aB.Ptr(); |
|
89 const TUint aSize = aA.Size(); |
|
90 const TUint bSize = aB.Size(); |
|
91 User::LeaveIfError((aSize <= N && bSize <= N) ? KErrNone : KErrArgument); |
|
92 |
|
93 AsymmetricMultiply(T, T+2*N, aReg, aSize, bReg, bSize); |
|
94 SetWords(T+aSize+bSize, 0, 2*N - aSize - bSize); |
|
95 MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N); |
|
96 } |
|
97 |
|
98 const TInteger& CMontgomeryStructure::SquareL(const TInteger& aA) const |
|
99 { |
|
100 RInteger a = RInteger::NewL(aA); |
|
101 CleanupStack::PushL(a); |
|
102 DoSquareL(iResult, ConvertIn(a)); |
|
103 ConvertOutL(iResult); |
|
104 CleanupStack::PopAndDestroy(&a); |
|
105 return iResult; |
|
106 } |
|
107 |
|
108 void CMontgomeryStructure::DoSquareL(TInteger& aResult, const TInteger& aA) const |
|
109 { |
|
110 User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument); |
|
111 TUint* const T = iWorkspace.Ptr(); |
|
112 TUint* const R = aResult.Ptr(); |
|
113 const TUint N = iModulus.Size(); |
|
114 const TUint* const aReg = aA.Ptr(); |
|
115 const TUint aSize = aA.Size(); |
|
116 |
|
117 User::LeaveIfError((aSize <= N) ? KErrNone : KErrArgument); |
|
118 |
|
119 RecursiveSquare(T, T+2*N, aReg, aSize); |
|
120 SetWords(T+2*aSize, 0, 2*N-2*aSize); |
|
121 MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N); |
|
122 } |
|
123 |
|
124 EXPORT_C const TInteger& CMontgomeryStructure::ExponentiateL( |
|
125 const TInteger& aBase, const TInteger& aExponent) const |
|
126 { |
|
127 //See HAC 14.85 |
|
128 if ((iResult.Size() != iModulus.Size()) || |
|
129 (aBase >= iModulus) || |
|
130 (!aBase.IsPositive()) || |
|
131 (!aExponent.IsPositive())) |
|
132 { |
|
133 User::Leave(KErrArgument); |
|
134 } |
|
135 |
|
136 // 1.1 Precomputation |
|
137 // g1 <- g |
|
138 // g2 <- g^2 |
|
139 RInteger g2 = RInteger::NewL(aBase); |
|
140 CleanupStack::PushL(g2); |
|
141 ConvertIn(g2); |
|
142 //ConvertIn can shrink g2, because we call DoSquare on g2, g2 must be the same size as the modulus |
|
143 g2.CleanGrowL(iModulus.Size()); |
|
144 RInteger g1 = RInteger::NewL(g2); |
|
145 CleanupStack::PushL(g1); |
|
146 DoSquareL(g2, g2); |
|
147 |
|
148 TWindowSlider slider(aExponent); |
|
149 |
|
150 // 1.2 |
|
151 // For i from 1 to (2^(k-1) -1) do g2i+1 <- g2i-1 * g2 |
|
152 TUint count = (1 << (slider.WindowSize()-1)) - 1; //2^(k-1) -1 |
|
153 RRArray<RInteger> powerArray(count+1); //+1 because we append g1 |
|
154 User::LeaveIfError(powerArray.Append(g1)); |
|
155 CleanupStack::Pop(&g1); |
|
156 CleanupClosePushL(powerArray); |
|
157 for(TUint k=1; k <= count; k++) |
|
158 { |
|
159 RInteger gi = RInteger::NewEmptyL(iModulus.Size()); |
|
160 DoMultiplyL(gi, g2, powerArray[k-1]); |
|
161 User::LeaveIfError(powerArray.Append(gi)); |
|
162 } |
|
163 |
|
164 // 2 A <- 1, i <- t |
|
165 RInteger temp = RInteger::NewL(TInteger::One()); |
|
166 CleanupStack::PushL(temp); |
|
167 ConvertIn(temp); |
|
168 |
|
169 RInteger& A = iResult; |
|
170 //Set A to one converted in for this modulus without changing the memory size of A (iResult) |
|
171 A.CopyL(temp, EFalse); |
|
172 CleanupStack::PopAndDestroy(&temp); |
|
173 |
|
174 TInt i = aExponent.BitCount() - 1; |
|
175 |
|
176 // 3 While i>=0 do: |
|
177 while( i>=0 ) |
|
178 { |
|
179 // 3.1 If ei == 0 then A <- A^2 |
|
180 if(!aExponent.Bit(i)) |
|
181 { |
|
182 DoSquareL(A, A); |
|
183 i--; |
|
184 } |
|
185 // 3.2 Find longest bitstring ei,ei-1,...,el s.t. i-l+1<=k and el==1 |
|
186 // and do: |
|
187 // A <- (A^2^(i-l+1)) * g[the index indicated by the bitstring value] |
|
188 else |
|
189 { |
|
190 slider.FindNextWindow(i); |
|
191 assert(slider.Length() >= 1); |
|
192 for(TUint j=0; j<slider.Length(); j++) |
|
193 { |
|
194 DoSquareL(A, A); |
|
195 } |
|
196 DoMultiplyL(A, A, powerArray[slider.Value()>>1]); |
|
197 i -= slider.Length(); |
|
198 } |
|
199 } |
|
200 CleanupStack::PopAndDestroy(2, &g2); //powerArray, g2 |
|
201 return ConvertOutL(A); // A == iResult |
|
202 } |
|
203 |
|
204 // Methods are excluded from coverage due to the problem with BullsEye on ONB. |
|
205 // Manually verified that these methods are functionally covered. |
|
206 #ifdef _BullseyeCoverage |
|
207 #pragma suppress_warnings on |
|
208 #pragma BullseyeCoverage off |
|
209 #pragma suppress_warnings off |
|
210 #endif |
|
211 |
|
212 const TInteger& CMontgomeryStructure::ReduceL( |
|
213 const TInteger& aInteger) const |
|
214 { |
|
215 RInteger temp = RInteger::NewL(aInteger); |
|
216 CleanupStack::PushL(temp); |
|
217 ConvertIn(temp); |
|
218 iResult.CopyL(ConvertOutL(temp), EFalse); |
|
219 CleanupStack::PopAndDestroy(&temp); |
|
220 return iResult; |
|
221 } |
|
222 |
|
223 CMontgomeryStructure* CMontgomeryStructure::NewL( |
|
224 const TInteger& aModulus) |
|
225 { |
|
226 CMontgomeryStructure* self = CMontgomeryStructure::NewLC(aModulus); |
|
227 CleanupStack::Pop(self); |
|
228 return self; |
|
229 } |
|
230 |
|
231 const TInteger& CMontgomeryStructure::MultiplyL(const TInteger& aA, |
|
232 const TInteger& aB) const |
|
233 { |
|
234 RInteger a = RInteger::NewL(aA); |
|
235 CleanupStack::PushL(a); |
|
236 RInteger b = RInteger::NewL(aB); |
|
237 CleanupStack::PushL(b); |
|
238 DoMultiplyL(iResult, ConvertIn(a), ConvertIn(b)); |
|
239 ConvertOutL(iResult); |
|
240 CleanupStack::PopAndDestroy(&b); |
|
241 CleanupStack::PopAndDestroy(&a); |
|
242 return iResult; |
|
243 } |