CoCalc -- ec_short_weierstrass.c

GitHub Repository: wine-mirror/wine
Path: blob/master/libs/symcrypt/lib/ec_short_weierstrass.c
¹⁵⁰¹⁰ views
1
//
2
// ec_short_weierstrass.c   ECPOINT functions for short Weierstrass curves.
3
//
4
// Copyright (c) Microsoft Corporation. Licensed under the MIT license.
5
//
6
//
7

8
#include "precomp.h"
9

10
//
11
// Scratch space requirements for each ECPOINT function.
12
//
13
// A function's requirements in scratch space consist of requirements for its own arithmetic
14
// operations and temporaries ("self" scratch space) and scratch space requirements for other
15
// ECPOINT functions it might call ("callee" scratch space).
16
//
17
// If the outer function does not need the temporaries after calling the inner ECPOINT
18
// function, then the total scratch space can be the maximum of both. Otherwise the scratch
19
// space of the outer function should be the concatenation of the "self" scratch space and
20
// the "callee" scratch space.
21
//
22
// The following table shows the scratch space requirements of each function with appropriate
23
// abbreviations. The calling sequence implies a directed graph that starting from the "leaves"
24
// (functions that do no call others) allows to calculate the total scratch space requirements.
25
//
26
//  #N Function                     Calls Function  Self Temporaries            Self Scratch
27
//   1 SetZero                      -               0                           COM_MOD(FMod)
28
//   2 SetDistinguishedPoint        -               0                           0
29
//   3 IsEqual                      -               4 ModEl                     COM_MOD(FMod)
30
//   4 IsZero                       -               1 ModEl                     COM_MOD(FMod)
31
//   5 OnCurve                      -               2 ModEl                     COM_MOD(FMod)
32
//   6 Double                       1,4,9           2 Ecp                       0
33
//   7 Add                          1,3,4,8,9       2 Ecp                       0
34
//   8 AddDiffNonZero               -               8 ModEl                     COM_MOD(FMod)
35
//   9 Double                       -               6 ModEl                     COM_MOD(FMod)
36
//
37
//  10 SetRandom                    11              0                           COM_MOD(GOrd)
38
//  11 ScalarMul                    4,5,7           1ModEl + (n+2)Ecp + 2Int    COM_MOD(GOrd)
39
//
40
// Since only 4 functions call others and to keep things simple, we will have 2
41
// types of scratch space: "ECURVE_COMMON" and "ECURVE_SCALAR"
42
//
43
// ---- All functions except 10 and 11 will use the "ECURVE_COMMON" scratch space. The size of it
44
//      depends only on parameters of the curve. Schematically it will be:
45
//          |----------COMMON------------------------------------------------------------------|
46
//          |------8 ModEl + 2 Ecpoint----||------COM_MOD(FMod)--------------------------------|
47
//
48
// ---- The SetRandom and ScalarMul have requirements that depend on temporaries for the pre-computation.
49
//      Also they depend on the "self" temporaries after calling the inner functions.
50
//      Therefore, these will require the "ECURVE_SCALAR" scratch space which
51
//      consists of two parts: The self space for the above two functions and the
52
//      common scratch space. These parts SHOULD NOT overlap. Schematically:
53
//
54
//          |--------------SCALAR---------------------------------------------------|
55
//          |----1ModEl + (n+2)Ecp + 2Int--------||---max(COMMON, COM_MOD(GOrd)----|
56

57
// The scratch space sizes are all calculated by the following function.
58
// *** Notice that almost all the curve parameters (exception is the distinguished point)
59
//     must have been initialized before calling this function.
60
VOID
61
SYMCRYPT_CALL
62
SymCryptShortWeierstrassFillScratchSpaces( _In_ PSYMCRYPT_ECURVE pCurve )
63
{
64
    UINT32 nDigits = SymCryptDigitsFromBits( pCurve->FModBitsize );
65

66
    //
67
    // All the scratch space computations are upper bounded by the SizeofXXX bound (2^19) and
68
    // the SCRATCH_BYTES_FOR_XXX bound (2^24) (see symcrypt_internal.h).
69
    //
70
    // One caveat is SymCryptSizeofEcpointFromCurve and SymCryptSizeofEcpointEx which calculate
71
    // the size of EcPoint with 4 coordinates (each one a modelement of max size 2^17). Thus upper
72
    // bounded by 2^20.
73
    //
74
    // Another is the precomp points computation where the nPrecompPoints are up to
75
    // 2^SYMCRYPT_ECURVE_SW_DEF_WINDOW = 2^6 and the nRecodedDigits are equal to the
76
    // GOrd bitsize < 2^20.
77
    //
78
    // Thus cbScratchScalarMulti is upper bounded by 2^6*2^20 + 2*2^20*2^4 ~ 2^26.
79
    //
80

81
    // Common
82
    pCurve->cbScratchCommon =
83
            8 * pCurve->cbModElement +
84
            2 * SymCryptSizeofEcpointFromCurve( pCurve ) +
85
            SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits );
86

87
    // Scalar (Overhead)
88
    pCurve->cbScratchScalar =
89
            pCurve->cbModElement +
90
            2 * SymCryptSizeofEcpointFromCurve( pCurve ) +
91
            2 * SymCryptSizeofIntFromDigits( pCurve->GOrdDigits ) +
92
            SYMCRYPT_MAX( pCurve->cbScratchCommon, SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->GOrdDigits ));
93

94
    // Scalar dependent on precomp points (be careful to align the UINT32 arrays properly)
95
    pCurve->cbScratchScalarMulti =
96
            pCurve->info.sw.nPrecompPoints * SymCryptSizeofEcpointFromCurve( pCurve ) +
97
            ((2*pCurve->info.sw.nRecodedDigits * sizeof(UINT32) + SYMCRYPT_ASYM_ALIGN_VALUE - 1 )/SYMCRYPT_ASYM_ALIGN_VALUE) * SYMCRYPT_ASYM_ALIGN_VALUE;
98

99
    // GetSetValue
100
    pCurve->cbScratchGetSetValue =
101
            SymCryptSizeofEcpointEx( pCurve->cbModElement, SYMCRYPT_ECPOINT_FORMAT_MAX_LENGTH ) +
102
            2 * pCurve->cbModElement +
103
            SYMCRYPT_MAX(    SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ),
104
                    SYMCRYPT_SCRATCH_BYTES_FOR_MODINV( pCurve->FModDigits ) );
105

106
    pCurve->cbScratchGetSetValue = SYMCRYPT_MAX( pCurve->cbScratchGetSetValue, SymCryptSizeofIntFromDigits( nDigits ) );
107

108
    // Eckey
109
    pCurve->cbScratchEckey =
110
            SYMCRYPT_MAX( pCurve->cbModElement + SymCryptSizeofIntFromDigits(SymCryptEcurveDigitsofScalarMultiplier(pCurve)),
111
                SymCryptSizeofEcpointFromCurve( pCurve ) ) +
112
            SYMCRYPT_MAX( pCurve->cbScratchScalar + pCurve->cbScratchScalarMulti, pCurve->cbScratchGetSetValue );
113
}
114

