/*
* Multi-precision integer library
*
- * Based on XySSL: Copyright (C) 2006-2008 Christophe Devine
+ * Copyright (C) 2006-2009, Paul Bakker <polarssl_maintainer at polarssl.org>
+ * All rights reserved.
*
- * Copyright (C) 2009 Paul Bakker <polarssl_maintainer at polarssl dot org>
+ * Joined copyright on original XySSL code with: Christophe Devine
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* http://math.libtomcrypt.com/files/tommath.pdf
*/
-/* $Cambridge: exim/src/src/pdkim/bignum.c,v 1.2 2009/06/10 07:34:05 tom Exp $ */
+/* $Cambridge: exim/src/src/pdkim/bignum.c,v 1.3 2009/12/07 13:05:07 tom Exp $ */
+
#include "bignum.h"
#include "bn_mul.h"
MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
MPI_CHK( mpi_mul_int( &T, X, radix ) );
- MPI_CHK( mpi_add_int( X, &T, d ) );
+
+ if( X->s == 1 )
+ {
+ MPI_CHK( mpi_add_int( X, &T, d ) );
+ }
+ else
+ {
+ MPI_CHK( mpi_sub_int( X, &T, d ) );
+ }
}
}
else
{
MPI_CHK( mpi_copy( &T, X ) );
+
+ if( T.s == -1 )
+ T.s = 1;
+
MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
}
if( X != A )
MPI_CHK( mpi_copy( X, A ) );
+ /*
+ * X should always be positive as a result of unsigned additions.
+ */
+ X->s = 1;
+
for( j = B->n - 1; j >= 0; j-- )
if( B->p[j] != 0 )
break;
if( X != A )
MPI_CHK( mpi_copy( X, A ) );
+ /*
+ * X should always be positive as a result of unsigned substractions.
+ */
+ X->s = 1;
+
ret = 0;
for( n = B->n - 1; n >= 0; n-- )
{
int ret;
+ if( mpi_cmp_int( B, 0 ) < 0 )
+ return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
+
MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
while( mpi_cmp_int( R, 0 ) < 0 )
return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
if( b < 0 )
- b = -b;
+ return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
/*
* handle trivial cases
y -= z * b;
}
+ /*
+ * If A is negative, then the current y represents a negative value.
+ * Flipping it to the positive side.
+ */
+ if( A->s < 0 && y != 0 )
+ y = b - y;
+
*r = y;
return( 0 );
*/
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 )
{
}
}
- MPI_CHK( mpi_mul_mpi( G, &TG, &TB ) );
+ MPI_CHK( mpi_shift_l( &TB, lz ) );
+ MPI_CHK( mpi_copy( G, &TB ) );
cleanup:
return( ret );
}
+#if defined(POLARSSL_GENPRIME)
+
/*
* Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
*/
mpi W, R, T, A, RR;
unsigned char *p;
- if( mpi_cmp_int( X, 0 ) == 0 )
+ if( mpi_cmp_int( X, 0 ) == 0 ||
+ mpi_cmp_int( X, 1 ) == 0 )
+ return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
+
+ if( mpi_cmp_int( X, 2 ) == 0 )
return( 0 );
mpi_init( &W, &R, &T, &A, &RR, NULL );
return( ret );
}
+
+#endif