mpi.cpp

RSA加密解密的算法例程

/*
 *  Multi-precision integer library
 *
 *  Copyright (C) 2006  Christophe Devine
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License, version 2.1 as published by the Free Software Foundation.
 *
 *  This library 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
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; 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://math.libtomcrypt.com/files/tommath.pdf
 */

#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE 1
#endif

#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>

#include "mpi.h"

#include "mem_alloc.h"

#define ciL    sizeof(t_int)    /* chars in limb  */
#define biL    (ciL << 3)       /* bits  in limb  */
#define biH    (ciL << 2)       /* half limb size */

/*  
 * Bits/chars to # of limbs conversion
 */
#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 )
    {
        memset( X, 0, sizeof( mpi ) );
        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 );
            mem_free( X->p );
        }

        X = va_arg( args, mpi* );
    }

    va_end( args );
}

/*
 * Enlarge total size to the specified # of limbs
 *
 * Returns 0 if successful
 *         1 if memory allocation failed
 */
int mpi_grow( mpi *X, int nblimbs )
{
    int n = X->n;

    if( n < nblimbs )
    {
        if( X->s == 0 )
            X->s = 1;

        X->n = nblimbs;
        X->p = (t_int *) mem_realloc( X->p, X->n * ciL );

        if( X->p == NULL )
            return( 1 );

        memset( X->p + n, 0, ( X->n - n ) * ciL );
    }

    return( 0 );
}

/*
 * Set value to integer z
 *
 * Returns 0 if successful
 *         1 if memory allocation failed
 */
int mpi_lset( mpi *X, int z )
{
    int ret;

    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 );
}

/*
 * Copy the contents of Y into X
 *
 * Returns 0 if successful
 *         1 if memory allocation failed
 */
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;

    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 ) );
}

/* 
 * Convert an ASCII character to digit value
 *
 * Returns 0 if successful
 *         ERR_MPI_INVALID_CHARACTER if conversion to digit failed
 */
int mpi_get_digit( t_int *d, int radix, char c )
{
    *d = 16;

    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( ERR_MPI_INVALID_CHARACTER );

    return( 0 );
}

/*
 * Set value from string
 *
 * Returns 0 if successful
 *         1 if memory allocation failed
 *         ERR_MPI_INVALID_PARAMETER if radix is not between 2 and 16
 *         ERR_MPI_INVALID_CHARACTER if a non-digit character is found
 */
int mpi_read( mpi *X, char *s, int radix )
{
    int ret, i, j, n;
    t_int d;
    mpi T;

    if( radix < 2 || radix > 16 )
        return( ERR_MPI_INVALID_PARAMETER );

    mpi_init( &T, NULL );

    if( radix == 16 )
    {
        n = BITS_TO_LIMBS( strlen(s) << 2 );

        CHK( mpi_grow( X, n ) );
        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;
            }

            CHK( mpi_get_digit( &d, radix, s[i] ) );
            X->p[j / (ciL * 2)] |= d << ( (j % (ciL * 2)) << 2 );
        }
    }
    else
    {
        CHK( mpi_lset( X, 0 ) );

        for( i = 0; i < (int) strlen( s ); i++ )
        {
            if( i == 0 && s[i] == '-' )
            {
                X->s = -1;
                continue;
            }

            CHK( mpi_get_digit( &d, radix, s[i] ) );
            CHK( mpi_mul_int( &T, X, radix ) );
            CHK( mpi_add_int( X, &T, d ) );
        }
    }

cleanup:

    mpi_free( &T, NULL );
    return( ret );
}

/* 
 * Helper to display the digits high-order first
 * (don't call this function directly, use mpi_showf)
 *
 * Returns 0 if successful
 *         1 if memory allocation failed
 *         ERR_MPI_INVALID_PARAMETER if base is not between 2 and 16
 */
int mpi_recurse_showf( FILE *fout, mpi *X, int radix )
{
    int ret;
    t_int r;

    if( radix < 2 || radix > 16 )
        return( ERR_MPI_INVALID_PARAMETER );

    CHK( mpi_mod_int( &r, X, radix ) );
    CHK( mpi_div_int( X, NULL, X, radix ) );

    if( mpi_cmp_int( X, 0 ) != 0 )
        CHK( mpi_recurse_showf( fout, X, radix ) );

    fprintf( fout, "%c", ( r < 10 ) ? ( (char) r + 0x30 )
                                    : ( (char) r + 0x37 ) );

cleanup:

    return( ret );
}

