diff options
author | Paul Bakker <p.j.bakker@polarssl.org> | 2009-01-29 22:24:33 +0000 |
---|---|---|
committer | Paul Bakker <p.j.bakker@polarssl.org> | 2009-01-29 22:24:33 +0000 |
commit | 4e0d7ca2331a07c263f9d2dded2e8bc2af69c918 (patch) | |
tree | 1e0f61df70a3c88c68403fcbf38dd383e38a2c7d | |
parent | 785a9eeecebbbb82f703ce6c5c22783d20f7322b (diff) | |
download | mbedtls-4e0d7ca2331a07c263f9d2dded2e8bc2af69c918.zip mbedtls-4e0d7ca2331a07c263f9d2dded2e8bc2af69c918.tar.gz mbedtls-4e0d7ca2331a07c263f9d2dded2e8bc2af69c918.tar.bz2 |
- Fixed a bug in mpi_gcd() that prevented correct funtioning when both input numbers are even.
-rw-r--r-- | ChangeLog | 8 | ||||
-rw-r--r-- | library/bignum.c | 52 |
2 files changed, 54 insertions, 6 deletions
@@ -1,5 +1,13 @@ PolarSSL ChangeLog
+= Version 0.10.2 released on 2009-XXXX
+ * Fixed a bug in mpi_gcd() so that it also works when both
+ input numbers are even and added testcases to check
+ (found by Pierre Habouzit)
+
+= Version 0.10.1 released on 2009-01-25
+ * Added BSD License
+
= Version 0.10.0 released on 2009-01-12
* Migrated XySSL to PolarSSL
* Added XTEA symmetric cipher
diff --git a/library/bignum.c b/library/bignum.c index 97d4d12..1685d30 100644 --- a/library/bignum.c +++ b/library/bignum.c @@ -1478,21 +1478,29 @@ cleanup: */ int mpi_gcd( mpi *G, mpi *A, mpi *B ) { - int ret; + int ret, lz, lzt; mpi TG, TA, TB; mpi_init( &TG, &TA, &TB, NULL ); - MPI_CHK( mpi_lset( &TG, 1 ) ); MPI_CHK( mpi_copy( &TA, A ) ); MPI_CHK( mpi_copy( &TB, B ) ); + lz = mpi_lsb( &TA ); + lzt = mpi_lsb( &TB ); + + if ( lzt < lz ) + lz = lzt; + + MPI_CHK( mpi_shift_r( &TA, lz ) ); + MPI_CHK( mpi_shift_r( &TB, lz ) ); + TA.s = TB.s = 1; while( mpi_cmp_int( &TA, 0 ) != 0 ) { - while( ( TA.p[0] & 1 ) == 0 ) MPI_CHK( mpi_shift_r( &TA, 1 ) ); - while( ( TB.p[0] & 1 ) == 0 ) MPI_CHK( mpi_shift_r( &TB, 1 ) ); + MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) ); + MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) ); if( mpi_cmp_mpi( &TA, &TB ) >= 0 ) { @@ -1506,7 +1514,8 @@ int mpi_gcd( mpi *G, mpi *A, mpi *B ) } } - MPI_CHK( mpi_mul_mpi( G, &TG, &TB ) ); + MPI_CHK( mpi_shift_l( &TB, lz ) ); + MPI_CHK( mpi_copy( G, &TB ) ); cleanup: @@ -1820,12 +1829,21 @@ cleanup: #if defined(POLARSSL_SELF_TEST) +#define GCD_PAIR_COUNT 3 + +static const int gcd_pairs[GCD_PAIR_COUNT][3] = +{ + { 693, 609, 21 }, + { 1764, 868, 28 }, + { 768454923, 542167814, 1 } +}; + /* * Checkup routine */ int mpi_self_test( int verbose ) { - int ret; + int ret, i; mpi A, E, N, X, Y, U, V; mpi_init( &A, &E, &N, &X, &Y, &U, &V, NULL ); @@ -1939,6 +1957,28 @@ int mpi_self_test( int verbose ) if( verbose != 0 ) printf( "passed\n" ); + if( verbose != 0 ) + printf( " MPI test #5 (simple gcd): " ); + + for ( i = 0; i < GCD_PAIR_COUNT; i++) + { + MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) ); + MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) ); + + MPI_CHK( mpi_gcd( &A, &X, &Y ) ); + + if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 ) + { + if( verbose != 0 ) + printf( "failed at %d\n", i ); + + return( 1 ); + } + } + + if( verbose != 0 ) + printf( "passed\n" ); + cleanup: if( ret != 0 && verbose != 0 ) |