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