115
//
116
// The following function sets the point to (1:1:0) in Jacobian coordinates.
117
//
118
VOID
119
SYMCRYPT_CALL
120
SymCryptShortWeierstrassSetZero(
121
    _In_    PCSYMCRYPT_ECURVE   pCurve,
122
    _Out_   PSYMCRYPT_ECPOINT   poDst,
123
    _Out_writes_bytes_( cbScratch )
124
            PBYTE               pbScratch,
125
            SIZE_T              cbScratch )
126
{
127
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
128
    PSYMCRYPT_MODELEMENT peTmp = NULL;
129

130
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
131
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
132
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ) );
133

134
    // Getting handle to X
135
    peTmp = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poDst );
136

137
    // Setting the right value (always 1)
138
    SymCryptModElementSetValueUint32( 1, FMod, peTmp, pbScratch, cbScratch );
139

140
    // Getting handle to Y
141
    peTmp = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poDst );
142

143
    // Setting the right value (always 1)
144
    SymCryptModElementSetValueUint32( 1, FMod, peTmp, pbScratch, cbScratch );
145

146
    // Getting handle to Z
147
    peTmp = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poDst );
148

149
    // Setting the right value (always 0)
150
    SymCryptModElementSetValueUint32( 0, pCurve->FMod, peTmp, pbScratch, cbScratch );
151
}
152

153
VOID
154
SYMCRYPT_CALL
155
SymCryptShortWeierstrassSetDistinguished(
156
    _In_    PCSYMCRYPT_ECURVE   pCurve,
157
    _Out_   PSYMCRYPT_ECPOINT   poDst,
158
    _Out_writes_bytes_( cbScratch )
159
            PBYTE               pbScratch,
160
            SIZE_T              cbScratch )
161
{
162
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
163
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
164

165
    UNREFERENCED_PARAMETER( pbScratch );
166
    UNREFERENCED_PARAMETER( cbScratch );
167

168
    SymCryptEcpointCopy( pCurve, pCurve->G, poDst );
169
}
170

171
//
172
// The following function checks if
173
//      - X1*Z2^2 = X2*Z1^2 and Y1*Z2^3 = Y2*Z1^3 (Equal case)
174
//      - X1*Z2^2 = X2*Z1^2 and Y1*Z2^3 = -Y2*Z1^3 (Negative case)
175
//
176
// Remark: The case where Z1 = Z2 = 0 is covered above (the zero point
177
//         is equal to its negative).
178
//
179
UINT32
180
SYMCRYPT_CALL
181
SymCryptShortWeierstrassIsEqual(
182
    _In_    PCSYMCRYPT_ECURVE   pCurve,
183
    _In_    PCSYMCRYPT_ECPOINT  poSrc1,
184
    _In_    PCSYMCRYPT_ECPOINT  poSrc2,
185
            UINT32              flags,
186
    _Out_writes_bytes_( cbScratch )
187
            PBYTE               pbScratch,
188
            SIZE_T              cbScratch )
189
{
190
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
191

192
    PSYMCRYPT_MODELEMENT peX1 = NULL;    // Pointer to X1
193
    PSYMCRYPT_MODELEMENT peY1 = NULL;    // Pointer to Y1
194
    PSYMCRYPT_MODELEMENT peZ1 = NULL;    // Pointer to Z1
195
    PSYMCRYPT_MODELEMENT peX2 = NULL;    // Pointer to X2
196
    PSYMCRYPT_MODELEMENT peY2 = NULL;    // Pointer to Y2
197
    PSYMCRYPT_MODELEMENT peZ2 = NULL;    // Pointer to Z2
198

199
    UINT32  dResX = 0;
200
    UINT32  dResY = 0;
201
    UINT32  dResYN = 0;
202

203
    PSYMCRYPT_MODELEMENT peT[4] = { 0 };  // Temporaries
204

205
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
206
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc1->pCurve) && SymCryptEcurveIsSame(pCurve, poSrc2->pCurve) );
207
    SYMCRYPT_ASSERT( (flags & ~(SYMCRYPT_FLAG_ECPOINT_EQUAL|SYMCRYPT_FLAG_ECPOINT_NEG_EQUAL)) == 0 );
208
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ) + 4 * pCurve->cbModElement );
209

210
    // Creating temporaries
211
    for (UINT32 i=0; i<4; i++)
212
    {
213
        peT[i] = SymCryptModElementCreate(
214
                pbScratch,
215
                pCurve->cbModElement,
216
                FMod );
217

218
        SYMCRYPT_ASSERT( peT[i] != NULL);
219

220
        pbScratch += pCurve->cbModElement;
221
    }
222

223
    // Fixing remaining scratch space size
224
    cbScratch -= 4 * pCurve->cbModElement;
225

226
    // Getting pointers to x and y of the source point
227
    peX1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc1 );
228
    peY1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc1 );
229
    peZ1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc1 );
230
    peX2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc2 );
231
    peY2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc2 );
232
    peZ2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc2 );
233

234
    // Setting the default flag if flags == 0
235
    flags |= ( SYMCRYPT_MASK32_ZERO( flags ) & SYMCRYPT_FLAG_ECPOINT_EQUAL );
236

237
    // Calculation
238
    SymCryptModSquare( FMod, peZ1, peT[0], pbScratch, cbScratch );            // T0 := Z1 * Z1 = Z1^2
239
    SymCryptModSquare( FMod, peZ2, peT[1], pbScratch, cbScratch );            // T1 := Z2 * Z2 = Z2^2
240
    SymCryptModMul( FMod, peX1, peT[1], peT[2], pbScratch, cbScratch );       // T2 := X1 * T1 = X1*Z2^2
241
    SymCryptModMul( FMod, peX2, peT[0], peT[3], pbScratch, cbScratch );       // T3 := X2 * T0 = X2*Z1^2
242

243
    dResX = SymCryptModElementIsEqual( FMod, peT[2], peT[3] );
244

245
    SymCryptModMul( FMod, peZ1, peT[0], peT[0], pbScratch, cbScratch );       // T0 := Z1 * T0 = Z1^3
246
    SymCryptModMul( FMod, peZ2, peT[1], peT[1], pbScratch, cbScratch );       // T1 := Z2 * T1 = Z2^3
247
    SymCryptModMul( FMod, peY1, peT[1], peT[2], pbScratch, cbScratch );       // T2 := Y1 * T1 = Y1*Z2^3
248
    SymCryptModMul( FMod, peY2, peT[0], peT[3], pbScratch, cbScratch );       // T3 := Y2 * T0 = Y2*Z1^3
249

250
    dResY = SymCryptModElementIsEqual( FMod, peT[2], peT[3] );
251

252
    SymCryptModNeg( FMod, peT[3], peT[3], pbScratch, cbScratch );             // T3 := -T3 = -Y2*Z1^3
253

254
    dResYN = SymCryptModElementIsEqual( FMod, peT[2], peT[3] );
255

256
    return (SYMCRYPT_MASK32_NONZERO(flags & SYMCRYPT_FLAG_ECPOINT_EQUAL) & dResX & dResY) |
257
           (SYMCRYPT_MASK32_NONZERO(flags & SYMCRYPT_FLAG_ECPOINT_NEG_EQUAL) & dResX & dResYN);
258
}
259

260
UINT32
261
SYMCRYPT_CALL
262
SymCryptShortWeierstrassIsZero(
263
    _In_    PCSYMCRYPT_ECURVE   pCurve,
264
    _In_    PCSYMCRYPT_ECPOINT  poSrc,
265
    _Out_writes_bytes_( cbScratch )
266
            PBYTE               pbScratch,
267
            SIZE_T              cbScratch )
