From: cpunk@remail.ecafe.org (ECafe Anonymous Remailer)
Date: Thu, 28 Dec 95 09:21:40 PST
To: cypherpunks@toad.com
Subject: Cryptolib 1.1 rsa.c
Message-ID: <199512281722.RAA18284@pangaea.ang.ecafe.org>
MIME-Version: 1.0
Content-Type: text/plain


I am informed that there is a serious bug in the version of cryptolib
that gets sent to people who don't have RSA licenses.  The bug
prevents it from doing RSA encrypt, decrypt or signature.  I cannot
imagine how this bug slipped through but it seems only to exist in the
copies of cryptolib that are sent to those without RSA licenses.
Fortunately I have an RSA licesnse and so my new copy (thanks Jack and
Matt!) does not suffer from the bug.

Here is the version of rsa.c that fixes the bug.

/*
 * This is version 1.1 of CryptoLib
 *
 * The authors of this software are Jack Lacy, Don Mitchell and Matt Blaze
 *              Copyright (c) 1991, 1992, 1993, 1994, 1995 by AT&T.
 * Permission to use, copy, and modify this software without fee
 * is hereby granted, provided that this entire notice is included in
 * all copies of any software which is or includes a copy or
 * modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * NOTE:
 * Some of the algorithms in cryptolib may be covered by patents.
 * It is the responsibility of the user to ensure that any required
 * licenses are obtained.
 *
 *
 * SOME PARTS OF CRYPTOLIB MAY BE RESTRICTED UNDER UNITED STATES EXPORT
 * REGULATIONS.
 *
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 */

/*
 *        Code for generating and manipulating RSA keys
 *        and doing encryption and decryption using RSA.
 *        AT&T recognizes that RSA is patented
 *        (Rivest et. al. U.S. Patent 4,405,829, issued 9/20/83).
 *	  Use of this code assumes proper licensing.
 *
 *        coded by Jack Lacy, December, 1991
 *
 */
#include "libcrypt.h"

static Key_exps *genKeyExps P((BigInt, BigInt, BigInt, int, BigInt));
static void chineseRemTheorem P((BigInt , RSAPrivateKey *, BigInt));
static void genPrimesFor3 P((int, BigInt, BigInt, BigInt, BigInt));

#ifdef K_AND_R
static Key_exps *
genKeyExps(p, q, e, ebits, randomStart)
  BigInt p, q, e;
  int ebits;
  BigInt randomStart;
#else
  static Key_exps *genKeyExps(BigInt p,
			      BigInt q,
			      BigInt e,
			      int ebits,
			      BigInt randomStart)
#endif
{
	BigInt phi, p1, q1;
	BigInt u1, ngcd, ignore;
	Key_exps *exps;
	int ebytes;
#ifdef DLLEXPORT
	HGLOBAL handle = clib_malloc(sizeof(Key_exps));
	exps = (Key_exps *)GlobalLock(handle);
	exps->exp_handle = handle;
#else
	exps = (Key_exps *)clib_malloc(sizeof(Key_exps));
#endif
	p1 = bigInit(0);
	q1 = bigInit(0);
	phi = bigInit(0);
	u1  = bigInit(0);
	ngcd = bigInit(0);
	ignore = bigInit(0);
	if (e == NULL)
		e = bigInit(3);
	
	bigSubtract(p, one, p1);
	bigSubtract(q, one, q1);
	bigMultiply(p1, q1, phi);
	freeBignum(p1);
	freeBignum(q1);
	
	/* Get public exponent, relatively prime to modulus. */
	/* A by product of the extendedGcd calculation is the inverse
	   of e mod phi, which is d, the private exponent.
	   If e has been specified, skip this.
	 */
	if (e == NULL) {
		if (ebits > 2) {
			ebytes = (ebits/8) + (ebits%8? 1: 0);
			if (randomStart == NULL) {
				bigRand(ebytes, e, PSEUDO);
			}
			else {
				bigCopy(randomStart, e);
			}
			if (EVEN(e))
				bigAdd(e, one, e);
		}
	}
	extendedGcd(e, phi, u1, ignore, ngcd);
	while (bigCompare(ngcd, one) != 0) {
		bigAdd(e, two, e);
		extendedGcd(e, phi, u1, ignore, ngcd);
	}
	exps->d = u1;
	exps->e = e;
	
	freeBignum(phi);
	freeBignum(ngcd);
	freeBignum(ignore);
	
	return exps;
}

