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