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