Why do I *still* need RSA?

Markus Friedl markus.friedl at informatik.uni-erlangen.de
Mon Jul 24 00:00:21 EST 2000


On Wed, Jul 19, 2000 at 12:16:01AM -0700, Robbie Stone wrote:
> 	When I attempt to build OpenSSH against an OpenSSL build without rc5,
> idea, or rsa it bombs since OpenSSL doesn't place the header files in
> the include dir. Now, that's fine and went away after I copied them to
> the appropriate location (hoping that it just *needed* the file, but
> that it didn't need any rc5, idea, or rsa functions exported by the
> OpenSSL libraries) but it looks like the RSA (aka, non SSH-2.0)
> functions are required to have a successful build of OpenSSH.

you still need RSA defines and stub-routines if you want to build
OpenSSH w/o RSA. you can patch OpenSSL with a patch similar to the
attached one. it replaces the RSA function calls with functions returning
error codes. but it should be easy to add dummy functions and struct RSA
defines to OpenSSH and exclude RSA from OpenSSL.

> 	Then question now is how OpenBSD is making available a solely SSH 2.0
> client/server without RSA, IDEA or RC5. I noticed on the OpenBSD web
> site that it became RSA equipped upon the installation of the rsaref
> module, but how to I make a system like that under something that isn't
> OpenBSD?

openbsd ships an openssl libcrypto that includes dummy rsa functions
returning errors if called.

-markus
-------------- next part --------------
diff -u --recursive /usr/src/lib/libssl/src/crypto/rsa/rsa_eay.c ./crypto/rsa/rsa_eay.c
--- /usr/src/lib/libssl/src/crypto/rsa/rsa_eay.c	Tue Apr 11 19:19:52 2000
+++ ./crypto/rsa/rsa_eay.c	Tue Apr 11 19:44:59 2000
@@ -1,13 +1,3 @@
-
-/* This file has been explicitly broken by ryker for OpenBSD, July
- * 1, 1998. In spite of the title, there is no implementation of the
- * RSA algorithm left in this file. All these routines will return an
- * error and fail when called. They exist as stubs and can be
- * ressurected from the bit bucket by someone in the free world once
- * the RSA algorithm is no longer subject to patent problems. Eric
- * Young's original copyright is below. 
- */
-
 /* crypto/rsa/rsa_eay.c */
 /* Copyright (C) 1995-1998 Eric Young (eay at cryptsoft.com)
  * All rights reserved.
@@ -184,13 +174,62 @@
 	unsigned char *buf=NULL;
 	BN_CTX *ctx=NULL;
 
-        BN_init(&f);
-        BN_init(&ret);
+	BN_init(&f);
+	BN_init(&ret);
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	if ((ctx=BN_CTX_new()) == NULL) goto err;
+	num=BN_num_bytes(rsa->n);
+	if ((buf=(unsigned char *)Malloc(num)) == NULL)
+		{
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT,ERR_R_MALLOC_FAILURE);
+		goto err;
+		}
 
+	switch (padding)
+		{
+	case RSA_PKCS1_PADDING:
+		i=RSA_padding_add_PKCS1_type_1(buf,num,from,flen);
+		break;
+	case RSA_NO_PADDING:
+		i=RSA_padding_add_none(buf,num,from,flen);
+		break;
+	case RSA_SSLV23_PADDING:
+	default:
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
+		goto err;
+		}
+	if (i <= 0) goto err;
+
+	if (BN_bin2bn(buf,num,&f) == NULL) goto err;
+
+	if ((rsa->flags & RSA_FLAG_BLINDING) && (rsa->blinding == NULL))
+		RSA_blinding_on(rsa,ctx);
+	if (rsa->flags & RSA_FLAG_BLINDING)
+		if (!BN_BLINDING_convert(&f,rsa->blinding,ctx)) goto err;
+
+	if ( (rsa->flags & RSA_FLAG_EXT_PKEY) ||
+		((rsa->p != NULL) &&
+		(rsa->q != NULL) &&
+		(rsa->dmp1 != NULL) &&
+		(rsa->dmq1 != NULL) &&
+		(rsa->iqmp != NULL)) )
+		{ if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err; }
+	else
+		{
+		if (!rsa->meth->bn_mod_exp(&ret,&f,rsa->d,rsa->n,ctx,NULL)) goto err;
+		}
+
+	if (rsa->flags & RSA_FLAG_BLINDING)
+		if (!BN_BLINDING_invert(&ret,rsa->blinding,ctx)) goto err;
+
+	/* put in leading 0 bytes if the number is less than the
+	 * length of the modulus */
+	j=BN_num_bytes(&ret);
+	i=BN_bn2bin(&ret,&(to[num-j]));
+	for (k=0; k<(num-i); k++)
+		to[k]=0;
+
+	r=num;
 err:
 	if (ctx != NULL) BN_CTX_free(ctx);
 	BN_clear_free(&ret);