#ifdef K_AND_R
_TYPE( RSAPublicKey * )
buildRSAPublicKey(e, n)
  BigInt e, n;
#else
_TYPE( RSAPublicKey * ) buildRSAPublicKey(BigInt e,
					  BigInt n)
#endif
{
	RSAPublicKey *pk;
#ifdef DLLEXPORT
	HGLOBAL handle = clib_malloc(sizeof(RSAPublicKey));
	pk = (RSAPublicKey *)GlobalLock(handle);
	pk->pubkey_handle = handle;
#else
	pk = (RSAPublicKey *)clib_malloc(sizeof(RSAPublicKey));
#endif
	pk->publicExponent = e;
	pk->modulus = n;
	return pk;
}

#ifdef K_AND_R
_TYPE( RSAPrivateKey * )
buildRSAPrivateKey(e, d, p, q, dp, dq, c12)
  BigInt e, d, p, q, dp, dq, c12;
#else
_TYPE( RSAPrivateKey * ) buildRSAPrivateKey(BigInt e,
					    BigInt d,
					    BigInt p,
					    BigInt q,
					    BigInt dp,
					    BigInt dq,
					    BigInt c12)
#endif
{
	RSAPrivateKey *pk;
	ChineseRemStruct *crt;
#ifdef DLLEXPORT
	HGLOBAL crt_handle = clib_malloc(sizeof(ChineseRemStruct));
	HGLOBAL handle = clib_malloc(sizeof(RSAPrivateKey));
	crt = (ChineseRemStruct *)GlobalLock(crt_handle);
	crt->crt_handle = crt_handle;
	pk = (RSAPrivateKey *)GlobalLock(handle);
	pk->privkey_handle = handle;
#else
	crt = (ChineseRemStruct *)clib_malloc(sizeof(ChineseRemStruct));
	pk = (RSAPrivateKey *)clib_malloc(sizeof(RSAPrivateKey));
#endif
	
	pk->publicExponent = e;
	pk->privateExponent = d;
	pk->modulus = bigInit(0);
	bigMultiply(p, q, pk->modulus);
	
	pk->crt = crt;
	pk->crt->p = p;
	pk->crt->q = q;
	pk->crt->dp = dp;
	pk->crt->dq = dq;
	pk->crt->c12 = c12;
	
	return pk;
}

#ifdef K_AND_R
_TYPE( RSAKeySet * )
buildRSAKeySet(e, d, p, q)
  BigInt e, d, p, q;
#else
_TYPE( RSAKeySet * ) buildRSAKeySet(BigInt e,
				    BigInt d,
				    BigInt p,
				    BigInt q)
#endif
{
	BigInt pminus1, qminus1, n, dp, dq, c12;
	BigInt ecopy, dcopy;
	RSAKeySet *ks;
#ifdef DLLEXPORT
	HGLOBAL ks_handle = clib_malloc(sizeof(RSAKeySet));
	ks = (RSAKeySet *)GlobalLock(ks_handle);
	ks->keyset_handle = ks_handle;
#else
	ks = (RSAKeySet *)clib_malloc(sizeof(RSAKeySet));
#endif
	n = bigInit(0);
	bigMultiply(p, q, n);
	
	ecopy = bigInit(0);
	bigCopy(e, ecopy);
	ks->publicKey = buildRSAPublicKey(ecopy, n);
	
	pminus1 = bigInit(0);
	qminus1 = bigInit(0);
	bigSubtract(p, one, pminus1);
	bigSubtract(q, one, qminus1);
	
	dp = bigInit(0);
	dq = bigInit(0);
	bigMod(d, pminus1, dp);
	bigMod(d, qminus1, dq);
	
	c12 = bigInit(0);
	getInverse(q, p, c12);

	ecopy = bigInit(0);
	bigCopy(e, ecopy);
	dcopy = bigInit(0);
	bigCopy(d, dcopy);
	ks->privateKey = buildRSAPrivateKey(ecopy, dcopy, p, q,
					    dp, dq, c12);
	
	freeBignum(pminus1);
	freeBignum(qminus1);
	
	return ks;
}


