Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Multi-precision integer library |
| 3 | * |
Manuel Pégourié-Gonnard | 6fb8187 | 2015-07-27 11:11:48 +0200 | [diff] [blame] | 4 | * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved |
Bence Szépkúti | 4e9f712 | 2020-06-05 13:02:18 +0200 | [diff] [blame] | 5 | * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later |
| 6 | * |
| 7 | * This file is provided under the Apache License 2.0, or the |
| 8 | * GNU General Public License v2.0 or later. |
| 9 | * |
| 10 | * ********** |
| 11 | * Apache License 2.0: |
Manuel Pégourié-Gonnard | 37ff140 | 2015-09-04 14:21:07 +0200 | [diff] [blame] | 12 | * |
| 13 | * Licensed under the Apache License, Version 2.0 (the "License"); you may |
| 14 | * not use this file except in compliance with the License. |
| 15 | * You may obtain a copy of the License at |
| 16 | * |
| 17 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 18 | * |
| 19 | * Unless required by applicable law or agreed to in writing, software |
| 20 | * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| 21 | * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 22 | * See the License for the specific language governing permissions and |
| 23 | * limitations under the License. |
Paul Bakker | b96f154 | 2010-07-18 20:36:00 +0000 | [diff] [blame] | 24 | * |
Bence Szépkúti | 4e9f712 | 2020-06-05 13:02:18 +0200 | [diff] [blame] | 25 | * ********** |
| 26 | * |
| 27 | * ********** |
| 28 | * GNU General Public License v2.0 or later: |
| 29 | * |
| 30 | * This program is free software; you can redistribute it and/or modify |
| 31 | * it under the terms of the GNU General Public License as published by |
| 32 | * the Free Software Foundation; either version 2 of the License, or |
| 33 | * (at your option) any later version. |
| 34 | * |
| 35 | * This program is distributed in the hope that it will be useful, |
| 36 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 37 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 38 | * GNU General Public License for more details. |
| 39 | * |
| 40 | * You should have received a copy of the GNU General Public License along |
| 41 | * with this program; if not, write to the Free Software Foundation, Inc., |
| 42 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
| 43 | * |
| 44 | * ********** |
| 45 | * |
Manuel Pégourié-Gonnard | fe44643 | 2015-03-06 13:17:10 +0000 | [diff] [blame] | 46 | * This file is part of mbed TLS (https://tls.mbed.org) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 47 | */ |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 48 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 49 | /* |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 50 | * The following sources were referenced in the design of this Multi-precision |
| 51 | * Integer library: |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 52 | * |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 53 | * [1] Handbook of Applied Cryptography - 1997 |
| 54 | * Menezes, van Oorschot and Vanstone |
| 55 | * |
| 56 | * [2] Multi-Precision Math |
| 57 | * Tom St Denis |
| 58 | * https://github.com/libtom/libtommath/blob/develop/tommath.pdf |
| 59 | * |
| 60 | * [3] GNU Multi-Precision Arithmetic Library |
| 61 | * https://gmplib.org/manual/index.html |
| 62 | * |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 63 | */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 64 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 65 | #if !defined(MBEDTLS_CONFIG_FILE) |
Manuel Pégourié-Gonnard | 7f80997 | 2015-03-09 17:05:11 +0000 | [diff] [blame] | 66 | #include "mbedtls/config.h" |
Manuel Pégourié-Gonnard | cef4ad2 | 2014-04-29 12:39:06 +0200 | [diff] [blame] | 67 | #else |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 68 | #include MBEDTLS_CONFIG_FILE |
Manuel Pégourié-Gonnard | cef4ad2 | 2014-04-29 12:39:06 +0200 | [diff] [blame] | 69 | #endif |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 70 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 71 | #if defined(MBEDTLS_BIGNUM_C) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 72 | |
Manuel Pégourié-Gonnard | 7f80997 | 2015-03-09 17:05:11 +0000 | [diff] [blame] | 73 | #include "mbedtls/bignum.h" |
| 74 | #include "mbedtls/bn_mul.h" |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 75 | |
Rich Evans | 00ab470 | 2015-02-06 13:43:58 +0000 | [diff] [blame] | 76 | #include <string.h> |
| 77 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 78 | #if defined(MBEDTLS_PLATFORM_C) |
Manuel Pégourié-Gonnard | 7f80997 | 2015-03-09 17:05:11 +0000 | [diff] [blame] | 79 | #include "mbedtls/platform.h" |
Paul Bakker | 6e339b5 | 2013-07-03 13:37:05 +0200 | [diff] [blame] | 80 | #else |
Rich Evans | 00ab470 | 2015-02-06 13:43:58 +0000 | [diff] [blame] | 81 | #include <stdio.h> |
| 82 | #include <stdlib.h> |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 83 | #define mbedtls_printf printf |
Manuel Pégourié-Gonnard | 7551cb9 | 2015-05-26 16:04:06 +0200 | [diff] [blame] | 84 | #define mbedtls_calloc calloc |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 85 | #define mbedtls_free free |
Paul Bakker | 6e339b5 | 2013-07-03 13:37:05 +0200 | [diff] [blame] | 86 | #endif |
| 87 | |
Paul Bakker | 3461772 | 2014-06-13 17:20:13 +0200 | [diff] [blame] | 88 | /* Implementation that should never be optimized out by the compiler */ |
Alexey Skalozub | e17a8da | 2016-01-13 17:19:33 +0200 | [diff] [blame] | 89 | static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n ) { |
Alexey Skalozub | 3d53f41 | 2016-01-13 16:53:40 +0200 | [diff] [blame] | 90 | volatile mbedtls_mpi_uint *p = v; while( n-- ) *p++ = 0; |
Paul Bakker | 3461772 | 2014-06-13 17:20:13 +0200 | [diff] [blame] | 91 | } |
| 92 | |
Hanno Becker | 8880711 | 2017-10-18 12:41:30 +0100 | [diff] [blame] | 93 | /* Implementation that should never be optimized out by the compiler */ |
| 94 | static void mbedtls_zeroize( void *v, size_t n ) { |
| 95 | volatile unsigned char *p = v; while( n-- ) *p++ = 0; |
| 96 | } |
| 97 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 98 | #define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 99 | #define biL (ciL << 3) /* bits in limb */ |
| 100 | #define biH (ciL << 2) /* half limb size */ |
| 101 | |
Manuel Pégourié-Gonnard | 2d70834 | 2015-10-05 15:23:11 +0100 | [diff] [blame] | 102 | #define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */ |
| 103 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 104 | /* |
| 105 | * Convert between bits/chars and number of limbs |
Manuel Pégourié-Gonnard | 58fb495 | 2015-09-28 13:48:04 +0200 | [diff] [blame] | 106 | * Divide first in order to avoid potential overflows |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 107 | */ |
Manuel Pégourié-Gonnard | 58fb495 | 2015-09-28 13:48:04 +0200 | [diff] [blame] | 108 | #define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) ) |
| 109 | #define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 110 | |
| 111 | /* |
Paul Bakker | 6c591fa | 2011-05-05 11:49:20 +0000 | [diff] [blame] | 112 | * Initialize one MPI |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 113 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 114 | void mbedtls_mpi_init( mbedtls_mpi *X ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 115 | { |
Paul Bakker | 6c591fa | 2011-05-05 11:49:20 +0000 | [diff] [blame] | 116 | if( X == NULL ) |
| 117 | return; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 118 | |
Paul Bakker | 6c591fa | 2011-05-05 11:49:20 +0000 | [diff] [blame] | 119 | X->s = 1; |
| 120 | X->n = 0; |
| 121 | X->p = NULL; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 122 | } |
| 123 | |
| 124 | /* |
Paul Bakker | 6c591fa | 2011-05-05 11:49:20 +0000 | [diff] [blame] | 125 | * Unallocate one MPI |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 126 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 127 | void mbedtls_mpi_free( mbedtls_mpi *X ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 128 | { |
Paul Bakker | 6c591fa | 2011-05-05 11:49:20 +0000 | [diff] [blame] | 129 | if( X == NULL ) |
| 130 | return; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 131 | |
Paul Bakker | 6c591fa | 2011-05-05 11:49:20 +0000 | [diff] [blame] | 132 | if( X->p != NULL ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 133 | { |
Alexey Skalozub | e17a8da | 2016-01-13 17:19:33 +0200 | [diff] [blame] | 134 | mbedtls_mpi_zeroize( X->p, X->n ); |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 135 | mbedtls_free( X->p ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 136 | } |
| 137 | |
Paul Bakker | 6c591fa | 2011-05-05 11:49:20 +0000 | [diff] [blame] | 138 | X->s = 1; |
| 139 | X->n = 0; |
| 140 | X->p = NULL; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 141 | } |
| 142 | |
| 143 | /* |
| 144 | * Enlarge to the specified number of limbs |
| 145 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 146 | int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 147 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 148 | mbedtls_mpi_uint *p; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 149 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 150 | if( nblimbs > MBEDTLS_MPI_MAX_LIMBS ) |
Manuel Pégourié-Gonnard | 6a8ca33 | 2015-05-28 09:33:39 +0200 | [diff] [blame] | 151 | return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); |
Paul Bakker | f968857 | 2011-05-05 10:00:45 +0000 | [diff] [blame] | 152 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 153 | if( X->n < nblimbs ) |
| 154 | { |
Simon Butcher | 2917689 | 2016-05-20 00:19:09 +0100 | [diff] [blame] | 155 | if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL ) |
Manuel Pégourié-Gonnard | 6a8ca33 | 2015-05-28 09:33:39 +0200 | [diff] [blame] | 156 | return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 157 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 158 | if( X->p != NULL ) |
| 159 | { |
| 160 | memcpy( p, X->p, X->n * ciL ); |
Alexey Skalozub | e17a8da | 2016-01-13 17:19:33 +0200 | [diff] [blame] | 161 | mbedtls_mpi_zeroize( X->p, X->n ); |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 162 | mbedtls_free( X->p ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 163 | } |
| 164 | |
| 165 | X->n = nblimbs; |
| 166 | X->p = p; |
| 167 | } |
| 168 | |
| 169 | return( 0 ); |
| 170 | } |
| 171 | |
| 172 | /* |
Manuel Pégourié-Gonnard | 5868163 | 2013-11-21 10:39:37 +0100 | [diff] [blame] | 173 | * Resize down as much as possible, |
| 174 | * while keeping at least the specified number of limbs |
| 175 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 176 | int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs ) |
Manuel Pégourié-Gonnard | 5868163 | 2013-11-21 10:39:37 +0100 | [diff] [blame] | 177 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 178 | mbedtls_mpi_uint *p; |
Manuel Pégourié-Gonnard | 5868163 | 2013-11-21 10:39:37 +0100 | [diff] [blame] | 179 | size_t i; |
| 180 | |
Gilles Peskine | 6a26967 | 2020-01-20 21:17:43 +0100 | [diff] [blame] | 181 | /* Actually resize up if there are currently fewer than nblimbs limbs. */ |
Manuel Pégourié-Gonnard | 5868163 | 2013-11-21 10:39:37 +0100 | [diff] [blame] | 182 | if( X->n <= nblimbs ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 183 | return( mbedtls_mpi_grow( X, nblimbs ) ); |
Gilles Peskine | 774c163 | 2020-01-21 13:59:51 +0100 | [diff] [blame] | 184 | /* After this point, then X->n > nblimbs and in particular X->n > 0. */ |
Manuel Pégourié-Gonnard | 5868163 | 2013-11-21 10:39:37 +0100 | [diff] [blame] | 185 | |
| 186 | for( i = X->n - 1; i > 0; i-- ) |
| 187 | if( X->p[i] != 0 ) |
| 188 | break; |
| 189 | i++; |
| 190 | |
| 191 | if( i < nblimbs ) |
| 192 | i = nblimbs; |
| 193 | |
Simon Butcher | 2917689 | 2016-05-20 00:19:09 +0100 | [diff] [blame] | 194 | if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL ) |
Manuel Pégourié-Gonnard | 6a8ca33 | 2015-05-28 09:33:39 +0200 | [diff] [blame] | 195 | return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); |
Manuel Pégourié-Gonnard | 5868163 | 2013-11-21 10:39:37 +0100 | [diff] [blame] | 196 | |
Manuel Pégourié-Gonnard | 5868163 | 2013-11-21 10:39:37 +0100 | [diff] [blame] | 197 | if( X->p != NULL ) |
| 198 | { |
| 199 | memcpy( p, X->p, i * ciL ); |
Alexey Skalozub | e17a8da | 2016-01-13 17:19:33 +0200 | [diff] [blame] | 200 | mbedtls_mpi_zeroize( X->p, X->n ); |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 201 | mbedtls_free( X->p ); |
Manuel Pégourié-Gonnard | 5868163 | 2013-11-21 10:39:37 +0100 | [diff] [blame] | 202 | } |
| 203 | |
| 204 | X->n = i; |
| 205 | X->p = p; |
| 206 | |
| 207 | return( 0 ); |
| 208 | } |
| 209 | |
| 210 | /* |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 211 | * Copy the contents of Y into X |
| 212 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 213 | int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 214 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 215 | int ret; |
| 216 | size_t i; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 217 | |
| 218 | if( X == Y ) |
| 219 | return( 0 ); |
| 220 | |
Gilles Peskine | 2aeab87 | 2020-01-20 21:12:50 +0100 | [diff] [blame] | 221 | if( Y->n == 0 ) |
Manuel Pégourié-Gonnard | f499993 | 2013-08-12 17:02:59 +0200 | [diff] [blame] | 222 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 223 | mbedtls_mpi_free( X ); |
Manuel Pégourié-Gonnard | f499993 | 2013-08-12 17:02:59 +0200 | [diff] [blame] | 224 | return( 0 ); |
| 225 | } |
| 226 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 227 | for( i = Y->n - 1; i > 0; i-- ) |
| 228 | if( Y->p[i] != 0 ) |
| 229 | break; |
| 230 | i++; |
| 231 | |
| 232 | X->s = Y->s; |
| 233 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 234 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 235 | |
| 236 | memset( X->p, 0, X->n * ciL ); |
| 237 | memcpy( X->p, Y->p, i * ciL ); |
| 238 | |
| 239 | cleanup: |
| 240 | |
| 241 | return( ret ); |
| 242 | } |
| 243 | |
| 244 | /* |
| 245 | * Swap the contents of X and Y |
| 246 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 247 | void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 248 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 249 | mbedtls_mpi T; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 250 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 251 | memcpy( &T, X, sizeof( mbedtls_mpi ) ); |
| 252 | memcpy( X, Y, sizeof( mbedtls_mpi ) ); |
| 253 | memcpy( Y, &T, sizeof( mbedtls_mpi ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 254 | } |
| 255 | |
| 256 | /* |
Gilles Peskine | 3c44c65 | 2020-06-04 19:14:58 +0200 | [diff] [blame] | 257 | * Conditionally assign dest = src, without leaking information |
| 258 | * about whether the assignment was made or not. |
| 259 | * dest and src must be arrays of limbs of size n. |
| 260 | * assign must be 0 or 1. |
| 261 | */ |
| 262 | static void mpi_safe_cond_assign( size_t n, |
| 263 | mbedtls_mpi_uint *dest, |
| 264 | const mbedtls_mpi_uint *src, |
| 265 | unsigned char assign ) |
| 266 | { |
| 267 | size_t i; |
| 268 | for( i = 0; i < n; i++ ) |
| 269 | dest[i] = dest[i] * ( 1 - assign ) + src[i] * assign; |
| 270 | } |
| 271 | |
| 272 | /* |
Manuel Pégourié-Gonnard | 71c2c21 | 2013-11-21 16:56:39 +0100 | [diff] [blame] | 273 | * Conditionally assign X = Y, without leaking information |
Manuel Pégourié-Gonnard | 96c7a92 | 2013-11-25 18:28:53 +0100 | [diff] [blame] | 274 | * about whether the assignment was made or not. |
| 275 | * (Leaking information about the respective sizes of X and Y is ok however.) |
Manuel Pégourié-Gonnard | 71c2c21 | 2013-11-21 16:56:39 +0100 | [diff] [blame] | 276 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 277 | int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign ) |
Manuel Pégourié-Gonnard | 71c2c21 | 2013-11-21 16:56:39 +0100 | [diff] [blame] | 278 | { |
| 279 | int ret = 0; |
| 280 | size_t i; |
| 281 | |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 282 | /* make sure assign is 0 or 1 in a time-constant manner */ |
| 283 | assign = (assign | (unsigned char)-assign) >> 7; |
Manuel Pégourié-Gonnard | 71c2c21 | 2013-11-21 16:56:39 +0100 | [diff] [blame] | 284 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 285 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) ); |
Manuel Pégourié-Gonnard | 71c2c21 | 2013-11-21 16:56:39 +0100 | [diff] [blame] | 286 | |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 287 | X->s = X->s * ( 1 - assign ) + Y->s * assign; |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 288 | |
Gilles Peskine | 3c44c65 | 2020-06-04 19:14:58 +0200 | [diff] [blame] | 289 | mpi_safe_cond_assign( Y->n, X->p, Y->p, assign ); |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 290 | |
Gilles Peskine | 3c44c65 | 2020-06-04 19:14:58 +0200 | [diff] [blame] | 291 | for( i = Y->n; i < X->n; i++ ) |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 292 | X->p[i] *= ( 1 - assign ); |
Manuel Pégourié-Gonnard | 71c2c21 | 2013-11-21 16:56:39 +0100 | [diff] [blame] | 293 | |
| 294 | cleanup: |
| 295 | return( ret ); |
| 296 | } |
| 297 | |
| 298 | /* |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 299 | * Conditionally swap X and Y, without leaking information |
| 300 | * about whether the swap was made or not. |
| 301 | * Here it is not ok to simply swap the pointers, which whould lead to |
| 302 | * different memory access patterns when X and Y are used afterwards. |
| 303 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 304 | int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap ) |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 305 | { |
| 306 | int ret, s; |
| 307 | size_t i; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 308 | mbedtls_mpi_uint tmp; |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 309 | |
| 310 | if( X == Y ) |
| 311 | return( 0 ); |
| 312 | |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 313 | /* make sure swap is 0 or 1 in a time-constant manner */ |
| 314 | swap = (swap | (unsigned char)-swap) >> 7; |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 315 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 316 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) ); |
| 317 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) ); |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 318 | |
| 319 | s = X->s; |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 320 | X->s = X->s * ( 1 - swap ) + Y->s * swap; |
| 321 | Y->s = Y->s * ( 1 - swap ) + s * swap; |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 322 | |
| 323 | |
| 324 | for( i = 0; i < X->n; i++ ) |
| 325 | { |
| 326 | tmp = X->p[i]; |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 327 | X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap; |
| 328 | Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap; |
Manuel Pégourié-Gonnard | a60fe89 | 2013-12-04 21:41:50 +0100 | [diff] [blame] | 329 | } |
| 330 | |
| 331 | cleanup: |
| 332 | return( ret ); |
| 333 | } |
| 334 | |
| 335 | /* |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 336 | * Set value from integer |
| 337 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 338 | int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 339 | { |
| 340 | int ret; |
| 341 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 342 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 343 | memset( X->p, 0, X->n * ciL ); |
| 344 | |
| 345 | X->p[0] = ( z < 0 ) ? -z : z; |
| 346 | X->s = ( z < 0 ) ? -1 : 1; |
| 347 | |
| 348 | cleanup: |
| 349 | |
| 350 | return( ret ); |
| 351 | } |
| 352 | |
| 353 | /* |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 354 | * Get a specific bit |
| 355 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 356 | int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos ) |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 357 | { |
| 358 | if( X->n * biL <= pos ) |
| 359 | return( 0 ); |
| 360 | |
Paul Bakker | d8bb826 | 2014-06-17 14:06:49 +0200 | [diff] [blame] | 361 | return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 ); |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 362 | } |
| 363 | |
Gilles Peskine | 220cc17 | 2018-11-20 16:47:47 +0100 | [diff] [blame] | 364 | /* Get a specific byte, without range checks. */ |
| 365 | #define GET_BYTE( X, i ) \ |
| 366 | ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff ) |
| 367 | |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 368 | /* |
| 369 | * Set a bit to a specific value of 0 or 1 |
| 370 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 371 | int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val ) |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 372 | { |
| 373 | int ret = 0; |
| 374 | size_t off = pos / biL; |
| 375 | size_t idx = pos % biL; |
| 376 | |
| 377 | if( val != 0 && val != 1 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 378 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
Paul Bakker | 9af723c | 2014-05-01 13:03:14 +0200 | [diff] [blame] | 379 | |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 380 | if( X->n * biL <= pos ) |
| 381 | { |
| 382 | if( val == 0 ) |
Paul Bakker | d8bb826 | 2014-06-17 14:06:49 +0200 | [diff] [blame] | 383 | return( 0 ); |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 384 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 385 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) ); |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 386 | } |
| 387 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 388 | X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx ); |
| 389 | X->p[off] |= (mbedtls_mpi_uint) val << idx; |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 390 | |
| 391 | cleanup: |
Paul Bakker | 9af723c | 2014-05-01 13:03:14 +0200 | [diff] [blame] | 392 | |
Paul Bakker | 2f5947e | 2011-05-18 15:47:11 +0000 | [diff] [blame] | 393 | return( ret ); |
| 394 | } |
| 395 | |
| 396 | /* |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 397 | * Return the number of less significant zero-bits |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 398 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 399 | size_t mbedtls_mpi_lsb( const mbedtls_mpi *X ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 400 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 401 | size_t i, j, count = 0; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 402 | |
| 403 | for( i = 0; i < X->n; i++ ) |
Paul Bakker | f968857 | 2011-05-05 10:00:45 +0000 | [diff] [blame] | 404 | for( j = 0; j < biL; j++, count++ ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 405 | if( ( ( X->p[i] >> j ) & 1 ) != 0 ) |
| 406 | return( count ); |
| 407 | |
| 408 | return( 0 ); |
| 409 | } |
| 410 | |
| 411 | /* |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 412 | * Count leading zero bits in a given integer |
| 413 | */ |
| 414 | static size_t mbedtls_clz( const mbedtls_mpi_uint x ) |
| 415 | { |
| 416 | size_t j; |
Manuel Pégourié-Gonnard | e3e8edf | 2015-12-01 09:31:52 +0100 | [diff] [blame] | 417 | mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1); |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 418 | |
| 419 | for( j = 0; j < biL; j++ ) |
| 420 | { |
| 421 | if( x & mask ) break; |
| 422 | |
| 423 | mask >>= 1; |
| 424 | } |
| 425 | |
| 426 | return j; |
| 427 | } |
| 428 | |
| 429 | /* |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 430 | * Return the number of bits |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 431 | */ |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 432 | size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 433 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 434 | size_t i, j; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 435 | |
Manuel Pégourié-Gonnard | 770b5e1 | 2015-04-29 17:02:01 +0200 | [diff] [blame] | 436 | if( X->n == 0 ) |
| 437 | return( 0 ); |
| 438 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 439 | for( i = X->n - 1; i > 0; i-- ) |
| 440 | if( X->p[i] != 0 ) |
| 441 | break; |
| 442 | |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 443 | j = biL - mbedtls_clz( X->p[i] ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 444 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 445 | return( ( i * biL ) + j ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 446 | } |
| 447 | |
| 448 | /* |
| 449 | * Return the total size in bytes |
| 450 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 451 | size_t mbedtls_mpi_size( const mbedtls_mpi *X ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 452 | { |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 453 | return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 454 | } |
| 455 | |
| 456 | /* |
| 457 | * Convert an ASCII character to digit value |
| 458 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 459 | static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 460 | { |
| 461 | *d = 255; |
| 462 | |
| 463 | if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30; |
| 464 | if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37; |
| 465 | if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57; |
| 466 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 467 | if( *d >= (mbedtls_mpi_uint) radix ) |
| 468 | return( MBEDTLS_ERR_MPI_INVALID_CHARACTER ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 469 | |
| 470 | return( 0 ); |
| 471 | } |
| 472 | |
| 473 | /* |
| 474 | * Import from an ASCII string |
| 475 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 476 | int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 477 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 478 | int ret; |
| 479 | size_t i, j, slen, n; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 480 | mbedtls_mpi_uint d; |
| 481 | mbedtls_mpi T; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 482 | |
| 483 | if( radix < 2 || radix > 16 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 484 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 485 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 486 | mbedtls_mpi_init( &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 487 | |
Paul Bakker | ff60ee6 | 2010-03-16 21:09:09 +0000 | [diff] [blame] | 488 | slen = strlen( s ); |
| 489 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 490 | if( radix == 16 ) |
| 491 | { |
Manuel Pégourié-Gonnard | 2d70834 | 2015-10-05 15:23:11 +0100 | [diff] [blame] | 492 | if( slen > MPI_SIZE_T_MAX >> 2 ) |
Manuel Pégourié-Gonnard | 58fb495 | 2015-09-28 13:48:04 +0200 | [diff] [blame] | 493 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
| 494 | |
Paul Bakker | ff60ee6 | 2010-03-16 21:09:09 +0000 | [diff] [blame] | 495 | n = BITS_TO_LIMBS( slen << 2 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 496 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 497 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) ); |
| 498 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 499 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 500 | for( i = slen, j = 0; i > 0; i--, j++ ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 501 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 502 | if( i == 1 && s[i - 1] == '-' ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 503 | { |
| 504 | X->s = -1; |
| 505 | break; |
| 506 | } |
| 507 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 508 | MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) ); |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 509 | X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 510 | } |
| 511 | } |
| 512 | else |
| 513 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 514 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 515 | |
Paul Bakker | ff60ee6 | 2010-03-16 21:09:09 +0000 | [diff] [blame] | 516 | for( i = 0; i < slen; i++ ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 517 | { |
| 518 | if( i == 0 && s[i] == '-' ) |
| 519 | { |
| 520 | X->s = -1; |
| 521 | continue; |
| 522 | } |
| 523 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 524 | MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) ); |
| 525 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) ); |
Paul Bakker | 05feca6 | 2009-06-20 08:22:43 +0000 | [diff] [blame] | 526 | |
| 527 | if( X->s == 1 ) |
| 528 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 529 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) ); |
Paul Bakker | 05feca6 | 2009-06-20 08:22:43 +0000 | [diff] [blame] | 530 | } |
| 531 | else |
| 532 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 533 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) ); |
Paul Bakker | 05feca6 | 2009-06-20 08:22:43 +0000 | [diff] [blame] | 534 | } |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 535 | } |
| 536 | } |
| 537 | |
| 538 | cleanup: |
| 539 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 540 | mbedtls_mpi_free( &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 541 | |
| 542 | return( ret ); |
| 543 | } |
| 544 | |
| 545 | /* |
Ron Eldor | e6cbfc3 | 2018-11-20 14:07:01 +0200 | [diff] [blame] | 546 | * Helper to write the digits high-order first. |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 547 | */ |
Ron Eldor | e6cbfc3 | 2018-11-20 14:07:01 +0200 | [diff] [blame] | 548 | static int mpi_write_hlp( mbedtls_mpi *X, int radix, |
| 549 | char **p, const size_t buflen ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 550 | { |
| 551 | int ret; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 552 | mbedtls_mpi_uint r; |
Ron Eldor | e6cbfc3 | 2018-11-20 14:07:01 +0200 | [diff] [blame] | 553 | size_t length = 0; |
| 554 | char *p_end = *p + buflen; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 555 | |
Ron Eldor | e6cbfc3 | 2018-11-20 14:07:01 +0200 | [diff] [blame] | 556 | do |
| 557 | { |
| 558 | if( length >= buflen ) |
| 559 | { |
| 560 | return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); |
| 561 | } |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 562 | |
Ron Eldor | e6cbfc3 | 2018-11-20 14:07:01 +0200 | [diff] [blame] | 563 | MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) ); |
| 564 | MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) ); |
| 565 | /* |
| 566 | * Write the residue in the current position, as an ASCII character. |
| 567 | */ |
| 568 | if( r < 0xA ) |
| 569 | *(--p_end) = (char)( '0' + r ); |
| 570 | else |
| 571 | *(--p_end) = (char)( 'A' + ( r - 0xA ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 572 | |
Ron Eldor | e6cbfc3 | 2018-11-20 14:07:01 +0200 | [diff] [blame] | 573 | length++; |
| 574 | } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 575 | |
Ron Eldor | e6cbfc3 | 2018-11-20 14:07:01 +0200 | [diff] [blame] | 576 | memmove( *p, p_end, length ); |
| 577 | *p += length; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 578 | |
| 579 | cleanup: |
| 580 | |
| 581 | return( ret ); |
| 582 | } |
| 583 | |
| 584 | /* |
| 585 | * Export into an ASCII string |
| 586 | */ |
Manuel Pégourié-Gonnard | f79b425 | 2015-06-02 15:41:48 +0100 | [diff] [blame] | 587 | int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix, |
| 588 | char *buf, size_t buflen, size_t *olen ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 589 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 590 | int ret = 0; |
| 591 | size_t n; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 592 | char *p; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 593 | mbedtls_mpi T; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 594 | |
| 595 | if( radix < 2 || radix > 16 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 596 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 597 | |
Hanno Becker | a277d4c | 2019-02-04 09:45:07 +0000 | [diff] [blame] | 598 | n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */ |
| 599 | if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present |
| 600 | * `n`. If radix > 4, this might be a strict |
| 601 | * overapproximation of the number of |
| 602 | * radix-adic digits needed to present `n`. */ |
| 603 | if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to |
| 604 | * present `n`. */ |
| 605 | |
Janos Follath | 216e738 | 2019-03-06 13:43:02 +0000 | [diff] [blame] | 606 | n += 1; /* Terminating null byte */ |
Hanno Becker | a277d4c | 2019-02-04 09:45:07 +0000 | [diff] [blame] | 607 | n += 1; /* Compensate for the divisions above, which round down `n` |
| 608 | * in case it's not even. */ |
| 609 | n += 1; /* Potential '-'-sign. */ |
| 610 | n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing, |
| 611 | * which always uses an even number of hex-digits. */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 612 | |
Manuel Pégourié-Gonnard | f79b425 | 2015-06-02 15:41:48 +0100 | [diff] [blame] | 613 | if( buflen < n ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 614 | { |
Manuel Pégourié-Gonnard | f79b425 | 2015-06-02 15:41:48 +0100 | [diff] [blame] | 615 | *olen = n; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 616 | return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 617 | } |
| 618 | |
Manuel Pégourié-Gonnard | f79b425 | 2015-06-02 15:41:48 +0100 | [diff] [blame] | 619 | p = buf; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 620 | mbedtls_mpi_init( &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 621 | |
| 622 | if( X->s == -1 ) |
Hanno Becker | eff335d | 2019-02-01 16:41:30 +0000 | [diff] [blame] | 623 | { |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 624 | *p++ = '-'; |
Hanno Becker | eff335d | 2019-02-01 16:41:30 +0000 | [diff] [blame] | 625 | buflen--; |
| 626 | } |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 627 | |
| 628 | if( radix == 16 ) |
| 629 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 630 | int c; |
| 631 | size_t i, j, k; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 632 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 633 | for( i = X->n, k = 0; i > 0; i-- ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 634 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 635 | for( j = ciL; j > 0; j-- ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 636 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 637 | c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 638 | |
Paul Bakker | 6c343d7 | 2014-07-10 14:36:19 +0200 | [diff] [blame] | 639 | if( c == 0 && k == 0 && ( i + j ) != 2 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 640 | continue; |
| 641 | |
Paul Bakker | 98fe5ea | 2012-10-24 11:17:48 +0000 | [diff] [blame] | 642 | *(p++) = "0123456789ABCDEF" [c / 16]; |
Paul Bakker | d2c167e | 2012-10-30 07:49:19 +0000 | [diff] [blame] | 643 | *(p++) = "0123456789ABCDEF" [c % 16]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 644 | k = 1; |
| 645 | } |
| 646 | } |
| 647 | } |
| 648 | else |
| 649 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 650 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) ); |
Paul Bakker | ce40a6d | 2009-06-23 19:46:08 +0000 | [diff] [blame] | 651 | |
| 652 | if( T.s == -1 ) |
| 653 | T.s = 1; |
| 654 | |
Ron Eldor | e6cbfc3 | 2018-11-20 14:07:01 +0200 | [diff] [blame] | 655 | MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 656 | } |
| 657 | |
| 658 | *p++ = '\0'; |
Manuel Pégourié-Gonnard | f79b425 | 2015-06-02 15:41:48 +0100 | [diff] [blame] | 659 | *olen = p - buf; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 660 | |
| 661 | cleanup: |
| 662 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 663 | mbedtls_mpi_free( &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 664 | |
| 665 | return( ret ); |
| 666 | } |
| 667 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 668 | #if defined(MBEDTLS_FS_IO) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 669 | /* |
| 670 | * Read X from an opened file |
| 671 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 672 | int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 673 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 674 | mbedtls_mpi_uint d; |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 675 | size_t slen; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 676 | char *p; |
Paul Bakker | fe3256e | 2011-11-25 12:11:43 +0000 | [diff] [blame] | 677 | /* |
Paul Bakker | cb37aa5 | 2011-11-30 16:00:20 +0000 | [diff] [blame] | 678 | * Buffer should have space for (short) label and decimal formatted MPI, |
| 679 | * newline characters and '\0' |
Paul Bakker | fe3256e | 2011-11-25 12:11:43 +0000 | [diff] [blame] | 680 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 681 | char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 682 | |
| 683 | memset( s, 0, sizeof( s ) ); |
| 684 | if( fgets( s, sizeof( s ) - 1, fin ) == NULL ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 685 | return( MBEDTLS_ERR_MPI_FILE_IO_ERROR ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 686 | |
| 687 | slen = strlen( s ); |
Paul Bakker | cb37aa5 | 2011-11-30 16:00:20 +0000 | [diff] [blame] | 688 | if( slen == sizeof( s ) - 2 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 689 | return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); |
Paul Bakker | cb37aa5 | 2011-11-30 16:00:20 +0000 | [diff] [blame] | 690 | |
Hanno Becker | b2034b7 | 2017-04-26 11:46:46 +0100 | [diff] [blame] | 691 | if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; } |
| 692 | if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; } |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 693 | |
| 694 | p = s + slen; |
Hanno Becker | b2034b7 | 2017-04-26 11:46:46 +0100 | [diff] [blame] | 695 | while( p-- > s ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 696 | if( mpi_get_digit( &d, radix, *p ) != 0 ) |
| 697 | break; |
| 698 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 699 | return( mbedtls_mpi_read_string( X, radix, p + 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 700 | } |
| 701 | |
| 702 | /* |
| 703 | * Write X into an opened file (or stdout if fout == NULL) |
| 704 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 705 | int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 706 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 707 | int ret; |
| 708 | size_t n, slen, plen; |
Paul Bakker | fe3256e | 2011-11-25 12:11:43 +0000 | [diff] [blame] | 709 | /* |
Paul Bakker | 5531c6d | 2012-09-26 19:20:46 +0000 | [diff] [blame] | 710 | * Buffer should have space for (short) label and decimal formatted MPI, |
| 711 | * newline characters and '\0' |
Paul Bakker | fe3256e | 2011-11-25 12:11:43 +0000 | [diff] [blame] | 712 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 713 | char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 714 | |
Manuel Pégourié-Gonnard | f79b425 | 2015-06-02 15:41:48 +0100 | [diff] [blame] | 715 | memset( s, 0, sizeof( s ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 716 | |
Manuel Pégourié-Gonnard | f79b425 | 2015-06-02 15:41:48 +0100 | [diff] [blame] | 717 | MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 718 | |
| 719 | if( p == NULL ) p = ""; |
| 720 | |
| 721 | plen = strlen( p ); |
| 722 | slen = strlen( s ); |
| 723 | s[slen++] = '\r'; |
| 724 | s[slen++] = '\n'; |
| 725 | |
| 726 | if( fout != NULL ) |
| 727 | { |
| 728 | if( fwrite( p, 1, plen, fout ) != plen || |
| 729 | fwrite( s, 1, slen, fout ) != slen ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 730 | return( MBEDTLS_ERR_MPI_FILE_IO_ERROR ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 731 | } |
| 732 | else |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 733 | mbedtls_printf( "%s%s", p, s ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 734 | |
| 735 | cleanup: |
| 736 | |
| 737 | return( ret ); |
| 738 | } |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 739 | #endif /* MBEDTLS_FS_IO */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 740 | |
| 741 | /* |
| 742 | * Import X from unsigned binary data, big endian |
| 743 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 744 | int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 745 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 746 | int ret; |
Hanno Becker | 073c199 | 2017-10-17 15:17:27 +0100 | [diff] [blame] | 747 | size_t i, j; |
| 748 | size_t const limbs = CHARS_TO_LIMBS( buflen ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 749 | |
Hanno Becker | 073c199 | 2017-10-17 15:17:27 +0100 | [diff] [blame] | 750 | /* Ensure that target MPI has exactly the necessary number of limbs */ |
| 751 | if( X->n != limbs ) |
| 752 | { |
| 753 | mbedtls_mpi_free( X ); |
| 754 | mbedtls_mpi_init( X ); |
| 755 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) ); |
| 756 | } |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 757 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 758 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 759 | |
Hanno Becker | 073c199 | 2017-10-17 15:17:27 +0100 | [diff] [blame] | 760 | for( i = buflen, j = 0; i > 0; i--, j++ ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 761 | X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 762 | |
| 763 | cleanup: |
| 764 | |
| 765 | return( ret ); |
| 766 | } |
| 767 | |
| 768 | /* |
| 769 | * Export X into unsigned binary data, big endian |
| 770 | */ |
Gilles Peskine | 220cc17 | 2018-11-20 16:47:47 +0100 | [diff] [blame] | 771 | int mbedtls_mpi_write_binary( const mbedtls_mpi *X, |
| 772 | unsigned char *buf, size_t buflen ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 773 | { |
Gilles Peskine | 220cc17 | 2018-11-20 16:47:47 +0100 | [diff] [blame] | 774 | size_t stored_bytes = X->n * ciL; |
| 775 | size_t bytes_to_copy; |
| 776 | unsigned char *p; |
| 777 | size_t i; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 778 | |
Gilles Peskine | 220cc17 | 2018-11-20 16:47:47 +0100 | [diff] [blame] | 779 | if( stored_bytes < buflen ) |
| 780 | { |
| 781 | /* There is enough space in the output buffer. Write initial |
| 782 | * null bytes and record the position at which to start |
| 783 | * writing the significant bytes. In this case, the execution |
| 784 | * trace of this function does not depend on the value of the |
| 785 | * number. */ |
| 786 | bytes_to_copy = stored_bytes; |
| 787 | p = buf + buflen - stored_bytes; |
| 788 | memset( buf, 0, buflen - stored_bytes ); |
| 789 | } |
| 790 | else |
| 791 | { |
| 792 | /* The output buffer is smaller than the allocated size of X. |
| 793 | * However X may fit if its leading bytes are zero. */ |
| 794 | bytes_to_copy = buflen; |
| 795 | p = buf; |
| 796 | for( i = bytes_to_copy; i < stored_bytes; i++ ) |
| 797 | { |
| 798 | if( GET_BYTE( X, i ) != 0 ) |
| 799 | return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); |
| 800 | } |
| 801 | } |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 802 | |
Gilles Peskine | 220cc17 | 2018-11-20 16:47:47 +0100 | [diff] [blame] | 803 | for( i = 0; i < bytes_to_copy; i++ ) |
| 804 | p[bytes_to_copy - i - 1] = GET_BYTE( X, i ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 805 | |
| 806 | return( 0 ); |
| 807 | } |
| 808 | |
| 809 | /* |
| 810 | * Left-shift: X <<= count |
| 811 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 812 | int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 813 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 814 | int ret; |
| 815 | size_t i, v0, t1; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 816 | mbedtls_mpi_uint r0 = 0, r1; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 817 | |
| 818 | v0 = count / (biL ); |
| 819 | t1 = count & (biL - 1); |
| 820 | |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 821 | i = mbedtls_mpi_bitlen( X ) + count; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 822 | |
Paul Bakker | f968857 | 2011-05-05 10:00:45 +0000 | [diff] [blame] | 823 | if( X->n * biL < i ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 824 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 825 | |
| 826 | ret = 0; |
| 827 | |
| 828 | /* |
| 829 | * shift by count / limb_size |
| 830 | */ |
| 831 | if( v0 > 0 ) |
| 832 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 833 | for( i = X->n; i > v0; i-- ) |
| 834 | X->p[i - 1] = X->p[i - v0 - 1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 835 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 836 | for( ; i > 0; i-- ) |
| 837 | X->p[i - 1] = 0; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 838 | } |
| 839 | |
| 840 | /* |
| 841 | * shift by count % limb_size |
| 842 | */ |
| 843 | if( t1 > 0 ) |
| 844 | { |
| 845 | for( i = v0; i < X->n; i++ ) |
| 846 | { |
| 847 | r1 = X->p[i] >> (biL - t1); |
| 848 | X->p[i] <<= t1; |
| 849 | X->p[i] |= r0; |
| 850 | r0 = r1; |
| 851 | } |
| 852 | } |
| 853 | |
| 854 | cleanup: |
| 855 | |
| 856 | return( ret ); |
| 857 | } |
| 858 | |
| 859 | /* |
| 860 | * Right-shift: X >>= count |
| 861 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 862 | int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 863 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 864 | size_t i, v0, v1; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 865 | mbedtls_mpi_uint r0 = 0, r1; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 866 | |
| 867 | v0 = count / biL; |
| 868 | v1 = count & (biL - 1); |
| 869 | |
Manuel Pégourié-Gonnard | e44ec10 | 2012-11-17 12:42:51 +0100 | [diff] [blame] | 870 | if( v0 > X->n || ( v0 == X->n && v1 > 0 ) ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 871 | return mbedtls_mpi_lset( X, 0 ); |
Manuel Pégourié-Gonnard | e44ec10 | 2012-11-17 12:42:51 +0100 | [diff] [blame] | 872 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 873 | /* |
| 874 | * shift by count / limb_size |
| 875 | */ |
| 876 | if( v0 > 0 ) |
| 877 | { |
| 878 | for( i = 0; i < X->n - v0; i++ ) |
| 879 | X->p[i] = X->p[i + v0]; |
| 880 | |
| 881 | for( ; i < X->n; i++ ) |
| 882 | X->p[i] = 0; |
| 883 | } |
| 884 | |
| 885 | /* |
| 886 | * shift by count % limb_size |
| 887 | */ |
| 888 | if( v1 > 0 ) |
| 889 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 890 | for( i = X->n; i > 0; i-- ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 891 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 892 | r1 = X->p[i - 1] << (biL - v1); |
| 893 | X->p[i - 1] >>= v1; |
| 894 | X->p[i - 1] |= r0; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 895 | r0 = r1; |
| 896 | } |
| 897 | } |
| 898 | |
| 899 | return( 0 ); |
| 900 | } |
| 901 | |
| 902 | /* |
| 903 | * Compare unsigned values |
| 904 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 905 | int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 906 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 907 | size_t i, j; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 908 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 909 | for( i = X->n; i > 0; i-- ) |
| 910 | if( X->p[i - 1] != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 911 | break; |
| 912 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 913 | for( j = Y->n; j > 0; j-- ) |
| 914 | if( Y->p[j - 1] != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 915 | break; |
| 916 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 917 | if( i == 0 && j == 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 918 | return( 0 ); |
| 919 | |
| 920 | if( i > j ) return( 1 ); |
| 921 | if( j > i ) return( -1 ); |
| 922 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 923 | for( ; i > 0; i-- ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 924 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 925 | if( X->p[i - 1] > Y->p[i - 1] ) return( 1 ); |
| 926 | if( X->p[i - 1] < Y->p[i - 1] ) return( -1 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 927 | } |
| 928 | |
| 929 | return( 0 ); |
| 930 | } |
| 931 | |
| 932 | /* |
| 933 | * Compare signed values |
| 934 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 935 | int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 936 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 937 | size_t i, j; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 938 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 939 | for( i = X->n; i > 0; i-- ) |
| 940 | if( X->p[i - 1] != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 941 | break; |
| 942 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 943 | for( j = Y->n; j > 0; j-- ) |
| 944 | if( Y->p[j - 1] != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 945 | break; |
| 946 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 947 | if( i == 0 && j == 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 948 | return( 0 ); |
| 949 | |
| 950 | if( i > j ) return( X->s ); |
Paul Bakker | 0c8f73b | 2012-03-22 14:08:57 +0000 | [diff] [blame] | 951 | if( j > i ) return( -Y->s ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 952 | |
| 953 | if( X->s > 0 && Y->s < 0 ) return( 1 ); |
| 954 | if( Y->s > 0 && X->s < 0 ) return( -1 ); |
| 955 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 956 | for( ; i > 0; i-- ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 957 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 958 | if( X->p[i - 1] > Y->p[i - 1] ) return( X->s ); |
| 959 | if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 960 | } |
| 961 | |
| 962 | return( 0 ); |
| 963 | } |
| 964 | |
Janos Follath | 3173a53 | 2019-10-14 09:09:32 +0100 | [diff] [blame] | 965 | /** Decide if an integer is less than the other, without branches. |
| 966 | * |
| 967 | * \param x First integer. |
| 968 | * \param y Second integer. |
| 969 | * |
| 970 | * \return 1 if \p x is less than \p y, 0 otherwise |
| 971 | */ |
Janos Follath | c3b376e | 2019-10-11 14:21:53 +0100 | [diff] [blame] | 972 | static unsigned ct_lt_mpi_uint( const mbedtls_mpi_uint x, |
| 973 | const mbedtls_mpi_uint y ) |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 974 | { |
| 975 | mbedtls_mpi_uint ret; |
| 976 | mbedtls_mpi_uint cond; |
| 977 | |
| 978 | /* |
| 979 | * Check if the most significant bits (MSB) of the operands are different. |
| 980 | */ |
| 981 | cond = ( x ^ y ); |
| 982 | /* |
| 983 | * If the MSB are the same then the difference x-y will be negative (and |
| 984 | * have its MSB set to 1 during conversion to unsigned) if and only if x<y. |
| 985 | */ |
| 986 | ret = ( x - y ) & ~cond; |
| 987 | /* |
| 988 | * If the MSB are different, then the operand with the MSB of 1 is the |
| 989 | * bigger. (That is if y has MSB of 1, then x<y is true and it is false if |
| 990 | * the MSB of y is 0.) |
| 991 | */ |
| 992 | ret |= y & cond; |
| 993 | |
| 994 | |
Janos Follath | db9f449 | 2019-10-14 08:59:14 +0100 | [diff] [blame] | 995 | ret = ret >> ( biL - 1 ); |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 996 | |
Janos Follath | 5823961 | 2019-10-29 15:08:46 +0000 | [diff] [blame] | 997 | return (unsigned) ret; |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 998 | } |
| 999 | |
| 1000 | /* |
| 1001 | * Compare signed values in constant time |
| 1002 | */ |
Janos Follath | c3b376e | 2019-10-11 14:21:53 +0100 | [diff] [blame] | 1003 | int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y, |
| 1004 | unsigned *ret ) |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 1005 | { |
| 1006 | size_t i; |
Janos Follath | a2b9a96 | 2019-10-28 12:23:18 +0000 | [diff] [blame] | 1007 | /* The value of any of these variables is either 0 or 1 at all times. */ |
Janos Follath | 8ec2a95 | 2019-10-28 12:31:34 +0000 | [diff] [blame] | 1008 | unsigned cond, done, X_is_negative, Y_is_negative; |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 1009 | |
| 1010 | if( X->n != Y->n ) |
| 1011 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
| 1012 | |
| 1013 | /* |
Janos Follath | 51ed14e | 2019-10-28 12:12:15 +0000 | [diff] [blame] | 1014 | * Set sign_N to 1 if N >= 0, 0 if N < 0. |
| 1015 | * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0. |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 1016 | */ |
Janos Follath | 8ec2a95 | 2019-10-28 12:31:34 +0000 | [diff] [blame] | 1017 | X_is_negative = ( X->s & 2 ) >> 1; |
| 1018 | Y_is_negative = ( Y->s & 2 ) >> 1; |
Janos Follath | c3b376e | 2019-10-11 14:21:53 +0100 | [diff] [blame] | 1019 | |
| 1020 | /* |
| 1021 | * If the signs are different, then the positive operand is the bigger. |
Janos Follath | 8ec2a95 | 2019-10-28 12:31:34 +0000 | [diff] [blame] | 1022 | * That is if X is negative (X_is_negative == 1), then X < Y is true and it |
| 1023 | * is false if X is positive (X_is_negative == 0). |
Janos Follath | c3b376e | 2019-10-11 14:21:53 +0100 | [diff] [blame] | 1024 | */ |
Janos Follath | 8ec2a95 | 2019-10-28 12:31:34 +0000 | [diff] [blame] | 1025 | cond = ( X_is_negative ^ Y_is_negative ); |
| 1026 | *ret = cond & X_is_negative; |
Janos Follath | c3b376e | 2019-10-11 14:21:53 +0100 | [diff] [blame] | 1027 | |
| 1028 | /* |
Janos Follath | a2b9a96 | 2019-10-28 12:23:18 +0000 | [diff] [blame] | 1029 | * This is a constant-time function. We might have the result, but we still |
Janos Follath | c3b376e | 2019-10-11 14:21:53 +0100 | [diff] [blame] | 1030 | * need to go through the loop. Record if we have the result already. |
| 1031 | */ |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 1032 | done = cond; |
| 1033 | |
| 1034 | for( i = X->n; i > 0; i-- ) |
| 1035 | { |
| 1036 | /* |
Janos Follath | b4edac5 | 2019-11-05 12:24:52 +0000 | [diff] [blame] | 1037 | * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both |
| 1038 | * X and Y are negative. |
Janos Follath | c3b376e | 2019-10-11 14:21:53 +0100 | [diff] [blame] | 1039 | * |
| 1040 | * Again even if we can make a decision, we just mark the result and |
| 1041 | * the fact that we are done and continue looping. |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 1042 | */ |
Janos Follath | b4edac5 | 2019-11-05 12:24:52 +0000 | [diff] [blame] | 1043 | cond = ct_lt_mpi_uint( Y->p[i - 1], X->p[i - 1] ); |
| 1044 | *ret |= cond & ( 1 - done ) & X_is_negative; |
Janos Follath | cff9e6e | 2019-10-28 12:37:21 +0000 | [diff] [blame] | 1045 | done |= cond; |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 1046 | |
| 1047 | /* |
Janos Follath | b4edac5 | 2019-11-05 12:24:52 +0000 | [diff] [blame] | 1048 | * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both |
| 1049 | * X and Y are positive. |
Janos Follath | c3b376e | 2019-10-11 14:21:53 +0100 | [diff] [blame] | 1050 | * |
| 1051 | * Again even if we can make a decision, we just mark the result and |
| 1052 | * the fact that we are done and continue looping. |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 1053 | */ |
Janos Follath | b4edac5 | 2019-11-05 12:24:52 +0000 | [diff] [blame] | 1054 | cond = ct_lt_mpi_uint( X->p[i - 1], Y->p[i - 1] ); |
| 1055 | *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative ); |
Janos Follath | cff9e6e | 2019-10-28 12:37:21 +0000 | [diff] [blame] | 1056 | done |= cond; |
Janos Follath | e0187b9 | 2019-09-05 14:47:19 +0100 | [diff] [blame] | 1057 | } |
| 1058 | |
| 1059 | return( 0 ); |
| 1060 | } |
| 1061 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1062 | /* |
| 1063 | * Compare signed values |
| 1064 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1065 | int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1066 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1067 | mbedtls_mpi Y; |
| 1068 | mbedtls_mpi_uint p[1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1069 | |
| 1070 | *p = ( z < 0 ) ? -z : z; |
| 1071 | Y.s = ( z < 0 ) ? -1 : 1; |
| 1072 | Y.n = 1; |
| 1073 | Y.p = p; |
| 1074 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1075 | return( mbedtls_mpi_cmp_mpi( X, &Y ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1076 | } |
| 1077 | |
| 1078 | /* |
| 1079 | * Unsigned addition: X = |A| + |B| (HAC 14.7) |
| 1080 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1081 | int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1082 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1083 | int ret; |
| 1084 | size_t i, j; |
Janos Follath | 6c92268 | 2015-10-30 17:43:11 +0100 | [diff] [blame] | 1085 | mbedtls_mpi_uint *o, *p, c, tmp; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1086 | |
| 1087 | if( X == B ) |
| 1088 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1089 | const mbedtls_mpi *T = A; A = X; B = T; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1090 | } |
| 1091 | |
| 1092 | if( X != A ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1093 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) ); |
Paul Bakker | 9af723c | 2014-05-01 13:03:14 +0200 | [diff] [blame] | 1094 | |
Paul Bakker | f7ca7b9 | 2009-06-20 10:31:06 +0000 | [diff] [blame] | 1095 | /* |
| 1096 | * X should always be positive as a result of unsigned additions. |
| 1097 | */ |
| 1098 | X->s = 1; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1099 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1100 | for( j = B->n; j > 0; j-- ) |
| 1101 | if( B->p[j - 1] != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1102 | break; |
| 1103 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1104 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1105 | |
| 1106 | o = B->p; p = X->p; c = 0; |
| 1107 | |
Janos Follath | 6c92268 | 2015-10-30 17:43:11 +0100 | [diff] [blame] | 1108 | /* |
| 1109 | * tmp is used because it might happen that p == o |
| 1110 | */ |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1111 | for( i = 0; i < j; i++, o++, p++ ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1112 | { |
Janos Follath | 6c92268 | 2015-10-30 17:43:11 +0100 | [diff] [blame] | 1113 | tmp= *o; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1114 | *p += c; c = ( *p < c ); |
Janos Follath | 6c92268 | 2015-10-30 17:43:11 +0100 | [diff] [blame] | 1115 | *p += tmp; c += ( *p < tmp ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1116 | } |
| 1117 | |
| 1118 | while( c != 0 ) |
| 1119 | { |
| 1120 | if( i >= X->n ) |
| 1121 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1122 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1123 | p = X->p + i; |
| 1124 | } |
| 1125 | |
Paul Bakker | 2d319fd | 2012-09-16 21:34:26 +0000 | [diff] [blame] | 1126 | *p += c; c = ( *p < c ); i++; p++; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1127 | } |
| 1128 | |
| 1129 | cleanup: |
| 1130 | |
| 1131 | return( ret ); |
| 1132 | } |
| 1133 | |
Gilles Peskine | f3317e6 | 2020-06-09 10:39:38 +0200 | [diff] [blame] | 1134 | /** |
Gilles Peskine | 6f3b68d | 2020-06-08 21:58:22 +0200 | [diff] [blame] | 1135 | * Helper for mbedtls_mpi subtraction. |
| 1136 | * |
| 1137 | * Calculate d - s where d and s have the same size. |
| 1138 | * This function operates modulo (2^ciL)^n and returns the carry |
| 1139 | * (1 if there was a wraparound, i.e. if `d < s`, and 0 otherwise). |
| 1140 | * |
| 1141 | * \param n Number of limbs of \p d and \p s. |
| 1142 | * \param[in,out] d On input, the left operand. |
| 1143 | * On output, the result of the subtraction: |
Gilles Peskine | f3317e6 | 2020-06-09 10:39:38 +0200 | [diff] [blame] | 1144 | * \param[in] s The right operand. |
Gilles Peskine | 6f3b68d | 2020-06-08 21:58:22 +0200 | [diff] [blame] | 1145 | * |
| 1146 | * \return 1 if `d < s`. |
| 1147 | * 0 if `d >= s`. |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1148 | */ |
Gilles Peskine | 6f3b68d | 2020-06-08 21:58:22 +0200 | [diff] [blame] | 1149 | static mbedtls_mpi_uint mpi_sub_hlp( size_t n, |
| 1150 | mbedtls_mpi_uint *d, |
| 1151 | const mbedtls_mpi_uint *s ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1152 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1153 | size_t i; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1154 | mbedtls_mpi_uint c, z; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1155 | |
| 1156 | for( i = c = 0; i < n; i++, s++, d++ ) |
| 1157 | { |
| 1158 | z = ( *d < c ); *d -= c; |
| 1159 | c = ( *d < *s ) + z; *d -= *s; |
| 1160 | } |
| 1161 | |
Gilles Peskine | 6f3b68d | 2020-06-08 21:58:22 +0200 | [diff] [blame] | 1162 | return( c ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1163 | } |
| 1164 | |
| 1165 | /* |
Gilles Peskine | fa85cc2 | 2020-06-08 22:50:35 +0200 | [diff] [blame] | 1166 | * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1167 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1168 | int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1169 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1170 | mbedtls_mpi TB; |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1171 | int ret; |
| 1172 | size_t n; |
Gilles Peskine | fa85cc2 | 2020-06-08 22:50:35 +0200 | [diff] [blame] | 1173 | mbedtls_mpi_uint carry; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1174 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1175 | mbedtls_mpi_init( &TB ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1176 | |
| 1177 | if( X == B ) |
| 1178 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1179 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1180 | B = &TB; |
| 1181 | } |
| 1182 | |
| 1183 | if( X != A ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1184 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1185 | |
Paul Bakker | 1ef7a53 | 2009-06-20 10:50:55 +0000 | [diff] [blame] | 1186 | /* |
Paul Bakker | 60b1d10 | 2013-10-29 10:02:51 +0100 | [diff] [blame] | 1187 | * X should always be positive as a result of unsigned subtractions. |
Paul Bakker | 1ef7a53 | 2009-06-20 10:50:55 +0000 | [diff] [blame] | 1188 | */ |
| 1189 | X->s = 1; |
| 1190 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1191 | ret = 0; |
| 1192 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1193 | for( n = B->n; n > 0; n-- ) |
| 1194 | if( B->p[n - 1] != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1195 | break; |
| 1196 | |
Gilles Peskine | fa85cc2 | 2020-06-08 22:50:35 +0200 | [diff] [blame] | 1197 | carry = mpi_sub_hlp( n, X->p, B->p ); |
| 1198 | if( carry != 0 ) |
Gilles Peskine | 6f3b68d | 2020-06-08 21:58:22 +0200 | [diff] [blame] | 1199 | { |
Gilles Peskine | fa85cc2 | 2020-06-08 22:50:35 +0200 | [diff] [blame] | 1200 | /* Propagate the carry to the first nonzero limb of X. */ |
| 1201 | for( ; n < X->n && X->p[n] == 0; n++ ) |
| 1202 | --X->p[n]; |
| 1203 | /* If we ran out of space for the carry, it means that the result |
| 1204 | * is negative. */ |
| 1205 | if( n == X->n ) |
| 1206 | return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); |
| 1207 | --X->p[n]; |
Gilles Peskine | 6f3b68d | 2020-06-08 21:58:22 +0200 | [diff] [blame] | 1208 | } |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1209 | |
| 1210 | cleanup: |
| 1211 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1212 | mbedtls_mpi_free( &TB ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1213 | |
| 1214 | return( ret ); |
| 1215 | } |
| 1216 | |
| 1217 | /* |
| 1218 | * Signed addition: X = A + B |
| 1219 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1220 | int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1221 | { |
| 1222 | int ret, s = A->s; |
| 1223 | |
| 1224 | if( A->s * B->s < 0 ) |
| 1225 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1226 | if( mbedtls_mpi_cmp_abs( A, B ) >= 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1227 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1228 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1229 | X->s = s; |
| 1230 | } |
| 1231 | else |
| 1232 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1233 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1234 | X->s = -s; |
| 1235 | } |
| 1236 | } |
| 1237 | else |
| 1238 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1239 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1240 | X->s = s; |
| 1241 | } |
| 1242 | |
| 1243 | cleanup: |
| 1244 | |
| 1245 | return( ret ); |
| 1246 | } |
| 1247 | |
| 1248 | /* |
Paul Bakker | 60b1d10 | 2013-10-29 10:02:51 +0100 | [diff] [blame] | 1249 | * Signed subtraction: X = A - B |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1250 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1251 | int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1252 | { |
| 1253 | int ret, s = A->s; |
| 1254 | |
| 1255 | if( A->s * B->s > 0 ) |
| 1256 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1257 | if( mbedtls_mpi_cmp_abs( A, B ) >= 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1258 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1259 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1260 | X->s = s; |
| 1261 | } |
| 1262 | else |
| 1263 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1264 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1265 | X->s = -s; |
| 1266 | } |
| 1267 | } |
| 1268 | else |
| 1269 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1270 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1271 | X->s = s; |
| 1272 | } |
| 1273 | |
| 1274 | cleanup: |
| 1275 | |
| 1276 | return( ret ); |
| 1277 | } |
| 1278 | |
| 1279 | /* |
| 1280 | * Signed addition: X = A + b |
| 1281 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1282 | int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1283 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1284 | mbedtls_mpi _B; |
| 1285 | mbedtls_mpi_uint p[1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1286 | |
| 1287 | p[0] = ( b < 0 ) ? -b : b; |
| 1288 | _B.s = ( b < 0 ) ? -1 : 1; |
| 1289 | _B.n = 1; |
| 1290 | _B.p = p; |
| 1291 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1292 | return( mbedtls_mpi_add_mpi( X, A, &_B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1293 | } |
| 1294 | |
| 1295 | /* |
Paul Bakker | 60b1d10 | 2013-10-29 10:02:51 +0100 | [diff] [blame] | 1296 | * Signed subtraction: X = A - b |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1297 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1298 | int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1299 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1300 | mbedtls_mpi _B; |
| 1301 | mbedtls_mpi_uint p[1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1302 | |
| 1303 | p[0] = ( b < 0 ) ? -b : b; |
| 1304 | _B.s = ( b < 0 ) ? -1 : 1; |
| 1305 | _B.n = 1; |
| 1306 | _B.p = p; |
| 1307 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1308 | return( mbedtls_mpi_sub_mpi( X, A, &_B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1309 | } |
| 1310 | |
| 1311 | /* |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1312 | * Helper for mbedtls_mpi multiplication |
Paul Bakker | fc4f46f | 2013-06-24 19:23:56 +0200 | [diff] [blame] | 1313 | */ |
| 1314 | static |
| 1315 | #if defined(__APPLE__) && defined(__arm__) |
| 1316 | /* |
| 1317 | * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn) |
| 1318 | * appears to need this to prevent bad ARM code generation at -O3. |
| 1319 | */ |
| 1320 | __attribute__ ((noinline)) |
| 1321 | #endif |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1322 | void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1323 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1324 | mbedtls_mpi_uint c = 0, t = 0; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1325 | |
| 1326 | #if defined(MULADDC_HUIT) |
| 1327 | for( ; i >= 8; i -= 8 ) |
| 1328 | { |
| 1329 | MULADDC_INIT |
| 1330 | MULADDC_HUIT |
| 1331 | MULADDC_STOP |
| 1332 | } |
| 1333 | |
| 1334 | for( ; i > 0; i-- ) |
| 1335 | { |
| 1336 | MULADDC_INIT |
| 1337 | MULADDC_CORE |
| 1338 | MULADDC_STOP |
| 1339 | } |
Paul Bakker | 9af723c | 2014-05-01 13:03:14 +0200 | [diff] [blame] | 1340 | #else /* MULADDC_HUIT */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1341 | for( ; i >= 16; i -= 16 ) |
| 1342 | { |
| 1343 | MULADDC_INIT |
| 1344 | MULADDC_CORE MULADDC_CORE |
| 1345 | MULADDC_CORE MULADDC_CORE |
| 1346 | MULADDC_CORE MULADDC_CORE |
| 1347 | MULADDC_CORE MULADDC_CORE |
| 1348 | |
| 1349 | MULADDC_CORE MULADDC_CORE |
| 1350 | MULADDC_CORE MULADDC_CORE |
| 1351 | MULADDC_CORE MULADDC_CORE |
| 1352 | MULADDC_CORE MULADDC_CORE |
| 1353 | MULADDC_STOP |
| 1354 | } |
| 1355 | |
| 1356 | for( ; i >= 8; i -= 8 ) |
| 1357 | { |
| 1358 | MULADDC_INIT |
| 1359 | MULADDC_CORE MULADDC_CORE |
| 1360 | MULADDC_CORE MULADDC_CORE |
| 1361 | |
| 1362 | MULADDC_CORE MULADDC_CORE |
| 1363 | MULADDC_CORE MULADDC_CORE |
| 1364 | MULADDC_STOP |
| 1365 | } |
| 1366 | |
| 1367 | for( ; i > 0; i-- ) |
| 1368 | { |
| 1369 | MULADDC_INIT |
| 1370 | MULADDC_CORE |
| 1371 | MULADDC_STOP |
| 1372 | } |
Paul Bakker | 9af723c | 2014-05-01 13:03:14 +0200 | [diff] [blame] | 1373 | #endif /* MULADDC_HUIT */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1374 | |
| 1375 | t++; |
| 1376 | |
| 1377 | do { |
| 1378 | *d += c; c = ( *d < c ); d++; |
| 1379 | } |
| 1380 | while( c != 0 ); |
| 1381 | } |
| 1382 | |
| 1383 | /* |
| 1384 | * Baseline multiplication: X = A * B (HAC 14.12) |
| 1385 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1386 | int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1387 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1388 | int ret; |
| 1389 | size_t i, j; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1390 | mbedtls_mpi TA, TB; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1391 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1392 | mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1393 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1394 | if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; } |
| 1395 | if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; } |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1396 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1397 | for( i = A->n; i > 0; i-- ) |
| 1398 | if( A->p[i - 1] != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1399 | break; |
| 1400 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1401 | for( j = B->n; j > 0; j-- ) |
| 1402 | if( B->p[j - 1] != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1403 | break; |
| 1404 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1405 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) ); |
| 1406 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1407 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1408 | for( i++; j > 0; j-- ) |
| 1409 | mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1410 | |
| 1411 | X->s = A->s * B->s; |
| 1412 | |
| 1413 | cleanup: |
| 1414 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1415 | mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1416 | |
| 1417 | return( ret ); |
| 1418 | } |
| 1419 | |
| 1420 | /* |
| 1421 | * Baseline multiplication: X = A * b |
| 1422 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1423 | int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1424 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1425 | mbedtls_mpi _B; |
| 1426 | mbedtls_mpi_uint p[1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1427 | |
| 1428 | _B.s = 1; |
| 1429 | _B.n = 1; |
| 1430 | _B.p = p; |
| 1431 | p[0] = b; |
| 1432 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1433 | return( mbedtls_mpi_mul_mpi( X, A, &_B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1434 | } |
| 1435 | |
| 1436 | /* |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1437 | * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and |
| 1438 | * mbedtls_mpi_uint divisor, d |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1439 | */ |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1440 | static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1, |
| 1441 | mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r ) |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1442 | { |
Manuel Pégourié-Gonnard | 1630888 | 2015-12-01 10:27:00 +0100 | [diff] [blame] | 1443 | #if defined(MBEDTLS_HAVE_UDBL) |
| 1444 | mbedtls_t_udbl dividend, quotient; |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1445 | #else |
Simon Butcher | 9803d07 | 2016-01-03 00:24:34 +0000 | [diff] [blame] | 1446 | const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH; |
| 1447 | const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1; |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1448 | mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient; |
| 1449 | mbedtls_mpi_uint u0_msw, u0_lsw; |
Simon Butcher | 9803d07 | 2016-01-03 00:24:34 +0000 | [diff] [blame] | 1450 | size_t s; |
Manuel Pégourié-Gonnard | 1630888 | 2015-12-01 10:27:00 +0100 | [diff] [blame] | 1451 | #endif |
| 1452 | |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1453 | /* |
| 1454 | * Check for overflow |
| 1455 | */ |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1456 | if( 0 == d || u1 >= d ) |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1457 | { |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1458 | if (r != NULL) *r = ~0; |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1459 | |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1460 | return ( ~0 ); |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1461 | } |
| 1462 | |
| 1463 | #if defined(MBEDTLS_HAVE_UDBL) |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1464 | dividend = (mbedtls_t_udbl) u1 << biL; |
| 1465 | dividend |= (mbedtls_t_udbl) u0; |
| 1466 | quotient = dividend / d; |
| 1467 | if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 ) |
| 1468 | quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1; |
| 1469 | |
| 1470 | if( r != NULL ) |
Simon Butcher | 9803d07 | 2016-01-03 00:24:34 +0000 | [diff] [blame] | 1471 | *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) ); |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1472 | |
| 1473 | return (mbedtls_mpi_uint) quotient; |
| 1474 | #else |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1475 | |
| 1476 | /* |
| 1477 | * Algorithm D, Section 4.3.1 - The Art of Computer Programming |
| 1478 | * Vol. 2 - Seminumerical Algorithms, Knuth |
| 1479 | */ |
| 1480 | |
| 1481 | /* |
| 1482 | * Normalize the divisor, d, and dividend, u0, u1 |
| 1483 | */ |
| 1484 | s = mbedtls_clz( d ); |
| 1485 | d = d << s; |
| 1486 | |
| 1487 | u1 = u1 << s; |
Simon Butcher | 9803d07 | 2016-01-03 00:24:34 +0000 | [diff] [blame] | 1488 | u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) ); |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1489 | u0 = u0 << s; |
| 1490 | |
| 1491 | d1 = d >> biH; |
Simon Butcher | 9803d07 | 2016-01-03 00:24:34 +0000 | [diff] [blame] | 1492 | d0 = d & uint_halfword_mask; |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1493 | |
| 1494 | u0_msw = u0 >> biH; |
Simon Butcher | 9803d07 | 2016-01-03 00:24:34 +0000 | [diff] [blame] | 1495 | u0_lsw = u0 & uint_halfword_mask; |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1496 | |
| 1497 | /* |
| 1498 | * Find the first quotient and remainder |
| 1499 | */ |
| 1500 | q1 = u1 / d1; |
| 1501 | r0 = u1 - d1 * q1; |
| 1502 | |
| 1503 | while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) ) |
| 1504 | { |
| 1505 | q1 -= 1; |
| 1506 | r0 += d1; |
| 1507 | |
| 1508 | if ( r0 >= radix ) break; |
| 1509 | } |
| 1510 | |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1511 | rAX = ( u1 * radix ) + ( u0_msw - q1 * d ); |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1512 | q0 = rAX / d1; |
| 1513 | r0 = rAX - q0 * d1; |
| 1514 | |
| 1515 | while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) ) |
| 1516 | { |
| 1517 | q0 -= 1; |
| 1518 | r0 += d1; |
| 1519 | |
| 1520 | if ( r0 >= radix ) break; |
| 1521 | } |
| 1522 | |
| 1523 | if (r != NULL) |
Simon Butcher | f5ba045 | 2015-12-27 23:01:55 +0000 | [diff] [blame] | 1524 | *r = ( rAX * radix + u0_lsw - q0 * d ) >> s; |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1525 | |
| 1526 | quotient = q1 * radix + q0; |
| 1527 | |
| 1528 | return quotient; |
| 1529 | #endif |
| 1530 | } |
| 1531 | |
| 1532 | /* |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1533 | * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1534 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1535 | int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1536 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1537 | int ret; |
| 1538 | size_t i, n, t, k; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1539 | mbedtls_mpi X, Y, Z, T1, T2; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1540 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1541 | if( mbedtls_mpi_cmp_int( B, 0 ) == 0 ) |
| 1542 | return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1543 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1544 | mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z ); |
| 1545 | mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1546 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1547 | if( mbedtls_mpi_cmp_abs( A, B ) < 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1548 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1549 | if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) ); |
| 1550 | if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1551 | return( 0 ); |
| 1552 | } |
| 1553 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1554 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) ); |
| 1555 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1556 | X.s = Y.s = 1; |
| 1557 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1558 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) ); |
| 1559 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) ); |
| 1560 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) ); |
| 1561 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1562 | |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 1563 | k = mbedtls_mpi_bitlen( &Y ) % biL; |
Paul Bakker | f968857 | 2011-05-05 10:00:45 +0000 | [diff] [blame] | 1564 | if( k < biL - 1 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1565 | { |
| 1566 | k = biL - 1 - k; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1567 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) ); |
| 1568 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1569 | } |
| 1570 | else k = 0; |
| 1571 | |
| 1572 | n = X.n - 1; |
| 1573 | t = Y.n - 1; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1574 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1575 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1576 | while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1577 | { |
| 1578 | Z.p[n - t]++; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1579 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1580 | } |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1581 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1582 | |
| 1583 | for( i = n; i > t ; i-- ) |
| 1584 | { |
| 1585 | if( X.p[i] >= Y.p[t] ) |
| 1586 | Z.p[i - t - 1] = ~0; |
| 1587 | else |
| 1588 | { |
Simon Butcher | 15b15d1 | 2015-11-26 19:35:03 +0000 | [diff] [blame] | 1589 | Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1], |
| 1590 | Y.p[t], NULL); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1591 | } |
| 1592 | |
| 1593 | Z.p[i - t - 1]++; |
| 1594 | do |
| 1595 | { |
| 1596 | Z.p[i - t - 1]--; |
| 1597 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1598 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) ); |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 1599 | T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1600 | T1.p[1] = Y.p[t]; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1601 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1602 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1603 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) ); |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 1604 | T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2]; |
| 1605 | T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1606 | T2.p[2] = X.p[i]; |
| 1607 | } |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1608 | while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1609 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1610 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) ); |
| 1611 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); |
| 1612 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1613 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1614 | if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1615 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1616 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) ); |
| 1617 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); |
| 1618 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1619 | Z.p[i - t - 1]--; |
| 1620 | } |
| 1621 | } |
| 1622 | |
| 1623 | if( Q != NULL ) |
| 1624 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1625 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1626 | Q->s = A->s * B->s; |
| 1627 | } |
| 1628 | |
| 1629 | if( R != NULL ) |
| 1630 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1631 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) ); |
Paul Bakker | f02c564 | 2012-11-13 10:25:21 +0000 | [diff] [blame] | 1632 | X.s = A->s; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1633 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1634 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1635 | if( mbedtls_mpi_cmp_int( R, 0 ) == 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1636 | R->s = 1; |
| 1637 | } |
| 1638 | |
| 1639 | cleanup: |
| 1640 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1641 | mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); |
| 1642 | mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1643 | |
| 1644 | return( ret ); |
| 1645 | } |
| 1646 | |
| 1647 | /* |
| 1648 | * Division by int: A = Q * b + R |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1649 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1650 | int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1651 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1652 | mbedtls_mpi _B; |
| 1653 | mbedtls_mpi_uint p[1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1654 | |
| 1655 | p[0] = ( b < 0 ) ? -b : b; |
| 1656 | _B.s = ( b < 0 ) ? -1 : 1; |
| 1657 | _B.n = 1; |
| 1658 | _B.p = p; |
| 1659 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1660 | return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1661 | } |
| 1662 | |
| 1663 | /* |
| 1664 | * Modulo: R = A mod B |
| 1665 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1666 | int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1667 | { |
| 1668 | int ret; |
| 1669 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1670 | if( mbedtls_mpi_cmp_int( B, 0 ) < 0 ) |
| 1671 | return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); |
Paul Bakker | ce40a6d | 2009-06-23 19:46:08 +0000 | [diff] [blame] | 1672 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1673 | MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1674 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1675 | while( mbedtls_mpi_cmp_int( R, 0 ) < 0 ) |
| 1676 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1677 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1678 | while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 ) |
| 1679 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1680 | |
| 1681 | cleanup: |
| 1682 | |
| 1683 | return( ret ); |
| 1684 | } |
| 1685 | |
| 1686 | /* |
| 1687 | * Modulo: r = A mod b |
| 1688 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1689 | int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1690 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1691 | size_t i; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1692 | mbedtls_mpi_uint x, y, z; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1693 | |
| 1694 | if( b == 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1695 | return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1696 | |
| 1697 | if( b < 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1698 | return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1699 | |
| 1700 | /* |
| 1701 | * handle trivial cases |
| 1702 | */ |
| 1703 | if( b == 1 ) |
| 1704 | { |
| 1705 | *r = 0; |
| 1706 | return( 0 ); |
| 1707 | } |
| 1708 | |
| 1709 | if( b == 2 ) |
| 1710 | { |
| 1711 | *r = A->p[0] & 1; |
| 1712 | return( 0 ); |
| 1713 | } |
| 1714 | |
| 1715 | /* |
| 1716 | * general case |
| 1717 | */ |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1718 | for( i = A->n, y = 0; i > 0; i-- ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1719 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1720 | x = A->p[i - 1]; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1721 | y = ( y << biH ) | ( x >> biH ); |
| 1722 | z = y / b; |
| 1723 | y -= z * b; |
| 1724 | |
| 1725 | x <<= biH; |
| 1726 | y = ( y << biH ) | ( x >> biH ); |
| 1727 | z = y / b; |
| 1728 | y -= z * b; |
| 1729 | } |
| 1730 | |
Paul Bakker | ce40a6d | 2009-06-23 19:46:08 +0000 | [diff] [blame] | 1731 | /* |
| 1732 | * If A is negative, then the current y represents a negative value. |
| 1733 | * Flipping it to the positive side. |
| 1734 | */ |
| 1735 | if( A->s < 0 && y != 0 ) |
| 1736 | y = b - y; |
| 1737 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1738 | *r = y; |
| 1739 | |
| 1740 | return( 0 ); |
| 1741 | } |
| 1742 | |
| 1743 | /* |
| 1744 | * Fast Montgomery initialization (thanks to Tom St Denis) |
| 1745 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1746 | static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1747 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1748 | mbedtls_mpi_uint x, m0 = N->p[0]; |
Manuel Pégourié-Gonnard | fdf3f0e | 2014-03-11 13:47:05 +0100 | [diff] [blame] | 1749 | unsigned int i; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1750 | |
| 1751 | x = m0; |
| 1752 | x += ( ( m0 + 2 ) & 4 ) << 1; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1753 | |
Manuel Pégourié-Gonnard | fdf3f0e | 2014-03-11 13:47:05 +0100 | [diff] [blame] | 1754 | for( i = biL; i >= 8; i /= 2 ) |
| 1755 | x *= ( 2 - ( m0 * x ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1756 | |
| 1757 | *mm = ~x + 1; |
| 1758 | } |
| 1759 | |
Gilles Peskine | d108d07 | 2020-06-04 15:00:49 +0200 | [diff] [blame] | 1760 | /** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36) |
| 1761 | * |
| 1762 | * \param[in,out] A One of the numbers to multiply. |
Gilles Peskine | cc6a6bf | 2020-06-08 22:37:50 +0200 | [diff] [blame] | 1763 | * It must have at least as many limbs as N |
| 1764 | * (A->n >= N->n), and any limbs beyond n are ignored. |
Gilles Peskine | d108d07 | 2020-06-04 15:00:49 +0200 | [diff] [blame] | 1765 | * On successful completion, A contains the result of |
| 1766 | * the multiplication A * B * R^-1 mod N where |
| 1767 | * R = (2^ciL)^n. |
| 1768 | * \param[in] B One of the numbers to multiply. |
| 1769 | * It must be nonzero and must not have more limbs than N |
| 1770 | * (B->n <= N->n). |
| 1771 | * \param[in] N The modulo. N must be odd. |
| 1772 | * \param mm The value calculated by `mpi_montg_init(&mm, N)`. |
| 1773 | * This is -N^-1 mod 2^ciL. |
| 1774 | * \param[in,out] T A bignum for temporary storage. |
| 1775 | * It must be at least twice the limb size of N plus 2 |
| 1776 | * (T->n >= 2 * (N->n + 1)). |
| 1777 | * Its initial content is unused and |
| 1778 | * its final content is indeterminate. |
| 1779 | * Note that unlike the usual convention in the library |
| 1780 | * for `const mbedtls_mpi*`, the content of T can change. |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1781 | */ |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 1782 | static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm, |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1783 | const mbedtls_mpi *T ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1784 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1785 | size_t i, n, m; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1786 | mbedtls_mpi_uint u0, u1, *d; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1787 | |
| 1788 | memset( T->p, 0, T->n * ciL ); |
| 1789 | |
| 1790 | d = T->p; |
| 1791 | n = N->n; |
| 1792 | m = ( B->n < n ) ? B->n : n; |
| 1793 | |
| 1794 | for( i = 0; i < n; i++ ) |
| 1795 | { |
| 1796 | /* |
| 1797 | * T = (T + u0*B + u1*N) / 2^biL |
| 1798 | */ |
| 1799 | u0 = A->p[i]; |
| 1800 | u1 = ( d[0] + u0 * B->p[0] ) * mm; |
| 1801 | |
| 1802 | mpi_mul_hlp( m, B->p, d, u0 ); |
| 1803 | mpi_mul_hlp( n, N->p, d, u1 ); |
| 1804 | |
| 1805 | *d++ = u0; d[n + 1] = 0; |
| 1806 | } |
| 1807 | |
Gilles Peskine | cc6a6bf | 2020-06-08 22:37:50 +0200 | [diff] [blame] | 1808 | /* At this point, d is either the desired result or the desired result |
| 1809 | * plus N. We now potentially subtract N, avoiding leaking whether the |
| 1810 | * subtraction is performed through side channels. */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1811 | |
Gilles Peskine | cc6a6bf | 2020-06-08 22:37:50 +0200 | [diff] [blame] | 1812 | /* Copy the n least significant limbs of d to A, so that |
| 1813 | * A = d if d < N (recall that N has n limbs). */ |
| 1814 | memcpy( A->p, d, n * ciL ); |
Gilles Peskine | f3317e6 | 2020-06-09 10:39:38 +0200 | [diff] [blame] | 1815 | /* If d >= N then we want to set A to d - N. To prevent timing attacks, |
Gilles Peskine | cc6a6bf | 2020-06-08 22:37:50 +0200 | [diff] [blame] | 1816 | * do the calculation without using conditional tests. */ |
| 1817 | /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */ |
Gilles Peskine | 7ff812e | 2020-06-04 21:05:24 +0200 | [diff] [blame] | 1818 | d[n] += 1; |
Gilles Peskine | 6f3b68d | 2020-06-08 21:58:22 +0200 | [diff] [blame] | 1819 | d[n] -= mpi_sub_hlp( n, d, N->p ); |
Gilles Peskine | cc6a6bf | 2020-06-08 22:37:50 +0200 | [diff] [blame] | 1820 | /* If d0 < N then d < (2^biL)^n |
| 1821 | * so d[n] == 0 and we want to keep A as it is. |
| 1822 | * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n |
| 1823 | * so d[n] == 1 and we want to set A to the result of the subtraction |
| 1824 | * which is d - (2^biL)^n, i.e. the n least significant limbs of d. |
| 1825 | * This exactly corresponds to a conditional assignment. */ |
| 1826 | mpi_safe_cond_assign( n, A->p, d, (unsigned char) d[n] ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1827 | } |
| 1828 | |
| 1829 | /* |
| 1830 | * Montgomery reduction: A = A * R^-1 mod N |
Gilles Peskine | d108d07 | 2020-06-04 15:00:49 +0200 | [diff] [blame] | 1831 | * |
| 1832 | * See mpi_montmul() regarding constraints and guarantees on the parameters. |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1833 | */ |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 1834 | static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, mbedtls_mpi_uint mm, const mbedtls_mpi *T ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1835 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1836 | mbedtls_mpi_uint z = 1; |
| 1837 | mbedtls_mpi U; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1838 | |
Paul Bakker | 8ddb645 | 2013-02-27 14:56:33 +0100 | [diff] [blame] | 1839 | U.n = U.s = (int) z; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1840 | U.p = &z; |
| 1841 | |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 1842 | mpi_montmul( A, &U, N, mm, T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1843 | } |
| 1844 | |
| 1845 | /* |
| 1846 | * Sliding-window exponentiation: X = A^E mod N (HAC 14.85) |
| 1847 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1848 | int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1849 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 1850 | int ret; |
| 1851 | size_t wbits, wsize, one = 1; |
| 1852 | size_t i, j, nblimbs; |
| 1853 | size_t bufsize, nbits; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1854 | mbedtls_mpi_uint ei, mm, state; |
| 1855 | mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos; |
Paul Bakker | f6198c1 | 2012-05-16 08:02:29 +0000 | [diff] [blame] | 1856 | int neg; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1857 | |
Hanno Becker | 930ec7d | 2018-03-09 10:48:00 +0000 | [diff] [blame] | 1858 | if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1859 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1860 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1861 | if( mbedtls_mpi_cmp_int( E, 0 ) < 0 ) |
| 1862 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
Paul Bakker | f6198c1 | 2012-05-16 08:02:29 +0000 | [diff] [blame] | 1863 | |
| 1864 | /* |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1865 | * Init temps and window size |
| 1866 | */ |
| 1867 | mpi_montg_init( &mm, N ); |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1868 | mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T ); |
| 1869 | mbedtls_mpi_init( &Apos ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1870 | memset( W, 0, sizeof( W ) ); |
| 1871 | |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 1872 | i = mbedtls_mpi_bitlen( E ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1873 | |
| 1874 | wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 : |
| 1875 | ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1; |
| 1876 | |
Peter Kolbus | f5d153d | 2018-12-11 14:01:44 -0600 | [diff] [blame] | 1877 | #if( MBEDTLS_MPI_WINDOW_SIZE < 6 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1878 | if( wsize > MBEDTLS_MPI_WINDOW_SIZE ) |
| 1879 | wsize = MBEDTLS_MPI_WINDOW_SIZE; |
Peter Kolbus | f5d153d | 2018-12-11 14:01:44 -0600 | [diff] [blame] | 1880 | #endif |
Paul Bakker | b6d5f08 | 2011-11-25 11:52:11 +0000 | [diff] [blame] | 1881 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1882 | j = N->n + 1; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1883 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); |
| 1884 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) ); |
| 1885 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1886 | |
| 1887 | /* |
Paul Bakker | 5054692 | 2012-05-19 08:40:49 +0000 | [diff] [blame] | 1888 | * Compensate for negative A (and correct at the end) |
| 1889 | */ |
| 1890 | neg = ( A->s == -1 ); |
Paul Bakker | 5054692 | 2012-05-19 08:40:49 +0000 | [diff] [blame] | 1891 | if( neg ) |
| 1892 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1893 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) ); |
Paul Bakker | 5054692 | 2012-05-19 08:40:49 +0000 | [diff] [blame] | 1894 | Apos.s = 1; |
| 1895 | A = &Apos; |
| 1896 | } |
| 1897 | |
| 1898 | /* |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1899 | * If 1st call, pre-compute R^2 mod N |
| 1900 | */ |
| 1901 | if( _RR == NULL || _RR->p == NULL ) |
| 1902 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1903 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) ); |
| 1904 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) ); |
| 1905 | MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1906 | |
| 1907 | if( _RR != NULL ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1908 | memcpy( _RR, &RR, sizeof( mbedtls_mpi ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1909 | } |
| 1910 | else |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1911 | memcpy( &RR, _RR, sizeof( mbedtls_mpi ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1912 | |
| 1913 | /* |
| 1914 | * W[1] = A * R^2 * R^-1 mod N = A * R mod N |
| 1915 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1916 | if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 ) |
| 1917 | MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) ); |
Paul Bakker | c2024f4 | 2014-01-23 20:38:35 +0100 | [diff] [blame] | 1918 | else |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1919 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1920 | |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 1921 | mpi_montmul( &W[1], &RR, N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1922 | |
| 1923 | /* |
| 1924 | * X = R^2 * R^-1 mod N = R mod N |
| 1925 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1926 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) ); |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 1927 | mpi_montred( X, N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1928 | |
| 1929 | if( wsize > 1 ) |
| 1930 | { |
| 1931 | /* |
| 1932 | * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1) |
| 1933 | */ |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 1934 | j = one << ( wsize - 1 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1935 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1936 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) ); |
| 1937 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1938 | |
| 1939 | for( i = 0; i < wsize - 1; i++ ) |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 1940 | mpi_montmul( &W[j], &W[j], N, mm, &T ); |
Paul Bakker | 0d7702c | 2013-10-29 16:18:35 +0100 | [diff] [blame] | 1941 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1942 | /* |
| 1943 | * W[i] = W[i - 1] * W[1] |
| 1944 | */ |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 1945 | for( i = j + 1; i < ( one << wsize ); i++ ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1946 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1947 | MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) ); |
| 1948 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1949 | |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 1950 | mpi_montmul( &W[i], &W[1], N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1951 | } |
| 1952 | } |
| 1953 | |
| 1954 | nblimbs = E->n; |
| 1955 | bufsize = 0; |
| 1956 | nbits = 0; |
| 1957 | wbits = 0; |
| 1958 | state = 0; |
| 1959 | |
| 1960 | while( 1 ) |
| 1961 | { |
| 1962 | if( bufsize == 0 ) |
| 1963 | { |
Paul Bakker | 0d7702c | 2013-10-29 16:18:35 +0100 | [diff] [blame] | 1964 | if( nblimbs == 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1965 | break; |
| 1966 | |
Paul Bakker | 0d7702c | 2013-10-29 16:18:35 +0100 | [diff] [blame] | 1967 | nblimbs--; |
| 1968 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 1969 | bufsize = sizeof( mbedtls_mpi_uint ) << 3; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1970 | } |
| 1971 | |
| 1972 | bufsize--; |
| 1973 | |
| 1974 | ei = (E->p[nblimbs] >> bufsize) & 1; |
| 1975 | |
| 1976 | /* |
| 1977 | * skip leading 0s |
| 1978 | */ |
| 1979 | if( ei == 0 && state == 0 ) |
| 1980 | continue; |
| 1981 | |
| 1982 | if( ei == 0 && state == 1 ) |
| 1983 | { |
| 1984 | /* |
| 1985 | * out of window, square X |
| 1986 | */ |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 1987 | mpi_montmul( X, X, N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1988 | continue; |
| 1989 | } |
| 1990 | |
| 1991 | /* |
| 1992 | * add ei to current window |
| 1993 | */ |
| 1994 | state = 2; |
| 1995 | |
| 1996 | nbits++; |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 1997 | wbits |= ( ei << ( wsize - nbits ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 1998 | |
| 1999 | if( nbits == wsize ) |
| 2000 | { |
| 2001 | /* |
| 2002 | * X = X^wsize R^-1 mod N |
| 2003 | */ |
| 2004 | for( i = 0; i < wsize; i++ ) |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 2005 | mpi_montmul( X, X, N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2006 | |
| 2007 | /* |
| 2008 | * X = X * W[wbits] R^-1 mod N |
| 2009 | */ |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 2010 | mpi_montmul( X, &W[wbits], N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2011 | |
| 2012 | state--; |
| 2013 | nbits = 0; |
| 2014 | wbits = 0; |
| 2015 | } |
| 2016 | } |
| 2017 | |
| 2018 | /* |
| 2019 | * process the remaining bits |
| 2020 | */ |
| 2021 | for( i = 0; i < nbits; i++ ) |
| 2022 | { |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 2023 | mpi_montmul( X, X, N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2024 | |
| 2025 | wbits <<= 1; |
| 2026 | |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 2027 | if( ( wbits & ( one << wsize ) ) != 0 ) |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 2028 | mpi_montmul( X, &W[1], N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2029 | } |
| 2030 | |
| 2031 | /* |
| 2032 | * X = A^E * R * R^-1 mod N = A^E mod N |
| 2033 | */ |
Gilles Peskine | 8ff7cc9 | 2020-06-04 20:55:15 +0200 | [diff] [blame] | 2034 | mpi_montred( X, N, mm, &T ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2035 | |
Hanno Becker | a4af1c4 | 2017-04-18 09:07:45 +0100 | [diff] [blame] | 2036 | if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 ) |
Paul Bakker | f6198c1 | 2012-05-16 08:02:29 +0000 | [diff] [blame] | 2037 | { |
| 2038 | X->s = -1; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2039 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) ); |
Paul Bakker | f6198c1 | 2012-05-16 08:02:29 +0000 | [diff] [blame] | 2040 | } |
| 2041 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2042 | cleanup: |
| 2043 | |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 2044 | for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2045 | mbedtls_mpi_free( &W[i] ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2046 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2047 | mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos ); |
Paul Bakker | 6c591fa | 2011-05-05 11:49:20 +0000 | [diff] [blame] | 2048 | |
Paul Bakker | 75a2860 | 2014-03-31 12:08:17 +0200 | [diff] [blame] | 2049 | if( _RR == NULL || _RR->p == NULL ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2050 | mbedtls_mpi_free( &RR ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2051 | |
| 2052 | return( ret ); |
| 2053 | } |
| 2054 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2055 | /* |
| 2056 | * Greatest common divisor: G = gcd(A, B) (HAC 14.54) |
| 2057 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2058 | int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2059 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 2060 | int ret; |
| 2061 | size_t lz, lzt; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2062 | mbedtls_mpi TG, TA, TB; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2063 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2064 | mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2065 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2066 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); |
| 2067 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2068 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2069 | lz = mbedtls_mpi_lsb( &TA ); |
| 2070 | lzt = mbedtls_mpi_lsb( &TB ); |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2071 | |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 2072 | if( lzt < lz ) |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2073 | lz = lzt; |
| 2074 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2075 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) ); |
| 2076 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) ); |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2077 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2078 | TA.s = TB.s = 1; |
| 2079 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2080 | while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2081 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2082 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) ); |
| 2083 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2084 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2085 | if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2086 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2087 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) ); |
| 2088 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2089 | } |
| 2090 | else |
| 2091 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2092 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) ); |
| 2093 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2094 | } |
| 2095 | } |
| 2096 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2097 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) ); |
| 2098 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2099 | |
| 2100 | cleanup: |
| 2101 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2102 | mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2103 | |
| 2104 | return( ret ); |
| 2105 | } |
| 2106 | |
Paul Bakker | 33dc46b | 2014-04-30 16:11:39 +0200 | [diff] [blame] | 2107 | /* |
| 2108 | * Fill X with size bytes of random. |
| 2109 | * |
| 2110 | * Use a temporary bytes representation to make sure the result is the same |
Paul Bakker | c37b0ac | 2014-05-01 14:19:23 +0200 | [diff] [blame] | 2111 | * regardless of the platform endianness (useful when f_rng is actually |
Paul Bakker | 33dc46b | 2014-04-30 16:11:39 +0200 | [diff] [blame] | 2112 | * deterministic, eg for tests). |
| 2113 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2114 | int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size, |
Paul Bakker | a3d195c | 2011-11-27 21:07:34 +0000 | [diff] [blame] | 2115 | int (*f_rng)(void *, unsigned char *, size_t), |
| 2116 | void *p_rng ) |
Paul Bakker | 287781a | 2011-03-26 13:18:49 +0000 | [diff] [blame] | 2117 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 2118 | int ret; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2119 | unsigned char buf[MBEDTLS_MPI_MAX_SIZE]; |
Paul Bakker | 33dc46b | 2014-04-30 16:11:39 +0200 | [diff] [blame] | 2120 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2121 | if( size > MBEDTLS_MPI_MAX_SIZE ) |
| 2122 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
Paul Bakker | 287781a | 2011-03-26 13:18:49 +0000 | [diff] [blame] | 2123 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2124 | MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) ); |
| 2125 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) ); |
Paul Bakker | 287781a | 2011-03-26 13:18:49 +0000 | [diff] [blame] | 2126 | |
| 2127 | cleanup: |
Hanno Becker | 8880711 | 2017-10-18 12:41:30 +0100 | [diff] [blame] | 2128 | mbedtls_zeroize( buf, sizeof( buf ) ); |
Paul Bakker | 287781a | 2011-03-26 13:18:49 +0000 | [diff] [blame] | 2129 | return( ret ); |
| 2130 | } |
| 2131 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2132 | /* |
| 2133 | * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64) |
| 2134 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2135 | int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2136 | { |
| 2137 | int ret; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2138 | mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2139 | |
Hanno Becker | 4bcb491 | 2017-04-18 15:49:39 +0100 | [diff] [blame] | 2140 | if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2141 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2142 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2143 | mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 ); |
| 2144 | mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV ); |
| 2145 | mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2146 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2147 | MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2148 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2149 | if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2150 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2151 | ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2152 | goto cleanup; |
| 2153 | } |
| 2154 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2155 | MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) ); |
| 2156 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) ); |
| 2157 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) ); |
| 2158 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2159 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2160 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) ); |
| 2161 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) ); |
| 2162 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) ); |
| 2163 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2164 | |
| 2165 | do |
| 2166 | { |
| 2167 | while( ( TU.p[0] & 1 ) == 0 ) |
| 2168 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2169 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2170 | |
| 2171 | if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 ) |
| 2172 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2173 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) ); |
| 2174 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2175 | } |
| 2176 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2177 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) ); |
| 2178 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2179 | } |
| 2180 | |
| 2181 | while( ( TV.p[0] & 1 ) == 0 ) |
| 2182 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2183 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2184 | |
| 2185 | if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 ) |
| 2186 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2187 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) ); |
| 2188 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2189 | } |
| 2190 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2191 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) ); |
| 2192 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2193 | } |
| 2194 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2195 | if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2196 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2197 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) ); |
| 2198 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) ); |
| 2199 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2200 | } |
| 2201 | else |
| 2202 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2203 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) ); |
| 2204 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) ); |
| 2205 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2206 | } |
| 2207 | } |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2208 | while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2209 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2210 | while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 ) |
| 2211 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2212 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2213 | while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 ) |
| 2214 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2215 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2216 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2217 | |
| 2218 | cleanup: |
| 2219 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2220 | mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 ); |
| 2221 | mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV ); |
| 2222 | mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2223 | |
| 2224 | return( ret ); |
| 2225 | } |
| 2226 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2227 | #if defined(MBEDTLS_GENPRIME) |
Paul Bakker | d9374b0 | 2012-11-02 11:02:58 +0000 | [diff] [blame] | 2228 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2229 | static const int small_prime[] = |
| 2230 | { |
| 2231 | 3, 5, 7, 11, 13, 17, 19, 23, |
| 2232 | 29, 31, 37, 41, 43, 47, 53, 59, |
| 2233 | 61, 67, 71, 73, 79, 83, 89, 97, |
| 2234 | 101, 103, 107, 109, 113, 127, 131, 137, |
| 2235 | 139, 149, 151, 157, 163, 167, 173, 179, |
| 2236 | 181, 191, 193, 197, 199, 211, 223, 227, |
| 2237 | 229, 233, 239, 241, 251, 257, 263, 269, |
| 2238 | 271, 277, 281, 283, 293, 307, 311, 313, |
| 2239 | 317, 331, 337, 347, 349, 353, 359, 367, |
| 2240 | 373, 379, 383, 389, 397, 401, 409, 419, |
| 2241 | 421, 431, 433, 439, 443, 449, 457, 461, |
| 2242 | 463, 467, 479, 487, 491, 499, 503, 509, |
| 2243 | 521, 523, 541, 547, 557, 563, 569, 571, |
| 2244 | 577, 587, 593, 599, 601, 607, 613, 617, |
| 2245 | 619, 631, 641, 643, 647, 653, 659, 661, |
| 2246 | 673, 677, 683, 691, 701, 709, 719, 727, |
| 2247 | 733, 739, 743, 751, 757, 761, 769, 773, |
| 2248 | 787, 797, 809, 811, 821, 823, 827, 829, |
| 2249 | 839, 853, 857, 859, 863, 877, 881, 883, |
| 2250 | 887, 907, 911, 919, 929, 937, 941, 947, |
| 2251 | 953, 967, 971, 977, 983, 991, 997, -103 |
| 2252 | }; |
| 2253 | |
| 2254 | /* |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2255 | * Small divisors test (X must be positive) |
| 2256 | * |
| 2257 | * Return values: |
| 2258 | * 0: no small factor (possible prime, more tests needed) |
| 2259 | * 1: certain prime |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2260 | * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2261 | * other negative: error |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2262 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2263 | static int mpi_check_small_factors( const mbedtls_mpi *X ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2264 | { |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2265 | int ret = 0; |
| 2266 | size_t i; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2267 | mbedtls_mpi_uint r; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2268 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2269 | if( ( X->p[0] & 1 ) == 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2270 | return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2271 | |
| 2272 | for( i = 0; small_prime[i] > 0; i++ ) |
| 2273 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2274 | if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 ) |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2275 | return( 1 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2276 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2277 | MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2278 | |
| 2279 | if( r == 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2280 | return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2281 | } |
| 2282 | |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2283 | cleanup: |
| 2284 | return( ret ); |
| 2285 | } |
| 2286 | |
| 2287 | /* |
| 2288 | * Miller-Rabin pseudo-primality test (HAC 4.24) |
| 2289 | */ |
Janos Follath | 72d555d | 2018-09-03 14:45:23 +0100 | [diff] [blame] | 2290 | static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds, |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2291 | int (*f_rng)(void *, unsigned char *, size_t), |
| 2292 | void *p_rng ) |
| 2293 | { |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 2294 | int ret, count; |
Janos Follath | 72d555d | 2018-09-03 14:45:23 +0100 | [diff] [blame] | 2295 | size_t i, j, k, s; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2296 | mbedtls_mpi W, R, T, A, RR; |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2297 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2298 | mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A ); |
| 2299 | mbedtls_mpi_init( &RR ); |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2300 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2301 | /* |
| 2302 | * W = |X| - 1 |
| 2303 | * R = W >> lsb( W ) |
| 2304 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2305 | MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) ); |
| 2306 | s = mbedtls_mpi_lsb( &W ); |
| 2307 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) ); |
| 2308 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2309 | |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 2310 | i = mbedtls_mpi_bitlen( X ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2311 | |
Janos Follath | 72d555d | 2018-09-03 14:45:23 +0100 | [diff] [blame] | 2312 | for( i = 0; i < rounds; i++ ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2313 | { |
| 2314 | /* |
| 2315 | * pick a random A, 1 < A < |X| - 1 |
| 2316 | */ |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 2317 | count = 0; |
| 2318 | do { |
Manuel Pégourié-Gonnard | 53c76c0 | 2015-04-17 20:15:36 +0200 | [diff] [blame] | 2319 | MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) ); |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 2320 | |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 2321 | j = mbedtls_mpi_bitlen( &A ); |
| 2322 | k = mbedtls_mpi_bitlen( &W ); |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 2323 | if (j > k) { |
Darryl Green | 56d7cc4 | 2018-10-02 13:21:35 +0100 | [diff] [blame] | 2324 | A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1; |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 2325 | } |
| 2326 | |
| 2327 | if (count++ > 30) { |
Jens Wiklander | b2aa938 | 2019-01-17 13:30:57 +0100 | [diff] [blame] | 2328 | ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
| 2329 | goto cleanup; |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 2330 | } |
| 2331 | |
Manuel Pégourié-Gonnard | 53c76c0 | 2015-04-17 20:15:36 +0200 | [diff] [blame] | 2332 | } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 || |
| 2333 | mbedtls_mpi_cmp_int( &A, 1 ) <= 0 ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2334 | |
| 2335 | /* |
| 2336 | * A = A^R mod |X| |
| 2337 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2338 | MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2339 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2340 | if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 || |
| 2341 | mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2342 | continue; |
| 2343 | |
| 2344 | j = 1; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2345 | while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2346 | { |
| 2347 | /* |
| 2348 | * A = A * A mod |X| |
| 2349 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2350 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) ); |
| 2351 | MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2352 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2353 | if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2354 | break; |
| 2355 | |
| 2356 | j++; |
| 2357 | } |
| 2358 | |
| 2359 | /* |
| 2360 | * not prime if A != |X| - 1 or A == 1 |
| 2361 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2362 | if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 || |
| 2363 | mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2364 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2365 | ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2366 | break; |
| 2367 | } |
| 2368 | } |
| 2369 | |
| 2370 | cleanup: |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2371 | mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A ); |
| 2372 | mbedtls_mpi_free( &RR ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2373 | |
| 2374 | return( ret ); |
| 2375 | } |
| 2376 | |
| 2377 | /* |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2378 | * Pseudo-primality test: small factors, then Miller-Rabin |
| 2379 | */ |
Darryl Green | 94759f6 | 2018-10-16 15:09:19 +0100 | [diff] [blame] | 2380 | static int mpi_is_prime_internal( const mbedtls_mpi *X, int rounds, |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2381 | int (*f_rng)(void *, unsigned char *, size_t), |
| 2382 | void *p_rng ) |
| 2383 | { |
| 2384 | int ret; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2385 | mbedtls_mpi XX; |
Manuel Pégourié-Gonnard | 7f4ed67 | 2014-10-14 20:56:02 +0200 | [diff] [blame] | 2386 | |
| 2387 | XX.s = 1; |
| 2388 | XX.n = X->n; |
| 2389 | XX.p = X->p; |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2390 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2391 | if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 || |
| 2392 | mbedtls_mpi_cmp_int( &XX, 1 ) == 0 ) |
| 2393 | return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2394 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2395 | if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 ) |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2396 | return( 0 ); |
| 2397 | |
| 2398 | if( ( ret = mpi_check_small_factors( &XX ) ) != 0 ) |
| 2399 | { |
| 2400 | if( ret == 1 ) |
| 2401 | return( 0 ); |
| 2402 | |
| 2403 | return( ret ); |
| 2404 | } |
| 2405 | |
Janos Follath | 72d555d | 2018-09-03 14:45:23 +0100 | [diff] [blame] | 2406 | return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) ); |
| 2407 | } |
| 2408 | |
| 2409 | /* |
| 2410 | * Pseudo-primality test, error probability 2^-80 |
| 2411 | */ |
| 2412 | int mbedtls_mpi_is_prime( const mbedtls_mpi *X, |
| 2413 | int (*f_rng)(void *, unsigned char *, size_t), |
| 2414 | void *p_rng ) |
| 2415 | { |
| 2416 | return mpi_is_prime_internal( X, 40, f_rng, p_rng ); |
Manuel Pégourié-Gonnard | 378fb4b | 2013-11-22 18:39:18 +0100 | [diff] [blame] | 2417 | } |
| 2418 | |
| 2419 | /* |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2420 | * Prime number generation |
| 2421 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2422 | int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag, |
Paul Bakker | a3d195c | 2011-11-27 21:07:34 +0000 | [diff] [blame] | 2423 | int (*f_rng)(void *, unsigned char *, size_t), |
| 2424 | void *p_rng ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2425 | { |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 2426 | int ret; |
| 2427 | size_t k, n; |
Janos Follath | 72d555d | 2018-09-03 14:45:23 +0100 | [diff] [blame] | 2428 | int rounds; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2429 | mbedtls_mpi_uint r; |
| 2430 | mbedtls_mpi Y; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2431 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2432 | if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS ) |
| 2433 | return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2434 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2435 | mbedtls_mpi_init( &Y ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2436 | |
| 2437 | n = BITS_TO_LIMBS( nbits ); |
| 2438 | |
Janos Follath | 72d555d | 2018-09-03 14:45:23 +0100 | [diff] [blame] | 2439 | /* |
| 2440 | * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 |
| 2441 | */ |
| 2442 | rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 : |
| 2443 | ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 : |
| 2444 | ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 ); |
| 2445 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2446 | MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2447 | |
Manuel Pégourié-Gonnard | c0696c2 | 2015-06-18 16:47:17 +0200 | [diff] [blame] | 2448 | k = mbedtls_mpi_bitlen( X ); |
Manuel Pégourié-Gonnard | 53c76c0 | 2015-04-17 20:15:36 +0200 | [diff] [blame] | 2449 | if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits + 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2450 | |
Manuel Pégourié-Gonnard | 53c76c0 | 2015-04-17 20:15:36 +0200 | [diff] [blame] | 2451 | mbedtls_mpi_set_bit( X, nbits-1, 1 ); |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 2452 | |
| 2453 | X->p[0] |= 1; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2454 | |
| 2455 | if( dh_flag == 0 ) |
| 2456 | { |
Janos Follath | 72d555d | 2018-09-03 14:45:23 +0100 | [diff] [blame] | 2457 | while( ( ret = mpi_is_prime_internal( X, rounds, f_rng, p_rng ) ) != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2458 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2459 | if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2460 | goto cleanup; |
| 2461 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2462 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 2 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2463 | } |
| 2464 | } |
| 2465 | else |
| 2466 | { |
Manuel Pégourié-Gonnard | 0160eac | 2013-11-22 17:54:59 +0100 | [diff] [blame] | 2467 | /* |
| 2468 | * An necessary condition for Y and X = 2Y + 1 to be prime |
| 2469 | * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). |
| 2470 | * Make sure it is satisfied, while keeping X = 3 mod 4 |
| 2471 | */ |
Pascal Junod | b99183d | 2015-03-11 16:49:45 +0100 | [diff] [blame] | 2472 | |
| 2473 | X->p[0] |= 2; |
| 2474 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2475 | MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) ); |
Manuel Pégourié-Gonnard | 0160eac | 2013-11-22 17:54:59 +0100 | [diff] [blame] | 2476 | if( r == 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2477 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) ); |
Manuel Pégourié-Gonnard | 0160eac | 2013-11-22 17:54:59 +0100 | [diff] [blame] | 2478 | else if( r == 1 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2479 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) ); |
Manuel Pégourié-Gonnard | 0160eac | 2013-11-22 17:54:59 +0100 | [diff] [blame] | 2480 | |
| 2481 | /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2482 | MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) ); |
| 2483 | MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2484 | |
| 2485 | while( 1 ) |
| 2486 | { |
Manuel Pégourié-Gonnard | ddf7615 | 2013-11-22 19:58:22 +0100 | [diff] [blame] | 2487 | /* |
| 2488 | * First, check small factors for X and Y |
| 2489 | * before doing Miller-Rabin on any of them |
| 2490 | */ |
| 2491 | if( ( ret = mpi_check_small_factors( X ) ) == 0 && |
| 2492 | ( ret = mpi_check_small_factors( &Y ) ) == 0 && |
Janos Follath | 72d555d | 2018-09-03 14:45:23 +0100 | [diff] [blame] | 2493 | ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) ) |
| 2494 | == 0 && |
| 2495 | ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) ) |
| 2496 | == 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2497 | { |
Manuel Pégourié-Gonnard | ddf7615 | 2013-11-22 19:58:22 +0100 | [diff] [blame] | 2498 | break; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2499 | } |
| 2500 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2501 | if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2502 | goto cleanup; |
| 2503 | |
Manuel Pégourié-Gonnard | 0160eac | 2013-11-22 17:54:59 +0100 | [diff] [blame] | 2504 | /* |
Manuel Pégourié-Gonnard | ddf7615 | 2013-11-22 19:58:22 +0100 | [diff] [blame] | 2505 | * Next candidates. We want to preserve Y = (X-1) / 2 and |
Manuel Pégourié-Gonnard | 0160eac | 2013-11-22 17:54:59 +0100 | [diff] [blame] | 2506 | * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) |
| 2507 | * so up Y by 6 and X by 12. |
| 2508 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2509 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) ); |
| 2510 | MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2511 | } |
| 2512 | } |
| 2513 | |
| 2514 | cleanup: |
| 2515 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2516 | mbedtls_mpi_free( &Y ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2517 | |
| 2518 | return( ret ); |
| 2519 | } |
| 2520 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2521 | #endif /* MBEDTLS_GENPRIME */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2522 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2523 | #if defined(MBEDTLS_SELF_TEST) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2524 | |
Paul Bakker | 23986e5 | 2011-04-24 08:57:21 +0000 | [diff] [blame] | 2525 | #define GCD_PAIR_COUNT 3 |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2526 | |
| 2527 | static const int gcd_pairs[GCD_PAIR_COUNT][3] = |
| 2528 | { |
| 2529 | { 693, 609, 21 }, |
| 2530 | { 1764, 868, 28 }, |
| 2531 | { 768454923, 542167814, 1 } |
| 2532 | }; |
| 2533 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2534 | /* |
| 2535 | * Checkup routine |
| 2536 | */ |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2537 | int mbedtls_mpi_self_test( int verbose ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2538 | { |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2539 | int ret, i; |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2540 | mbedtls_mpi A, E, N, X, Y, U, V; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2541 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2542 | mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X ); |
| 2543 | mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2544 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2545 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16, |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2546 | "EFE021C2645FD1DC586E69184AF4A31E" \ |
| 2547 | "D5F53E93B5F123FA41680867BA110131" \ |
| 2548 | "944FE7952E2517337780CB0DB80E61AA" \ |
| 2549 | "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) ); |
| 2550 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2551 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16, |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2552 | "B2E7EFD37075B9F03FF989C7C5051C20" \ |
| 2553 | "34D2A323810251127E7BF8625A4F49A5" \ |
| 2554 | "F3E27F4DA8BD59C47D6DAABA4C8127BD" \ |
| 2555 | "5B5C25763222FEFCCFC38B832366C29E" ) ); |
| 2556 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2557 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16, |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2558 | "0066A198186C18C10B2F5ED9B522752A" \ |
| 2559 | "9830B69916E535C8F047518A889A43A5" \ |
| 2560 | "94B6BED27A168D31D4A52F88925AA8F5" ) ); |
| 2561 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2562 | MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2563 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2564 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2565 | "602AB7ECA597A3D6B56FF9829A5E8B85" \ |
| 2566 | "9E857EA95A03512E2BAE7391688D264A" \ |
| 2567 | "A5663B0341DB9CCFD2C4C5F421FEC814" \ |
| 2568 | "8001B72E848A38CAE1C65F78E56ABDEF" \ |
| 2569 | "E12D3C039B8A02D6BE593F0BBBDA56F1" \ |
| 2570 | "ECF677152EF804370C1A305CAF3B5BF1" \ |
| 2571 | "30879B56C61DE584A0F53A2447A51E" ) ); |
| 2572 | |
| 2573 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2574 | mbedtls_printf( " MPI test #1 (mul_mpi): " ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2575 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2576 | if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2577 | { |
| 2578 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2579 | mbedtls_printf( "failed\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2580 | |
Manuel Pégourié-Gonnard | 9e987ed | 2014-01-20 10:03:15 +0100 | [diff] [blame] | 2581 | ret = 1; |
| 2582 | goto cleanup; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2583 | } |
| 2584 | |
| 2585 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2586 | mbedtls_printf( "passed\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2587 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2588 | MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2589 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2590 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2591 | "256567336059E52CAE22925474705F39A94" ) ); |
| 2592 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2593 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16, |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2594 | "6613F26162223DF488E9CD48CC132C7A" \ |
| 2595 | "0AC93C701B001B092E4E5B9F73BCD27B" \ |
| 2596 | "9EE50D0657C77F374E903CDFA4C642" ) ); |
| 2597 | |
| 2598 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2599 | mbedtls_printf( " MPI test #2 (div_mpi): " ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2600 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2601 | if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 || |
| 2602 | mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2603 | { |
| 2604 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2605 | mbedtls_printf( "failed\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2606 | |
Manuel Pégourié-Gonnard | 9e987ed | 2014-01-20 10:03:15 +0100 | [diff] [blame] | 2607 | ret = 1; |
| 2608 | goto cleanup; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2609 | } |
| 2610 | |
| 2611 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2612 | mbedtls_printf( "passed\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2613 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2614 | MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2615 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2616 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2617 | "36E139AEA55215609D2816998ED020BB" \ |
| 2618 | "BD96C37890F65171D948E9BC7CBAA4D9" \ |
| 2619 | "325D24D6A3C12710F10A09FA08AB87" ) ); |
| 2620 | |
| 2621 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2622 | mbedtls_printf( " MPI test #3 (exp_mod): " ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2623 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2624 | if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2625 | { |
| 2626 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2627 | mbedtls_printf( "failed\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2628 | |
Manuel Pégourié-Gonnard | 9e987ed | 2014-01-20 10:03:15 +0100 | [diff] [blame] | 2629 | ret = 1; |
| 2630 | goto cleanup; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2631 | } |
| 2632 | |
| 2633 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2634 | mbedtls_printf( "passed\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2635 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2636 | MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2637 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2638 | MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2639 | "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \ |
| 2640 | "C3DBA76456363A10869622EAC2DD84EC" \ |
| 2641 | "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) ); |
| 2642 | |
| 2643 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2644 | mbedtls_printf( " MPI test #4 (inv_mod): " ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2645 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2646 | if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2647 | { |
| 2648 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2649 | mbedtls_printf( "failed\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2650 | |
Manuel Pégourié-Gonnard | 9e987ed | 2014-01-20 10:03:15 +0100 | [diff] [blame] | 2651 | ret = 1; |
| 2652 | goto cleanup; |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2653 | } |
| 2654 | |
| 2655 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2656 | mbedtls_printf( "passed\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2657 | |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2658 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2659 | mbedtls_printf( " MPI test #5 (simple gcd): " ); |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2660 | |
Paul Bakker | 66d5d07 | 2014-06-17 16:39:18 +0200 | [diff] [blame] | 2661 | for( i = 0; i < GCD_PAIR_COUNT; i++ ) |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2662 | { |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2663 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) ); |
| 2664 | MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) ); |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2665 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2666 | MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) ); |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2667 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2668 | if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 ) |
Manuel Pégourié-Gonnard | 9e987ed | 2014-01-20 10:03:15 +0100 | [diff] [blame] | 2669 | { |
| 2670 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2671 | mbedtls_printf( "failed at %d\n", i ); |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2672 | |
Manuel Pégourié-Gonnard | 9e987ed | 2014-01-20 10:03:15 +0100 | [diff] [blame] | 2673 | ret = 1; |
| 2674 | goto cleanup; |
| 2675 | } |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2676 | } |
| 2677 | |
| 2678 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2679 | mbedtls_printf( "passed\n" ); |
Paul Bakker | 4e0d7ca | 2009-01-29 22:24:33 +0000 | [diff] [blame] | 2680 | |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2681 | cleanup: |
| 2682 | |
| 2683 | if( ret != 0 && verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2684 | mbedtls_printf( "Unexpected error, return code = %08X\n", ret ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2685 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2686 | mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X ); |
| 2687 | mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2688 | |
| 2689 | if( verbose != 0 ) |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2690 | mbedtls_printf( "\n" ); |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2691 | |
| 2692 | return( ret ); |
| 2693 | } |
| 2694 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2695 | #endif /* MBEDTLS_SELF_TEST */ |
Paul Bakker | 5121ce5 | 2009-01-03 21:22:43 +0000 | [diff] [blame] | 2696 | |
Manuel Pégourié-Gonnard | 2cf5a7c | 2015-04-08 12:49:31 +0200 | [diff] [blame] | 2697 | #endif /* MBEDTLS_BIGNUM_C */ |