268
{
269
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
270
    PSYMCRYPT_MODELEMENT peZ = NULL;    // Pointer to Z
271

272
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
273
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc->pCurve) );
274

275
    UNREFERENCED_PARAMETER( pbScratch );
276
    UNREFERENCED_PARAMETER( cbScratch );
277

278
    // Getting pointer to Z of the source point
279
    peZ = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc );
280

281
    // Setting temporary to 0
282
    return SymCryptModElementIsZero( FMod, peZ );
283
}
284

285
//
286
// The following function verifies if the point (X:Y:Z) in Jacobian
287
// coordinates satisfies the equation Y^2 = X^3 + aXZ^4+bZ^6 .
288
//
289
UINT32
290
SYMCRYPT_CALL
291
SymCryptShortWeierstrassOnCurve(
292
    _In_    PCSYMCRYPT_ECURVE   pCurve,
293
    _In_    PCSYMCRYPT_ECPOINT  poSrc,
294
    _Out_writes_bytes_( cbScratch )
295
            PBYTE               pbScratch,
296
            SIZE_T              cbScratch )
297
{
298
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
299

300
    PSYMCRYPT_MODELEMENT peX = NULL;    // Pointer to X
301
    PSYMCRYPT_MODELEMENT peY = NULL;    // Pointer to Y
302
    PSYMCRYPT_MODELEMENT peZ = NULL;    // Pointer to Z
303

304
    PSYMCRYPT_MODELEMENT peT[2] = { 0 }; // Temporaries
305

306
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
307
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc->pCurve) );
308
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ) + 2 * pCurve->cbModElement );
309

310
    // Creating temporaries
311
    for (UINT32 i=0; i<2; i++)
312
    {
313
        peT[i] = SymCryptModElementCreate(
314
                pbScratch,
315
                pCurve->cbModElement,
316
                FMod );
317

318
        SYMCRYPT_ASSERT( peT[i] != NULL);
319

320
        pbScratch += pCurve->cbModElement;
321
    }
322

323
    // Fixing remaining scratch space size
324
    cbScratch -= 2*pCurve->cbModElement;
325

326
    // Getting pointers to coordinates of the source point
327
    peX = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc );
328
    peY = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc );
329
    peZ = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc );
330

331
    // Calculation
332
    SymCryptModSquare( FMod, peZ, peT[0], pbScratch, cbScratch );               // T1 := Z  * Z  = Z^2
333
    SymCryptModSquare( FMod, peT[0], peT[1], pbScratch, cbScratch );            // T2 := T1 * T1 = Z^4
334
    SymCryptModMul( FMod, peT[0], peT[1], peT[0], pbScratch, cbScratch );       // T1 := T1 * T2 = Z^6
335

336
    SymCryptModMul( FMod, peT[0], pCurve->B, peT[0], pbScratch, cbScratch );    // T1 := T1 * b  = bZ^6
337

338
    SymCryptModMul( FMod, peT[1], peX, peT[1], pbScratch, cbScratch );          // T2 := T2 * X  = XZ^4
339
    SymCryptModMul( FMod, peT[1], pCurve->A, peT[1], pbScratch, cbScratch );    // T2 := T2 * a  = aXZ^4
340

341
    SymCryptModAdd( FMod, peT[0], peT[1], peT[1], pbScratch, cbScratch );       // T2 := T1 + T2 = aXZ^4 + bZ^6
342

343
    SymCryptModSquare( FMod, peX, peT[0], pbScratch, cbScratch );               // T1 := X  * X  = X^2
344
    SymCryptModMul( FMod, peT[0], peX, peT[0], pbScratch, cbScratch );          // T1 := T1 * X  = X^3
345
    SymCryptModAdd( FMod, peT[0], peT[1], peT[1], pbScratch, cbScratch );       // T2 := T1 + T2 = X^3 + aXZ^4 + bZ^6
346

347
    SymCryptModSquare( FMod, peY, peT[0], pbScratch, cbScratch );               // T1 := Y  * Y  = Y^2
348

349
    return SymCryptModElementIsEqual( FMod, peT[0], peT[1] );
350
}
351

352
//
353
// based on dbl-2007-bl formula
354
// but tweaked by saml to
355
//   a) remove overeager conversions from modular multiplication to modular squaring which introduce
356
//      more addition/subtraction. With current implementations (based on montgomery reduction),
357
//      the cost of [a square and an add/sub] is greater than the cost of [a multiplication]
358
//   b) share intermediate results of producing 8YYYY. [add/sub] is ~10% of cost of mul, so reducing
359
//      count of these operation has a real impact
360
//
361
//      2Y = 2*Y1
362
//      2YY = 2Y*Y1
363
//      4YY = 2*2YY
364
//      8YYYY = 2YY*4YY
365
//      S = X1*4YY
366
//      XX = X1^2
367
//      ZZ = Z1^2
368
//      ZZZZ = ZZ^2
369
//      M = 3*XX+a*ZZZZ
370
//      T = M^2-2*S
371
//      X3 = T
372
//      Y3 = M*(S-T)-8YYYY
373
//      Z3 = Z1*2Y
374
//
375
// Total cost:
376
//      6 Mul (1 by a)
377
//      4 Sqr
378
//      2 Add
379
//      4 Sub
380
//      3 Dbl
381
//
382
// Special Case:
383
//      If the source point is equal to the identity
384
//      point of the curve (i.e. Z1 = 0 in Jacobian
385
//      coordinates) then the resulting point has
386
//      Z3 = Z1*2Y1 = 0. Thus, this formula is
387
//      complete (it works for all points).
388
//
389
VOID
390
SYMCRYPT_CALL
391
SymCryptShortWeierstrassDouble(
392
    _In_    PCSYMCRYPT_ECURVE   pCurve,
393
    _In_    PCSYMCRYPT_ECPOINT  poSrc,
394
    _Out_   PSYMCRYPT_ECPOINT   poDst,
395
            UINT32              flags,
396
    _Out_writes_bytes_( cbScratch )
397
            PBYTE               pbScratch,
398
            SIZE_T              cbScratch )
399
{
400
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
401
    PSYMCRYPT_MODELEMENT peT[3] = { 0 };    // Temporaries
402

403
    PCSYMCRYPT_MODELEMENT peX1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc );
404
    PCSYMCRYPT_MODELEMENT peY1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc );
405
    PCSYMCRYPT_MODELEMENT peZ1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc );
406

407
    PSYMCRYPT_MODELEMENT  peX3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poDst );
408
    PSYMCRYPT_MODELEMENT  peY3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poDst );
409
    PSYMCRYPT_MODELEMENT  peZ3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poDst );
410

411
    SYMCRYPT_ASSERT( pCurve->type == SYMCRYPT_INTERNAL_ECURVE_TYPE_SHORT_WEIERSTRASS );
412
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc->pCurve) && SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
413
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ) + 3 * pCurve->cbModElement );
414

415
    UNREFERENCED_PARAMETER( flags );
416

417
    // Creating temporaries
418
    for (UINT32 i=0; i<3; i++)
419
    {
420
        peT[i] = SymCryptModElementCreate(
421
                pbScratch,
422
                pCurve->cbModElement,
423
                FMod );
424

425
        SYMCRYPT_ASSERT( peT[i] != NULL);
426

427
        pbScratch += pCurve->cbModElement;
428
    }
