blob: 8d6e17bcda52e1f8c841e8c11b9adad46a503d6d [file] [log] [blame]
Hanno Becker71f4b0d2022-08-23 12:09:35 +01001/*
2 * Multi-precision integer library
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 "mbedtls/bignum.h"
25#include "bignum_core.h"
26#include "bn_mul.h"
Tom Cosgrove25237912022-08-19 08:43:56 +010027#include "constant_time_internal.h"
Hanno Becker71f4b0d2022-08-23 12:09:35 +010028
29#include <string.h>
30
Tom Cosgrove90c426b2022-08-23 16:15:19 +010031void mbedtls_mpi_core_montmul( mbedtls_mpi_uint *X,
32 const mbedtls_mpi_uint *A,
33 const mbedtls_mpi_uint *B,
34 size_t B_len,
35 const mbedtls_mpi_uint *N,
36 size_t n,
37 mbedtls_mpi_uint mm,
38 mbedtls_mpi_uint *T )
Hanno Becker71f4b0d2022-08-23 12:09:35 +010039{
Tom Cosgrove4641ec62022-08-17 06:56:08 +010040 memset( T, 0, ( 2 * n + 1 ) * ciL );
Hanno Becker71f4b0d2022-08-23 12:09:35 +010041
42 for( size_t i = 0; i < n; i++, T++ )
43 {
44 mbedtls_mpi_uint u0, u1;
45 /* T = (T + u0*B + u1*N) / 2^biL */
46 u0 = A[i];
47 u1 = ( T[0] + u0 * B[0] ) * mm;
48
Tom Cosgrove90c426b2022-08-23 16:15:19 +010049 (void) mbedtls_mpi_core_mla( T, n + 2, B, B_len, u0 );
50 (void) mbedtls_mpi_core_mla( T, n + 2, N, n, u1 );
Hanno Becker71f4b0d2022-08-23 12:09:35 +010051 }
52
Tom Cosgrove25237912022-08-19 08:43:56 +010053 /* It's possible that the result in T is > N, and so we might need to subtract N */
Hanno Becker71f4b0d2022-08-23 12:09:35 +010054
Tom Cosgrove25237912022-08-19 08:43:56 +010055 mbedtls_mpi_uint carry = T[n];
56 mbedtls_mpi_uint borrow = mbedtls_mpi_core_sub( X, T, N, n );
57
58 /*
59 * Both carry and borrow can only be 0 or 1.
60 *
61 * If carry = 1, the result in T must be > N by definition, and the subtraction
62 * using only n limbs will create borrow, but that will have the correct
63 * final result.
64 *
65 * i.e. (carry, borrow) of (1, 1) => return X
66 *
67 * If carry = 0, then we want to use the result of the subtraction iff
68 * borrow = 0.
69 *
70 * i.e. (carry, borrow) of (0, 0) => return X
71 * (0, 1) => return T
72 *
73 * We've confirmed that the unit tests exercise this function with all 3 of
74 * the valid (carry, borrow) combinations (listed above), and that we don't
75 * see (carry, borrow) = (1, 0).
76 *
77 * So the correct return value is already in X if (carry ^ borrow) = 0,
78 * but is in (the lower n limbs of) T if (carry ^ borrow) = 1.
79 */
80 mbedtls_ct_mpi_uint_cond_assign( n, X, T, (unsigned char) ( carry ^ borrow ) );
Hanno Becker71f4b0d2022-08-23 12:09:35 +010081}
82
Tom Cosgrove79b70f62022-08-17 06:17:00 +010083/*
84 * Fast Montgomery initialization (thanks to Tom St Denis).
85 */
86mbedtls_mpi_uint mbedtls_mpi_montg_init( mbedtls_mpi_uint m0 )
87{
88 mbedtls_mpi_uint x = m0;
89
90 x += ( ( m0 + 2 ) & 4 ) << 1;
91
92 for( unsigned int i = biL; i >= 8; i /= 2 )
93 x *= ( 2 - ( m0 * x ) );
94
95 return( ~x + 1 );
96}
97
Tom Cosgrove90c426b2022-08-23 16:15:19 +010098mbedtls_mpi_uint mbedtls_mpi_core_mla( mbedtls_mpi_uint *d, size_t d_len,
99 const mbedtls_mpi_uint *s, size_t s_len,
100 mbedtls_mpi_uint b )
Hanno Becker71f4b0d2022-08-23 12:09:35 +0100101{
102 mbedtls_mpi_uint c = 0; /* carry */
103 if( d_len < s_len )
104 s_len = d_len;
105 size_t excess_len = d_len - s_len;
106 size_t steps_x8 = s_len / 8;
107 size_t steps_x1 = s_len & 7;
108
109 while( steps_x8-- )
110 {
111 MULADDC_X8_INIT
112 MULADDC_X8_CORE
113 MULADDC_X8_STOP
114 }
115
116 while( steps_x1-- )
117 {
118 MULADDC_X1_INIT
119 MULADDC_X1_CORE
120 MULADDC_X1_STOP
121 }
122
123 while( excess_len-- )
124 {
125 *d += c; c = ( *d < c ); d++;
126 }
127
128 return( c );
129}
130
Tom Cosgrove90c426b2022-08-23 16:15:19 +0100131mbedtls_mpi_uint mbedtls_mpi_core_sub( mbedtls_mpi_uint *d,
132 const mbedtls_mpi_uint *l,
133 const mbedtls_mpi_uint *r,
134 size_t n )
Hanno Becker71f4b0d2022-08-23 12:09:35 +0100135{
Tom Cosgrove4641ec62022-08-17 06:56:08 +0100136 mbedtls_mpi_uint c = 0;
Hanno Becker71f4b0d2022-08-23 12:09:35 +0100137
138 for( size_t i = 0; i < n; i++ )
139 {
Tom Cosgrove4641ec62022-08-17 06:56:08 +0100140 mbedtls_mpi_uint z = ( l[i] < c );
141 mbedtls_mpi_uint t = l[i] - c;
142 c = ( t < r[i] ) + z;
143 d[i] = t - r[i];
Hanno Becker71f4b0d2022-08-23 12:09:35 +0100144 }
145
146 return( c );
147}
148
Tom Cosgrove90c426b2022-08-23 16:15:19 +0100149mbedtls_mpi_uint mbedtls_mpi_core_add_if( mbedtls_mpi_uint *d,
150 const mbedtls_mpi_uint *r,
151 size_t n,
152 unsigned cond )
Hanno Becker71f4b0d2022-08-23 12:09:35 +0100153{
154 mbedtls_mpi_uint c = 0, t;
155 for( size_t i = 0; i < n; i++ )
156 {
157 mbedtls_mpi_uint add = cond * r[i];
158 t = c;
159 t += d[i]; c = ( t < d[i] );
160 t += add; c += ( t < add );
161 d[i] = t;
162 }
163 return( c );
164}
165
166#endif /* MBEDTLS_BIGNUM_C */