/* 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" typedef struct { gcry_mpi_t n; /* modulus */ gcry_mpi_t e; /* exponent */ } RSA_public_key; typedef struct { gcry_mpi_t n; /* public modulus */ gcry_mpi_t e; /* public exponent */ gcry_mpi_t d; /* exponent */ gcry_mpi_t p; /* prime p. */ gcry_mpi_t q; /* prime q. */ gcry_mpi_t 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 (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey); static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey); static void test_keys( RSA_secret_key *sk, unsigned nbits ) { RSA_public_key pk; gcry_mpi_t test = gcry_mpi_new ( nbits ); gcry_mpi_t out1 = gcry_mpi_new ( nbits ); gcry_mpi_t 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, gcry_mpi_t a) { gcry_mpi_t e = arg; gcry_mpi_t 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) { gcry_mpi_t p, q; /* the two primes */ gcry_mpi_t d; /* the private key */ gcry_mpi_t u; gcry_mpi_t t1, t2; gcry_mpi_t n; /* the public key */ gcry_mpi_t e; /* the exponent */ gcry_mpi_t phi; /* helper: (p-1)(q-1) */ gcry_mpi_t g; gcry_mpi_t 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; gcry_mpi_t 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(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey ) { if( output == input ) /* powm doesn't like output and input the same */ { gcry_mpi_t 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 ) { gcry_mpi_t t = mpi_alloc_secure ( 0 ); gcry_mpi_t t1 = mpi_alloc_secure ( 0 ); gcry_mpi_t t2 = mpi_alloc_secure ( 0 ); gcry_mpi_t 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(gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey ) { if (!skey->p && !skey->q && !skey->u) { mpi_powm (output, input, skey->d, skey->n); } else { gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); gcry_mpi_t 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 ); mpi_free ( h ); mpi_free ( m1 ); mpi_free ( m2 ); } } /* Perform RSA blinding. */ static gcry_mpi_t rsa_blind (gcry_mpi_t x, gcry_mpi_t r, gcry_mpi_t e, gcry_mpi_t n) { /* A helper. */ gcry_mpi_t a; /* Result. */ gcry_mpi_t 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. */ static gcry_mpi_t rsa_unblind (gcry_mpi_t x, gcry_mpi_t ri, gcry_mpi_t n) { gcry_mpi_t 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; } /********************************************* ************** interface ****************** *********************************************/ gcry_err_code_t _gcry_rsa_generate (int algo, unsigned int nbits, unsigned long use_e, gcry_mpi_t *skey, gcry_mpi_t **retfactors) { RSA_secret_key sk; 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 GPG_ERR_NO_ERROR; } gcry_err_code_t _gcry_rsa_check_secret_key( int algo, gcry_mpi_t *skey ) { gcry_err_code_t err = GPG_ERR_NO_ERROR; RSA_secret_key sk; 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)) err = GPG_ERR_PUBKEY_ALGO; return err; } gcry_err_code_t _gcry_rsa_encrypt (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *pkey, int flags) { RSA_public_key pk; pk.n = pkey[0]; pk.e = pkey[1]; resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.n)); public (resarr[0], data, &pk); return GPG_ERR_NO_ERROR; } gcry_err_code_t _gcry_rsa_decrypt (int algo, gcry_mpi_t *result, gcry_mpi_t *data, gcry_mpi_t *skey, int flags) { RSA_secret_key sk; gcry_mpi_t r = MPI_NULL; /* Random number needed for blinding. */ gcry_mpi_t ri = MPI_NULL; /* Modular multiplicative inverse of r. */ gcry_mpi_t x = MPI_NULL; /* Data to decrypt. */ gcry_mpi_t y; /* Result. */ /* 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)) x = rsa_blind (data[0], r, sk.e, sk.n); else x = data[0]; /* Do the encryption. */ secret (y, x, &sk); if (! (flags & PUBKEY_FLAG_NO_BLINDING)) { /* Undo blinding. */ gcry_mpi_t a = gcry_mpi_copy (y); gcry_mpi_release (y); y = 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 GPG_ERR_NO_ERROR; } gcry_err_code_t _gcry_rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey) { RSA_secret_key sk; 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 GPG_ERR_NO_ERROR; } gcry_err_code_t _gcry_rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey, int (*cmp) (void *opaque, gcry_mpi_t tmp), void *opaquev) { RSA_public_key pk; gcry_mpi_t result; gcry_err_code_t rc; 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) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR; gcry_mpi_release (result); return rc; } unsigned int _gcry_rsa_get_nbits (int algo, gcry_mpi_t *pkey) { return mpi_get_nbits (pkey[0]); } static char *rsa_names[] = { "rsa", "openpgp-rsa", "oid.1.2.840.113549.1.1.1", NULL, }; gcry_pk_spec_t _gcry_pubkey_spec_rsa = { "RSA", rsa_names, "ne", "nedpqu", "a", "s", "n", GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR, _gcry_rsa_generate, _gcry_rsa_check_secret_key, _gcry_rsa_encrypt, _gcry_rsa_decrypt, _gcry_rsa_sign, _gcry_rsa_verify, _gcry_rsa_get_nbits, };