Sergey Pastor / 1

Webserver+3d print

Dependents:   Nucleo

cyclone_crypto/mpi.c@0:8918a71cdbe9, 2017-02-04 (annotated)

Committer:
Sergunb
Date:
Sat Feb 04 18:15:49 2017 +0000
Revision:
0:8918a71cdbe9
nothing else

Who changed what in which revision?

UserRevisionLine numberNew contents of line
Sergunb 0:8918a71cdbe9 1 /**
Sergunb 0:8918a71cdbe9 2 * @file mpi.c
Sergunb 0:8918a71cdbe9 3 * @brief MPI (Multiple Precision Integer Arithmetic)
Sergunb 0:8918a71cdbe9 4 *
Sergunb 0:8918a71cdbe9 5 * @section License
Sergunb 0:8918a71cdbe9 6 *
Sergunb 0:8918a71cdbe9 7 * Copyright (C) 2010-2017 Oryx Embedded SARL. All rights reserved.
Sergunb 0:8918a71cdbe9 8 *
Sergunb 0:8918a71cdbe9 9 * This file is part of CycloneCrypto Open.
Sergunb 0:8918a71cdbe9 10 *
Sergunb 0:8918a71cdbe9 11 * This program is free software; you can redistribute it and/or
Sergunb 0:8918a71cdbe9 12 * modify it under the terms of the GNU General Public License
Sergunb 0:8918a71cdbe9 13 * as published by the Free Software Foundation; either version 2
Sergunb 0:8918a71cdbe9 14 * of the License, or (at your option) any later version.
Sergunb 0:8918a71cdbe9 15 *
Sergunb 0:8918a71cdbe9 16 * This program is distributed in the hope that it will be useful,
Sergunb 0:8918a71cdbe9 17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
Sergunb 0:8918a71cdbe9 18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
Sergunb 0:8918a71cdbe9 19 * GNU General Public License for more details.
Sergunb 0:8918a71cdbe9 20 *
Sergunb 0:8918a71cdbe9 21 * You should have received a copy of the GNU General Public License
Sergunb 0:8918a71cdbe9 22 * along with this program; if not, write to the Free Software Foundation,
Sergunb 0:8918a71cdbe9 23 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
Sergunb 0:8918a71cdbe9 24 *
Sergunb 0:8918a71cdbe9 25 * @author Oryx Embedded SARL (www.oryx-embedded.com)
Sergunb 0:8918a71cdbe9 26 * @version 1.7.6
Sergunb 0:8918a71cdbe9 27 **/
Sergunb 0:8918a71cdbe9 28
Sergunb 0:8918a71cdbe9 29 //Switch to the appropriate trace level
Sergunb 0:8918a71cdbe9 30 #define TRACE_LEVEL CRYPTO_TRACE_LEVEL
Sergunb 0:8918a71cdbe9 31
Sergunb 0:8918a71cdbe9 32 //Dependencies
Sergunb 0:8918a71cdbe9 33 #include <stdlib.h>
Sergunb 0:8918a71cdbe9 34 #include <string.h>
Sergunb 0:8918a71cdbe9 35 #include "crypto.h"
Sergunb 0:8918a71cdbe9 36 #include "mpi.h"
Sergunb 0:8918a71cdbe9 37 #include "debug.h"
Sergunb 0:8918a71cdbe9 38
Sergunb 0:8918a71cdbe9 39 //Check crypto library configuration
Sergunb 0:8918a71cdbe9 40 #if (MPI_SUPPORT == ENABLED)
Sergunb 0:8918a71cdbe9 41
Sergunb 0:8918a71cdbe9 42
Sergunb 0:8918a71cdbe9 43 /**
Sergunb 0:8918a71cdbe9 44 * @brief Initialize a multiple precision integer
Sergunb 0:8918a71cdbe9 45 * @param[in,out] r Pointer to the multiple precision integer to be initialized
Sergunb 0:8918a71cdbe9 46 **/
Sergunb 0:8918a71cdbe9 47
Sergunb 0:8918a71cdbe9 48 void mpiInit(Mpi *r)
Sergunb 0:8918a71cdbe9 49 {
Sergunb 0:8918a71cdbe9 50 //Initialize structure
Sergunb 0:8918a71cdbe9 51 r->sign = 1;
Sergunb 0:8918a71cdbe9 52 r->size = 0;
Sergunb 0:8918a71cdbe9 53 r->data = NULL;
Sergunb 0:8918a71cdbe9 54 }
Sergunb 0:8918a71cdbe9 55
Sergunb 0:8918a71cdbe9 56
Sergunb 0:8918a71cdbe9 57 /**
Sergunb 0:8918a71cdbe9 58 * @brief Release a multiple precision integer
Sergunb 0:8918a71cdbe9 59 * @param[in,out] r Pointer to the multiple precision integer to be freed
Sergunb 0:8918a71cdbe9 60 **/
Sergunb 0:8918a71cdbe9 61
Sergunb 0:8918a71cdbe9 62 void mpiFree(Mpi *r)
Sergunb 0:8918a71cdbe9 63 {
Sergunb 0:8918a71cdbe9 64 //Any memory previously allocated?
Sergunb 0:8918a71cdbe9 65 if(r->data != NULL)
Sergunb 0:8918a71cdbe9 66 {
Sergunb 0:8918a71cdbe9 67 //Erase contents before releasing memory
Sergunb 0:8918a71cdbe9 68 memset(r->data, 0, r->size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 69 cryptoFreeMem(r->data);
Sergunb 0:8918a71cdbe9 70 }
Sergunb 0:8918a71cdbe9 71
Sergunb 0:8918a71cdbe9 72 //Set size to zero
Sergunb 0:8918a71cdbe9 73 r->size = 0;
Sergunb 0:8918a71cdbe9 74 r->data = NULL;
Sergunb 0:8918a71cdbe9 75 }
Sergunb 0:8918a71cdbe9 76
Sergunb 0:8918a71cdbe9 77
Sergunb 0:8918a71cdbe9 78 /**
Sergunb 0:8918a71cdbe9 79 * @brief Adjust the size of multiple precision integer
Sergunb 0:8918a71cdbe9 80 * @param[in,out] r A multiple precision integer whose size is to be increased
Sergunb 0:8918a71cdbe9 81 * @param[in] size Desired size in words
Sergunb 0:8918a71cdbe9 82 * @return Error code
Sergunb 0:8918a71cdbe9 83 **/
Sergunb 0:8918a71cdbe9 84
Sergunb 0:8918a71cdbe9 85 error_t mpiGrow(Mpi *r, uint_t size)
Sergunb 0:8918a71cdbe9 86 {
Sergunb 0:8918a71cdbe9 87 uint_t *data;
Sergunb 0:8918a71cdbe9 88
Sergunb 0:8918a71cdbe9 89 //Ensure the parameter is valid
Sergunb 0:8918a71cdbe9 90 size = MAX(size, 1);
Sergunb 0:8918a71cdbe9 91
Sergunb 0:8918a71cdbe9 92 //Check the current size
Sergunb 0:8918a71cdbe9 93 if(r->size >= size)
Sergunb 0:8918a71cdbe9 94 return NO_ERROR;
Sergunb 0:8918a71cdbe9 95
Sergunb 0:8918a71cdbe9 96 //Allocate a memory buffer
Sergunb 0:8918a71cdbe9 97 data = cryptoAllocMem(size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 98 //Failed to allocate memory?
Sergunb 0:8918a71cdbe9 99 if(data == NULL)
Sergunb 0:8918a71cdbe9 100 return ERROR_OUT_OF_MEMORY;
Sergunb 0:8918a71cdbe9 101
Sergunb 0:8918a71cdbe9 102 //Clear buffer contents
Sergunb 0:8918a71cdbe9 103 memset(data, 0, size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 104
Sergunb 0:8918a71cdbe9 105 //Any data to copy?
Sergunb 0:8918a71cdbe9 106 if(r->size > 0)
Sergunb 0:8918a71cdbe9 107 {
Sergunb 0:8918a71cdbe9 108 //Copy original data
Sergunb 0:8918a71cdbe9 109 memcpy(data, r->data, r->size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 110 //Free previously allocated memory
Sergunb 0:8918a71cdbe9 111 cryptoFreeMem(r->data);
Sergunb 0:8918a71cdbe9 112 }
Sergunb 0:8918a71cdbe9 113
Sergunb 0:8918a71cdbe9 114 //Update the size of the multiple precision integer
Sergunb 0:8918a71cdbe9 115 r->size = size;
Sergunb 0:8918a71cdbe9 116 r->data = data;
Sergunb 0:8918a71cdbe9 117
Sergunb 0:8918a71cdbe9 118 //Successful operation
Sergunb 0:8918a71cdbe9 119 return NO_ERROR;
Sergunb 0:8918a71cdbe9 120 }
Sergunb 0:8918a71cdbe9 121
Sergunb 0:8918a71cdbe9 122
Sergunb 0:8918a71cdbe9 123 /**
Sergunb 0:8918a71cdbe9 124 * @brief Get the actual length in words
Sergunb 0:8918a71cdbe9 125 * @param[in] a Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 126 * @return The actual length in words
Sergunb 0:8918a71cdbe9 127 **/
Sergunb 0:8918a71cdbe9 128
Sergunb 0:8918a71cdbe9 129 uint_t mpiGetLength(const Mpi *a)
Sergunb 0:8918a71cdbe9 130 {
Sergunb 0:8918a71cdbe9 131 int_t i;
Sergunb 0:8918a71cdbe9 132
Sergunb 0:8918a71cdbe9 133 //Check whether the specified multiple precision integer is empty
Sergunb 0:8918a71cdbe9 134 if(a->size == 0)
Sergunb 0:8918a71cdbe9 135 return 0;
Sergunb 0:8918a71cdbe9 136
Sergunb 0:8918a71cdbe9 137 //Start from the most significant word
Sergunb 0:8918a71cdbe9 138 for(i = a->size - 1; i >= 0; i--)
Sergunb 0:8918a71cdbe9 139 {
Sergunb 0:8918a71cdbe9 140 //Loop as long as the current word is zero
Sergunb 0:8918a71cdbe9 141 if(a->data[i] != 0)
Sergunb 0:8918a71cdbe9 142 break;
Sergunb 0:8918a71cdbe9 143 }
Sergunb 0:8918a71cdbe9 144
Sergunb 0:8918a71cdbe9 145 //Return the actual length
Sergunb 0:8918a71cdbe9 146 return i + 1;
Sergunb 0:8918a71cdbe9 147 }
Sergunb 0:8918a71cdbe9 148
Sergunb 0:8918a71cdbe9 149
Sergunb 0:8918a71cdbe9 150 /**
Sergunb 0:8918a71cdbe9 151 * @brief Get the actual length in bytes
Sergunb 0:8918a71cdbe9 152 * @param[in] a Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 153 * @return The actual byte count
Sergunb 0:8918a71cdbe9 154 **/
Sergunb 0:8918a71cdbe9 155
Sergunb 0:8918a71cdbe9 156 uint_t mpiGetByteLength(const Mpi *a)
Sergunb 0:8918a71cdbe9 157 {
Sergunb 0:8918a71cdbe9 158 uint_t n;
Sergunb 0:8918a71cdbe9 159 uint32_t m;
Sergunb 0:8918a71cdbe9 160
Sergunb 0:8918a71cdbe9 161 //Check whether the specified multiple precision integer is empty
Sergunb 0:8918a71cdbe9 162 if(a->size == 0)
Sergunb 0:8918a71cdbe9 163 return 0;
Sergunb 0:8918a71cdbe9 164
Sergunb 0:8918a71cdbe9 165 //Start from the most significant word
Sergunb 0:8918a71cdbe9 166 for(n = a->size - 1; n > 0; n--)
Sergunb 0:8918a71cdbe9 167 {
Sergunb 0:8918a71cdbe9 168 //Loop as long as the current word is zero
Sergunb 0:8918a71cdbe9 169 if(a->data[n] != 0)
Sergunb 0:8918a71cdbe9 170 break;
Sergunb 0:8918a71cdbe9 171 }
Sergunb 0:8918a71cdbe9 172
Sergunb 0:8918a71cdbe9 173 //Get the current word
Sergunb 0:8918a71cdbe9 174 m = a->data[n];
Sergunb 0:8918a71cdbe9 175 //Convert the length to a byte count
Sergunb 0:8918a71cdbe9 176 n *= MPI_INT_SIZE;
Sergunb 0:8918a71cdbe9 177
Sergunb 0:8918a71cdbe9 178 //Adjust the byte count
Sergunb 0:8918a71cdbe9 179 for(; m != 0; m >>= 8) n++;
Sergunb 0:8918a71cdbe9 180
Sergunb 0:8918a71cdbe9 181 //Return the actual length in bytes
Sergunb 0:8918a71cdbe9 182 return n;
Sergunb 0:8918a71cdbe9 183 }
Sergunb 0:8918a71cdbe9 184
Sergunb 0:8918a71cdbe9 185
Sergunb 0:8918a71cdbe9 186 /**
Sergunb 0:8918a71cdbe9 187 * @brief Get the actual length in bits
Sergunb 0:8918a71cdbe9 188 * @param[in] a Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 189 * @return The actual bit count
Sergunb 0:8918a71cdbe9 190 **/
Sergunb 0:8918a71cdbe9 191
Sergunb 0:8918a71cdbe9 192 uint_t mpiGetBitLength(const Mpi *a)
Sergunb 0:8918a71cdbe9 193 {
Sergunb 0:8918a71cdbe9 194 uint_t n;
Sergunb 0:8918a71cdbe9 195 uint32_t m;
Sergunb 0:8918a71cdbe9 196
Sergunb 0:8918a71cdbe9 197 //Check whether the specified multiple precision integer is empty
Sergunb 0:8918a71cdbe9 198 if(a->size == 0)
Sergunb 0:8918a71cdbe9 199 return 0;
Sergunb 0:8918a71cdbe9 200
Sergunb 0:8918a71cdbe9 201 //Start from the most significant word
Sergunb 0:8918a71cdbe9 202 for(n = a->size - 1; n > 0; n--)
Sergunb 0:8918a71cdbe9 203 {
Sergunb 0:8918a71cdbe9 204 //Loop as long as the current word is zero
Sergunb 0:8918a71cdbe9 205 if(a->data[n] != 0)
Sergunb 0:8918a71cdbe9 206 break;
Sergunb 0:8918a71cdbe9 207 }
Sergunb 0:8918a71cdbe9 208
Sergunb 0:8918a71cdbe9 209 //Get the current word
Sergunb 0:8918a71cdbe9 210 m = a->data[n];
Sergunb 0:8918a71cdbe9 211 //Convert the length to a bit count
Sergunb 0:8918a71cdbe9 212 n *= MPI_INT_SIZE * 8;
Sergunb 0:8918a71cdbe9 213
Sergunb 0:8918a71cdbe9 214 //Adjust the bit count
Sergunb 0:8918a71cdbe9 215 for(; m != 0; m >>= 1) n++;
Sergunb 0:8918a71cdbe9 216
Sergunb 0:8918a71cdbe9 217 //Return the actual length in bits
Sergunb 0:8918a71cdbe9 218 return n;
Sergunb 0:8918a71cdbe9 219 }
Sergunb 0:8918a71cdbe9 220
Sergunb 0:8918a71cdbe9 221
Sergunb 0:8918a71cdbe9 222 /**
Sergunb 0:8918a71cdbe9 223 * @brief Set the bit value at the specified index
Sergunb 0:8918a71cdbe9 224 * @param[in] r Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 225 * @param[in] index Position of the bit to be written
Sergunb 0:8918a71cdbe9 226 * @param[in] value Bit value
Sergunb 0:8918a71cdbe9 227 * @return Error code
Sergunb 0:8918a71cdbe9 228 **/
Sergunb 0:8918a71cdbe9 229
Sergunb 0:8918a71cdbe9 230 error_t mpiSetBitValue(Mpi *r, uint_t index, uint_t value)
Sergunb 0:8918a71cdbe9 231 {
Sergunb 0:8918a71cdbe9 232 error_t error;
Sergunb 0:8918a71cdbe9 233 uint_t n1;
Sergunb 0:8918a71cdbe9 234 uint_t n2;
Sergunb 0:8918a71cdbe9 235
Sergunb 0:8918a71cdbe9 236 //Retrieve the position of the bit to be written
Sergunb 0:8918a71cdbe9 237 n1 = index / (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 238 n2 = index % (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 239
Sergunb 0:8918a71cdbe9 240 //Ajust the size of the multiple precision integer if necessary
Sergunb 0:8918a71cdbe9 241 error = mpiGrow(r, (index + (MPI_INT_SIZE * 8) - 1) / (MPI_INT_SIZE * 8));
Sergunb 0:8918a71cdbe9 242 //Failed to adjust the size?
Sergunb 0:8918a71cdbe9 243 if(error)
Sergunb 0:8918a71cdbe9 244 return error;
Sergunb 0:8918a71cdbe9 245
Sergunb 0:8918a71cdbe9 246 //Set bit value
Sergunb 0:8918a71cdbe9 247 if(value)
Sergunb 0:8918a71cdbe9 248 r->data[n1] |= (1 << n2);
Sergunb 0:8918a71cdbe9 249 else
Sergunb 0:8918a71cdbe9 250 r->data[n1] &= ~(1 << n2);
Sergunb 0:8918a71cdbe9 251
Sergunb 0:8918a71cdbe9 252 //No error to report
Sergunb 0:8918a71cdbe9 253 return NO_ERROR;
Sergunb 0:8918a71cdbe9 254 }
Sergunb 0:8918a71cdbe9 255
Sergunb 0:8918a71cdbe9 256
Sergunb 0:8918a71cdbe9 257 /**
Sergunb 0:8918a71cdbe9 258 * @brief Get the bit value at the specified index
Sergunb 0:8918a71cdbe9 259 * @param[in] a Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 260 * @param[in] index Position where to read the bit
Sergunb 0:8918a71cdbe9 261 * @return The actual bit value
Sergunb 0:8918a71cdbe9 262 **/
Sergunb 0:8918a71cdbe9 263
Sergunb 0:8918a71cdbe9 264 uint_t mpiGetBitValue(const Mpi *a, uint_t index)
Sergunb 0:8918a71cdbe9 265 {
Sergunb 0:8918a71cdbe9 266 uint_t n1;
Sergunb 0:8918a71cdbe9 267 uint_t n2;
Sergunb 0:8918a71cdbe9 268
Sergunb 0:8918a71cdbe9 269 //Retrieve the position of the bit to be read
Sergunb 0:8918a71cdbe9 270 n1 = index / (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 271 n2 = index % (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 272
Sergunb 0:8918a71cdbe9 273 //Index out of range?
Sergunb 0:8918a71cdbe9 274 if(n1 >= a->size)
Sergunb 0:8918a71cdbe9 275 return 0;
Sergunb 0:8918a71cdbe9 276
Sergunb 0:8918a71cdbe9 277 //Return the actual bit value
Sergunb 0:8918a71cdbe9 278 return (a->data[n1] >> n2) & 0x01;
Sergunb 0:8918a71cdbe9 279 }
Sergunb 0:8918a71cdbe9 280
Sergunb 0:8918a71cdbe9 281
Sergunb 0:8918a71cdbe9 282 /**
Sergunb 0:8918a71cdbe9 283 * @brief Compare two multiple precision integers
Sergunb 0:8918a71cdbe9 284 * @param[in] a The first multiple precision integer to be compared
Sergunb 0:8918a71cdbe9 285 * @param[in] b The second multiple precision integer to be compared
Sergunb 0:8918a71cdbe9 286 * @return Comparison result
Sergunb 0:8918a71cdbe9 287 **/
Sergunb 0:8918a71cdbe9 288
Sergunb 0:8918a71cdbe9 289 int_t mpiComp(const Mpi *a, const Mpi *b)
Sergunb 0:8918a71cdbe9 290 {
Sergunb 0:8918a71cdbe9 291 uint_t m;
Sergunb 0:8918a71cdbe9 292 uint_t n;
Sergunb 0:8918a71cdbe9 293
Sergunb 0:8918a71cdbe9 294 //Determine the actual length of A and B
Sergunb 0:8918a71cdbe9 295 m = mpiGetLength(a);
Sergunb 0:8918a71cdbe9 296 n = mpiGetLength(b);
Sergunb 0:8918a71cdbe9 297
Sergunb 0:8918a71cdbe9 298 //Compare lengths
Sergunb 0:8918a71cdbe9 299 if(!m && !n)
Sergunb 0:8918a71cdbe9 300 return 0;
Sergunb 0:8918a71cdbe9 301 else if(m > n)
Sergunb 0:8918a71cdbe9 302 return a->sign;
Sergunb 0:8918a71cdbe9 303 else if(m < n)
Sergunb 0:8918a71cdbe9 304 return -b->sign;
Sergunb 0:8918a71cdbe9 305
Sergunb 0:8918a71cdbe9 306 //Compare signs
Sergunb 0:8918a71cdbe9 307 if(a->sign > 0 && b->sign < 0)
Sergunb 0:8918a71cdbe9 308 return 1;
Sergunb 0:8918a71cdbe9 309 else if(a->sign < 0 && b->sign > 0)
Sergunb 0:8918a71cdbe9 310 return -1;
Sergunb 0:8918a71cdbe9 311
Sergunb 0:8918a71cdbe9 312 //Then compare values
Sergunb 0:8918a71cdbe9 313 while(n--)
Sergunb 0:8918a71cdbe9 314 {
Sergunb 0:8918a71cdbe9 315 if(a->data[n] > b->data[n])
Sergunb 0:8918a71cdbe9 316 return a->sign;
Sergunb 0:8918a71cdbe9 317 else if(a->data[n] < b->data[n])
Sergunb 0:8918a71cdbe9 318 return -a->sign;
Sergunb 0:8918a71cdbe9 319 }
Sergunb 0:8918a71cdbe9 320
Sergunb 0:8918a71cdbe9 321 //Multiple precision integers are equals
Sergunb 0:8918a71cdbe9 322 return 0;
Sergunb 0:8918a71cdbe9 323 }
Sergunb 0:8918a71cdbe9 324
Sergunb 0:8918a71cdbe9 325
Sergunb 0:8918a71cdbe9 326 /**
Sergunb 0:8918a71cdbe9 327 * @brief Compare a multiple precision integer with an integer
Sergunb 0:8918a71cdbe9 328 * @param[in] a Multiple precision integer to be compared
Sergunb 0:8918a71cdbe9 329 * @param[in] b Integer to be compared
Sergunb 0:8918a71cdbe9 330 * @return Comparison result
Sergunb 0:8918a71cdbe9 331 **/
Sergunb 0:8918a71cdbe9 332
Sergunb 0:8918a71cdbe9 333 int_t mpiCompInt(const Mpi *a, int_t b)
Sergunb 0:8918a71cdbe9 334 {
Sergunb 0:8918a71cdbe9 335 uint_t value;
Sergunb 0:8918a71cdbe9 336 Mpi t;
Sergunb 0:8918a71cdbe9 337
Sergunb 0:8918a71cdbe9 338 //Initialize a temporary multiple precision integer
Sergunb 0:8918a71cdbe9 339 value = (b >= 0) ? b : -b;
Sergunb 0:8918a71cdbe9 340 t.sign = (b >= 0) ? 1 : -1;
Sergunb 0:8918a71cdbe9 341 t.size = 1;
Sergunb 0:8918a71cdbe9 342 t.data = &value;
Sergunb 0:8918a71cdbe9 343
Sergunb 0:8918a71cdbe9 344 //Return comparison result
Sergunb 0:8918a71cdbe9 345 return mpiComp(a, &t);
Sergunb 0:8918a71cdbe9 346 }
Sergunb 0:8918a71cdbe9 347
Sergunb 0:8918a71cdbe9 348
Sergunb 0:8918a71cdbe9 349 /**
Sergunb 0:8918a71cdbe9 350 * @brief Compare the absolute value of two multiple precision integers
Sergunb 0:8918a71cdbe9 351 * @param[in] a The first multiple precision integer to be compared
Sergunb 0:8918a71cdbe9 352 * @param[in] b The second multiple precision integer to be compared
Sergunb 0:8918a71cdbe9 353 * @return Comparison result
Sergunb 0:8918a71cdbe9 354 **/
Sergunb 0:8918a71cdbe9 355
Sergunb 0:8918a71cdbe9 356 int_t mpiCompAbs(const Mpi *a, const Mpi *b)
Sergunb 0:8918a71cdbe9 357 {
Sergunb 0:8918a71cdbe9 358 uint_t m;
Sergunb 0:8918a71cdbe9 359 uint_t n;
Sergunb 0:8918a71cdbe9 360
Sergunb 0:8918a71cdbe9 361 //Determine the actual length of A and B
Sergunb 0:8918a71cdbe9 362 m = mpiGetLength(a);
Sergunb 0:8918a71cdbe9 363 n = mpiGetLength(b);
Sergunb 0:8918a71cdbe9 364
Sergunb 0:8918a71cdbe9 365 //Compare lengths
Sergunb 0:8918a71cdbe9 366 if(!m && !n)
Sergunb 0:8918a71cdbe9 367 return 0;
Sergunb 0:8918a71cdbe9 368 else if(m > n)
Sergunb 0:8918a71cdbe9 369 return 1;
Sergunb 0:8918a71cdbe9 370 else if(m < n)
Sergunb 0:8918a71cdbe9 371 return -1;
Sergunb 0:8918a71cdbe9 372
Sergunb 0:8918a71cdbe9 373 //Then compare values
Sergunb 0:8918a71cdbe9 374 while(n--)
Sergunb 0:8918a71cdbe9 375 {
Sergunb 0:8918a71cdbe9 376 if(a->data[n] > b->data[n])
Sergunb 0:8918a71cdbe9 377 return 1;
Sergunb 0:8918a71cdbe9 378 else if(a->data[n] < b->data[n])
Sergunb 0:8918a71cdbe9 379 return -1;
Sergunb 0:8918a71cdbe9 380 }
Sergunb 0:8918a71cdbe9 381
Sergunb 0:8918a71cdbe9 382 //Operands are equals
Sergunb 0:8918a71cdbe9 383 return 0;
Sergunb 0:8918a71cdbe9 384 }
Sergunb 0:8918a71cdbe9 385
Sergunb 0:8918a71cdbe9 386
Sergunb 0:8918a71cdbe9 387 /**
Sergunb 0:8918a71cdbe9 388 * @brief Copy a multiple precision integer
Sergunb 0:8918a71cdbe9 389 * @param[out] r Pointer to a multiple precision integer (destination)
Sergunb 0:8918a71cdbe9 390 * @param[in] a Pointer to a multiple precision integer (source)
Sergunb 0:8918a71cdbe9 391 * @return Error code
Sergunb 0:8918a71cdbe9 392 **/
Sergunb 0:8918a71cdbe9 393
Sergunb 0:8918a71cdbe9 394 error_t mpiCopy(Mpi *r, const Mpi *a)
Sergunb 0:8918a71cdbe9 395 {
Sergunb 0:8918a71cdbe9 396 error_t error;
Sergunb 0:8918a71cdbe9 397 uint_t n;
Sergunb 0:8918a71cdbe9 398
Sergunb 0:8918a71cdbe9 399 //R and A are the same instance?
Sergunb 0:8918a71cdbe9 400 if(r == a)
Sergunb 0:8918a71cdbe9 401 return NO_ERROR;
Sergunb 0:8918a71cdbe9 402
Sergunb 0:8918a71cdbe9 403 //Determine the actual length of A
Sergunb 0:8918a71cdbe9 404 n = mpiGetLength(a);
Sergunb 0:8918a71cdbe9 405
Sergunb 0:8918a71cdbe9 406 //Ajust the size of the destination operand
Sergunb 0:8918a71cdbe9 407 error = mpiGrow(r, n);
Sergunb 0:8918a71cdbe9 408 //Any error to report?
Sergunb 0:8918a71cdbe9 409 if(error)
Sergunb 0:8918a71cdbe9 410 return error;
Sergunb 0:8918a71cdbe9 411
Sergunb 0:8918a71cdbe9 412 //Clear the contents of the multiple precision integer
Sergunb 0:8918a71cdbe9 413 memset(r->data, 0, r->size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 414 //Let R = A
Sergunb 0:8918a71cdbe9 415 memcpy(r->data, a->data, n * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 416 //Set the sign of R
Sergunb 0:8918a71cdbe9 417 r->sign = a->sign;
Sergunb 0:8918a71cdbe9 418
Sergunb 0:8918a71cdbe9 419 //Successful operation
Sergunb 0:8918a71cdbe9 420 return NO_ERROR;
Sergunb 0:8918a71cdbe9 421 }
Sergunb 0:8918a71cdbe9 422
Sergunb 0:8918a71cdbe9 423
Sergunb 0:8918a71cdbe9 424 /**
Sergunb 0:8918a71cdbe9 425 * @brief Set the value of a multiple precision integer
Sergunb 0:8918a71cdbe9 426 * @param[out] r Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 427 * @param[in] a Value to be assigned to the multiple precision integer
Sergunb 0:8918a71cdbe9 428 * @return Error code
Sergunb 0:8918a71cdbe9 429 **/
Sergunb 0:8918a71cdbe9 430
Sergunb 0:8918a71cdbe9 431 error_t mpiSetValue(Mpi *r, int_t a)
Sergunb 0:8918a71cdbe9 432 {
Sergunb 0:8918a71cdbe9 433 error_t error;
Sergunb 0:8918a71cdbe9 434
Sergunb 0:8918a71cdbe9 435 //Ajust the size of the destination operand
Sergunb 0:8918a71cdbe9 436 error = mpiGrow(r, 1);
Sergunb 0:8918a71cdbe9 437 //Failed to adjust the size?
Sergunb 0:8918a71cdbe9 438 if(error)
Sergunb 0:8918a71cdbe9 439 return error;
Sergunb 0:8918a71cdbe9 440
Sergunb 0:8918a71cdbe9 441 //Clear the contents of the multiple precision integer
Sergunb 0:8918a71cdbe9 442 memset(r->data, 0, r->size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 443 //Set the value or R
Sergunb 0:8918a71cdbe9 444 r->data[0] = (a >= 0) ? a : -a;
Sergunb 0:8918a71cdbe9 445 //Set the sign of R
Sergunb 0:8918a71cdbe9 446 r->sign = (a >= 0) ? 1 : -1;
Sergunb 0:8918a71cdbe9 447
Sergunb 0:8918a71cdbe9 448 //Successful operation
Sergunb 0:8918a71cdbe9 449 return NO_ERROR;
Sergunb 0:8918a71cdbe9 450 }
Sergunb 0:8918a71cdbe9 451
Sergunb 0:8918a71cdbe9 452
Sergunb 0:8918a71cdbe9 453 /**
Sergunb 0:8918a71cdbe9 454 * @brief Generate a random value
Sergunb 0:8918a71cdbe9 455 * @param[out] r Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 456 * @param[in] length Desired length in bits
Sergunb 0:8918a71cdbe9 457 * @param[in] prngAlgo PRNG algorithm
Sergunb 0:8918a71cdbe9 458 * @param[in] prngContext Pointer to the PRNG context
Sergunb 0:8918a71cdbe9 459 * @return Error code
Sergunb 0:8918a71cdbe9 460 **/
Sergunb 0:8918a71cdbe9 461
Sergunb 0:8918a71cdbe9 462 error_t mpiRand(Mpi *r, uint_t length, const PrngAlgo *prngAlgo, void *prngContext)
Sergunb 0:8918a71cdbe9 463 {
Sergunb 0:8918a71cdbe9 464 error_t error;
Sergunb 0:8918a71cdbe9 465 uint_t m;
Sergunb 0:8918a71cdbe9 466 uint_t n;
Sergunb 0:8918a71cdbe9 467
Sergunb 0:8918a71cdbe9 468 //Compute the required length, in words
Sergunb 0:8918a71cdbe9 469 n = (length + (MPI_INT_SIZE * 8) - 1) / (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 470 //Number of bits in the most significant word
Sergunb 0:8918a71cdbe9 471 m = length % (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 472
Sergunb 0:8918a71cdbe9 473 //Ajust the size of the multiple precision integer if necessary
Sergunb 0:8918a71cdbe9 474 error = mpiGrow(r, n);
Sergunb 0:8918a71cdbe9 475 //Failed to adjust the size?
Sergunb 0:8918a71cdbe9 476 if(error)
Sergunb 0:8918a71cdbe9 477 return error;
Sergunb 0:8918a71cdbe9 478
Sergunb 0:8918a71cdbe9 479 //Clear the contents of the multiple precision integer
Sergunb 0:8918a71cdbe9 480 memset(r->data, 0, r->size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 481 //Set the sign of R
Sergunb 0:8918a71cdbe9 482 r->sign = 1;
Sergunb 0:8918a71cdbe9 483
Sergunb 0:8918a71cdbe9 484 //Generate a random pattern
Sergunb 0:8918a71cdbe9 485 error = prngAlgo->read(prngContext, (uint8_t *) r->data, n * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 486 //Any error to report?
Sergunb 0:8918a71cdbe9 487 if(error)
Sergunb 0:8918a71cdbe9 488 return error;
Sergunb 0:8918a71cdbe9 489
Sergunb 0:8918a71cdbe9 490 //Remove the meaningless bits in the most significant word
Sergunb 0:8918a71cdbe9 491 if(n > 0 && m > 0)
Sergunb 0:8918a71cdbe9 492 r->data[n - 1] &= (1 << m) - 1;
Sergunb 0:8918a71cdbe9 493
Sergunb 0:8918a71cdbe9 494 //Successful operation
Sergunb 0:8918a71cdbe9 495 return NO_ERROR;
Sergunb 0:8918a71cdbe9 496 }
Sergunb 0:8918a71cdbe9 497
Sergunb 0:8918a71cdbe9 498
Sergunb 0:8918a71cdbe9 499 /**
Sergunb 0:8918a71cdbe9 500 * @brief Octet string to integer conversion
Sergunb 0:8918a71cdbe9 501 *
Sergunb 0:8918a71cdbe9 502 * Converts an octet string to a non-negative integer
Sergunb 0:8918a71cdbe9 503 *
Sergunb 0:8918a71cdbe9 504 * @param[out] r Non-negative integer resulting from the conversion
Sergunb 0:8918a71cdbe9 505 * @param[in] data Octet string to be converted
Sergunb 0:8918a71cdbe9 506 * @param[in] length Length of the octet string
Sergunb 0:8918a71cdbe9 507 * @return Error code
Sergunb 0:8918a71cdbe9 508 **/
Sergunb 0:8918a71cdbe9 509
Sergunb 0:8918a71cdbe9 510 error_t mpiReadRaw(Mpi *r, const uint8_t *data, uint_t length)
Sergunb 0:8918a71cdbe9 511 {
Sergunb 0:8918a71cdbe9 512 error_t error;
Sergunb 0:8918a71cdbe9 513 uint_t i;
Sergunb 0:8918a71cdbe9 514
Sergunb 0:8918a71cdbe9 515 //Skip leading zeroes
Sergunb 0:8918a71cdbe9 516 while(length > 1 && *data == 0)
Sergunb 0:8918a71cdbe9 517 {
Sergunb 0:8918a71cdbe9 518 //Advance read pointer
Sergunb 0:8918a71cdbe9 519 data++;
Sergunb 0:8918a71cdbe9 520 length--;
Sergunb 0:8918a71cdbe9 521 }
Sergunb 0:8918a71cdbe9 522
Sergunb 0:8918a71cdbe9 523 //Ajust the size of the multiple precision integer
Sergunb 0:8918a71cdbe9 524 error = mpiGrow(r, (length + MPI_INT_SIZE - 1) / MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 525 //Failed to adjust the size?
Sergunb 0:8918a71cdbe9 526 if(error)
Sergunb 0:8918a71cdbe9 527 return error;
Sergunb 0:8918a71cdbe9 528
Sergunb 0:8918a71cdbe9 529 //Clear the contents of the multiple precision integer
Sergunb 0:8918a71cdbe9 530 memset(r->data, 0, r->size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 531 //Set sign
Sergunb 0:8918a71cdbe9 532 r->sign = 1;
Sergunb 0:8918a71cdbe9 533
Sergunb 0:8918a71cdbe9 534 //Start from the least significant byte
Sergunb 0:8918a71cdbe9 535 data += length - 1;
Sergunb 0:8918a71cdbe9 536
Sergunb 0:8918a71cdbe9 537 //Copy data
Sergunb 0:8918a71cdbe9 538 for(i = 0; i < length; i++, data--)
Sergunb 0:8918a71cdbe9 539 r->data[i / MPI_INT_SIZE] |= *data << ((i % MPI_INT_SIZE) * 8);
Sergunb 0:8918a71cdbe9 540
Sergunb 0:8918a71cdbe9 541 //The conversion succeeded
Sergunb 0:8918a71cdbe9 542 return NO_ERROR;
Sergunb 0:8918a71cdbe9 543 }
Sergunb 0:8918a71cdbe9 544
Sergunb 0:8918a71cdbe9 545
Sergunb 0:8918a71cdbe9 546 /**
Sergunb 0:8918a71cdbe9 547 * @brief Integer to octet string conversion
Sergunb 0:8918a71cdbe9 548 *
Sergunb 0:8918a71cdbe9 549 * Converts an integer to an octet string of a specified length
Sergunb 0:8918a71cdbe9 550 *
Sergunb 0:8918a71cdbe9 551 * @param[in] a Non-negative integer to be converted
Sergunb 0:8918a71cdbe9 552 * @param[out] data Octet string resulting from the conversion
Sergunb 0:8918a71cdbe9 553 * @param[in] length Intended length of the resulting octet string
Sergunb 0:8918a71cdbe9 554 * @return Error code
Sergunb 0:8918a71cdbe9 555 **/
Sergunb 0:8918a71cdbe9 556
Sergunb 0:8918a71cdbe9 557 error_t mpiWriteRaw(const Mpi *a, uint8_t *data, uint_t length)
Sergunb 0:8918a71cdbe9 558 {
Sergunb 0:8918a71cdbe9 559 uint_t i;
Sergunb 0:8918a71cdbe9 560
Sergunb 0:8918a71cdbe9 561 //Get the actual length in bytes
Sergunb 0:8918a71cdbe9 562 uint_t n = mpiGetByteLength(a);
Sergunb 0:8918a71cdbe9 563
Sergunb 0:8918a71cdbe9 564 //Make sure the output buffer is large enough
Sergunb 0:8918a71cdbe9 565 if(n > length)
Sergunb 0:8918a71cdbe9 566 return ERROR_INVALID_LENGTH;
Sergunb 0:8918a71cdbe9 567
Sergunb 0:8918a71cdbe9 568 //Clear output buffer
Sergunb 0:8918a71cdbe9 569 memset(data, 0, length);
Sergunb 0:8918a71cdbe9 570
Sergunb 0:8918a71cdbe9 571 //Start from the least significant word
Sergunb 0:8918a71cdbe9 572 data += length - 1;
Sergunb 0:8918a71cdbe9 573
Sergunb 0:8918a71cdbe9 574 //Copy data
Sergunb 0:8918a71cdbe9 575 for(i = 0; i < n; i++, data--)
Sergunb 0:8918a71cdbe9 576 *data = a->data[i / MPI_INT_SIZE] >> ((i % MPI_INT_SIZE) * 8);
Sergunb 0:8918a71cdbe9 577
Sergunb 0:8918a71cdbe9 578 //The conversion succeeded
Sergunb 0:8918a71cdbe9 579 return NO_ERROR;
Sergunb 0:8918a71cdbe9 580 }
Sergunb 0:8918a71cdbe9 581
Sergunb 0:8918a71cdbe9 582
Sergunb 0:8918a71cdbe9 583 /**
Sergunb 0:8918a71cdbe9 584 * @brief Multiple precision addition
Sergunb 0:8918a71cdbe9 585 * @param[out] r Resulting integer R = A + B
Sergunb 0:8918a71cdbe9 586 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 587 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 588 * @return Error code
Sergunb 0:8918a71cdbe9 589 **/
Sergunb 0:8918a71cdbe9 590
Sergunb 0:8918a71cdbe9 591 error_t mpiAdd(Mpi *r, const Mpi *a, const Mpi *b)
Sergunb 0:8918a71cdbe9 592 {
Sergunb 0:8918a71cdbe9 593 error_t error;
Sergunb 0:8918a71cdbe9 594 int_t sign;
Sergunb 0:8918a71cdbe9 595
Sergunb 0:8918a71cdbe9 596 //Retrieve the sign of A
Sergunb 0:8918a71cdbe9 597 sign = a->sign;
Sergunb 0:8918a71cdbe9 598
Sergunb 0:8918a71cdbe9 599 //Both operands have the same sign?
Sergunb 0:8918a71cdbe9 600 if(a->sign == b->sign)
Sergunb 0:8918a71cdbe9 601 {
Sergunb 0:8918a71cdbe9 602 //Perform addition
Sergunb 0:8918a71cdbe9 603 error = mpiAddAbs(r, a, b);
Sergunb 0:8918a71cdbe9 604 //Set the sign of the resulting number
Sergunb 0:8918a71cdbe9 605 r->sign = sign;
Sergunb 0:8918a71cdbe9 606 }
Sergunb 0:8918a71cdbe9 607 //Operands have different signs?
Sergunb 0:8918a71cdbe9 608 else
Sergunb 0:8918a71cdbe9 609 {
Sergunb 0:8918a71cdbe9 610 //Compare the absolute value of A and B
Sergunb 0:8918a71cdbe9 611 if(mpiCompAbs(a, b) >= 0)
Sergunb 0:8918a71cdbe9 612 {
Sergunb 0:8918a71cdbe9 613 //Perform subtraction
Sergunb 0:8918a71cdbe9 614 error = mpiSubAbs(r, a, b);
Sergunb 0:8918a71cdbe9 615 //Set the sign of the resulting number
Sergunb 0:8918a71cdbe9 616 r->sign = sign;
Sergunb 0:8918a71cdbe9 617 }
Sergunb 0:8918a71cdbe9 618 else
Sergunb 0:8918a71cdbe9 619 {
Sergunb 0:8918a71cdbe9 620 //Perform subtraction
Sergunb 0:8918a71cdbe9 621 error = mpiSubAbs(r, b, a);
Sergunb 0:8918a71cdbe9 622 //Set the sign of the resulting number
Sergunb 0:8918a71cdbe9 623 r->sign = -sign;
Sergunb 0:8918a71cdbe9 624 }
Sergunb 0:8918a71cdbe9 625 }
Sergunb 0:8918a71cdbe9 626
Sergunb 0:8918a71cdbe9 627 //Return status code
Sergunb 0:8918a71cdbe9 628 return error;
Sergunb 0:8918a71cdbe9 629 }
Sergunb 0:8918a71cdbe9 630
Sergunb 0:8918a71cdbe9 631
Sergunb 0:8918a71cdbe9 632 /**
Sergunb 0:8918a71cdbe9 633 * @brief Add an integer to a multiple precision integer
Sergunb 0:8918a71cdbe9 634 * @param[out] r Resulting integer R = A + B
Sergunb 0:8918a71cdbe9 635 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 636 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 637 * @return Error code
Sergunb 0:8918a71cdbe9 638 **/
Sergunb 0:8918a71cdbe9 639
Sergunb 0:8918a71cdbe9 640 error_t mpiAddInt(Mpi *r, const Mpi *a, int_t b)
Sergunb 0:8918a71cdbe9 641 {
Sergunb 0:8918a71cdbe9 642 uint_t value;
Sergunb 0:8918a71cdbe9 643 Mpi t;
Sergunb 0:8918a71cdbe9 644
Sergunb 0:8918a71cdbe9 645 //Convert the second operand to a multiple precision integer
Sergunb 0:8918a71cdbe9 646 value = (b >= 0) ? b : -b;
Sergunb 0:8918a71cdbe9 647 t.sign = (b >= 0) ? 1 : -1;
Sergunb 0:8918a71cdbe9 648 t.size = 1;
Sergunb 0:8918a71cdbe9 649 t.data = &value;
Sergunb 0:8918a71cdbe9 650
Sergunb 0:8918a71cdbe9 651 //Perform addition
Sergunb 0:8918a71cdbe9 652 return mpiAdd(r, a ,&t);
Sergunb 0:8918a71cdbe9 653 }
Sergunb 0:8918a71cdbe9 654
Sergunb 0:8918a71cdbe9 655
Sergunb 0:8918a71cdbe9 656 /**
Sergunb 0:8918a71cdbe9 657 * @brief Multiple precision subtraction
Sergunb 0:8918a71cdbe9 658 * @param[out] r Resulting integer R = A - B
Sergunb 0:8918a71cdbe9 659 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 660 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 661 * @return Error code
Sergunb 0:8918a71cdbe9 662 **/
Sergunb 0:8918a71cdbe9 663
Sergunb 0:8918a71cdbe9 664 error_t mpiSub(Mpi *r, const Mpi *a, const Mpi *b)
Sergunb 0:8918a71cdbe9 665 {
Sergunb 0:8918a71cdbe9 666 error_t error;
Sergunb 0:8918a71cdbe9 667 int_t sign;
Sergunb 0:8918a71cdbe9 668
Sergunb 0:8918a71cdbe9 669 //Retrieve the sign of A
Sergunb 0:8918a71cdbe9 670 sign = a->sign;
Sergunb 0:8918a71cdbe9 671
Sergunb 0:8918a71cdbe9 672 //Both operands have the same sign?
Sergunb 0:8918a71cdbe9 673 if(a->sign == b->sign)
Sergunb 0:8918a71cdbe9 674 {
Sergunb 0:8918a71cdbe9 675 //Compare the absolute value of A and B
Sergunb 0:8918a71cdbe9 676 if(mpiCompAbs(a, b) >= 0)
Sergunb 0:8918a71cdbe9 677 {
Sergunb 0:8918a71cdbe9 678 //Perform subtraction
Sergunb 0:8918a71cdbe9 679 error = mpiSubAbs(r, a, b);
Sergunb 0:8918a71cdbe9 680 //Set the sign of the resulting number
Sergunb 0:8918a71cdbe9 681 r->sign = sign;
Sergunb 0:8918a71cdbe9 682 }
Sergunb 0:8918a71cdbe9 683 else
Sergunb 0:8918a71cdbe9 684 {
Sergunb 0:8918a71cdbe9 685 //Perform subtraction
Sergunb 0:8918a71cdbe9 686 error = mpiSubAbs(r, b, a);
Sergunb 0:8918a71cdbe9 687 //Set the sign of the resulting number
Sergunb 0:8918a71cdbe9 688 r->sign = -sign;
Sergunb 0:8918a71cdbe9 689 }
Sergunb 0:8918a71cdbe9 690 }
Sergunb 0:8918a71cdbe9 691 //Operands have different signs?
Sergunb 0:8918a71cdbe9 692 else
Sergunb 0:8918a71cdbe9 693 {
Sergunb 0:8918a71cdbe9 694 //Perform addition
Sergunb 0:8918a71cdbe9 695 error = mpiAddAbs(r, a, b);
Sergunb 0:8918a71cdbe9 696 //Set the sign of the resulting number
Sergunb 0:8918a71cdbe9 697 r->sign = sign;
Sergunb 0:8918a71cdbe9 698 }
Sergunb 0:8918a71cdbe9 699
Sergunb 0:8918a71cdbe9 700 //Return status code
Sergunb 0:8918a71cdbe9 701 return error;
Sergunb 0:8918a71cdbe9 702 }
Sergunb 0:8918a71cdbe9 703
Sergunb 0:8918a71cdbe9 704
Sergunb 0:8918a71cdbe9 705 /**
Sergunb 0:8918a71cdbe9 706 * @brief Subtract an integer from a multiple precision integer
Sergunb 0:8918a71cdbe9 707 * @param[out] r Resulting integer R = A - B
Sergunb 0:8918a71cdbe9 708 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 709 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 710 * @return Error code
Sergunb 0:8918a71cdbe9 711 **/
Sergunb 0:8918a71cdbe9 712
Sergunb 0:8918a71cdbe9 713 error_t mpiSubInt(Mpi *r, const Mpi *a, int_t b)
Sergunb 0:8918a71cdbe9 714 {
Sergunb 0:8918a71cdbe9 715 uint_t value;
Sergunb 0:8918a71cdbe9 716 Mpi t;
Sergunb 0:8918a71cdbe9 717
Sergunb 0:8918a71cdbe9 718 //Convert the second operand to a multiple precision integer
Sergunb 0:8918a71cdbe9 719 value = (b >= 0) ? b : -b;
Sergunb 0:8918a71cdbe9 720 t.sign = (b >= 0) ? 1 : -1;
Sergunb 0:8918a71cdbe9 721 t.size = 1;
Sergunb 0:8918a71cdbe9 722 t.data = &value;
Sergunb 0:8918a71cdbe9 723
Sergunb 0:8918a71cdbe9 724 //Perform subtraction
Sergunb 0:8918a71cdbe9 725 return mpiSub(r, a ,&t);
Sergunb 0:8918a71cdbe9 726 }
Sergunb 0:8918a71cdbe9 727
Sergunb 0:8918a71cdbe9 728
Sergunb 0:8918a71cdbe9 729 /**
Sergunb 0:8918a71cdbe9 730 * @brief Helper routine for multiple precision addition
Sergunb 0:8918a71cdbe9 731 * @param[out] r Resulting integer R = |A + B|
Sergunb 0:8918a71cdbe9 732 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 733 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 734 * @return Error code
Sergunb 0:8918a71cdbe9 735 **/
Sergunb 0:8918a71cdbe9 736
Sergunb 0:8918a71cdbe9 737 error_t mpiAddAbs(Mpi *r, const Mpi *a, const Mpi *b)
Sergunb 0:8918a71cdbe9 738 {
Sergunb 0:8918a71cdbe9 739 error_t error;
Sergunb 0:8918a71cdbe9 740 uint_t i;
Sergunb 0:8918a71cdbe9 741 uint_t n;
Sergunb 0:8918a71cdbe9 742 uint_t c;
Sergunb 0:8918a71cdbe9 743 uint_t d;
Sergunb 0:8918a71cdbe9 744
Sergunb 0:8918a71cdbe9 745 //R and B are the same instance?
Sergunb 0:8918a71cdbe9 746 if(r == b)
Sergunb 0:8918a71cdbe9 747 {
Sergunb 0:8918a71cdbe9 748 //Swap A and B
Sergunb 0:8918a71cdbe9 749 const Mpi *t = a;
Sergunb 0:8918a71cdbe9 750 a = b;
Sergunb 0:8918a71cdbe9 751 b = t;
Sergunb 0:8918a71cdbe9 752 }
Sergunb 0:8918a71cdbe9 753 //R is neither A nor B?
Sergunb 0:8918a71cdbe9 754 else if(r != a)
Sergunb 0:8918a71cdbe9 755 {
Sergunb 0:8918a71cdbe9 756 //Copy the first operand to R
Sergunb 0:8918a71cdbe9 757 MPI_CHECK(mpiCopy(r, a));
Sergunb 0:8918a71cdbe9 758 }
Sergunb 0:8918a71cdbe9 759
Sergunb 0:8918a71cdbe9 760 //Determine the actual length of B
Sergunb 0:8918a71cdbe9 761 n = mpiGetLength(b);
Sergunb 0:8918a71cdbe9 762 //Extend the size of the destination register as needed
Sergunb 0:8918a71cdbe9 763 MPI_CHECK(mpiGrow(r, n));
Sergunb 0:8918a71cdbe9 764
Sergunb 0:8918a71cdbe9 765 //The result is always positive
Sergunb 0:8918a71cdbe9 766 r->sign = 1;
Sergunb 0:8918a71cdbe9 767 //Clear carry bit
Sergunb 0:8918a71cdbe9 768 c = 0;
Sergunb 0:8918a71cdbe9 769
Sergunb 0:8918a71cdbe9 770 //Add operands
Sergunb 0:8918a71cdbe9 771 for(i = 0; i < n; i++)
Sergunb 0:8918a71cdbe9 772 {
Sergunb 0:8918a71cdbe9 773 //Add carry bit
Sergunb 0:8918a71cdbe9 774 d = r->data[i] + c;
Sergunb 0:8918a71cdbe9 775 //Update carry bit
Sergunb 0:8918a71cdbe9 776 if(d != 0) c = 0;
Sergunb 0:8918a71cdbe9 777 //Perform addition
Sergunb 0:8918a71cdbe9 778 d += b->data[i];
Sergunb 0:8918a71cdbe9 779 //Update carry bit
Sergunb 0:8918a71cdbe9 780 if(d < b->data[i]) c = 1;
Sergunb 0:8918a71cdbe9 781 //Save result
Sergunb 0:8918a71cdbe9 782 r->data[i] = d;
Sergunb 0:8918a71cdbe9 783 }
Sergunb 0:8918a71cdbe9 784
Sergunb 0:8918a71cdbe9 785 //Loop as long as the carry bit is set
Sergunb 0:8918a71cdbe9 786 for(i = n; c && i < r->size; i++)
Sergunb 0:8918a71cdbe9 787 {
Sergunb 0:8918a71cdbe9 788 //Add carry bit
Sergunb 0:8918a71cdbe9 789 r->data[i] += c;
Sergunb 0:8918a71cdbe9 790 //Update carry bit
Sergunb 0:8918a71cdbe9 791 if(r->data[i] != 0) c = 0;
Sergunb 0:8918a71cdbe9 792 }
Sergunb 0:8918a71cdbe9 793
Sergunb 0:8918a71cdbe9 794 //Check the final carry bit
Sergunb 0:8918a71cdbe9 795 if(c && n >= r->size)
Sergunb 0:8918a71cdbe9 796 {
Sergunb 0:8918a71cdbe9 797 //Extend the size of the destination register
Sergunb 0:8918a71cdbe9 798 MPI_CHECK(mpiGrow(r, n + 1));
Sergunb 0:8918a71cdbe9 799 //Add carry bit
Sergunb 0:8918a71cdbe9 800 r->data[n] = 1;
Sergunb 0:8918a71cdbe9 801 }
Sergunb 0:8918a71cdbe9 802
Sergunb 0:8918a71cdbe9 803 end:
Sergunb 0:8918a71cdbe9 804 //Return status code
Sergunb 0:8918a71cdbe9 805 return error;
Sergunb 0:8918a71cdbe9 806 }
Sergunb 0:8918a71cdbe9 807
Sergunb 0:8918a71cdbe9 808
Sergunb 0:8918a71cdbe9 809 /**
Sergunb 0:8918a71cdbe9 810 * @brief Helper routine for multiple precision subtraction
Sergunb 0:8918a71cdbe9 811 * @param[out] r Resulting integer R = |A - B|
Sergunb 0:8918a71cdbe9 812 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 813 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 814 * @return Error code
Sergunb 0:8918a71cdbe9 815 **/
Sergunb 0:8918a71cdbe9 816
Sergunb 0:8918a71cdbe9 817 error_t mpiSubAbs(Mpi *r, const Mpi *a, const Mpi *b)
Sergunb 0:8918a71cdbe9 818 {
Sergunb 0:8918a71cdbe9 819 error_t error;
Sergunb 0:8918a71cdbe9 820 uint_t c;
Sergunb 0:8918a71cdbe9 821 uint_t d;
Sergunb 0:8918a71cdbe9 822 uint_t i;
Sergunb 0:8918a71cdbe9 823 uint_t m;
Sergunb 0:8918a71cdbe9 824 uint_t n;
Sergunb 0:8918a71cdbe9 825
Sergunb 0:8918a71cdbe9 826 //Check input parameters
Sergunb 0:8918a71cdbe9 827 if(mpiCompAbs(a, b) < 0)
Sergunb 0:8918a71cdbe9 828 {
Sergunb 0:8918a71cdbe9 829 //Swap A and B if necessary
Sergunb 0:8918a71cdbe9 830 const Mpi *t = b;
Sergunb 0:8918a71cdbe9 831 a = b;
Sergunb 0:8918a71cdbe9 832 b = t;
Sergunb 0:8918a71cdbe9 833 }
Sergunb 0:8918a71cdbe9 834
Sergunb 0:8918a71cdbe9 835 //Determine the actual length of A
Sergunb 0:8918a71cdbe9 836 m = mpiGetLength(a);
Sergunb 0:8918a71cdbe9 837 //Determine the actual length of B
Sergunb 0:8918a71cdbe9 838 n = mpiGetLength(b);
Sergunb 0:8918a71cdbe9 839
Sergunb 0:8918a71cdbe9 840 //Extend the size of the destination register as needed
Sergunb 0:8918a71cdbe9 841 MPI_CHECK(mpiGrow(r, m));
Sergunb 0:8918a71cdbe9 842
Sergunb 0:8918a71cdbe9 843 //The result is always positive
Sergunb 0:8918a71cdbe9 844 r->sign = 1;
Sergunb 0:8918a71cdbe9 845 //Clear carry bit
Sergunb 0:8918a71cdbe9 846 c = 0;
Sergunb 0:8918a71cdbe9 847
Sergunb 0:8918a71cdbe9 848 //Subtract operands
Sergunb 0:8918a71cdbe9 849 for(i = 0; i < n; i++)
Sergunb 0:8918a71cdbe9 850 {
Sergunb 0:8918a71cdbe9 851 //Read first operand
Sergunb 0:8918a71cdbe9 852 d = a->data[i];
Sergunb 0:8918a71cdbe9 853
Sergunb 0:8918a71cdbe9 854 //Check the carry bit
Sergunb 0:8918a71cdbe9 855 if(c)
Sergunb 0:8918a71cdbe9 856 {
Sergunb 0:8918a71cdbe9 857 //Update carry bit
Sergunb 0:8918a71cdbe9 858 if(d != 0) c = 0;
Sergunb 0:8918a71cdbe9 859 //Propagate carry bit
Sergunb 0:8918a71cdbe9 860 d -= 1;
Sergunb 0:8918a71cdbe9 861 }
Sergunb 0:8918a71cdbe9 862
Sergunb 0:8918a71cdbe9 863 //Update carry bit
Sergunb 0:8918a71cdbe9 864 if(d < b->data[i]) c = 1;
Sergunb 0:8918a71cdbe9 865 //Perform subtraction
Sergunb 0:8918a71cdbe9 866 r->data[i] = d - b->data[i];
Sergunb 0:8918a71cdbe9 867 }
Sergunb 0:8918a71cdbe9 868
Sergunb 0:8918a71cdbe9 869 //Loop as long as the carry bit is set
Sergunb 0:8918a71cdbe9 870 for(i = n; c && i < m; i++)
Sergunb 0:8918a71cdbe9 871 {
Sergunb 0:8918a71cdbe9 872 //Update carry bit
Sergunb 0:8918a71cdbe9 873 if(a->data[i] != 0) c = 0;
Sergunb 0:8918a71cdbe9 874 //Propagate carry bit
Sergunb 0:8918a71cdbe9 875 r->data[i] = a->data[i] - 1;
Sergunb 0:8918a71cdbe9 876 }
Sergunb 0:8918a71cdbe9 877
Sergunb 0:8918a71cdbe9 878 //R and A are not the same instance?
Sergunb 0:8918a71cdbe9 879 if(r != a)
Sergunb 0:8918a71cdbe9 880 {
Sergunb 0:8918a71cdbe9 881 //Copy the remaining words
Sergunb 0:8918a71cdbe9 882 for(; i < m; i++)
Sergunb 0:8918a71cdbe9 883 r->data[i] = a->data[i];
Sergunb 0:8918a71cdbe9 884
Sergunb 0:8918a71cdbe9 885 //Zero the upper part of R
Sergunb 0:8918a71cdbe9 886 for(; i < r->size; i++)
Sergunb 0:8918a71cdbe9 887 r->data[i] = 0;
Sergunb 0:8918a71cdbe9 888 }
Sergunb 0:8918a71cdbe9 889
Sergunb 0:8918a71cdbe9 890 end:
Sergunb 0:8918a71cdbe9 891 //Return status code
Sergunb 0:8918a71cdbe9 892 return error;
Sergunb 0:8918a71cdbe9 893 }
Sergunb 0:8918a71cdbe9 894
Sergunb 0:8918a71cdbe9 895
Sergunb 0:8918a71cdbe9 896 /**
Sergunb 0:8918a71cdbe9 897 * @brief Left shift operation
Sergunb 0:8918a71cdbe9 898 * @param[in,out] r The multiple precision integer to be shifted to the left
Sergunb 0:8918a71cdbe9 899 * @param[in] n The number of bits to shift
Sergunb 0:8918a71cdbe9 900 * @return Error code
Sergunb 0:8918a71cdbe9 901 **/
Sergunb 0:8918a71cdbe9 902
Sergunb 0:8918a71cdbe9 903 error_t mpiShiftLeft(Mpi *r, uint_t n)
Sergunb 0:8918a71cdbe9 904 {
Sergunb 0:8918a71cdbe9 905 error_t error;
Sergunb 0:8918a71cdbe9 906 uint_t i;
Sergunb 0:8918a71cdbe9 907
Sergunb 0:8918a71cdbe9 908 //Number of 32-bit words to shift
Sergunb 0:8918a71cdbe9 909 uint_t n1 = n / (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 910 //Number of bits to shift
Sergunb 0:8918a71cdbe9 911 uint_t n2 = n % (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 912
Sergunb 0:8918a71cdbe9 913 //Check parameters
Sergunb 0:8918a71cdbe9 914 if(!r->size || !n)
Sergunb 0:8918a71cdbe9 915 return NO_ERROR;
Sergunb 0:8918a71cdbe9 916
Sergunb 0:8918a71cdbe9 917 //Increase the size of the multiple-precision number
Sergunb 0:8918a71cdbe9 918 error = mpiGrow(r, r->size + (n + 31) / 32);
Sergunb 0:8918a71cdbe9 919 //Check return code
Sergunb 0:8918a71cdbe9 920 if(error)
Sergunb 0:8918a71cdbe9 921 return error;
Sergunb 0:8918a71cdbe9 922
Sergunb 0:8918a71cdbe9 923 //First, shift words
Sergunb 0:8918a71cdbe9 924 if(n1 > 0)
Sergunb 0:8918a71cdbe9 925 {
Sergunb 0:8918a71cdbe9 926 //Process the most significant words
Sergunb 0:8918a71cdbe9 927 for(i = r->size - 1; i >= n1; i--)
Sergunb 0:8918a71cdbe9 928 r->data[i] = r->data[i - n1];
Sergunb 0:8918a71cdbe9 929 //Fill the rest with zeroes
Sergunb 0:8918a71cdbe9 930 for(i = 0; i < n1; i++)
Sergunb 0:8918a71cdbe9 931 r->data[i] = 0;
Sergunb 0:8918a71cdbe9 932 }
Sergunb 0:8918a71cdbe9 933 //Then shift bits
Sergunb 0:8918a71cdbe9 934 if(n2 > 0)
Sergunb 0:8918a71cdbe9 935 {
Sergunb 0:8918a71cdbe9 936 //Process the most significant words
Sergunb 0:8918a71cdbe9 937 for(i = r->size - 1; i >= 1; i--)
Sergunb 0:8918a71cdbe9 938 r->data[i] = (r->data[i] << n2) | (r->data[i - 1] >> (32 - n2));
Sergunb 0:8918a71cdbe9 939 //The least significant word requires a special handling
Sergunb 0:8918a71cdbe9 940 r->data[0] <<= n2;
Sergunb 0:8918a71cdbe9 941 }
Sergunb 0:8918a71cdbe9 942
Sergunb 0:8918a71cdbe9 943 //Shift operation is complete
Sergunb 0:8918a71cdbe9 944 return NO_ERROR;
Sergunb 0:8918a71cdbe9 945 }
Sergunb 0:8918a71cdbe9 946
Sergunb 0:8918a71cdbe9 947
Sergunb 0:8918a71cdbe9 948 /**
Sergunb 0:8918a71cdbe9 949 * @brief Right shift operation
Sergunb 0:8918a71cdbe9 950 * @param[in,out] r The multiple precision integer to be shifted to the right
Sergunb 0:8918a71cdbe9 951 * @param[in] n The number of bits to shift
Sergunb 0:8918a71cdbe9 952 * @return Error code
Sergunb 0:8918a71cdbe9 953 **/
Sergunb 0:8918a71cdbe9 954
Sergunb 0:8918a71cdbe9 955 error_t mpiShiftRight(Mpi *r, uint_t n)
Sergunb 0:8918a71cdbe9 956 {
Sergunb 0:8918a71cdbe9 957 uint_t i;
Sergunb 0:8918a71cdbe9 958 uint_t m;
Sergunb 0:8918a71cdbe9 959
Sergunb 0:8918a71cdbe9 960 //Number of 32-bit words to shift
Sergunb 0:8918a71cdbe9 961 uint_t n1 = n / (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 962 //Number of bits to shift
Sergunb 0:8918a71cdbe9 963 uint_t n2 = n % (MPI_INT_SIZE * 8);
Sergunb 0:8918a71cdbe9 964
Sergunb 0:8918a71cdbe9 965 //Check parameters
Sergunb 0:8918a71cdbe9 966 if(n1 >= r->size)
Sergunb 0:8918a71cdbe9 967 {
Sergunb 0:8918a71cdbe9 968 memset(r->data, 0, r->size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 969 return NO_ERROR;
Sergunb 0:8918a71cdbe9 970 }
Sergunb 0:8918a71cdbe9 971
Sergunb 0:8918a71cdbe9 972 //First, shift words
Sergunb 0:8918a71cdbe9 973 if(n1 > 0)
Sergunb 0:8918a71cdbe9 974 {
Sergunb 0:8918a71cdbe9 975 //Process the least significant words
Sergunb 0:8918a71cdbe9 976 for(m = r->size - n1, i = 0; i < m; i++)
Sergunb 0:8918a71cdbe9 977 r->data[i] = r->data[i + n1];
Sergunb 0:8918a71cdbe9 978 //Fill the rest with zeroes
Sergunb 0:8918a71cdbe9 979 for(i = m; i < r->size; i++)
Sergunb 0:8918a71cdbe9 980 r->data[i] = 0;
Sergunb 0:8918a71cdbe9 981 }
Sergunb 0:8918a71cdbe9 982 //Then shift bits
Sergunb 0:8918a71cdbe9 983 if(n2 > 0)
Sergunb 0:8918a71cdbe9 984 {
Sergunb 0:8918a71cdbe9 985 //Process the least significant words
Sergunb 0:8918a71cdbe9 986 for(m = r->size - n1 - 1, i = 0; i < m; i++)
Sergunb 0:8918a71cdbe9 987 r->data[i] = (r->data[i] >> n2) | (r->data[i + 1] << (32 - n2));
Sergunb 0:8918a71cdbe9 988 //The most significant word requires a special handling
Sergunb 0:8918a71cdbe9 989 r->data[m] >>= n2;
Sergunb 0:8918a71cdbe9 990 }
Sergunb 0:8918a71cdbe9 991
Sergunb 0:8918a71cdbe9 992 //Shift operation is complete
Sergunb 0:8918a71cdbe9 993 return NO_ERROR;
Sergunb 0:8918a71cdbe9 994 }
Sergunb 0:8918a71cdbe9 995
Sergunb 0:8918a71cdbe9 996
Sergunb 0:8918a71cdbe9 997 /**
Sergunb 0:8918a71cdbe9 998 * @brief Multiple precision multiplication
Sergunb 0:8918a71cdbe9 999 * @param[out] r Resulting integer R = A * B
Sergunb 0:8918a71cdbe9 1000 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 1001 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 1002 * @return Error code
Sergunb 0:8918a71cdbe9 1003 **/
Sergunb 0:8918a71cdbe9 1004
Sergunb 0:8918a71cdbe9 1005 error_t mpiMul(Mpi *r, const Mpi *a, const Mpi *b)
Sergunb 0:8918a71cdbe9 1006 {
Sergunb 0:8918a71cdbe9 1007 error_t error;
Sergunb 0:8918a71cdbe9 1008 int_t i;
Sergunb 0:8918a71cdbe9 1009 int_t m;
Sergunb 0:8918a71cdbe9 1010 int_t n;
Sergunb 0:8918a71cdbe9 1011 Mpi ta;
Sergunb 0:8918a71cdbe9 1012 Mpi tb;
Sergunb 0:8918a71cdbe9 1013
Sergunb 0:8918a71cdbe9 1014 //Initialize multiple precision integers
Sergunb 0:8918a71cdbe9 1015 mpiInit(&ta);
Sergunb 0:8918a71cdbe9 1016 mpiInit(&tb);
Sergunb 0:8918a71cdbe9 1017
Sergunb 0:8918a71cdbe9 1018 //R and A are the same instance?
Sergunb 0:8918a71cdbe9 1019 if(r == a)
Sergunb 0:8918a71cdbe9 1020 {
Sergunb 0:8918a71cdbe9 1021 //Copy A to TA
Sergunb 0:8918a71cdbe9 1022 MPI_CHECK(mpiCopy(&ta, a));
Sergunb 0:8918a71cdbe9 1023 //Use TA instead of A
Sergunb 0:8918a71cdbe9 1024 a = &ta;
Sergunb 0:8918a71cdbe9 1025 }
Sergunb 0:8918a71cdbe9 1026
Sergunb 0:8918a71cdbe9 1027 //R and B are the same instance?
Sergunb 0:8918a71cdbe9 1028 if(r == b)
Sergunb 0:8918a71cdbe9 1029 {
Sergunb 0:8918a71cdbe9 1030 //Copy B to TB
Sergunb 0:8918a71cdbe9 1031 MPI_CHECK(mpiCopy(&tb, b));
Sergunb 0:8918a71cdbe9 1032 //Use TB instead of B
Sergunb 0:8918a71cdbe9 1033 b = &tb;
Sergunb 0:8918a71cdbe9 1034 }
Sergunb 0:8918a71cdbe9 1035
Sergunb 0:8918a71cdbe9 1036 //Determine the actual length of A and B
Sergunb 0:8918a71cdbe9 1037 m = mpiGetLength(a);
Sergunb 0:8918a71cdbe9 1038 n = mpiGetLength(b);
Sergunb 0:8918a71cdbe9 1039
Sergunb 0:8918a71cdbe9 1040 //Adjust the size of R
Sergunb 0:8918a71cdbe9 1041 MPI_CHECK(mpiGrow(r, m + n));
Sergunb 0:8918a71cdbe9 1042 //Set the sign of R
Sergunb 0:8918a71cdbe9 1043 r->sign = (a->sign == b->sign) ? 1 : -1;
Sergunb 0:8918a71cdbe9 1044
Sergunb 0:8918a71cdbe9 1045 //Clear the contents of the destination integer
Sergunb 0:8918a71cdbe9 1046 memset(r->data, 0, r->size * MPI_INT_SIZE);
Sergunb 0:8918a71cdbe9 1047
Sergunb 0:8918a71cdbe9 1048 //Perform multiplication
Sergunb 0:8918a71cdbe9 1049 if(m < n)
Sergunb 0:8918a71cdbe9 1050 {
Sergunb 0:8918a71cdbe9 1051 for(i = 0; i < m; i++)
Sergunb 0:8918a71cdbe9 1052 mpiMulAccCore(&r->data[i], b->data, n, a->data[i]);
Sergunb 0:8918a71cdbe9 1053 }
Sergunb 0:8918a71cdbe9 1054 else
Sergunb 0:8918a71cdbe9 1055 {
Sergunb 0:8918a71cdbe9 1056 for(i = 0; i < n; i++)
Sergunb 0:8918a71cdbe9 1057 mpiMulAccCore(&r->data[i], a->data, m, b->data[i]);
Sergunb 0:8918a71cdbe9 1058 }
Sergunb 0:8918a71cdbe9 1059
Sergunb 0:8918a71cdbe9 1060 end:
Sergunb 0:8918a71cdbe9 1061 //Release multiple precision integers
Sergunb 0:8918a71cdbe9 1062 mpiFree(&ta);
Sergunb 0:8918a71cdbe9 1063 mpiFree(&tb);
Sergunb 0:8918a71cdbe9 1064
Sergunb 0:8918a71cdbe9 1065 //Return status code
Sergunb 0:8918a71cdbe9 1066 return error;
Sergunb 0:8918a71cdbe9 1067 }
Sergunb 0:8918a71cdbe9 1068
Sergunb 0:8918a71cdbe9 1069
Sergunb 0:8918a71cdbe9 1070 /**
Sergunb 0:8918a71cdbe9 1071 * @brief Multiply a multiple precision integer by an integer
Sergunb 0:8918a71cdbe9 1072 * @param[out] r Resulting integer R = A * B
Sergunb 0:8918a71cdbe9 1073 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 1074 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 1075 * @return Error code
Sergunb 0:8918a71cdbe9 1076 **/
Sergunb 0:8918a71cdbe9 1077
Sergunb 0:8918a71cdbe9 1078 error_t mpiMulInt(Mpi *r, const Mpi *a, int_t b)
Sergunb 0:8918a71cdbe9 1079 {
Sergunb 0:8918a71cdbe9 1080 uint_t value;
Sergunb 0:8918a71cdbe9 1081 Mpi t;
Sergunb 0:8918a71cdbe9 1082
Sergunb 0:8918a71cdbe9 1083 //Convert the second operand to a multiple precision integer
Sergunb 0:8918a71cdbe9 1084 value = (b >= 0) ? b : -b;
Sergunb 0:8918a71cdbe9 1085 t.sign = (b >= 0) ? 1 : -1;
Sergunb 0:8918a71cdbe9 1086 t.size = 1;
Sergunb 0:8918a71cdbe9 1087 t.data = &value;
Sergunb 0:8918a71cdbe9 1088
Sergunb 0:8918a71cdbe9 1089 //Perform multiplication
Sergunb 0:8918a71cdbe9 1090 return mpiMul(r, a, &t);
Sergunb 0:8918a71cdbe9 1091 }
Sergunb 0:8918a71cdbe9 1092
Sergunb 0:8918a71cdbe9 1093
Sergunb 0:8918a71cdbe9 1094 /**
Sergunb 0:8918a71cdbe9 1095 * @brief Multiple precision division
Sergunb 0:8918a71cdbe9 1096 * @param[out] q The quotient Q = A / B
Sergunb 0:8918a71cdbe9 1097 * @param[out] r The remainder R = A mod B
Sergunb 0:8918a71cdbe9 1098 * @param[in] a The dividend A
Sergunb 0:8918a71cdbe9 1099 * @param[in] b The divisor B
Sergunb 0:8918a71cdbe9 1100 * @return Error code
Sergunb 0:8918a71cdbe9 1101 **/
Sergunb 0:8918a71cdbe9 1102
Sergunb 0:8918a71cdbe9 1103 error_t mpiDiv(Mpi *q, Mpi *r, const Mpi *a, const Mpi *b)
Sergunb 0:8918a71cdbe9 1104 {
Sergunb 0:8918a71cdbe9 1105 error_t error;
Sergunb 0:8918a71cdbe9 1106 uint_t m;
Sergunb 0:8918a71cdbe9 1107 uint_t n;
Sergunb 0:8918a71cdbe9 1108 Mpi c;
Sergunb 0:8918a71cdbe9 1109 Mpi d;
Sergunb 0:8918a71cdbe9 1110 Mpi e;
Sergunb 0:8918a71cdbe9 1111
Sergunb 0:8918a71cdbe9 1112 //Check whether the divisor is equal to zero
Sergunb 0:8918a71cdbe9 1113 if(!mpiCompInt(b, 0))
Sergunb 0:8918a71cdbe9 1114 return ERROR_INVALID_PARAMETER;
Sergunb 0:8918a71cdbe9 1115
Sergunb 0:8918a71cdbe9 1116 //Initialize multiple precision integers
Sergunb 0:8918a71cdbe9 1117 mpiInit(&c);
Sergunb 0:8918a71cdbe9 1118 mpiInit(&d);
Sergunb 0:8918a71cdbe9 1119 mpiInit(&e);
Sergunb 0:8918a71cdbe9 1120
Sergunb 0:8918a71cdbe9 1121 MPI_CHECK(mpiCopy(&c, a));
Sergunb 0:8918a71cdbe9 1122 MPI_CHECK(mpiCopy(&d, b));
Sergunb 0:8918a71cdbe9 1123 MPI_CHECK(mpiSetValue(&e, 0));
Sergunb 0:8918a71cdbe9 1124
Sergunb 0:8918a71cdbe9 1125 m = mpiGetBitLength(&c);
Sergunb 0:8918a71cdbe9 1126 n = mpiGetBitLength(&d);
Sergunb 0:8918a71cdbe9 1127
Sergunb 0:8918a71cdbe9 1128 if(m > n)
Sergunb 0:8918a71cdbe9 1129 MPI_CHECK(mpiShiftLeft(&d, m - n));
Sergunb 0:8918a71cdbe9 1130
Sergunb 0:8918a71cdbe9 1131 while(n++ <= m)
Sergunb 0:8918a71cdbe9 1132 {
Sergunb 0:8918a71cdbe9 1133 MPI_CHECK(mpiShiftLeft(&e, 1));
Sergunb 0:8918a71cdbe9 1134
Sergunb 0:8918a71cdbe9 1135 if(mpiComp(&c, &d) >= 0)
Sergunb 0:8918a71cdbe9 1136 {
Sergunb 0:8918a71cdbe9 1137 MPI_CHECK(mpiSetBitValue(&e, 0, 1));
Sergunb 0:8918a71cdbe9 1138 MPI_CHECK(mpiSub(&c, &c, &d));
Sergunb 0:8918a71cdbe9 1139 }
Sergunb 0:8918a71cdbe9 1140
Sergunb 0:8918a71cdbe9 1141 MPI_CHECK(mpiShiftRight(&d, 1));
Sergunb 0:8918a71cdbe9 1142 }
Sergunb 0:8918a71cdbe9 1143
Sergunb 0:8918a71cdbe9 1144 if(q != NULL)
Sergunb 0:8918a71cdbe9 1145 MPI_CHECK(mpiCopy(q, &e));
Sergunb 0:8918a71cdbe9 1146
Sergunb 0:8918a71cdbe9 1147 if(r != NULL)
Sergunb 0:8918a71cdbe9 1148 MPI_CHECK(mpiCopy(r, &c));
Sergunb 0:8918a71cdbe9 1149
Sergunb 0:8918a71cdbe9 1150 end:
Sergunb 0:8918a71cdbe9 1151 //Release previously allocated memory
Sergunb 0:8918a71cdbe9 1152 mpiFree(&c);
Sergunb 0:8918a71cdbe9 1153 mpiFree(&d);
Sergunb 0:8918a71cdbe9 1154 mpiFree(&e);
Sergunb 0:8918a71cdbe9 1155
Sergunb 0:8918a71cdbe9 1156 //Return status code
Sergunb 0:8918a71cdbe9 1157 return error;
Sergunb 0:8918a71cdbe9 1158 }
Sergunb 0:8918a71cdbe9 1159
Sergunb 0:8918a71cdbe9 1160
Sergunb 0:8918a71cdbe9 1161 /**
Sergunb 0:8918a71cdbe9 1162 * @brief Divide a multiple precision integer by an integer
Sergunb 0:8918a71cdbe9 1163 * @param[out] q The quotient Q = A / B
Sergunb 0:8918a71cdbe9 1164 * @param[out] r The remainder R = A mod B
Sergunb 0:8918a71cdbe9 1165 * @param[in] a The dividend A
Sergunb 0:8918a71cdbe9 1166 * @param[in] b The divisor B
Sergunb 0:8918a71cdbe9 1167 * @return Error code
Sergunb 0:8918a71cdbe9 1168 **/
Sergunb 0:8918a71cdbe9 1169
Sergunb 0:8918a71cdbe9 1170 error_t mpiDivInt(Mpi *q, Mpi *r, const Mpi *a, int_t b)
Sergunb 0:8918a71cdbe9 1171 {
Sergunb 0:8918a71cdbe9 1172 uint_t value;
Sergunb 0:8918a71cdbe9 1173 Mpi t;
Sergunb 0:8918a71cdbe9 1174
Sergunb 0:8918a71cdbe9 1175 //Convert the divisor to a multiple precision integer
Sergunb 0:8918a71cdbe9 1176 value = (b >= 0) ? b : -b;
Sergunb 0:8918a71cdbe9 1177 t.sign = (b >= 0) ? 1 : -1;
Sergunb 0:8918a71cdbe9 1178 t.size = 1;
Sergunb 0:8918a71cdbe9 1179 t.data = &value;
Sergunb 0:8918a71cdbe9 1180
Sergunb 0:8918a71cdbe9 1181 //Perform division
Sergunb 0:8918a71cdbe9 1182 return mpiDiv(q, r, a, &t);
Sergunb 0:8918a71cdbe9 1183 }
Sergunb 0:8918a71cdbe9 1184
Sergunb 0:8918a71cdbe9 1185
Sergunb 0:8918a71cdbe9 1186 /**
Sergunb 0:8918a71cdbe9 1187 * @brief Modulo operation
Sergunb 0:8918a71cdbe9 1188 * @param[out] r Resulting integer R = A mod P
Sergunb 0:8918a71cdbe9 1189 * @param[in] a The multiple precision integer to be reduced
Sergunb 0:8918a71cdbe9 1190 * @param[in] p The modulus P
Sergunb 0:8918a71cdbe9 1191 * @return Error code
Sergunb 0:8918a71cdbe9 1192 **/
Sergunb 0:8918a71cdbe9 1193
Sergunb 0:8918a71cdbe9 1194 error_t mpiMod(Mpi *r, const Mpi *a, const Mpi *p)
Sergunb 0:8918a71cdbe9 1195 {
Sergunb 0:8918a71cdbe9 1196 error_t error;
Sergunb 0:8918a71cdbe9 1197 int_t sign;
Sergunb 0:8918a71cdbe9 1198 uint_t m;
Sergunb 0:8918a71cdbe9 1199 uint_t n;
Sergunb 0:8918a71cdbe9 1200 Mpi c;
Sergunb 0:8918a71cdbe9 1201
Sergunb 0:8918a71cdbe9 1202 //Make sure the modulus is positive
Sergunb 0:8918a71cdbe9 1203 if(mpiCompInt(p, 0) <= 0)
Sergunb 0:8918a71cdbe9 1204 return ERROR_INVALID_PARAMETER;
Sergunb 0:8918a71cdbe9 1205
Sergunb 0:8918a71cdbe9 1206 //Initialize multiple precision integer
Sergunb 0:8918a71cdbe9 1207 mpiInit(&c);
Sergunb 0:8918a71cdbe9 1208
Sergunb 0:8918a71cdbe9 1209 //Save the sign of A
Sergunb 0:8918a71cdbe9 1210 sign = a->sign;
Sergunb 0:8918a71cdbe9 1211 //Determine the actual length of A
Sergunb 0:8918a71cdbe9 1212 m = mpiGetBitLength(a);
Sergunb 0:8918a71cdbe9 1213 //Determine the actual length of P
Sergunb 0:8918a71cdbe9 1214 n = mpiGetBitLength(p);
Sergunb 0:8918a71cdbe9 1215
Sergunb 0:8918a71cdbe9 1216 //Let R = A
Sergunb 0:8918a71cdbe9 1217 MPI_CHECK(mpiCopy(r, a));
Sergunb 0:8918a71cdbe9 1218
Sergunb 0:8918a71cdbe9 1219 if(m >= n)
Sergunb 0:8918a71cdbe9 1220 {
Sergunb 0:8918a71cdbe9 1221 MPI_CHECK(mpiCopy(&c, p));
Sergunb 0:8918a71cdbe9 1222 MPI_CHECK(mpiShiftLeft(&c, m - n));
Sergunb 0:8918a71cdbe9 1223
Sergunb 0:8918a71cdbe9 1224 while(mpiCompAbs(r, p) >= 0)
Sergunb 0:8918a71cdbe9 1225 {
Sergunb 0:8918a71cdbe9 1226 if(mpiCompAbs(r, &c) >= 0)
Sergunb 0:8918a71cdbe9 1227 {
Sergunb 0:8918a71cdbe9 1228 MPI_CHECK(mpiSubAbs(r, r, &c));
Sergunb 0:8918a71cdbe9 1229 }
Sergunb 0:8918a71cdbe9 1230
Sergunb 0:8918a71cdbe9 1231 MPI_CHECK(mpiShiftRight(&c, 1));
Sergunb 0:8918a71cdbe9 1232 }
Sergunb 0:8918a71cdbe9 1233 }
Sergunb 0:8918a71cdbe9 1234
Sergunb 0:8918a71cdbe9 1235 if(sign < 0)
Sergunb 0:8918a71cdbe9 1236 {
Sergunb 0:8918a71cdbe9 1237 MPI_CHECK(mpiSubAbs(r, p, r));
Sergunb 0:8918a71cdbe9 1238 }
Sergunb 0:8918a71cdbe9 1239
Sergunb 0:8918a71cdbe9 1240 end:
Sergunb 0:8918a71cdbe9 1241 //Release previously allocated memory
Sergunb 0:8918a71cdbe9 1242 mpiFree(&c);
Sergunb 0:8918a71cdbe9 1243
Sergunb 0:8918a71cdbe9 1244 //Return status code
Sergunb 0:8918a71cdbe9 1245 return error;
Sergunb 0:8918a71cdbe9 1246 }
Sergunb 0:8918a71cdbe9 1247
Sergunb 0:8918a71cdbe9 1248
Sergunb 0:8918a71cdbe9 1249
Sergunb 0:8918a71cdbe9 1250 /**
Sergunb 0:8918a71cdbe9 1251 * @brief Modular addition
Sergunb 0:8918a71cdbe9 1252 * @param[out] r Resulting integer R = A + B mod P
Sergunb 0:8918a71cdbe9 1253 * @param[in] a The first operand A
Sergunb 0:8918a71cdbe9 1254 * @param[in] b The second operand B
Sergunb 0:8918a71cdbe9 1255 * @param[in] p The modulus P
Sergunb 0:8918a71cdbe9 1256 * @return Error code
Sergunb 0:8918a71cdbe9 1257 **/
Sergunb 0:8918a71cdbe9 1258
Sergunb 0:8918a71cdbe9 1259 error_t mpiAddMod(Mpi *r, const Mpi *a, const Mpi *b, const Mpi *p)
Sergunb 0:8918a71cdbe9 1260 {
Sergunb 0:8918a71cdbe9 1261 error_t error;
Sergunb 0:8918a71cdbe9 1262
Sergunb 0:8918a71cdbe9 1263 //Perform modular addition
Sergunb 0:8918a71cdbe9 1264 MPI_CHECK(mpiAdd(r, a, b));
Sergunb 0:8918a71cdbe9 1265 MPI_CHECK(mpiMod(r, r, p));
Sergunb 0:8918a71cdbe9 1266
Sergunb 0:8918a71cdbe9 1267 end:
Sergunb 0:8918a71cdbe9 1268 //Return status code
Sergunb 0:8918a71cdbe9 1269 return error;
Sergunb 0:8918a71cdbe9 1270 }
Sergunb 0:8918a71cdbe9 1271
Sergunb 0:8918a71cdbe9 1272
Sergunb 0:8918a71cdbe9 1273 /**
Sergunb 0:8918a71cdbe9 1274 * @brief Modular subtraction
Sergunb 0:8918a71cdbe9 1275 * @param[out] r Resulting integer R = A - B mod P
Sergunb 0:8918a71cdbe9 1276 * @param[in] a The first operand A
Sergunb 0:8918a71cdbe9 1277 * @param[in] b The second operand B
Sergunb 0:8918a71cdbe9 1278 * @param[in] p The modulus P
Sergunb 0:8918a71cdbe9 1279 * @return Error code
Sergunb 0:8918a71cdbe9 1280 **/
Sergunb 0:8918a71cdbe9 1281
Sergunb 0:8918a71cdbe9 1282 error_t mpiSubMod(Mpi *r, const Mpi *a, const Mpi *b, const Mpi *p)
Sergunb 0:8918a71cdbe9 1283 {
Sergunb 0:8918a71cdbe9 1284 error_t error;
Sergunb 0:8918a71cdbe9 1285
Sergunb 0:8918a71cdbe9 1286 //Perform modular subtraction
Sergunb 0:8918a71cdbe9 1287 MPI_CHECK(mpiSub(r, a, b));
Sergunb 0:8918a71cdbe9 1288 MPI_CHECK(mpiMod(r, r, p));
Sergunb 0:8918a71cdbe9 1289
Sergunb 0:8918a71cdbe9 1290 end:
Sergunb 0:8918a71cdbe9 1291 //Return status code
Sergunb 0:8918a71cdbe9 1292 return error;
Sergunb 0:8918a71cdbe9 1293 }
Sergunb 0:8918a71cdbe9 1294
Sergunb 0:8918a71cdbe9 1295
Sergunb 0:8918a71cdbe9 1296 /**
Sergunb 0:8918a71cdbe9 1297 * @brief Modular multiplication
Sergunb 0:8918a71cdbe9 1298 * @param[out] r Resulting integer R = A * B mod P
Sergunb 0:8918a71cdbe9 1299 * @param[in] a The first operand A
Sergunb 0:8918a71cdbe9 1300 * @param[in] b The second operand B
Sergunb 0:8918a71cdbe9 1301 * @param[in] p The modulus P
Sergunb 0:8918a71cdbe9 1302 * @return Error code
Sergunb 0:8918a71cdbe9 1303 **/
Sergunb 0:8918a71cdbe9 1304
Sergunb 0:8918a71cdbe9 1305 error_t mpiMulMod(Mpi *r, const Mpi *a, const Mpi *b, const Mpi *p)
Sergunb 0:8918a71cdbe9 1306 {
Sergunb 0:8918a71cdbe9 1307 error_t error;
Sergunb 0:8918a71cdbe9 1308
Sergunb 0:8918a71cdbe9 1309 //Perform modular multiplication
Sergunb 0:8918a71cdbe9 1310 MPI_CHECK(mpiMul(r, a, b));
Sergunb 0:8918a71cdbe9 1311 MPI_CHECK(mpiMod(r, r, p));
Sergunb 0:8918a71cdbe9 1312
Sergunb 0:8918a71cdbe9 1313 end:
Sergunb 0:8918a71cdbe9 1314 //Return status code
Sergunb 0:8918a71cdbe9 1315 return error;
Sergunb 0:8918a71cdbe9 1316 }
Sergunb 0:8918a71cdbe9 1317
Sergunb 0:8918a71cdbe9 1318
Sergunb 0:8918a71cdbe9 1319 /**
Sergunb 0:8918a71cdbe9 1320 * @brief Modular inverse
Sergunb 0:8918a71cdbe9 1321 * @param[out] r Resulting integer R = A^-1 mod P
Sergunb 0:8918a71cdbe9 1322 * @param[in] a The multiple precision integer A
Sergunb 0:8918a71cdbe9 1323 * @param[in] p The modulus P
Sergunb 0:8918a71cdbe9 1324 * @return Error code
Sergunb 0:8918a71cdbe9 1325 **/
Sergunb 0:8918a71cdbe9 1326
Sergunb 0:8918a71cdbe9 1327 error_t mpiInvMod(Mpi *r, const Mpi *a, const Mpi *p)
Sergunb 0:8918a71cdbe9 1328 {
Sergunb 0:8918a71cdbe9 1329 error_t error;
Sergunb 0:8918a71cdbe9 1330 Mpi b;
Sergunb 0:8918a71cdbe9 1331 Mpi c;
Sergunb 0:8918a71cdbe9 1332 Mpi q0;
Sergunb 0:8918a71cdbe9 1333 Mpi r0;
Sergunb 0:8918a71cdbe9 1334 Mpi t;
Sergunb 0:8918a71cdbe9 1335 Mpi u;
Sergunb 0:8918a71cdbe9 1336 Mpi v;
Sergunb 0:8918a71cdbe9 1337
Sergunb 0:8918a71cdbe9 1338 //Initialize multiple precision integers
Sergunb 0:8918a71cdbe9 1339 mpiInit(&b);
Sergunb 0:8918a71cdbe9 1340 mpiInit(&c);
Sergunb 0:8918a71cdbe9 1341 mpiInit(&q0);
Sergunb 0:8918a71cdbe9 1342 mpiInit(&r0);
Sergunb 0:8918a71cdbe9 1343 mpiInit(&t);
Sergunb 0:8918a71cdbe9 1344 mpiInit(&u);
Sergunb 0:8918a71cdbe9 1345 mpiInit(&v);
Sergunb 0:8918a71cdbe9 1346
Sergunb 0:8918a71cdbe9 1347 MPI_CHECK(mpiCopy(&b, p));
Sergunb 0:8918a71cdbe9 1348 MPI_CHECK(mpiCopy(&c, a));
Sergunb 0:8918a71cdbe9 1349 MPI_CHECK(mpiSetValue(&u, 0));
Sergunb 0:8918a71cdbe9 1350 MPI_CHECK(mpiSetValue(&v, 1));
Sergunb 0:8918a71cdbe9 1351
Sergunb 0:8918a71cdbe9 1352 while(mpiCompInt(&c, 0) > 0)
Sergunb 0:8918a71cdbe9 1353 {
Sergunb 0:8918a71cdbe9 1354 MPI_CHECK(mpiDiv(&q0, &r0, &b, &c));
Sergunb 0:8918a71cdbe9 1355
Sergunb 0:8918a71cdbe9 1356 MPI_CHECK(mpiCopy(&b, &c));
Sergunb 0:8918a71cdbe9 1357 MPI_CHECK(mpiCopy(&c, &r0));
Sergunb 0:8918a71cdbe9 1358
Sergunb 0:8918a71cdbe9 1359 MPI_CHECK(mpiCopy(&t, &v));
Sergunb 0:8918a71cdbe9 1360 MPI_CHECK(mpiMul(&q0, &q0, &v));
Sergunb 0:8918a71cdbe9 1361 MPI_CHECK(mpiSub(&v, &u, &q0));
Sergunb 0:8918a71cdbe9 1362 MPI_CHECK(mpiCopy(&u, &t));
Sergunb 0:8918a71cdbe9 1363 }
Sergunb 0:8918a71cdbe9 1364
Sergunb 0:8918a71cdbe9 1365 if(mpiCompInt(&b, 1))
Sergunb 0:8918a71cdbe9 1366 {
Sergunb 0:8918a71cdbe9 1367 MPI_CHECK(ERROR_FAILURE);
Sergunb 0:8918a71cdbe9 1368 }
Sergunb 0:8918a71cdbe9 1369
Sergunb 0:8918a71cdbe9 1370 if(mpiCompInt(&u, 0) > 0)
Sergunb 0:8918a71cdbe9 1371 {
Sergunb 0:8918a71cdbe9 1372 MPI_CHECK(mpiCopy(r, &u));
Sergunb 0:8918a71cdbe9 1373 }
Sergunb 0:8918a71cdbe9 1374 else
Sergunb 0:8918a71cdbe9 1375 {
Sergunb 0:8918a71cdbe9 1376 MPI_CHECK(mpiAdd(r, &u, p));
Sergunb 0:8918a71cdbe9 1377 }
Sergunb 0:8918a71cdbe9 1378
Sergunb 0:8918a71cdbe9 1379 end:
Sergunb 0:8918a71cdbe9 1380 //Release previously allocated memory
Sergunb 0:8918a71cdbe9 1381 mpiFree(&b);
Sergunb 0:8918a71cdbe9 1382 mpiFree(&c);
Sergunb 0:8918a71cdbe9 1383 mpiFree(&q0);
Sergunb 0:8918a71cdbe9 1384 mpiFree(&r0);
Sergunb 0:8918a71cdbe9 1385 mpiFree(&t);
Sergunb 0:8918a71cdbe9 1386 mpiFree(&u);
Sergunb 0:8918a71cdbe9 1387 mpiFree(&v);
Sergunb 0:8918a71cdbe9 1388
Sergunb 0:8918a71cdbe9 1389 //Return status code
Sergunb 0:8918a71cdbe9 1390 return error;
Sergunb 0:8918a71cdbe9 1391 }
Sergunb 0:8918a71cdbe9 1392
Sergunb 0:8918a71cdbe9 1393
Sergunb 0:8918a71cdbe9 1394 /**
Sergunb 0:8918a71cdbe9 1395 * @brief Modular exponentiation
Sergunb 0:8918a71cdbe9 1396 * @param[out] r Resulting integer R = A ^ E mod P
Sergunb 0:8918a71cdbe9 1397 * @param[in] a Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 1398 * @param[in] e Exponent
Sergunb 0:8918a71cdbe9 1399 * @param[in] p Modulus
Sergunb 0:8918a71cdbe9 1400 * @return Error code
Sergunb 0:8918a71cdbe9 1401 **/
Sergunb 0:8918a71cdbe9 1402
Sergunb 0:8918a71cdbe9 1403 error_t mpiExpMod(Mpi *r, const Mpi *a, const Mpi *e, const Mpi *p)
Sergunb 0:8918a71cdbe9 1404 {
Sergunb 0:8918a71cdbe9 1405 error_t error;
Sergunb 0:8918a71cdbe9 1406 int_t i;
Sergunb 0:8918a71cdbe9 1407 int_t j;
Sergunb 0:8918a71cdbe9 1408 int_t n;
Sergunb 0:8918a71cdbe9 1409 uint_t d;
Sergunb 0:8918a71cdbe9 1410 uint_t k;
Sergunb 0:8918a71cdbe9 1411 uint_t u;
Sergunb 0:8918a71cdbe9 1412 Mpi b;
Sergunb 0:8918a71cdbe9 1413 Mpi c2;
Sergunb 0:8918a71cdbe9 1414 Mpi t;
Sergunb 0:8918a71cdbe9 1415 Mpi s[8];
Sergunb 0:8918a71cdbe9 1416
Sergunb 0:8918a71cdbe9 1417 //Initialize multiple precision integers
Sergunb 0:8918a71cdbe9 1418 mpiInit(&b);
Sergunb 0:8918a71cdbe9 1419 mpiInit(&c2);
Sergunb 0:8918a71cdbe9 1420 mpiInit(&t);
Sergunb 0:8918a71cdbe9 1421
Sergunb 0:8918a71cdbe9 1422 //Initialize precomputed values
Sergunb 0:8918a71cdbe9 1423 for(i = 0; i < arraysize(s); i++)
Sergunb 0:8918a71cdbe9 1424 mpiInit(&s[i]);
Sergunb 0:8918a71cdbe9 1425
Sergunb 0:8918a71cdbe9 1426 //Very small exponents are often selected with low Hamming weight.
Sergunb 0:8918a71cdbe9 1427 //The sliding window mechanism should be disabled in that case
Sergunb 0:8918a71cdbe9 1428 d = (mpiGetBitLength(e) <= 32) ? 1 : 4;
Sergunb 0:8918a71cdbe9 1429
Sergunb 0:8918a71cdbe9 1430 //Even modulus?
Sergunb 0:8918a71cdbe9 1431 if(mpiIsEven(p))
Sergunb 0:8918a71cdbe9 1432 {
Sergunb 0:8918a71cdbe9 1433 //Let B = A^2
Sergunb 0:8918a71cdbe9 1434 MPI_CHECK(mpiMulMod(&b, a, a, p));
Sergunb 0:8918a71cdbe9 1435 //Let S[0] = A
Sergunb 0:8918a71cdbe9 1436 MPI_CHECK(mpiCopy(&s[0], a));
Sergunb 0:8918a71cdbe9 1437
Sergunb 0:8918a71cdbe9 1438 //Precompute S[i] = A^(2 * i + 1)
Sergunb 0:8918a71cdbe9 1439 for(i = 1; i < (1 << (d - 1)); i++)
Sergunb 0:8918a71cdbe9 1440 {
Sergunb 0:8918a71cdbe9 1441 MPI_CHECK(mpiMulMod(&s[i], &s[i - 1], &b, p));
Sergunb 0:8918a71cdbe9 1442 }
Sergunb 0:8918a71cdbe9 1443
Sergunb 0:8918a71cdbe9 1444 //Let R = 1
Sergunb 0:8918a71cdbe9 1445 MPI_CHECK(mpiSetValue(r, 1));
Sergunb 0:8918a71cdbe9 1446
Sergunb 0:8918a71cdbe9 1447 //The exponent is processed in a right-to-left fashion
Sergunb 0:8918a71cdbe9 1448 i = mpiGetBitLength(e) - 1;
Sergunb 0:8918a71cdbe9 1449
Sergunb 0:8918a71cdbe9 1450 //Perform sliding window exponentiation
Sergunb 0:8918a71cdbe9 1451 while(i >= 0)
Sergunb 0:8918a71cdbe9 1452 {
Sergunb 0:8918a71cdbe9 1453 //The sliding window exponentiation algorithm decomposes E
Sergunb 0:8918a71cdbe9 1454 //into zero and nonzero windows
Sergunb 0:8918a71cdbe9 1455 if(!mpiGetBitValue(e, i))
Sergunb 0:8918a71cdbe9 1456 {
Sergunb 0:8918a71cdbe9 1457 //Compute R = R^2
Sergunb 0:8918a71cdbe9 1458 MPI_CHECK(mpiMulMod(r, r, r, p));
Sergunb 0:8918a71cdbe9 1459 //Next bit to be processed
Sergunb 0:8918a71cdbe9 1460 i--;
Sergunb 0:8918a71cdbe9 1461 }
Sergunb 0:8918a71cdbe9 1462 else
Sergunb 0:8918a71cdbe9 1463 {
Sergunb 0:8918a71cdbe9 1464 //Find the longest window
Sergunb 0:8918a71cdbe9 1465 n = MAX(i - d + 1, 0);
Sergunb 0:8918a71cdbe9 1466
Sergunb 0:8918a71cdbe9 1467 //The least significant bit of the window must be equal to 1
Sergunb 0:8918a71cdbe9 1468 while(!mpiGetBitValue(e, n)) n++;
Sergunb 0:8918a71cdbe9 1469
Sergunb 0:8918a71cdbe9 1470 //The algorithm processes more than one bit per iteration
Sergunb 0:8918a71cdbe9 1471 for(u = 0, j = i; j >= n; j--)
Sergunb 0:8918a71cdbe9 1472 {
Sergunb 0:8918a71cdbe9 1473 //Compute R = R^2
Sergunb 0:8918a71cdbe9 1474 MPI_CHECK(mpiMulMod(r, r, r, p));
Sergunb 0:8918a71cdbe9 1475 //Compute the relevant index to be used in the precomputed table
Sergunb 0:8918a71cdbe9 1476 u = (u << 1) | mpiGetBitValue(e, j);
Sergunb 0:8918a71cdbe9 1477 }
Sergunb 0:8918a71cdbe9 1478
Sergunb 0:8918a71cdbe9 1479 //Perform a single multiplication per iteration
Sergunb 0:8918a71cdbe9 1480 MPI_CHECK(mpiMulMod(r, r, &s[u >> 1], p));
Sergunb 0:8918a71cdbe9 1481 //Next bit to be processed
Sergunb 0:8918a71cdbe9 1482 i = n - 1;
Sergunb 0:8918a71cdbe9 1483 }
Sergunb 0:8918a71cdbe9 1484 }
Sergunb 0:8918a71cdbe9 1485 }
Sergunb 0:8918a71cdbe9 1486 else
Sergunb 0:8918a71cdbe9 1487 {
Sergunb 0:8918a71cdbe9 1488 //Compute the smaller C = (2^32)^k such as C > P
Sergunb 0:8918a71cdbe9 1489 k = mpiGetLength(p);
Sergunb 0:8918a71cdbe9 1490
Sergunb 0:8918a71cdbe9 1491 //Compute C^2 mod P
Sergunb 0:8918a71cdbe9 1492 MPI_CHECK(mpiSetValue(&c2, 1));
Sergunb 0:8918a71cdbe9 1493 MPI_CHECK(mpiShiftLeft(&c2, 2 * k * (MPI_INT_SIZE * 8)));
Sergunb 0:8918a71cdbe9 1494 MPI_CHECK(mpiMod(&c2, &c2, p));
Sergunb 0:8918a71cdbe9 1495
Sergunb 0:8918a71cdbe9 1496 //Let B = A * C mod P
Sergunb 0:8918a71cdbe9 1497 if(mpiComp(a, p) >= 0)
Sergunb 0:8918a71cdbe9 1498 {
Sergunb 0:8918a71cdbe9 1499 MPI_CHECK(mpiMod(&b, a, p));
Sergunb 0:8918a71cdbe9 1500 MPI_CHECK(mpiMontgomeryMul(&b, &b, &c2, k, p, &t));
Sergunb 0:8918a71cdbe9 1501 }
Sergunb 0:8918a71cdbe9 1502 else
Sergunb 0:8918a71cdbe9 1503 {
Sergunb 0:8918a71cdbe9 1504 MPI_CHECK(mpiMontgomeryMul(&b, a, &c2, k, p, &t));
Sergunb 0:8918a71cdbe9 1505 }
Sergunb 0:8918a71cdbe9 1506
Sergunb 0:8918a71cdbe9 1507 //Let R = B^2 * C^-1 mod P
Sergunb 0:8918a71cdbe9 1508 MPI_CHECK(mpiMontgomeryMul(r, &b, &b, k, p, &t));
Sergunb 0:8918a71cdbe9 1509 //Let S[0] = B
Sergunb 0:8918a71cdbe9 1510 MPI_CHECK(mpiCopy(&s[0], &b));
Sergunb 0:8918a71cdbe9 1511
Sergunb 0:8918a71cdbe9 1512 //Precompute S[i] = B^(2 * i + 1) * C^-1 mod P
Sergunb 0:8918a71cdbe9 1513 for(i = 1; i < (1 << (d - 1)); i++)
Sergunb 0:8918a71cdbe9 1514 {
Sergunb 0:8918a71cdbe9 1515 MPI_CHECK(mpiMontgomeryMul(&s[i], &s[i - 1], r, k, p, &t));
Sergunb 0:8918a71cdbe9 1516 }
Sergunb 0:8918a71cdbe9 1517
Sergunb 0:8918a71cdbe9 1518 //Let R = C mod P
Sergunb 0:8918a71cdbe9 1519 MPI_CHECK(mpiCopy(r, &c2));
Sergunb 0:8918a71cdbe9 1520 MPI_CHECK(mpiMontgomeryRed(r, r, k, p, &t));
Sergunb 0:8918a71cdbe9 1521
Sergunb 0:8918a71cdbe9 1522 //The exponent is processed in a right-to-left fashion
Sergunb 0:8918a71cdbe9 1523 i = mpiGetBitLength(e) - 1;
Sergunb 0:8918a71cdbe9 1524
Sergunb 0:8918a71cdbe9 1525 //Perform sliding window exponentiation
Sergunb 0:8918a71cdbe9 1526 while(i >= 0)
Sergunb 0:8918a71cdbe9 1527 {
Sergunb 0:8918a71cdbe9 1528 //The sliding window exponentiation algorithm decomposes E
Sergunb 0:8918a71cdbe9 1529 //into zero and nonzero windows
Sergunb 0:8918a71cdbe9 1530 if(!mpiGetBitValue(e, i))
Sergunb 0:8918a71cdbe9 1531 {
Sergunb 0:8918a71cdbe9 1532 //Compute R = R^2 * C^-1 mod P
Sergunb 0:8918a71cdbe9 1533 MPI_CHECK(mpiMontgomeryMul(r, r, r, k, p, &t));
Sergunb 0:8918a71cdbe9 1534 //Next bit to be processed
Sergunb 0:8918a71cdbe9 1535 i--;
Sergunb 0:8918a71cdbe9 1536 }
Sergunb 0:8918a71cdbe9 1537 else
Sergunb 0:8918a71cdbe9 1538 {
Sergunb 0:8918a71cdbe9 1539 //Find the longest window
Sergunb 0:8918a71cdbe9 1540 n = MAX(i - d + 1, 0);
Sergunb 0:8918a71cdbe9 1541
Sergunb 0:8918a71cdbe9 1542 //The least significant bit of the window must be equal to 1
Sergunb 0:8918a71cdbe9 1543 while(!mpiGetBitValue(e, n)) n++;
Sergunb 0:8918a71cdbe9 1544
Sergunb 0:8918a71cdbe9 1545 //The algorithm processes more than one bit per iteration
Sergunb 0:8918a71cdbe9 1546 for(u = 0, j = i; j >= n; j--)
Sergunb 0:8918a71cdbe9 1547 {
Sergunb 0:8918a71cdbe9 1548 //Compute R = R^2 * C^-1 mod P
Sergunb 0:8918a71cdbe9 1549 MPI_CHECK(mpiMontgomeryMul(r, r, r, k, p, &t));
Sergunb 0:8918a71cdbe9 1550 //Compute the relevant index to be used in the precomputed table
Sergunb 0:8918a71cdbe9 1551 u = (u << 1) | mpiGetBitValue(e, j);
Sergunb 0:8918a71cdbe9 1552 }
Sergunb 0:8918a71cdbe9 1553
Sergunb 0:8918a71cdbe9 1554 //Compute R = R * T[u/2] * C^-1 mod P
Sergunb 0:8918a71cdbe9 1555 MPI_CHECK(mpiMontgomeryMul(r, r, &s[u >> 1], k, p, &t));
Sergunb 0:8918a71cdbe9 1556 //Next bit to be processed
Sergunb 0:8918a71cdbe9 1557 i = n - 1;
Sergunb 0:8918a71cdbe9 1558 }
Sergunb 0:8918a71cdbe9 1559 }
Sergunb 0:8918a71cdbe9 1560
Sergunb 0:8918a71cdbe9 1561 //Compute R = R * C^-1 mod P
Sergunb 0:8918a71cdbe9 1562 MPI_CHECK(mpiMontgomeryRed(r, r, k, p, &t));
Sergunb 0:8918a71cdbe9 1563 }
Sergunb 0:8918a71cdbe9 1564
Sergunb 0:8918a71cdbe9 1565 end:
Sergunb 0:8918a71cdbe9 1566 //Release multiple precision integers
Sergunb 0:8918a71cdbe9 1567 mpiFree(&b);
Sergunb 0:8918a71cdbe9 1568 mpiFree(&c2);
Sergunb 0:8918a71cdbe9 1569 mpiFree(&t);
Sergunb 0:8918a71cdbe9 1570
Sergunb 0:8918a71cdbe9 1571 //Release precomputed values
Sergunb 0:8918a71cdbe9 1572 for(i = 0; i < arraysize(s); i++)
Sergunb 0:8918a71cdbe9 1573 mpiFree(&s[i]);
Sergunb 0:8918a71cdbe9 1574
Sergunb 0:8918a71cdbe9 1575 //Return status code
Sergunb 0:8918a71cdbe9 1576 return error;
Sergunb 0:8918a71cdbe9 1577 }
Sergunb 0:8918a71cdbe9 1578
Sergunb 0:8918a71cdbe9 1579
Sergunb 0:8918a71cdbe9 1580 /**
Sergunb 0:8918a71cdbe9 1581 * @brief Montgomery multiplication
Sergunb 0:8918a71cdbe9 1582 * @param[out] r Resulting integer R = A * B / 2^k mod P
Sergunb 0:8918a71cdbe9 1583 * @param[in] a An integer A such as 0 <= A < 2^k
Sergunb 0:8918a71cdbe9 1584 * @param[in] b An integer B such as 0 <= B < 2^k
Sergunb 0:8918a71cdbe9 1585 * @param[in] k An integer k such as P < 2^k
Sergunb 0:8918a71cdbe9 1586 * @param[in] p Modulus P
Sergunb 0:8918a71cdbe9 1587 * @param[in] t An preallocated integer T (for internal operation)
Sergunb 0:8918a71cdbe9 1588 * @return Error code
Sergunb 0:8918a71cdbe9 1589 **/
Sergunb 0:8918a71cdbe9 1590
Sergunb 0:8918a71cdbe9 1591 error_t mpiMontgomeryMul(Mpi *r, const Mpi *a, const Mpi *b, uint_t k, const Mpi *p, Mpi *t)
Sergunb 0:8918a71cdbe9 1592 {
Sergunb 0:8918a71cdbe9 1593 error_t error;
Sergunb 0:8918a71cdbe9 1594 uint_t i;
Sergunb 0:8918a71cdbe9 1595 uint_t m;
Sergunb 0:8918a71cdbe9 1596 uint_t n;
Sergunb 0:8918a71cdbe9 1597 uint_t q;
Sergunb 0:8918a71cdbe9 1598
Sergunb 0:8918a71cdbe9 1599 //Use Newton's method to compute the inverse of P[0] mod 2^32
Sergunb 0:8918a71cdbe9 1600 for(m = 2 - p->data[0], i = 0; i < 4; i++)
Sergunb 0:8918a71cdbe9 1601 m = m * (2 - m * p->data[0]);
Sergunb 0:8918a71cdbe9 1602
Sergunb 0:8918a71cdbe9 1603 //Precompute -1/P[0] mod 2^32;
Sergunb 0:8918a71cdbe9 1604 m = ~m + 1;
Sergunb 0:8918a71cdbe9 1605
Sergunb 0:8918a71cdbe9 1606 //We assume that B is always less than 2^k
Sergunb 0:8918a71cdbe9 1607 n = MIN(b->size, k);
Sergunb 0:8918a71cdbe9 1608
Sergunb 0:8918a71cdbe9 1609 //Make sure T is large enough
Sergunb 0:8918a71cdbe9 1610 MPI_CHECK(mpiGrow(t, 2 * k + 1));
Sergunb 0:8918a71cdbe9 1611 //Let T = 0
Sergunb 0:8918a71cdbe9 1612 MPI_CHECK(mpiSetValue(t, 0));
Sergunb 0:8918a71cdbe9 1613
Sergunb 0:8918a71cdbe9 1614 //Perform Montgomery multiplication
Sergunb 0:8918a71cdbe9 1615 for(i = 0; i < k; i++)
Sergunb 0:8918a71cdbe9 1616 {
Sergunb 0:8918a71cdbe9 1617 //Check current index
Sergunb 0:8918a71cdbe9 1618 if(i < a->size)
Sergunb 0:8918a71cdbe9 1619 {
Sergunb 0:8918a71cdbe9 1620 //Compute q = ((T[i] + A[i] * B[0]) * m) mod 2^32
Sergunb 0:8918a71cdbe9 1621 q = (t->data[i] + a->data[i] * b->data[0]) * m;
Sergunb 0:8918a71cdbe9 1622 //Compute T = T + A[i] * B
Sergunb 0:8918a71cdbe9 1623 mpiMulAccCore(t->data + i, b->data, n, a->data[i]);
Sergunb 0:8918a71cdbe9 1624 }
Sergunb 0:8918a71cdbe9 1625 else
Sergunb 0:8918a71cdbe9 1626 {
Sergunb 0:8918a71cdbe9 1627 //Compute q = (T[i] * m) mod 2^32
Sergunb 0:8918a71cdbe9 1628 q = t->data[i] * m;
Sergunb 0:8918a71cdbe9 1629 }
Sergunb 0:8918a71cdbe9 1630
Sergunb 0:8918a71cdbe9 1631 //Compute T = T + q * P
Sergunb 0:8918a71cdbe9 1632 mpiMulAccCore(t->data + i, p->data, k, q);
Sergunb 0:8918a71cdbe9 1633 }
Sergunb 0:8918a71cdbe9 1634
Sergunb 0:8918a71cdbe9 1635 //Compute R = T / 2^(32 * k)
Sergunb 0:8918a71cdbe9 1636 MPI_CHECK(mpiShiftRight(t, k * (MPI_INT_SIZE * 8)));
Sergunb 0:8918a71cdbe9 1637 MPI_CHECK(mpiCopy(r, t));
Sergunb 0:8918a71cdbe9 1638
Sergunb 0:8918a71cdbe9 1639 //A final subtraction is required
Sergunb 0:8918a71cdbe9 1640 if(mpiComp(r, p) >= 0)
Sergunb 0:8918a71cdbe9 1641 {
Sergunb 0:8918a71cdbe9 1642 MPI_CHECK(mpiSub(r, r, p));
Sergunb 0:8918a71cdbe9 1643 }
Sergunb 0:8918a71cdbe9 1644
Sergunb 0:8918a71cdbe9 1645 end:
Sergunb 0:8918a71cdbe9 1646 //Return status code
Sergunb 0:8918a71cdbe9 1647 return error;
Sergunb 0:8918a71cdbe9 1648 }
Sergunb 0:8918a71cdbe9 1649
Sergunb 0:8918a71cdbe9 1650
Sergunb 0:8918a71cdbe9 1651 /**
Sergunb 0:8918a71cdbe9 1652 * @brief Montgomery reduction
Sergunb 0:8918a71cdbe9 1653 * @param[out] r Resulting integer R = A / 2^k mod P
Sergunb 0:8918a71cdbe9 1654 * @param[in] a An integer A such as 0 <= A < 2^k
Sergunb 0:8918a71cdbe9 1655 * @param[in] k An integer k such as P < 2^k
Sergunb 0:8918a71cdbe9 1656 * @param[in] p Modulus P
Sergunb 0:8918a71cdbe9 1657 * @param[in] t An preallocated integer T (for internal operation)
Sergunb 0:8918a71cdbe9 1658 * @return Error code
Sergunb 0:8918a71cdbe9 1659 **/
Sergunb 0:8918a71cdbe9 1660
Sergunb 0:8918a71cdbe9 1661 error_t mpiMontgomeryRed(Mpi *r, const Mpi *a, uint_t k, const Mpi *p, Mpi *t)
Sergunb 0:8918a71cdbe9 1662 {
Sergunb 0:8918a71cdbe9 1663 uint_t value;
Sergunb 0:8918a71cdbe9 1664 Mpi b;
Sergunb 0:8918a71cdbe9 1665
Sergunb 0:8918a71cdbe9 1666 //Let B = 1
Sergunb 0:8918a71cdbe9 1667 value = 1;
Sergunb 0:8918a71cdbe9 1668 b.sign = 1;
Sergunb 0:8918a71cdbe9 1669 b.size = 1;
Sergunb 0:8918a71cdbe9 1670 b.data = &value;
Sergunb 0:8918a71cdbe9 1671
Sergunb 0:8918a71cdbe9 1672 //Compute R = A / 2^k mod P
Sergunb 0:8918a71cdbe9 1673 return mpiMontgomeryMul(r, a, &b, k, p, t);
Sergunb 0:8918a71cdbe9 1674 }
Sergunb 0:8918a71cdbe9 1675
Sergunb 0:8918a71cdbe9 1676
Sergunb 0:8918a71cdbe9 1677 #if (MPI_ASM_SUPPORT == DISABLED)
Sergunb 0:8918a71cdbe9 1678
Sergunb 0:8918a71cdbe9 1679 /**
Sergunb 0:8918a71cdbe9 1680 * @brief Multiply-accumulate operation
Sergunb 0:8918a71cdbe9 1681 * @param[out] r Resulting integer
Sergunb 0:8918a71cdbe9 1682 * @param[in] a First operand A
Sergunb 0:8918a71cdbe9 1683 * @param[in] m Size of A in words
Sergunb 0:8918a71cdbe9 1684 * @param[in] b Second operand B
Sergunb 0:8918a71cdbe9 1685 **/
Sergunb 0:8918a71cdbe9 1686
Sergunb 0:8918a71cdbe9 1687 void mpiMulAccCore(uint_t *r, const uint_t *a, int_t m, const uint_t b)
Sergunb 0:8918a71cdbe9 1688 {
Sergunb 0:8918a71cdbe9 1689 int_t i;
Sergunb 0:8918a71cdbe9 1690 uint32_t c;
Sergunb 0:8918a71cdbe9 1691 uint32_t u;
Sergunb 0:8918a71cdbe9 1692 uint32_t v;
Sergunb 0:8918a71cdbe9 1693 uint64_t p;
Sergunb 0:8918a71cdbe9 1694
Sergunb 0:8918a71cdbe9 1695 //Clear variables
Sergunb 0:8918a71cdbe9 1696 c = 0;
Sergunb 0:8918a71cdbe9 1697 u = 0;
Sergunb 0:8918a71cdbe9 1698 v = 0;
Sergunb 0:8918a71cdbe9 1699
Sergunb 0:8918a71cdbe9 1700 //Perform multiplication
Sergunb 0:8918a71cdbe9 1701 for(i = 0; i < m; i++)
Sergunb 0:8918a71cdbe9 1702 {
Sergunb 0:8918a71cdbe9 1703 p = (uint64_t) a[i] * b;
Sergunb 0:8918a71cdbe9 1704 u = (uint32_t) p;
Sergunb 0:8918a71cdbe9 1705 v = (uint32_t) (p >> 32);
Sergunb 0:8918a71cdbe9 1706
Sergunb 0:8918a71cdbe9 1707 u += c;
Sergunb 0:8918a71cdbe9 1708 if(u < c) v++;
Sergunb 0:8918a71cdbe9 1709
Sergunb 0:8918a71cdbe9 1710 u += r[i];
Sergunb 0:8918a71cdbe9 1711 if(u < r[i]) v++;
Sergunb 0:8918a71cdbe9 1712
Sergunb 0:8918a71cdbe9 1713 r[i] = u;
Sergunb 0:8918a71cdbe9 1714 c = v;
Sergunb 0:8918a71cdbe9 1715 }
Sergunb 0:8918a71cdbe9 1716
Sergunb 0:8918a71cdbe9 1717 //Propagate carry
Sergunb 0:8918a71cdbe9 1718 for(; c != 0; i++)
Sergunb 0:8918a71cdbe9 1719 {
Sergunb 0:8918a71cdbe9 1720 r[i] += c;
Sergunb 0:8918a71cdbe9 1721 c = (r[i] < c);
Sergunb 0:8918a71cdbe9 1722 }
Sergunb 0:8918a71cdbe9 1723 }
Sergunb 0:8918a71cdbe9 1724
Sergunb 0:8918a71cdbe9 1725 #endif
Sergunb 0:8918a71cdbe9 1726
Sergunb 0:8918a71cdbe9 1727
Sergunb 0:8918a71cdbe9 1728 /**
Sergunb 0:8918a71cdbe9 1729 * @brief Display the contents of a multiple precision integer
Sergunb 0:8918a71cdbe9 1730 * @param[in] stream Pointer to a FILE object that identifies an output stream
Sergunb 0:8918a71cdbe9 1731 * @param[in] prepend String to prepend to the left of each line
Sergunb 0:8918a71cdbe9 1732 * @param[in] a Pointer to a multiple precision integer
Sergunb 0:8918a71cdbe9 1733 **/
Sergunb 0:8918a71cdbe9 1734
Sergunb 0:8918a71cdbe9 1735 void mpiDump(FILE *stream, const char_t *prepend, const Mpi *a)
Sergunb 0:8918a71cdbe9 1736 {
Sergunb 0:8918a71cdbe9 1737 uint_t i;
Sergunb 0:8918a71cdbe9 1738
Sergunb 0:8918a71cdbe9 1739 //Process each word
Sergunb 0:8918a71cdbe9 1740 for(i = 0; i < a->size; i++)
Sergunb 0:8918a71cdbe9 1741 {
Sergunb 0:8918a71cdbe9 1742 //Beginning of a new line?
Sergunb 0:8918a71cdbe9 1743 if(i == 0 || ((a->size - i - 1) % 8) == 7)
Sergunb 0:8918a71cdbe9 1744 fprintf(stream, "%s", prepend);
Sergunb 0:8918a71cdbe9 1745
Sergunb 0:8918a71cdbe9 1746 //Display current data
Sergunb 0:8918a71cdbe9 1747 fprintf(stream, "%08X ", a->data[a->size - 1 - i]);
Sergunb 0:8918a71cdbe9 1748
Sergunb 0:8918a71cdbe9 1749 //End of current line?
Sergunb 0:8918a71cdbe9 1750 if(!((a->size - i - 1) % 8) || i == (a->size - 1))
Sergunb 0:8918a71cdbe9 1751 fprintf(stream, "\r\n");
Sergunb 0:8918a71cdbe9 1752 }
Sergunb 0:8918a71cdbe9 1753 }
Sergunb 0:8918a71cdbe9 1754
Sergunb 0:8918a71cdbe9 1755 #endif
Sergunb 0:8918a71cdbe9 1756