/* rsa.c - RSA function * Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn) * Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc. * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt 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 program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA */ /* This code uses an algorithm protected by U.S. Patent #4,405,829 which expired on September 20, 2000. The patent holder placed that patent into the public domain on Sep 6th, 2000. */ #include #include #include #include #include "g10lib.h" #include "mpi.h" #include "cipher.h" #include "rsa.h" 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; static void test_keys( RSA_secret_key *sk, unsigned nbits ); static void generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e ); 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 = gcry_mpi_new ( nbits ); MPI out1 = gcry_mpi_new ( nbits ); MPI out2 = gcry_mpi_new ( nbits ); pk.n = sk->n; pk.e = sk->e; gcry_mpi_randomize( test, nbits, GCRY_WEAK_RANDOM ); public( out1, test, &pk ); secret( out2, out1, sk ); if( mpi_cmp( test, out2 ) ) log_fatal("RSA operation: public, secret failed\n"); secret( out1, test, sk ); public( out2, out1, &pk ); if( mpi_cmp( test, out2 ) ) log_fatal("RSA operation: secret, public failed\n"); gcry_mpi_release ( test ); gcry_mpi_release ( out1 ); gcry_mpi_release ( out2 ); } /* Callback used by the prime generation to test whether the exponent is suitable. Returns 0 if the test has been passed. */ static int check_exponent (void *arg, MPI a) { MPI e = arg; MPI tmp; int result; mpi_sub_ui (a, a, 1); tmp = _gcry_mpi_alloc_like (a); result = !gcry_mpi_gcd(tmp, e, a); /* GCD is not 1. */ gcry_mpi_release (tmp); mpi_add_ui (a, a, 1); return result; } /**************** * Generate a key pair with a key of size NBITS. * USE_E = 0 let Libcgrypt decide what exponent to use. * = 1 request the use of a "secure" exponent; this is required by some * specification to be 65537. * > 2 Try starting at this value until a working exponent is found. * Returns: 2 structures filled with all needed values */ static void generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e) { 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-1)(q-1) */ MPI g; MPI f; /* make sure that nbits is even so that we generate p, q of equal size */ if ( (nbits&1) ) nbits++; if (use_e == 1) /* Alias for a secure value. */ use_e = 65537; /* as demanded by Spinx. */ /* Public exponent: In general we use 41 as this is quite fast and more secure than the commonly used 17. Benchmarking the RSA verify function with a 1024 bit key yields (2001-11-08): e=17 0.54 ms e=41 0.75 ms e=257 0.95 ms e=65537 1.80 ms */ e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB ); if (!use_e) mpi_set_ui (e, 41); /* This is a reasonable secure and fast value */ else { use_e |= 1; /* make sure this is odd */ mpi_set_ui (e, use_e); } n = gcry_mpi_new (nbits); p = q = NULL; do { /* select two (very secret) primes */ if (p) gcry_mpi_release (p); if (q) gcry_mpi_release (q); if (use_e) { /* Do an extra test to ensure that the given exponent is suitable. */ p = _gcry_generate_secret_prime (nbits/2, check_exponent, e); q = _gcry_generate_secret_prime (nbits/2, check_exponent, e); } else { /* We check the exponent later. */ p = _gcry_generate_secret_prime (nbits/2, NULL, NULL); q = _gcry_generate_secret_prime (nbits/2, NULL, NULL); } if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/ mpi_swap(p,q); /* calculate the modulus */ mpi_mul( n, p, q ); } while ( mpi_get_nbits(n) != nbits ); /* calculate Euler totient: phi = (p-1)(q-1) */ t1 = mpi_alloc_secure( mpi_get_nlimbs(p) ); t2 = mpi_alloc_secure( mpi_get_nlimbs(p) ); phi = gcry_mpi_snew ( nbits ); g = gcry_mpi_snew ( nbits ); f = gcry_mpi_snew ( nbits ); mpi_sub_ui( t1, p, 1 ); mpi_sub_ui( t2, q, 1 ); mpi_mul( phi, t1, t2 ); gcry_mpi_gcd(g, t1, t2); mpi_fdiv_q(f, phi, g); while (!gcry_mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */ { if (use_e) BUG (); /* The prime generator already made sure that we never can get to here. */ mpi_add_ui (e, e, 2); } /* calculate the secret key d = e^1 mod phi */ d = gcry_mpi_snew ( nbits ); mpi_invm(d, e, f ); /* calculate the inverse of p and q (used for chinese remainder theorem)*/ u = gcry_mpi_snew ( nbits ); mpi_invm(u, p, q ); if( DBG_CIPHER ) { log_mpidump(" p= ", p ); log_mpidump(" q= ", q ); log_mpidump("phi= ", phi ); log_mpidump(" g= ", g ); log_mpidump(" f= ", f ); log_mpidump(" n= ", n ); log_mpidump(" e= ", e ); log_mpidump(" d= ", d ); log_mpidump(" u= ", u ); } gcry_mpi_release (t1); gcry_mpi_release (t2); gcry_mpi_release (phi); gcry_mpi_release (f); gcry_mpi_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 = mpi_alloc( mpi_get_nlimbs(sk->p)*2 ); mpi_mul(temp, sk->p, sk->q ); rc = mpi_cmp( temp, sk->n ); mpi_free(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 = mpi_alloc( mpi_get_nlimbs(input)*2 ); mpi_powm( x, input, pkey->e, pkey->n ); mpi_set(output, x); mpi_free(x); } else mpi_powm( output, input, pkey->e, pkey->n ); } #if 0 static void stronger_key_check ( RSA_secret_key *skey ) { MPI t = mpi_alloc_secure ( 0 ); MPI t1 = mpi_alloc_secure ( 0 ); MPI t2 = mpi_alloc_secure ( 0 ); MPI phi = mpi_alloc_secure ( 0 ); /* check that n == p * q */ mpi_mul( t, skey->p, skey->q); if (mpi_cmp( t, skey->n) ) log_info ( "RSA Oops: n != p * q\n" ); /* check that p is less than q */ if( mpi_cmp( skey->p, skey->q ) > 0 ) { log_info ("RSA Oops: p >= q - fixed\n"); _gcry_mpi_swap ( skey->p, skey->q); } /* check that e divides neither p-1 nor q-1 */ mpi_sub_ui(t, skey->p, 1 ); mpi_fdiv_r(t, t, skey->e ); if ( !mpi_cmp_ui( t, 0) ) log_info ( "RSA Oops: e divides p-1\n" ); mpi_sub_ui(t, skey->q, 1 ); mpi_fdiv_r(t, t, skey->e ); if ( !mpi_cmp_ui( t, 0) ) log_info ( "RSA Oops: e divides q-1\n" ); /* check that d is correct */ mpi_sub_ui( t1, skey->p, 1 ); mpi_sub_ui( t2, skey->q, 1 ); mpi_mul( phi, t1, t2 ); gcry_mpi_gcd(t, t1, t2); mpi_fdiv_q(t, phi, t); mpi_invm(t, skey->e, t ); if ( mpi_cmp(t, skey->d ) ) { log_info ( "RSA Oops: d is wrong - fixed\n"); mpi_set (skey->d, t); _gcry_log_mpidump (" fixed d", skey->d); } /* check for correctness of u */ mpi_invm(t, skey->p, skey->q ); if ( mpi_cmp(t, skey->u ) ) { log_info ( "RSA Oops: u is wrong - fixed\n"); mpi_set (skey->u, t); _gcry_log_mpidump (" fixed u", skey->u); } log_info ( "RSA secret key check finished\n"); mpi_free (t); mpi_free (t1); mpi_free (t2); mpi_free (phi); } #endif /**************** * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT. * * m = c^d mod n * * Or faster: * * m1 = c ^ (d mod (p-1)) mod p * m2 = c ^ (d mod (q-1)) mod q * h = u * (m2 - m1) mod q * m = m1 + h * p * * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY. */ static void secret(MPI output, MPI input, RSA_secret_key *skey ) { #if 0 mpi_powm( output, input, skey->d, skey->n ); #else MPI m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); MPI m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); MPI h = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); /* m1 = c ^ (d mod (p-1)) mod p */ mpi_sub_ui( h, skey->p, 1 ); mpi_fdiv_r( h, skey->d, h ); mpi_powm( m1, input, h, skey->p ); /* m2 = c ^ (d mod (q-1)) mod q */ mpi_sub_ui( h, skey->q, 1 ); mpi_fdiv_r( h, skey->d, h ); mpi_powm( m2, input, h, skey->q ); /* h = u * ( m2 - m1 ) mod q */ mpi_sub( h, m2, m1 ); if ( mpi_is_neg( h ) ) mpi_add ( h, h, skey->q ); mpi_mulm( h, skey->u, h, skey->q ); /* m = m2 + h * p */ mpi_mul ( h, h, skey->p ); mpi_add ( output, m1, h ); /* ready */ mpi_free ( h ); mpi_free ( m1 ); mpi_free ( m2 ); #endif } /********************************************* ************** interface ****************** *********************************************/ int _gcry_rsa_generate (int algo, unsigned int nbits, unsigned long use_e, MPI *skey, MPI **retfactors) { RSA_secret_key sk; if( !is_RSA(algo) ) return GCRYERR_INV_PK_ALGO; generate( &sk, nbits, use_e ); 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 = gcry_xcalloc( 1, sizeof **retfactors ); return 0; } int _gcry_rsa_check_secret_key( int algo, MPI *skey ) { RSA_secret_key sk; if( !is_RSA(algo) ) return GCRYERR_INV_PK_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 GCRYERR_INV_PK_ALGO; return 0; } int _gcry_rsa_encrypt (int algo, MPI *resarr, MPI data, MPI *pkey, int flags) { RSA_public_key pk; if( algo != 1 && algo != 2 ) return GCRYERR_INV_PK_ALGO; pk.n = pkey[0]; pk.e = pkey[1]; resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) ); public( resarr[0], data, &pk ); return 0; } /* Perform RSA blinding. */ GcryMPI _gcry_rsa_blind (MPI x, MPI r, MPI e, MPI n) { /* A helper. */ GcryMPI a; /* Result. */ GcryMPI y; a = gcry_mpi_snew (gcry_mpi_get_nbits (n)); y = gcry_mpi_snew (gcry_mpi_get_nbits (n)); /* Now we calculate: y = (x * r^e) mod n, where r is the random number, e is the public exponent, x is the non-blinded data and n is the RSA modulus. */ gcry_mpi_powm (a, r, e, n); gcry_mpi_mulm (y, a, x, n); gcry_mpi_release (a); return y; } /* Undo RSA blinding. */ GcryMPI _gcry_rsa_unblind (MPI x, MPI ri, MPI n) { GcryMPI y; y = gcry_mpi_snew (gcry_mpi_get_nbits (n)); /* Here we calculate: y = (x * r^-1) mod n, where x is the blinded decrypted data, ri is the modular multiplicative inverse of r and n is the RSA modulus. */ gcry_mpi_mulm (y, ri, x, n); return y; } int _gcry_rsa_decrypt (int algo, MPI *result, MPI *data, MPI *skey, int flags) { RSA_secret_key sk; GcryMPI r = MPI_NULL; /* Random number needed for blinding. */ GcryMPI ri = MPI_NULL; /* Modular multiplicative inverse of r. */ GcryMPI x = MPI_NULL; /* Data to decrypt. */ GcryMPI y; /* Result. */ if (algo != 1 && algo != 2) return GCRYERR_INV_PK_ALGO; /* Extract private key. */ sk.n = skey[0]; sk.e = skey[1]; sk.d = skey[2]; sk.p = skey[3]; sk.q = skey[4]; sk.u = skey[5]; y = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n)); if (! (flags & PUBKEY_FLAG_NO_BLINDING)) { /* Initialize blinding. */ /* First, we need a random number r between 0 and n - 1, which is relatively prime to n (i.e. it is neither p nor q). */ r = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n)); ri = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n)); gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n), GCRY_STRONG_RANDOM); gcry_mpi_mod (r, r, sk.n); /* Actually it should be okay to skip the check for equality with either p or q here. */ /* Calculate inverse of r. */ if (! gcry_mpi_invm (ri, r, sk.n)) BUG (); } if (! (flags & PUBKEY_FLAG_NO_BLINDING)) /* Do blinding. */ x = _gcry_rsa_blind (data[0], r, sk.e, sk.n); else /* Skip blinding. */ x = data[0]; /* Do the encryption. */ secret (y, x, &sk); if (! (flags & PUBKEY_FLAG_NO_BLINDING)) { /* Undo blinding. */ GcryMPI a = gcry_mpi_copy (y); gcry_mpi_release (y); y = _gcry_rsa_unblind (a, ri, sk.n); } if (! (flags & PUBKEY_FLAG_NO_BLINDING)) { /* Deallocate resources needed for blinding. */ gcry_mpi_release (x); gcry_mpi_release (r); gcry_mpi_release (ri); } /* Copy out result. */ *result = y; return 0; } int _gcry_rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey ) { RSA_secret_key sk; if( algo != 1 && algo != 3 ) return GCRYERR_INV_PK_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] = mpi_alloc( mpi_get_nlimbs( sk.n ) ); secret( resarr[0], data, &sk ); return 0; } int _gcry_rsa_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 GCRYERR_INV_PK_ALGO; pk.n = pkey[0]; pk.e = pkey[1]; result = gcry_mpi_new ( 160 ); public( result, data[0], &pk ); /*rc = (*cmp)( opaquev, result );*/ rc = mpi_cmp( result, hash )? GCRYERR_BAD_SIGNATURE:0; gcry_mpi_release (result); return rc; } unsigned int _gcry_rsa_get_nbits( int algo, MPI *pkey ) { if( !is_RSA(algo) ) return 0; return mpi_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 */ const char * _gcry_rsa_get_info( int algo, int *npkey, int *nskey, int *nenc, int *nsig, int *r_usage ) { *npkey = 2; *nskey = 6; *nenc = 1; *nsig = 1; switch( algo ) { case 1: *r_usage = GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR; return "RSA"; case 2: *r_usage = GCRY_PK_USAGE_ENCR; return "RSA-E"; case 3: *r_usage = GCRY_PK_USAGE_SIGN; return "RSA-S"; default:*r_usage = 0; return NULL; } }