@@ -212,12 +251,77 @@
 	unsigned char *buf=NULL;
 	BN_CTX *ctx=NULL;
 
-        BN_init(&f);
-        BN_init(&ret);
+	BN_init(&f);
+	BN_init(&ret);
+	ctx=BN_CTX_new();
+	if (ctx == NULL) goto err;
+
+	num=BN_num_bytes(rsa->n);
+
+	if ((buf=(unsigned char *)Malloc(num)) == NULL)
+		{
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,ERR_R_MALLOC_FAILURE);
+		goto err;
+		}
+
+	/* This check was for equality but PGP does evil things
+	 * and chops off the top '0' bytes */
+	if (flen > num)
+		{
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_DATA_GREATER_THAN_MOD_LEN);
+		goto err;
+		}
+
+	/* make data into a big number */
+	if (BN_bin2bn(from,(int)flen,&f) == NULL) goto err;
+
+	if ((rsa->flags & RSA_FLAG_BLINDING) && (rsa->blinding == NULL))
+		RSA_blinding_on(rsa,ctx);
+	if (rsa->flags & RSA_FLAG_BLINDING)
+		if (!BN_BLINDING_convert(&f,rsa->blinding,ctx)) goto err;
+
+	/* do the decrypt */
+	if ( (rsa->flags & RSA_FLAG_EXT_PKEY) ||
+		((rsa->p != NULL) &&
+		(rsa->q != NULL) &&
+		(rsa->dmp1 != NULL) &&
+		(rsa->dmq1 != NULL) &&
+		(rsa->iqmp != NULL)) )
+		{ if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err; }
+	else
+		{
+		if (!rsa->meth->bn_mod_exp(&ret,&f,rsa->d,rsa->n,ctx,NULL))
+			goto err;
+		}
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	if (rsa->flags & RSA_FLAG_BLINDING)
+		if (!BN_BLINDING_invert(&ret,rsa->blinding,ctx)) goto err;
+
+	p=buf;
+	j=BN_bn2bin(&ret,p); /* j is only used with no-padding mode */
+
+	switch (padding)
+		{
+	case RSA_PKCS1_PADDING:
+		r=RSA_padding_check_PKCS1_type_2(to,num,buf,j,num);
+		break;
+#ifndef NO_SHA
+        case RSA_PKCS1_OAEP_PADDING:
+	        r=RSA_padding_check_PKCS1_OAEP(to,num,buf,j,num,NULL,0);
+                break;
+#endif
+ 	case RSA_SSLV23_PADDING:
+		r=RSA_padding_check_SSLv23(to,num,buf,j,num);
+		break;
+	case RSA_NO_PADDING:
+		r=RSA_padding_check_none(to,num,buf,j,num);
+		break;
+	default:
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
+		goto err;
+		}
+	if (r < 0)
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_PADDING_CHECK_FAILED);
 
 err:
 	if (ctx != NULL) BN_CTX_free(ctx);
@@ -240,12 +344,56 @@
 	unsigned char *buf=NULL;
 	BN_CTX *ctx=NULL;
 
