Coverage Report

Created: 2024-11-21 07:03

/src/boringssl/crypto/fipsmodule/ec/ec_montgomery.c.inc
Line
Count
Source (jump to first uncovered line)
1
/* Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
2
 * ====================================================================
3
 * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
4
 *
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
7
 * are met:
8
 *
9
 * 1. Redistributions of source code must retain the above copyright
10
 *    notice, this list of conditions and the following disclaimer.
11
 *
12
 * 2. Redistributions in binary form must reproduce the above copyright
13
 *    notice, this list of conditions and the following disclaimer in
14
 *    the documentation and/or other materials provided with the
15
 *    distribution.
16
 *
17
 * 3. All advertising materials mentioning features or use of this
18
 *    software must display the following acknowledgment:
19
 *    "This product includes software developed by the OpenSSL Project
20
 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21
 *
22
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23
 *    endorse or promote products derived from this software without
24
 *    prior written permission. For written permission, please contact
25
 *    openssl-core@openssl.org.
26
 *
27
 * 5. Products derived from this software may not be called "OpenSSL"
28
 *    nor may "OpenSSL" appear in their names without prior written
29
 *    permission of the OpenSSL Project.
30
 *
31
 * 6. Redistributions of any form whatsoever must retain the following
32
 *    acknowledgment:
33
 *    "This product includes software developed by the OpenSSL Project
34
 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35
 *
36
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
40
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47
 * OF THE POSSIBILITY OF SUCH DAMAGE.
48
 * ====================================================================
49
 *
50
 * This product includes cryptographic software written by Eric Young
51
 * (eay@cryptsoft.com).  This product includes software written by Tim
52
 * Hudson (tjh@cryptsoft.com).
53
 *
54
 */
55
/* ====================================================================
56
 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
57
 *
58
 * Portions of the attached software ("Contribution") are developed by
59
 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
60
 *
61
 * The Contribution is licensed pursuant to the OpenSSL open source
62
 * license provided above.
63
 *
64
 * The elliptic curve binary polynomial software is originally written by
65
 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
66
 * Laboratories. */
67
68
#include <openssl/ec.h>
69
70
#include <openssl/bn.h>
71
#include <openssl/err.h>
72
#include <openssl/mem.h>
73
74
#include "../bn/internal.h"
75
#include "../delocate.h"
76
#include "internal.h"
77
78
79
static void ec_GFp_mont_felem_to_montgomery(const EC_GROUP *group,
80
556
                                            EC_FELEM *out, const EC_FELEM *in) {
81
556
  bn_to_montgomery_small(out->words, in->words, group->field.N.width,
82
556
                         &group->field);
83
556
}
84
85
static void ec_GFp_mont_felem_from_montgomery(const EC_GROUP *group,
86
                                              EC_FELEM *out,
87
157
                                              const EC_FELEM *in) {
88
157
  bn_from_montgomery_small(out->words, group->field.N.width, in->words,
89
157
                           group->field.N.width, &group->field);
90
157
}
91
92
static void ec_GFp_mont_felem_inv0(const EC_GROUP *group, EC_FELEM *out,
93
44
                                   const EC_FELEM *a) {
94
44
  bn_mod_inverse0_prime_mont_small(out->words, a->words, group->field.N.width,
95
44
                                   &group->field);
96
44
}
97
98
void ec_GFp_mont_felem_mul(const EC_GROUP *group, EC_FELEM *r,
99
115k
                           const EC_FELEM *a, const EC_FELEM *b) {
100
115k
  bn_mod_mul_montgomery_small(r->words, a->words, b->words,
101
115k
                              group->field.N.width, &group->field);
102
115k
}
103
104
void ec_GFp_mont_felem_sqr(const EC_GROUP *group, EC_FELEM *r,
105
127k
                           const EC_FELEM *a) {
106
127k
  bn_mod_mul_montgomery_small(r->words, a->words, a->words,
107
127k
                              group->field.N.width, &group->field);
108
127k
}
109
110
void ec_GFp_mont_felem_to_bytes(const EC_GROUP *group, uint8_t *out,
111
153
                                size_t *out_len, const EC_FELEM *in) {
112
153
  EC_FELEM tmp;
113
153
  ec_GFp_mont_felem_from_montgomery(group, &tmp, in);
114
153
  ec_GFp_simple_felem_to_bytes(group, out, out_len, &tmp);
115
153
}
116
117
int ec_GFp_mont_felem_from_bytes(const EC_GROUP *group, EC_FELEM *out,
118
556
                                 const uint8_t *in, size_t len) {
119
556
  if (!ec_GFp_simple_felem_from_bytes(group, out, in, len)) {
120
0
    return 0;
121
0
  }
122
123
556
  ec_GFp_mont_felem_to_montgomery(group, out, out);
124
556
  return 1;
125
556
}
126
127
void ec_GFp_mont_felem_reduce(const EC_GROUP *group, EC_FELEM *out,
128
0
                              const BN_ULONG *words, size_t num) {
129
  // Convert "from" Montgomery form so the value is reduced mod p.
130
0
  bn_from_montgomery_small(out->words, group->field.N.width, words, num,
131
0
                           &group->field);
132
  // Convert "to" Montgomery form to remove the R^-1 factor added.
133
0
  ec_GFp_mont_felem_to_montgomery(group, out, out);
134
  // Convert to Montgomery form to match this implementation's representation.
135
0
  ec_GFp_mont_felem_to_montgomery(group, out, out);
136
0
}
137
138
void ec_GFp_mont_felem_exp(const EC_GROUP *group, EC_FELEM *out,
139
                           const EC_FELEM *a, const BN_ULONG *exp,
140
0
                           size_t num_exp) {
141
0
  bn_mod_exp_mont_small(out->words, a->words, group->field.N.width, exp,
142
0
                        num_exp, &group->field);
143
0
}
144
145
static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group,
146
                                                    const EC_JACOBIAN *point,
