blob: c57372c94a860ea8bb90166a14be719a83450947 [file] [log] [blame]
Gabor Mezeic5328cf2022-07-18 23:13:13 +02001/**
Janos Follatha95f2042022-08-19 12:09:17 +01002 * Low-level modular bignum functions
Janos Follath63184682022-08-11 17:42:59 +01003 *
Janos Follathaf3f39c2022-08-22 09:06:32 +01004 * This interface should only be used by the higher-level modular bignum
Janos Follath63184682022-08-11 17:42:59 +01005 * module (bignum_mod.c) and the ECP module (ecp.c, ecp_curves.c). All other
Janos Follathaf3f39c2022-08-22 09:06:32 +01006 * modules should use the high-level modular bignum interface (bignum_mod.h)
Janos Follath63184682022-08-11 17:42:59 +01007 * or the legacy bignum interface (bignum.h).
Gabor Mezeic5328cf2022-07-18 23:13:13 +02008 *
Gilles Peskine7aab2fb2022-09-27 13:19:13 +02009 * This is a low-level interface to operations on integers modulo which
10 * has no protection against passing invalid arguments such as arrays of
11 * the wrong size. The functions in bignum_mod.h provide a higher-level
12 * interface that includes protections against accidental misuse, at the
13 * expense of code size and sometimes more cumbersome memory management.
Gilles Peskine7f887bd2022-09-27 13:12:30 +020014 */
15
16/*
Gabor Mezeic5328cf2022-07-18 23:13:13 +020017 * Copyright The Mbed TLS Contributors
18 * SPDX-License-Identifier: Apache-2.0
19 *
20 * Licensed under the Apache License, Version 2.0 (the "License"); you may
21 * not use this file except in compliance with the License.
22 * You may obtain a copy of the License at
23 *
24 * http://www.apache.org/licenses/LICENSE-2.0
25 *
26 * Unless required by applicable law or agreed to in writing, software
27 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
28 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
29 * See the License for the specific language governing permissions and
30 * limitations under the License.
31 */
32
Janos Follath5005edb2022-07-19 12:45:13 +010033#ifndef MBEDTLS_BIGNUM_MOD_RAW_H
34#define MBEDTLS_BIGNUM_MOD_RAW_H
Gabor Mezeic5328cf2022-07-18 23:13:13 +020035
36#include "common.h"
37
38#if defined(MBEDTLS_BIGNUM_C)
39#include "mbedtls/bignum.h"
40#endif
41
Janos Follath0ded6312022-08-09 13:34:54 +010042#include "bignum_mod.h"
43
Gabor Mezei12071d42022-09-12 16:35:58 +020044/**
Gabor Mezei4086de62022-10-14 16:29:42 +020045 * \brief Perform a safe conditional copy of an MPI which doesn't reveal
46 * whether the assignment was done or not.
Gabor Mezei12071d42022-09-12 16:35:58 +020047 *
Gabor Mezeidba26772022-10-03 17:01:02 +020048 * The size to copy is determined by \p N.
49 *
Gabor Mezei4086de62022-10-14 16:29:42 +020050 * \param[out] X The address of the destination MPI.
51 * This must be initialized. Must have enough limbs to
52 * store the full value of \p A.
53 * \param[in] A The address of the source MPI. This must be initialized.
Gabor Mezei86dfe382022-09-30 14:03:04 +020054 * \param[in] N The address of the modulus related to \p X and \p A.
Gabor Mezei12071d42022-09-12 16:35:58 +020055 * \param assign The condition deciding whether to perform the
56 * assignment or not. Must be either 0 or 1:
Gabor Mezei1c628d52022-09-27 12:13:51 +020057 * * \c 1: Perform the assignment `X = A`.
Gabor Mezei12071d42022-09-12 16:35:58 +020058 * * \c 0: Keep the original value of \p X.
59 *
60 * \note This function avoids leaking any information about whether
61 * the assignment was done or not.
62 *
63 * \warning If \p assign is neither 0 nor 1, the result of this function
64 * is indeterminate, and the resulting value in \p X might be
Gabor Mezei4086de62022-10-14 16:29:42 +020065 * neither its original value nor the value in \p A.
Gabor Mezei12071d42022-09-12 16:35:58 +020066 */
Gabor Mezei63c32822022-09-15 20:01:31 +020067void mbedtls_mpi_mod_raw_cond_assign( mbedtls_mpi_uint *X,
Gabor Mezei1c628d52022-09-27 12:13:51 +020068 const mbedtls_mpi_uint *A,
Gabor Mezeie5b85852022-09-30 13:54:02 +020069 const mbedtls_mpi_mod_modulus *N,
Gabor Mezei63c32822022-09-15 20:01:31 +020070 unsigned char assign );
Gabor Mezei12071d42022-09-12 16:35:58 +020071
72/**
Gabor Mezei4086de62022-10-14 16:29:42 +020073 * \brief Perform a safe conditional swap of two MPIs which doesn't reveal
74 * whether the swap was done or not.
Gabor Mezei12071d42022-09-12 16:35:58 +020075 *
Gabor Mezeidba26772022-10-03 17:01:02 +020076 * The size to swap is determined by \p N.
77 *
Gabor Mezei86dfe382022-09-30 14:03:04 +020078 * \param[in,out] X The address of the first MPI. This must be initialized.
79 * \param[in,out] Y The address of the second MPI. This must be initialized.
80 * \param[in] N The address of the modulus related to \p X and \p Y.
Gabor Mezei12071d42022-09-12 16:35:58 +020081 * \param swap The condition deciding whether to perform
82 * the swap or not. Must be either 0 or 1:
Gabor Mezeie5b85852022-09-30 13:54:02 +020083 * * \c 1: Swap the values of \p X and \p Y.
84 * * \c 0: Keep the original values of \p X and \p Y.
Gabor Mezei12071d42022-09-12 16:35:58 +020085 *
86 * \note This function avoids leaking any information about whether
87 * the swap was done or not.
88 *
89 * \warning If \p swap is neither 0 nor 1, the result of this function
Gabor Mezeie5b85852022-09-30 13:54:02 +020090 * is indeterminate, and both \p X and \p Y might end up with
Gabor Mezei12071d42022-09-12 16:35:58 +020091 * values different to either of the original ones.
Gabor Mezei63c32822022-09-15 20:01:31 +020092 */
Gabor Mezeie5b85852022-09-30 13:54:02 +020093void mbedtls_mpi_mod_raw_cond_swap( mbedtls_mpi_uint *X,
94 mbedtls_mpi_uint *Y,
95 const mbedtls_mpi_mod_modulus *N,
Gabor Mezei63c32822022-09-15 20:01:31 +020096 unsigned char swap );
Gabor Mezei12071d42022-09-12 16:35:58 +020097
Gabor Mezei37b06362022-08-02 17:22:18 +020098/** Import X from unsigned binary data.
99 *
Janos Follath63184682022-08-11 17:42:59 +0100100 * The MPI needs to have enough limbs to store the full value (including any
101 * most significant zero bytes in the input).
Gabor Mezei37b06362022-08-02 17:22:18 +0200102 *
Janos Follathb7a88ec2022-08-19 12:24:40 +0100103 * \param[out] X The address of the MPI. The size is determined by \p m.
104 * (In particular, it must have at least as many limbs as
105 * the modulus \p m.)
106 * \param[in] m The address of the modulus related to \p X.
107 * \param[in] input The input buffer to import from.
108 * \param input_length The length in bytes of \p input.
Gabor Mezei37b06362022-08-02 17:22:18 +0200109 *
110 * \return \c 0 if successful.
111 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't
Janos Follathb7a88ec2022-08-19 12:24:40 +0100112 * large enough to hold the value in \p input.
Janos Follath8ff07292022-08-08 08:39:52 +0100113 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation
Janos Follathdae11472022-08-08 11:50:02 +0100114 * of \p m is invalid or \p X is not less than \p m.
Gabor Mezei37b06362022-08-02 17:22:18 +0200115 */
Gabor Mezeic5328cf2022-07-18 23:13:13 +0200116int mbedtls_mpi_mod_raw_read( mbedtls_mpi_uint *X,
Janos Follath6b8a4ad2022-08-19 10:58:34 +0100117 const mbedtls_mpi_mod_modulus *m,
Janos Follathb7a88ec2022-08-19 12:24:40 +0100118 const unsigned char *input,
119 size_t input_length );
Gabor Mezeic5328cf2022-07-18 23:13:13 +0200120
Janos Follathb7a88ec2022-08-19 12:24:40 +0100121/** Export A into unsigned binary data.
Gabor Mezei37b06362022-08-02 17:22:18 +0200122 *
Janos Follathb7a88ec2022-08-19 12:24:40 +0100123 * \param[in] A The address of the MPI. The size is determined by \p m.
124 * (In particular, it must have at least as many limbs as
125 * the modulus \p m.)
126 * \param[in] m The address of the modulus related to \p A.
127 * \param[out] output The output buffer to export to.
128 * \param output_length The length in bytes of \p output.
Gabor Mezei37b06362022-08-02 17:22:18 +0200129 *
130 * \return \c 0 if successful.
Janos Follathb7a88ec2022-08-19 12:24:40 +0100131 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't
132 * large enough to hold the value of \p A.
Janos Follath8ff07292022-08-08 08:39:52 +0100133 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation
Gabor Mezei37b06362022-08-02 17:22:18 +0200134 * of \p m is invalid.
135 */
Janos Follathb7a88ec2022-08-19 12:24:40 +0100136int mbedtls_mpi_mod_raw_write( const mbedtls_mpi_uint *A,
Janos Follath6b8a4ad2022-08-19 10:58:34 +0100137 const mbedtls_mpi_mod_modulus *m,
Janos Follathb7a88ec2022-08-19 12:24:40 +0100138 unsigned char *output,
139 size_t output_length );
Gabor Mezeic5328cf2022-07-18 23:13:13 +0200140
Janos Follath5933f692022-11-02 14:35:17 +0000141/* BEGIN MERGE SLOT 1 */
142
143/* END MERGE SLOT 1 */
144
145/* BEGIN MERGE SLOT 2 */
146
147/* END MERGE SLOT 2 */
148
149/* BEGIN MERGE SLOT 3 */
150
151/* END MERGE SLOT 3 */
152
153/* BEGIN MERGE SLOT 4 */
154
155/* END MERGE SLOT 4 */
156
157/* BEGIN MERGE SLOT 5 */
Hanno Beckera45b6fe2022-11-01 13:14:28 +0000158/**
159 * \brief Perform a known-size modular addition.
160 *
161 * Calculate A + B mod N.
162 *
163 * \param[out] X The result of the modular addition.
164 * \param[in] A The left operand. This must be smaller than \p N.
165 * \param[in] B The right operand. This must be smaller than \p N.
166 * \param[in] N The modulus.
167 * \param n Number of limbs of \p X, \p A, \p B and \p N.
168 */
169void MPI_CORE(add_mod)( mbedtls_mpi_uint *X, mbedtls_mpi_uint const *A,
170 mbedtls_mpi_uint const *B, const mbedtls_mpi_uint *N,
171 size_t n );
Janos Follath5933f692022-11-02 14:35:17 +0000172/* END MERGE SLOT 5 */
173
174/* BEGIN MERGE SLOT 6 */
175
176/* END MERGE SLOT 6 */
177
178/* BEGIN MERGE SLOT 7 */
Minos Galanakisd9299c32022-11-01 16:19:07 +0000179/** Convert an MPI into Montgomery form.
Hanno Becker5ad4a932022-08-09 14:45:53 +0100180 *
181 * \param X The address of the MPI.
Minos Galanakisd9299c32022-11-01 16:19:07 +0000182 * Must have the same number of limbs as \p m.
183 * \param m The address of the modulus, which gives the size of
184 * the base `R` = 2^(biL*m->limbs).
Hanno Becker5ad4a932022-08-09 14:45:53 +0100185 *
186 * \return \c 0 if successful.
187 */
Minos Galanakisd9299c32022-11-01 16:19:07 +0000188int mbedtls_mpi_mod_raw_to_mont_rep( mbedtls_mpi_uint *X,
189 const mbedtls_mpi_mod_modulus *m );
Janos Follath5933f692022-11-02 14:35:17 +0000190
Minos Galanakisd9299c32022-11-01 16:19:07 +0000191/** Convert an MPI back from Montgomery representation.
Hanno Becker5ad4a932022-08-09 14:45:53 +0100192 *
193 * \param X The address of the MPI.
Minos Galanakisd9299c32022-11-01 16:19:07 +0000194 * Must have the same number of limbs as \p m.
195 * \param m The address of the modulus, which gives the size of
196 * the base `R`= 2^(biL*m->limbs).
Hanno Becker5ad4a932022-08-09 14:45:53 +0100197 *
198 * \return \c 0 if successful.
199 */
Minos Galanakisd9299c32022-11-01 16:19:07 +0000200int mbedtls_mpi_mod_raw_from_mont_rep( mbedtls_mpi_uint *X,
201 const mbedtls_mpi_mod_modulus *m );
Janos Follath5933f692022-11-02 14:35:17 +0000202/* END MERGE SLOT 7 */
203
204/* BEGIN MERGE SLOT 8 */
205
206/* END MERGE SLOT 8 */
207
208/* BEGIN MERGE SLOT 9 */
209
210/* END MERGE SLOT 9 */
211
212/* BEGIN MERGE SLOT 10 */
213
214/* END MERGE SLOT 10 */
215
Janos Follath5005edb2022-07-19 12:45:13 +0100216#endif /* MBEDTLS_BIGNUM_MOD_RAW_H */