2 * Multi-precision integer library
4 * Copyright (C) 2006-2010, Brainspark B.V.
6 * This file is part of PolarSSL (http://www.polarssl.org)
7 * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
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.
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.
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.
26 * This MPI implementation is based on:
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
33 /* $Cambridge: exim/src/src/pdkim/bignum.c,v 1.3 2009/12/07 13:05:07 tom Exp $ */
42 #define ciL ((int) sizeof(t_int)) /* chars in limb */
43 #define biL (ciL << 3) /* bits in limb */
44 #define biH (ciL << 2) /* half limb size */
47 * Convert between bits/chars and number of limbs
49 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
50 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
53 * Initialize one or more mpi
55 void mpi_init( mpi *X, ... )
67 X = va_arg( args, mpi* );
74 * Unallocate one or more mpi
76 void mpi_free( mpi *X, ... )
86 memset( X->p, 0, X->n * ciL );
94 X = va_arg( args, mpi* );
101 * Enlarge to the specified number of limbs
103 int mpi_grow( mpi *X, int nblimbs )
109 if( ( p = (t_int *) malloc( nblimbs * ciL ) ) == NULL )
112 memset( p, 0, nblimbs * ciL );
116 memcpy( p, X->p, X->n * ciL );
117 memset( X->p, 0, X->n * ciL );
129 * Copy the contents of Y into X
131 int mpi_copy( mpi *X, const mpi *Y )
138 for( i = Y->n - 1; i > 0; i-- )
145 MPI_CHK( mpi_grow( X, i ) );
147 memset( X->p, 0, X->n * ciL );
148 memcpy( X->p, Y->p, i * ciL );
156 * Swap the contents of X and Y
158 void mpi_swap( mpi *X, mpi *Y )
162 memcpy( &T, X, sizeof( mpi ) );
163 memcpy( X, Y, sizeof( mpi ) );
164 memcpy( Y, &T, sizeof( mpi ) );
168 * Set value from integer
170 int mpi_lset( mpi *X, int z )
174 MPI_CHK( mpi_grow( X, 1 ) );
175 memset( X->p, 0, X->n * ciL );
177 X->p[0] = ( z < 0 ) ? -z : z;
178 X->s = ( z < 0 ) ? -1 : 1;
186 * Return the number of least significant bits
188 int mpi_lsb( const mpi *X )
192 for( i = 0; i < X->n; i++ )
193 for( j = 0; j < (int) biL; j++, count++ )
194 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
201 * Return the number of most significant bits
203 int mpi_msb( const mpi *X )
207 for( i = X->n - 1; i > 0; i-- )
211 for( j = biL - 1; j >= 0; j-- )
212 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
215 return( ( i * biL ) + j + 1 );
219 * Return the total size in bytes
221 int mpi_size( const mpi *X )
223 return( ( mpi_msb( X ) + 7 ) >> 3 );
227 * Convert an ASCII character to digit value
229 static int mpi_get_digit( t_int *d, int radix, char c )
233 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
234 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
235 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
237 if( *d >= (t_int) radix )
238 return( POLARSSL_ERR_MPI_INVALID_CHARACTER );
244 * Import from an ASCII string
246 int mpi_read_string( mpi *X, int radix, const char *s )
248 int ret, i, j, n, slen;
252 if( radix < 2 || radix > 16 )
253 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
255 mpi_init( &T, NULL );
261 n = BITS_TO_LIMBS( slen << 2 );
263 MPI_CHK( mpi_grow( X, n ) );
264 MPI_CHK( mpi_lset( X, 0 ) );
266 for( i = slen - 1, j = 0; i >= 0; i--, j++ )
268 if( i == 0 && s[i] == '-' )
274 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
275 X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
280 MPI_CHK( mpi_lset( X, 0 ) );
282 for( i = 0; i < slen; i++ )
284 if( i == 0 && s[i] == '-' )
290 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
291 MPI_CHK( mpi_mul_int( &T, X, radix ) );
295 MPI_CHK( mpi_add_int( X, &T, d ) );
299 MPI_CHK( mpi_sub_int( X, &T, d ) );
306 mpi_free( &T, NULL );
312 * Helper to write the digits high-order first
314 static int mpi_write_hlp( mpi *X, int radix, char **p )
319 if( radix < 2 || radix > 16 )
320 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
322 MPI_CHK( mpi_mod_int( &r, X, radix ) );
323 MPI_CHK( mpi_div_int( X, NULL, X, radix ) );
325 if( mpi_cmp_int( X, 0 ) != 0 )
326 MPI_CHK( mpi_write_hlp( X, radix, p ) );
329 *(*p)++ = (char)( r + 0x30 );
331 *(*p)++ = (char)( r + 0x37 );
339 * Export into an ASCII string
341 int mpi_write_string( const mpi *X, int radix, char *s, int *slen )
347 if( radix < 2 || radix > 16 )
348 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
351 if( radix >= 4 ) n >>= 1;
352 if( radix >= 16 ) n >>= 1;
358 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
362 mpi_init( &T, NULL );
371 for( i = X->n - 1, k = 0; i >= 0; i-- )
373 for( j = ciL - 1; j >= 0; j-- )
375 c = ( X->p[i] >> (j << 3) ) & 0xFF;
377 if( c == 0 && k == 0 && (i + j) != 0 )
380 p += sprintf( p, "%02X", c );
387 MPI_CHK( mpi_copy( &T, X ) );
392 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
400 mpi_free( &T, NULL );
406 * Read X from an opened file
408 int mpi_read_file( mpi *X, int radix, FILE *fin )
415 memset( s, 0, sizeof( s ) );
416 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
417 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
420 if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
421 if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
425 if( mpi_get_digit( &d, radix, *p ) != 0 )
428 return( mpi_read_string( X, radix, p + 1 ) );
432 * Write X into an opened file (or stdout if fout == NULL)
434 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout )
445 MPI_CHK( mpi_write_string( X, radix, s, (int *) &n ) );
447 if( p == NULL ) p = "";
456 if( fwrite( p, 1, plen, fout ) != plen ||
457 fwrite( s, 1, slen, fout ) != slen )
458 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
461 printf( "%s%s", p, s );
469 * Import X from unsigned binary data, big endian
471 int mpi_read_binary( mpi *X, const unsigned char *buf, int buflen )
475 for( n = 0; n < buflen; n++ )
479 MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
480 MPI_CHK( mpi_lset( X, 0 ) );
482 for( i = buflen - 1, j = 0; i >= n; i--, j++ )
483 X->p[j / ciL] |= ((t_int) buf[i]) << ((j % ciL) << 3);
491 * Export X into unsigned binary data, big endian
493 int mpi_write_binary( const mpi *X, unsigned char *buf, int buflen )
500 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
502 memset( buf, 0, buflen );
504 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
505 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
511 * Left-shift: X <<= count
513 int mpi_shift_l( mpi *X, int count )
519 t1 = count & (biL - 1);
521 i = mpi_msb( X ) + count;
523 if( X->n * (int) biL < i )
524 MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );
529 * shift by count / limb_size
533 for( i = X->n - 1; i >= v0; i-- )
534 X->p[i] = X->p[i - v0];
541 * shift by count % limb_size
545 for( i = v0; i < X->n; i++ )
547 r1 = X->p[i] >> (biL - t1);
560 * Right-shift: X >>= count
562 int mpi_shift_r( mpi *X, int count )
568 v1 = count & (biL - 1);
571 * shift by count / limb_size
575 for( i = 0; i < X->n - v0; i++ )
576 X->p[i] = X->p[i + v0];
578 for( ; i < X->n; i++ )
583 * shift by count % limb_size
587 for( i = X->n - 1; i >= 0; i-- )
589 r1 = X->p[i] << (biL - v1);
600 * Compare unsigned values
602 int mpi_cmp_abs( const mpi *X, const mpi *Y )
606 for( i = X->n - 1; i >= 0; i-- )
610 for( j = Y->n - 1; j >= 0; j-- )
617 if( i > j ) return( 1 );
618 if( j > i ) return( -1 );
622 if( X->p[i] > Y->p[i] ) return( 1 );
623 if( X->p[i] < Y->p[i] ) return( -1 );
630 * Compare signed values
632 int mpi_cmp_mpi( const mpi *X, const mpi *Y )
636 for( i = X->n - 1; i >= 0; i-- )
640 for( j = Y->n - 1; j >= 0; j-- )
647 if( i > j ) return( X->s );
648 if( j > i ) return( -X->s );
650 if( X->s > 0 && Y->s < 0 ) return( 1 );
651 if( Y->s > 0 && X->s < 0 ) return( -1 );
655 if( X->p[i] > Y->p[i] ) return( X->s );
656 if( X->p[i] < Y->p[i] ) return( -X->s );
663 * Compare signed values
665 int mpi_cmp_int( const mpi *X, int z )
670 *p = ( z < 0 ) ? -z : z;
671 Y.s = ( z < 0 ) ? -1 : 1;
675 return( mpi_cmp_mpi( X, &Y ) );
679 * Unsigned addition: X = |A| + |B| (HAC 14.7)
681 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B )
688 const mpi *T = A; A = X; B = T;
692 MPI_CHK( mpi_copy( X, A ) );
695 * X should always be positive as a result of unsigned additions.
699 for( j = B->n - 1; j >= 0; j-- )
703 MPI_CHK( mpi_grow( X, j + 1 ) );
705 o = B->p; p = X->p; c = 0;
707 for( i = 0; i <= j; i++, o++, p++ )
709 *p += c; c = ( *p < c );
710 *p += *o; c += ( *p < *o );
717 MPI_CHK( mpi_grow( X, i + 1 ) );
721 *p += c; c = ( *p < c ); i++;
730 * Helper for mpi substraction
732 static void mpi_sub_hlp( int n, t_int *s, t_int *d )
737 for( i = c = 0; i < n; i++, s++, d++ )
739 z = ( *d < c ); *d -= c;
740 c = ( *d < *s ) + z; *d -= *s;
745 z = ( *d < c ); *d -= c;
751 * Unsigned substraction: X = |A| - |B| (HAC 14.9)
753 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B )
758 if( mpi_cmp_abs( A, B ) < 0 )
759 return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
761 mpi_init( &TB, NULL );
765 MPI_CHK( mpi_copy( &TB, B ) );
770 MPI_CHK( mpi_copy( X, A ) );
773 * X should always be positive as a result of unsigned substractions.
779 for( n = B->n - 1; n >= 0; n-- )
783 mpi_sub_hlp( n + 1, B->p, X->p );
787 mpi_free( &TB, NULL );
793 * Signed addition: X = A + B
795 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B )
799 if( A->s * B->s < 0 )
801 if( mpi_cmp_abs( A, B ) >= 0 )
803 MPI_CHK( mpi_sub_abs( X, A, B ) );
808 MPI_CHK( mpi_sub_abs( X, B, A ) );
814 MPI_CHK( mpi_add_abs( X, A, B ) );
824 * Signed substraction: X = A - B
826 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B )
830 if( A->s * B->s > 0 )
832 if( mpi_cmp_abs( A, B ) >= 0 )
834 MPI_CHK( mpi_sub_abs( X, A, B ) );
839 MPI_CHK( mpi_sub_abs( X, B, A ) );
845 MPI_CHK( mpi_add_abs( X, A, B ) );
855 * Signed addition: X = A + b
857 int mpi_add_int( mpi *X, const mpi *A, int b )
862 p[0] = ( b < 0 ) ? -b : b;
863 _B.s = ( b < 0 ) ? -1 : 1;
867 return( mpi_add_mpi( X, A, &_B ) );
871 * Signed substraction: X = A - b
873 int mpi_sub_int( mpi *X, const mpi *A, int b )
878 p[0] = ( b < 0 ) ? -b : b;
879 _B.s = ( b < 0 ) ? -1 : 1;
883 return( mpi_sub_mpi( X, A, &_B ) );
887 * Helper for mpi multiplication
889 static void mpi_mul_hlp( int i, t_int *s, t_int *d, t_int b )
893 #if defined(MULADDC_HUIT)
894 for( ; i >= 8; i -= 8 )
908 for( ; i >= 16; i -= 16 )
911 MULADDC_CORE MULADDC_CORE
912 MULADDC_CORE MULADDC_CORE
913 MULADDC_CORE MULADDC_CORE
914 MULADDC_CORE MULADDC_CORE
916 MULADDC_CORE MULADDC_CORE
917 MULADDC_CORE MULADDC_CORE
918 MULADDC_CORE MULADDC_CORE
919 MULADDC_CORE MULADDC_CORE
923 for( ; i >= 8; i -= 8 )
926 MULADDC_CORE MULADDC_CORE
927 MULADDC_CORE MULADDC_CORE
929 MULADDC_CORE MULADDC_CORE
930 MULADDC_CORE MULADDC_CORE
945 *d += c; c = ( *d < c ); d++;
951 * Baseline multiplication: X = A * B (HAC 14.12)
953 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B )
958 mpi_init( &TA, &TB, NULL );
960 if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; }
961 if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; }
963 for( i = A->n - 1; i >= 0; i-- )
967 for( j = B->n - 1; j >= 0; j-- )
971 MPI_CHK( mpi_grow( X, i + j + 2 ) );
972 MPI_CHK( mpi_lset( X, 0 ) );
974 for( i++; j >= 0; j-- )
975 mpi_mul_hlp( i, A->p, X->p + j, B->p[j] );
981 mpi_free( &TB, &TA, NULL );
987 * Baseline multiplication: X = A * b
989 int mpi_mul_int( mpi *X, const mpi *A, t_int b )
999 return( mpi_mul_mpi( X, A, &_B ) );
1003 * Division by mpi: A = Q * B + R (HAC 14.20)
1005 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B )
1007 int ret, i, n, t, k;
1008 mpi X, Y, Z, T1, T2;
1010 if( mpi_cmp_int( B, 0 ) == 0 )
1011 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
1013 mpi_init( &X, &Y, &Z, &T1, &T2, NULL );
1015 if( mpi_cmp_abs( A, B ) < 0 )
1017 if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) );
1018 if( R != NULL ) MPI_CHK( mpi_copy( R, A ) );
1022 MPI_CHK( mpi_copy( &X, A ) );
1023 MPI_CHK( mpi_copy( &Y, B ) );
1026 MPI_CHK( mpi_grow( &Z, A->n + 2 ) );
1027 MPI_CHK( mpi_lset( &Z, 0 ) );
1028 MPI_CHK( mpi_grow( &T1, 2 ) );
1029 MPI_CHK( mpi_grow( &T2, 3 ) );
1031 k = mpi_msb( &Y ) % biL;
1032 if( k < (int) biL - 1 )
1035 MPI_CHK( mpi_shift_l( &X, k ) );
1036 MPI_CHK( mpi_shift_l( &Y, k ) );
1042 mpi_shift_l( &Y, biL * (n - t) );
1044 while( mpi_cmp_mpi( &X, &Y ) >= 0 )
1047 mpi_sub_mpi( &X, &X, &Y );
1049 mpi_shift_r( &Y, biL * (n - t) );
1051 for( i = n; i > t ; i-- )
1053 if( X.p[i] >= Y.p[t] )
1054 Z.p[i - t - 1] = ~0;
1057 #if defined(POLARSSL_HAVE_LONGLONG)
1060 r = (t_dbl) X.p[i] << biL;
1061 r |= (t_dbl) X.p[i - 1];
1063 if( r > ((t_dbl) 1 << biL) - 1)
1064 r = ((t_dbl) 1 << biL) - 1;
1066 Z.p[i - t - 1] = (t_int) r;
1069 * __udiv_qrnnd_c, from gmp/longlong.h
1071 t_int q0, q1, r0, r1;
1075 d0 = ( d << biH ) >> biH;
1079 r1 = X.p[i] - d1 * q1;
1081 r1 |= ( X.p[i - 1] >> biH );
1087 while( r1 >= d && r1 < m )
1095 r0 |= ( X.p[i - 1] << biH ) >> biH;
1101 while( r0 >= d && r0 < m )
1106 Z.p[i - t - 1] = ( q1 << biH ) | q0;
1115 MPI_CHK( mpi_lset( &T1, 0 ) );
1116 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1118 MPI_CHK( mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1120 MPI_CHK( mpi_lset( &T2, 0 ) );
1121 T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1122 T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1125 while( mpi_cmp_mpi( &T1, &T2 ) > 0 );
1127 MPI_CHK( mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1128 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
1129 MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) );
1131 if( mpi_cmp_int( &X, 0 ) < 0 )
1133 MPI_CHK( mpi_copy( &T1, &Y ) );
1134 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
1135 MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) );
1148 mpi_shift_r( &X, k );
1152 if( mpi_cmp_int( R, 0 ) == 0 )
1158 mpi_free( &X, &Y, &Z, &T1, &T2, NULL );
1164 * Division by int: A = Q * b + R
1166 * Returns 0 if successful
1167 * 1 if memory allocation failed
1168 * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
1170 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, int b )
1175 p[0] = ( b < 0 ) ? -b : b;
1176 _B.s = ( b < 0 ) ? -1 : 1;
1180 return( mpi_div_mpi( Q, R, A, &_B ) );
1184 * Modulo: R = A mod B
1186 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B )
1190 if( mpi_cmp_int( B, 0 ) < 0 )
1191 return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
1193 MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
1195 while( mpi_cmp_int( R, 0 ) < 0 )
1196 MPI_CHK( mpi_add_mpi( R, R, B ) );
1198 while( mpi_cmp_mpi( R, B ) >= 0 )
1199 MPI_CHK( mpi_sub_mpi( R, R, B ) );
1207 * Modulo: r = A mod b
1209 int mpi_mod_int( t_int *r, const mpi *A, int b )
1215 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
1218 return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
1221 * handle trivial cases
1238 for( i = A->n - 1, y = 0; i >= 0; i-- )
1241 y = ( y << biH ) | ( x >> biH );
1246 y = ( y << biH ) | ( x >> biH );
1252 * If A is negative, then the current y represents a negative value.
1253 * Flipping it to the positive side.
1255 if( A->s < 0 && y != 0 )
1264 * Fast Montgomery initialization (thanks to Tom St Denis)
1266 static void mpi_montg_init( t_int *mm, const mpi *N )
1268 t_int x, m0 = N->p[0];
1271 x += ( ( m0 + 2 ) & 4 ) << 1;
1272 x *= ( 2 - ( m0 * x ) );
1274 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
1275 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
1276 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
1282 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1284 static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_int mm, const mpi *T )
1289 memset( T->p, 0, T->n * ciL );
1293 m = ( B->n < n ) ? B->n : n;
1295 for( i = 0; i < n; i++ )
1298 * T = (T + u0*B + u1*N) / 2^biL
1301 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1303 mpi_mul_hlp( m, B->p, d, u0 );
1304 mpi_mul_hlp( n, N->p, d, u1 );
1306 *d++ = u0; d[n + 1] = 0;
1309 memcpy( A->p, d, (n + 1) * ciL );
1311 if( mpi_cmp_abs( A, N ) >= 0 )
1312 mpi_sub_hlp( n, N->p, A->p );
1314 /* prevent timing attacks */
1315 mpi_sub_hlp( n, A->p, T->p );
1319 * Montgomery reduction: A = A * R^-1 mod N
1321 static void mpi_montred( mpi *A, const mpi *N, t_int mm, const mpi *T )
1329 mpi_montmul( A, &U, N, mm, T );
1333 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1335 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR )
1337 int ret, i, j, wsize, wbits;
1338 int bufsize, nblimbs, nbits;
1339 t_int ei, mm, state;
1342 if( mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
1343 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1346 * Init temps and window size
1348 mpi_montg_init( &mm, N );
1349 mpi_init( &RR, &T, NULL );
1350 memset( W, 0, sizeof( W ) );
1354 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1355 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1358 MPI_CHK( mpi_grow( X, j ) );
1359 MPI_CHK( mpi_grow( &W[1], j ) );
1360 MPI_CHK( mpi_grow( &T, j * 2 ) );
1363 * If 1st call, pre-compute R^2 mod N
1365 if( _RR == NULL || _RR->p == NULL )
1367 MPI_CHK( mpi_lset( &RR, 1 ) );
1368 MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) );
1369 MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) );
1372 memcpy( _RR, &RR, sizeof( mpi ) );
1375 memcpy( &RR, _RR, sizeof( mpi ) );
1378 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1380 if( mpi_cmp_mpi( A, N ) >= 0 )
1381 mpi_mod_mpi( &W[1], A, N );
1382 else mpi_copy( &W[1], A );
1384 mpi_montmul( &W[1], &RR, N, mm, &T );
1387 * X = R^2 * R^-1 mod N = R mod N
1389 MPI_CHK( mpi_copy( X, &RR ) );
1390 mpi_montred( X, N, mm, &T );
1395 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1397 j = 1 << (wsize - 1);
1399 MPI_CHK( mpi_grow( &W[j], N->n + 1 ) );
1400 MPI_CHK( mpi_copy( &W[j], &W[1] ) );
1402 for( i = 0; i < wsize - 1; i++ )
1403 mpi_montmul( &W[j], &W[j], N, mm, &T );
1406 * W[i] = W[i - 1] * W[1]
1408 for( i = j + 1; i < (1 << wsize); i++ )
1410 MPI_CHK( mpi_grow( &W[i], N->n + 1 ) );
1411 MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) );
1413 mpi_montmul( &W[i], &W[1], N, mm, &T );
1427 if( nblimbs-- == 0 )
1430 bufsize = sizeof( t_int ) << 3;
1435 ei = (E->p[nblimbs] >> bufsize) & 1;
1440 if( ei == 0 && state == 0 )
1443 if( ei == 0 && state == 1 )
1446 * out of window, square X
1448 mpi_montmul( X, X, N, mm, &T );
1453 * add ei to current window
1458 wbits |= (ei << (wsize - nbits));
1460 if( nbits == wsize )
1463 * X = X^wsize R^-1 mod N
1465 for( i = 0; i < wsize; i++ )
1466 mpi_montmul( X, X, N, mm, &T );
1469 * X = X * W[wbits] R^-1 mod N
1471 mpi_montmul( X, &W[wbits], N, mm, &T );
1480 * process the remaining bits
1482 for( i = 0; i < nbits; i++ )
1484 mpi_montmul( X, X, N, mm, &T );
1488 if( (wbits & (1 << wsize)) != 0 )
1489 mpi_montmul( X, &W[1], N, mm, &T );
1493 * X = A^E * R * R^-1 mod N = A^E mod N
1495 mpi_montred( X, N, mm, &T );
1499 for( i = (1 << (wsize - 1)); i < (1 << wsize); i++ )
1500 mpi_free( &W[i], NULL );
1503 mpi_free( &W[1], &T, NULL );
1504 else mpi_free( &W[1], &T, &RR, NULL );
1510 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1512 int mpi_gcd( mpi *G, const mpi *A, const mpi *B )
1517 mpi_init( &TG, &TA, &TB, NULL );
1519 MPI_CHK( mpi_copy( &TA, A ) );
1520 MPI_CHK( mpi_copy( &TB, B ) );
1522 lz = mpi_lsb( &TA );
1523 lzt = mpi_lsb( &TB );
1528 MPI_CHK( mpi_shift_r( &TA, lz ) );
1529 MPI_CHK( mpi_shift_r( &TB, lz ) );
1533 while( mpi_cmp_int( &TA, 0 ) != 0 )
1535 MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) );
1536 MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) );
1538 if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
1540 MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
1541 MPI_CHK( mpi_shift_r( &TA, 1 ) );
1545 MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
1546 MPI_CHK( mpi_shift_r( &TB, 1 ) );
1550 MPI_CHK( mpi_shift_l( &TB, lz ) );
1551 MPI_CHK( mpi_copy( G, &TB ) );
1555 mpi_free( &TB, &TA, &TG, NULL );
1560 #if defined(POLARSSL_GENPRIME)
1563 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1565 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N )
1568 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1570 if( mpi_cmp_int( N, 0 ) <= 0 )
1571 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1573 mpi_init( &TA, &TU, &U1, &U2, &G,
1574 &TB, &TV, &V1, &V2, NULL );
1576 MPI_CHK( mpi_gcd( &G, A, N ) );
1578 if( mpi_cmp_int( &G, 1 ) != 0 )
1580 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
1584 MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
1585 MPI_CHK( mpi_copy( &TU, &TA ) );
1586 MPI_CHK( mpi_copy( &TB, N ) );
1587 MPI_CHK( mpi_copy( &TV, N ) );
1589 MPI_CHK( mpi_lset( &U1, 1 ) );
1590 MPI_CHK( mpi_lset( &U2, 0 ) );
1591 MPI_CHK( mpi_lset( &V1, 0 ) );
1592 MPI_CHK( mpi_lset( &V2, 1 ) );
1596 while( ( TU.p[0] & 1 ) == 0 )
1598 MPI_CHK( mpi_shift_r( &TU, 1 ) );
1600 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1602 MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
1603 MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
1606 MPI_CHK( mpi_shift_r( &U1, 1 ) );
1607 MPI_CHK( mpi_shift_r( &U2, 1 ) );
1610 while( ( TV.p[0] & 1 ) == 0 )
1612 MPI_CHK( mpi_shift_r( &TV, 1 ) );
1614 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1616 MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
1617 MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
1620 MPI_CHK( mpi_shift_r( &V1, 1 ) );
1621 MPI_CHK( mpi_shift_r( &V2, 1 ) );
1624 if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
1626 MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
1627 MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
1628 MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
1632 MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
1633 MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
1634 MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
1637 while( mpi_cmp_int( &TU, 0 ) != 0 );
1639 while( mpi_cmp_int( &V1, 0 ) < 0 )
1640 MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
1642 while( mpi_cmp_mpi( &V1, N ) >= 0 )
1643 MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
1645 MPI_CHK( mpi_copy( X, &V1 ) );
1649 mpi_free( &V2, &V1, &TV, &TB, &G,
1650 &U2, &U1, &TU, &TA, NULL );
1655 static const int small_prime[] =
1657 3, 5, 7, 11, 13, 17, 19, 23,
1658 29, 31, 37, 41, 43, 47, 53, 59,
1659 61, 67, 71, 73, 79, 83, 89, 97,
1660 101, 103, 107, 109, 113, 127, 131, 137,
1661 139, 149, 151, 157, 163, 167, 173, 179,
1662 181, 191, 193, 197, 199, 211, 223, 227,
1663 229, 233, 239, 241, 251, 257, 263, 269,
1664 271, 277, 281, 283, 293, 307, 311, 313,
1665 317, 331, 337, 347, 349, 353, 359, 367,
1666 373, 379, 383, 389, 397, 401, 409, 419,
1667 421, 431, 433, 439, 443, 449, 457, 461,
1668 463, 467, 479, 487, 491, 499, 503, 509,
1669 521, 523, 541, 547, 557, 563, 569, 571,
1670 577, 587, 593, 599, 601, 607, 613, 617,
1671 619, 631, 641, 643, 647, 653, 659, 661,
1672 673, 677, 683, 691, 701, 709, 719, 727,
1673 733, 739, 743, 751, 757, 761, 769, 773,
1674 787, 797, 809, 811, 821, 823, 827, 829,
1675 839, 853, 857, 859, 863, 877, 881, 883,
1676 887, 907, 911, 919, 929, 937, 941, 947,
1677 953, 967, 971, 977, 983, 991, 997, -103
1681 * Miller-Rabin primality test (HAC 4.24)
1683 int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng )
1685 int ret, i, j, n, s, xs;
1689 if( mpi_cmp_int( X, 0 ) == 0 ||
1690 mpi_cmp_int( X, 1 ) == 0 )
1691 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1693 if( mpi_cmp_int( X, 2 ) == 0 )
1696 mpi_init( &W, &R, &T, &A, &RR, NULL );
1698 xs = X->s; X->s = 1;
1701 * test trivial factors first
1703 if( ( X->p[0] & 1 ) == 0 )
1704 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1706 for( i = 0; small_prime[i] > 0; i++ )
1710 if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
1713 MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
1716 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1723 MPI_CHK( mpi_sub_int( &W, X, 1 ) );
1725 MPI_CHK( mpi_copy( &R, &W ) );
1726 MPI_CHK( mpi_shift_r( &R, s ) );
1732 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1733 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1734 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1736 for( i = 0; i < n; i++ )
1739 * pick a random A, 1 < A < |X| - 1
1741 MPI_CHK( mpi_grow( &A, X->n ) );
1743 p = (unsigned char *) A.p;
1744 for( j = 0; j < A.n * ciL; j++ )
1745 *p++ = (unsigned char) f_rng( p_rng );
1747 j = mpi_msb( &A ) - mpi_msb( &W );
1748 MPI_CHK( mpi_shift_r( &A, j + 1 ) );
1754 MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
1756 if( mpi_cmp_mpi( &A, &W ) == 0 ||
1757 mpi_cmp_int( &A, 1 ) == 0 )
1761 while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
1766 MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
1767 MPI_CHK( mpi_mod_mpi( &A, &T, X ) );
1769 if( mpi_cmp_int( &A, 1 ) == 0 )
1776 * not prime if A != |X| - 1 or A == 1
1778 if( mpi_cmp_mpi( &A, &W ) != 0 ||
1779 mpi_cmp_int( &A, 1 ) == 0 )
1781 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
1790 mpi_free( &RR, &A, &T, &R, &W, NULL );
1796 * Prime number generation
1798 int mpi_gen_prime( mpi *X, int nbits, int dh_flag,
1799 int (*f_rng)(void *), void *p_rng )
1806 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1808 mpi_init( &Y, NULL );
1810 n = BITS_TO_LIMBS( nbits );
1812 MPI_CHK( mpi_grow( X, n ) );
1813 MPI_CHK( mpi_lset( X, 0 ) );
1815 p = (unsigned char *) X->p;
1816 for( k = 0; k < X->n * ciL; k++ )
1817 *p++ = (unsigned char) f_rng( p_rng );
1820 if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) );
1821 if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits ) );
1827 while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1829 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1832 MPI_CHK( mpi_add_int( X, X, 2 ) );
1837 MPI_CHK( mpi_sub_int( &Y, X, 1 ) );
1838 MPI_CHK( mpi_shift_r( &Y, 1 ) );
1842 if( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) == 0 )
1844 if( ( ret = mpi_is_prime( &Y, f_rng, p_rng ) ) == 0 )
1847 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1851 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1854 MPI_CHK( mpi_add_int( &Y, X, 1 ) );
1855 MPI_CHK( mpi_add_int( X, X, 2 ) );
1856 MPI_CHK( mpi_shift_r( &Y, 1 ) );
1862 mpi_free( &Y, NULL );