-        BN_init(&f);
-        BN_init(&ret);
+	BN_init(&f);
+	BN_init(&ret);
+	ctx=BN_CTX_new();
+	if (ctx == NULL) goto err;
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	num=BN_num_bytes(rsa->n);
+	buf=(unsigned char *)Malloc(num);
+	if (buf == NULL)
+		{
+		RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,ERR_R_MALLOC_FAILURE);
+		goto err;
+		}
+
+	/* This check was for equality but PGP does evil things
+	 * and chops off the top '0' bytes */
+	if (flen > num)
+		{
+		RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_DATA_GREATER_THAN_MOD_LEN);
+		goto err;
+		}
+
+	if (BN_bin2bn(from,flen,&f) == NULL) goto err;
+	/* do the decrypt */
+	if ((rsa->_method_mod_n == NULL) && (rsa->flags & RSA_FLAG_CACHE_PUBLIC))
+		{
+		if ((rsa->_method_mod_n=BN_MONT_CTX_new()) != NULL)
+			if (!BN_MONT_CTX_set(rsa->_method_mod_n,rsa->n,ctx))
+			    goto err;
+		}
+
+	if (!rsa->meth->bn_mod_exp(&ret,&f,rsa->e,rsa->n,ctx,
+		rsa->_method_mod_n)) goto err;
+
+	p=buf;
+	i=BN_bn2bin(&ret,p);
+
+	switch (padding)
+		{
+	case RSA_PKCS1_PADDING:
+		r=RSA_padding_check_PKCS1_type_1(to,num,buf,i,num);
+		break;
+	case RSA_NO_PADDING:
+		r=RSA_padding_check_none(to,num,buf,i,num);
+		break;
+	default:
+		RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
+		goto err;
+		}
+	if (r < 0)
+		RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_PADDING_CHECK_FAILED);
 
 err:
 	if (ctx != NULL) BN_CTX_free(ctx);
