/*
* 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
* 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>
/*
* 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;
/*
* Return the number of least significant bits
*/
-int mpi_lsb( mpi *X )
+int mpi_lsb( const mpi *X )
{
int i, j, count = 0;
/*
* Return the number of most significant bits
*/
-int mpi_msb( mpi *X )
+int mpi_msb( const mpi *X )
{
int i, j;
/*
* Return the total size in bytes
*/
-int mpi_size( mpi *X )
+int mpi_size( const mpi *X )
{
return( ( mpi_msb( X ) + 7 ) >> 3 );
}
/*
* 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;
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] == '-' )
{
{
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] == '-' )
{
/*
* 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;
/*
* Write X into an opened file (or stdout if fout == NULL)
*/
-int mpi_write_file( const 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 );
/*
* 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;
/*
* 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;
/*
* Compare unsigned values
*/
-int mpi_cmp_abs( mpi *X, mpi *Y )
+int mpi_cmp_abs( const mpi *X, const mpi *Y )
{
int i, j;
/*
* Compare signed values
*/
-int mpi_cmp_mpi( mpi *X, mpi *Y )
+int mpi_cmp_mpi( const mpi *X, const mpi *Y )
{
int i, j;
/*
* 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];
/*
* 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 )
/*
* 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;
/*
* 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;
/*
* 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;
/*
* 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];
/*
* 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];
/*
* 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;
/*
* 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];
/*
* 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;
* 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];
/*
* 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;
/*
* 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;
/*
* 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];
/*
* 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;
/*
* 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;
/*
* 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;
/*
* 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;
/*
* 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;
* 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 ) );
}
#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
git://git.exim.org / exim.git / blobdiff