/src/SymCrypt/lib/ecurve.c
Line | Count | Source (jump to first uncovered line) |
1 | | // |
2 | | // ecurve.c Ecurve functions |
3 | | // |
4 | | // Copyright (c) Microsoft Corporation. Licensed under the MIT license. |
5 | | // |
6 | | // |
7 | | |
8 | | #include "precomp.h" |
9 | | |
10 | | // Approximate number of consecutive operations with the modulus and the |
11 | | // (sub)group order of the curve. These numbers can trigger special optimizations |
12 | | // on the underlying code, e.g. use of Montgomery multiplication or not. |
13 | 946 | #define SYMCRYPT_INTERNAL_ECURVE_MODULUS_NUMOF_OPERATIONS( _bitsize ) ( 100 * (_bitsize) ) |
14 | 946 | #define SYMCRYPT_INTERNAL_ECURVE_GROUP_ORDER_NUMOF_OPERATIONS ( 1 ) |
15 | | |
16 | | // We limit the max size of the elliptic curve to avoid denial-of-service attacks when |
17 | | // an attacker sends a curve specification. |
18 | | // Elliptic curve operations are O(n^3) in the curve size. Theoretically SymCrypt supports |
19 | | // values up to 2^20 bits at the moment, so that is 2^12 times more than a typical curve size |
20 | | // of 256 bits. Operations are then 2^36 times slower, and a single operation could take months. |
21 | | // Our largest curve is 521 bits, and we won't see curves > 1024 bits for a while yet. |
22 | 1.89k | #define SYMCRYPT_INTERNAL_MAX_ECURVE_SIZE (1024) |
23 | | |
24 | | // Private struct which records the sizes of various different parts of the elliptic curve |
25 | | // structure. |
26 | | typedef struct _SYMCRYPT_ECURVE_SIZES { |
27 | | UINT32 nDigitsFieldLength; |
28 | | UINT32 nDigitsSubgroupOrder; |
29 | | UINT32 nDigitsCoFactor; |
30 | | UINT32 cbAlloc; // Length of the whole curve buffer |
31 | | UINT32 cbModulus; |
32 | | UINT32 cbModElement; |
33 | | UINT32 cbEcpoint; |
34 | | UINT32 cbSubgroupOrder; |
35 | | UINT32 cbCoFactor; |
36 | | UINT32 cbScratch; |
37 | | SYMCRYPT_ECPOINT_COORDINATES eCoordinates; |
38 | | } SYMCRYPT_ECURVE_SIZES, *PSYMCRYPT_ECURVE_SIZES; |
39 | | typedef const SYMCRYPT_ECURVE_SIZES * PCSYMCRYPT_ECURVE_SIZES; |
40 | | |
41 | | // Helper function which validates curve parameters and computes various buffer sizes. |
42 | | static |
43 | | BOOLEAN |
44 | | SymCryptEcurveValidateAndComputeSizes( |
45 | | _In_ PCSYMCRYPT_ECURVE_PARAMS pParams, |
46 | | _Out_ PSYMCRYPT_ECURVE_SIZES pSizes ) |
47 | 946 | { |
48 | 946 | BOOLEAN fSuccess = FALSE; |
49 | | |
50 | | // Check that the parameters are well formatted |
51 | 946 | SYMCRYPT_ASSERT( pParams != NULL ); |
52 | 946 | SYMCRYPT_ASSERT( (pParams->version == 1) || (pParams->version == 2) ); |
53 | 946 | SYMCRYPT_ASSERT( pParams->cbFieldLength != 0 ); |
54 | 946 | SYMCRYPT_ASSERT( pParams->cbSubgroupOrder != 0 ); |
55 | 946 | SYMCRYPT_ASSERT( pParams->cbCofactor != 0 ); |
56 | 946 | SYMCRYPT_ASSERT( (pParams->type == SYMCRYPT_ECURVE_TYPE_SHORT_WEIERSTRASS) || |
57 | 946 | (pParams->type == SYMCRYPT_ECURVE_TYPE_TWISTED_EDWARDS) || |
58 | 946 | (pParams->type == SYMCRYPT_ECURVE_TYPE_MONTGOMERY) ); |
59 | | |
60 | | // Reject inputs that are wildly big to avoid denial-of-service attacks. |
61 | 946 | if ( pParams->cbFieldLength > SYMCRYPT_INTERNAL_MAX_ECURVE_SIZE/8 || |
62 | 946 | pParams->cbSubgroupOrder > SYMCRYPT_INTERNAL_MAX_ECURVE_SIZE / 8 + 1 || // subgroup can be > field prime |
63 | 946 | pParams->cbCofactor > 2 || // We support co-factor = 256 |
64 | 946 | pParams->cbSeed > 256 ) |
65 | 0 | { |
66 | 0 | goto cleanup; |
67 | 0 | } |
68 | | |
69 | | // Getting the # of digits of the various parameters |
70 | 946 | pSizes->nDigitsFieldLength = SymCryptDigitsFromBits( pParams->cbFieldLength * 8 ); |
71 | 946 | pSizes->nDigitsSubgroupOrder = SymCryptDigitsFromBits( pParams->cbSubgroupOrder * 8 ); |
72 | 946 | pSizes->nDigitsCoFactor = SymCryptDigitsFromBits( pParams->cbCofactor * 8 ); |
73 | | |
74 | | // ----------------------------------------------- |
75 | | // Getting the byte sizes of different objects |
76 | | // ----------------------------------------------- |
77 | 946 | pSizes->cbModulus = SymCryptSizeofModulusFromDigits( pSizes->nDigitsFieldLength ); |
78 | 946 | pSizes->cbSubgroupOrder = SymCryptSizeofModulusFromDigits( pSizes->nDigitsSubgroupOrder ); |
79 | 946 | pSizes->cbCoFactor = SymCryptSizeofIntFromDigits( pSizes->nDigitsCoFactor ); |
80 | | |
81 | 946 | pSizes->cbModElement = SYMCRYPT_SIZEOF_MODELEMENT_FROM_BITS( pParams->cbFieldLength * 8 ); |
82 | | |
83 | | // EcPoint: The curve is not initialized yet, we call the helper function. |
84 | | // It depends on the default format of each curve type |
85 | 946 | switch (pParams->type) |
86 | 946 | { |
87 | 852 | case (SYMCRYPT_ECURVE_TYPE_SHORT_WEIERSTRASS): |
88 | 852 | pSizes->eCoordinates = SYMCRYPT_ECPOINT_COORDINATES_JACOBIAN; |
89 | 852 | break; |
90 | 94 | case (SYMCRYPT_ECURVE_TYPE_TWISTED_EDWARDS): |
91 | 94 | pSizes->eCoordinates = SYMCRYPT_ECPOINT_COORDINATES_EXTENDED_PROJECTIVE; |
92 | 94 | break; |
93 | 0 | case (SYMCRYPT_ECURVE_TYPE_MONTGOMERY): |
94 | 0 | pSizes->eCoordinates = SYMCRYPT_ECPOINT_COORDINATES_SINGLE_PROJECTIVE; |
95 | 0 | break; |
96 | 0 | default: |
97 | 0 | goto cleanup; |
98 | 946 | } |
99 | | |
100 | 946 | pSizes->cbEcpoint = SymCryptSizeofEcpointEx( pSizes->cbModElement, SYMCRYPT_INTERNAL_NUMOF_COORDINATES( pSizes->eCoordinates ) ); |
101 | | // ----------------------------------------------- |
102 | | |
103 | | // Compute memory needed for the curve |
104 | | // |
105 | | // From symcrypt_internal.h we have: |
106 | | // - sizeof results are upper bounded by 2^19 |
107 | | // Thus the following calculation does not overflow cbAlloc. |
108 | | // |
109 | 946 | pSizes->cbAlloc = sizeof( SYMCRYPT_ECURVE ) + |
110 | 946 | pSizes->cbModulus + |
111 | 946 | 2 * pSizes->cbModElement + |
112 | 946 | pSizes->cbSubgroupOrder + |
113 | 946 | pSizes->cbCoFactor; |
114 | | |
115 | 946 | if ( (pParams->type == SYMCRYPT_ECURVE_TYPE_SHORT_WEIERSTRASS) || |
116 | 946 | (pParams->type == SYMCRYPT_ECURVE_TYPE_TWISTED_EDWARDS) ) |
117 | 946 | { |
118 | | // If the curve's type is short Weierstrass allocate space for 2^(w-2) ECPOINTs |
119 | | // at the end of the curve's structure, where w is the width of the window. |
120 | | // |
121 | | // Note: The window width is fixed now. In later versions we can pass it in as a parameter. |
122 | | // SYMCRYPT_ASSERT( (1 << (SYMCRYPT_ECURVE_SW_DEF_WINDOW-2)) <= SYMCRYPT_ECURVE_SW_MAX_NPRECOMP_POINTS ); |
123 | 946 | pSizes->cbAlloc += (1 << (SYMCRYPT_ECURVE_SW_DEF_WINDOW-2))*pSizes->cbEcpoint; |
124 | 946 | } |
125 | 0 | else |
126 | 0 | { |
127 | | // Otherwise just allocate space for just the distinguished point |
128 | 0 | pSizes->cbAlloc += pSizes->cbEcpoint; |
129 | 0 | } |
130 | | |
131 | | // Compute memory needed for internal scratch space |
132 | | // EcpointSetValue and SymCryptOfflinePrecomputation |
133 | | |
134 | | // |
135 | | // From symcrypt_internal.h we have: |
136 | | // - sizeof results are upper bounded by 2^19 |
137 | | // - SYMCRYPT_SCRATCH_BYTES results are upper bounded by 2^27 (including RSA and ECURVE) |
138 | | // - SymCryptSizeofEcpointEx is bounded by 2^20 |
139 | | // Thus the following calculation does not overflow cbScratch. |
140 | | // |
141 | 946 | pSizes->cbScratch = SymCryptSizeofEcpointEx( pSizes->cbModElement, SYMCRYPT_ECPOINT_FORMAT_MAX_LENGTH ) + |
142 | 946 | 8 * pSizes->cbModElement + |
143 | 946 | SYMCRYPT_MAX( SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pSizes->nDigitsFieldLength ), |
144 | 946 | SYMCRYPT_SCRATCH_BYTES_FOR_MODINV( pSizes->nDigitsFieldLength ) ); |
145 | | // IntToModulus( FMod and GOrd ) |
146 | 946 | pSizes->cbScratch = SYMCRYPT_MAX( pSizes->cbScratch, |
147 | 946 | SYMCRYPT_SCRATCH_BYTES_FOR_INT_TO_MODULUS( SYMCRYPT_MAX(pSizes->nDigitsFieldLength, pSizes->nDigitsSubgroupOrder) ) ); |
148 | | // ModElementSetValue( FMod ) |
149 | 946 | pSizes->cbScratch = SYMCRYPT_MAX( pSizes->cbScratch, |
150 | 946 | SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pSizes->nDigitsFieldLength ) ); |
151 | | |
152 | 946 | fSuccess = TRUE; |
153 | | |
154 | 946 | cleanup: |
155 | 946 | return fSuccess; |
156 | 946 | } |
157 | | |
158 | | BOOLEAN |
159 | | SYMCRYPT_CALL |
160 | | SymCryptEcurveBufferSizesFromParams( |
161 | | _In_ PCSYMCRYPT_ECURVE_PARAMS pParams, |
162 | | _Out_ SIZE_T * pcbCurve, |
163 | | _Out_ SIZE_T * pcbScratch ) |
164 | 0 | { |
165 | 0 | BOOLEAN fSuccess = FALSE; |
166 | 0 | SYMCRYPT_ECURVE_SIZES sizes; |
167 | |
|
168 | 0 | if ( !SymCryptEcurveValidateAndComputeSizes( pParams, &sizes )) |
169 | 0 | { |
170 | 0 | goto cleanup; |
171 | 0 | } |
172 | | |
173 | 0 | *pcbCurve = sizes.cbAlloc; |
174 | 0 | *pcbScratch = sizes.cbScratch; |
175 | |
|
176 | 0 | fSuccess = TRUE; |
177 | |
|
178 | 0 | cleanup: |
179 | 0 | return fSuccess; |
180 | 0 | } |
181 | | |
182 | | // Internal function which actually computes and writes curve into the given buffer. |
183 | | // |
184 | | // This is called internally by both SymCryptEcurveCreate() and SymCryptEcurveAllocate(). |
185 | | static |
186 | | PSYMCRYPT_ECURVE |
187 | | SymCryptEcurveInitialize( |
188 | | _In_ PCSYMCRYPT_ECURVE_PARAMS pParams, |
189 | | _In_ UINT32 flags, |
190 | | _In_ PCSYMCRYPT_ECURVE_SIZES pSizes, |
191 | | _Out_writes_bytes_( pSizes->cbAlloc ) PBYTE pbCurve, |
192 | | _Out_writes_bytes_( pSizes->cbScratch) PBYTE pbScratch ) |
193 | 946 | { |
194 | 946 | BOOLEAN fSuccess = FALSE; |
195 | 946 | SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR; |
196 | | |
197 | 946 | PSYMCRYPT_ECURVE pCurve = (PSYMCRYPT_ECURVE)pbCurve; |
198 | 946 | PBYTE pDst = NULL; // Destination pointer |
199 | 946 | PBYTE pSrc = NULL; // Source pointer |
200 | | |
201 | 946 | PBYTE pSrcGenerator = NULL; // We have to set the generator point |
202 | | // only after we have fully initialized the curve |
203 | | |
204 | 946 | PSYMCRYPT_INT pTempInt = 0; |
205 | | |
206 | 946 | PSYMCRYPT_MODELEMENT peTemp = NULL; |
207 | | |
208 | 946 | PCSYMCRYPT_ECURVE_PARAMS_V2_EXTENSION pcParamsV2Ext = NULL; |
209 | | |
210 | 946 | UNREFERENCED_PARAMETER( flags ); |
211 | | |
212 | | // ----------------------------------------------- |
213 | | // Populating the fields of the curve object |
214 | | // ----------------------------------------------- |
215 | | |
216 | | // Version of curve structure |
217 | 946 | pCurve->version = SYMCRYPT_INTERNAL_ECURVE_VERSION_LATEST; |
218 | | |
219 | | // Type of curve |
220 | 946 | pCurve->type = (int) pParams->type; |
221 | | |
222 | | // Curve point format |
223 | 946 | pCurve->eCoordinates = pSizes->eCoordinates; |
224 | | |
225 | | // Number of digits of the field modulus |
226 | 946 | pCurve->FModDigits = pSizes->nDigitsFieldLength; |
227 | | |
228 | | // Number of digits of the group order |
229 | 946 | pCurve->GOrdDigits = pSizes->nDigitsSubgroupOrder; |
230 | | |
231 | | // Byte size of field elements |
232 | 946 | pCurve->FModBytesize = (UINT32)pParams->cbFieldLength; |
233 | | |
234 | | // Byte size of group elements |
235 | 946 | SYMCRYPT_ASSERT( pParams->cbSubgroupOrder < UINT32_MAX ); |
236 | 946 | pCurve->GOrdBytesize = (UINT32)pParams->cbSubgroupOrder; |
237 | | |
238 | | // Byte size of mod elements |
239 | 946 | pCurve->cbModElement = pSizes->cbModElement; |
240 | | |
241 | | // Total bytesize of the curve (used to free the curve object) |
242 | 946 | pCurve->cbAlloc = pSizes->cbAlloc; |
243 | | |
244 | | // Set destination and source pointers |
245 | 946 | pDst = ((PBYTE) pCurve) + sizeof( SYMCRYPT_ECURVE ); |
246 | 946 | pSrc = ((PBYTE) pParams) + sizeof( SYMCRYPT_ECURVE_PARAMS ); |
247 | | |
248 | | // Field Modulus |
249 | 946 | pCurve->FMod = SymCryptModulusCreate( pDst, pSizes->cbModulus, pSizes->nDigitsFieldLength ); |
250 | 946 | if ( pCurve->FMod == NULL ) |
251 | 0 | { |
252 | 0 | goto cleanup; |
253 | 0 | } |
254 | | |
255 | 946 | pTempInt = SymCryptIntFromModulus( pCurve->FMod ); |
256 | 946 | if ( pTempInt == NULL) |
257 | 0 | { |
258 | 0 | goto cleanup; |
259 | 0 | } |
260 | | |
261 | 946 | scError = SymCryptIntSetValue( pSrc, pParams->cbFieldLength, SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, pTempInt ); |
262 | 946 | if ( scError != SYMCRYPT_NO_ERROR ) |
263 | 0 | { |
264 | 0 | goto cleanup; |
265 | 0 | } |
266 | | |
267 | | // Field Modulus Bitsize |
268 | 946 | pCurve->FModBitsize = SymCryptIntBitsizeOfValue( pTempInt ); |
269 | 946 | if (pCurve->FModBitsize < SYMCRYPT_ECURVE_MIN_BITSIZE_FMOD) |
270 | 0 | { |
271 | 0 | scError = SYMCRYPT_WRONG_KEY_SIZE; |
272 | 0 | goto cleanup; |
273 | 0 | } |
274 | | |
275 | 946 | if( (SymCryptIntGetValueLsbits32( pTempInt ) & 1) == 0 ) |
276 | 0 | { |
277 | | // 'Prime' must be odd to avoid errors in conversion to modulus |
278 | 0 | scError = SYMCRYPT_INVALID_ARGUMENT; |
279 | 0 | goto cleanup; |
280 | 0 | } |
281 | | |
282 | | // IntToModulus requirement: |
283 | | // FModBitsize >= SYMCRYPT_ECURVE_MIN_BITSIZE_FMOD --> pTempInt > 0 |
284 | 946 | SymCryptIntToModulus( |
285 | 946 | pTempInt, |
286 | 946 | pCurve->FMod, |
287 | 946 | SYMCRYPT_INTERNAL_ECURVE_MODULUS_NUMOF_OPERATIONS( 8 * pParams->cbFieldLength ), |
288 | 946 | SYMCRYPT_FLAG_DATA_PUBLIC | SYMCRYPT_FLAG_MODULUS_PRIME, |
289 | 946 | pbScratch, |
290 | 946 | pSizes->cbScratch ); |
291 | | |
292 | 946 | pDst += pSizes->cbModulus; |
293 | 946 | pSrc += pParams->cbFieldLength; |
294 | | |
295 | | // A constant |
296 | 946 | pCurve->A = SymCryptModElementCreate( pDst, pSizes->cbModElement, pCurve->FMod ); |
297 | 946 | if ( pCurve->A == NULL ) |
298 | 0 | { |
299 | 0 | goto cleanup; |
300 | 0 | } |
301 | 946 | scError = SymCryptModElementSetValue( |
302 | 946 | pSrc, |
303 | 946 | pParams->cbFieldLength, |
304 | 946 | SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, |
305 | 946 | pCurve->FMod, |
306 | 946 | pCurve->A, |
307 | 946 | pbScratch, |
308 | 946 | pSizes->cbScratch ); |
309 | 946 | if ( scError != SYMCRYPT_NO_ERROR ) |
310 | 0 | { |
311 | 0 | goto cleanup; |
312 | 0 | } |
313 | 946 | pDst += pSizes->cbModElement; |
314 | 946 | pSrc += pParams->cbFieldLength; |
315 | | |
316 | | // B constant |
317 | 946 | pCurve->B = SymCryptModElementCreate( pDst, pSizes->cbModElement, pCurve->FMod ); |
318 | 946 | if ( pCurve->B == NULL ) |
319 | 0 | { |
320 | 0 | goto cleanup; |
321 | 0 | } |
322 | | |
323 | | // Detect Short-Weierstrass curves with A == -3 (NIST prime curves are all of this form) |
324 | | // Use B's ModElement space for check |
325 | 946 | if( pParams->type == SYMCRYPT_ECURVE_TYPE_SHORT_WEIERSTRASS ) |
326 | 852 | { |
327 | 852 | SymCryptModElementSetValueNegUint32( |
328 | 852 | 3, |
329 | 852 | pCurve->FMod, |
330 | 852 | pCurve->B, |
331 | 852 | pbScratch, |
332 | 852 | pSizes->cbScratch ); |
333 | 852 | if ( scError != SYMCRYPT_NO_ERROR ) |
334 | 0 | { |
335 | 0 | goto cleanup; |
336 | 0 | } |
337 | 852 | if( SymCryptModElementIsEqual( pCurve->FMod, pCurve->A, pCurve->B ) ) |
338 | 852 | { |
339 | 852 | pCurve->type = SYMCRYPT_INTERNAL_ECURVE_TYPE_SHORT_WEIERSTRASS_AM3; |
340 | 852 | } |
341 | 852 | } |
342 | | |
343 | | // Set B to the correct value |
344 | 946 | scError = SymCryptModElementSetValue( |
345 | 946 | pSrc, |
346 | 946 | pParams->cbFieldLength, |
347 | 946 | SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, |
348 | 946 | pCurve->FMod, |
349 | 946 | pCurve->B, |
350 | 946 | pbScratch, |
351 | 946 | pSizes->cbScratch ); |
352 | 946 | if ( scError != SYMCRYPT_NO_ERROR ) |
353 | 0 | { |
354 | 0 | goto cleanup; |
355 | 0 | } |
356 | 946 | pDst += pSizes->cbModElement; |
357 | 946 | pSrc += pParams->cbFieldLength; |
358 | | |
359 | | // Skip over the distinguished point until we fix all the parameters and scratch space sizes |
360 | 946 | pSrcGenerator = pSrc; |
361 | 946 | pSrc += pParams->cbFieldLength * 2; |
362 | | |
363 | | // Subgroup Order |
364 | 946 | pCurve->GOrd = SymCryptModulusCreate( pDst, pSizes->cbSubgroupOrder, pSizes->nDigitsSubgroupOrder ); |
365 | 946 | if ( pCurve->GOrd == NULL ) |
366 | 0 | { |
367 | 0 | goto cleanup; |
368 | 0 | } |
369 | | |
370 | 946 | pTempInt = SymCryptIntFromModulus( pCurve->GOrd ); |
371 | 946 | if ( pTempInt == NULL) |
372 | 0 | { |
373 | 0 | goto cleanup; |
374 | 0 | } |
375 | | |
376 | 946 | scError = SymCryptIntSetValue( pSrc, pParams->cbSubgroupOrder, SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, pTempInt ); |
377 | 946 | if ( scError != SYMCRYPT_NO_ERROR ) |
378 | 0 | { |
379 | 0 | goto cleanup; |
380 | 0 | } |
381 | | |
382 | | // Subgroup Order Bitsize |
383 | 946 | pCurve->GOrdBitsize = SymCryptIntBitsizeOfValue( pTempInt ); |
384 | 946 | if (pCurve->GOrdBitsize < SYMCRYPT_ECURVE_MIN_BITSIZE_GORD) |
385 | 0 | { |
386 | 0 | scError = SYMCRYPT_WRONG_KEY_SIZE; |
387 | 0 | goto cleanup; |
388 | 0 | } |
389 | | |
390 | 946 | if( (SymCryptIntGetValueLsbits32( pTempInt ) & 1) == 0 ) |
391 | 0 | { |
392 | | // 'Prime' must be odd to avoid errors in conversion to modulus |
393 | 0 | scError = SYMCRYPT_INVALID_ARGUMENT; |
394 | 0 | goto cleanup; |
395 | 0 | } |
396 | | |
397 | | // IntToModulus requirement: |
398 | | // GOrdBitsize >= SYMCRYPT_ECURVE_MIN_BITSIZE_GORD --> pTempInt > 0 |
399 | 946 | SymCryptIntToModulus( |
400 | 946 | pTempInt, |
401 | 946 | pCurve->GOrd, |
402 | 946 | SYMCRYPT_INTERNAL_ECURVE_GROUP_ORDER_NUMOF_OPERATIONS, |
403 | 946 | SYMCRYPT_FLAG_DATA_PUBLIC | SYMCRYPT_FLAG_MODULUS_PRIME, |
404 | 946 | pbScratch, |
405 | 946 | pSizes->cbScratch ); |
406 | | |
407 | 946 | pDst += pSizes->cbSubgroupOrder; |
408 | 946 | pSrc += pParams->cbSubgroupOrder; |
409 | | |
410 | | // Cofactor |
411 | 946 | pCurve->H = SymCryptIntCreate( pDst, pSizes->cbCoFactor, pSizes->nDigitsCoFactor ); |
412 | 946 | if ( pCurve->H == NULL ) |
413 | 0 | { |
414 | 0 | goto cleanup; |
415 | 0 | } |
416 | 946 | scError = SymCryptIntSetValue( |
417 | 946 | pSrc, |
418 | 946 | pParams->cbCofactor, |
419 | 946 | SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, |
420 | 946 | pCurve->H ); |
421 | 946 | if ( scError != SYMCRYPT_NO_ERROR ) |
422 | 0 | { |
423 | 0 | goto cleanup; |
424 | 0 | } |
425 | | |
426 | | |
427 | | // Make sure that the cofactor is not zero or too big |
428 | 946 | pCurve->coFactorPower = SymCryptIntBitsizeOfValue( pCurve->H ) - 1; |
429 | 946 | if (pCurve->coFactorPower == (UINT32)-1 || pCurve->coFactorPower > SYMCRYPT_ECURVE_MAX_COFACTOR_POWER) |
430 | 0 | { |
431 | 0 | goto cleanup; |
432 | 0 | } |
433 | | |
434 | | // Validate that the cofactor is a power of two |
435 | 946 | if (!SymCryptIntIsEqualUint32( pCurve->H, 1<<(pCurve->coFactorPower) )) |
436 | 0 | { |
437 | 0 | goto cleanup; |
438 | 0 | } |
439 | | |
440 | 946 | pDst += pSizes->cbCoFactor; |
441 | 946 | pSrc += pParams->cbCofactor; |
442 | | |
443 | | // Calculate scratch spaces' sizes |
444 | 946 | if (pParams->type == SYMCRYPT_ECURVE_TYPE_SHORT_WEIERSTRASS) |
445 | 852 | { |
446 | 852 | pCurve->info.sw.window = SYMCRYPT_ECURVE_SW_DEF_WINDOW; |
447 | 852 | pCurve->info.sw.nPrecompPoints = (1 << (SYMCRYPT_ECURVE_SW_DEF_WINDOW-2)); |
448 | 852 | pCurve->info.sw.nRecodedDigits = pCurve->GOrdBitsize + 1; // This is the maximum - used by the wNAF Interleaving method |
449 | | |
450 | 852 | SymCryptShortWeierstrassFillScratchSpaces( pCurve ); |
451 | 852 | } |
452 | 94 | else if ( pParams->type == SYMCRYPT_ECURVE_TYPE_TWISTED_EDWARDS ) |
453 | 94 | { |
454 | 94 | pCurve->info.sw.window = SYMCRYPT_ECURVE_SW_DEF_WINDOW; |
455 | 94 | pCurve->info.sw.nPrecompPoints = (1 << (SYMCRYPT_ECURVE_SW_DEF_WINDOW-2)); |
456 | 94 | pCurve->info.sw.nRecodedDigits = pCurve->GOrdBitsize + 1; // This is the maximum - used by the wNAF Interleaving method |
457 | | |
458 | 94 | SymCryptTwistedEdwardsFillScratchSpaces( pCurve ); |
459 | 94 | } |
460 | 0 | else if ( pParams->type == SYMCRYPT_ECURVE_TYPE_MONTGOMERY ) |
461 | 0 | { |
462 | 0 | SymCryptMontgomeryFillScratchSpaces( pCurve ); |
463 | 0 | } |
464 | | |
465 | | // Now set the distinguished point |
466 | 946 | pCurve->G = SymCryptEcpointCreate( pDst, pSizes->cbEcpoint, pCurve ); |
467 | 946 | if ( pCurve->G == NULL ) |
468 | 0 | { |
469 | 0 | goto cleanup; |
470 | 0 | } |
471 | 946 | scError = SymCryptEcpointSetValue( |
472 | 946 | pCurve, |
473 | 946 | pSrcGenerator, |
474 | 946 | pParams->cbFieldLength * 2, |
475 | 946 | SYMCRYPT_NUMBER_FORMAT_MSB_FIRST, |
476 | 946 | SYMCRYPT_ECPOINT_FORMAT_XY, |
477 | 946 | pCurve->G, |
478 | 946 | SYMCRYPT_FLAG_DATA_PUBLIC, |
479 | 946 | pbScratch, |
480 | 946 | pSizes->cbScratch ); |
481 | 946 | if ( scError != SYMCRYPT_NO_ERROR ) |
482 | 0 | { |
483 | 0 | goto cleanup; |
484 | 0 | } |
485 | 946 | pDst += pSizes->cbEcpoint; |
486 | | |
487 | | // Fill the precomputed table |
488 | 946 | if ( (pParams->type == SYMCRYPT_ECURVE_TYPE_SHORT_WEIERSTRASS) || |
489 | 946 | (pParams->type == SYMCRYPT_ECURVE_TYPE_TWISTED_EDWARDS) ) |
490 | 946 | { |
491 | | // The first point of the table is the generator |
492 | 946 | pCurve->info.sw.poPrecompPoints[0] = pCurve->G; |
493 | | |
494 | 15.1k | for (UINT32 i=1; i<pCurve->info.sw.nPrecompPoints; i++) |
495 | 14.1k | { |
496 | 14.1k | pCurve->info.sw.poPrecompPoints[i] = SymCryptEcpointCreate( pDst, pSizes->cbEcpoint, pCurve ); |
497 | 14.1k | if ( pCurve->info.sw.poPrecompPoints[i] == NULL ) |
498 | 0 | { |
499 | 0 | goto cleanup; |
500 | 0 | } |
501 | 14.1k | pDst += pSizes->cbEcpoint; |
502 | 14.1k | } |
503 | | |
504 | 946 | SymCryptOfflinePrecomputation( pCurve, pbScratch, pSizes->cbScratch ); |
505 | 946 | } |
506 | | |
507 | | // For Montgomery curve, we calculate A = (A + 2) / 4 |
508 | 946 | if (pParams->type == SYMCRYPT_ECURVE_TYPE_MONTGOMERY) |
509 | 0 | { |
510 | 0 | peTemp = SymCryptModElementCreate( pbScratch, pSizes->cbModElement, pCurve->FMod ); |
511 | | |
512 | | // SetValueUint32 requirements: |
513 | | // FMod > 2 since it has more than SYMCRYPT_ECURVE_MIN_BITSIZE_FMOD bits |
514 | 0 | SymCryptModElementSetValueUint32( 2, pCurve->FMod, peTemp, pbScratch + pSizes->cbModElement, pSizes->cbScratch - pSizes->cbModElement ); |
515 | 0 | SymCryptModAdd (pCurve->FMod, pCurve->A, peTemp, pCurve->A, pbScratch + pSizes->cbModElement, pSizes->cbScratch - pSizes->cbModElement ); // A = A + 2; |
516 | 0 | SymCryptModDivPow2( pCurve->FMod, pCurve->A, 2, pCurve->A, pbScratch + pSizes->cbModElement, pSizes->cbScratch - pSizes->cbModElement ); // A = (A + 2) / 4 |
517 | 0 | } |
518 | | |
519 | | // Set the default curve policy for parameters of version 2 |
520 | 946 | if (pParams->version == 2) |
521 | 0 | { |
522 | | // Skip over the seed (if any) |
523 | 0 | pSrc += pParams->cbSeed; |
524 | | |
525 | | // Copy the extension info (it can be unaligned) |
526 | 0 | pcParamsV2Ext = (PCSYMCRYPT_ECURVE_PARAMS_V2_EXTENSION) pSrc; |
527 | 0 | } |
528 | 946 | else |
529 | 946 | { |
530 | | // Set the defaults for version 1 |
531 | 946 | if (pParams->type == SYMCRYPT_ECURVE_TYPE_SHORT_WEIERSTRASS) |
532 | 852 | { |
533 | 852 | pcParamsV2Ext = SymCryptEcurveParamsV2ExtensionShortWeierstrass; |
534 | 852 | } |
535 | 94 | else if ( pParams->type == SYMCRYPT_ECURVE_TYPE_TWISTED_EDWARDS ) |
536 | 94 | { |
537 | 94 | pcParamsV2Ext = SymCryptEcurveParamsV2ExtensionTwistedEdwards; |
538 | 94 | } |
539 | 0 | else if ( pParams->type == SYMCRYPT_ECURVE_TYPE_MONTGOMERY ) |
540 | 0 | { |
541 | 0 | pcParamsV2Ext = SymCryptEcurveParamsV2ExtensionMontgomery; |
542 | 0 | } |
543 | 946 | } |
544 | | |
545 | 946 | pCurve->PrivateKeyDefaultFormat = pcParamsV2Ext->PrivateKeyDefaultFormat; |
546 | 946 | pCurve->HighBitRestrictionNumOfBits = pcParamsV2Ext->HighBitRestrictionNumOfBits; |
547 | 946 | pCurve->HighBitRestrictionPosition = pcParamsV2Ext->HighBitRestrictionPosition; |
548 | 946 | pCurve->HighBitRestrictionValue = pcParamsV2Ext->HighBitRestrictionValue; |
549 | | |
550 | | // Make sure that the HighBitRestrictions make sense |
551 | | // (see SymCryptIntGet/SetBits) |
552 | 946 | if ( (pCurve->HighBitRestrictionNumOfBits>32) || |
553 | 946 | ((pCurve->HighBitRestrictionNumOfBits>0) && |
554 | 946 | (pCurve->HighBitRestrictionPosition + pCurve->HighBitRestrictionNumOfBits > pCurve->GOrdBitsize + pCurve->coFactorPower)) ) |
555 | 0 | { |
556 | 0 | scError = SYMCRYPT_INVALID_ARGUMENT; |
557 | 0 | goto cleanup; |
558 | 0 | } |
559 | | |
560 | | // Setting the magic |
561 | 946 | SYMCRYPT_SET_MAGIC( pCurve ); |
562 | | |
563 | 946 | fSuccess = TRUE; |
564 | | |
565 | 946 | cleanup: |
566 | 946 | if (!fSuccess) |
567 | 0 | { |
568 | 0 | SymCryptWipe( pbCurve, pSizes->cbAlloc ); |
569 | 0 | pCurve = NULL; |
570 | 0 | } |
571 | | |
572 | 946 | return pCurve; |
573 | 946 | } |
574 | | |
575 | | PSYMCRYPT_ECURVE |
576 | | SYMCRYPT_CALL |
577 | | SymCryptEcurveCreate( |
578 | | _In_ PSYMCRYPT_ECURVE_PARAMS pParams, |
579 | | _In_ UINT32 flags, |
580 | | _Out_writes_bytes_( cbCurve ) PBYTE pbCurve, |
581 | | SIZE_T cbCurve, |
582 | | _Out_writes_bytes_( cbScratch ) PBYTE pbScratch, |
583 | | SIZE_T cbScratch) |
584 | 0 | { |
585 | 0 | SYMCRYPT_ECURVE_SIZES sizes; |
586 | |
|
587 | 0 | PSYMCRYPT_ECURVE pCurve = NULL; |
588 | |
|
589 | 0 | if ( !SymCryptEcurveValidateAndComputeSizes(pParams, &sizes) ) |
590 | 0 | { |
591 | 0 | goto cleanup; |
592 | 0 | } |
593 | | |
594 | 0 | if ( cbCurve < sizes.cbAlloc ) |
595 | 0 | { |
596 | 0 | goto cleanup; |
597 | 0 | } |
598 | | |
599 | 0 | if ( cbScratch < sizes.cbScratch ) |
600 | 0 | { |
601 | 0 | goto cleanup; |
602 | 0 | } |
603 | | |
604 | 0 | pCurve = SymCryptEcurveInitialize( pParams, flags, &sizes, pbCurve, pbScratch ); |
605 | |
|
606 | 0 | cleanup: |
607 | 0 | return pCurve; |
608 | 0 | } |
609 | | |
610 | | PSYMCRYPT_ECURVE |
611 | | SYMCRYPT_CALL |
612 | | SymCryptEcurveAllocate( |
613 | | _In_ PCSYMCRYPT_ECURVE_PARAMS pParams, |
614 | | _In_ UINT32 flags ) |
615 | 946 | { |
616 | 946 | SYMCRYPT_ECURVE_SIZES sizes; |
617 | | |
618 | 946 | PBYTE pbCurve = NULL; |
619 | 946 | PBYTE pbScratch = NULL; |
620 | | |
621 | 946 | PSYMCRYPT_ECURVE pCurve = NULL; |
622 | | |
623 | 946 | if ( !SymCryptEcurveValidateAndComputeSizes(pParams, &sizes) ) |
624 | 0 | { |
625 | 0 | goto cleanup; |
626 | 0 | } |
627 | | |
628 | 946 | pbCurve = SymCryptCallbackAlloc( sizes.cbAlloc ); |
629 | 946 | if ( pbCurve == NULL ) |
630 | 0 | { |
631 | 0 | goto cleanup; |
632 | 0 | } |
633 | | |
634 | 946 | pbScratch = SymCryptCallbackAlloc( sizes.cbScratch ); |
635 | 946 | if ( pbScratch == NULL ) |
636 | 0 | { |
637 | 0 | goto cleanup; |
638 | 0 | } |
639 | | |
640 | 946 | pCurve = SymCryptEcurveInitialize( pParams, flags, &sizes, pbCurve, pbScratch ); |
641 | 946 | if ( pCurve != NULL ) |
642 | 946 | { |
643 | 946 | pbCurve = NULL; |
644 | 946 | } |
645 | | |
646 | 946 | cleanup: |
647 | 946 | if ( pbScratch != NULL ) |
648 | 946 | { |
649 | 946 | SymCryptWipe( pbScratch, sizes.cbScratch ); |
650 | 946 | SymCryptCallbackFree( pbScratch ); |
651 | 946 | } |
652 | | |
653 | 946 | if ( pbCurve != NULL ) |
654 | 0 | { |
655 | 0 | SymCryptCallbackFree( pbCurve ); |
656 | 0 | } |
657 | | |
658 | 946 | return pCurve; |
659 | 946 | } |
660 | | |
661 | | VOID |
662 | | SYMCRYPT_CALL |
663 | | SymCryptEcurveFree( _Out_ PSYMCRYPT_ECURVE pCurve ) |
664 | 946 | { |
665 | 946 | SYMCRYPT_CHECK_MAGIC( pCurve ); |
666 | | |
667 | 946 | SymCryptWipe( (PBYTE) pCurve, pCurve->cbAlloc ); |
668 | | |
669 | 946 | SymCryptCallbackFree( pCurve ); |
670 | 946 | } |
671 | | |
672 | | UINT32 |
673 | | SYMCRYPT_CALL |
674 | | SymCryptEcurveBitsizeofFieldModulus( _In_ PCSYMCRYPT_ECURVE pCurve ) |
675 | 0 | { |
676 | 0 | return pCurve->FModBitsize; |
677 | 0 | } |
678 | | |
679 | | UINT32 |
680 | | SYMCRYPT_CALL |
681 | | SymCryptEcurveBitsizeofGroupOrder( _In_ PCSYMCRYPT_ECURVE pCurve ) |
682 | 330 | { |
683 | 330 | return pCurve->GOrdBitsize; |
684 | 330 | } |
685 | | |
686 | | UINT32 |
687 | | SYMCRYPT_CALL |
688 | | SymCryptEcurveDigitsofFieldElement( _In_ PCSYMCRYPT_ECURVE pCurve ) |
689 | 1.17k | { |
690 | 1.17k | return pCurve->FModDigits; |
691 | 1.17k | } |
692 | | |
693 | | UINT32 |
694 | | SYMCRYPT_CALL |
695 | | SymCryptEcurveSizeofFieldElement( _In_ PCSYMCRYPT_ECURVE pCurve ) |
696 | 4.24k | { |
697 | 4.24k | return pCurve->FModBytesize; |
698 | 4.24k | } |
699 | | |
700 | | UINT32 |
701 | | SYMCRYPT_CALL |
702 | | SymCryptEcurveSizeofScalarMultiplier( _In_ PCSYMCRYPT_ECURVE pCurve ) |
703 | 1.41k | { |
704 | 1.41k | return pCurve->GOrdBytesize; |
705 | 1.41k | } |
706 | | |
707 | | PCSYMCRYPT_MODULUS |
708 | | SYMCRYPT_CALL |
709 | | SymCryptEcurveGroupOrder( _In_ PCSYMCRYPT_ECURVE pCurve ) |
710 | 0 | { |
711 | 0 | return pCurve->GOrd; |
712 | 0 | } |
713 | | |
714 | | UINT32 |
715 | | SYMCRYPT_CALL |
716 | | SymCryptEcurveDigitsofScalarMultiplier( _In_ PCSYMCRYPT_ECURVE pCurve ) |
717 | 6.68k | { |
718 | 6.68k | return SymCryptDigitsFromBits( pCurve->GOrdBitsize + pCurve->coFactorPower ); |
719 | 6.68k | } |
720 | | |
721 | | UINT32 |
722 | | SYMCRYPT_CALL |
723 | | SymCryptEcurvePrivateKeyDefaultFormat( _In_ PCSYMCRYPT_ECURVE pCurve ) |
724 | 0 | { |
725 | 0 | return pCurve->PrivateKeyDefaultFormat; |
726 | 0 | } |
727 | | |
728 | | UINT32 |
729 | | SYMCRYPT_CALL |
730 | | SymCryptEcurveHighBitRestrictionNumOfBits( _In_ PCSYMCRYPT_ECURVE pCurve ) |
731 | 0 | { |
732 | 0 | return pCurve->HighBitRestrictionNumOfBits; |
733 | 0 | } |
734 | | |
735 | | UINT32 |
736 | | SYMCRYPT_CALL |
737 | | SymCryptEcurveHighBitRestrictionPosition( _In_ PCSYMCRYPT_ECURVE pCurve ) |
738 | 0 | { |
739 | 0 | return pCurve->HighBitRestrictionPosition; |
740 | 0 | } |
741 | | |
742 | | UINT32 |
743 | | SYMCRYPT_CALL |
744 | | SymCryptEcurveHighBitRestrictionValue( _In_ PCSYMCRYPT_ECURVE pCurve ) |
745 | 0 | { |
746 | 0 | return pCurve->HighBitRestrictionValue; |
747 | 0 | } |
748 | | |
749 | | BOOLEAN |
750 | | SYMCRYPT_CALL |
751 | | SymCryptEcurveIsSame( |
752 | | _In_ PCSYMCRYPT_ECURVE pCurve1, |
753 | | _In_ PCSYMCRYPT_ECURVE pCurve2) |
754 | 3.18M | { |
755 | 3.18M | BOOLEAN fIsSameCurve = FALSE; |
756 | | |
757 | 3.18M | if ( pCurve1 == pCurve2 ) |
758 | 3.18M | { |
759 | 3.18M | fIsSameCurve = TRUE; |
760 | 3.18M | goto cleanup; |
761 | 3.18M | } |
762 | | |
763 | 0 | if ( (pCurve1->type != pCurve2->type) || |
764 | 0 | !SymCryptIntIsEqual ( |
765 | 0 | SymCryptIntFromModulus( pCurve1->FMod ), |
766 | 0 | SymCryptIntFromModulus( pCurve2->FMod ) ) || |
767 | 0 | !SymCryptModElementIsEqual ( pCurve1->FMod, pCurve1->A, pCurve2->A ) || |
768 | 0 | !SymCryptModElementIsEqual ( pCurve1->FMod, pCurve1->B, pCurve2->B ) ) |
769 | 0 | { |
770 | 0 | goto cleanup; |
771 | 0 | } |
772 | | |
773 | 0 | fIsSameCurve = TRUE; |
774 | |
|
775 | 3.18M | cleanup: |
776 | 3.18M | return fIsSameCurve; |
777 | 0 | } |