/* *  Multi-precision integer library * *  Copyright (C) 2006-2007  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 *  the Free Software Foundation; either version 2 of the License, or *  (at your option) any later version. * *  This program is distributed in the hope that it will be useful, *  but WITHOUT ANY WARRANTY; without even the implied warranty of *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the *  GNU General Public License for more details. * *  You should have received a copy of the GNU General Public License along *  with this program; if not, write to the Free Software Foundation, Inc., *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. *//* *  This MPI implementation is based on: * *  http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf *  http://www.stillhq.com/extracted/gnupg-api/mpi/ *  http://math.libtomcrypt.com/files/tommath.pdf */#include "config.h"#if defined(XYSSL_BIGNUM_C)#include "bignum.h"#include "bn_mul.h"#include <string.h>#include <stdlib.h>#include <stdarg.h>#define ciL    ((int) sizeof(t_int))    /* chars in limb  */#define biL    (ciL << 3)               /* bits  in limb  */#define biH    (ciL << 2)               /* half limb size *//* * Convert between bits/chars and number of limbs */#define BITS_TO_LIMBS(i)  (((i) + biL - 1) / biL)#define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)/* * Initialize one or more mpi */void mpi_init( mpi *X, ... ){    va_list args;    va_start( args, X );    while( X != NULL )    {        X->s = 1;        X->n = 0;        X->p = NULL;        X = va_arg( args, mpi* );    }    va_end( args );}/* * Unallocate one or more mpi */void mpi_free( mpi *X, ... ){    va_list args;    va_start( args, X );    while( X != NULL )    {        if( X->p != NULL )        {            memset( X->p, 0, X->n * ciL );            free( X->p );        }        X->s = 1;        X->n = 0;        X->p = NULL;        X = va_arg( args, mpi* );    }    va_end( args );}/* * Enlarge to the specified number of limbs */int mpi_grow( mpi *X, int nblimbs ){    t_int *p;    if( X->n < nblimbs )    {        if( ( p = (t_int *) malloc( nblimbs * ciL ) ) == NULL )            return( 1 );        memset( p, 0, nblimbs * ciL );        if( X->p != NULL )        {            memcpy( p, X->p, X->n * ciL );            memset( X->p, 0, X->n * ciL );            free( X->p );        }        X->n = nblimbs;        X->p = p;    }    return( 0 );}/* * Copy the contents of Y into X */int mpi_copy( mpi *X, mpi *Y ){    int ret, i;    if( X == Y )        return( 0 );    for( i = Y->n - 1; i > 0; i-- )        if( Y->p[i] != 0 )            break;    i++;    X->s = Y->s;    MPI_CHK( mpi_grow( X, i ) );    memset( X->p, 0, X->n * ciL );    memcpy( X->p, Y->p, i * ciL );cleanup:    return( ret );}/* * Swap the contents of X and Y */void mpi_swap( mpi *X, mpi *Y ){    mpi T;    memcpy( &T,  X, sizeof( mpi ) );    memcpy(  X,  Y, sizeof( mpi ) );    memcpy(  Y, &T, sizeof( mpi ) );}/* * Set value from integer */int mpi_lset( mpi *X, int z ){    int ret;    MPI_CHK( mpi_grow( X, 1 ) );    memset( X->p, 0, X->n * ciL );    X->p[0] = ( z < 0 ) ? -z : z;    X->s    = ( z < 0 ) ? -1 : 1;cleanup:    return( ret );}/* * Return the number of least significant bits */int mpi_lsb( mpi *X ){    int i, j, count = 0;    for( i = 0; i < X->n; i++ )        for( j = 0; j < (int) biL; j++, count++ )            if( ( ( X->p[i] >> j ) & 1 ) != 0 )                return( count );    return( 0 );}/* * Return the number of most significant bits */int mpi_msb( mpi *X ){    int i, j;    for( i = X->n - 1; i > 0; i-- )        if( X->p[i] != 0 )            break;    for( j = biL - 1; j >= 0; j-- )        if( ( ( X->p[i] >> j ) & 1 ) != 0 )            break;    return( ( i * biL ) + j + 1 );}/* * Return the total size in bytes */int mpi_size( mpi *X ){    return( ( mpi_msb( X ) + 7 ) >> 3 );}/* * Convert an ASCII character to digit value */static int mpi_get_digit( t_int *d, int radix, char c ){    *d = 255;    if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;    if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;    if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;    if( *d >= (t_int) radix )        return( XYSSL_ERR_MPI_INVALID_CHARACTER );    return( 0 );}/* * Import from an ASCII string */int mpi_read_string( mpi *X, int radix, char *s ){    int ret, i, j, n;    t_int d;    mpi T;    if( radix < 2 || radix > 16 )        return( XYSSL_ERR_MPI_BAD_INPUT_DATA );    mpi_init( &T, NULL );    if( radix == 16 )    {        n = BITS_TO_LIMBS( strlen( s ) << 2 );        MPI_CHK( mpi_grow( X, n ) );        MPI_CHK( mpi_lset( X, 0 ) );        for( i = strlen( s ) - 1, j = 0; i >= 0; i--, j++ )        {            if( i == 0 && s[i] == '-' )            {                X->s = -1;                break;            }            MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );            X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );        }    }    else    {        MPI_CHK( mpi_lset( X, 0 ) );        for( i = 0; i < (int) strlen( s ); i++ )        {            if( i == 0 && s[i] == '-' )            {                X->s = -1;                continue;            }            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 ) );        }    }cleanup:    mpi_free( &T, NULL );    return( ret );}/* * Helper to write the digits high-order first */static int mpi_write_hlp( mpi *X, int radix, char **p ){    int ret;    t_int r;    if( radix < 2 || radix > 16 )        return( XYSSL_ERR_MPI_BAD_INPUT_DATA );    MPI_CHK( mpi_mod_int( &r, X, radix ) );    MPI_CHK( mpi_div_int( X, NULL, X, radix ) );    if( mpi_cmp_int( X, 0 ) != 0 )        MPI_CHK( mpi_write_hlp( X, radix, p ) );    if( r < 10 )        *(*p)++ = (char)( r + 0x30 );    else        *(*p)++ = (char)( r + 0x37 );cleanup:    return( ret );}/* * Export into an ASCII string */int mpi_write_string( mpi *X, int radix, char *s, int *slen ){    int ret = 0, n;    char *p;    mpi T;    if( radix < 2 || radix > 16 )        return( XYSSL_ERR_MPI_BAD_INPUT_DATA );    n = mpi_msb( X );    if( radix >=  4 ) n >>= 1;    if( radix >= 16 ) n >>= 1;    n += 3;    if( *slen < n )    {        *slen = n;        return( XYSSL_ERR_MPI_BUFFER_TOO_SMALL );    }    p = s;    mpi_init( &T, NULL );    if( X->s == -1 )        *p++ = '-';    if( radix == 16 )    {        int c, i, j, k;        for( i = X->n - 1, k = 0; i >= 0; i-- )        {            for( j = ciL - 1; j >= 0; j-- )            {                c = ( X->p[i] >> (j << 3) ) & 0xFF;                if( c == 0 && k == 0 && (i + j) != 0 )                    continue;                p += sprintf( p, "%02X", c );                k = 1;            }        }    }    else    {        MPI_CHK( mpi_copy( &T, X ) );        MPI_CHK( mpi_write_hlp( &T, radix, &p ) );    }    *p++ = '\0';    *slen = p - s;cleanup:    mpi_free( &T, NULL );    return( ret );}/* * Read X from an opened file */int mpi_read_file( mpi *X, int radix, FILE *fin ){    t_int d;    int slen;    char *p;    char s[1024];    memset( s, 0, sizeof( s ) );    if( fgets( s, sizeof( s ) - 1, fin ) == NULL )        return( XYSSL_ERR_MPI_FILE_IO_ERROR );    slen = strlen( s );    if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }    if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }    p = s + slen;    while( --p >= s )        if( mpi_get_digit( &d, radix, *p ) != 0 )            break;    return( mpi_read_string( X, radix, p + 1 ) );}/* * Write X into an opened file (or stdout if fout == NULL) */int mpi_write_file( char *p, mpi *X, int radix, FILE *fout ){    int n, ret;    size_t slen;    size_t plen;    char s[1024];    n = sizeof( s );    memset( s, 0, n );    n -= 2;    MPI_CHK( mpi_write_string( X, radix, s, (int *) &n ) );    if( p == NULL ) p = "";    plen = strlen( p );    slen = strlen( s );    s[slen++] = '\r';    s[slen++] = '\n';    if( fout != NULL )    {        if( fwrite( p, 1, plen, fout ) != plen ||            fwrite( s, 1, slen, fout ) != slen )            return( XYSSL_ERR_MPI_FILE_IO_ERROR );    }    else        printf( "%s%s", p, s );cleanup:    return( ret );}/* * Import X from unsigned binary data, big endian */int mpi_read_binary( mpi *X, unsigned char *buf, int buflen ){    int ret, i, j, n;    for( n = 0; n < buflen; n++ )        if( buf[n] != 0 )            break;    MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );    MPI_CHK( mpi_lset( X, 0 ) );    for( i = buflen - 1, j = 0; i >= n; i--, j++ )        X->p[j / ciL] |= ((t_int) buf[i]) << ((j % ciL) << 3);cleanup:    return( ret );}/* * Export X into unsigned binary data, big endian */int mpi_write_binary( mpi *X, unsigned char *buf, int buflen ){    int i, j, n;    n = mpi_size( X );    if( buflen < n )        return( XYSSL_ERR_MPI_BUFFER_TOO_SMALL );    memset( buf, 0, buflen );    for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )        buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );    return( 0 );}/* * Left-shift: X <<= count */int mpi_shift_l( mpi *X, int count ){    int ret, i, v0, t1;    t_int r0 = 0, r1;    v0 = count / (biL    );    t1 = count & (biL - 1);    i = mpi_msb( X ) + count;    if( X->n * (int) biL < i )        MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );    ret = 0;    /*     * shift by count / limb_size     */    if( v0 > 0 )    {        for( i = X->n - 1; i >= v0; i-- )            X->p[i] = X->p[i - v0];        for( ; i >= 0; i-- )            X->p[i] = 0;    }    /*     * shift by count % limb_size     */    if( t1 > 0 )    {        for( i = v0; i < X->n; i++ )        {            r1 = X->p[i] >> (biL - t1);            X->p[i] <<= t1;            X->p[i] |= r0;            r0 = r1;        }    }cleanup:    return( ret );}/* * Right-shift: X >>= count */int mpi_shift_r( mpi *X, int count ){    int i, v0, v1;    t_int r0 = 0, r1;    v0 = count /  biL;    v1 = count & (biL - 1);    /*     * shift by count / limb_size     */    if( v0 > 0 )    {        for( i = 0; i < X->n - v0; i++ )            X->p[i] = X->p[i + v0];        for( ; i < X->n; i++ )            X->p[i] = 0;    }    /*     * shift by count % limb_size     */    if( v1 > 0 )    {        for( i = X->n - 1; i >= 0; i-- )        {            r1 = X->p[i] << (biL - v1);            X->p[i] >>= v1;            X->p[i] |= r0;            r0 = r1;        }    }    return( 0 );}/* * Compare unsigned values */int mpi_cmp_abs( mpi *X, mpi *Y ){    int i, j;    for( i = X->n - 1; i >= 0; i-- )        if( X->p[i] != 0 )            break;    for( j = Y->n - 1; j >= 0; j-- )        if( Y->p[j] != 0 )            break;    if( i < 0 && j < 0 )        return( 0 );    if( i > j ) return(  1 );    if( j > i ) return( -1 );    for( ; i >= 0; i-- )    {        if( X->p[i] > Y->p[i] ) return(  1 );        if( X->p[i] < Y->p[i] ) return( -1 );    }    return( 0 );}/* * Compare signed values */int mpi_cmp_mpi( mpi *X, mpi *Y ){    int i, j;    for( i = X->n - 1; i >= 0; i-- )        if( X->p[i] != 0 )            break;    for( j = Y->n - 1; j >= 0; j-- )        if( Y->p[j] != 0 )            break;    if( i < 0 && j < 0 )        return( 0 );    if( i > j ) return(  X->s );    if( j > i ) return( -X->s );    if( X->s > 0 && Y->s < 0 ) return(  1 );    if( Y->s > 0 && X->s < 0 ) return( -1 );    for( ; i >= 0; i-- )    {        if( X->p[i] > Y->p[i] ) return(  X->s );        if( X->p[i] < Y->p[i] ) return( -X->s );    }    return( 0 );}/* * Compare signed values */int mpi_cmp_int( mpi *X, int z ){    mpi Y;    t_int p[1];