X-Git-Url: https://git.exim.org/exim.git/blobdiff_plain/2f1c4d4cc07565389135d9ecaa8390b46d043d86..67932e542eb65f681779f5d49974afe8369a9b9a:/src/src/pdkim/bignum.c

diff --git a/src/src/pdkim/bignum.c b/src/src/pdkim/bignum.c
index 23d79968c..e4fc92d2c 100644
--- a/src/src/pdkim/bignum.c
+++ b/src/src/pdkim/bignum.c
@@ -1,9 +1,10 @@
 /*
  *  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
@@ -27,7 +28,8 @@
  *  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"
@@ -284,7 +286,15 @@ int mpi_read_string( mpi *X, int radix, char *s )
 
             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 ) );
+            }
         }
     }
 
@@ -372,6 +382,10 @@ int mpi_write_string( mpi *X, int radix, char *s, int *slen )
     else
     {
         MPI_CHK( mpi_copy( &T, X ) );
+
+        if( T.s == -1 )
+            T.s = 1;
+
         MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
     }
 
@@ -674,6 +688,11 @@ int mpi_add_abs( mpi *X, mpi *A, mpi *B )
     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;
@@ -747,6 +766,11 @@ int mpi_sub_abs( mpi *X, mpi *A, mpi *B )
     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-- )
@@ -1160,6 +1184,9 @@ int mpi_mod_mpi( mpi *R, mpi *A, mpi *B )
 {
     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 )
@@ -1185,7 +1212,7 @@ int mpi_mod_int( t_int *r, mpi *A, int b )
         return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
 
     if( b < 0 )
-        b = -b;
+        return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
 
     /*
      * handle trivial cases
@@ -1218,6 +1245,13 @@ int mpi_mod_int( t_int *r, mpi *A, int b )
         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 );
@@ -1474,21 +1508,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 )
         {
@@ -1502,7 +1544,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:
 
@@ -1511,6 +1554,8 @@ cleanup:
     return( ret );
 }
 
+#if defined(POLARSSL_GENPRIME)
+
 /*
  * Modular inverse: X = A^-1 mod N  (HAC 14.61 / 14.64)
  */
@@ -1638,7 +1683,11 @@ int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng )
     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 );
@@ -1811,3 +1860,5 @@ cleanup:
 
     return( ret );
 }
+
+#endif