rsa加密算法的实现.txt

几个常用的加密算法的实现

/* rsa.c  -  RSA function
 *	Copyright (c) 1997,1998,1999 by Werner Koch (dd9jn)
 ***********************************************************************
 * ATTENTION: This code should not be exported to the United States
 * nor should it be used there without a license agreement with PKP.
 * The RSA algorithm is protected by U.S. Patent #4,405,829 which
 * expires on September 20, 2000!
 ***********************************************************************
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * WERNER KOCH BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * Except as contained in this notice, the name of Werner Koch shall not be
 * used in advertising or otherwise to promote the sale, use or other dealings
 * in this Software without prior written authorization from Werner Koch.
 */

/* How to compile:
 *
	 gcc -Wall -O2 -shared -fPIC -o rsa rsa.c
 */

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

/* configuration stuff */
#ifdef __alpha__
  #define SIZEOF_UNSIGNED_LONG 8
#else
  #define SIZEOF_UNSIGNED_LONG 4
#endif

#if defined(__mc68000__) || defined (__sparc__) || defined (__PPC__) \
    || (defined(__mips__) && (defined(MIPSEB) || defined (__MIPSEB__)) ) \
    || defined(__hpux__)  /* should be replaced by the macro for the PA */
  #define BIG_ENDIAN_HOST 1
#else
  #define LITTLE_ENDIAN_HOST 1
#endif

typedef unsigned long  ulong;
typedef unsigned short ushort;
typedef unsigned char  byte;

typedef unsigned short u16;
typedef unsigned long  u32;

/* end configurable stuff */


const char * const gnupgext_version = "RSA ($Revision: 1.10 $)";

#ifndef DIM
  #define DIM(v) (sizeof(v)/sizeof((v)[0]))
  #define DIMof(type,member)   DIM(((type *)0)->member)
#endif

#define is_RSA(a) ((a)>=1 && (a)<=3)

#define BAD_ALGO  4
#define BAD_KEY   7
#define BAD_SIGN  8

struct mpi_struct { int hidden_stuff; };
typedef struct mpi_struct *MPI;

extern int g10c_debug_mode;
extern int g10_opt_verbose;



typedef struct {
    MPI n;	    /* modulus */
    MPI e;	    /* exponent */
} RSA_public_key;


typedef struct {
    MPI n;	    /* public modulus */
    MPI e;	    /* public exponent */
    MPI d;	    /* exponent */
    MPI p;	    /* prime  p. */
    MPI q;	    /* prime  q. */
    MPI u;	    /* inverse of p mod q. */
} RSA_secret_key;

/* imports */
void *g10_malloc( size_t n );
void *g10_calloc( size_t n );
void g10_free( void *p);
void g10_log_fatal( const char *fmt, ... );
void g10_log_error( const char *fmt, ... );
void g10_log_info( const char *fmt, ... );
void g10_log_debug( const char *fmt, ... );
void g10_log_hexdump( const char *text, char *buf, size_t len );
void g10_log_mpidump( const char *text, MPI a );
MPI  g10c_generate_secret_prime( unsigned nbits );
char *g10c_get_random_bits( unsigned nbits, int level, int secure );
MPI  g10m_new( unsigned nbits );
MPI  g10m_new_secure( unsigned nbits );
void g10m_release( MPI a );
void g10m_set( MPI w, MPI u);
void g10m_set_ui( MPI w, unsigned long u);
void g10m_set_buffer( MPI a, const char *buffer, unsigned nbytes, int sign );
MPI  g10m_copy( MPI a );
void g10m_swap( MPI a, MPI b);
unsigned g10m_get_nbits( MPI a );
unsigned g10m_get_size( MPI a );
int  g10m_cmp( MPI u, MPI v );
void g10m_add_ui(MPI w, MPI u, unsigned long v );
void g10m_sub_ui(MPI w, MPI u, unsigned long v );
void g10m_mul( MPI w, MPI u, MPI v);
void g10m_fdiv_q( MPI quot, MPI dividend, MPI divisor );
void g10m_powm( MPI res, MPI base, MPI exp, MPI mod);
int  g10m_gcd( MPI g, MPI a, MPI b );
int  g10m_invm( MPI x, MPI u, MPI v );