147
45
                                                    EC_FELEM *x, EC_FELEM *y) {
148
45
  if (constant_time_declassify_int(
149
45
          ec_GFp_simple_is_at_infinity(group, point))) {
150
1
    OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
151
1
    return 0;
152
1
  }
153
154
  // Transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3). Note the check above
155
  // ensures |point->Z| is non-zero, so the inverse always exists.
156
44
  EC_FELEM z1, z2;
157
44
  ec_GFp_mont_felem_inv0(group, &z2, &point->Z);
158
44
  ec_GFp_mont_felem_sqr(group, &z1, &z2);
159
160
44
  if (x != NULL) {
161
44
    ec_GFp_mont_felem_mul(group, x, &point->X, &z1);
162
44
  }
163
164
44
  if (y != NULL) {
165
43
    ec_GFp_mont_felem_mul(group, &z1, &z1, &z2);
166
43
    ec_GFp_mont_felem_mul(group, y, &point->Y, &z1);
167
43
  }
168
169
44
  return 1;
170
45
}
171
172
static int ec_GFp_mont_jacobian_to_affine_batch(const EC_GROUP *group,
173
                                                EC_AFFINE *out,
174
                                                const EC_JACOBIAN *in,
175
0
                                                size_t num) {
176
0
  if (num == 0) {
177
0
    return 1;
178
0
  }
179
180
  // Compute prefix products of all Zs. Use |out[i].X| as scratch space
181
  // to store these values.
182
0
  out[0].X = in[0].Z;
183
0
  for (size_t i = 1; i < num; i++) {
184
0
    ec_GFp_mont_felem_mul(group, &out[i].X, &out[i - 1].X, &in[i].Z);
185
0
  }
186
187
  // Some input was infinity iff the product of all Zs is zero.
188
0
  if (ec_felem_non_zero_mask(group, &out[num - 1].X) == 0) {
189
0
    OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
190
0
    return 0;
191
0
  }
192
193
  // Invert the product of all Zs.
194
0
  EC_FELEM zinvprod;
195
0
  ec_GFp_mont_felem_inv0(group, &zinvprod, &out[num - 1].X);
196
0
  for (size_t i = num - 1; i < num; i--) {
197
    // Our loop invariant is that |zinvprod| is Z0^-1 * Z1^-1 * ... * Zi^-1.
198
    // Recover Zi^-1 by multiplying by the previous product.
199
0
    EC_FELEM zinv, zinv2;
200
0
    if (i == 0) {
201
0
      zinv = zinvprod;
202
0
    } else {
203
0
      ec_GFp_mont_felem_mul(group, &zinv, &zinvprod, &out[i - 1].X);
204
      // Maintain the loop invariant for the next iteration.
205
0
      ec_GFp_mont_felem_mul(group, &zinvprod, &zinvprod, &in[i].Z);
206
0
    }
207
208
    // Compute affine coordinates: x = X * Z^-2 and y = Y * Z^-3.
209
0
    ec_GFp_mont_felem_sqr(group, &zinv2, &zinv);
210
0
    ec_GFp_mont_felem_mul(group, &out[i].X, &in[i].X, &zinv2);
211
0
    ec_GFp_mont_felem_mul(group, &out[i].Y, &in[i].Y, &zinv2);
212
0
    ec_GFp_mont_felem_mul(group, &out[i].Y, &out[i].Y, &zinv);
213
0
  }
214
215
0
  return 1;
216
0
}
217
218
void ec_GFp_mont_add(const EC_GROUP *group, EC_JACOBIAN *out,
219
4.87k
                     const EC_JACOBIAN *a, const EC_JACOBIAN *b) {
220
4.87k
  if (a == b) {
221
0
    ec_GFp_mont_dbl(group, out, a);
222
0
    return;
223
0
  }
224
225
  // The method is taken from:
226
  //   http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl
227
  //
228
  // Coq transcription and correctness proof:
229
  // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L467>
230
  // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L544>
231
4.87k
  EC_FELEM x_out, y_out, z_out;
232
4.87k
  BN_ULONG z1nz = ec_felem_non_zero_mask(group, &a->Z);
233
4.87k
  BN_ULONG z2nz = ec_felem_non_zero_mask(group, &b->Z);
234
235
  // z1z1 = z1z1 = z1**2
236
4.87k
  EC_FELEM z1z1;
237
4.87k
  ec_GFp_mont_felem_sqr(group, &z1z1, &a->Z);
238
239
  // z2z2 = z2**2
240
4.87k
  EC_FELEM z2z2;
241
4.87k
  ec_GFp_mont_felem_sqr(group, &z2z2, &b->Z);
242
243
  // u1 = x1*z2z2
244
4.87k
  EC_FELEM u1;
245
4.87k
  ec_GFp_mont_felem_mul(group, &u1, &a->X, &z2z2);
246
247
  // two_z1z2 = (z1 + z2)**2 - (z1z1 + z2z2) = 2z1z2
248
4.87k
  EC_FELEM two_z1z2;
249
4.87k
  ec_felem_add(group, &two_z1z2, &a->Z, &b->Z);
250
4.87k
  ec_GFp_mont_felem_sqr(group, &two_z1z2, &two_z1z2);
251
4.87k
  ec_felem_sub(group, &two_z1z2, &two_z1z2, &z1z1);
252
4.87k
  ec_felem_sub(group, &two_z1z2, &two_z1z2, &z2z2);
253
254
  // s1 = y1 * z2**3
255
4.87k
  EC_FELEM s1;
256
4.87k
  ec_GFp_mont_felem_mul(group, &s1, &b->Z, &z2z2);
257
4.87k
  ec_GFp_mont_felem_mul(group, &s1, &s1, &a->Y);
258
259
  // u2 = x2*z1z1
260
4.87k
  EC_FELEM u2;
261
4.87k
  ec_GFp_mont_felem_mul(group, &u2, &b->X, &z1z1);
262
263
  // h = u2 - u1
264
4.87k
  EC_FELEM h;
265
4.87k
  ec_felem_sub(group, &h, &u2, &u1);
266
267
4.87k
  BN_ULONG xneq = ec_felem_non_zero_mask(group, &h);
268
269
  // z_out = two_z1z2 * h
270
4.87k
  ec_GFp_mont_felem_mul(group, &z_out, &h, &two_z1z2);
271
272
  // z1z1z1 = z1 * z1z1
273
4.87k
  EC_FELEM z1z1z1;
274
4.87k
  ec_GFp_mont_felem_mul(group, &z1z1z1, &a->Z, &z1z1);
275
276
  // s2 = y2 * z1**3
277
4.87k
  EC_FELEM s2;
278
4.87k
  ec_GFp_mont_felem_mul(group, &s2, &b->Y, &z1z1z1);
279
280
  // r = (s2 - s1)*2
281
4.87k
  EC_FELEM r;
282
4.87k
  ec_felem_sub(group, &r, &s2, &s1);
283
4.87k
  ec_felem_add(group, &r, &r, &r);
284
285
4.87k
  BN_ULONG yneq = ec_felem_non_zero_mask(group, &r);
286
287
  // This case will never occur in the constant-time |ec_GFp_mont_mul|.
288
4.87k
  BN_ULONG is_nontrivial_double = ~xneq & ~yneq & z1nz & z2nz;
289
4.87k
  if (constant_time_declassify_w(is_nontrivial_double)) {
290
2
    ec_GFp_mont_dbl(group, out, a);
291
2
    return;
292
2
  }
293
294
  // I = (2h)**2
295
4.87k
  EC_FELEM i;
296
4.87k
  ec_felem_add(group, &i, &h, &h);
297
4.87k
  ec_GFp_mont_felem_sqr(group, &i, &i);
298
299
  // J = h * I
300
4.87k
  EC_FELEM j;
301
4.87k
  ec_GFp_mont_felem_mul(group, &j, &h, &i);
302
303
  // V = U1 * I
304
4.87k
  EC_FELEM v;
305
4.87k
  ec_GFp_mont_felem_mul(group, &v, &u1, &i);
306
307
  // x_out = r**2 - J - 2V
308
4.87k
  ec_GFp_mont_felem_sqr(group, &x_out, &r);
309
4.87k
  ec_felem_sub(group, &x_out, &x_out, &j);
310
4.87k
  ec_felem_sub(group, &x_out, &x_out, &v);
311
4.87k
  ec_felem_sub(group, &x_out, &x_out, &v);
312
313
  // y_out = r(V-x_out) - 2 * s1 * J
314
4.87k
  ec_felem_sub(group, &y_out, &v, &x_out);
315
4.87k
  ec_GFp_mont_felem_mul(group, &y_out, &y_out, &r);
316
4.87k
  EC_FELEM s1j;
317
4.87k
  ec_GFp_mont_felem_mul(group, &s1j, &s1, &j);
318
4.87k
  ec_felem_sub(group, &y_out, &y_out, &s1j);
319
4.87k
  ec_felem_sub(group, &y_out, &y_out, &s1j);
320
321
4.87k
  ec_felem_select(group, &x_out, z1nz, &x_out, &b->X);
322
4.87k
  ec_felem_select(group, &out->X, z2nz, &x_out, &a->X);
323
4.87k
  ec_felem_select(group, &y_out, z1nz, &y_out, &b->Y);
324
4.87k
  ec_felem_select(group, &out->Y, z2nz, &y_out, &a->Y);
325
4.87k
  ec_felem_select(group, &z_out, z1nz, &z_out, &b->Z);
326
4.87k
  ec_felem_select(group, &out->Z, z2nz, &z_out, &a->Z);
327
4.87k
}
328
329
void ec_GFp_mont_dbl(const EC_GROUP *group, EC_JACOBIAN *r,
330
20.4k
                     const EC_JACOBIAN *a) {
331
20.4k
  if (group->a_is_minus3) {
332
    // The method is taken from:
333
    //   http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
334
    //
335
    // Coq transcription and correctness proof:
336
    // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L93>
337
    // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L201>
338
20.4k
    EC_FELEM delta, gamma, beta, ftmp, ftmp2, tmptmp, alpha, fourbeta;
339
    // delta = z^2
340
20.4k
    ec_GFp_mont_felem_sqr(group, &delta, &a->Z);
341
    // gamma = y^2
342
20.4k
    ec_GFp_mont_felem_sqr(group, &gamma, &a->Y);
343
    // beta = x*gamma
344
20.4k
    ec_GFp_mont_felem_mul(group, &beta, &a->X, &gamma);
345
346
    // alpha = 3*(x-delta)*(x+delta)
347
20.4k
    ec_felem_sub(group, &ftmp, &a->X, &delta);
348
20.4k
    ec_felem_add(group, &ftmp2, &a->X, &delta);
349
350
20.4k
    ec_felem_add(group, &tmptmp, &ftmp2, &ftmp2);
351
20.4k
    ec_felem_add(group, &ftmp2, &ftmp2, &tmptmp);
352
20.4k
    ec_GFp_mont_felem_mul(group, &alpha, &ftmp, &ftmp2);
353
354
    // x' = alpha^2 - 8*beta
355
20.4k
    ec_GFp_mont_felem_sqr(group, &r->X, &alpha);
356
20.4k
    ec_felem_add(group, &fourbeta, &beta, &beta);
357
20.4k
    ec_felem_add(group, &fourbeta, &fourbeta, &fourbeta);
358
20.4k
    ec_felem_add(group, &tmptmp, &fourbeta, &fourbeta);
359
20.4k
    ec_felem_sub(group, &r->X, &r->X, &tmptmp);
360
361
    // z' = (y + z)^2 - gamma - delta
362
20.4k
    ec_felem_add(group, &delta, &gamma, &delta);
363
20.4k
    ec_felem_add(group, &ftmp, &a->Y, &a->Z);
364
20.4k
    ec_GFp_mont_felem_sqr(group, &r->Z, &ftmp);
365
20.4k
    ec_felem_sub(group, &r->Z, &r->Z, &delta);
366
367
    // y' = alpha*(4*beta - x') - 8*gamma^2
368
20.4k
    ec_felem_sub(group, &r->Y, &fourbeta, &r->X);
369
20.4k
    ec_felem_add(group, &gamma, &gamma, &gamma);
370
20.4k
    ec_GFp_mont_felem_sqr(group, &gamma, &gamma);
371
20.4k
    ec_GFp_mont_felem_mul(group, &r->Y, &alpha, &r->Y);
372
20.4k
    ec_felem_add(group, &gamma, &gamma, &gamma);
373
20.4k
    ec_felem_sub(group, &r->Y, &r->Y, &gamma);
374
20.4k
  } else {
375
    // The method is taken from:
376
    //   http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
377
    //
378
    // Coq transcription and correctness proof:
379
    // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L102>
380
    // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L534>
381
0
    EC_FELEM xx, yy, yyyy, zz;
382
0
    ec_GFp_mont_felem_sqr(group, &xx, &a->X);
383
0
    ec_GFp_mont_felem_sqr(group, &yy, &a->Y);
384
0
    ec_GFp_mont_felem_sqr(group, &yyyy, &yy);
385
0
    ec_GFp_mont_felem_sqr(group, &zz, &a->Z);
386
387
    // s = 2*((x_in + yy)^2 - xx - yyyy)
388
0
    EC_FELEM s;
389
0
    ec_felem_add(group, &s, &a->X, &yy);
390
0
    ec_GFp_mont_felem_sqr(group, &s, &s);
391
0
    ec_felem_sub(group, &s, &s, &xx);
392
0
    ec_felem_sub(group, &s, &s, &yyyy);
393
0
    ec_felem_add(group, &s, &s, &s);
394
395
    // m = 3*xx + a*zz^2
396
0
    EC_FELEM m;
397
0
    ec_GFp_mont_felem_sqr(group, &m, &zz);
398
0
    ec_GFp_mont_felem_mul(group, &m, &group->a, &m);
399
0
    ec_felem_add(group, &m, &m, &xx);
400
0
    ec_felem_add(group, &m, &m, &xx);
401
0
    ec_felem_add(group, &m, &m, &xx);
402
403
    // x_out = m^2 - 2*s
404
0
    ec_GFp_mont_felem_sqr(group, &r->X, &m);
405
0
    ec_felem_sub(group, &r->X, &r->X, &s);
406
0
    ec_felem_sub(group, &r->X, &r->X, &s);
407
408
    // z_out = (y_in + z_in)^2 - yy - zz
409
0
    ec_felem_add(group, &r->Z, &a->Y, &a->Z);
410
0
    ec_GFp_mont_felem_sqr(group, &r->Z, &r->Z);
411
0
    ec_felem_sub(group, &r->Z, &r->Z, &yy);
412
0
    ec_felem_sub(group, &r->Z, &r->Z, &zz);
413
414
    // y_out = m*(s-x_out) - 8*yyyy
415
0
    ec_felem_add(group, &yyyy, &yyyy, &yyyy);
416
0
    ec_felem_add(group, &yyyy, &yyyy, &yyyy);
417
0
    ec_felem_add(group, &yyyy, &yyyy, &yyyy);
418
0
    ec_felem_sub(group, &r->Y, &s, &r->X);
419
0
    ec_GFp_mont_felem_mul(group, &r->Y, &r->Y, &m);
420
0
    ec_felem_sub(group, &r->Y, &r->Y, &yyyy);
421
0
  }
422
20.4k
}
423
424
static int ec_GFp_mont_cmp_x_coordinate(const EC_GROUP *group,
425
                                        const EC_JACOBIAN *p,
426
4
                                        const EC_SCALAR *r) {
427
4
  if (!group->field_greater_than_order ||
428
4
      group->field.N.width != group->order.N.width) {
429
    // Do not bother optimizing this case. p > order in all commonly-used
430
    // curves.
431
0
    return ec_GFp_simple_cmp_x_coordinate(group, p, r);
432
0
  }
433
434
4
  if (ec_GFp_simple_is_at_infinity(group, p)) {
435
0
    return 0;
436
0
  }
437
438
  // We wish to compare X/Z^2 with r. This is equivalent to comparing X with
439
  // r*Z^2. Note that X and Z are represented in Montgomery form, while r is
440
  // not.
441
4
  EC_FELEM r_Z2, Z2_mont, X;
442
4
  ec_GFp_mont_felem_mul(group, &Z2_mont, &p->Z, &p->Z);
443
  // r < order < p, so this is valid.
444
4
  OPENSSL_memcpy(r_Z2.words, r->words, group->field.N.width * sizeof(BN_ULONG));
445
4
  ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont);
