1// Copyright 2001-2016 The OpenSSL Project Authors. All Rights Reserved.
2// Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved.
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//     https://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16#include <openssl/ec.h>
17
18#include <string.h>
19
20#include <openssl/bn.h>
21#include <openssl/err.h>
22#include <openssl/mem.h>
23
24#include "internal.h"
25#include "../../internal.h"
26
27
28// Most method functions in this file are designed to work with non-trivial
29// representations of field elements if necessary (see ecp_mont.c): while
30// standard modular addition and subtraction are used, the field_mul and
31// field_sqr methods will be used for multiplication, and field_encode and
32// field_decode (if defined) will be used for converting between
33// representations.
34//
35// Functions here specifically assume that if a non-trivial representation is
36// used, it is a Montgomery representation (i.e. 'encoding' means multiplying
37// by some factor R).
38
39int ec_GFp_simple_group_set_curve(EC_GROUP *group, const BIGNUM *p,
40                                  const BIGNUM *a, const BIGNUM *b,
41                                  BN_CTX *ctx) {
42  // p must be a prime > 3
43  if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
44    OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FIELD);
45    return 0;
46  }
47
48  bssl::BN_CTXScope scope(ctx);
49  BIGNUM *tmp = BN_CTX_get(ctx);
50  if (tmp == nullptr) {
51    return 0;
52  }
53
54  if (!BN_MONT_CTX_set(&group->field, p, ctx) ||
55      !ec_bignum_to_felem(group, &group->a, a) ||
56      !ec_bignum_to_felem(group, &group->b, b) ||
57      // Reuse Z from the generator to cache the value one.
58      !ec_bignum_to_felem(group, &group->generator.raw.Z, BN_value_one())) {
59    return 0;
60  }
61
62  // group->a_is_minus3
63  if (!BN_copy(tmp, a) ||
64      !BN_add_word(tmp, 3)) {
65    return 0;
66  }
67  group->a_is_minus3 = (0 == BN_cmp(tmp, &group->field.N));
68
69  return 1;
70}
71
72int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
73                                  BIGNUM *b) {
74  if ((p != NULL && !BN_copy(p, &group->field.N)) ||
75      (a != NULL && !ec_felem_to_bignum(group, a, &group->a)) ||
76      (b != NULL && !ec_felem_to_bignum(group, b, &group->b))) {
77    return 0;
78  }
79  return 1;
80}
81
82void ec_GFp_simple_point_init(EC_JACOBIAN *point) {
83  OPENSSL_memset(&point->X, 0, sizeof(EC_FELEM));
84  OPENSSL_memset(&point->Y, 0, sizeof(EC_FELEM));
85  OPENSSL_memset(&point->Z, 0, sizeof(EC_FELEM));
86}
87
88void ec_GFp_simple_point_copy(EC_JACOBIAN *dest, const EC_JACOBIAN *src) {
89  OPENSSL_memcpy(&dest->X, &src->X, sizeof(EC_FELEM));
90  OPENSSL_memcpy(&dest->Y, &src->Y, sizeof(EC_FELEM));
91  OPENSSL_memcpy(&dest->Z, &src->Z, sizeof(EC_FELEM));
92}
93
94void ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
95                                         EC_JACOBIAN *point) {
96  // Although it is strictly only necessary to zero Z, we zero the entire point
97  // in case |point| was stack-allocated and yet to be initialized.
98  ec_GFp_simple_point_init(point);
99}
100
101void ec_GFp_simple_invert(const EC_GROUP *group, EC_JACOBIAN *point) {
102  ec_felem_neg(group, &point->Y, &point->Y);
103}
104
105int ec_GFp_simple_is_at_infinity(const EC_GROUP *group,
106                                 const EC_JACOBIAN *point) {
107  return ec_felem_non_zero_mask(group, &point->Z) == 0;
108}
109
110int ec_GFp_simple_is_on_curve(const EC_GROUP *group,
111                              const EC_JACOBIAN *point) {
112  // We have a curve defined by a Weierstrass equation
113  //      y^2 = x^3 + a*x + b.
114  // The point to consider is given in Jacobian projective coordinates
115  // where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
116  // Substituting this and multiplying by  Z^6  transforms the above equation
117  // into
118  //      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
119  // To test this, we add up the right-hand side in 'rh'.
120  //
121  // This function may be used when double-checking the secret result of a point
122  // multiplication, so we proceed in constant-time.
123
124  void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a,
125                          const EC_FELEM *b) = group->meth->felem_mul;
126  void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) =
127      group->meth->felem_sqr;
128
129  // rh := X^2
130  EC_FELEM rh;
131  felem_sqr(group, &rh, &point->X);
132
133  EC_FELEM tmp, Z4, Z6;
134  felem_sqr(group, &tmp, &point->Z);
135  felem_sqr(group, &Z4, &tmp);
136  felem_mul(group, &Z6, &Z4, &tmp);
137
138  // rh := rh + a*Z^4
139  if (group->a_is_minus3) {
140    ec_felem_add(group, &tmp, &Z4, &Z4);
141    ec_felem_add(group, &tmp, &tmp, &Z4);
142    ec_felem_sub(group, &rh, &rh, &tmp);
143  } else {
144    felem_mul(group, &tmp, &Z4, &group->a);
145    ec_felem_add(group, &rh, &rh, &tmp);
146  }
147
148  // rh := (rh + a*Z^4)*X
149  felem_mul(group, &rh, &rh, &point->X);
150
151  // rh := rh + b*Z^6
152  felem_mul(group, &tmp, &group->b, &Z6);
153  ec_felem_add(group, &rh, &rh, &tmp);
154
155  // 'lh' := Y^2
156  felem_sqr(group, &tmp, &point->Y);
157
158  ec_felem_sub(group, &tmp, &tmp, &rh);
159  BN_ULONG not_equal = ec_felem_non_zero_mask(group, &tmp);
160
161  // If Z = 0, the point is infinity, which is always on the curve.
162  BN_ULONG not_infinity = ec_felem_non_zero_mask(group, &point->Z);
163
164  return 1 & ~(not_infinity & not_equal);
165}
166
167int ec_GFp_simple_points_equal(const EC_GROUP *group, const EC_JACOBIAN *a,
168                               const EC_JACOBIAN *b) {
169  // This function is implemented in constant-time for two reasons. First,
170  // although EC points are usually public, their Jacobian Z coordinates may be
171  // secret, or at least are not obviously public. Second, more complex
172  // protocols will sometimes manipulate secret points.
173  //
174  // This does mean that we pay a 6M+2S Jacobian comparison when comparing two
175  // publicly affine points costs no field operations at all. If needed, we can
176  // restore this optimization by keeping better track of affine vs. Jacobian
177  // forms. See https://crbug.com/boringssl/326.
178
179  // If neither |a| or |b| is infinity, we have to decide whether
180  //     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
181  // or equivalently, whether
182  //     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
183
184  void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a,
185                          const EC_FELEM *b) = group->meth->felem_mul;
186  void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) =
187      group->meth->felem_sqr;
188
189  EC_FELEM tmp1, tmp2, Za23, Zb23;
190  felem_sqr(group, &Zb23, &b->Z);         // Zb23 = Z_b^2
191  felem_mul(group, &tmp1, &a->X, &Zb23);  // tmp1 = X_a * Z_b^2
192  felem_sqr(group, &Za23, &a->Z);         // Za23 = Z_a^2
193  felem_mul(group, &tmp2, &b->X, &Za23);  // tmp2 = X_b * Z_a^2
194  ec_felem_sub(group, &tmp1, &tmp1, &tmp2);
195  const BN_ULONG x_not_equal = ec_felem_non_zero_mask(group, &tmp1);
196
197  felem_mul(group, &Zb23, &Zb23, &b->Z);  // Zb23 = Z_b^3
198  felem_mul(group, &tmp1, &a->Y, &Zb23);  // tmp1 = Y_a * Z_b^3
199  felem_mul(group, &Za23, &Za23, &a->Z);  // Za23 = Z_a^3
200  felem_mul(group, &tmp2, &b->Y, &Za23);  // tmp2 = Y_b * Z_a^3
201  ec_felem_sub(group, &tmp1, &tmp1, &tmp2);
202  const BN_ULONG y_not_equal = ec_felem_non_zero_mask(group, &tmp1);
203  const BN_ULONG x_and_y_equal = ~(x_not_equal | y_not_equal);
204
205  const BN_ULONG a_not_infinity = ec_felem_non_zero_mask(group, &a->Z);
206  const BN_ULONG b_not_infinity = ec_felem_non_zero_mask(group, &b->Z);
207  const BN_ULONG a_and_b_infinity = ~(a_not_infinity | b_not_infinity);
208
209  const BN_ULONG equal =
210      a_and_b_infinity | (a_not_infinity & b_not_infinity & x_and_y_equal);
211  return equal & 1;
212}
213
214int ec_affine_jacobian_equal(const EC_GROUP *group, const EC_AFFINE *a,
215                             const EC_JACOBIAN *b) {
216  // If |b| is not infinity, we have to decide whether
217  //     (X_a, Y_a) = (X_b/Z_b^2, Y_b/Z_b^3),
218  // or equivalently, whether
219  //     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b, Y_b).
220
221  void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a,
222                          const EC_FELEM *b) = group->meth->felem_mul;
223  void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) =
224      group->meth->felem_sqr;
225
226  EC_FELEM tmp, Zb2;
227  felem_sqr(group, &Zb2, &b->Z);        // Zb2 = Z_b^2
228  felem_mul(group, &tmp, &a->X, &Zb2);  // tmp = X_a * Z_b^2
229  ec_felem_sub(group, &tmp, &tmp, &b->X);
230  const BN_ULONG x_not_equal = ec_felem_non_zero_mask(group, &tmp);
231
232  felem_mul(group, &tmp, &a->Y, &Zb2);  // tmp = Y_a * Z_b^2
233  felem_mul(group, &tmp, &tmp, &b->Z);  // tmp = Y_a * Z_b^3
234  ec_felem_sub(group, &tmp, &tmp, &b->Y);
235  const BN_ULONG y_not_equal = ec_felem_non_zero_mask(group, &tmp);
236  const BN_ULONG x_and_y_equal = ~(x_not_equal | y_not_equal);
237
238  const BN_ULONG b_not_infinity = ec_felem_non_zero_mask(group, &b->Z);
239
240  const BN_ULONG equal = b_not_infinity & x_and_y_equal;
241  return equal & 1;
242}
243
244int ec_GFp_simple_cmp_x_coordinate(const EC_GROUP *group, const EC_JACOBIAN *p,
245                                   const EC_SCALAR *r) {
246  if (ec_GFp_simple_is_at_infinity(group, p)) {
247    // |ec_get_x_coordinate_as_scalar| will check this internally, but this way
248    // we do not push to the error queue.
249    return 0;
250  }
251
252  EC_SCALAR x;
253  return ec_get_x_coordinate_as_scalar(group, &x, p) &&
254         ec_scalar_equal_vartime(group, &x, r);
255}
256
257void ec_GFp_simple_felem_to_bytes(const EC_GROUP *group, uint8_t *out,
258                                  size_t *out_len, const EC_FELEM *in) {
259  size_t len = BN_num_bytes(&group->field.N);
260  bn_words_to_big_endian(out, len, in->words, group->field.N.width);
261  *out_len = len;
262}
263
264int ec_GFp_simple_felem_from_bytes(const EC_GROUP *group, EC_FELEM *out,
265                                   const uint8_t *in, size_t len) {
266  if (len != BN_num_bytes(&group->field.N)) {
267    OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR);
268    return 0;
269  }
270
271  bn_big_endian_to_words(out->words, group->field.N.width, in, len);
272
273  if (!bn_less_than_words(out->words, group->field.N.d, group->field.N.width)) {
274    OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR);
275    return 0;
276  }
277
278  return 1;
279}
280