/* local prototypes */
static void test_keys( RSA_secret_key *sk, unsigned nbits );
static void generate( RSA_secret_key *sk, unsigned nbits );
static int  check_secret_key( RSA_secret_key *sk );
static void public(MPI output, MPI input, RSA_public_key *skey );
static void secret(MPI output, MPI input, RSA_secret_key *skey );


static void
test_keys( RSA_secret_key *sk, unsigned nbits )
{
    RSA_public_key pk;
    MPI test = g10m_new( nbits );
    MPI out1 = g10m_new( nbits );
    MPI out2 = g10m_new( nbits );

    pk.n = sk->n;
    pk.e = sk->e;
    {	char *p = g10c_get_random_bits( nbits, 0, 0 );
	g10m_set_buffer( test, p, (nbits+7)/8, 0 );
	g10_free(p);
    }

    public( out1, test, &pk );
    secret( out2, out1, sk );
    if( g10m_cmp( test, out2 ) )
	g10_log_fatal("RSA operation: public, secret failed\n");
    secret( out1, test, sk );
    public( out2, out1, &pk );
    if( g10m_cmp( test, out2 ) )
	g10_log_fatal("RSA operation: secret, public failed\n");
    g10m_release( test );
    g10m_release( out1 );
    g10m_release( out2 );
}

/****************
 * Generate a key pair with a key of size NBITS
 * Returns: 2 structures filles with all needed values
 */
