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