/src/SymCrypt/lib/ec_montgomery.c
Line | Count | Source (jump to first uncovered line) |
1 | | // |
2 | | // ec_montgomery.c Montgomery Implementation |
3 | | // |
4 | | // Copyright (c) Microsoft Corporation. Licensed under the MIT license. |
5 | | // |
6 | | |
7 | | #include "precomp.h" |
8 | | |
9 | | VOID |
10 | | SYMCRYPT_CALL |
11 | | SymCryptMontgomeryFillScratchSpaces(_In_ PSYMCRYPT_ECURVE pCurve) |
12 | 0 | { |
13 | 0 | UINT32 nDigits = SymCryptDigitsFromBits( pCurve->FModBitsize ); |
14 | 0 | UINT32 nBytes = SymCryptSizeofModElementFromModulus( pCurve->FMod ); |
15 | 0 | UINT32 nCommon = SYMCRYPT_MAX( SymCryptSizeofIntFromDigits( nDigits ), SYMCRYPT_MAX( SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( nDigits ), SYMCRYPT_SCRATCH_BYTES_FOR_MODINV( nDigits ) ) ); |
16 | 0 | UINT32 cbModElement = pCurve->cbModElement; |
17 | 0 | UINT32 nDigitsFieldLength = pCurve->FModDigits; |
18 | | |
19 | | // |
20 | | // All the scratch space computations are upper bounded by the SizeofXXX bound (2^19) and |
21 | | // the SCRATCH_BYTES_FOR_XXX bound (2^24) (see symcrypt_internal.h). |
22 | | // |
23 | | // One caveat is SymCryptSizeofEcpointFromCurve and SymCryptSizeofEcpointEx which calculate the |
24 | | // size of EcPoint with 4 coordinates (each one a modelement of max size 2^17). Thus upper |
25 | | // bounded by 2^20. |
26 | | // |
27 | |
|
28 | 0 | pCurve->cbScratchCommon = nCommon; |
29 | 0 | pCurve->cbScratchScalar = |
30 | 0 | SymCryptSizeofIntFromDigits(nDigits) + |
31 | 0 | 6 * nBytes + |
32 | 0 | nCommon; |
33 | |
|
34 | 0 | pCurve->cbScratchScalarMulti = 0; |
35 | 0 | pCurve->cbScratchGetSetValue = |
36 | 0 | SymCryptSizeofEcpointEx( cbModElement, SYMCRYPT_ECPOINT_FORMAT_MAX_LENGTH ) + |
37 | 0 | 2 * cbModElement + |
38 | 0 | SYMCRYPT_MAX( SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( nDigitsFieldLength ), |
39 | 0 | SYMCRYPT_SCRATCH_BYTES_FOR_MODINV( nDigitsFieldLength ) ); |
40 | |
|
41 | 0 | pCurve->cbScratchGetSetValue = SYMCRYPT_MAX( pCurve->cbScratchGetSetValue, SymCryptSizeofIntFromDigits( nDigits ) ); |
42 | |
|
43 | 0 | pCurve->cbScratchEckey = |
44 | 0 | SYMCRYPT_MAX( cbModElement + SymCryptSizeofIntFromDigits(SymCryptEcurveDigitsofScalarMultiplier(pCurve)), |
45 | 0 | SymCryptSizeofEcpointFromCurve( pCurve ) ) + |
46 | 0 | SYMCRYPT_MAX( pCurve->cbScratchScalar, pCurve->cbScratchGetSetValue ); |
47 | 0 | } |
48 | | |
49 | | VOID |
50 | | SYMCRYPT_CALL |
51 | | SymCryptMontgomerySetDistinguished( |
52 | | _In_ PCSYMCRYPT_ECURVE pCurve, |
53 | | _Out_ PSYMCRYPT_ECPOINT poDst, |
54 | | _Out_writes_bytes_( cbScratch ) |
55 | | PBYTE pbScratch, |
56 | | SIZE_T cbScratch ) |
57 | 0 | { |
58 | 0 | SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_MONTGOMERY_TYPE(pCurve) ); |
59 | 0 | SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poDst->pCurve) ); |
60 | |
|
61 | 0 | UNREFERENCED_PARAMETER( pbScratch ); |
62 | 0 | UNREFERENCED_PARAMETER( cbScratch ); |
63 | |
|
64 | 0 | SymCryptEcpointCopy( pCurve, pCurve->G, poDst ); |
65 | 0 | } |
66 | | |
67 | | // |
68 | | // Verify poSrc1(X1, Z1) = poSrc2(X2, Z2) |
69 | | // To avoid ModInv for 1/Z, we do |
70 | | // X1 * Z2 = X2 * Z1 |
71 | | // |
72 | | // This function currently ignores the flags parameter as there is no distinction between equal and |
73 | | // negative equal case in Single Projective Coordinates used in Montgomery curves. We accept the flags |
74 | | // to maintain the same API as for other curves. |
75 | | // |
76 | | UINT32 |
77 | | SYMCRYPT_CALL |
78 | | SymCryptMontgomeryIsEqual( |
79 | | _In_ PCSYMCRYPT_ECURVE pCurve, |
80 | | _In_ PCSYMCRYPT_ECPOINT poSrc1, |
81 | | _In_ PCSYMCRYPT_ECPOINT poSrc2, |
82 | | UINT32 flags, |
83 | | _Out_writes_bytes_( cbScratch ) |
84 | | PBYTE pbScratch, |
85 | | SIZE_T cbScratch) |
86 | 0 | { |
87 | 0 | PSYMCRYPT_MODELEMENT peTemp[2]; |
88 | 0 | PSYMCRYPT_MODELEMENT peSrc1X, peSrc1Z; |
89 | 0 | PSYMCRYPT_MODELEMENT peSrc2X, peSrc2Z; |
90 | 0 | PSYMCRYPT_MODULUS pmMod = pCurve->FMod; |
91 | 0 | SIZE_T nBytes; |
92 | |
|
93 | 0 | SYMCRYPT_ASSERT( (flags & ~(SYMCRYPT_FLAG_ECPOINT_EQUAL|SYMCRYPT_FLAG_ECPOINT_NEG_EQUAL)) == 0 ); |
94 | 0 | SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_MONTGOMERY_TYPE(pCurve) ); |
95 | 0 | SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc1->pCurve) && SymCryptEcurveIsSame(pCurve, poSrc2->pCurve) ); |
96 | 0 | SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_INTERNAL_SCRATCH_BYTES_FOR_COMMON_ECURVE_OPERATIONS( pCurve ) ); |
97 | |
|
98 | 0 | UNREFERENCED_PARAMETER( flags ); |
99 | |
|
100 | 0 | nBytes = SymCryptSizeofModElementFromModulus( pmMod ); |
101 | |
|
102 | 0 | SYMCRYPT_ASSERT( cbScratch >= 2 * nBytes ); |
103 | |
|
104 | 0 | for (UINT32 i = 0; i < 2; ++i) |
105 | 0 | { |
106 | 0 | peTemp[i] = SymCryptModElementCreate( pbScratch, nBytes, pmMod ); |
107 | 0 | pbScratch += nBytes; |
108 | 0 | cbScratch -= nBytes; |
109 | 0 | } |
110 | |
|
111 | 0 | peSrc1X = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc1 ); |
112 | 0 | peSrc1Z = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc1 ); |
113 | |
|
114 | 0 | peSrc2X = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc2 ); |
115 | 0 | peSrc2Z = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc2 ); |
116 | | |
117 | | // peTemp[0] = X1 * Z2 |
118 | 0 | SymCryptModMul( pmMod, peSrc1X, peSrc2Z, peTemp[0], pbScratch, cbScratch ); |
119 | | |
120 | | // peTemp[1] = X2 * Z1 |
121 | 0 | SymCryptModMul( pmMod, peSrc2X, peSrc1Z, peTemp[1], pbScratch, cbScratch ); |
122 | |
|
123 | 0 | return SymCryptModElementIsEqual( pmMod, peTemp[0], peTemp[1] ); |
124 | 0 | } |
125 | | |
126 | | UINT32 |
127 | | SYMCRYPT_CALL |
128 | | SymCryptMontgomeryIsZero( |
129 | | _In_ PCSYMCRYPT_ECURVE pCurve, |
130 | | _In_ PCSYMCRYPT_ECPOINT poSrc, |
131 | | _Out_writes_bytes_( cbScratch ) |
132 | | PBYTE pbScratch, |
133 | | SIZE_T cbScratch ) |
134 | 0 | { |
135 | 0 | PCSYMCRYPT_MODULUS FMod = pCurve->FMod; |
136 | 0 | PSYMCRYPT_MODELEMENT peZ = NULL; // Pointer to Z |
137 | |
|
138 | 0 | SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_MONTGOMERY_TYPE(pCurve) ); |
139 | 0 | SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc->pCurve) ); |
140 | |
|
141 | 0 | UNREFERENCED_PARAMETER( pbScratch ); |
142 | 0 | UNREFERENCED_PARAMETER( cbScratch ); |
143 | | |
144 | | // Getting pointer to Z of the source point |
145 | 0 | peZ = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc ); |
146 | |
|
147 | 0 | return SymCryptModElementIsZero( FMod, peZ ); |
148 | 0 | } |
149 | | |
150 | | VOID |
151 | | SymCryptMontgomeryDoubleAndAdd( |
152 | | _In_ PCSYMCRYPT_MODULUS pmMod, |
153 | | _In_ PCSYMCRYPT_MODELEMENT peX1, |
154 | | _In_opt_ PCSYMCRYPT_MODELEMENT peZ1, |
155 | | _In_ PCSYMCRYPT_MODELEMENT peA24, |
156 | | _Inout_ PSYMCRYPT_MODELEMENT peX2, |
157 | | _Inout_ PSYMCRYPT_MODELEMENT peZ2, |
158 | | _Inout_ PSYMCRYPT_MODELEMENT peX3, |
159 | | _Inout_ PSYMCRYPT_MODELEMENT peZ3, |
160 | | _Inout_ PSYMCRYPT_MODELEMENT peTemp1, |
161 | | _Inout_ PSYMCRYPT_MODELEMENT peTemp2, |
162 | | _Out_writes_bytes_( cbScratch ) PBYTE pbScratch, |
163 | | SIZE_T cbScratch) |
164 | | /* |
165 | | We use the notation of ladd-1987-m-3, this is a generic Montgomery ladder implementation. |
166 | | This is similar to RFC7748 for TLS use of curve25519, however, unlike in the RFC, we support the case when Z1 != 1. |
167 | | |
168 | | When it is statically known that Z1 == 1 the caller can set peZ1 to NULL to skip one redundant modular multiplication. |
169 | | Note that this will be revealed through timing, so peZ1 can only be set to NULL it is not secret that Z1 == 1. |
170 | | Z1 == 1 is statically known for points which have just been imported into SymCrypt (and for the distinguished point of the |
171 | | curve), and this knowledge is tracked in an ecPoint's normalized flag. |
172 | | |
173 | | The (X,Z) values represent an x-coordinate (X/Z) but it avoids the modular division. |
174 | | |
175 | | The value a24 is such that 4*a24 = a+2 where a is one of the Montgomery curve parameters. |
176 | | Thus, a24 = (a+2)/4. For curve25519, A = 486662, so a24 = 121666 (=0x01db42) |
177 | | |
178 | | Algorithm (ladd-1987-m-3), with all operations expanded |
179 | | A = X2 + Z2 |
180 | | AA = A^2 |
181 | | B = X2 - Z2 |
182 | | BB = B^2 |
183 | | E = AA - BB |
184 | | C = X3 + Z3 |
185 | | D = X3 - Z3 |
186 | | DA = D * A |
187 | | CB = C * B |
188 | | X5 = (DA + CB)^2 |
189 | | DApCB = DA + CB |
190 | | X5 = DApCB^2 |
191 | | if peZ1 != NULL: |
192 | | X5 = Z1 * X5 |
193 | | Z5 = X1 * (DA - CB)^2 |
194 | | DAmCB = DA - CB |
195 | | DAmCB2 = DAmCB ^ 2 |
196 | | Z5 = X1 * DAmCB2 |
197 | | X4 = AA * BB |
198 | | Z4 = E * (BB + a24 * E) |
199 | | A24E = A24 * E |
200 | | BAE = BB + A24 * E |
201 | | Z4 = E * BAE |
202 | | |
203 | | If we write a = (X2,Z2) and b = (X3,Z3), and a-b = (X1,Z1), then this algorithm computes |
204 | | (2*a) and (a+b) into (X4, Z4) and (X5,Z5) respectively. |
205 | | The Montgomery ladder uses this as follows: |
206 | | - Store xP and (x+1)P |
207 | | - To process a 0 bit in the scalar, apply the DoubleAndAdd to (xP,(x+1)P) to get (2xP, (2x+1)P) |
208 | | - To process a 1 bit in the scalar, apply the DoubleAndAdd to ((x+1)P, xP) to get ((2x+2)P, (2x+1)P) |
209 | | This updates the state to either (2xP, (2x+1)P) or to ((2x+1)P, (2x+2)P) and corresponds to updating |
210 | | x to either 2x or 2x+1. |
211 | | |
212 | | The starting value is (0,P), represented as ((1,0),(P_x,P_z) |
213 | | The algorithm above, when applied to (1, 0, X, Z) produces: |
214 | | A = 1, AA = 1, B = 1, BB = 1, E = 0, |
215 | | C = X+Z, D = X-Z, DA = X-Z, CB = X+Z, |
216 | | X5 = 4(X^2)Z, Z5 = 4X(Z^2) |
217 | | X4 = 1, Z4 = 0 |
218 | | for an output of (1, 0, 4(X^2)Z, 4X(Z^2)) |
219 | | But (4(X^2)Z, 4X(Z^2)) is just another representation of (X,Z) as only the quotient of the two numbers is significant. |
220 | | So even if an exponent starts with a bunch of 0 bits, the DoubleAndAdd-based function computes the right result in constant time. |
221 | | |
222 | | */ |
223 | 0 | { |
224 | | // Temp1 = A = X2 + Z2 |
225 | 0 | SymCryptModAdd( pmMod, peX2, peZ2, peTemp1, pbScratch, cbScratch ); |
226 | | |
227 | | // Z2 = B = X2 - Z2 |
228 | 0 | SymCryptModSub( pmMod, peX2, peZ2, peZ2, pbScratch, cbScratch ); |
229 | | |
230 | | // Temp2 = C = X3 + Z3 |
231 | 0 | SymCryptModAdd( pmMod, peX3, peZ3, peTemp2, pbScratch, cbScratch ); |
232 | | |
233 | | // Z3 = D = X3 - Z3 |
234 | 0 | SymCryptModSub( pmMod, peX3, peZ3, peZ3, pbScratch, cbScratch ); |
235 | | |
236 | | // X3 = CB = C * B = Temp2 * Z2 |
237 | 0 | SymCryptModMul( pmMod, peTemp2, peZ2, peX3, pbScratch, cbScratch ); |
238 | | |
239 | | // Z3 = DA = D * A = Z3 * Temp1 |
240 | 0 | SymCryptModMul( pmMod, peZ3, peTemp1, peZ3, pbScratch, cbScratch ); |
241 | | |
242 | | // From this point on, the outputs (X5,Z5) depend only on (X3,Z3) and (X1,Z1) |
243 | | // and the outputs (X4,Z4) only on (Temp1,Z2) and A24 |
244 | | // We'll do the (X4,Z4) first |
245 | | |
246 | | // X2 = AA = A * A = Temp1 * Temp1 |
247 | 0 | SymCryptModSquare( pmMod, peTemp1, peX2, pbScratch, cbScratch ); |
248 | | |
249 | | // Temp1 = BB = B * B = Z2 * Z2 |
250 | 0 | SymCryptModSquare( pmMod, peZ2, peTemp1, pbScratch, cbScratch ); |
251 | | |
252 | | // Temp2 = E = AA - BB = X2 - Temp1 |
253 | 0 | SymCryptModSub( pmMod, peX2, peTemp1, peTemp2, pbScratch, cbScratch ); |
254 | | |
255 | | // X2 = X4 = AA * BB = X2 * Temp1 |
256 | 0 | SymCryptModMul( pmMod, peX2, peTemp1, peX2, pbScratch, cbScratch ); |
257 | | |
258 | | // Z2 = A24E = A24 * E = A24 * Temp2 |
259 | 0 | SymCryptModMul( pmMod, peA24, peTemp2, peZ2, pbScratch, cbScratch ); |
260 | | |
261 | | // Z2 = BAE = (BB + a24 * E) = BB + A24E = Temp1 + Z2 |
262 | 0 | SymCryptModAdd( pmMod, peTemp1, peZ2, peZ2, pbScratch, cbScratch ); |
263 | | |
264 | | // Z2 = Z4 = E * BAE = Temp2 + Z2 |
265 | 0 | SymCryptModMul( pmMod, peTemp2, peZ2, peZ2, pbScratch, cbScratch ); |
266 | | |
267 | | // Now we compute (X5, Z5) |
268 | | |
269 | | // Temp1 = DApCB = DA + CB = Z3 + X3 |
270 | 0 | SymCryptModAdd( pmMod, peZ3, peX3, peTemp1, pbScratch, cbScratch ); |
271 | | |
272 | | // Z3 = DAmCB = DA - CB = Z3 - X3 |
273 | 0 | SymCryptModSub( pmMod, peZ3, peX3, peZ3, pbScratch, cbScratch ); |
274 | | |
275 | | // X3 = DApCB^2 = Temp1 ^ 2 ( = X5 when (peZ1 == NULL) => Z1 == 1) |
276 | 0 | SymCryptModSquare( pmMod, peTemp1, peX3, pbScratch, cbScratch ); |
277 | |
|
278 | 0 | if (peZ1 != NULL) // source point is not normalized |
279 | 0 | { |
280 | | // X3 = X5 = Z1 * DApCB^2 = Z1 * X3 |
281 | 0 | SymCryptModMul( pmMod, peZ1, peX3, peX3, pbScratch, cbScratch ); |
282 | 0 | } |
283 | | |
284 | | // Z3 = DAmCB2 = DAmCB ^ 2 = Z3 ^ 2 |
285 | 0 | SymCryptModSquare( pmMod, peZ3, peZ3, pbScratch, cbScratch ); |
286 | | |
287 | | // Z3 = Z5 = X1 * DAmCB2 = X1 * Z3 |
288 | 0 | SymCryptModMul( pmMod, peX1, peZ3, peZ3, pbScratch, cbScratch ); |
289 | 0 | } |
290 | | |
291 | | // |
292 | | // Montgomery point multiplication only works on X-coordinates. |
293 | | // We ignore the Y-coordinates. |
294 | | // |
295 | | SYMCRYPT_ERROR |
296 | | SYMCRYPT_CALL |
297 | | SymCryptMontgomeryPointScalarMul( |
298 | | _In_ PCSYMCRYPT_ECURVE pCurve, |
299 | | _In_ PCSYMCRYPT_INT piScalar, |
300 | | _In_opt_ |
301 | | PCSYMCRYPT_ECPOINT poSrc, |
302 | | UINT32 flags, |
303 | | _Out_ PSYMCRYPT_ECPOINT poDst, |
304 | | _Out_writes_bytes_( cbScratch ) |
305 | | PBYTE pbScratch, |
306 | | SIZE_T cbScratch) |
307 | 0 | { |
308 | 0 | SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR; |
309 | |
|
310 | 0 | PSYMCRYPT_MODULUS pmMod; |
311 | 0 | PSYMCRYPT_MODELEMENT peX1, peZ1, peA24, peX2, peZ2, peX3, peZ3, peTemp1, peTemp2, peResult; |
312 | 0 | UINT32 i, nBytes, nDigits, cond, newcond, nCommon; |
313 | 0 | PBYTE pBegin; |
314 | 0 | SIZE_T cbAllScratch; |
315 | |
|
316 | 0 | SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_MONTGOMERY_TYPE(pCurve) ); |
317 | 0 | SYMCRYPT_ASSERT( (poSrc == NULL || SymCryptEcurveIsSame(pCurve, poSrc->pCurve)) && SymCryptEcurveIsSame(pCurve, poDst->pCurve) ); |
318 | | |
319 | | // Make sure we only specify the correct flags |
320 | 0 | if ((flags & ~SYMCRYPT_FLAG_ECC_LL_COFACTOR_MUL) != 0) |
321 | 0 | { |
322 | 0 | scError = SYMCRYPT_INVALID_ARGUMENT; |
323 | 0 | goto cleanup; |
324 | 0 | } |
325 | | |
326 | 0 | if (poSrc == NULL) |
327 | 0 | { |
328 | 0 | poSrc = pCurve->G; |
329 | 0 | } |
330 | | |
331 | | // |
332 | | // Set up structure for X2, Z2, X3, Z3, Temp1, and Temp2, and the scratch space. |
333 | | // |
334 | 0 | pmMod = pCurve->FMod; |
335 | |
|
336 | 0 | nDigits = SymCryptDigitsFromBits( pCurve->FModBitsize ); |
337 | 0 | nBytes = SymCryptSizeofModElementFromModulus( pmMod ); |
338 | 0 | nCommon = SYMCRYPT_MAX( SymCryptSizeofIntFromDigits(nDigits), SYMCRYPT_MAX(SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS(nDigits), SYMCRYPT_SCRATCH_BYTES_FOR_MODINV(nDigits))); |
339 | |
|
340 | 0 | SYMCRYPT_ASSERT( cbScratch >= 6 * nBytes + nCommon ); |
341 | |
|
342 | 0 | cbAllScratch = cbScratch; |
343 | 0 | pBegin = pbScratch; |
344 | | |
345 | | // |
346 | | // Create mod elements |
347 | | // |
348 | 0 | peX2 = SymCryptModElementCreate( pbScratch, nBytes, pmMod ); |
349 | 0 | pbScratch += nBytes; |
350 | |
|
351 | 0 | peZ2 = SymCryptModElementCreate( pbScratch, nBytes, pmMod ); |
352 | 0 | pbScratch += nBytes; |
353 | |
|
354 | 0 | peX3 = SymCryptModElementCreate( pbScratch, nBytes, pmMod ); |
355 | 0 | pbScratch += nBytes; |
356 | |
|
357 | 0 | peZ3 = SymCryptModElementCreate( pbScratch, nBytes, pmMod ); |
358 | 0 | pbScratch += nBytes; |
359 | |
|
360 | 0 | peTemp1 = SymCryptModElementCreate( pbScratch, nBytes, pmMod ); |
361 | 0 | pbScratch += nBytes; |
362 | |
|
363 | 0 | peTemp2 = SymCryptModElementCreate( pbScratch, nBytes, pmMod ); |
364 | 0 | pbScratch += nBytes; |
365 | |
|
366 | 0 | cbScratch = nCommon; |
367 | | |
368 | | // |
369 | | // Set up values |
370 | | // |
371 | |
|
372 | 0 | peA24 = pCurve->A; |
373 | | |
374 | | // X1 = X, Z1 = Z |
375 | 0 | peX1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc); |
376 | 0 | peZ1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc); |
377 | | |
378 | | // X2 = 1, Z2 = 0, X3 = X, Z3 = Z |
379 | 0 | SymCryptModElementSetValueUint32( 1, pmMod, peX2, pbScratch, cbScratch ); |
380 | 0 | SymCryptModElementSetValueUint32( 0, pmMod, peZ2, pbScratch, cbScratch ); |
381 | 0 | SymCryptModElementCopy( pmMod, peX1, peX3 ); |
382 | 0 | SymCryptModElementCopy( pmMod, peZ1, peZ3 ); |
383 | |
|
384 | 0 | if ( poSrc->normalized ) |
385 | 0 | { |
386 | | // Set peZ1 to NULL to avoid redundant multiplications in SymCryptMontgomeryDoubleAndAdd |
387 | 0 | peZ1 = NULL; |
388 | 0 | } |
389 | | |
390 | | // |
391 | | // Montgomery ladder scalar multiplication |
392 | | // |
393 | |
|
394 | 0 | i = (pCurve->GOrdBitsize + pCurve->coFactorPower); |
395 | 0 | cond = 0; |
396 | 0 | while ( i != 0 ) |
397 | 0 | { |
398 | | // If cond = 0, we have (X2, Z2, X3, Z3) |
399 | | // if cond = 1, we have (X3, Z3, X2, Z2) |
400 | 0 | i--; |
401 | 0 | newcond = SymCryptIntGetBit( piScalar, i ); |
402 | 0 | cond ^= newcond; |
403 | |
|
404 | 0 | SymCryptModElementConditionalSwap( pmMod, peX2, peX3, cond); |
405 | 0 | SymCryptModElementConditionalSwap( pmMod, peZ2, peZ3, cond); |
406 | |
|
407 | 0 | cond = newcond; |
408 | |
|
409 | 0 | SymCryptMontgomeryDoubleAndAdd( pmMod, peX1, peZ1, peA24, peX2, peZ2, peX3, peZ3, peTemp1, peTemp2, pbScratch, cbScratch ); |
410 | 0 | } |
411 | | |
412 | | // Now put them back in the normal order |
413 | 0 | SymCryptModElementConditionalSwap( pmMod, peX2, peX3, cond); |
414 | 0 | SymCryptModElementConditionalSwap( pmMod, peZ2, peZ3, cond); |
415 | | |
416 | | // Multiply by the cofactor (if needed) by continuing the doubling |
417 | 0 | if ((flags & SYMCRYPT_FLAG_ECC_LL_COFACTOR_MUL) != 0) |
418 | 0 | { |
419 | 0 | i = pCurve->coFactorPower; |
420 | 0 | while (i!=0) |
421 | 0 | { |
422 | 0 | i--; |
423 | | // We only use the doubling output here, so we definitely don't need to provide Z1 |
424 | | // We could refactor to have a separate SymCryptMontgomeryDouble function but for Curve25519 this loop is ~1% of runtime |
425 | 0 | SymCryptMontgomeryDoubleAndAdd( pmMod, peX1, NULL, peA24, peX2, peZ2, peX3, peZ3, peTemp1, peTemp2, pbScratch, cbScratch ); |
426 | 0 | } |
427 | 0 | } |
428 | | |
429 | | // Set X coordinate |
430 | 0 | peResult = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poDst); |
431 | 0 | SymCryptModElementCopy( pCurve->FMod, peX2, peResult ); |
432 | | |
433 | | // Set Z coordinate |
434 | 0 | peResult = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poDst); |
435 | 0 | SymCryptModElementCopy( pCurve->FMod, peZ2, peResult ); |
436 | |
|
437 | 0 | poDst->normalized = FALSE; |
438 | |
|
439 | 0 | scError = SYMCRYPT_NO_ERROR; |
440 | |
|
441 | 0 | cleanup: |
442 | 0 | return scError; |
443 | 0 | } |