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