Hanno Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 1 | /* |
| 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 Cosgrove | 2523791 | 2022-08-19 08:43:56 +0100 | [diff] [blame^] | 27 | #include "constant_time_internal.h" |
Hanno Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 28 | |
| 29 | #include <string.h> |
| 30 | |
Tom Cosgrove | 90c426b | 2022-08-23 16:15:19 +0100 | [diff] [blame] | 31 | void 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 Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 39 | { |
Tom Cosgrove | 4641ec6 | 2022-08-17 06:56:08 +0100 | [diff] [blame] | 40 | memset( T, 0, ( 2 * n + 1 ) * ciL ); |
Hanno Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 41 | |
| 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 Cosgrove | 90c426b | 2022-08-23 16:15:19 +0100 | [diff] [blame] | 49 | (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 Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 51 | } |
| 52 | |
Tom Cosgrove | 2523791 | 2022-08-19 08:43:56 +0100 | [diff] [blame^] | 53 | /* It's possible that the result in T is > N, and so we might need to subtract N */ |
Hanno Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 54 | |
Tom Cosgrove | 2523791 | 2022-08-19 08:43:56 +0100 | [diff] [blame^] | 55 | 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 Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 81 | } |
| 82 | |
Tom Cosgrove | 79b70f6 | 2022-08-17 06:17:00 +0100 | [diff] [blame] | 83 | /* |
| 84 | * Fast Montgomery initialization (thanks to Tom St Denis). |
| 85 | */ |
| 86 | mbedtls_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 Cosgrove | 90c426b | 2022-08-23 16:15:19 +0100 | [diff] [blame] | 98 | mbedtls_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 Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 101 | { |
| 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 Cosgrove | 90c426b | 2022-08-23 16:15:19 +0100 | [diff] [blame] | 131 | mbedtls_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 Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 135 | { |
Tom Cosgrove | 4641ec6 | 2022-08-17 06:56:08 +0100 | [diff] [blame] | 136 | mbedtls_mpi_uint c = 0; |
Hanno Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 137 | |
| 138 | for( size_t i = 0; i < n; i++ ) |
| 139 | { |
Tom Cosgrove | 4641ec6 | 2022-08-17 06:56:08 +0100 | [diff] [blame] | 140 | 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 Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 144 | } |
| 145 | |
| 146 | return( c ); |
| 147 | } |
| 148 | |
Tom Cosgrove | 90c426b | 2022-08-23 16:15:19 +0100 | [diff] [blame] | 149 | mbedtls_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 Becker | 71f4b0d | 2022-08-23 12:09:35 +0100 | [diff] [blame] | 153 | { |
| 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 */ |