429

430
    // Fixing remaining scratch space size
431
    cbScratch -= 3*pCurve->cbModElement;
432

433
    // Calculate the points
434
    SymCryptModAdd( FMod, peY1, peY1, peT[0], pbScratch, cbScratch );           /* T0 := Y1 + Y1 = 2Y */
435
    SymCryptModSquare( FMod, peZ1, peT[1], pbScratch, cbScratch );              /* T1 := Z1 * Z1 = ZZ */
436
    SymCryptModMul( FMod, peT[0], peZ1, peZ3, pbScratch, cbScratch );           /* Z3 := 2Y * Z1 = 2YZ */
437

438
    SymCryptModMul( FMod, peY1, peT[0], peY3, pbScratch, cbScratch );           /* Y3 := 2Y * Y1 = 2YY */
439
    SymCryptModAdd( FMod, peY3, peY3, peT[0], pbScratch, cbScratch );           /* T0 := 2YY + 2YY = 4YY */
440
    SymCryptModMul( FMod, peT[0], peY3, peY3, pbScratch, cbScratch );           /* Y3 := 2YY * 4YY = 8YYYY */
441

442
    SymCryptModMul( FMod, peT[0], peX1, peT[0], pbScratch, cbScratch );         /* T0 := X1 * 4YY = 4XYY = S */
443

444
    SymCryptModSquare( FMod, peT[1], peT[1], pbScratch, cbScratch );            /* T1 := T1 * T1 = ZZZZ */
445
    SymCryptModSquare( FMod, peX1, peT[2], pbScratch, cbScratch );              /* T2 := X1 * X1 = XX */
446
    SymCryptModMul( FMod, peT[1], pCurve->A, peT[1], pbScratch, cbScratch );    /* T1 := T1 * a  = a*ZZZZ */
447
    SymCryptModAdd( FMod, peT[2], peT[1], peT[1], pbScratch, cbScratch );       /* T1 := T2 + T1 = XX + a*ZZZZ */
448
    SymCryptModAdd( FMod, peT[2], peT[2], peT[2], pbScratch, cbScratch );       /* T2 := T2 + T2 = 2*XX */
449
    SymCryptModAdd( FMod, peT[0], peT[0], peX3, pbScratch, cbScratch );         /* X3 := 2*S */
450
    SymCryptModAdd( FMod, peT[2], peT[1], peT[1], pbScratch, cbScratch );       /* T1 := T2 + T1 = 3*XX + a*ZZZZ = M */
451

452
    SymCryptModSquare( FMod, peT[1], peT[2], pbScratch, cbScratch );            /* T2 := M^2 */
453
    SymCryptModSub( FMod, peT[2], peX3, peX3, pbScratch, cbScratch );           /* X3 := M^2 - 2*S = T */
454

455
    SymCryptModSub( FMod, peT[0], peX3, peT[0], pbScratch, cbScratch );         /* T0 := S - T */
456
    SymCryptModMul( FMod, peT[1], peT[0], peT[0], pbScratch, cbScratch );       /* T0 := M * (S - T) */
457
    SymCryptModSub( FMod, peT[0], peY3, peY3, pbScratch, cbScratch );           /* Y3 := M * (S - T) - 8*YYYY */
458
}
459

460

461
//
462
// based on dbl-2007-bl / dbl-2001-b formulae
463
// but tweaked by saml to
464
//   a) remove overeager conversions from modular multiplication to modular squaring which introduce
465
//      more addition/subtraction. With current implementations (based on montgomery reduction),
466
//      the cost of [a square and an add/sub] is greater than the cost of [a multiplication]
467
//   b) share intermediate results of producing 8YYYY. [add/sub] is ~10% of cost of mul, so reducing
468
//      count of these operation has a real impact
469
//   c) make use of knowledge that curve has a == -3, so M can be calculated more efficiently
470
//
471
//      2Y = 2*Y1
472
//      2YY = 2Y*Y1
473
//      4YY = 2*2YY
474
//      8YYYY = 2YY*4YY
475
//      ZZ = Z1^2
476
//      S = X1*4YY
477
//      M = 3*(X1+ZZ)*(X1-ZZ) = 3*(XX - ZZZZ)
478
//      T = M^2-2*S
479
//      X3 = T
480
//      Y3 = M*(S-T)-8YYYY
481
//      Z3 = 2Y*Z1
482
//
483
// Total cost:
484
//      6 Mul
485
//      2 Sqr
486
//      2 Add
487
//      4 Sub
488
//      4 Dbl
489
//
490
// Special Case:
491
//      If the source point is equal to the identity
492
//      point of the curve (i.e. Z1 = 0 in Jacobian
493
//      coordinates) then the resulting point has
494
//      Z3 = Z1*2Y1 = 0. Thus, this formula is
495
//      complete (it works for all points).
496
//
497
VOID
498
SYMCRYPT_CALL
499
SymCryptShortWeierstrassDoubleSpecializedAm3(
500
    _In_    PCSYMCRYPT_ECURVE   pCurve,
501
    _In_    PCSYMCRYPT_ECPOINT  poSrc,
502
    _Out_   PSYMCRYPT_ECPOINT   poDst,
503
            UINT32              flags,
504
    _Out_writes_bytes_( cbScratch )
505
            PBYTE               pbScratch,
506
            SIZE_T              cbScratch )
507
{
508
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
509
    PSYMCRYPT_MODELEMENT peT[3] = { 0 };    // Temporaries
510

511
    PCSYMCRYPT_MODELEMENT peX1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc );
512
    PCSYMCRYPT_MODELEMENT peY1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc );
513
    PCSYMCRYPT_MODELEMENT peZ1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc );
514

515
    PSYMCRYPT_MODELEMENT  peX3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poDst );
516
    PSYMCRYPT_MODELEMENT  peY3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poDst );
517
    PSYMCRYPT_MODELEMENT  peZ3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poDst );
518

519
    SYMCRYPT_ASSERT( pCurve->type == SYMCRYPT_INTERNAL_ECURVE_TYPE_SHORT_WEIERSTRASS_AM3 );
520
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc->pCurve) && SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
521
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ) + 3 * pCurve->cbModElement );
522

523
    UNREFERENCED_PARAMETER( flags );
524

525
    // Creating temporaries
526
    for (UINT32 i=0; i<3; i++)
527
    {
528
        peT[i] = SymCryptModElementCreate(
529
                pbScratch,
530
                pCurve->cbModElement,
531
                FMod );
532

533
        SYMCRYPT_ASSERT( peT[i] != NULL);
534

535
        pbScratch += pCurve->cbModElement;
536
    }
537

538
    // Fixing remaining scratch space size
539
    cbScratch -= 3*pCurve->cbModElement;
540

541
    // Calculate the points
542
    SymCryptModAdd( FMod, peY1, peY1, peT[0], pbScratch, cbScratch );       /* T0 := Y1 + Y1 = 2Y */
543
    SymCryptModSquare( FMod, peZ1, peT[1], pbScratch, cbScratch );          /* T1 := Z1 * Z1 = ZZ */
544
    SymCryptModMul( FMod, peY1, peT[0], peY3, pbScratch, cbScratch );       /* Y3 := 2Y * Y1 = 2YY */
545

