X-Git-Url: https://git.exim.org/exim.git/blobdiff_plain/80a47a2c9633437d4ceebd214cd44abfbd4f4543..62d3e98d02a82d430436431b138ea74658ec23a9:/src/src/pdkim/bignum.c

diff --git a/src/src/pdkim/bignum.c b/src/src/pdkim/bignum.c
index 23d79968c..fd3b66a44 100644
--- a/src/src/pdkim/bignum.c
+++ b/src/src/pdkim/bignum.c
@@ -1,9 +1,12 @@
 /*
  *  Multi-precision integer library
  *
- *  Based on XySSL: Copyright (C) 2006-2008  Christophe Devine
+ *  Copyright (C) 2006-2010, Brainspark B.V.
  *
- *  Copyright (C) 2009  Paul Bakker <polarssl_maintainer at polarssl dot org>
+ *  This file is part of PolarSSL (http://www.polarssl.org)
+ *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
+ *
+ *  All rights reserved.
  *
  *  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 +30,7 @@
  *  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"
@@ -125,7 +128,7 @@ int mpi_grow( mpi *X, int nblimbs )
 /*
  * Copy the contents of Y into X
  */
-int mpi_copy( mpi *X, mpi *Y )
+int mpi_copy( mpi *X, const mpi *Y )
 {
     int ret, i;
 
@@ -182,7 +185,7 @@ cleanup:
 /*
  * Return the number of least significant bits
  */
-int mpi_lsb( mpi *X )
+int mpi_lsb( const mpi *X )
 {
     int i, j, count = 0;
 
@@ -197,7 +200,7 @@ int mpi_lsb( mpi *X )
 /*
  * Return the number of most significant bits
  */
-int mpi_msb( mpi *X )
+int mpi_msb( const mpi *X )
 {
     int i, j;
 
@@ -215,7 +218,7 @@ int mpi_msb( mpi *X )
 /*
  * Return the total size in bytes
  */
-int mpi_size( mpi *X )
+int mpi_size( const mpi *X )
 {
     return( ( mpi_msb( X ) + 7 ) >> 3 );
 }
@@ -240,9 +243,9 @@ static int mpi_get_digit( t_int *d, int radix, char c )
 /*
  * Import from an ASCII string
  */
-int mpi_read_string( mpi *X, int radix, char *s )
+int mpi_read_string( mpi *X, int radix, const char *s )
 {
-    int ret, i, j, n;
+    int ret, i, j, n, slen;
     t_int d;
     mpi T;
 
@@ -251,14 +254,16 @@ int mpi_read_string( mpi *X, int radix, char *s )
 
     mpi_init( &T, NULL );
 
+    slen = strlen( s );
+
     if( radix == 16 )
     {
-        n = BITS_TO_LIMBS( strlen( s ) << 2 );
+        n = BITS_TO_LIMBS( slen << 2 );
 
         MPI_CHK( mpi_grow( X, n ) );
         MPI_CHK( mpi_lset( X, 0 ) );
 
-        for( i = strlen( s ) - 1, j = 0; i >= 0; i--, j++ )
+        for( i = slen - 1, j = 0; i >= 0; i--, j++ )
         {
             if( i == 0 && s[i] == '-' )
             {
@@ -274,7 +279,7 @@ int mpi_read_string( mpi *X, int radix, char *s )
     {
         MPI_CHK( mpi_lset( X, 0 ) );
 
-        for( i = 0; i < (int) strlen( s ); i++ )
+        for( i = 0; i < slen; i++ )
         {
             if( i == 0 && s[i] == '-' )
             {
@@ -284,7 +289,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 ) );
+            }
         }
     }
 
@@ -325,7 +338,7 @@ cleanup:
 /*
  * Export into an ASCII string
  */
-int mpi_write_string( mpi *X, int radix, char *s, int *slen )
+int mpi_write_string( const mpi *X, int radix, char *s, int *slen )
 {
     int ret = 0, n;
     char *p;
@@ -372,6 +385,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 ) );
     }
 
@@ -414,12 +431,12 @@ int mpi_read_file( mpi *X, int radix, FILE *fin )
 /*
  * Write X into an opened file (or stdout if fout == NULL)
  */
-int mpi_write_file( char *p, mpi *X, int radix, FILE *fout )
+int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout )
 {
     int n, ret;
     size_t slen;
     size_t plen;
-    char s[1024];
+    char s[2048];
 
     n = sizeof( s );
     memset( s, 0, n );
@@ -451,7 +468,7 @@ cleanup:
 /*
  * Import X from unsigned binary data, big endian
  */
-int mpi_read_binary( mpi *X, unsigned char *buf, int buflen )
+int mpi_read_binary( mpi *X, const unsigned char *buf, int buflen )
 {
     int ret, i, j, n;
 
@@ -473,7 +490,7 @@ cleanup:
 /*
  * Export X into unsigned binary data, big endian
  */
-int mpi_write_binary( mpi *X, unsigned char *buf, int buflen )
+int mpi_write_binary( const mpi *X, unsigned char *buf, int buflen )
 {
     int i, j, n;
 
@@ -582,7 +599,7 @@ int mpi_shift_r( mpi *X, int count )
 /*
  * Compare unsigned values
  */
-int mpi_cmp_abs( mpi *X, mpi *Y )
+int mpi_cmp_abs( const mpi *X, const mpi *Y )
 {
     int i, j;
 
@@ -612,7 +629,7 @@ int mpi_cmp_abs( mpi *X, mpi *Y )
 /*
  * Compare signed values
  */
-int mpi_cmp_mpi( mpi *X, mpi *Y )
+int mpi_cmp_mpi( const mpi *X, const mpi *Y )
 {
     int i, j;
 
@@ -645,7 +662,7 @@ int mpi_cmp_mpi( mpi *X, mpi *Y )
 /*
  * Compare signed values
  */
-int mpi_cmp_int( mpi *X, int z )
+int mpi_cmp_int( const mpi *X, int z )
 {
     mpi Y;
     t_int p[1];
@@ -661,19 +678,24 @@ int mpi_cmp_int( mpi *X, int z )
 /*
  * Unsigned addition: X = |A| + |B|  (HAC 14.7)
  */
-int mpi_add_abs( mpi *X, mpi *A, mpi *B )
+int mpi_add_abs( mpi *X, const mpi *A, const mpi *B )
 {
     int ret, i, j;
     t_int *o, *p, c;
 
     if( X == B )
     {
-        mpi *T = A; A = X; B = T;
+        const mpi *T = A; A = X; B = T;
     }
 
     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;
@@ -728,7 +750,7 @@ static void mpi_sub_hlp( int n, t_int *s, t_int *d )
 /*
  * Unsigned substraction: X = |A| - |B|  (HAC 14.9)
  */
-int mpi_sub_abs( mpi *X, mpi *A, mpi *B )
+int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B )
 {
     mpi TB;
     int ret, n;
@@ -747,6 +769,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-- )
@@ -765,7 +792,7 @@ cleanup:
 /*
  * Signed addition: X = A + B
  */
-int mpi_add_mpi( mpi *X, mpi *A, mpi *B )
+int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B )
 {
     int ret, s = A->s;
 
@@ -796,7 +823,7 @@ cleanup:
 /*
  * Signed substraction: X = A - B
  */
-int mpi_sub_mpi( mpi *X, mpi *A, mpi *B )
+int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B )
 {
     int ret, s = A->s;
 
@@ -827,7 +854,7 @@ cleanup:
 /*
  * Signed addition: X = A + b
  */
-int mpi_add_int( mpi *X, mpi *A, int b )
+int mpi_add_int( mpi *X, const mpi *A, int b )
 {
     mpi _B;
     t_int p[1];
@@ -843,7 +870,7 @@ int mpi_add_int( mpi *X, mpi *A, int b )
 /*
  * Signed substraction: X = A - b
  */
-int mpi_sub_int( mpi *X, mpi *A, int b )
+int mpi_sub_int( mpi *X, const mpi *A, int b )
 {
     mpi _B;
     t_int p[1];
@@ -923,7 +950,7 @@ static void mpi_mul_hlp( int i, t_int *s, t_int *d, t_int b )
 /*
  * Baseline multiplication: X = A * B  (HAC 14.12)
  */
-int mpi_mul_mpi( mpi *X, mpi *A, mpi *B )
+int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B )
 {
     int ret, i, j;
     mpi TA, TB;
@@ -959,7 +986,7 @@ cleanup:
 /*
  * Baseline multiplication: X = A * b
  */
-int mpi_mul_int( mpi *X, mpi *A, t_int b )
+int mpi_mul_int( mpi *X, const mpi *A, t_int b )
 {
     mpi _B;
     t_int p[1];
@@ -975,7 +1002,7 @@ int mpi_mul_int( mpi *X, mpi *A, t_int b )
 /*
  * Division by mpi: A = Q * B + R  (HAC 14.20)
  */
-int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B )
+int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B )
 {
     int ret, i, n, t, k;
     mpi X, Y, Z, T1, T2;
@@ -1140,7 +1167,7 @@ cleanup:
  *         1 if memory allocation failed
  *         POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
  */
-int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b )
+int mpi_div_int( mpi *Q, mpi *R, const mpi *A, int b )
 {
     mpi _B;
     t_int p[1];
@@ -1156,10 +1183,13 @@ int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b )
 /*
  * Modulo: R = A mod B
  */
-int mpi_mod_mpi( mpi *R, mpi *A, mpi *B )
+int mpi_mod_mpi( mpi *R, const mpi *A, const 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 )
@@ -1176,7 +1206,7 @@ cleanup:
 /*
  * Modulo: r = A mod b
  */
-int mpi_mod_int( t_int *r, mpi *A, int b )
+int mpi_mod_int( t_int *r, const mpi *A, int b )
 {
     int i;
     t_int x, y, z;
@@ -1185,7 +1215,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 +1248,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 );
@@ -1226,7 +1263,7 @@ int mpi_mod_int( t_int *r, mpi *A, int b )
 /*
  * Fast Montgomery initialization (thanks to Tom St Denis)
  */
-static void mpi_montg_init( t_int *mm, mpi *N )
+static void mpi_montg_init( t_int *mm, const mpi *N )
 {
     t_int x, m0 = N->p[0];
 
@@ -1244,7 +1281,7 @@ static void mpi_montg_init( t_int *mm, mpi *N )
 /*
  * Montgomery multiplication: A = A * B * R^-1 mod N  (HAC 14.36)
  */
-static void mpi_montmul( mpi *A, mpi *B, mpi *N, t_int mm, mpi *T )
+static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_int mm, const mpi *T )
 {
     int i, n, m;
     t_int u0, u1, *d;
@@ -1281,7 +1318,7 @@ static void mpi_montmul( mpi *A, mpi *B, mpi *N, t_int mm, mpi *T )
 /*
  * Montgomery reduction: A = A * R^-1 mod N
  */
-static void mpi_montred( mpi *A, mpi *N, t_int mm, mpi *T )
+static void mpi_montred( mpi *A, const mpi *N, t_int mm, const mpi *T )
 {
     t_int z = 1;
     mpi U;
@@ -1295,7 +1332,7 @@ static void mpi_montred( mpi *A, mpi *N, t_int mm, mpi *T )
 /*
  * Sliding-window exponentiation: X = A^E mod N  (HAC 14.85)
  */
-int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR )
+int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR )
 {
     int ret, i, j, wsize, wbits;
     int bufsize, nblimbs, nbits;
@@ -1472,23 +1509,31 @@ cleanup:
 /*
  * Greatest common divisor: G = gcd(A, B)  (HAC 14.54)
  */
-int mpi_gcd( mpi *G, mpi *A, mpi *B )
+int mpi_gcd( mpi *G, const mpi *A, const 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 +1547,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,10 +1557,12 @@ cleanup:
     return( ret );
 }
 
+#if defined(POLARSSL_GENPRIME)
+
 /*
  * Modular inverse: X = A^-1 mod N  (HAC 14.61 / 14.64)
  */
-int mpi_inv_mod( mpi *X, mpi *A, mpi *N )
+int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N )
 {
     int ret;
     mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
@@ -1638,7 +1686,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 );
@@ -1668,8 +1720,8 @@ int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng )
      * W = |X| - 1
      * R = W >> lsb( W )
      */
-    s = mpi_lsb( &W );
     MPI_CHK( mpi_sub_int( &W, X, 1 ) );
+    s = mpi_lsb( &W );
     MPI_CHK( mpi_copy( &R, &W ) );
     MPI_CHK( mpi_shift_r( &R, s ) );
 
@@ -1811,3 +1863,5 @@ cleanup:
 
     return( ret );
 }
+
+#endif