2 * Multi-precision integer library
4 * Based on XySSL: Copyright (C) 2006-2008 Christophe Devine
6 * Copyright (C) 2009 Paul Bakker <polarssl_maintainer at polarssl dot org>
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License along
19 * with this program; if not, write to the Free Software Foundation, Inc.,
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 * This MPI implementation is based on:
25 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
26 * http://www.stillhq.com/extracted/gnupg-api/mpi/
27 * http://math.libtomcrypt.com/files/tommath.pdf
30 /* $Cambridge: exim/src/src/pdkim/bignum.c,v 1.1.2.2 2009/04/09 07:49:11 tom Exp $ */
39 #define ciL ((int) sizeof(t_int)) /* chars in limb */
40 #define biL (ciL << 3) /* bits in limb */
41 #define biH (ciL << 2) /* half limb size */
44 * Convert between bits/chars and number of limbs
46 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
47 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
50 * Initialize one or more mpi
52 void mpi_init( mpi *X, ... )
64 X = va_arg( args, mpi* );
71 * Unallocate one or more mpi
73 void mpi_free( mpi *X, ... )
83 memset( X->p, 0, X->n * ciL );
91 X = va_arg( args, mpi* );
98 * Enlarge to the specified number of limbs
100 int mpi_grow( mpi *X, int nblimbs )
106 if( ( p = (t_int *) malloc( nblimbs * ciL ) ) == NULL )
109 memset( p, 0, nblimbs * ciL );
113 memcpy( p, X->p, X->n * ciL );
114 memset( X->p, 0, X->n * ciL );
126 * Copy the contents of Y into X
128 int mpi_copy( mpi *X, mpi *Y )
135 for( i = Y->n - 1; i > 0; i-- )
142 MPI_CHK( mpi_grow( X, i ) );
144 memset( X->p, 0, X->n * ciL );
145 memcpy( X->p, Y->p, i * ciL );
153 * Swap the contents of X and Y
155 void mpi_swap( mpi *X, mpi *Y )
159 memcpy( &T, X, sizeof( mpi ) );
160 memcpy( X, Y, sizeof( mpi ) );
161 memcpy( Y, &T, sizeof( mpi ) );
165 * Set value from integer
167 int mpi_lset( mpi *X, int z )
171 MPI_CHK( mpi_grow( X, 1 ) );
172 memset( X->p, 0, X->n * ciL );
174 X->p[0] = ( z < 0 ) ? -z : z;
175 X->s = ( z < 0 ) ? -1 : 1;
183 * Return the number of least significant bits
185 int mpi_lsb( mpi *X )
189 for( i = 0; i < X->n; i++ )
190 for( j = 0; j < (int) biL; j++, count++ )
191 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
198 * Return the number of most significant bits
200 int mpi_msb( mpi *X )
204 for( i = X->n - 1; i > 0; i-- )
208 for( j = biL - 1; j >= 0; j-- )
209 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
212 return( ( i * biL ) + j + 1 );
216 * Return the total size in bytes
218 int mpi_size( mpi *X )
220 return( ( mpi_msb( X ) + 7 ) >> 3 );
224 * Convert an ASCII character to digit value
226 static int mpi_get_digit( t_int *d, int radix, char c )
230 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
231 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
232 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
234 if( *d >= (t_int) radix )
235 return( POLARSSL_ERR_MPI_INVALID_CHARACTER );
241 * Import from an ASCII string
243 int mpi_read_string( mpi *X, int radix, char *s )
249 if( radix < 2 || radix > 16 )
250 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
252 mpi_init( &T, NULL );
256 n = BITS_TO_LIMBS( strlen( s ) << 2 );
258 MPI_CHK( mpi_grow( X, n ) );
259 MPI_CHK( mpi_lset( X, 0 ) );
261 for( i = strlen( s ) - 1, j = 0; i >= 0; i--, j++ )
263 if( i == 0 && s[i] == '-' )
269 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
270 X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
275 MPI_CHK( mpi_lset( X, 0 ) );
277 for( i = 0; i < (int) strlen( s ); i++ )
279 if( i == 0 && s[i] == '-' )
285 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
286 MPI_CHK( mpi_mul_int( &T, X, radix ) );
287 MPI_CHK( mpi_add_int( X, &T, d ) );
293 mpi_free( &T, NULL );
299 * Helper to write the digits high-order first
301 static int mpi_write_hlp( mpi *X, int radix, char **p )
306 if( radix < 2 || radix > 16 )
307 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
309 MPI_CHK( mpi_mod_int( &r, X, radix ) );
310 MPI_CHK( mpi_div_int( X, NULL, X, radix ) );
312 if( mpi_cmp_int( X, 0 ) != 0 )
313 MPI_CHK( mpi_write_hlp( X, radix, p ) );
316 *(*p)++ = (char)( r + 0x30 );
318 *(*p)++ = (char)( r + 0x37 );
326 * Export into an ASCII string
328 int mpi_write_string( mpi *X, int radix, char *s, int *slen )
334 if( radix < 2 || radix > 16 )
335 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
338 if( radix >= 4 ) n >>= 1;
339 if( radix >= 16 ) n >>= 1;
345 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
349 mpi_init( &T, NULL );
358 for( i = X->n - 1, k = 0; i >= 0; i-- )
360 for( j = ciL - 1; j >= 0; j-- )
362 c = ( X->p[i] >> (j << 3) ) & 0xFF;
364 if( c == 0 && k == 0 && (i + j) != 0 )
367 p += sprintf( p, "%02X", c );
374 MPI_CHK( mpi_copy( &T, X ) );
375 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
383 mpi_free( &T, NULL );
389 * Read X from an opened file
391 int mpi_read_file( mpi *X, int radix, FILE *fin )
398 memset( s, 0, sizeof( s ) );
399 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
400 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
403 if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
404 if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
408 if( mpi_get_digit( &d, radix, *p ) != 0 )
411 return( mpi_read_string( X, radix, p + 1 ) );
415 * Write X into an opened file (or stdout if fout == NULL)
417 int mpi_write_file( char *p, mpi *X, int radix, FILE *fout )
428 MPI_CHK( mpi_write_string( X, radix, s, (int *) &n ) );
430 if( p == NULL ) p = "";
439 if( fwrite( p, 1, plen, fout ) != plen ||
440 fwrite( s, 1, slen, fout ) != slen )
441 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
444 printf( "%s%s", p, s );
452 * Import X from unsigned binary data, big endian
454 int mpi_read_binary( mpi *X, unsigned char *buf, int buflen )
458 for( n = 0; n < buflen; n++ )
462 MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
463 MPI_CHK( mpi_lset( X, 0 ) );
465 for( i = buflen - 1, j = 0; i >= n; i--, j++ )
466 X->p[j / ciL] |= ((t_int) buf[i]) << ((j % ciL) << 3);
474 * Export X into unsigned binary data, big endian
476 int mpi_write_binary( mpi *X, unsigned char *buf, int buflen )
483 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
485 memset( buf, 0, buflen );
487 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
488 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
494 * Left-shift: X <<= count
496 int mpi_shift_l( mpi *X, int count )
502 t1 = count & (biL - 1);
504 i = mpi_msb( X ) + count;
506 if( X->n * (int) biL < i )
507 MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );
512 * shift by count / limb_size
516 for( i = X->n - 1; i >= v0; i-- )
517 X->p[i] = X->p[i - v0];
524 * shift by count % limb_size
528 for( i = v0; i < X->n; i++ )
530 r1 = X->p[i] >> (biL - t1);
543 * Right-shift: X >>= count
545 int mpi_shift_r( mpi *X, int count )
551 v1 = count & (biL - 1);
554 * shift by count / limb_size
558 for( i = 0; i < X->n - v0; i++ )
559 X->p[i] = X->p[i + v0];
561 for( ; i < X->n; i++ )
566 * shift by count % limb_size
570 for( i = X->n - 1; i >= 0; i-- )
572 r1 = X->p[i] << (biL - v1);
583 * Compare unsigned values
585 int mpi_cmp_abs( mpi *X, mpi *Y )
589 for( i = X->n - 1; i >= 0; i-- )
593 for( j = Y->n - 1; j >= 0; j-- )
600 if( i > j ) return( 1 );
601 if( j > i ) return( -1 );
605 if( X->p[i] > Y->p[i] ) return( 1 );
606 if( X->p[i] < Y->p[i] ) return( -1 );
613 * Compare signed values
615 int mpi_cmp_mpi( mpi *X, mpi *Y )
619 for( i = X->n - 1; i >= 0; i-- )
623 for( j = Y->n - 1; j >= 0; j-- )
630 if( i > j ) return( X->s );
631 if( j > i ) return( -X->s );
633 if( X->s > 0 && Y->s < 0 ) return( 1 );
634 if( Y->s > 0 && X->s < 0 ) return( -1 );
638 if( X->p[i] > Y->p[i] ) return( X->s );
639 if( X->p[i] < Y->p[i] ) return( -X->s );
646 * Compare signed values
648 int mpi_cmp_int( mpi *X, int z )
653 *p = ( z < 0 ) ? -z : z;
654 Y.s = ( z < 0 ) ? -1 : 1;
658 return( mpi_cmp_mpi( X, &Y ) );
662 * Unsigned addition: X = |A| + |B| (HAC 14.7)
664 int mpi_add_abs( mpi *X, mpi *A, mpi *B )
671 mpi *T = A; A = X; B = T;
675 MPI_CHK( mpi_copy( X, A ) );
677 for( j = B->n - 1; j >= 0; j-- )
681 MPI_CHK( mpi_grow( X, j + 1 ) );
683 o = B->p; p = X->p; c = 0;
685 for( i = 0; i <= j; i++, o++, p++ )
687 *p += c; c = ( *p < c );
688 *p += *o; c += ( *p < *o );
695 MPI_CHK( mpi_grow( X, i + 1 ) );
699 *p += c; c = ( *p < c ); i++;
708 * Helper for mpi substraction
710 static void mpi_sub_hlp( int n, t_int *s, t_int *d )
715 for( i = c = 0; i < n; i++, s++, d++ )
717 z = ( *d < c ); *d -= c;
718 c = ( *d < *s ) + z; *d -= *s;
723 z = ( *d < c ); *d -= c;
729 * Unsigned substraction: X = |A| - |B| (HAC 14.9)
731 int mpi_sub_abs( mpi *X, mpi *A, mpi *B )
736 if( mpi_cmp_abs( A, B ) < 0 )
737 return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
739 mpi_init( &TB, NULL );
743 MPI_CHK( mpi_copy( &TB, B ) );
748 MPI_CHK( mpi_copy( X, A ) );
752 for( n = B->n - 1; n >= 0; n-- )
756 mpi_sub_hlp( n + 1, B->p, X->p );
760 mpi_free( &TB, NULL );
766 * Signed addition: X = A + B
768 int mpi_add_mpi( mpi *X, mpi *A, mpi *B )
772 if( A->s * B->s < 0 )
774 if( mpi_cmp_abs( A, B ) >= 0 )
776 MPI_CHK( mpi_sub_abs( X, A, B ) );
781 MPI_CHK( mpi_sub_abs( X, B, A ) );
787 MPI_CHK( mpi_add_abs( X, A, B ) );
797 * Signed substraction: X = A - B
799 int mpi_sub_mpi( mpi *X, mpi *A, mpi *B )
803 if( A->s * B->s > 0 )
805 if( mpi_cmp_abs( A, B ) >= 0 )
807 MPI_CHK( mpi_sub_abs( X, A, B ) );
812 MPI_CHK( mpi_sub_abs( X, B, A ) );
818 MPI_CHK( mpi_add_abs( X, A, B ) );
828 * Signed addition: X = A + b
830 int mpi_add_int( mpi *X, mpi *A, int b )
835 p[0] = ( b < 0 ) ? -b : b;
836 _B.s = ( b < 0 ) ? -1 : 1;
840 return( mpi_add_mpi( X, A, &_B ) );
844 * Signed substraction: X = A - b
846 int mpi_sub_int( mpi *X, mpi *A, int b )
851 p[0] = ( b < 0 ) ? -b : b;
852 _B.s = ( b < 0 ) ? -1 : 1;
856 return( mpi_sub_mpi( X, A, &_B ) );
860 * Helper for mpi multiplication
862 static void mpi_mul_hlp( int i, t_int *s, t_int *d, t_int b )
866 #if defined(MULADDC_HUIT)
867 for( ; i >= 8; i -= 8 )
881 for( ; i >= 16; i -= 16 )
884 MULADDC_CORE MULADDC_CORE
885 MULADDC_CORE MULADDC_CORE
886 MULADDC_CORE MULADDC_CORE
887 MULADDC_CORE MULADDC_CORE
889 MULADDC_CORE MULADDC_CORE
890 MULADDC_CORE MULADDC_CORE
891 MULADDC_CORE MULADDC_CORE
892 MULADDC_CORE MULADDC_CORE
896 for( ; i >= 8; i -= 8 )
899 MULADDC_CORE MULADDC_CORE
900 MULADDC_CORE MULADDC_CORE
902 MULADDC_CORE MULADDC_CORE
903 MULADDC_CORE MULADDC_CORE
918 *d += c; c = ( *d < c ); d++;
924 * Baseline multiplication: X = A * B (HAC 14.12)
926 int mpi_mul_mpi( mpi *X, mpi *A, mpi *B )
931 mpi_init( &TA, &TB, NULL );
933 if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; }
934 if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; }
936 for( i = A->n - 1; i >= 0; i-- )
940 for( j = B->n - 1; j >= 0; j-- )
944 MPI_CHK( mpi_grow( X, i + j + 2 ) );
945 MPI_CHK( mpi_lset( X, 0 ) );
947 for( i++; j >= 0; j-- )
948 mpi_mul_hlp( i, A->p, X->p + j, B->p[j] );
954 mpi_free( &TB, &TA, NULL );
960 * Baseline multiplication: X = A * b
962 int mpi_mul_int( mpi *X, mpi *A, t_int b )
972 return( mpi_mul_mpi( X, A, &_B ) );
976 * Division by mpi: A = Q * B + R (HAC 14.20)
978 int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B )
983 if( mpi_cmp_int( B, 0 ) == 0 )
984 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
986 mpi_init( &X, &Y, &Z, &T1, &T2, NULL );
988 if( mpi_cmp_abs( A, B ) < 0 )
990 if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) );
991 if( R != NULL ) MPI_CHK( mpi_copy( R, A ) );
995 MPI_CHK( mpi_copy( &X, A ) );
996 MPI_CHK( mpi_copy( &Y, B ) );
999 MPI_CHK( mpi_grow( &Z, A->n + 2 ) );
1000 MPI_CHK( mpi_lset( &Z, 0 ) );
1001 MPI_CHK( mpi_grow( &T1, 2 ) );
1002 MPI_CHK( mpi_grow( &T2, 3 ) );
1004 k = mpi_msb( &Y ) % biL;
1005 if( k < (int) biL - 1 )
1008 MPI_CHK( mpi_shift_l( &X, k ) );
1009 MPI_CHK( mpi_shift_l( &Y, k ) );
1015 mpi_shift_l( &Y, biL * (n - t) );
1017 while( mpi_cmp_mpi( &X, &Y ) >= 0 )
1020 mpi_sub_mpi( &X, &X, &Y );
1022 mpi_shift_r( &Y, biL * (n - t) );
1024 for( i = n; i > t ; i-- )
1026 if( X.p[i] >= Y.p[t] )
1027 Z.p[i - t - 1] = ~0;
1030 #if defined(POLARSSL_HAVE_LONGLONG)
1033 r = (t_dbl) X.p[i] << biL;
1034 r |= (t_dbl) X.p[i - 1];
1036 if( r > ((t_dbl) 1 << biL) - 1)
1037 r = ((t_dbl) 1 << biL) - 1;
1039 Z.p[i - t - 1] = (t_int) r;
1042 * __udiv_qrnnd_c, from gmp/longlong.h
1044 t_int q0, q1, r0, r1;
1048 d0 = ( d << biH ) >> biH;
1052 r1 = X.p[i] - d1 * q1;
1054 r1 |= ( X.p[i - 1] >> biH );
1060 while( r1 >= d && r1 < m )
1068 r0 |= ( X.p[i - 1] << biH ) >> biH;
1074 while( r0 >= d && r0 < m )
1079 Z.p[i - t - 1] = ( q1 << biH ) | q0;
1088 MPI_CHK( mpi_lset( &T1, 0 ) );
1089 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1091 MPI_CHK( mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1093 MPI_CHK( mpi_lset( &T2, 0 ) );
1094 T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1095 T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1098 while( mpi_cmp_mpi( &T1, &T2 ) > 0 );
1100 MPI_CHK( mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1101 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
1102 MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) );
1104 if( mpi_cmp_int( &X, 0 ) < 0 )
1106 MPI_CHK( mpi_copy( &T1, &Y ) );
1107 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
1108 MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) );
1121 mpi_shift_r( &X, k );
1125 if( mpi_cmp_int( R, 0 ) == 0 )
1131 mpi_free( &X, &Y, &Z, &T1, &T2, NULL );
1137 * Division by int: A = Q * b + R
1139 * Returns 0 if successful
1140 * 1 if memory allocation failed
1141 * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
1143 int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b )
1148 p[0] = ( b < 0 ) ? -b : b;
1149 _B.s = ( b < 0 ) ? -1 : 1;
1153 return( mpi_div_mpi( Q, R, A, &_B ) );
1157 * Modulo: R = A mod B
1159 int mpi_mod_mpi( mpi *R, mpi *A, mpi *B )
1163 MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
1165 while( mpi_cmp_int( R, 0 ) < 0 )
1166 MPI_CHK( mpi_add_mpi( R, R, B ) );
1168 while( mpi_cmp_mpi( R, B ) >= 0 )
1169 MPI_CHK( mpi_sub_mpi( R, R, B ) );
1177 * Modulo: r = A mod b
1179 int mpi_mod_int( t_int *r, mpi *A, int b )
1185 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
1191 * handle trivial cases
1208 for( i = A->n - 1, y = 0; i >= 0; i-- )
1211 y = ( y << biH ) | ( x >> biH );
1216 y = ( y << biH ) | ( x >> biH );
1227 * Fast Montgomery initialization (thanks to Tom St Denis)
1229 static void mpi_montg_init( t_int *mm, mpi *N )
1231 t_int x, m0 = N->p[0];
1234 x += ( ( m0 + 2 ) & 4 ) << 1;
1235 x *= ( 2 - ( m0 * x ) );
1237 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
1238 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
1239 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
1245 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1247 static void mpi_montmul( mpi *A, mpi *B, mpi *N, t_int mm, mpi *T )
1252 memset( T->p, 0, T->n * ciL );
1256 m = ( B->n < n ) ? B->n : n;
1258 for( i = 0; i < n; i++ )
1261 * T = (T + u0*B + u1*N) / 2^biL
1264 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1266 mpi_mul_hlp( m, B->p, d, u0 );
1267 mpi_mul_hlp( n, N->p, d, u1 );
1269 *d++ = u0; d[n + 1] = 0;
1272 memcpy( A->p, d, (n + 1) * ciL );
1274 if( mpi_cmp_abs( A, N ) >= 0 )
1275 mpi_sub_hlp( n, N->p, A->p );
1277 /* prevent timing attacks */
1278 mpi_sub_hlp( n, A->p, T->p );
1282 * Montgomery reduction: A = A * R^-1 mod N
1284 static void mpi_montred( mpi *A, mpi *N, t_int mm, mpi *T )
1292 mpi_montmul( A, &U, N, mm, T );
1296 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1298 int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR )
1300 int ret, i, j, wsize, wbits;
1301 int bufsize, nblimbs, nbits;
1302 t_int ei, mm, state;
1305 if( mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
1306 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1309 * Init temps and window size
1311 mpi_montg_init( &mm, N );
1312 mpi_init( &RR, &T, NULL );
1313 memset( W, 0, sizeof( W ) );
1317 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1318 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1321 MPI_CHK( mpi_grow( X, j ) );
1322 MPI_CHK( mpi_grow( &W[1], j ) );
1323 MPI_CHK( mpi_grow( &T, j * 2 ) );
1326 * If 1st call, pre-compute R^2 mod N
1328 if( _RR == NULL || _RR->p == NULL )
1330 MPI_CHK( mpi_lset( &RR, 1 ) );
1331 MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) );
1332 MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) );
1335 memcpy( _RR, &RR, sizeof( mpi ) );
1338 memcpy( &RR, _RR, sizeof( mpi ) );
1341 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1343 if( mpi_cmp_mpi( A, N ) >= 0 )
1344 mpi_mod_mpi( &W[1], A, N );
1345 else mpi_copy( &W[1], A );
1347 mpi_montmul( &W[1], &RR, N, mm, &T );
1350 * X = R^2 * R^-1 mod N = R mod N
1352 MPI_CHK( mpi_copy( X, &RR ) );
1353 mpi_montred( X, N, mm, &T );
1358 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1360 j = 1 << (wsize - 1);
1362 MPI_CHK( mpi_grow( &W[j], N->n + 1 ) );
1363 MPI_CHK( mpi_copy( &W[j], &W[1] ) );
1365 for( i = 0; i < wsize - 1; i++ )
1366 mpi_montmul( &W[j], &W[j], N, mm, &T );
1369 * W[i] = W[i - 1] * W[1]
1371 for( i = j + 1; i < (1 << wsize); i++ )
1373 MPI_CHK( mpi_grow( &W[i], N->n + 1 ) );
1374 MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) );
1376 mpi_montmul( &W[i], &W[1], N, mm, &T );
1390 if( nblimbs-- == 0 )
1393 bufsize = sizeof( t_int ) << 3;
1398 ei = (E->p[nblimbs] >> bufsize) & 1;
1403 if( ei == 0 && state == 0 )
1406 if( ei == 0 && state == 1 )
1409 * out of window, square X
1411 mpi_montmul( X, X, N, mm, &T );
1416 * add ei to current window
1421 wbits |= (ei << (wsize - nbits));
1423 if( nbits == wsize )
1426 * X = X^wsize R^-1 mod N
1428 for( i = 0; i < wsize; i++ )
1429 mpi_montmul( X, X, N, mm, &T );
1432 * X = X * W[wbits] R^-1 mod N
1434 mpi_montmul( X, &W[wbits], N, mm, &T );
1443 * process the remaining bits
1445 for( i = 0; i < nbits; i++ )
1447 mpi_montmul( X, X, N, mm, &T );
1451 if( (wbits & (1 << wsize)) != 0 )
1452 mpi_montmul( X, &W[1], N, mm, &T );
1456 * X = A^E * R * R^-1 mod N = A^E mod N
1458 mpi_montred( X, N, mm, &T );
1462 for( i = (1 << (wsize - 1)); i < (1 << wsize); i++ )
1463 mpi_free( &W[i], NULL );
1466 mpi_free( &W[1], &T, NULL );
1467 else mpi_free( &W[1], &T, &RR, NULL );
1473 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1475 int mpi_gcd( mpi *G, mpi *A, mpi *B )
1480 mpi_init( &TG, &TA, &TB, NULL );
1482 MPI_CHK( mpi_lset( &TG, 1 ) );
1483 MPI_CHK( mpi_copy( &TA, A ) );
1484 MPI_CHK( mpi_copy( &TB, B ) );
1488 while( mpi_cmp_int( &TA, 0 ) != 0 )
1490 while( ( TA.p[0] & 1 ) == 0 ) MPI_CHK( mpi_shift_r( &TA, 1 ) );
1491 while( ( TB.p[0] & 1 ) == 0 ) MPI_CHK( mpi_shift_r( &TB, 1 ) );
1493 if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
1495 MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
1496 MPI_CHK( mpi_shift_r( &TA, 1 ) );
1500 MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
1501 MPI_CHK( mpi_shift_r( &TB, 1 ) );
1505 MPI_CHK( mpi_mul_mpi( G, &TG, &TB ) );
1509 mpi_free( &TB, &TA, &TG, NULL );
1515 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1517 int mpi_inv_mod( mpi *X, mpi *A, mpi *N )
1520 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1522 if( mpi_cmp_int( N, 0 ) <= 0 )
1523 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1525 mpi_init( &TA, &TU, &U1, &U2, &G,
1526 &TB, &TV, &V1, &V2, NULL );
1528 MPI_CHK( mpi_gcd( &G, A, N ) );
1530 if( mpi_cmp_int( &G, 1 ) != 0 )
1532 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
1536 MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
1537 MPI_CHK( mpi_copy( &TU, &TA ) );
1538 MPI_CHK( mpi_copy( &TB, N ) );
1539 MPI_CHK( mpi_copy( &TV, N ) );
1541 MPI_CHK( mpi_lset( &U1, 1 ) );
1542 MPI_CHK( mpi_lset( &U2, 0 ) );
1543 MPI_CHK( mpi_lset( &V1, 0 ) );
1544 MPI_CHK( mpi_lset( &V2, 1 ) );
1548 while( ( TU.p[0] & 1 ) == 0 )
1550 MPI_CHK( mpi_shift_r( &TU, 1 ) );
1552 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1554 MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
1555 MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
1558 MPI_CHK( mpi_shift_r( &U1, 1 ) );
1559 MPI_CHK( mpi_shift_r( &U2, 1 ) );
1562 while( ( TV.p[0] & 1 ) == 0 )
1564 MPI_CHK( mpi_shift_r( &TV, 1 ) );
1566 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1568 MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
1569 MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
1572 MPI_CHK( mpi_shift_r( &V1, 1 ) );
1573 MPI_CHK( mpi_shift_r( &V2, 1 ) );
1576 if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
1578 MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
1579 MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
1580 MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
1584 MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
1585 MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
1586 MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
1589 while( mpi_cmp_int( &TU, 0 ) != 0 );
1591 while( mpi_cmp_int( &V1, 0 ) < 0 )
1592 MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
1594 while( mpi_cmp_mpi( &V1, N ) >= 0 )
1595 MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
1597 MPI_CHK( mpi_copy( X, &V1 ) );
1601 mpi_free( &V2, &V1, &TV, &TB, &G,
1602 &U2, &U1, &TU, &TA, NULL );
1607 static const int small_prime[] =
1609 3, 5, 7, 11, 13, 17, 19, 23,
1610 29, 31, 37, 41, 43, 47, 53, 59,
1611 61, 67, 71, 73, 79, 83, 89, 97,
1612 101, 103, 107, 109, 113, 127, 131, 137,
1613 139, 149, 151, 157, 163, 167, 173, 179,
1614 181, 191, 193, 197, 199, 211, 223, 227,
1615 229, 233, 239, 241, 251, 257, 263, 269,
1616 271, 277, 281, 283, 293, 307, 311, 313,
1617 317, 331, 337, 347, 349, 353, 359, 367,
1618 373, 379, 383, 389, 397, 401, 409, 419,
1619 421, 431, 433, 439, 443, 449, 457, 461,
1620 463, 467, 479, 487, 491, 499, 503, 509,
1621 521, 523, 541, 547, 557, 563, 569, 571,
1622 577, 587, 593, 599, 601, 607, 613, 617,
1623 619, 631, 641, 643, 647, 653, 659, 661,
1624 673, 677, 683, 691, 701, 709, 719, 727,
1625 733, 739, 743, 751, 757, 761, 769, 773,
1626 787, 797, 809, 811, 821, 823, 827, 829,
1627 839, 853, 857, 859, 863, 877, 881, 883,
1628 887, 907, 911, 919, 929, 937, 941, 947,
1629 953, 967, 971, 977, 983, 991, 997, -103
1633 * Miller-Rabin primality test (HAC 4.24)
1635 int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng )
1637 int ret, i, j, n, s, xs;
1641 if( mpi_cmp_int( X, 0 ) == 0 )
1644 mpi_init( &W, &R, &T, &A, &RR, NULL );
1646 xs = X->s; X->s = 1;
1649 * test trivial factors first
1651 if( ( X->p[0] & 1 ) == 0 )
1652 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1654 for( i = 0; small_prime[i] > 0; i++ )
1658 if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
1661 MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
1664 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1672 MPI_CHK( mpi_sub_int( &W, X, 1 ) );
1673 MPI_CHK( mpi_copy( &R, &W ) );
1674 MPI_CHK( mpi_shift_r( &R, s ) );
1680 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1681 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1682 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1684 for( i = 0; i < n; i++ )
1687 * pick a random A, 1 < A < |X| - 1
1689 MPI_CHK( mpi_grow( &A, X->n ) );
1691 p = (unsigned char *) A.p;
1692 for( j = 0; j < A.n * ciL; j++ )
1693 *p++ = (unsigned char) f_rng( p_rng );
1695 j = mpi_msb( &A ) - mpi_msb( &W );
1696 MPI_CHK( mpi_shift_r( &A, j + 1 ) );
1702 MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
1704 if( mpi_cmp_mpi( &A, &W ) == 0 ||
1705 mpi_cmp_int( &A, 1 ) == 0 )
1709 while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
1714 MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
1715 MPI_CHK( mpi_mod_mpi( &A, &T, X ) );
1717 if( mpi_cmp_int( &A, 1 ) == 0 )
1724 * not prime if A != |X| - 1 or A == 1
1726 if( mpi_cmp_mpi( &A, &W ) != 0 ||
1727 mpi_cmp_int( &A, 1 ) == 0 )
1729 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
1738 mpi_free( &RR, &A, &T, &R, &W, NULL );
1744 * Prime number generation
1746 int mpi_gen_prime( mpi *X, int nbits, int dh_flag,
1747 int (*f_rng)(void *), void *p_rng )
1754 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1756 mpi_init( &Y, NULL );
1758 n = BITS_TO_LIMBS( nbits );
1760 MPI_CHK( mpi_grow( X, n ) );
1761 MPI_CHK( mpi_lset( X, 0 ) );
1763 p = (unsigned char *) X->p;
1764 for( k = 0; k < X->n * ciL; k++ )
1765 *p++ = (unsigned char) f_rng( p_rng );
1768 if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) );
1769 if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits ) );
1775 while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1777 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1780 MPI_CHK( mpi_add_int( X, X, 2 ) );
1785 MPI_CHK( mpi_sub_int( &Y, X, 1 ) );
1786 MPI_CHK( mpi_shift_r( &Y, 1 ) );
1790 if( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) == 0 )
1792 if( ( ret = mpi_is_prime( &Y, f_rng, p_rng ) ) == 0 )
1795 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1799 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1802 MPI_CHK( mpi_add_int( &Y, X, 1 ) );
1803 MPI_CHK( mpi_add_int( X, X, 2 ) );
1804 MPI_CHK( mpi_shift_r( &Y, 1 ) );
1810 mpi_free( &Y, NULL );