@@ -263,15 +411,59 @@
 	{
 	BIGNUM r1,m1;
 	int ret=0;
-	BN_CTX *ctx = NULL;
+	BN_CTX *ctx;
 
+	if ((ctx=BN_CTX_new()) == NULL) goto err;
 	BN_init(&m1);
 	BN_init(&r1);
-	if ((ctx=BN_CTX_new()) == NULL) goto err;
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	if (rsa->flags & RSA_FLAG_CACHE_PRIVATE)
+		{
+		if (rsa->_method_mod_p == NULL)
+			{
+			if ((rsa->_method_mod_p=BN_MONT_CTX_new()) != NULL)
+				if (!BN_MONT_CTX_set(rsa->_method_mod_p,rsa->p,
+						     ctx))
+					goto err;
+			}
+		if (rsa->_method_mod_q == NULL)
+			{
+			if ((rsa->_method_mod_q=BN_MONT_CTX_new()) != NULL)
+				if (!BN_MONT_CTX_set(rsa->_method_mod_q,rsa->q,
+						     ctx))
+					goto err;
+			}
+		}
+
+	if (!BN_mod(&r1,I,rsa->q,ctx)) goto err;
+	if (!rsa->meth->bn_mod_exp(&m1,&r1,rsa->dmq1,rsa->q,ctx,
+		rsa->_method_mod_q)) goto err;
+
+	if (!BN_mod(&r1,I,rsa->p,ctx)) goto err;
+	if (!rsa->meth->bn_mod_exp(r0,&r1,rsa->dmp1,rsa->p,ctx,
+		rsa->_method_mod_p)) goto err;
+
+	if (!BN_sub(r0,r0,&m1)) goto err;
+	/* This will help stop the size of r0 increasing, which does
+	 * affect the multiply if it optimised for a power of 2 size */
+	if (r0->neg)
+		if (!BN_add(r0,r0,rsa->p)) goto err;
+
+	if (!BN_mul(&r1,r0,rsa->iqmp,ctx)) goto err;
+	if (!BN_mod(r0,&r1,rsa->p,ctx)) goto err;
+	/* If p < q it is occasionally possible for the correction of
+         * adding 'p' if r0 is negative above to leave the result still
+	 * negative. This can break the private key operations: the following
+	 * second correction should *always* correct this rare occurrence.
+	 * This will *never* happen with OpenSSL generated keys because
+         * they ensure p > q [steve]
+         */
+	if (r0->neg)
+		if (!BN_add(r0,r0,rsa->p)) goto err;
+	if (!BN_mul(&r1,r0,rsa->q,ctx)) goto err;
+	if (!BN_add(r0,&r1,&m1)) goto err;
+
+	ret=1;
 err:
 	BN_clear_free(&m1);
 	BN_clear_free(&r1);
diff -u --recursive /usr/src/lib/libssl/src/crypto/rsa/rsa_gen.c ./crypto/rsa/rsa_gen.c
--- /usr/src/lib/libssl/src/crypto/rsa/rsa_gen.c	Sun Mar 19 04:11:39 2000
+++ ./crypto/rsa/rsa_gen.c	Tue Apr 11 19:44:59 2000
@@ -74,11 +74,108 @@
 	if (ctx == NULL) goto err;
 	ctx2=BN_CTX_new();
 	if (ctx2 == NULL) goto err;
+	BN_CTX_start(ctx);
+	r0 = BN_CTX_get(ctx);
+	r1 = BN_CTX_get(ctx);
+	r2 = BN_CTX_get(ctx);
+	r3 = BN_CTX_get(ctx);
+	if (r3 == NULL) goto err;
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	bitsp=(bits+1)/2;
+	bitsq=bits-bitsp;
+	rsa=RSA_new();
+	if (rsa == NULL) goto err;
 
+	/* set e */ 
+	rsa->e=BN_new();
+	if (rsa->e == NULL) goto err;
+
+#if 1
+	/* The problem is when building with 8, 16, or 32 BN_ULONG,
+	 * unsigned long can be larger */
+	for (i=0; i<sizeof(unsigned long)*8; i++)
+		{
+		if (e_value & (1<<i))
+			BN_set_bit(rsa->e,i);
+		}
+#else
+	if (!BN_set_word(rsa->e,e_value)) goto err;
+#endif
+
+	/* generate p and q */
+	for (;;)
+		{
+		rsa->p=BN_generate_prime(NULL,bitsp,0,NULL,NULL,callback,cb_arg);
+		if (rsa->p == NULL) goto err;
+		if (!BN_sub(r2,rsa->p,BN_value_one())) goto err;
+		if (!BN_gcd(r1,r2,rsa->e,ctx)) goto err;
+		if (BN_is_one(r1)) break;
+		if (callback != NULL) callback(2,n++,cb_arg);
+		BN_free(rsa->p);
+		}
+	if (callback != NULL) callback(3,0,cb_arg);
+	for (;;)
+		{
+		rsa->q=BN_generate_prime(NULL,bitsq,0,NULL,NULL,callback,cb_arg);
+		if (rsa->q == NULL) goto err;
+		if (!BN_sub(r2,rsa->q,BN_value_one())) goto err;
+		if (!BN_gcd(r1,r2,rsa->e,ctx)) goto err;
+		if (BN_is_one(r1) && (BN_cmp(rsa->p,rsa->q) != 0))
+			break;
+		if (callback != NULL) callback(2,n++,cb_arg);
+		BN_free(rsa->q);
+		}
+	if (callback != NULL) callback(3,1,cb_arg);
+	if (BN_cmp(rsa->p,rsa->q) < 0)
+		{
+		tmp=rsa->p;
+		rsa->p=rsa->q;
+		rsa->q=tmp;
+		}
+
+	/* calculate n */
+	rsa->n=BN_new();
+	if (rsa->n == NULL) goto err;
+	if (!BN_mul(rsa->n,rsa->p,rsa->q,ctx)) goto err;
+
+	/* calculate d */
+	if (!BN_sub(r1,rsa->p,BN_value_one())) goto err;	/* p-1 */
+	if (!BN_sub(r2,rsa->q,BN_value_one())) goto err;	/* q-1 */
+	if (!BN_mul(r0,r1,r2,ctx)) goto err;	/* (p-1)(q-1) */
+
+/* should not be needed, since gcd(p-1,e) == 1 and gcd(q-1,e) == 1 */
+/*	for (;;)
+		{
+		if (!BN_gcd(r3,r0,rsa->e,ctx)) goto err;
+		if (BN_is_one(r3)) break;
+
+		if (1)
+			{
+			if (!BN_add_word(rsa->e,2L)) goto err;
+			continue;
+			}
+		RSAerr(RSA_F_RSA_GENERATE_KEY,RSA_R_BAD_E_VALUE);
+		goto err;
+		}
+*/
+	rsa->d=BN_mod_inverse(NULL,rsa->e,r0,ctx2);	/* d */
+	if (rsa->d == NULL) goto err;
+
+	/* calculate d mod (p-1) */
+	rsa->dmp1=BN_new();
+	if (rsa->dmp1 == NULL) goto err;
+	if (!BN_mod(rsa->dmp1,rsa->d,r1,ctx)) goto err;
+
+	/* calculate d mod (q-1) */
+	rsa->dmq1=BN_new();
+	if (rsa->dmq1 == NULL) goto err;
+	if (!BN_mod(rsa->dmq1,rsa->d,r2,ctx)) goto err;
+
+	/* calculate inverse of q mod p */
+	rsa->iqmp=BN_mod_inverse(NULL,rsa->q,rsa->p,ctx2);
+	if (rsa->iqmp == NULL) goto err;
+
+	ok=1;
 err:
 	if (ok == -1)
 		{


More information about the openssh-unix-dev mailing list