|
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 CMontgomeryStructure* CMontgomeryStructure::NewL( |
|
27 const TInteger& aModulus) |
|
28 { |
|
29 CMontgomeryStructure* self = CMontgomeryStructure::NewLC(aModulus); |
|
30 CleanupStack::Pop(self); |
|
31 return self; |
|
32 } |
|
33 |
|
34 CMontgomeryStructure* CMontgomeryStructure::NewLC( |
|
35 const TInteger& aModulus) |
|
36 { |
|
37 CMontgomeryStructure* self = new(ELeave) CMontgomeryStructure; |
|
38 CleanupStack::PushL(self); |
|
39 self->ConstructL(aModulus); |
|
40 return self; |
|
41 } |
|
42 |
|
43 CMontgomeryStructure::~CMontgomeryStructure() |
|
44 { |
|
45 iModulus.Close(); |
|
46 iModulusInv.Close(); |
|
47 iWorkspace.Close(); |
|
48 iResult.Close(); |
|
49 } |
|
50 |
|
51 void CMontgomeryStructure::ConstructL(const TInteger& aModulus) |
|
52 { |
|
53 User::LeaveIfError(aModulus.IsOdd() ? KErrNone : KErrArgument); |
|
54 |
|
55 iModulusInv = RInteger::NewEmptyL(aModulus.Size()); |
|
56 iWorkspace = RInteger::NewEmptyL(5*aModulus.Size()); |
|
57 iModulus = RInteger::NewL(aModulus); |
|
58 iResult = RInteger::NewEmptyL(aModulus.Size()); |
|
59 RecursiveInverseModPower2(iModulusInv.Ptr(), iWorkspace.Ptr(), |
|
60 iModulus.Ptr(), iModulus.Size()); |
|
61 } |
|
62 |
|
63 CMontgomeryStructure::CMontgomeryStructure() |
|
64 { |
|
65 } |
|
66 |
|
67 TInteger& CMontgomeryStructure::ConvertInL(TInteger& aInteger) const |
|
68 { |
|
69 aInteger <<= WordsToBits(iModulus.Size()); |
|
70 aInteger %= iModulus; |
|
71 return aInteger; |
|
72 } |
|
73 |
|
74 TInteger& CMontgomeryStructure::ConvertOutL(TInteger& aInteger) const |
|
75 { |
|
76 TUint* const T = iWorkspace.Ptr(); |
|
77 TUint* const R = aInteger.Ptr(); |
|
78 const TUint N = iModulus.Size(); |
|
79 User::LeaveIfError((aInteger.Size() <= N) ? KErrNone : KErrArgument); |
|
80 |
|
81 CopyWords(T, aInteger.Ptr(), aInteger.Size()); |
|
82 SetWords(T + aInteger.Size(), 0, 2*N - aInteger.Size()); |
|
83 MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N); |
|
84 return aInteger; |
|
85 } |
|
86 |
|
87 const TInteger& CMontgomeryStructure::ReduceL( |
|
88 const TInteger& aInteger) const |
|
89 { |
|
90 RInteger temp = RInteger::NewL(aInteger); |
|
91 CleanupStack::PushL(temp); |
|
92 ConvertInL(temp); |
|
93 iResult.CopyL(ConvertOutL(temp), EFalse); |
|
94 CleanupStack::PopAndDestroy(&temp); |
|
95 return iResult; |
|
96 } |
|
97 |
|
98 const TInteger& CMontgomeryStructure::MultiplyL(const TInteger& aA, |
|
99 const TInteger& aB) const |
|
100 { |
|
101 RInteger a = RInteger::NewL(aA); |
|
102 CleanupStack::PushL(a); |
|
103 RInteger b = RInteger::NewL(aB); |
|
104 CleanupStack::PushL(b); |
|
105 DoMultiplyL(iResult, ConvertInL(a), ConvertInL(b)); |
|
106 ConvertOutL(iResult); |
|
107 CleanupStack::PopAndDestroy(&b); |
|
108 CleanupStack::PopAndDestroy(&a); |
|
109 return iResult; |
|
110 } |
|
111 |
|
112 void CMontgomeryStructure::DoMultiplyL(TInteger& aResult, const TInteger& aA, |
|
113 const TInteger& aB) const |
|
114 { |
|
115 User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument); |
|
116 |
|
117 TUint* const T = iWorkspace.Ptr(); |
|
118 TUint* const R = aResult.Ptr(); |
|
119 const TUint N = iModulus.Size(); |
|
120 const TUint* const aReg = aA.Ptr(); |
|
121 const TUint* const bReg = aB.Ptr(); |
|
122 const TUint aSize = aA.Size(); |
|
123 const TUint bSize = aB.Size(); |
|
124 User::LeaveIfError((aSize <= N && bSize <= N) ? KErrNone : KErrArgument); |
|
125 |
|
126 AsymmetricMultiply(T, T+2*N, aReg, aSize, bReg, bSize); |
|
127 SetWords(T+aSize+bSize, 0, 2*N - aSize - bSize); |
|
128 MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N); |
|
129 } |
|
130 |
|
131 const TInteger& CMontgomeryStructure::SquareL(const TInteger& aA) const |
|
132 { |
|
133 RInteger a = RInteger::NewL(aA); |
|
134 CleanupStack::PushL(a); |
|
135 DoSquareL(iResult, ConvertInL(a)); |
|
136 ConvertOutL(iResult); |
|
137 CleanupStack::PopAndDestroy(&a); |
|
138 return iResult; |
|
139 } |
|
140 |
|
141 void CMontgomeryStructure::DoSquareL(TInteger& aResult, const TInteger& aA) const |
|
142 { |
|
143 User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument); |
|
144 TUint* const T = iWorkspace.Ptr(); |
|
145 TUint* const R = aResult.Ptr(); |
|
146 const TUint N = iModulus.Size(); |
|
147 const TUint* const aReg = aA.Ptr(); |
|
148 const TUint aSize = aA.Size(); |
|
149 |
|
150 User::LeaveIfError((aSize <= N) ? KErrNone : KErrArgument); |
|
151 |
|
152 RecursiveSquare(T, T+2*N, aReg, aSize); |
|
153 SetWords(T+2*aSize, 0, 2*N-2*aSize); |
|
154 MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N); |
|
155 } |
|
156 |
|
157 const TInteger& CMontgomeryStructure::ExponentiateL( |
|
158 const TInteger& aBase, const TInteger& aExponent) const |
|
159 { |
|
160 //See HAC 14.85 |
|
161 if ((iResult.Size() != iModulus.Size()) || |
|
162 (aBase >= iModulus) || |
|
163 (!aBase.IsPositive()) || |
|
164 (!aExponent.IsPositive())) |
|
165 { |
|
166 User::Leave(KErrArgument); |
|
167 } |
|
168 |
|
169 // 1.1 Precomputation |
|
170 // g1 <- g |
|
171 // g2 <- g^2 |
|
172 RInteger g2 = RInteger::NewL(aBase); |
|
173 CleanupStack::PushL(g2); |
|
174 ConvertInL(g2); |
|
175 //ConvertIn can shrink g2, because we call DoSquare on g2, g2 must be the same size as the modulus |
|
176 g2.CleanGrowL(iModulus.Size()); |
|
177 RInteger g1 = RInteger::NewL(g2); |
|
178 CleanupStack::PushL(g1); |
|
179 DoSquareL(g2, g2); |
|
180 |
|
181 TWindowSlider slider(aExponent); |
|
182 |
|
183 // 1.2 |
|
184 // For i from 1 to (2^(k-1) -1) do g2i+1 <- g2i-1 * g2 |
|
185 TUint count = (1 << (slider.WindowSize()-1)) - 1; //2^(k-1) -1 |
|
186 RRArray<RInteger> powerArray(count+1); //+1 because we append g1 |
|
187 User::LeaveIfError(powerArray.Append(g1)); |
|
188 CleanupStack::Pop(&g1); |
|
189 CleanupClosePushL(powerArray); |
|
190 for(TUint k=1; k <= count; k++) |
|
191 { |
|
192 RInteger gi = RInteger::NewEmptyL(iModulus.Size()); |
|
193 DoMultiplyL(gi, g2, powerArray[k-1]); |
|
194 User::LeaveIfError(powerArray.Append(gi)); |
|
195 } |
|
196 |
|
197 // 2 A <- 1, i <- t |
|
198 RInteger temp = RInteger::NewL(TInteger::One()); |
|
199 CleanupStack::PushL(temp); |
|
200 ConvertInL(temp); |
|
201 |
|
202 RInteger& A = iResult; |
|
203 //Set A to one converted in for this modulus without changing the memory size of A (iResult) |
|
204 A.CopyL(temp, EFalse); |
|
205 CleanupStack::PopAndDestroy(&temp); |
|
206 |
|
207 TInt i = aExponent.BitCount() - 1; |
|
208 |
|
209 // 3 While i>=0 do: |
|
210 while( i>=0 ) |
|
211 { |
|
212 // 3.1 If ei == 0 then A <- A^2 |
|
213 if(!aExponent.Bit(i)) |
|
214 { |
|
215 DoSquareL(A, A); |
|
216 i--; |
|
217 } |
|
218 // 3.2 Find longest bitstring ei,ei-1,...,el s.t. i-l+1<=k and el==1 |
|
219 // and do: |
|
220 // A <- (A^2^(i-l+1)) * g[the index indicated by the bitstring value] |
|
221 else |
|
222 { |
|
223 slider.FindNextWindow(i); |
|
224 assert(slider.Length() >= 1); |
|
225 for(TUint j=0; j<slider.Length(); j++) |
|
226 { |
|
227 DoSquareL(A, A); |
|
228 } |
|
229 DoMultiplyL(A, A, powerArray[slider.Value()>>1]); |
|
230 i -= slider.Length(); |
|
231 } |
|
232 } |
|
233 CleanupStack::PopAndDestroy(2, &g2); //powerArray, g2 |
|
234 return ConvertOutL(A); // A == iResult |
|
235 } |