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