#ifdef K_AND_R
static void
genPrimesFor3(nbits, p, q, r1, r2)
  int nbits;
  BigInt p, q, r1, r2;
#else
  static void genPrimesFor3(int nbits,
			    BigInt p,
			    BigInt q,
			    BigInt r1,
			    BigInt r2)
#endif
{
	BigInt ngcd, ignore, three, pminus1, qminus1;
	
	ignore = bigInit(0);
	three = bigInit(3);
	pminus1 = bigInit(0);
	qminus1 = bigInit(0);

	/* Gordon algorithm doesn't care about the p-1 factor size */
	genStrongPrimeSet(nbits/2, p, (int)NULL, ignore, GORDON, r1);
	bigSubtract(p, one, pminus1);
	ngcd = gcd(three, pminus1);
	while (bigCompare(ngcd, one) != 0) {
		if (r1 != NULL)
			randomize(r1);
		freeBignum(ngcd);
		genStrongPrimeSet(nbits/2, p, (int)NULL, ignore, GORDON, r1);
		bigSubtract(p, one, pminus1);
		ngcd = gcd(three, pminus1);
	}
	freeBignum(ngcd);
	
	genStrongPrimeSet(nbits/2, q, (int)NULL, ignore, GORDON, r2);
	bigSubtract(q, one, qminus1);
	ngcd = gcd(three, qminus1);
	while (bigCompare(ngcd, one) != 0) {
		if (r2 != NULL)
			randomize(r2);
		freeBignum(ngcd);
		genStrongPrimeSet(nbits/2, q, (int)NULL, ignore, GORDON, r2);
		bigSubtract(q, one, qminus1);
		ngcd = gcd(three, qminus1);
	}
	freeBignum(ngcd);
	freeBignum(pminus1);
	freeBignum(qminus1);
	freeBignum(ignore);
	freeBignum(three);
}


#ifdef K_AND_R
_TYPE( int )
randBytesNeededForRSA (modlen, ebits)
  int modlen, ebits;
#else
_TYPE( int ) randBytesNeededForRSA (int modlen, int ebits)
#endif
{
	int bytes;

	bytes = ((modlen + ebits)/8) + ((modlen+ebits)%8? 1: 0);

	return bytes;
}

#ifdef K_AND_R
_TYPE( RSAKeySet * )
genRSAKeySet(nbits, ebits, e, randomStart)
  Ulong nbits, ebits, randomStart;
  BigInt e;
#else
_TYPE( RSAKeySet * ) genRSAKeySet(int nbits,
				  int ebits,
				  BigInt e,
				  BigInt randomStart)
#endif
{
	BigInt p, q, ignore, r1, r2;
	Key_exps *exps;
	RSAKeySet *key_set;
	int oldlen;
	BigInt randStart;
	
	p = bigInit(0);
	q = bigInit(0);
	r1 = NULL;
	r2 = NULL;
	randStart = NULL;
	if (randomStart != NULL) {
		r1 = bigInit(0);
		r2 = bigInit(0);
		randStart = bigInit(0);
		bigCopy(randomStart, randStart);
		oldlen = LENGTH(randStart);
		LENGTH(randStart) = nbits/32/2;
		bigCopy(randStart, r1);
		LENGTH(randStart) = oldlen;
		bigRightShift(randStart, nbits/2, randStart);
		oldlen = LENGTH(randStart);
		LENGTH(randStart) = nbits/32/2;
		bigCopy(randStart, r2);
		LENGTH(randStart) = oldlen;
		bigRightShift(randStart, nbits/2, randStart);
	}
	if (ebits == 2)
		genPrimesFor3(nbits, p, q, r1, r2);
	
	else {
		ignore = bigInit(0);
		genStrongPrimeSet(nbits/2, p, (int)NULL, ignore, GORDON, r1);
		genStrongPrimeSet(nbits/2, q, (int)NULL, ignore, GORDON, r2);
		freeBignum(ignore);
	}
	exps = genKeyExps(p, q, e, ebits, randStart);
	key_set = buildRSAKeySet(exps->e, exps->d, p, q);
	freeBignum(exps->e);
	freeBignum(exps->d);
	if (r1 != NULL) {
		freeBignum(r1);
		freeBignum(r2);
		freeBignum(randStart);
	}
#ifdef DLLEXPORT
	GlobalUnlock(exps->exp_handle);
	GlobalFree(exps->exp_handle);
#else
	free((char *)exps);
#endif
	return key_set;
}