static void
generate( RSA_secret_key *sk, unsigned nbits )
{
    MPI p, q; /* the two primes */
    MPI d;    /* the private key */
    MPI u;
    MPI t1, t2;
    MPI n;    /* the public key */
    MPI e;    /* the exponent */
    MPI phi;  /* helper: (p-a)(q-1) */
    MPI g;
    MPI f;

    /* select two (very secret) primes */
    p = g10c_generate_secret_prime( nbits / 2 );
    q = g10c_generate_secret_prime( nbits / 2 );
    if( g10m_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
	g10m_swap(p,q);
    /* calculate Euler totient: phi = (p-1)(q-1) */
    t1 = g10m_new_secure( g10m_get_size(p) );
    t2 = g10m_new_secure( g10m_get_size(p) );
    phi = g10m_new_secure( nbits );
    g	= g10m_new_secure( nbits  );
    f	= g10m_new_secure( nbits  );
    g10m_sub_ui( t1, p, 1 );
    g10m_sub_ui( t2, q, 1 );
    g10m_mul( phi, t1, t2 );
    g10m_gcd(g, t1, t2);
    g10m_fdiv_q(f, phi, g);
    /* multiply them to make the private key */
    n = g10m_new( nbits );
    g10m_mul( n, p, q );
    /* find a public exponent  */
    e = g10m_new(6);
    g10m_set_ui( e, 17); /* start with 17 */
    while( !g10m_gcd(t1, e, phi) ) /* (while gcd is not 1) */
	g10m_add_ui( e, e, 2);
    /* calculate the secret key d = e^1 mod phi */
    d = g10m_new( nbits );
    g10m_invm(d, e, f );
    /* calculate the inverse of p and q (used for chinese remainder theorem)*/
    u = g10m_new( nbits );
    g10m_invm(u, p, q );

    if( g10c_debug_mode ) {
	g10_log_mpidump("  p= ", p );
	g10_log_mpidump("  q= ", q );
	g10_log_mpidump("phi= ", phi );
	g10_log_mpidump("  g= ", g );
	g10_log_mpidump("  f= ", f );
	g10_log_mpidump("  n= ", n );
	g10_log_mpidump("  e= ", e );
	g10_log_mpidump("  d= ", d );
	g10_log_mpidump("  u= ", u );
    }

    g10m_release(t1);
    g10m_release(t2);
    g10m_release(phi);
    g10m_release(f);
    g10m_release(g);

    sk->n = n;
    sk->e = e;
    sk->p = p;
    sk->q = q;
    sk->d = d;
    sk->u = u;

    /* now we can test our keys (this should never fail!) */
    test_keys( sk, nbits - 64 );
}


/****************
 * Test wether the secret key is valid.
 * Returns: true if this is a valid key.
 */
static int
check_secret_key( RSA_secret_key *sk )
{
    int rc;
    MPI temp = g10m_new( g10m_get_size(sk->p)*2 );

    g10m_mul(temp, sk->p, sk->q );
    rc = g10m_cmp( temp, sk->n );
    g10m_release(temp);
    return !rc;
}



/****************
 * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
 *
 *	c = m^e mod n
 *
 * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
 */
static void
public(MPI output, MPI input, RSA_public_key *pkey )
{
    if( output == input ) { /* powm doesn't like output and input the same */
	MPI x = g10m_new( g10m_get_size(input)*2 );
	g10m_powm( x, input, pkey->e, pkey->n );
	g10m_set(output, x);
	g10m_release(x);
    }
    else
	g10m_powm( output, input, pkey->e, pkey->n );
}

/****************
 * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
 *
 *	m = c^d mod n
 *
 * Where m is OUTPUT, c is INPUT and d,n are elements of PKEY.
 *
 * FIXME: We should better use the Chinese Remainder Theorem
 */
static void
secret(MPI output, MPI input, RSA_secret_key *skey )
{
    g10m_powm( output, input, skey->d, skey->n );
}


/*********************************************
 **************  interface  ******************
 *********************************************/

static int
do_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
{
    RSA_secret_key sk;

    if( !is_RSA(algo) )
	return BAD_ALGO;

    generate( &sk, nbits );
    skey[0] = sk.n;
    skey[1] = sk.e;
    skey[2] = sk.d;
    skey[3] = sk.p;
    skey[4] = sk.q;
    skey[5] = sk.u;
    /* make an empty list of factors */
    *retfactors = g10_calloc( 1 * sizeof **retfactors );
    return 0;
}


static int
do_check_secret_key( int algo, MPI *skey )
{
    RSA_secret_key sk;

    if( !is_RSA(algo) )
	return BAD_ALGO;

    sk.n = skey[0];
    sk.e = skey[1];
    sk.d = skey[2];
    sk.p = skey[3];
    sk.q = skey[4];
    sk.u = skey[5];
    if( !check_secret_key( &sk ) )
	return BAD_KEY;

    return 0;
}



static int
do_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
{
    RSA_public_key pk;

    if( algo != 1 && algo != 2 )
	return BAD_ALGO;

    pk.n = pkey[0];
    pk.e = pkey[1];
    resarr[0] = g10m_new( g10m_get_size( pk.n ) );
    public( resarr[0], data, &pk );
    return 0;
}

static int
do_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
{
    RSA_secret_key sk;

    if( algo != 1 && algo != 2 )
	return BAD_ALGO;

    sk.n = skey[0];
    sk.e = skey[1];
    sk.d = skey[2];
    sk.p = skey[3];
    sk.q = skey[4];
    sk.u = skey[5];
    *result = g10m_new_secure( g10m_get_size( sk.n ) );
    secret( *result, data[0], &sk );
    return 0;
}

static int
do_sign( int algo, MPI *resarr, MPI data, MPI *skey )
{
    RSA_secret_key sk;

    if( algo != 1 && algo != 3 )
	return BAD_ALGO;

    sk.n = skey[0];
    sk.e = skey[1];
    sk.d = skey[2];
    sk.p = skey[3];
    sk.q = skey[4];
    sk.u = skey[5];
    resarr[0] = g10m_new( g10m_get_size( sk.n ) );
    secret( resarr[0], data, &sk );

    return 0;
}

static int
do_verify( int algo, MPI hash, MPI *data, MPI *pkey,
	   int (*cmp)(void *opaque, MPI tmp), void *opaquev )
{
    RSA_public_key pk;
    MPI result;
    int rc;

    if( algo != 1 && algo != 3 )
	return BAD_ALGO;
    pk.n = pkey[0];
    pk.e = pkey[1];
    result = g10m_new(160);
    public( result, data[0], &pk );
    /*rc = (*cmp)( opaquev, result );*/
    rc = g10m_cmp( result, hash )? BAD_SIGN:0;
    g10m_release(result);

    return rc;
}


static unsigned
do_get_nbits( int algo, MPI *pkey )
{
    if( !is_RSA(algo) )
	return 0;
    return g10m_get_nbits( pkey[0] );
}


/****************
 * Return some information about the algorithm.  We need algo here to
 * distinguish different flavors of the algorithm.
 * Returns: A pointer to string describing the algorithm or NULL if
 *	    the ALGO is invalid.
 * Usage: Bit 0 set : allows signing
 *	      1 set : allows encryption
 */
static const char *
rsa_get_info( int algo,
	      int *npkey, int *nskey, int *nenc, int *nsig, int *usage,
    int (**r_generate)( int algo, unsigned nbits, MPI *skey, MPI **retfactors ),
    int (**r_check_secret_key)( int algo, MPI *skey ),
    int (**r_encrypt)( int algo, MPI *resarr, MPI data, MPI *pkey ),
    int (**r_decrypt)( int algo, MPI *result, MPI *data, MPI *skey ),
    int (**r_sign)( int algo, MPI *resarr, MPI data, MPI *skey ),
    int (**r_verify)( int algo, MPI hash, MPI *data, MPI *pkey,
				    int (*)(void *, MPI), void *),
    unsigned (**r_get_nbits)( int algo, MPI *pkey ) )
{
    *npkey = 2;
    *nskey = 6;
    *nenc = 1;
    *nsig = 1;
    *r_generate 	= do_generate	     ;
    *r_check_secret_key = do_check_secret_key;
    *r_encrypt		= do_encrypt	     ;
    *r_decrypt		= do_decrypt	     ;
    *r_sign		= do_sign	     ;
    *r_verify		= do_verify	     ;
    *r_get_nbits	= do_get_nbits	     ;

    switch( algo ) {
      case 1: *usage = 2|1; return "RSA";
      case 2: *usage = 2  ; return "RSA-E";
      case 3: *usage =	 1; return "RSA-S";
      default:*usage = 0; return NULL;
    }
}


static struct {
    int class;
    int version;
    int  value;
    void (*func)(void);
} func_table[] = {
    { 30, 1, 0, (void(*)(void))rsa_get_info },
    { 31, 1, 1 }, /* RSA */
    { 31, 1, 2 }, /* RSA encrypt only */
    { 31, 1, 3 }, /* RSA sign only */
};



/****************
 * Enumerate the names of the functions together with informations about
 * this function. Set sequence to an integer with a initial value of 0 and
 * do not change it.
 * If what is 0 all kind of functions are returned.
 * Return values: class := class of function:
 *			   10 = message digest algorithm info function
 *			   11 = integer with available md algorithms
 *			   20 = cipher algorithm info function
 *			   21 = integer with available cipher algorithms
 *			   30 = public key algorithm info function
 *			   31 = integer with available pubkey algorithms
 *		  version = interface version of the function/pointer
 */
void *
gnupgext_enum_func( int what, int *sequence, int *class, int *vers )
{
    void *ret;
    int i = *sequence;

    do {
	if( i >= DIM(func_table) || i < 0 ) {
	    return NULL;
	}
	*class = func_table[i].class;
	*vers  = func_table[i].version;
	switch( *class ) {
	  case 11:
	  case 21:
	  case 31:
	    ret = &func_table[i].value;
	    break;
	  default:
	    ret = func_table[i].func;
	    break;
	}
	i++;
    } while( what && what != *class );

    *sequence = i;
    return ret;
}