d4a7a1abdc60af5a02d5b153df0293960d0e0bfb
[openssl.git] / crypto / ec / ec2_oct.c
1 /*
2  * Copyright 2011-2020 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
4  *
5  * Licensed under the Apache License 2.0 (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  */
10
11 /*
12  * ECDSA low level APIs are deprecated for public use, but still ok for
13  * internal use.
14  */
15 #include "internal/deprecated.h"
16
17 #include <openssl/err.h>
18
19 #include "ec_local.h"
20
21 #ifndef OPENSSL_NO_EC2M
22
23 /*-
24  * Calculates and sets the affine coordinates of an EC_POINT from the given
25  * compressed coordinates.  Uses algorithm 2.3.4 of SEC 1.
26  * Note that the simple implementation only uses affine coordinates.
27  *
28  * The method is from the following publication:
29  *
30  *     Harper, Menezes, Vanstone:
31  *     "Public-Key Cryptosystems with Very Small Key Lengths",
32  *     EUROCRYPT '92, Springer-Verlag LNCS 658,
33  *     published February 1993
34  *
35  * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe
36  * the same method, but claim no priority date earlier than July 29, 1994
37  * (and additionally fail to cite the EUROCRYPT '92 publication as prior art).
38  */
39 int ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group,
40                                               EC_POINT *point,
41                                               const BIGNUM *x_, int y_bit,
42                                               BN_CTX *ctx)
43 {
44     BIGNUM *tmp, *x, *y, *z;
45     int ret = 0, z0;
46 #ifndef FIPS_MODE
47     BN_CTX *new_ctx = NULL;
48
49     /* clear error queue */
50     ERR_clear_error();
51
52     if (ctx == NULL) {
53         ctx = new_ctx = BN_CTX_new();
54         if (ctx == NULL)
55             return 0;
56     }
57 #endif
58
59     y_bit = (y_bit != 0) ? 1 : 0;
60
61     BN_CTX_start(ctx);
62     tmp = BN_CTX_get(ctx);
63     x = BN_CTX_get(ctx);
64     y = BN_CTX_get(ctx);
65     z = BN_CTX_get(ctx);
66     if (z == NULL)
67         goto err;
68
69     if (!BN_GF2m_mod_arr(x, x_, group->poly))
70         goto err;
71     if (BN_is_zero(x)) {
72         if (!BN_GF2m_mod_sqrt_arr(y, group->b, group->poly, ctx))
73             goto err;
74     } else {
75         if (!group->meth->field_sqr(group, tmp, x, ctx))
76             goto err;
77         if (!group->meth->field_div(group, tmp, group->b, tmp, ctx))
78             goto err;
79         if (!BN_GF2m_add(tmp, group->a, tmp))
80             goto err;
81         if (!BN_GF2m_add(tmp, x, tmp))
82             goto err;
83         if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) {
84 #ifndef FIPS_MODE
85             unsigned long err = ERR_peek_last_error();
86
87             if (ERR_GET_LIB(err) == ERR_LIB_BN
88                 && ERR_GET_REASON(err) == BN_R_NO_SOLUTION) {
89                 ERR_clear_error();
90                 ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES,
91                       EC_R_INVALID_COMPRESSED_POINT);
92             } else
93 #endif
94             {
95                 ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES,
96                       ERR_R_BN_LIB);
97             }
98             goto err;
99         }
100         z0 = (BN_is_odd(z)) ? 1 : 0;
101         if (!group->meth->field_mul(group, y, x, z, ctx))
102             goto err;
103         if (z0 != y_bit) {
104             if (!BN_GF2m_add(y, y, x))
105                 goto err;
106         }
107     }
108
109     if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
110         goto err;
111
112     ret = 1;
113
114  err:
115     BN_CTX_end(ctx);
116 #ifndef FIPS_MODE
117     BN_CTX_free(new_ctx);
118 #endif
119     return ret;
120 }
121
122 /*
123  * Converts an EC_POINT to an octet string. If buf is NULL, the encoded
124  * length will be returned. If the length len of buf is smaller than required
125  * an error will be returned.
126  */
127 size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
128                                 point_conversion_form_t form,
129                                 unsigned char *buf, size_t len, BN_CTX *ctx)
130 {
131     size_t ret;
132     int used_ctx = 0;
133     BIGNUM *x, *y, *yxi;
134     size_t field_len, i, skip;
135 #ifndef FIPS_MODE
136     BN_CTX *new_ctx = NULL;
137 #endif
138
139     if ((form != POINT_CONVERSION_COMPRESSED)
140         && (form != POINT_CONVERSION_UNCOMPRESSED)
141         && (form != POINT_CONVERSION_HYBRID)) {
142         ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
143         goto err;
144     }
145
146     if (EC_POINT_is_at_infinity(group, point)) {
147         /* encodes to a single 0 octet */
148         if (buf != NULL) {
149             if (len < 1) {
150                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
151                 return 0;
152             }
153             buf[0] = 0;
154         }
155         return 1;
156     }
157
158     /* ret := required output buffer length */
159     field_len = (EC_GROUP_get_degree(group) + 7) / 8;
160     ret =
161         (form ==
162          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
163
164     /* if 'buf' is NULL, just return required length */
165     if (buf != NULL) {
166         if (len < ret) {
167             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
168             goto err;
169         }
170
171 #ifndef FIPS_MODE
172         if (ctx == NULL) {
173             ctx = new_ctx = BN_CTX_new();
174             if (ctx == NULL)
175                 return 0;
176         }
177 #endif
178
179         BN_CTX_start(ctx);
180         used_ctx = 1;
181         x = BN_CTX_get(ctx);
182         y = BN_CTX_get(ctx);
183         yxi = BN_CTX_get(ctx);
184         if (yxi == NULL)
185             goto err;
186
187         if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
188             goto err;
189
190         buf[0] = form;
191         if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) {
192             if (!group->meth->field_div(group, yxi, y, x, ctx))
193                 goto err;
194             if (BN_is_odd(yxi))
195                 buf[0]++;
196         }
197
198         i = 1;
199
200         skip = field_len - BN_num_bytes(x);
201         if (skip > field_len) {
202             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
203             goto err;
204         }
205         while (skip > 0) {
206             buf[i++] = 0;
207             skip--;
208         }
209         skip = BN_bn2bin(x, buf + i);
210         i += skip;
211         if (i != 1 + field_len) {
212             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
213             goto err;
214         }
215
216         if (form == POINT_CONVERSION_UNCOMPRESSED
217             || form == POINT_CONVERSION_HYBRID) {
218             skip = field_len - BN_num_bytes(y);
219             if (skip > field_len) {
220                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
221                 goto err;
222             }
223             while (skip > 0) {
224                 buf[i++] = 0;
225                 skip--;
226             }
227             skip = BN_bn2bin(y, buf + i);
228             i += skip;
229         }
230
231         if (i != ret) {
232             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
233             goto err;
234         }
235     }
236
237     if (used_ctx)
238         BN_CTX_end(ctx);
239 #ifndef FIPS_MODE
240     BN_CTX_free(new_ctx);
241 #endif
242     return ret;
243
244  err:
245     if (used_ctx)
246         BN_CTX_end(ctx);
247 #ifndef FIPS_MODE
248     BN_CTX_free(new_ctx);
249 #endif
250     return 0;
251 }
252
253 /*
254  * Converts an octet string representation to an EC_POINT. Note that the
255  * simple implementation only uses affine coordinates.
256  */
257 int ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
258                              const unsigned char *buf, size_t len,
259                              BN_CTX *ctx)
260 {
261     point_conversion_form_t form;
262     int y_bit, m;
263     BIGNUM *x, *y, *yxi;
264     size_t field_len, enc_len;
265     int ret = 0;
266 #ifndef FIPS_MODE
267     BN_CTX *new_ctx = NULL;
268 #endif
269
270     if (len == 0) {
271         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
272         return 0;
273     }
274     form = buf[0];
275     y_bit = form & 1;
276     form = form & ~1U;
277     if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
278         && (form != POINT_CONVERSION_UNCOMPRESSED)
279         && (form != POINT_CONVERSION_HYBRID)) {
280         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
281         return 0;
282     }
283     if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
284         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
285         return 0;
286     }
287
288     if (form == 0) {
289         if (len != 1) {
290             ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
291             return 0;
292         }
293
294         return EC_POINT_set_to_infinity(group, point);
295     }
296
297     m = EC_GROUP_get_degree(group);
298     field_len = (m + 7) / 8;
299     enc_len =
300         (form ==
301          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
302
303     if (len != enc_len) {
304         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
305         return 0;
306     }
307
308 #ifndef FIPS_MODE
309     if (ctx == NULL) {
310         ctx = new_ctx = BN_CTX_new();
311         if (ctx == NULL)
312             return 0;
313     }
314 #endif
315
316     BN_CTX_start(ctx);
317     x = BN_CTX_get(ctx);
318     y = BN_CTX_get(ctx);
319     yxi = BN_CTX_get(ctx);
320     if (yxi == NULL)
321         goto err;
322
323     if (!BN_bin2bn(buf + 1, field_len, x))
324         goto err;
325     if (BN_num_bits(x) > m) {
326         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
327         goto err;
328     }
329
330     if (form == POINT_CONVERSION_COMPRESSED) {
331         if (!EC_POINT_set_compressed_coordinates(group, point, x, y_bit, ctx))
332             goto err;
333     } else {
334         if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
335             goto err;
336         if (BN_num_bits(y) > m) {
337             ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
338             goto err;
339         }
340         if (form == POINT_CONVERSION_HYBRID) {
341             if (!group->meth->field_div(group, yxi, y, x, ctx))
342                 goto err;
343             if (y_bit != BN_is_odd(yxi)) {
344                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
345                 goto err;
346             }
347         }
348
349         /*
350          * EC_POINT_set_affine_coordinates is responsible for checking that
351          * the point is on the curve.
352          */
353         if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
354             goto err;
355     }
356
357     ret = 1;
358
359  err:
360     BN_CTX_end(ctx);
361 #ifndef FIPS_MODE
362     BN_CTX_free(new_ctx);
363 #endif
364     return ret;
365 }
366 #endif