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