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