546
    SymCryptModMul( FMod, peT[0], peZ1, peZ3, pbScratch, cbScratch );       /* Z3 := 2Y * Z1 = 2YZ */
547

548
    SymCryptModAdd( FMod, peY3, peY3, peT[0], pbScratch, cbScratch );       /* T0 := 2YY + 2YY = 4YY */
549
    SymCryptModAdd( FMod, peX1, peT[1], peT[2], pbScratch, cbScratch );     /* T2 := X1 + ZZ */
550
    SymCryptModMul( FMod, peT[0], peY3, peY3, pbScratch, cbScratch );       /* Y3 := 2YY * 4YY = 8YYYY */
551

552
    SymCryptModSub( FMod, peX1, peT[1], peT[1], pbScratch, cbScratch );     /* T1 := X1 - ZZ */
553
    SymCryptModMul( FMod, peT[0], peX1, peT[0], pbScratch, cbScratch );     /* T0 := X1 * 4YY = 4XYY = S */
554

555
    SymCryptModMul( FMod, peT[2], peT[1], peT[2], pbScratch, cbScratch );   /* T2 := (X1 + ZZ)*(X1 - ZZ) = XX - ZZZZ */
556
    SymCryptModAdd( FMod, peT[2], peT[2], peT[1], pbScratch, cbScratch );   /* T1 := 2*(XX - ZZZZ) */
557
    SymCryptModAdd( FMod, peT[0], peT[0], peX3, pbScratch, cbScratch );     /* X3 := 2*S */
558
    SymCryptModAdd( FMod, peT[1], peT[2], peT[1], pbScratch, cbScratch );   /* T1 := 3*(XX - ZZZZ) = M */
559

560
    SymCryptModSquare( FMod, peT[1], peT[2], pbScratch, cbScratch );        /* T2 := M^2 */
561
    SymCryptModSub( FMod, peT[2], peX3, peX3, pbScratch, cbScratch );       /* X3 := M^2 - 2*S = T */
562

563
    SymCryptModSub( FMod, peT[0], peX3, peT[0], pbScratch, cbScratch );     /* T0 := S - T */
564
    SymCryptModMul( FMod, peT[1], peT[0], peT[0], pbScratch, cbScratch );   /* T0 := M * (S - T) */
565
    SymCryptModSub( FMod, peT[0], peY3, peY3, pbScratch, cbScratch );       /* Y3 := M * (S - T) - 8*YYYY */
566
}
567

568
//
569
// based on add-2007-bl formula
570
// but tweaked by saml to
571
//      remove overeager conversions from modular multiplication to modular squaring which introduce
572
//      more addition/subtraction.
573
//
574
//      Z1Z1 = Z1^2
575
//      Z2Z2 = Z2^2
576
//      U1 = X1*Z2Z2
577
//      U2 = X2*Z1Z1
578
//      S1 = Y1*Z2*Z2Z2
579
//      S2 = Y2*Z1*Z1Z1
580
//      H = U2-U1
581
//      2H = 2*H
582
//      I = (2H)^2
583
//      J = H*I
584
//      r = 2*(S2-S1)
585
//      V = U1*I
586
//      X3 = r^2-J-2*V
587
//      Y3 = r*(V-X3)-2*S1*J
588
//      Z3 = (Z1*Z2)*2H
589
//
590
// Total cost:
591
//     12 Mul
592
//      4 Sqr
593
//      0 Add
594
//      7 Sub
595
//      3 Dbl
596
//
597
// Special Case:
598
//      If the two source points are opposite (X1 / Z1^2 == X2 / Z2^2),
599
//      then H = U2-U1 = 0. Thus Z3 = 0 and the result is correct.
600
//
601
VOID
602
SYMCRYPT_CALL
603
SymCryptShortWeierstrassAddDiffNonZero(
604
    _In_    PCSYMCRYPT_ECURVE   pCurve,
605
    _In_    PCSYMCRYPT_ECPOINT  poSrc1,
606
    _In_    PCSYMCRYPT_ECPOINT  poSrc2,
607
    _Out_   PSYMCRYPT_ECPOINT   poDst,
608
    _Out_writes_bytes_( cbScratch )
609
            PBYTE               pbScratch,
610
            SIZE_T              cbScratch )
611
{
612
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
613

614
    PCSYMCRYPT_MODELEMENT peX1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc1 );
615
    PCSYMCRYPT_MODELEMENT peY1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc1 );
616
    PCSYMCRYPT_MODELEMENT peZ1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc1 );
617

618
    PCSYMCRYPT_MODELEMENT peX2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc2 );
619
    PCSYMCRYPT_MODELEMENT peY2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc2 );
620
    PCSYMCRYPT_MODELEMENT peZ2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc2 );
621

622
    PSYMCRYPT_MODELEMENT  peX3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poDst );
623
    PSYMCRYPT_MODELEMENT  peY3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poDst );
624
    PSYMCRYPT_MODELEMENT  peZ3 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poDst );
625

626
    PSYMCRYPT_MODELEMENT peT[7] = { 0 };  // Temporaries
627

628
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
629
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc1->pCurve) && SymCryptEcurveIsSame(pCurve, poSrc2->pCurve) && SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
630
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ) + 7 * pCurve->cbModElement );
631

632
    // Creating temporaries
633
    for (UINT32 i=0; i<7; i++)
634
    {
635
        peT[i] = SymCryptModElementCreate(
636
                pbScratch,
637
                pCurve->cbModElement,
638
                FMod );
639

640
        SYMCRYPT_ASSERT( peT[i] != NULL);
641

642
        pbScratch += pCurve->cbModElement;
643
    }
644

645
    // Fixing remaining scratch space size
646
    cbScratch -= 7*pCurve->cbModElement;
647

648
    // Calculation
649

650
    SymCryptModSquare( FMod, peZ1, peT[0], pbScratch, cbScratch );          /* T0 := Z1 * Z1 = Z1Z1 */
651
    SymCryptModMul( FMod, peZ1, peT[0], peT[1], pbScratch, cbScratch );     /* T1 := Z1*Z1Z1 */
652

653
    SymCryptModSquare( FMod, peZ2, peT[6], pbScratch, cbScratch );          /* T6 := Z2 * Z2 = Z2Z2 */
654
    SymCryptModMul( FMod, peX1, peT[6], peT[2], pbScratch, cbScratch );     /* T2 := X1 * T6 = X1*Z2Z2 = U1 */
655
    SymCryptModMul( FMod, peX2, peT[0], peT[3], pbScratch, cbScratch );     /* T3 := X2 * Z1Z1 = U2 */
656
    SymCryptModSub( FMod, peT[3], peT[2], peT[5], pbScratch, cbScratch );   /* T5 := T3 - T2 = U2 - U1 = H */
657
    SymCryptModAdd( FMod, peT[5], peT[5], peT[3], pbScratch, cbScratch );   /* T3 := T5 + T5 = 2H */
658

659
    SymCryptModMul( FMod, peZ1, peZ2, peT[4], pbScratch, cbScratch );       /* T4 := Z1 * Z2 */
660

661
    SymCryptModMul( FMod, peZ2, peT[6], peT[6], pbScratch, cbScratch );     /* T6 := Z2 * T6 = Z2*Z2Z2 */
662
    SymCryptModMul( FMod, peT[4], peT[3], peZ3, pbScratch, cbScratch );     /* Z3 := T4 * T3 = Z1*Z2*2H */
