1/*
2 * Copyright 2011-2021 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#include <openssl/symhacks.h>
19
20#include "ec_local.h"
21
22int ossl_ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group,
23                                                  EC_POINT *point,
24                                                  const BIGNUM *x_, int y_bit,
25                                                  BN_CTX *ctx)
26{
27    BN_CTX *new_ctx = NULL;
28    BIGNUM *tmp1, *tmp2, *x, *y;
29    int ret = 0;
30
31    if (ctx == NULL) {
32        ctx = new_ctx = BN_CTX_new_ex(group->libctx);
33        if (ctx == NULL)
34            return 0;
35    }
36
37    y_bit = (y_bit != 0);
38
39    BN_CTX_start(ctx);
40    tmp1 = BN_CTX_get(ctx);
41    tmp2 = BN_CTX_get(ctx);
42    x = BN_CTX_get(ctx);
43    y = BN_CTX_get(ctx);
44    if (y == NULL)
45        goto err;
46
47    /*-
48     * Recover y.  We have a Weierstrass equation
49     *     y^2 = x^3 + a*x + b,
50     * so  y  is one of the square roots of  x^3 + a*x + b.
51     */
52
53    /* tmp1 := x^3 */
54    if (!BN_nnmod(x, x_, group->field, ctx))
55        goto err;
56    if (group->meth->field_decode == 0) {
57        /* field_{sqr,mul} work on standard representation */
58        if (!group->meth->field_sqr(group, tmp2, x_, ctx))
59            goto err;
60        if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx))
61            goto err;
62    } else {
63        if (!BN_mod_sqr(tmp2, x_, group->field, ctx))
64            goto err;
65        if (!BN_mod_mul(tmp1, tmp2, x_, group->field, ctx))
66            goto err;
67    }
68
69    /* tmp1 := tmp1 + a*x */
70    if (group->a_is_minus3) {
71        if (!BN_mod_lshift1_quick(tmp2, x, group->field))
72            goto err;
73        if (!BN_mod_add_quick(tmp2, tmp2, x, group->field))
74            goto err;
75        if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, group->field))
76            goto err;
77    } else {
78        if (group->meth->field_decode) {
79            if (!group->meth->field_decode(group, tmp2, group->a, ctx))
80                goto err;
81            if (!BN_mod_mul(tmp2, tmp2, x, group->field, ctx))
82                goto err;
83        } else {
84            /* field_mul works on standard representation */
85            if (!group->meth->field_mul(group, tmp2, group->a, x, ctx))
86                goto err;
87        }
88
89        if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field))
90            goto err;
91    }
92
93    /* tmp1 := tmp1 + b */
94    if (group->meth->field_decode) {
95        if (!group->meth->field_decode(group, tmp2, group->b, ctx))
96            goto err;
97        if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field))
98            goto err;
99    } else {
100        if (!BN_mod_add_quick(tmp1, tmp1, group->b, group->field))
101            goto err;
102    }
103
104    ERR_set_mark();
105    if (!BN_mod_sqrt(y, tmp1, group->field, ctx)) {
106#ifndef FIPS_MODULE
107        unsigned long err = ERR_peek_last_error();
108
109        if (ERR_GET_LIB(err) == ERR_LIB_BN
110            && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) {
111            ERR_pop_to_mark();
112            ERR_raise(ERR_LIB_EC, EC_R_INVALID_COMPRESSED_POINT);
113        } else
114#endif
115        {
116            ERR_clear_last_mark();
117            ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
118        }
119        goto err;
120    }
121    ERR_clear_last_mark();
122
123    if (y_bit != BN_is_odd(y)) {
124        if (BN_is_zero(y)) {
125            int kron;
126
127            kron = BN_kronecker(x, group->field, ctx);
128            if (kron == -2)
129                goto err;
130
131            if (kron == 1)
132                ERR_raise(ERR_LIB_EC, EC_R_INVALID_COMPRESSION_BIT);
133            else
134                /*
135                 * BN_mod_sqrt() should have caught this error (not a square)
136                 */
137                ERR_raise(ERR_LIB_EC, EC_R_INVALID_COMPRESSED_POINT);
138            goto err;
139        }
140        if (!BN_usub(y, group->field, y))
141            goto err;
142    }
143    if (y_bit != BN_is_odd(y)) {
144        ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
145        goto err;
146    }
147
148    if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
149        goto err;
150
151    ret = 1;
152
153 err:
154    BN_CTX_end(ctx);
155    BN_CTX_free(new_ctx);
156    return ret;
157}
158
159size_t ossl_ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
160                                    point_conversion_form_t form,
161                                    unsigned char *buf, size_t len, BN_CTX *ctx)
162{
163    size_t ret;
164    BN_CTX *new_ctx = NULL;
165    int used_ctx = 0;
166    BIGNUM *x, *y;
167    size_t field_len, i, skip;
168
169    if ((form != POINT_CONVERSION_COMPRESSED)
170        && (form != POINT_CONVERSION_UNCOMPRESSED)
171        && (form != POINT_CONVERSION_HYBRID)) {
172        ERR_raise(ERR_LIB_EC, EC_R_INVALID_FORM);
173        goto err;
174    }
175
176    if (EC_POINT_is_at_infinity(group, point)) {
177        /* encodes to a single 0 octet */
178        if (buf != NULL) {
179            if (len < 1) {
180                ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL);
181                return 0;
182            }
183            buf[0] = 0;
184        }
185        return 1;
186    }
187
188    /* ret := required output buffer length */
189    field_len = BN_num_bytes(group->field);
190    ret =
191        (form ==
192         POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
193
194    /* if 'buf' is NULL, just return required length */
195    if (buf != NULL) {
196        if (len < ret) {
197            ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL);
198            goto err;
199        }
200
201        if (ctx == NULL) {
202            ctx = new_ctx = BN_CTX_new_ex(group->libctx);
203            if (ctx == NULL)
204                return 0;
205        }
206
207        BN_CTX_start(ctx);
208        used_ctx = 1;
209        x = BN_CTX_get(ctx);
210        y = BN_CTX_get(ctx);
211        if (y == NULL)
212            goto err;
213
214        if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
215            goto err;
216
217        if ((form == POINT_CONVERSION_COMPRESSED
218             || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
219            buf[0] = form + 1;
220        else
221            buf[0] = form;
222
223        i = 1;
224
225        skip = field_len - BN_num_bytes(x);
226        if (skip > field_len) {
227            ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
228            goto err;
229        }
230        while (skip > 0) {
231            buf[i++] = 0;
232            skip--;
233        }
234        skip = BN_bn2bin(x, buf + i);
235        i += skip;
236        if (i != 1 + field_len) {
237            ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
238            goto err;
239        }
240
241        if (form == POINT_CONVERSION_UNCOMPRESSED
242            || form == POINT_CONVERSION_HYBRID) {
243            skip = field_len - BN_num_bytes(y);
244            if (skip > field_len) {
245                ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
246                goto err;
247            }
248            while (skip > 0) {
249                buf[i++] = 0;
250                skip--;
251            }
252            skip = BN_bn2bin(y, buf + i);
253            i += skip;
254        }
255
256        if (i != ret) {
257            ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
258            goto err;
259        }
260    }
261
262    if (used_ctx)
263        BN_CTX_end(ctx);
264    BN_CTX_free(new_ctx);
265    return ret;
266
267 err:
268    if (used_ctx)
269        BN_CTX_end(ctx);
270    BN_CTX_free(new_ctx);
271    return 0;
272}
273
274int ossl_ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
275                                 const unsigned char *buf, size_t len,
276                                 BN_CTX *ctx)
277{
278    point_conversion_form_t form;
279    int y_bit;
280    BN_CTX *new_ctx = NULL;
281    BIGNUM *x, *y;
282    size_t field_len, enc_len;
283    int ret = 0;
284
285    if (len == 0) {
286        ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL);
287        return 0;
288    }
289    form = buf[0];
290    y_bit = form & 1;
291    form = form & ~1U;
292    if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
293        && (form != POINT_CONVERSION_UNCOMPRESSED)
294        && (form != POINT_CONVERSION_HYBRID)) {
295        ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
296        return 0;
297    }
298    if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
299        ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
300        return 0;
301    }
302
303    if (form == 0) {
304        if (len != 1) {
305            ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
306            return 0;
307        }
308
309        return EC_POINT_set_to_infinity(group, point);
310    }
311
312    field_len = BN_num_bytes(group->field);
313    enc_len =
314        (form ==
315         POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
316
317    if (len != enc_len) {
318        ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
319        return 0;
320    }
321
322    if (ctx == NULL) {
323        ctx = new_ctx = BN_CTX_new_ex(group->libctx);
324        if (ctx == NULL)
325            return 0;
326    }
327
328    BN_CTX_start(ctx);
329    x = BN_CTX_get(ctx);
330    y = BN_CTX_get(ctx);
331    if (y == NULL)
332        goto err;
333
334    if (!BN_bin2bn(buf + 1, field_len, x))
335        goto err;
336    if (BN_ucmp(x, group->field) >= 0) {
337        ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
338        goto err;
339    }
340
341    if (form == POINT_CONVERSION_COMPRESSED) {
342        if (!EC_POINT_set_compressed_coordinates(group, point, x, y_bit, ctx))
343            goto err;
344    } else {
345        if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
346            goto err;
347        if (BN_ucmp(y, group->field) >= 0) {
348            ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
349            goto err;
350        }
351        if (form == POINT_CONVERSION_HYBRID) {
352            if (y_bit != BN_is_odd(y)) {
353                ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
354                goto err;
355            }
356        }
357
358        /*
359         * EC_POINT_set_affine_coordinates is responsible for checking that
360         * the point is on the curve.
361         */
362        if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
363            goto err;
364    }
365
366    ret = 1;
367
368 err:
369    BN_CTX_end(ctx);
370    BN_CTX_free(new_ctx);
371    return ret;
372}
373