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

diff --git a/src/src/pdkim/bignum.c b/src/src/pdkim/bignum.c
index e4fc92d2c..b55c2b8ff 100644
--- a/src/src/pdkim/bignum.c
+++ b/src/src/pdkim/bignum.c
@@ -1,10 +1,12 @@
 /*
  *  Multi-precision integer library
  *
- *  Copyright (C) 2006-2009, Paul Bakker <polarssl_maintainer at polarssl.org>
- *  All rights reserved.
+ *  Copyright (C) 2006-2010, Brainspark B.V.
+ *
+ *  This file is part of PolarSSL (http://www.polarssl.org)
+ *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
  *
- *  Joined copyright on original XySSL code with: Christophe Devine
+ *  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
@@ -28,11 +30,12 @@
  *  http://math.libtomcrypt.com/files/tommath.pdf
  */
 
-/* $Cambridge: exim/src/src/pdkim/bignum.c,v 1.3 2009/12/07 13:05:07 tom Exp $ */
+#include "polarssl/config.h"
 
+#if defined(POLARSSL_BIGNUM_C)
 
-#include "bignum.h"
-#include "bn_mul.h"
+#include "polarssl/bignum.h"
+#include "polarssl/bn_mul.h"
 
 #include <string.h>
 #include <stdlib.h>
@@ -127,7 +130,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;
 
@@ -184,7 +187,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;
 
@@ -199,7 +202,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;
 
@@ -217,7 +220,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 );
 }
@@ -242,9 +245,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;
 
@@ -253,14 +256,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] == '-' )
             {
@@ -276,7 +281,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] == '-' )
             {
@@ -335,7 +340,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;
@@ -428,12 +433,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 );
@@ -465,7 +470,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;
 
@@ -487,7 +492,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;
 
@@ -596,7 +601,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;
 
@@ -626,7 +631,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;
 
@@ -659,7 +664,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];
@@ -675,14 +680,14 @@ 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 )
@@ -747,7 +752,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;
@@ -789,7 +794,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;
 
@@ -820,7 +825,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;
 
@@ -851,7 +856,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];
@@ -867,7 +872,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];
@@ -947,7 +952,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;
@@ -983,7 +988,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];
@@ -999,7 +1004,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;
@@ -1164,7 +1169,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];
@@ -1180,7 +1185,7 @@ 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;
 
@@ -1203,7 +1208,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;
@@ -1260,7 +1265,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];
 
@@ -1278,7 +1283,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;
@@ -1315,7 +1320,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;
@@ -1329,7 +1334,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;
@@ -1506,7 +1511,7 @@ 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, lz, lzt;
     mpi TG, TA, TB;
@@ -1559,7 +1564,7 @@ cleanup:
 /*
  * 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;
@@ -1717,8 +1722,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 ) );
 
@@ -1862,3 +1867,172 @@ cleanup:
 }
 
 #endif
+
+#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, i;
+    mpi A, E, N, X, Y, U, V;
+
+    mpi_init( &A, &E, &N, &X, &Y, &U, &V, NULL );
+
+    MPI_CHK( mpi_read_string( &A, 16,
+        "EFE021C2645FD1DC586E69184AF4A31E" \
+        "D5F53E93B5F123FA41680867BA110131" \
+        "944FE7952E2517337780CB0DB80E61AA" \
+        "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
+
+    MPI_CHK( mpi_read_string( &E, 16,
+        "B2E7EFD37075B9F03FF989C7C5051C20" \
+        "34D2A323810251127E7BF8625A4F49A5" \
+        "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
+        "5B5C25763222FEFCCFC38B832366C29E" ) );
+
+    MPI_CHK( mpi_read_string( &N, 16,
+        "0066A198186C18C10B2F5ED9B522752A" \
+        "9830B69916E535C8F047518A889A43A5" \
+        "94B6BED27A168D31D4A52F88925AA8F5" ) );
+
+    MPI_CHK( mpi_mul_mpi( &X, &A, &N ) );
+
+    MPI_CHK( mpi_read_string( &U, 16,
+        "602AB7ECA597A3D6B56FF9829A5E8B85" \
+        "9E857EA95A03512E2BAE7391688D264A" \
+        "A5663B0341DB9CCFD2C4C5F421FEC814" \
+        "8001B72E848A38CAE1C65F78E56ABDEF" \
+        "E12D3C039B8A02D6BE593F0BBBDA56F1" \
+        "ECF677152EF804370C1A305CAF3B5BF1" \
+        "30879B56C61DE584A0F53A2447A51E" ) );
+
+    if( verbose != 0 )
+        printf( "  MPI test #1 (mul_mpi): " );
+
+    if( mpi_cmp_mpi( &X, &U ) != 0 )
+    {
+        if( verbose != 0 )
+            printf( "failed\n" );
+
+        return( 1 );
+    }
+
+    if( verbose != 0 )
+        printf( "passed\n" );
+
+    MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
+
+    MPI_CHK( mpi_read_string( &U, 16,
+        "256567336059E52CAE22925474705F39A94" ) );
+
+    MPI_CHK( mpi_read_string( &V, 16,
+        "6613F26162223DF488E9CD48CC132C7A" \
+        "0AC93C701B001B092E4E5B9F73BCD27B" \
+        "9EE50D0657C77F374E903CDFA4C642" ) );
+
+    if( verbose != 0 )
+        printf( "  MPI test #2 (div_mpi): " );
+
+    if( mpi_cmp_mpi( &X, &U ) != 0 ||
+        mpi_cmp_mpi( &Y, &V ) != 0 )
+    {
+        if( verbose != 0 )
+            printf( "failed\n" );
+
+        return( 1 );
+    }
+
+    if( verbose != 0 )
+        printf( "passed\n" );
+
+    MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) );
+
+    MPI_CHK( mpi_read_string( &U, 16,
+        "36E139AEA55215609D2816998ED020BB" \
+        "BD96C37890F65171D948E9BC7CBAA4D9" \
+        "325D24D6A3C12710F10A09FA08AB87" ) );
+
+    if( verbose != 0 )
+        printf( "  MPI test #3 (exp_mod): " );
+
+    if( mpi_cmp_mpi( &X, &U ) != 0 )
+    {
+        if( verbose != 0 )
+            printf( "failed\n" );
+
+        return( 1 );
+    }
+
+    if( verbose != 0 )
+        printf( "passed\n" );
+
+    MPI_CHK( mpi_inv_mod( &X, &A, &N ) );
+
+    MPI_CHK( mpi_read_string( &U, 16,
+        "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
+        "C3DBA76456363A10869622EAC2DD84EC" \
+        "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
+
+    if( verbose != 0 )
+        printf( "  MPI test #4 (inv_mod): " );
+
+    if( mpi_cmp_mpi( &X, &U ) != 0 )
+    {
+        if( verbose != 0 )
+            printf( "failed\n" );
+
+        return( 1 );
+    }
+
+    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 )
+        printf( "Unexpected error, return code = %08X\n", ret );
+
+    mpi_free( &V, &U, &Y, &X, &N, &E, &A, NULL );
+
+    if( verbose != 0 )
+        printf( "\n" );
+
+    return( ret );
+}
+
+#endif
+
+#endif