home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
linuxmafia.com 2016
/
linuxmafia.com.tar
/
linuxmafia.com
/
pub
/
linux
/
security
/
gnupg
/
rsa.c
< prev
Wrap
C/C++ Source or Header
|
2000-09-05
|
14KB
|
533 lines
/* 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;
}