446
4
  ec_GFp_mont_felem_from_montgomery(group, &X, &p->X);
447
448
4
  if (ec_felem_equal(group, &r_Z2, &X)) {
449
3
    return 1;
450
3
  }
451
452
  // During signing the x coefficient is reduced modulo the group order.
453
  // Therefore there is a small possibility, less than 1/2^128, that group_order
454
  // < p.x < P. in that case we need not only to compare against |r| but also to
455
  // compare against r+group_order.
456
1
  BN_ULONG carry = bn_add_words(r_Z2.words, r->words, group->order.N.d,
457
1
                                group->field.N.width);
458
1
  if (carry == 0 &&
459
1
      bn_less_than_words(r_Z2.words, group->field.N.d, group->field.N.width)) {
460
    // r + group_order < p, so compare (r + group_order) * Z^2 against X.
461
0
    ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont);
462
0
    if (ec_felem_equal(group, &r_Z2, &X)) {
463
0
      return 1;
464
0
    }
465
0
  }
466
467
1
  return 0;
468
1
}
469
470
2
DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_mont_method) {
471
2
  out->point_get_affine_coordinates = ec_GFp_mont_point_get_affine_coordinates;
472
2
  out->jacobian_to_affine_batch = ec_GFp_mont_jacobian_to_affine_batch;
473
2
  out->add = ec_GFp_mont_add;
474
2
  out->dbl = ec_GFp_mont_dbl;
475
2
  out->mul = ec_GFp_mont_mul;
476
2
  out->mul_base = ec_GFp_mont_mul_base;
477
2
  out->mul_batch = ec_GFp_mont_mul_batch;
478
2
  out->mul_public_batch = ec_GFp_mont_mul_public_batch;
479
2
  out->init_precomp = ec_GFp_mont_init_precomp;
480
2
  out->mul_precomp = ec_GFp_mont_mul_precomp;
481
2
  out->felem_mul = ec_GFp_mont_felem_mul;
482
2
  out->felem_sqr = ec_GFp_mont_felem_sqr;
483
2
  out->felem_to_bytes = ec_GFp_mont_felem_to_bytes;
484
2
  out->felem_from_bytes = ec_GFp_mont_felem_from_bytes;
485
2
  out->felem_reduce = ec_GFp_mont_felem_reduce;
486
2
  out->felem_exp = ec_GFp_mont_felem_exp;
487
2
  out->scalar_inv0_montgomery = ec_simple_scalar_inv0_montgomery;
488
2
  out->scalar_to_montgomery_inv_vartime =
489
2
      ec_simple_scalar_to_montgomery_inv_vartime;
490
2
  out->cmp_x_coordinate = ec_GFp_mont_cmp_x_coordinate;
491
2
}