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