1/*
2 *  Low-level modular bignum functions
3 *
4 *  Copyright The Mbed TLS Contributors
5 *  SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 */
7
8#include "common.h"
9
10#if defined(MBEDTLS_BIGNUM_C) && defined(MBEDTLS_ECP_WITH_MPI_UINT)
11
12#include <string.h>
13
14#include "mbedtls/error.h"
15#include "mbedtls/platform_util.h"
16
17#include "mbedtls/platform.h"
18
19#include "bignum_core.h"
20#include "bignum_mod_raw.h"
21#include "bignum_mod.h"
22#include "constant_time_internal.h"
23
24#include "bignum_mod_raw_invasive.h"
25
26void mbedtls_mpi_mod_raw_cond_assign(mbedtls_mpi_uint *X,
27                                     const mbedtls_mpi_uint *A,
28                                     const mbedtls_mpi_mod_modulus *N,
29                                     unsigned char assign)
30{
31    mbedtls_mpi_core_cond_assign(X, A, N->limbs, mbedtls_ct_bool(assign));
32}
33
34void mbedtls_mpi_mod_raw_cond_swap(mbedtls_mpi_uint *X,
35                                   mbedtls_mpi_uint *Y,
36                                   const mbedtls_mpi_mod_modulus *N,
37                                   unsigned char swap)
38{
39    mbedtls_mpi_core_cond_swap(X, Y, N->limbs, mbedtls_ct_bool(swap));
40}
41
42int mbedtls_mpi_mod_raw_read(mbedtls_mpi_uint *X,
43                             const mbedtls_mpi_mod_modulus *N,
44                             const unsigned char *input,
45                             size_t input_length,
46                             mbedtls_mpi_mod_ext_rep ext_rep)
47{
48    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
49
50    switch (ext_rep) {
51        case MBEDTLS_MPI_MOD_EXT_REP_LE:
52            ret = mbedtls_mpi_core_read_le(X, N->limbs,
53                                           input, input_length);
54            break;
55        case MBEDTLS_MPI_MOD_EXT_REP_BE:
56            ret = mbedtls_mpi_core_read_be(X, N->limbs,
57                                           input, input_length);
58            break;
59        default:
60            return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
61    }
62
63    if (ret != 0) {
64        goto cleanup;
65    }
66
67    if (!mbedtls_mpi_core_lt_ct(X, N->p, N->limbs)) {
68        ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
69        goto cleanup;
70    }
71
72cleanup:
73
74    return ret;
75}
76
77int mbedtls_mpi_mod_raw_write(const mbedtls_mpi_uint *A,
78                              const mbedtls_mpi_mod_modulus *N,
79                              unsigned char *output,
80                              size_t output_length,
81                              mbedtls_mpi_mod_ext_rep ext_rep)
82{
83    switch (ext_rep) {
84        case MBEDTLS_MPI_MOD_EXT_REP_LE:
85            return mbedtls_mpi_core_write_le(A, N->limbs,
86                                             output, output_length);
87        case MBEDTLS_MPI_MOD_EXT_REP_BE:
88            return mbedtls_mpi_core_write_be(A, N->limbs,
89                                             output, output_length);
90        default:
91            return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
92    }
93}
94
95void mbedtls_mpi_mod_raw_sub(mbedtls_mpi_uint *X,
96                             const mbedtls_mpi_uint *A,
97                             const mbedtls_mpi_uint *B,
98                             const mbedtls_mpi_mod_modulus *N)
99{
100    mbedtls_mpi_uint c = mbedtls_mpi_core_sub(X, A, B, N->limbs);
101
102    (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) c);
103}
104
105MBEDTLS_STATIC_TESTABLE
106void mbedtls_mpi_mod_raw_fix_quasi_reduction(mbedtls_mpi_uint *X,
107                                             const mbedtls_mpi_mod_modulus *N)
108{
109    mbedtls_mpi_uint c = mbedtls_mpi_core_sub(X, X, N->p, N->limbs);
110
111    (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) c);
112}
113
114
115void mbedtls_mpi_mod_raw_mul(mbedtls_mpi_uint *X,
116                             const mbedtls_mpi_uint *A,
117                             const mbedtls_mpi_uint *B,
118                             const mbedtls_mpi_mod_modulus *N,
119                             mbedtls_mpi_uint *T)
120{
121    /* Standard (A * B) multiplication stored into pre-allocated T
122     * buffer of fixed limb size of (2N + 1).
123     *
124     * The space may not not fully filled by when
125     * MBEDTLS_MPI_MOD_REP_OPT_RED is used. */
126    const size_t T_limbs = BITS_TO_LIMBS(N->bits) * 2;
127    switch (N->int_rep) {
128        case MBEDTLS_MPI_MOD_REP_MONTGOMERY:
129            mbedtls_mpi_core_montmul(X, A, B, N->limbs, N->p, N->limbs,
130                                     N->rep.mont.mm, T);
131            break;
132        case MBEDTLS_MPI_MOD_REP_OPT_RED:
133            mbedtls_mpi_core_mul(T, A, N->limbs, B, N->limbs);
134
135            /* Optimised Reduction */
136            (*N->rep.ored.modp)(T, T_limbs);
137
138            /* Convert back to canonical representation */
139            mbedtls_mpi_mod_raw_fix_quasi_reduction(T, N);
140            memcpy(X, T, N->limbs * sizeof(mbedtls_mpi_uint));
141            break;
142        default:
143            break;
144    }
145
146}
147
148size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs(size_t AN_limbs)
149{
150    /* mbedtls_mpi_mod_raw_inv_prime() needs a temporary for the exponent,
151     * which will be the same size as the modulus and input (AN_limbs),
152     * and additional space to pass to mbedtls_mpi_core_exp_mod(). */
153    return AN_limbs +
154           mbedtls_mpi_core_exp_mod_working_limbs(AN_limbs, AN_limbs);
155}
156
157void mbedtls_mpi_mod_raw_inv_prime(mbedtls_mpi_uint *X,
158                                   const mbedtls_mpi_uint *A,
159                                   const mbedtls_mpi_uint *N,
160                                   size_t AN_limbs,
161                                   const mbedtls_mpi_uint *RR,
162                                   mbedtls_mpi_uint *T)
163{
164    /* Inversion by power: g^|G| = 1 => g^(-1) = g^(|G|-1), and
165     *                       |G| = N - 1, so we want
166     *                 g^(|G|-1) = g^(N - 2)
167     */
168
169    /* Use the first AN_limbs of T to hold N - 2 */
170    mbedtls_mpi_uint *Nminus2 = T;
171    (void) mbedtls_mpi_core_sub_int(Nminus2, N, 2, AN_limbs);
172
173    /* Rest of T is given to exp_mod for its working space */
174    mbedtls_mpi_core_exp_mod(X,
175                             A, N, AN_limbs, Nminus2, AN_limbs,
176                             RR, T + AN_limbs);
177}
178
179void mbedtls_mpi_mod_raw_add(mbedtls_mpi_uint *X,
180                             const mbedtls_mpi_uint *A,
181                             const mbedtls_mpi_uint *B,
182                             const mbedtls_mpi_mod_modulus *N)
183{
184    mbedtls_mpi_uint carry, borrow;
185    carry  = mbedtls_mpi_core_add(X, A, B, N->limbs);
186    borrow = mbedtls_mpi_core_sub(X, X, N->p, N->limbs);
187    (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) (carry ^ borrow));
188}
189
190int mbedtls_mpi_mod_raw_canonical_to_modulus_rep(
191    mbedtls_mpi_uint *X,
192    const mbedtls_mpi_mod_modulus *N)
193{
194    switch (N->int_rep) {
195        case MBEDTLS_MPI_MOD_REP_MONTGOMERY:
196            return mbedtls_mpi_mod_raw_to_mont_rep(X, N);
197        case MBEDTLS_MPI_MOD_REP_OPT_RED:
198            return 0;
199        default:
200            return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
201    }
202}
203
204int mbedtls_mpi_mod_raw_modulus_to_canonical_rep(
205    mbedtls_mpi_uint *X,
206    const mbedtls_mpi_mod_modulus *N)
207{
208    switch (N->int_rep) {
209        case MBEDTLS_MPI_MOD_REP_MONTGOMERY:
210            return mbedtls_mpi_mod_raw_from_mont_rep(X, N);
211        case MBEDTLS_MPI_MOD_REP_OPT_RED:
212            return 0;
213        default:
214            return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
215    }
216}
217
218int mbedtls_mpi_mod_raw_random(mbedtls_mpi_uint *X,
219                               mbedtls_mpi_uint min,
220                               const mbedtls_mpi_mod_modulus *N,
221                               int (*f_rng)(void *, unsigned char *, size_t),
222                               void *p_rng)
223{
224    int ret = mbedtls_mpi_core_random(X, min, N->p, N->limbs, f_rng, p_rng);
225    if (ret != 0) {
226        return ret;
227    }
228    return mbedtls_mpi_mod_raw_canonical_to_modulus_rep(X, N);
229}
230
231int mbedtls_mpi_mod_raw_to_mont_rep(mbedtls_mpi_uint *X,
232                                    const mbedtls_mpi_mod_modulus *N)
233{
234    mbedtls_mpi_uint *T;
235    const size_t t_limbs = mbedtls_mpi_core_montmul_working_limbs(N->limbs);
236
237    if ((T = (mbedtls_mpi_uint *) mbedtls_calloc(t_limbs, ciL)) == NULL) {
238        return MBEDTLS_ERR_MPI_ALLOC_FAILED;
239    }
240
241    mbedtls_mpi_core_to_mont_rep(X, X, N->p, N->limbs,
242                                 N->rep.mont.mm, N->rep.mont.rr, T);
243
244    mbedtls_zeroize_and_free(T, t_limbs * ciL);
245    return 0;
246}
247
248int mbedtls_mpi_mod_raw_from_mont_rep(mbedtls_mpi_uint *X,
249                                      const mbedtls_mpi_mod_modulus *N)
250{
251    const size_t t_limbs = mbedtls_mpi_core_montmul_working_limbs(N->limbs);
252    mbedtls_mpi_uint *T;
253
254    if ((T = (mbedtls_mpi_uint *) mbedtls_calloc(t_limbs, ciL)) == NULL) {
255        return MBEDTLS_ERR_MPI_ALLOC_FAILED;
256    }
257
258    mbedtls_mpi_core_from_mont_rep(X, X, N->p, N->limbs, N->rep.mont.mm, T);
259
260    mbedtls_zeroize_and_free(T, t_limbs * ciL);
261    return 0;
262}
263
264void mbedtls_mpi_mod_raw_neg(mbedtls_mpi_uint *X,
265                             const mbedtls_mpi_uint *A,
266                             const mbedtls_mpi_mod_modulus *N)
267{
268    mbedtls_mpi_core_sub(X, N->p, A, N->limbs);
269
270    /* If A=0 initially, then X=N now. Detect this by
271     * subtracting N and catching the carry. */
272    mbedtls_mpi_uint borrow = mbedtls_mpi_core_sub(X, X, N->p, N->limbs);
273    (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) borrow);
274}
275
276#endif /* MBEDTLS_BIGNUM_C && MBEDTLS_ECP_WITH_MPI_UINT */
277