PolarSSL v1.3.1
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 substraction
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 substraction: 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 substractions.
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 substraction: 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 substraction: 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  bufsize = sizeof( t_uint ) << 3;
1523  }
1524 
1525  bufsize--;
1526 
1527  ei = (E->p[nblimbs] >> bufsize) & 1;
1528 
1529  /*
1530  * skip leading 0s
1531  */
1532  if( ei == 0 && state == 0 )
1533  continue;
1534 
1535  if( ei == 0 && state == 1 )
1536  {
1537  /*
1538  * out of window, square X
1539  */
1540  mpi_montmul( X, X, N, mm, &T );
1541  continue;
1542  }
1543 
1544  /*
1545  * add ei to current window
1546  */
1547  state = 2;
1548 
1549  nbits++;
1550  wbits |= (ei << (wsize - nbits));
1551 
1552  if( nbits == wsize )
1553  {
1554  /*
1555  * X = X^wsize R^-1 mod N
1556  */
1557  for( i = 0; i < wsize; i++ )
1558  mpi_montmul( X, X, N, mm, &T );
1559 
1560  /*
1561  * X = X * W[wbits] R^-1 mod N
1562  */
1563  mpi_montmul( X, &W[wbits], N, mm, &T );
1564 
1565  state--;
1566  nbits = 0;
1567  wbits = 0;
1568  }
1569  }
1570 
1571  /*
1572  * process the remaining bits
1573  */
1574  for( i = 0; i < nbits; i++ )
1575  {
1576  mpi_montmul( X, X, N, mm, &T );
1577 
1578  wbits <<= 1;
1579 
1580  if( (wbits & (one << wsize)) != 0 )
1581  mpi_montmul( X, &W[1], N, mm, &T );
1582  }
1583 
1584  /*
1585  * X = A^E * R * R^-1 mod N = A^E mod N
1586  */
1587  mpi_montred( X, N, mm, &T );
1588 
1589  if( neg )
1590  {
1591  X->s = -1;
1592  mpi_add_mpi( X, N, X );
1593  }
1594 
1595 cleanup:
1596 
1597  for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
1598  mpi_free( &W[i] );
1599 
1600  mpi_free( &W[1] ); mpi_free( &T ); mpi_free( &Apos );
1601 
1602  if( _RR == NULL )
1603  mpi_free( &RR );
1604 
1605  return( ret );
1606 }
1607 
1608 /*
1609  * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1610  */
1611 int mpi_gcd( mpi *G, const mpi *A, const mpi *B )
1612 {
1613  int ret;
1614  size_t lz, lzt;
1615  mpi TG, TA, TB;
1616 
1617  mpi_init( &TG ); mpi_init( &TA ); mpi_init( &TB );
1618 
1619  MPI_CHK( mpi_copy( &TA, A ) );
1620  MPI_CHK( mpi_copy( &TB, B ) );
1621 
1622  lz = mpi_lsb( &TA );
1623  lzt = mpi_lsb( &TB );
1624 
1625  if ( lzt < lz )
1626  lz = lzt;
1627 
1628  MPI_CHK( mpi_shift_r( &TA, lz ) );
1629  MPI_CHK( mpi_shift_r( &TB, lz ) );
1630 
1631  TA.s = TB.s = 1;
1632 
1633  while( mpi_cmp_int( &TA, 0 ) != 0 )
1634  {
1635  MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) );
1636  MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) );
1637 
1638  if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
1639  {
1640  MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
1641  MPI_CHK( mpi_shift_r( &TA, 1 ) );
1642  }
1643  else
1644  {
1645  MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
1646  MPI_CHK( mpi_shift_r( &TB, 1 ) );
1647  }
1648  }
1649 
1650  MPI_CHK( mpi_shift_l( &TB, lz ) );
1651  MPI_CHK( mpi_copy( G, &TB ) );
1652 
1653 cleanup:
1654 
1655  mpi_free( &TG ); mpi_free( &TA ); mpi_free( &TB );
1656 
1657  return( ret );
1658 }
1659 
1660 int mpi_fill_random( mpi *X, size_t size,
1661  int (*f_rng)(void *, unsigned char *, size_t),
1662  void *p_rng )
1663 {
1664  int ret;
1665 
1666  MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( size ) ) );
1667  MPI_CHK( mpi_lset( X, 0 ) );
1668 
1669  MPI_CHK( f_rng( p_rng, (unsigned char *) X->p, size ) );
1670 
1671 cleanup:
1672  return( ret );
1673 }
1674 
1675 /*
1676  * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1677  */
1678 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N )
1679 {
1680  int ret;
1681  mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1682 
1683  if( mpi_cmp_int( N, 0 ) <= 0 )
1685 
1686  mpi_init( &TA ); mpi_init( &TU ); mpi_init( &U1 ); mpi_init( &U2 );
1687  mpi_init( &G ); mpi_init( &TB ); mpi_init( &TV );
1688  mpi_init( &V1 ); mpi_init( &V2 );
1689 
1690  MPI_CHK( mpi_gcd( &G, A, N ) );
1691 
1692  if( mpi_cmp_int( &G, 1 ) != 0 )
1693  {
1695  goto cleanup;
1696  }
1697 
1698  MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
1699  MPI_CHK( mpi_copy( &TU, &TA ) );
1700  MPI_CHK( mpi_copy( &TB, N ) );
1701  MPI_CHK( mpi_copy( &TV, N ) );
1702 
1703  MPI_CHK( mpi_lset( &U1, 1 ) );
1704  MPI_CHK( mpi_lset( &U2, 0 ) );
1705  MPI_CHK( mpi_lset( &V1, 0 ) );
1706  MPI_CHK( mpi_lset( &V2, 1 ) );
1707 
1708  do
1709  {
1710  while( ( TU.p[0] & 1 ) == 0 )
1711  {
1712  MPI_CHK( mpi_shift_r( &TU, 1 ) );
1713 
1714  if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1715  {
1716  MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
1717  MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
1718  }
1719 
1720  MPI_CHK( mpi_shift_r( &U1, 1 ) );
1721  MPI_CHK( mpi_shift_r( &U2, 1 ) );
1722  }
1723 
1724  while( ( TV.p[0] & 1 ) == 0 )
1725  {
1726  MPI_CHK( mpi_shift_r( &TV, 1 ) );
1727 
1728  if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1729  {
1730  MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
1731  MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
1732  }
1733 
1734  MPI_CHK( mpi_shift_r( &V1, 1 ) );
1735  MPI_CHK( mpi_shift_r( &V2, 1 ) );
1736  }
1737 
1738  if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
1739  {
1740  MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
1741  MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
1742  MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
1743  }
1744  else
1745  {
1746  MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
1747  MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
1748  MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
1749  }
1750  }
1751  while( mpi_cmp_int( &TU, 0 ) != 0 );
1752 
1753  while( mpi_cmp_int( &V1, 0 ) < 0 )
1754  MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
1755 
1756  while( mpi_cmp_mpi( &V1, N ) >= 0 )
1757  MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
1758 
1759  MPI_CHK( mpi_copy( X, &V1 ) );
1760 
1761 cleanup:
1762 
1763  mpi_free( &TA ); mpi_free( &TU ); mpi_free( &U1 ); mpi_free( &U2 );
1764  mpi_free( &G ); mpi_free( &TB ); mpi_free( &TV );
1765  mpi_free( &V1 ); mpi_free( &V2 );
1766 
1767  return( ret );
1768 }
1769 
1770 #if defined(POLARSSL_GENPRIME)
1771 
1772 static const int small_prime[] =
1773 {
1774  3, 5, 7, 11, 13, 17, 19, 23,
1775  29, 31, 37, 41, 43, 47, 53, 59,
1776  61, 67, 71, 73, 79, 83, 89, 97,
1777  101, 103, 107, 109, 113, 127, 131, 137,
1778  139, 149, 151, 157, 163, 167, 173, 179,
1779  181, 191, 193, 197, 199, 211, 223, 227,
1780  229, 233, 239, 241, 251, 257, 263, 269,
1781  271, 277, 281, 283, 293, 307, 311, 313,
1782  317, 331, 337, 347, 349, 353, 359, 367,
1783  373, 379, 383, 389, 397, 401, 409, 419,
1784  421, 431, 433, 439, 443, 449, 457, 461,
1785  463, 467, 479, 487, 491, 499, 503, 509,
1786  521, 523, 541, 547, 557, 563, 569, 571,
1787  577, 587, 593, 599, 601, 607, 613, 617,
1788  619, 631, 641, 643, 647, 653, 659, 661,
1789  673, 677, 683, 691, 701, 709, 719, 727,
1790  733, 739, 743, 751, 757, 761, 769, 773,
1791  787, 797, 809, 811, 821, 823, 827, 829,
1792  839, 853, 857, 859, 863, 877, 881, 883,
1793  887, 907, 911, 919, 929, 937, 941, 947,
1794  953, 967, 971, 977, 983, 991, 997, -103
1795 };
1796 
1797 /*
1798  * Miller-Rabin primality test (HAC 4.24)
1799  */
1800 int mpi_is_prime( mpi *X,
1801  int (*f_rng)(void *, unsigned char *, size_t),
1802  void *p_rng )
1803 {
1804  int ret, xs;
1805  size_t i, j, n, s;
1806  mpi W, R, T, A, RR;
1807 
1808  if( mpi_cmp_int( X, 0 ) == 0 ||
1809  mpi_cmp_int( X, 1 ) == 0 )
1811 
1812  if( mpi_cmp_int( X, 2 ) == 0 )
1813  return( 0 );
1814 
1815  mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
1816  mpi_init( &RR );
1817 
1818  xs = X->s; X->s = 1;
1819 
1820  /*
1821  * test trivial factors first
1822  */
1823  if( ( X->p[0] & 1 ) == 0 )
1825 
1826  for( i = 0; small_prime[i] > 0; i++ )
1827  {
1828  t_uint r;
1829 
1830  if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
1831  return( 0 );
1832 
1833  MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
1834 
1835  if( r == 0 )
1837  }
1838 
1839  /*
1840  * W = |X| - 1
1841  * R = W >> lsb( W )
1842  */
1843  MPI_CHK( mpi_sub_int( &W, X, 1 ) );
1844  s = mpi_lsb( &W );
1845  MPI_CHK( mpi_copy( &R, &W ) );
1846  MPI_CHK( mpi_shift_r( &R, s ) );
1847 
1848  i = mpi_msb( X );
1849  /*
1850  * HAC, table 4.4
1851  */
1852  n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1853  ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1854  ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1855 
1856  for( i = 0; i < n; i++ )
1857  {
1858  /*
1859  * pick a random A, 1 < A < |X| - 1
1860  */
1861  MPI_CHK( mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
1862 
1863  if( mpi_cmp_mpi( &A, &W ) >= 0 )
1864  {
1865  j = mpi_msb( &A ) - mpi_msb( &W );
1866  MPI_CHK( mpi_shift_r( &A, j + 1 ) );
1867  }
1868  A.p[0] |= 3;
1869 
1870  /*
1871  * A = A^R mod |X|
1872  */
1873  MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
1874 
1875  if( mpi_cmp_mpi( &A, &W ) == 0 ||
1876  mpi_cmp_int( &A, 1 ) == 0 )
1877  continue;
1878 
1879  j = 1;
1880  while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
1881  {
1882  /*
1883  * A = A * A mod |X|
1884  */
1885  MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
1886  MPI_CHK( mpi_mod_mpi( &A, &T, X ) );
1887 
1888  if( mpi_cmp_int( &A, 1 ) == 0 )
1889  break;
1890 
1891  j++;
1892  }
1893 
1894  /*
1895  * not prime if A != |X| - 1 or A == 1
1896  */
1897  if( mpi_cmp_mpi( &A, &W ) != 0 ||
1898  mpi_cmp_int( &A, 1 ) == 0 )
1899  {
1901  break;
1902  }
1903  }
1904 
1905 cleanup:
1906 
1907  X->s = xs;
1908 
1909  mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A );
1910  mpi_free( &RR );
1911 
1912  return( ret );
1913 }
1914 
1915 /*
1916  * Prime number generation
1917  */
1918 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
1919  int (*f_rng)(void *, unsigned char *, size_t),
1920  void *p_rng )
1921 {
1922  int ret;
1923  size_t k, n;
1924  mpi Y;
1925 
1926  if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS )
1928 
1929  mpi_init( &Y );
1930 
1931  n = BITS_TO_LIMBS( nbits );
1932 
1933  MPI_CHK( mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
1934 
1935  k = mpi_msb( X );
1936  if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) );
1937  if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits ) );
1938 
1939  X->p[0] |= 3;
1940 
1941  if( dh_flag == 0 )
1942  {
1943  while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1944  {
1945  if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1946  goto cleanup;
1947 
1948  MPI_CHK( mpi_add_int( X, X, 2 ) );
1949  }
1950  }
1951  else
1952  {
1953  MPI_CHK( mpi_sub_int( &Y, X, 1 ) );
1954  MPI_CHK( mpi_shift_r( &Y, 1 ) );
1955 
1956  while( 1 )
1957  {
1958  if( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) == 0 )
1959  {
1960  if( ( ret = mpi_is_prime( &Y, f_rng, p_rng ) ) == 0 )
1961  break;
1962 
1963  if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1964  goto cleanup;
1965  }
1966 
1967  if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1968  goto cleanup;
1969 
1970  MPI_CHK( mpi_add_int( &Y, X, 1 ) );
1971  MPI_CHK( mpi_add_int( X, X, 2 ) );
1972  MPI_CHK( mpi_shift_r( &Y, 1 ) );
1973  }
1974  }
1975 
1976 cleanup:
1977 
1978  mpi_free( &Y );
1979 
1980  return( ret );
1981 }
1982 
1983 #endif /* POLARSSL_GENPRIME */
1984 
1985 #if defined(POLARSSL_SELF_TEST)
1986 
1987 #define GCD_PAIR_COUNT 3
1988 
1989 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
1990 {
1991  { 693, 609, 21 },
1992  { 1764, 868, 28 },
1993  { 768454923, 542167814, 1 }
1994 };
1995 
1996 /*
1997  * Checkup routine
1998  */
1999 int mpi_self_test( int verbose )
2000 {
2001  int ret, i;
2002  mpi A, E, N, X, Y, U, V;
2003 
2004  mpi_init( &A ); mpi_init( &E ); mpi_init( &N ); mpi_init( &X );
2005  mpi_init( &Y ); mpi_init( &U ); mpi_init( &V );
2006 
2007  MPI_CHK( mpi_read_string( &A, 16,
2008  "EFE021C2645FD1DC586E69184AF4A31E" \
2009  "D5F53E93B5F123FA41680867BA110131" \
2010  "944FE7952E2517337780CB0DB80E61AA" \
2011  "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2012 
2013  MPI_CHK( mpi_read_string( &E, 16,
2014  "B2E7EFD37075B9F03FF989C7C5051C20" \
2015  "34D2A323810251127E7BF8625A4F49A5" \
2016  "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2017  "5B5C25763222FEFCCFC38B832366C29E" ) );
2018 
2019  MPI_CHK( mpi_read_string( &N, 16,
2020  "0066A198186C18C10B2F5ED9B522752A" \
2021  "9830B69916E535C8F047518A889A43A5" \
2022  "94B6BED27A168D31D4A52F88925AA8F5" ) );
2023 
2024  MPI_CHK( mpi_mul_mpi( &X, &A, &N ) );
2025 
2026  MPI_CHK( mpi_read_string( &U, 16,
2027  "602AB7ECA597A3D6B56FF9829A5E8B85" \
2028  "9E857EA95A03512E2BAE7391688D264A" \
2029  "A5663B0341DB9CCFD2C4C5F421FEC814" \
2030  "8001B72E848A38CAE1C65F78E56ABDEF" \
2031  "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2032  "ECF677152EF804370C1A305CAF3B5BF1" \
2033  "30879B56C61DE584A0F53A2447A51E" ) );
2034 
2035  if( verbose != 0 )
2036  printf( " MPI test #1 (mul_mpi): " );
2037 
2038  if( mpi_cmp_mpi( &X, &U ) != 0 )
2039  {
2040  if( verbose != 0 )
2041  printf( "failed\n" );
2042 
2043  return( 1 );
2044  }
2045 
2046  if( verbose != 0 )
2047  printf( "passed\n" );
2048 
2049  MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
2050 
2051  MPI_CHK( mpi_read_string( &U, 16,
2052  "256567336059E52CAE22925474705F39A94" ) );
2053 
2054  MPI_CHK( mpi_read_string( &V, 16,
2055  "6613F26162223DF488E9CD48CC132C7A" \
2056  "0AC93C701B001B092E4E5B9F73BCD27B" \
2057  "9EE50D0657C77F374E903CDFA4C642" ) );
2058 
2059  if( verbose != 0 )
2060  printf( " MPI test #2 (div_mpi): " );
2061 
2062  if( mpi_cmp_mpi( &X, &U ) != 0 ||
2063  mpi_cmp_mpi( &Y, &V ) != 0 )
2064  {
2065  if( verbose != 0 )
2066  printf( "failed\n" );
2067 
2068  return( 1 );
2069  }
2070 
2071  if( verbose != 0 )
2072  printf( "passed\n" );
2073 
2074  MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) );
2075 
2076  MPI_CHK( mpi_read_string( &U, 16,
2077  "36E139AEA55215609D2816998ED020BB" \
2078  "BD96C37890F65171D948E9BC7CBAA4D9" \
2079  "325D24D6A3C12710F10A09FA08AB87" ) );
2080 
2081  if( verbose != 0 )
2082  printf( " MPI test #3 (exp_mod): " );
2083 
2084  if( mpi_cmp_mpi( &X, &U ) != 0 )
2085  {
2086  if( verbose != 0 )
2087  printf( "failed\n" );
2088 
2089  return( 1 );
2090  }
2091 
2092  if( verbose != 0 )
2093  printf( "passed\n" );
2094 
2095  MPI_CHK( mpi_inv_mod( &X, &A, &N ) );
2096 
2097  MPI_CHK( mpi_read_string( &U, 16,
2098  "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2099  "C3DBA76456363A10869622EAC2DD84EC" \
2100  "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2101 
2102  if( verbose != 0 )
2103  printf( " MPI test #4 (inv_mod): " );
2104 
2105  if( mpi_cmp_mpi( &X, &U ) != 0 )
2106  {
2107  if( verbose != 0 )
2108  printf( "failed\n" );
2109 
2110  return( 1 );
2111  }
2112 
2113  if( verbose != 0 )
2114  printf( "passed\n" );
2115 
2116  if( verbose != 0 )
2117  printf( " MPI test #5 (simple gcd): " );
2118 
2119  for ( i = 0; i < GCD_PAIR_COUNT; i++)
2120  {
2121  MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) );
2122  MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) );
2123 
2124  MPI_CHK( mpi_gcd( &A, &X, &Y ) );
2125 
2126  if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
2127  {
2128  if( verbose != 0 )
2129  printf( "failed at %d\n", i );
2130 
2131  return( 1 );
2132  }
2133  }
2134 
2135  if( verbose != 0 )
2136  printf( "passed\n" );
2137 
2138 cleanup:
2139 
2140  if( ret != 0 && verbose != 0 )
2141  printf( "Unexpected error, return code = %08X\n", ret );
2142 
2143  mpi_free( &A ); mpi_free( &E ); mpi_free( &N ); mpi_free( &X );
2144  mpi_free( &Y ); mpi_free( &U ); mpi_free( &V );
2145 
2146  if( verbose != 0 )
2147  printf( "\n" );
2148 
2149  return( ret );
2150 }
2151 
2152 #endif
2153 
2154 #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:146
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:170
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 substraction: 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:168
#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:152
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:145
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:172
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:171
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 substraction: 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 substraction: 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