1/*
2 * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License").  You may not use
5 * this file except in compliance with the License.  You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10#include "internal/cryptlib.h"
11#include "bn_local.h"
12
13void BN_RECP_CTX_init(BN_RECP_CTX *recp)
14{
15    memset(recp, 0, sizeof(*recp));
16    bn_init(&(recp->N));
17    bn_init(&(recp->Nr));
18}
19
20BN_RECP_CTX *BN_RECP_CTX_new(void)
21{
22    BN_RECP_CTX *ret;
23
24    if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
25        ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE);
26        return NULL;
27    }
28
29    bn_init(&(ret->N));
30    bn_init(&(ret->Nr));
31    ret->flags = BN_FLG_MALLOCED;
32    return ret;
33}
34
35void BN_RECP_CTX_free(BN_RECP_CTX *recp)
36{
37    if (recp == NULL)
38        return;
39    BN_free(&recp->N);
40    BN_free(&recp->Nr);
41    if (recp->flags & BN_FLG_MALLOCED)
42        OPENSSL_free(recp);
43}
44
45int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)
46{
47    if (BN_is_zero(d) || !BN_copy(&(recp->N), d))
48        return 0;
49    BN_zero(&(recp->Nr));
50    recp->num_bits = BN_num_bits(d);
51    recp->shift = 0;
52    return 1;
53}
54
55int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
56                          BN_RECP_CTX *recp, BN_CTX *ctx)
57{
58    int ret = 0;
59    BIGNUM *a;
60    const BIGNUM *ca;
61
62    BN_CTX_start(ctx);
63    if ((a = BN_CTX_get(ctx)) == NULL)
64        goto err;
65    if (y != NULL) {
66        if (x == y) {
67            if (!BN_sqr(a, x, ctx))
68                goto err;
69        } else {
70            if (!BN_mul(a, x, y, ctx))
71                goto err;
72        }
73        ca = a;
74    } else
75        ca = x;                 /* Just do the mod */
76
77    ret = BN_div_recp(NULL, r, ca, recp, ctx);
78 err:
79    BN_CTX_end(ctx);
80    bn_check_top(r);
81    return ret;
82}
83
84int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
85                BN_RECP_CTX *recp, BN_CTX *ctx)
86{
87    int i, j, ret = 0;
88    BIGNUM *a, *b, *d, *r;
89
90    BN_CTX_start(ctx);
91    d = (dv != NULL) ? dv : BN_CTX_get(ctx);
92    r = (rem != NULL) ? rem : BN_CTX_get(ctx);
93    a = BN_CTX_get(ctx);
94    b = BN_CTX_get(ctx);
95    if (b == NULL)
96        goto err;
97
98    if (BN_ucmp(m, &(recp->N)) < 0) {
99        BN_zero(d);
100        if (!BN_copy(r, m)) {
101            BN_CTX_end(ctx);
102            return 0;
103        }
104        BN_CTX_end(ctx);
105        return 1;
106    }
107
108    /*
109     * We want the remainder Given input of ABCDEF / ab we need multiply
110     * ABCDEF by 3 digests of the reciprocal of ab
111     */
112
113    /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
114    i = BN_num_bits(m);
115    j = recp->num_bits << 1;
116    if (j > i)
117        i = j;
118
119    /* Nr := round(2^i / N) */
120    if (i != recp->shift)
121        recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);
122    /* BN_reciprocal could have returned -1 for an error */
123    if (recp->shift == -1)
124        goto err;
125
126    /*-
127     * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
128     *    = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
129     *   <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
130     *    = |m/N|
131     */
132    if (!BN_rshift(a, m, recp->num_bits))
133        goto err;
134    if (!BN_mul(b, a, &(recp->Nr), ctx))
135        goto err;
136    if (!BN_rshift(d, b, i - recp->num_bits))
137        goto err;
138    d->neg = 0;
139
140    if (!BN_mul(b, &(recp->N), d, ctx))
141        goto err;
142    if (!BN_usub(r, m, b))
143        goto err;
144    r->neg = 0;
145
146    j = 0;
147    while (BN_ucmp(r, &(recp->N)) >= 0) {
148        if (j++ > 2) {
149            ERR_raise(ERR_LIB_BN, BN_R_BAD_RECIPROCAL);
150            goto err;
151        }
152        if (!BN_usub(r, r, &(recp->N)))
153            goto err;
154        if (!BN_add_word(d, 1))
155            goto err;
156    }
157
158    r->neg = BN_is_zero(r) ? 0 : m->neg;
159    d->neg = m->neg ^ recp->N.neg;
160    ret = 1;
161 err:
162    BN_CTX_end(ctx);
163    bn_check_top(dv);
164    bn_check_top(rem);
165    return ret;
166}
167
168/*
169 * len is the expected size of the result We actually calculate with an extra
170 * word of precision, so we can do faster division if the remainder is not
171 * required.
172 */
173/* r := 2^len / m */
174int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)
175{
176    int ret = -1;
177    BIGNUM *t;
178
179    BN_CTX_start(ctx);
180    if ((t = BN_CTX_get(ctx)) == NULL)
181        goto err;
182
183    if (!BN_set_bit(t, len))
184        goto err;
185
186    if (!BN_div(r, NULL, t, m, ctx))
187        goto err;
188
189    ret = len;
190 err:
191    bn_check_top(r);
192    BN_CTX_end(ctx);
193    return ret;
194}
195