aboutsummaryrefslogtreecommitdiffstats
path: root/cipher/rsa.c
diff options
context:
space:
mode:
Diffstat (limited to 'cipher/rsa.c')
-rw-r--r--cipher/rsa.c136
1 files changed, 116 insertions, 20 deletions
diff --git a/cipher/rsa.c b/cipher/rsa.c
index 5d852cd88..2bb451002 100644
--- a/cipher/rsa.c
+++ b/cipher/rsa.c
@@ -1,10 +1,6 @@
/* rsa.c - RSA function
* Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
* Copyright (C) 2000 Free Software Foundation, Inc.
- ***********************************************************************
- * ATTENTION: This code should not be used in the United States
- * before the U.S. Patent #4,405,829 expires on September 20, 2000!
- ***********************************************************************
*
* This file is part of GnuPG.
*
@@ -23,11 +19,16 @@
* 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 expires 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 "util.h"
+#include "g10lib.h"
#include "mpi.h"
#include "cipher.h"
#include "rsa.h"
@@ -68,7 +69,7 @@ test_keys( RSA_secret_key *sk, unsigned nbits )
pk.e = sk->e;
{ char *p = get_random_bits( nbits, 0, 0 );
mpi_set_buffer( test, p, (nbits+7)/8, 0 );
- m_free(p);
+ g10_free(p);
}
public( out1, test, &pk );
@@ -200,22 +201,111 @@ public(MPI output, MPI input, RSA_public_key *pkey )
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\n");
+
+
+ /* 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 );
+ 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\n");
+
+ /* check for crrectness of u */
+ mpi_invm(t, skey->p, skey->q );
+ if ( mpi_cmp(t, skey->u ) )
+ log_info ( "RSA Oops: u is wrong\n");
+
+ 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
*
- * Where m is OUTPUT, c is INPUT and d,n are elements of PKEY.
+ * Or faster:
*
- * FIXME: We should better use the Chinese Remainder Theorem
+ * 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 ******************
*********************************************/
@@ -226,7 +316,7 @@ rsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
RSA_secret_key sk;
if( !is_RSA(algo) )
- return G10ERR_PUBKEY_ALGO;
+ return GCRYERR_INV_PK_ALGO;
generate( &sk, nbits );
skey[0] = sk.n;
@@ -236,7 +326,7 @@ rsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
skey[4] = sk.q;
skey[5] = sk.u;
/* make an empty list of factors */
- *retfactors = m_alloc_clear( 1 * sizeof **retfactors );
+ *retfactors = g10_xcalloc( 1, sizeof **retfactors );
return 0;
}
@@ -247,7 +337,7 @@ rsa_check_secret_key( int algo, MPI *skey )
RSA_secret_key sk;
if( !is_RSA(algo) )
- return G10ERR_PUBKEY_ALGO;
+ return GCRYERR_INV_PK_ALGO;
sk.n = skey[0];
sk.e = skey[1];
@@ -256,7 +346,7 @@ rsa_check_secret_key( int algo, MPI *skey )
sk.q = skey[4];
sk.u = skey[5];
if( !check_secret_key( &sk ) )
- return G10ERR_BAD_SECKEY;
+ return GCRYERR_INV_PK_ALGO;
return 0;
}
@@ -269,7 +359,7 @@ rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
RSA_public_key pk;
if( algo != 1 && algo != 2 )
- return G10ERR_PUBKEY_ALGO;
+ return GCRYERR_INV_PK_ALGO;
pk.n = pkey[0];
pk.e = pkey[1];
@@ -284,7 +374,7 @@ rsa_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
RSA_secret_key sk;
if( algo != 1 && algo != 2 )
- return G10ERR_PUBKEY_ALGO;
+ return GCRYERR_INV_PK_ALGO;
sk.n = skey[0];
sk.e = skey[1];
@@ -303,7 +393,7 @@ rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
RSA_secret_key sk;
if( algo != 1 && algo != 3 )
- return G10ERR_PUBKEY_ALGO;
+ return GCRYERR_INV_PK_ALGO;
sk.n = skey[0];
sk.e = skey[1];
@@ -326,13 +416,13 @@ rsa_verify( int algo, MPI hash, MPI *data, MPI *pkey,
int rc;
if( algo != 1 && algo != 3 )
- return G10ERR_PUBKEY_ALGO;
+ return GCRYERR_INV_PK_ALGO;
pk.n = pkey[0];
pk.e = pkey[1];
result = mpi_alloc( (160+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB);
public( result, data[0], &pk );
/*rc = (*cmp)( opaquev, result );*/
- rc = mpi_cmp( result, hash )? G10ERR_BAD_SIGN:0;
+ rc = mpi_cmp( result, hash )? GCRYERR_BAD_SIGNATURE:0;
mpi_free(result);
return rc;
@@ -366,10 +456,16 @@ rsa_get_info( int algo,
*nsig = 1;
switch( algo ) {
- case 1: *usage = PUBKEY_USAGE_SIG | PUBKEY_USAGE_ENC; return "RSA";
- case 2: *usage = PUBKEY_USAGE_ENC; return "RSA-E";
- case 3: *usage = PUBKEY_USAGE_SIG; return "RSA-S";
+ case 1: *usage = GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR; return "RSA";
+ case 2: *usage = GCRY_PK_USAGE_ENCR; return "RSA-E";
+ case 3: *usage = GCRY_PK_USAGE_SIGN; return "RSA-S";
default:*usage = 0; return NULL;
}
}
+
+
+
+
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-28 18:02:07 +0000