/*
   Chinese Remainder Theorem reconstruction of m^d mod n, using
   m^dp mod p and m^dq mod q with dp = d mod p-1, dq = d mod q-1.
   */
#ifdef K_AND_R
static void
chineseRemTheorem(m, key, em)
  BigInt m, em;
  RSAPrivateKey *key;
#else
  static void chineseRemTheorem(BigInt m,
				RSAPrivateKey *key,
				BigInt em)
#endif
{
	BigInt u1, u2;
	BigInt p, q, dp, dq, c12;
	
	p = key->crt->p;
	q = key->crt->q;
	dp = key->crt->dp;
	dq = key->crt->dq;
	c12 = key->crt->c12;
	
	u1 = bigInit(0);
	u2 = bigInit(0);

	bigPow(m, dp, p, u1);
	bigPow(m, dq, q, u2);
	
	crtCombine(u1, u2, p, q, c12, em);
	
	freeBignum(u1);
	freeBignum(u2);
	
}

#ifdef K_AND_R
_TYPE( void )
freeRSAPublicKey(pk)
  RSAPublicKey *pk;
#else
_TYPE( void ) freeRSAPublicKey(RSAPublicKey *pk)
#endif
{
	freeBignum(pk->publicExponent);
	freeBignum(pk->modulus);
#ifdef DLLEXPORT
	GlobalUnlock(pk->pubkey_handle);
	GlobalFree(pk->pubkey_handle);
#else
	free((char *)pk);
#endif
}

#ifdef K_AND_R
_TYPE( void )
freeRSAPrivateKey(pk)
  RSAPrivateKey *pk;
#else
_TYPE( void ) freeRSAPrivateKey(RSAPrivateKey *pk)
#endif
{
	freeBignum(pk->publicExponent);
	freeBignum(pk->privateExponent);
	freeBignum(pk->modulus);
	freeBignum(pk->crt->p);
	freeBignum(pk->crt->q);
	freeBignum(pk->crt->dp);
	freeBignum(pk->crt->dq);
	freeBignum(pk->crt->c12);
#ifdef DLLEXPORT
	GlobalUnlock(pk->crt->crt_handle);
	GlobalFree(pk->crt->crt_handle);
	GlobalUnlock(pk->privkey_handle);
	GlobalFree(pk->privkey_handle);
#else
	free((char *)pk->crt);
	free((char *)pk);
#endif	
}

#ifdef K_AND_R
_TYPE( void )
freeRSAKeys(ks)
  RSAKeySet *ks;
#else
_TYPE( void ) freeRSAKeys(RSAKeySet *ks)
#endif
{
	
	freeRSAPublicKey(ks->publicKey);
	freeRSAPrivateKey(ks->privateKey);
#ifdef DLLEXPORT
	GlobalUnlock(ks->keyset_handle);
	GlobalFree(ks->keyset_handle);
#else
	free((char *)ks);
#endif
}

#ifdef K_AND_R
_TYPE( BigInt )
RSAEncrypt(message, key)
  BigInt message;
  RSAPublicKey *key;
#else
_TYPE( BigInt ) RSAEncrypt(BigInt message,
			   RSAPublicKey *key)
#endif
{
	BigInt result;
	
	result = bigInit(3);
	if (bigCompare(key->publicExponent, result) == 0) {
		reset_big(result, 0);
		bigCube(message, key->modulus, result);
	}
	else {
		reset_big(result, 0);
		bigPow(message, key->publicExponent, key->modulus, result);
	}
	return result;
}