/*
 * Print value in the given numeric base (into fout)
 *
 * Returns 0 if successful
 *         1 if memory allocation failed
 *         ERR_MPI_INVALID_PARAMETER if base is not between 2 and 16
 */
int mpi_showf( FILE *fout, char *name, mpi *X, int radix )
{
    int ret, i, j, k, l;
    mpi T;

    if( radix < 2 || radix > 16 )
        return( ERR_MPI_INVALID_PARAMETER );

    mpi_init( &T, NULL );

    fprintf( fout, "%s%c", name, ( X->s == -1 ) ? '-' : ' ' );

    if( radix == 16 )
    {
        ret = 0;

        for( i = X->n - 1, l = 0; i >= 0; i-- )
        {
            for( j = ciL - 1; j >= 0; j-- )
            {
                k = ( X->p[i] >> (j << 3) ) & 0xFF;

                if( k == 0 && l == 0 && (i + j) != 0 )
                    continue;

                fprintf( fout, "%02X", k );
                l = 1;
            }
        }
    }
    else
    {
        CHK( mpi_copy( &T, X ) );
        CHK( mpi_recurse_showf( fout, &T, radix ) );
    }

    fprintf( fout, "\n" );

cleanup:

    mpi_free( &T, NULL );
    return( ret );
}

/*
 * Print value in the given numeric base (into stdout)
 *
 * Returns 0 if successful
 *         1 if memory allocation failed
 *         ERR_MPI_INVALID_PARAMETER if base is not between 2 and 16
 */
int mpi_show( char *name, mpi *X, int radix )
{
    return( mpi_showf( stdout, name, X, radix ) );
}

/*
 * Import unsigned value from binary data
 *
 * Returns 0 if successful
 *         1 if memory allocation failed
 */
int mpi_import( mpi *X, unsigned char *buf, uint buflen )
{
    int ret, i, j;
    uint n;

    for( n = 0; n < buflen; n++ )
        if( buf[n] != 0 )
            break;

    CHK( mpi_grow( X, CHARS_TO_LIMBS(buflen - n) ) );
    CHK( mpi_lset( X, 0 ) );

    for( i = buflen - 1, j = 0; i >= (int) n; i--, j++ )
        X->p[j / ciL] |= (t_int) buf[i] << ((j % ciL ) << 3);

cleanup:

    return( ret );
}

/*
 * Export unsigned value into binary data
 *
 * Call this function with buflen = 0 to obtain the required
 * buffer size in buflen.
 *
 * Returns 0 if successful
 *         ERR_MPI_BUFFER_TOO_SMALL if buf hasn't enough room
 */
int mpi_export( mpi *X, unsigned char *buf, uint *buflen )
{
    int i, j;
    uint n;

    n = ( mpi_size( X ) + 7 ) >> 3;

    if( *buflen < n )
    {
        *buflen = n;
        return( ERR_MPI_BUFFER_TOO_SMALL );
    }

    memset( buf, 0, *buflen );

    for( i = *buflen - 1, j = 0; n > 0; i--, j++, n-- )
        buf[i] = (uchar) (X->p[j / ciL] >> ((j % ciL) << 3));

    return( 0 );
}

/*
 * Returns actual size in bits
 */
uint mpi_size( 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 );
}

/*
 * Returns # of least significant bits
 */
uint mpi_lsb( mpi *X )
{
    int i, j;
    uint 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 );
}

/*
 * Left-shift: X <<= count
 *
 * Returns 0 if successful,
 *         1 if memory allocation failed
 */
int mpi_shift_l( mpi *X, uint count )
{
    int ret, i, v0, t1;
    t_int r0 = 0, r1;

    v0 = count /  biL;
    t1 = count & (biL - 1);

    i = mpi_size( X ) + count;

    if( X->n * (int) biL < i )
        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 );
}

/*