1 /*
2 * Low-level modular bignum functions
3 *
4 * Copyright The Mbed TLS Contributors
5 * SPDX-License-Identifier: Apache-2.0
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20 #include "common.h"
21
22 #if defined(MBEDTLS_BIGNUM_C)
23
24 #include <string.h>
25
26 #include "mbedtls/error.h"
27 #include "mbedtls/platform_util.h"
28
29 #include "mbedtls/platform.h"
30
31 #include "bignum_core.h"
32 #include "bignum_mod_raw.h"
33 #include "bignum_mod.h"
34 #include "constant_time_internal.h"
35
36 #include "bignum_mod_raw_invasive.h"
37
mbedtls_mpi_mod_raw_cond_assign(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_mod_modulus * N,unsigned char assign)38 void mbedtls_mpi_mod_raw_cond_assign(mbedtls_mpi_uint *X,
39 const mbedtls_mpi_uint *A,
40 const mbedtls_mpi_mod_modulus *N,
41 unsigned char assign)
42 {
43 mbedtls_mpi_core_cond_assign(X, A, N->limbs, assign);
44 }
45
mbedtls_mpi_mod_raw_cond_swap(mbedtls_mpi_uint * X,mbedtls_mpi_uint * Y,const mbedtls_mpi_mod_modulus * N,unsigned char swap)46 void mbedtls_mpi_mod_raw_cond_swap(mbedtls_mpi_uint *X,
47 mbedtls_mpi_uint *Y,
48 const mbedtls_mpi_mod_modulus *N,
49 unsigned char swap)
50 {
51 mbedtls_mpi_core_cond_swap(X, Y, N->limbs, swap);
52 }
53
mbedtls_mpi_mod_raw_read(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N,const unsigned char * input,size_t input_length,mbedtls_mpi_mod_ext_rep ext_rep)54 int mbedtls_mpi_mod_raw_read(mbedtls_mpi_uint *X,
55 const mbedtls_mpi_mod_modulus *N,
56 const unsigned char *input,
57 size_t input_length,
58 mbedtls_mpi_mod_ext_rep ext_rep)
59 {
60 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
61
62 switch (ext_rep) {
63 case MBEDTLS_MPI_MOD_EXT_REP_LE:
64 ret = mbedtls_mpi_core_read_le(X, N->limbs,
65 input, input_length);
66 break;
67 case MBEDTLS_MPI_MOD_EXT_REP_BE:
68 ret = mbedtls_mpi_core_read_be(X, N->limbs,
69 input, input_length);
70 break;
71 default:
72 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
73 }
74
75 if (ret != 0) {
76 goto cleanup;
77 }
78
79 if (!mbedtls_mpi_core_lt_ct(X, N->p, N->limbs)) {
80 ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
81 goto cleanup;
82 }
83
84 cleanup:
85
86 return ret;
87 }
88
mbedtls_mpi_mod_raw_write(const mbedtls_mpi_uint * A,const mbedtls_mpi_mod_modulus * N,unsigned char * output,size_t output_length,mbedtls_mpi_mod_ext_rep ext_rep)89 int mbedtls_mpi_mod_raw_write(const mbedtls_mpi_uint *A,
90 const mbedtls_mpi_mod_modulus *N,
91 unsigned char *output,
92 size_t output_length,
93 mbedtls_mpi_mod_ext_rep ext_rep)
94 {
95 switch (ext_rep) {
96 case MBEDTLS_MPI_MOD_EXT_REP_LE:
97 return mbedtls_mpi_core_write_le(A, N->limbs,
98 output, output_length);
99 case MBEDTLS_MPI_MOD_EXT_REP_BE:
100 return mbedtls_mpi_core_write_be(A, N->limbs,
101 output, output_length);
102 default:
103 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
104 }
105 }
106
107 /* BEGIN MERGE SLOT 1 */
108
109 /* END MERGE SLOT 1 */
110
111 /* BEGIN MERGE SLOT 2 */
112
mbedtls_mpi_mod_raw_sub(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_uint * B,const mbedtls_mpi_mod_modulus * N)113 void mbedtls_mpi_mod_raw_sub(mbedtls_mpi_uint *X,
114 const mbedtls_mpi_uint *A,
115 const mbedtls_mpi_uint *B,
116 const mbedtls_mpi_mod_modulus *N)
117 {
118 mbedtls_mpi_uint c = mbedtls_mpi_core_sub(X, A, B, N->limbs);
119
120 (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) c);
121 }
122
123 #if defined(MBEDTLS_TEST_HOOKS)
124
125 MBEDTLS_STATIC_TESTABLE
mbedtls_mpi_mod_raw_fix_quasi_reduction(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)126 void mbedtls_mpi_mod_raw_fix_quasi_reduction(mbedtls_mpi_uint *X,
127 const mbedtls_mpi_mod_modulus *N)
128 {
129 mbedtls_mpi_uint c = mbedtls_mpi_core_sub(X, X, N->p, N->limbs);
130
131 (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) c);
132 }
133
134 #endif /* MBEDTLS_TEST_HOOKS */
135
mbedtls_mpi_mod_raw_mul(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_uint * B,const mbedtls_mpi_mod_modulus * N,mbedtls_mpi_uint * T)136 void mbedtls_mpi_mod_raw_mul(mbedtls_mpi_uint *X,
137 const mbedtls_mpi_uint *A,
138 const mbedtls_mpi_uint *B,
139 const mbedtls_mpi_mod_modulus *N,
140 mbedtls_mpi_uint *T)
141 {
142 mbedtls_mpi_core_montmul(X, A, B, N->limbs, N->p, N->limbs,
143 N->rep.mont.mm, T);
144 }
145
146 /* END MERGE SLOT 2 */
147
148 /* BEGIN MERGE SLOT 3 */
149
mbedtls_mpi_mod_raw_inv_prime_working_limbs(size_t AN_limbs)150 size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs(size_t AN_limbs)
151 {
152 /* mbedtls_mpi_mod_raw_inv_prime() needs a temporary for the exponent,
153 * which will be the same size as the modulus and input (AN_limbs),
154 * and additional space to pass to mbedtls_mpi_core_exp_mod(). */
155 return AN_limbs +
156 mbedtls_mpi_core_exp_mod_working_limbs(AN_limbs, AN_limbs);
157 }
158
mbedtls_mpi_mod_raw_inv_prime(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_uint * N,size_t AN_limbs,const mbedtls_mpi_uint * RR,mbedtls_mpi_uint * T)159 void mbedtls_mpi_mod_raw_inv_prime(mbedtls_mpi_uint *X,
160 const mbedtls_mpi_uint *A,
161 const mbedtls_mpi_uint *N,
162 size_t AN_limbs,
163 const mbedtls_mpi_uint *RR,
164 mbedtls_mpi_uint *T)
165 {
166 /* Inversion by power: g^|G| = 1 => g^(-1) = g^(|G|-1), and
167 * |G| = N - 1, so we want
168 * g^(|G|-1) = g^(N - 2)
169 */
170
171 /* Use the first AN_limbs of T to hold N - 2 */
172 mbedtls_mpi_uint *Nminus2 = T;
173 (void) mbedtls_mpi_core_sub_int(Nminus2, N, 2, AN_limbs);
174
175 /* Rest of T is given to exp_mod for its working space */
176 mbedtls_mpi_core_exp_mod(X,
177 A, N, AN_limbs, Nminus2, AN_limbs,
178 RR, T + AN_limbs);
179 }
180
181 /* END MERGE SLOT 3 */
182
183 /* BEGIN MERGE SLOT 4 */
184
185 /* END MERGE SLOT 4 */
186
187 /* BEGIN MERGE SLOT 5 */
mbedtls_mpi_mod_raw_add(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_uint * B,const mbedtls_mpi_mod_modulus * N)188 void mbedtls_mpi_mod_raw_add(mbedtls_mpi_uint *X,
189 const mbedtls_mpi_uint *A,
190 const mbedtls_mpi_uint *B,
191 const mbedtls_mpi_mod_modulus *N)
192 {
193 mbedtls_mpi_uint carry, borrow;
194 carry = mbedtls_mpi_core_add(X, A, B, N->limbs);
195 borrow = mbedtls_mpi_core_sub(X, X, N->p, N->limbs);
196 (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) (carry ^ borrow));
197 }
198 /* END MERGE SLOT 5 */
199
200 /* BEGIN MERGE SLOT 6 */
201
mbedtls_mpi_mod_raw_canonical_to_modulus_rep(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)202 int mbedtls_mpi_mod_raw_canonical_to_modulus_rep(
203 mbedtls_mpi_uint *X,
204 const mbedtls_mpi_mod_modulus *N)
205 {
206 switch (N->int_rep) {
207 case MBEDTLS_MPI_MOD_REP_MONTGOMERY:
208 return mbedtls_mpi_mod_raw_to_mont_rep(X, N);
209 case MBEDTLS_MPI_MOD_REP_OPT_RED:
210 return 0;
211 default:
212 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
213 }
214 }
215
mbedtls_mpi_mod_raw_modulus_to_canonical_rep(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)216 int mbedtls_mpi_mod_raw_modulus_to_canonical_rep(
217 mbedtls_mpi_uint *X,
218 const mbedtls_mpi_mod_modulus *N)
219 {
220 switch (N->int_rep) {
221 case MBEDTLS_MPI_MOD_REP_MONTGOMERY:
222 return mbedtls_mpi_mod_raw_from_mont_rep(X, N);
223 case MBEDTLS_MPI_MOD_REP_OPT_RED:
224 return 0;
225 default:
226 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
227 }
228 }
229
mbedtls_mpi_mod_raw_random(mbedtls_mpi_uint * X,mbedtls_mpi_uint min,const mbedtls_mpi_mod_modulus * N,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)230 int mbedtls_mpi_mod_raw_random(mbedtls_mpi_uint *X,
231 mbedtls_mpi_uint min,
232 const mbedtls_mpi_mod_modulus *N,
233 int (*f_rng)(void *, unsigned char *, size_t),
234 void *p_rng)
235 {
236 int ret = mbedtls_mpi_core_random(X, min, N->p, N->limbs, f_rng, p_rng);
237 if (ret != 0) {
238 return ret;
239 }
240 return mbedtls_mpi_mod_raw_canonical_to_modulus_rep(X, N);
241 }
242
243 /* END MERGE SLOT 6 */
244
245 /* BEGIN MERGE SLOT 7 */
mbedtls_mpi_mod_raw_to_mont_rep(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)246 int mbedtls_mpi_mod_raw_to_mont_rep(mbedtls_mpi_uint *X,
247 const mbedtls_mpi_mod_modulus *N)
248 {
249 mbedtls_mpi_uint *T;
250 const size_t t_limbs = mbedtls_mpi_core_montmul_working_limbs(N->limbs);
251
252 if ((T = (mbedtls_mpi_uint *) mbedtls_calloc(t_limbs, ciL)) == NULL) {
253 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
254 }
255
256 mbedtls_mpi_core_to_mont_rep(X, X, N->p, N->limbs,
257 N->rep.mont.mm, N->rep.mont.rr, T);
258
259 mbedtls_platform_zeroize(T, t_limbs * ciL);
260 mbedtls_free(T);
261 return 0;
262 }
263
mbedtls_mpi_mod_raw_from_mont_rep(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)264 int mbedtls_mpi_mod_raw_from_mont_rep(mbedtls_mpi_uint *X,
265 const mbedtls_mpi_mod_modulus *N)
266 {
267 const size_t t_limbs = mbedtls_mpi_core_montmul_working_limbs(N->limbs);
268 mbedtls_mpi_uint *T;
269
270 if ((T = (mbedtls_mpi_uint *) mbedtls_calloc(t_limbs, ciL)) == NULL) {
271 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
272 }
273
274 mbedtls_mpi_core_from_mont_rep(X, X, N->p, N->limbs, N->rep.mont.mm, T);
275
276 mbedtls_platform_zeroize(T, t_limbs * ciL);
277 mbedtls_free(T);
278 return 0;
279 }
280
mbedtls_mpi_mod_raw_neg(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_mod_modulus * N)281 void mbedtls_mpi_mod_raw_neg(mbedtls_mpi_uint *X,
282 const mbedtls_mpi_uint *A,
283 const mbedtls_mpi_mod_modulus *N)
284 {
285 mbedtls_mpi_core_sub(X, N->p, A, N->limbs);
286
287 /* If A=0 initially, then X=N now. Detect this by
288 * subtracting N and catching the carry. */
289 mbedtls_mpi_uint borrow = mbedtls_mpi_core_sub(X, X, N->p, N->limbs);
290 (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) borrow);
291 }
292 /* END MERGE SLOT 7 */
293
294 /* BEGIN MERGE SLOT 8 */
295
296 /* END MERGE SLOT 8 */
297
298 /* BEGIN MERGE SLOT 9 */
299
300 /* END MERGE SLOT 9 */
301
302 /* BEGIN MERGE SLOT 10 */
303
304 /* END MERGE SLOT 10 */
305
306 #endif /* MBEDTLS_BIGNUM_C */
307