Initial revision

1 files changed, 630 insertions, 0 deletions

diff --git a/pwmanager/libcrypt/cipher/rsa.c b/pwmanager/libcrypt/cipher/rsa.c
new file mode 100644
index 0000000..fa26622
--- a/dev/null
+++ b/pwmanager/libcrypt/cipher/rsa.c
@@ -0,0 +1,630 @@
+/* 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 <config.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#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,
+  };