663

664
    SymCryptModMul( FMod, peY1, peT[6], peT[6], pbScratch, cbScratch );     /* T6 := Y1 * T6 = Y1*Z2*Z2Z2 = S1 */
665
    SymCryptModMul( FMod, peY2, peT[1], peT[4], pbScratch, cbScratch );     /* T4 := Y2*Z1*Z1Z1 = S2 */
666
    SymCryptModSub( FMod, peT[4], peT[6], peT[4], pbScratch, cbScratch );   /* T4 := T4 - T6 = S2-S1 */
667
    SymCryptModAdd( FMod, peT[4], peT[4], peT[4], pbScratch, cbScratch );   /* T4 := T4 + T4 = 2*(S2-S1) = r */
668

669
    SymCryptModSquare( FMod, peT[3], peT[3], pbScratch, cbScratch );        /* T3 := T3 * T3 = (2*H)^2 = I */
670
    SymCryptModMul( FMod, peT[3], peT[5], peT[5], pbScratch, cbScratch );   /* T5 := T3 * T5 = H*I = J */
671
    SymCryptModMul( FMod, peT[2], peT[3], peT[3], pbScratch, cbScratch );   /* T3 := T2 * T3 = U1*I = V */
672

673
    SymCryptModSquare( FMod, peT[4], peT[2], pbScratch, cbScratch );        /* T2 := T4 * T4 = r^2 */
674
    SymCryptModSub( FMod, peT[2], peT[5], peT[2], pbScratch, cbScratch );   /* T2 := T2 - T5 = r^2 - J */
675
    SymCryptModSub( FMod, peT[2], peT[3], peT[2], pbScratch, cbScratch );   /* T2 := T2 - T3 = r^2 - J - V */
676
    SymCryptModSub( FMod, peT[2], peT[3], peX3, pbScratch, cbScratch );     /* T2 := T2 - T3 = r^2 - J - 2*V = X3 */
677

678
    SymCryptModSub( FMod, peT[3], peX3, peT[3], pbScratch, cbScratch );     /* T3 := T3 - T2 = V - X3 */
679
    SymCryptModMul( FMod, peT[3], peT[4], peT[3], pbScratch, cbScratch );   /* T3 := T3 * T4 = r*(V-X3) */
680
    SymCryptModMul( FMod, peT[6], peT[5], peT[6], pbScratch, cbScratch );   /* T6 := T6 * T5 = S1*J */
681
    SymCryptModAdd( FMod, peT[6], peT[6], peT[6], pbScratch, cbScratch );   /* T6 := T6 + T6 = 2*S1*J */
682
    SymCryptModSub( FMod, peT[3], peT[6], peY3, pbScratch, cbScratch );     /* Y3 := T6 - T3 = r*(V-X3) - 2*S1*J */
683
}
684

685
//
686
// The following function is a complete **SIDE-CHANNEL-UNSAFE**
687
// addition of points that detects as fast as possible the special cases
688
// and merges the two previous calls.
689
//
690
VOID
691
SYMCRYPT_CALL
692
SymCryptShortWeierstrassAddSideChannelUnsafe(
693
    _In_    PCSYMCRYPT_ECURVE   pCurve,
694
    _In_    PCSYMCRYPT_ECPOINT  poSrc1,
695
    _In_    PCSYMCRYPT_ECPOINT  poSrc2,
696
    _Out_   PSYMCRYPT_ECPOINT   poDst,
697
    _Out_writes_bytes_( cbScratch )
698
            PBYTE               pbScratch,
699
            SIZE_T              cbScratch )
700
{
701
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
702

703
    PCSYMCRYPT_MODELEMENT peX1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc1 );
704
    PCSYMCRYPT_MODELEMENT peY1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc1 );
705
    PCSYMCRYPT_MODELEMENT peZ1 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc1 );
706

707
    PCSYMCRYPT_MODELEMENT peX2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poSrc2 );
708
    PCSYMCRYPT_MODELEMENT peY2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc2 );
709
    PCSYMCRYPT_MODELEMENT peZ2 = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poSrc2 );
710

711
    PSYMCRYPT_MODELEMENT peT[8] = { 0 };  // Temporaries
712

713
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
714
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc1->pCurve) && SymCryptEcurveIsSame(pCurve, poSrc2->pCurve) && SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
715
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ) + 8 * pCurve->cbModElement );
716

717
    // Check if one of the points is zero
718
    if (SymCryptModElementIsZero( FMod, peZ1 ))
719
    {
720
        SymCryptEcpointCopy( pCurve, poSrc2, poDst);
721
        return;
722
    }
723

724
    if (SymCryptModElementIsZero( FMod, peZ2 ))
725
    {
726
        SymCryptEcpointCopy( pCurve, poSrc1, poDst);
727
        return;
728
    }
729

730
    // Creating temporaries
731
    for (UINT32 i=0; i<8; i++)
732
    {
733
        peT[i] = SymCryptModElementCreate(
734
                pbScratch,
735
                pCurve->cbModElement,
736
                FMod );
737

738
        SYMCRYPT_ASSERT( peT[i] != NULL);
739

740
        pbScratch += pCurve->cbModElement;
741
    }
742

743
    // Fixing remaining scratch space size
744
    cbScratch -= 8*pCurve->cbModElement;
745

746
    // Calculation
747

748
    SymCryptModSquare( FMod, peZ1, peT[0], pbScratch, cbScratch );          /* T0 := Z1 * Z1 = Z1Z1 */
749
    SymCryptModMul( FMod, peZ1, peT[0], peT[1], pbScratch, cbScratch );     /* T1 := Z1*Z1Z1 */
750

751
    SymCryptModSquare( FMod, peZ2, peT[6], pbScratch, cbScratch );          /* T6 := Z2 * Z2 = Z2Z2 */
752
    SymCryptModMul( FMod, peX1, peT[6], peT[2], pbScratch, cbScratch );     /* T2 := X1 * T6 = X1*Z2Z2 = U1 */
753
    SymCryptModMul( FMod, peX2, peT[0], peT[3], pbScratch, cbScratch );     /* T3 := X2 * Z1Z1 = U2 */
754
    SymCryptModSub( FMod, peT[3], peT[2], peT[5], pbScratch, cbScratch );   /* T5 := T3 - T2 = U2 - U1 = H */
755

756
    SymCryptModMul( FMod, peY2, peT[1], peT[7], pbScratch, cbScratch );     /* T7 := Y2 * T1 = Y2*Z1*Z1Z1 = S2 */
757
    SymCryptModMul( FMod, peZ2, peT[6], peT[1], pbScratch, cbScratch );     /* T1 := Z2 * T6 = Z2*Z2Z2 */
758
    SymCryptModMul( FMod, peY1, peT[1], peT[1], pbScratch, cbScratch );     /* T1 := Y1 * T1 = Y1*Z2*Z2Z2 = S1 */
759
    SymCryptModSub( FMod, peT[7], peT[1], peT[7], pbScratch, cbScratch );   /* T7 := T7 - T1 = S2-S1 */
760

761
    if (SymCryptModElementIsZero( FMod, peT[5] ) & SymCryptModElementIsZero( FMod, peT[7] ))