#ifdef K_AND_R
_TYPE( BigInt )
RSADecrypt(message, key)
  BigInt message;
  RSAPrivateKey *key;
#else
_TYPE( BigInt ) RSADecrypt(BigInt message,
			   RSAPrivateKey *key)
#endif
{
	BigInt result;
	
	result = bigInit(0);
	
	chineseRemTheorem(message, key, result);
	return result;
	
}


#ifdef K_AND_R
_TYPE( RSASignature * )
RSASign(message, key)
  BigInt message;
  RSAPrivateKey *key;
#else
_TYPE( RSASignature * ) RSASign(BigInt message,
				RSAPrivateKey *key)
#endif
{
	return (RSASignature *)RSADecrypt(message, key);
}


#ifdef K_AND_R
_TYPE( Boolean )
RSAVerify(message, sig, key)
  BigInt message;
  RSASignature *sig;
  RSAPublicKey *key;
#else
_TYPE( Boolean ) RSAVerify(BigInt message,
			   RSASignature *sig,
			   RSAPublicKey *key)
#endif
{
	Boolean retval;
	BigInt cmp;
	
	cmp = (BigInt)RSAEncrypt((BigInt)sig, key);
	
	if (bigCompare(message, cmp) == 0)
		retval = TRUE;
	else
		retval = FALSE;
	
	freeBignum(cmp);
	
	return retval;
}

#ifdef K_AND_R
_TYPE( void )
freeRSASig(sig)
  RSASignature *sig;
#else
_TYPE( void ) freeRSASig(RSASignature *sig)
#endif
{
	freeBignum((BigInt)sig);
}

#ifdef K_AND_R
_TYPE( void )
RSAPrivateKeyDesEncrypt(pk, deskey)
  RSAPrivateKey *pk;
  unsigned char *deskey;
#else
_TYPE( void )
RSAPrivateKeyDesEncrypt(RSAPrivateKey *pk, unsigned char *deskey)
#endif
{
	bignumDesEncrypt(pk->publicExponent, deskey);
	bignumDesEncrypt(pk->privateExponent, deskey);
	bignumDesEncrypt(pk->modulus, deskey);
	bignumDesEncrypt(pk->crt->p, deskey);
	bignumDesEncrypt(pk->crt->q, deskey);
	bignumDesEncrypt(pk->crt->dp, deskey);
	bignumDesEncrypt(pk->crt->dq, deskey);
	bignumDesEncrypt(pk->crt->c12, deskey);
}

#ifdef K_AND_R
_TYPE( void )
RSAPrivateKeyDesDecrypt(pk, deskey)
  RSAPrivateKey *pk;
  unsigned char *deskey;
#else
_TYPE( void )
RSAPrivateKeyDesDecrypt(RSAPrivateKey *pk, unsigned char *deskey)
#endif
{
	bignumDesDecrypt(pk->publicExponent, deskey);
	bignumDesDecrypt(pk->privateExponent, deskey);
	bignumDesDecrypt(pk->modulus, deskey);
	bignumDesDecrypt(pk->crt->p, deskey);
	bignumDesDecrypt(pk->crt->q, deskey);
	bignumDesDecrypt(pk->crt->dp, deskey);
	bignumDesDecrypt(pk->crt->dq, deskey);
	bignumDesDecrypt(pk->crt->c12, deskey);
}

#ifdef K_AND_R
_TYPE( BigInt )
quantized_RSADecrypt(m, key)
  BigInt m;
  RSAPrivateKey *key;
#else
_TYPE( BigInt )
quantized_RSADecrypt(BigInt m, RSAPrivateKey *key)
#endif
{
	BigInt result;

	start_quantize(STD_QUANTUM);
	result = RSADecrypt(m, key);
	end_quantize();

	return result;
}


#ifdef K_AND_R
_TYPE( RSASignature *)
quantized_RSASign(m, key)
  BigInt m;
  RSAPrivateKey *key;
#else
_TYPE( RSASignature *)
quantized_RSASign(BigInt m, RSAPrivateKey *key)
#endif
{
	return (RSASignature *)quantized_RSADecrypt(m, key);
}