762
    {
763
        // Points are equal - run double on poSrc1
764

765
        SymCryptModElementCopy( FMod, peT[0], peT[4] );                             /* Move Z1Z1 for later */
766

767
        SymCryptModSquare( FMod, peX1, peT[0], pbScratch, cbScratch );              /* T0 := X1 * X1 = XX */
768
        SymCryptModSquare( FMod, peY1, peT[3], pbScratch, cbScratch );              /* T3 := Y1 * Y1 = YY */
769
        SymCryptModSquare( FMod, peT[3], peT[5], pbScratch, cbScratch );            /* T5 := T3 * T3 = YYYY */
770

771
        SymCryptModAdd( FMod, peX1, peT[3], peT[1], pbScratch, cbScratch );         /* T1 := X1 + T3 = X + YY */
772
        SymCryptModSquare( FMod, peT[1], peT[1], pbScratch, cbScratch );            /* T1 := T1 * T1 = (X + YY)^2 */
773
        SymCryptModSub( FMod, peT[1], peT[0], peT[1], pbScratch, cbScratch );       /* T1 := T1 - T0 = (X + YY)^2 - XX */
774
        SymCryptModSub( FMod, peT[1], peT[5], peT[1], pbScratch, cbScratch );       /* T1 := T1 - T5 = (X + YY)^2 - XX - YYYY */
775
        SymCryptModAdd( FMod, peT[1], peT[1], peT[1], pbScratch, cbScratch );       /* T1 := T1 + T1 = 2*((X + YY)^2 - XX - YYYY) = S */
776

777
        //SymCryptModSquare( FMod, peZ1, peT[4], pbScratch, cbScratch );              /* T4 := Z1 * Z1 = ZZ */
778

779
        SymCryptModSquare( FMod, peT[4], peT[2], pbScratch, cbScratch );            /* T2 := T4 * T4 = ZZ^2 */
780
        SymCryptModMul( FMod, peT[2], pCurve->A, peT[2], pbScratch, cbScratch );    /* T2 := T2 * a  = a*ZZ^2 */
781
        SymCryptModAdd( FMod, peT[2], peT[0], peT[2], pbScratch, cbScratch );       /* T2 := T2 + T0 = XX + a*ZZ^2 */
782
        SymCryptModAdd( FMod, peT[0], peT[0], peT[0], pbScratch, cbScratch );       /* T0 := T0 + T0 = 2*XX */
783
        SymCryptModAdd( FMod, peT[2], peT[0], peT[2], pbScratch, cbScratch );       /* T2 := T2 + T0 = 3*XX + a*ZZ^2 = M */
784

785
        SymCryptModSquare( FMod, peT[2], peT[0], pbScratch, cbScratch );            /* T0 := T2 * T2 = M^2 */
786
        SymCryptModSub( FMod, peT[0], peT[1], peT[0], pbScratch, cbScratch );       /* T0 := T0 - T1 = M^2 - S */
787
        SymCryptModSub( FMod, peT[0], peT[1], peT[0], pbScratch, cbScratch );       /* T0 := T0 - T1 = M^2 - 2*S = T = X3 */
788

789
        SymCryptModSub( FMod, peT[1], peT[0], peT[1], pbScratch, cbScratch );       /* T1 := T1 - T0 = S - T */
790
        SymCryptModMul( FMod, peT[2], peT[1], peT[1], pbScratch, cbScratch );       /* T1 := T2 * T1 = M * (S - T) */
791
        SymCryptModAdd( FMod, peT[5], peT[5], peT[5], pbScratch, cbScratch );       /* T5 := T5 + T5 = 2*YYYY */
792
        SymCryptModAdd( FMod, peT[5], peT[5], peT[5], pbScratch, cbScratch );       /* T5 := T5 + T5 = 4*YYYY */
793
        SymCryptModAdd( FMod, peT[5], peT[5], peT[5], pbScratch, cbScratch );       /* T5 := T5 + T5 = 8*YYYY */
794
        SymCryptModSub( FMod, peT[1], peT[5], peT[1], pbScratch, cbScratch );       /* T1 := T1 - T5 = M * (S - T) - 8*YYYY = Y3 */
795

796
        SymCryptModAdd( FMod, peY1, peZ1, peT[2], pbScratch, cbScratch );           /* T2 := Y1 + Z1 */
797
        SymCryptModSquare( FMod, peT[2], peT[2], pbScratch, cbScratch );            /* T2 := T2 * T2 = (Y + Z )^2 */
798
        SymCryptModSub( FMod, peT[2], peT[3], peT[2], pbScratch, cbScratch );       /* T2 := T2 - T3 = (Y + Z )^2 - YY */
799
        SymCryptModSub( FMod, peT[2], peT[4], peT[2], pbScratch, cbScratch );       /* T2 := T2 - T4 = (Y + Z )^2 - YY - ZZ = Z3 */
800

801
        // Setting the result
802
        SymCryptModElementCopy( FMod, peT[0], SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poDst ) );
803
        SymCryptModElementCopy( FMod, peT[1], SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poDst ) );
804
        SymCryptModElementCopy( FMod, peT[2], SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poDst ) );
805
    }
806
    else
807
    {
808
        // Continue the addition
809

810
        SymCryptModAdd( FMod, peZ1, peZ2, peT[4], pbScratch, cbScratch );       /* T4 := Z1 + Z2 */
811
        SymCryptModSquare( FMod, peT[4], peT[4], pbScratch, cbScratch );        /* T4 := T4 * T4 = (Z1 + Z2)^2 */
812
        SymCryptModSub( FMod, peT[4], peT[0], peT[4], pbScratch, cbScratch );   /* T4 := T4 - Z1Z1 = (Z1 + Z2)^2 - Z1Z1 */
813
        SymCryptModSub( FMod, peT[4], peT[6], peT[4], pbScratch, cbScratch );   /* T4 := T4 - T6 = (Z1 + Z2)^2 - Z1Z1 - Z2Z2 */
814
        SymCryptModMul( FMod, peT[4], peT[5], peT[4], pbScratch, cbScratch );   /* T4 := T4 * T5 = ((Z1 + Z2)^2 - Z1Z1 - Z2Z2)*H = Z3 */
815

816
        SymCryptModAdd( FMod, peT[7], peT[7], peT[7], pbScratch, cbScratch );   /* T7 := T7 + T7 = 2*(S2-S1) = r */
817

818
        SymCryptModAdd( FMod, peT[5], peT[5], peT[3], pbScratch, cbScratch );   /* T3 := T5 + T5 = 2*H */
819
        SymCryptModSquare( FMod, peT[3], peT[3], pbScratch, cbScratch );        /* T3 := T3 * T3 = (2*H)^2 = I */
820
        SymCryptModMul( FMod, peT[3], peT[5], peT[5], pbScratch, cbScratch );   /* T5 := T3 * T5 = H*I = J */
821
        SymCryptModMul( FMod, peT[2], peT[3], peT[3], pbScratch, cbScratch );   /* T3 := T2 * T3 = U1*I = V */
822

823
        SymCryptModSquare( FMod, peT[7], peT[2], pbScratch, cbScratch );        /* T2 := T7 * T7 = r^2 */
824
        SymCryptModSub( FMod, peT[2], peT[5], peT[2], pbScratch, cbScratch );   /* T2 := T2 - T5 = r^2 - J */
825
        SymCryptModSub( FMod, peT[2], peT[3], peT[2], pbScratch, cbScratch );   /* T2 := T2 - T3 = r^2 - J - V */
826
        SymCryptModSub( FMod, peT[2], peT[3], peT[2], pbScratch, cbScratch );   /* T2 := T2 - T3 = r^2 - J - 2*V = X3 */
827

828
        SymCryptModSub( FMod, peT[3], peT[2], peT[3], pbScratch, cbScratch );   /* T3 := T3 - T2 = V - X3 */
829
        SymCryptModMul( FMod, peT[3], peT[7], peT[3], pbScratch, cbScratch );   /* T3 := T3 * T7 = r*(V-X3) */
830
        SymCryptModMul( FMod, peT[1], peT[5], peT[6], pbScratch, cbScratch );   /* T6 := T1 * T5 = S1*J */
831
        SymCryptModAdd( FMod, peT[6], peT[6], peT[6], pbScratch, cbScratch );   /* T6 := T6 + T6 = 2*S1*J */
832
        SymCryptModSub( FMod, peT[3], peT[6], peT[3], pbScratch, cbScratch );   /* T3 := T6 - T3 = r*(V-X3) - 2*S1*J = Y3 */
833

834
        // Setting the result
835
        SymCryptModElementCopy( FMod, peT[2], SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 0, pCurve, poDst ) );
836
        SymCryptModElementCopy( FMod, peT[3], SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poDst ) );
837
        SymCryptModElementCopy( FMod, peT[4], SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 2, pCurve, poDst ) );
838
    }
839
}
840

841
VOID
842
SYMCRYPT_CALL
843
SymCryptShortWeierstrassAdd(
844
    _In_    PCSYMCRYPT_ECURVE   pCurve,
845
    _In_    PCSYMCRYPT_ECPOINT  poSrc1,
846
    _In_    PCSYMCRYPT_ECPOINT  poSrc2,
847
    _Out_   PSYMCRYPT_ECPOINT   poDst,
848
            UINT32              flags,
849
    _Out_writes_bytes_( cbScratch )
850
            PBYTE               pbScratch,
851
            SIZE_T              cbScratch )
852
{
853
    UINT32 dSrc1Zero = 0;
854
    UINT32 dSrc2Zero = 0;
855
    UINT32 dSrcEqual = 0;
856

857
    // Temporary points
858
    PSYMCRYPT_ECPOINT   poQ0 = NULL;
859
    PSYMCRYPT_ECPOINT   poQ1 = NULL;
860

861
    SIZE_T cbEcpoint = SymCryptSizeofEcpointFromCurve( pCurve );
862

863
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
864
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc1->pCurve) && SymCryptEcurveIsSame(pCurve, poSrc2->pCurve) && SymCryptEcurveIsSame(pCurve, poDst->pCurve) );
865
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_INTERNAL_SCRATCH_BYTES_FOR_COMMON_ECURVE_OPERATIONS( pCurve ) );     // We will need the entire scratch space
866

867
    SYMCRYPT_ASSERT( cbScratch > 2*cbEcpoint );
868

869
    if ((flags & SYMCRYPT_FLAG_DATA_PUBLIC) != 0)
870
    {
871
        SymCryptShortWeierstrassAddSideChannelUnsafe( pCurve, poSrc1, poSrc2, poDst, pbScratch, cbScratch );
872
    }
873
    else
874
    {
875
        // Creating temporary points
876
        poQ0 = SymCryptEcpointCreate( pbScratch, cbEcpoint, pCurve );
877
        SYMCRYPT_ASSERT( poQ0 != NULL);
878
        pbScratch += cbEcpoint;
879

880
        poQ1 = SymCryptEcpointCreate( pbScratch, cbEcpoint, pCurve );
881
        SYMCRYPT_ASSERT( poQ1 != NULL);
882
        pbScratch += cbEcpoint;
883

884
        // Fixing remaining scratch space size
885
        cbScratch -= 2*cbEcpoint;
886

887
        // Calculate the masks
888
        dSrc1Zero = SymCryptShortWeierstrassIsZero( pCurve, poSrc1, pbScratch, cbScratch );
889
        dSrc2Zero = SymCryptShortWeierstrassIsZero( pCurve, poSrc2, pbScratch, cbScratch );
890
        dSrcEqual = SymCryptShortWeierstrassIsEqual( pCurve, poSrc1, poSrc2, SYMCRYPT_FLAG_ECPOINT_EQUAL, pbScratch, cbScratch );
891

892
        // Side-channel safe computations
893
        SymCryptShortWeierstrassAddDiffNonZero( pCurve, poSrc1, poSrc2, poQ0, pbScratch, cbScratch );   // This covers the cases where Src1 != Src2 or Src1 = -Src2
894

895
        SymCryptEcpointDouble( pCurve, poSrc1, poQ1, 0, pbScratch, cbScratch );     // Dispatch to Double function; enables type assertion on SymCryptShortWeierstrassDouble to be specific
896
        SymCryptEcpointMaskedCopy( pCurve, poQ1, poQ0, dSrcEqual );                                     // (Masked) copy if the points are equal
897

898
        SymCryptEcpointMaskedCopy( pCurve, poSrc1, poQ0, dSrc2Zero );                                   // (Masked) copy if Src2 = 0
899
        SymCryptEcpointMaskedCopy( pCurve, poSrc2, poQ0, dSrc1Zero );                                   // (Masked) copy if Src1 = 0
900

901
        SymCryptEcpointCopy( pCurve, poQ0, poDst );                                 // Copy the final result to destination
902
    }
903
}
904

905
VOID
906
SYMCRYPT_CALL
907
SymCryptShortWeierstrassNegate(
908
    _In_    PCSYMCRYPT_ECURVE   pCurve,
909
    _Inout_ PSYMCRYPT_ECPOINT   poSrc,
910
            UINT32              mask,
911
    _Out_writes_bytes_( cbScratch )
912
            PBYTE               pbScratch,
913
            SIZE_T              cbScratch )
914
{
915
    PCSYMCRYPT_MODULUS FMod = pCurve->FMod;
916
    PSYMCRYPT_MODELEMENT peY = SYMCRYPT_INTERNAL_ECPOINT_COORDINATE( 1, pCurve, poSrc);
917

918
    PSYMCRYPT_MODELEMENT peTmp = NULL;
919

920
    SYMCRYPT_ASSERT( SYMCRYPT_CURVE_IS_SHORT_WEIERSTRASS_TYPE(pCurve) );
921
    SYMCRYPT_ASSERT( SymCryptEcurveIsSame(pCurve, poSrc->pCurve) );
922
    SYMCRYPT_ASSERT( cbScratch >= SYMCRYPT_SCRATCH_BYTES_FOR_COMMON_MOD_OPERATIONS( pCurve->FModDigits ) + pCurve->cbModElement);
923

924
    peTmp = SymCryptModElementCreate(
925
                pbScratch,
926
                pCurve->cbModElement,
927
                FMod );
928
    SYMCRYPT_ASSERT( peTmp != NULL);
929

930
    pbScratch += pCurve->cbModElement;
931
    cbScratch -= pCurve->cbModElement;
932

933
    SymCryptModNeg( FMod, peY, peTmp, pbScratch, cbScratch );
934
    SymCryptModElementMaskedCopy( FMod, peTmp, peY, mask );
935
}
936

937
Product

Resources

Company
