Re: [PATCH RESEND 1/1] crypto API: RSA algorithm patch (kernelversion 2.6.20.1) (and i hope pine does not break it either)

[Randy Dunlap]

On Mon, 19 Mar 2007 19:22:00 +0200 (EET) Tasos Parisinos wrote:

> As mentioned in the subject this patch applies in kernel version 2.6.20.1.

It needs to apply to Linus's current tree (and it doesn't).

> diff -uprN -X linux-2.6.20.1-vanilla/Documentation/dontdiff linux-2.6.20.1/crypto/Kconfig linux-2.6.20.1-vanilla/crypto/Kconfig
> --- linux-2.6.20.1/crypto/Kconfig	2007-02-20 08:34:32.000000000 +0200
> +++ linux-2.6.20.1-vanilla/crypto/Kconfig	2007-03-11 14:12:24.000000000 +0200
> @@ -458,6 +458,46 @@ config CRYPTO_CRC32C
>   	  See Castagnoli93.  This implementation uses lib/libcrc32c.
>             Module will be crc32c.
> 
> +config CRYPTO_RSA
> +	tristate "RSA cipher algorithm"
> +	depends on CRYPTO
> +	help
> +	  The famous RSA asymmetric cipher algorithm. This may be used in-kernel
> +	  (no userland interface yet) to compute modular exponentiation.  It can
> +	  be also used to do some multi-precision arithmetics.
> +
> +	  If it is selected it will add approximately 8K to the kernel size.
> +	  Select M to build this driver as a module.
> +	  If unsure say N.
> +
> +config CRYPTO_RSA_DEBUG
> +	bool "Debugging capabilities"
> +	depends on CRYPTO_RSA
> +	help
> +		This adds lots of debugging information and debugging capabilities in
> +		the rsa module. It also adds approximately 1 more K to the kernel.

Use <tab><space><space> to indent kconfig help text (as done up above
and below).

> +config RSA_AUXCOUNT
> +	int "Initial preallocated mpi pool size"
> +	default "8"
> +	depends on CRYPTO_RSA
> +	help
> +	  The rsa module needs some preallocated space to avoid computation-time
> +	  allocations. The 'mpi' is the struct used by the rsa module to hold  a
> +	  multi-precision integer, so this setting is the number of mpi's alloca
> +	  ted at module load time.
> +
> +config RSA_AUXSIZE
> +	int "Initial preallocated mpi limb size"
> +	default "128"
> +	depends on CRYPTO_RSA && RSA_AUXCOUNT!="0"
> +	help
> +	  The rsa module needs some preallocated space to avoid computation-time
> +	  allocations. The 'mpi' is the struct used by the rsa module to hold  a
                                                       extra space after ^^^^
> +	  multi-precision  integer. This struct maps a number on multiple 32 bit
> +	  limbs (it is actually a 32 bit array).Here you select the default size
                                                ^space (move one from above :)

> +	  (in limbs) of the preallocated mpis.
> +
>   config CRYPTO_TEST
>   	tristate "Testing module"
>   	depends on m

> diff -uprN -X linux-2.6.20.1-vanilla/Documentation/dontdiff linux-2.6.20.1/crypto/rsa.c linux-2.6.20.1-vanilla/crypto/rsa.c
> --- linux-2.6.20.1/crypto/rsa.c	1970-01-01 02:00:00.000000000 +0200
> +++ linux-2.6.20.1-vanilla/crypto/rsa.c	2007-03-19 16:45:21.000000000 +0200
> @@ -0,0 +1,884 @@
> +
> +#include "rsa.h"
> +
> +static mpi *	aux[RSA_AUX_COUNT];

Kernel style is:
static mpi *aux[RSA_AUX_COUNT];

> +static _u32 	modinv = 0;

No need to init to 0, plus it bloats the codefile.

> +static inline _i32 rsa_max(_i32 x, _i32 y)
> +{
> +	return (x > y)? x: y;
> +}

Use min_t() from kernel.h ?

> +
> +/*
> + * Module loading callback function
> + *
> + * Returns 0 on success or a negative value indicating error
> + */
> +static _err __init rsa_load(void)
> +{
> +	_u32 i;
> +	_err retval = RSA_NO_ERR;
> +
> +	/* Pre-allocate some auxilliary mpis */
> +	rsa_echo("Preallocating %lu bytes for auxilliary operands\n",
> +		 RSA_AUX_SIZE * RSA_AUX_COUNT * sizeof(_u32));
> +
> +	memset(&aux, 0, sizeof(aux));
> +	for(i = 0; i < RSA_AUX_COUNT; i++) {

style:  space after "for" and after "if" (many locations)

> +		retval = rsa_mpi_alloc(&aux[i], RSA_AUX_SIZE);
> +		if(retval < 0)
> +			goto rollback;
> +	}
> +
> +	rsa_echo("RSA cipher algorithm module initialized\n");
> +	return RSA_NO_ERR;
> +
> +/* Free all allocated resources if any errors occur */
> +rollback:
> +	for(i = 0; i < RSA_AUX_COUNT; i++)
> +		rsa_mpi_free(aux[i]);
> +	return retval;
> +}

> +/*
> + * Preallocate an mpi. The allocated mpi will be all-zeroed and not
> + * canonicalized.
> + *
> + * Returns 0 on success or a negative value indicating error
> + *
> + * @n: 	  pointer pointer to the allocated mpi
> + * @limbs: number of allocated limbs (32 bit digits)
> + */
> +static _err rsa_mpi_alloc(mpi ** n, _i32 limbs)
> +{
> +	mpi * handle;
> +
> +	*n = NULL;
> +	if(!limbs)
> +		return RSA_ERR_INVARG;
> +
> +	/* Allocate space for the mpi */
> +	handle = *n = kmalloc(sizeof(mpi), GFP_KERNEL);
> +	if(!handle) {
> +		rsa_debug("%s: kmalloc failed\n", __FUNCTION__);
> +		return RSA_ERR_NOMEM;
> +	}
> +
> +	handle->data = kzalloc(limbs * sizeof(_u32), GFP_KERNEL);
> +	if(!handle->data) {
> +		kfree(handle);
> +		*n = NULL;
> +		rsa_debug("%s: kzalloc failed\n", __FUNCTION__);
> +		return RSA_ERR_NOMEM;
> +	}
> +
> +	handle->sign = 0;
> +	handle->size = handle->limbs = limbs;
> +	return RSA_NO_ERR;
> +}

> +/*
> + * Initialize an mpi given its hex (absolute) value. The optional leading
> + * zeroes will be taken into account, so that the mpi created will not be
> + * canonicalized
> + *
> + * Returns 0 on success or a negative value indicating error
> + *
> + * @n:	  pointer pointer to the allocated mpi
> + * @str:  hex data
> + * @size: sizeof(str)
> + * @xtra: how many extra limbs to preallocate to avoid reallocations
> + */
> +static _err rsa_mpi_init(mpi ** n, _u8 * str, _u32 size, _u32 xtra)
> +{
> +	_i32 i, j;
> +	_u32 * buf;
> +	_i32 s;
> +	_err retval;
> +
> +	*n = NULL;
> +	if(!size && !xtra) {
> +		rsa_debug("%s: invalid initialization string\n", __FUNCTION__);
> +		return RSA_ERR_INVARG;
> +	}
> +
> +	/* Allocate space for the mpi and its data */
> +	s = (size / 4) + ((size % 4)? 1: 0);

That's usually done as:
	s = (size + 3) / 4;
which appears to be:
	s = DIV_ROUND_UP(size, 4);

> +	retval = rsa_mpi_alloc(n, s + xtra);
> +	if(retval < 0)
> +		return retval;
> +
> +	(*n)->size = s;
> +	buf = (*n)->data;
> +
> +	/* Copy the data */
> +	for(i = size - 1, j = 0; i >= 0; i--, j++)
> +		buf[j / 4] |= ((_u32)str[i] << ((j % 4) * 8));
> +	return RSA_NO_ERR;
> +}

> +/*
> + * Set the value of an mpi given its hex (absolute) value. The optional
> + * leading zeroes will be taken into account, so that the mpi created will
> + * not be canonicalized. The mpi passed in will be re-allocated (and relocated)
> + * if needeed
> + *
> + * Returns 0 on success or a negative value indicating error
> + *
> + * @n:	 pointer pointer to the allocated mpi
> + * @str:  hex data
> + * @size: sizeof(str)
> + */
> +static _err rsa_mpi_set(mpi ** n, _u8 * str, _u32 size)
> +{
> +	_i32 s, i, j;
> +	_u32 * buf;
> +	_err retval;
> +
> +	if(!size) {
> +		rsa_debug("%s: invalid initialization string\n", __FUNCTION__);
> +		return RSA_ERR_INVARG;
> +	}
> +
> +	/* Size of the new mpi value (in limbs) */
> +	s = (size / 4) + ((size % 4)? 1: 0);

Use canonical form.

> +	retval = rsa_mpi_resize(n, s, false);
> +	if(retval < 0)
> +		return retval;
> +
> +	/* Copy the data */
> +	buf = (*n)->data;
> +	for(i = size - 1, j = 0; i >= 0; i--, j++)
> +		buf[j / 4] |= ((_u32)str[i] << ((j % 4) * 8));
> +	return RSA_NO_ERR;
> +}
> +
> +/*
> + * Mpi to mpi copy
> + *
> + * Returns 0 on success or a negative value indicating error
> + *
> + * @dest: destination mpi
> + * @src:  source mpi
> + */
> +static inline _err rsa_mpi_copy(mpi **	dest, mpi * src)
> +{
> +	_i32 i, s;
> +	_u32 * destbuf, * srcbuf;

style:  *identifier  (in many places)

> +	_err retval;
> +
> +	retval = rsa_mpi_resize(dest, src->size, false);
> +	if(retval < 0)
> +		return retval;
> +
> +	(*dest)->sign = src->sign;
> +	destbuf = (*dest)->data;
> +	srcbuf = src->data;
> +	for(i = 0, s = src->size; i < s; i++)
> +		destbuf[i] = srcbuf[i];
> +	return RSA_NO_ERR;
> +}

> +/*
> + * Count leading zeroes
> + *
> + * Returns the number of leading zero bits
> + *
> + * @n: the mpi
> + */
> +static _u64 rsa_mpi_clz( mpi * n)

no space between ( and mpi

> +{
> +	_u64 retval = 0;
> +	_i32 i;
> +	_u32 limb;
> +
> +	for(i = n->size - 1; i >= 0; i--) {
> +		limb = n->data[i];
> +
> +		if(!limb) {
> +			retval += 32;
> +			continue;
> +		}
> +
> +		while(!(limb & 0x80000000)) {
> +			retval++;
> +			limb = limb << 1;
> +		}
> +
> +		break;
> +	}
> +
> +	return retval;
> +}

> +/*
> + * Shift a number both directions

I think that's "either direction".

> + *
> + * Returns 0 on success or a negative value indicating error
> + *
> + * @n: 	  pointer pointer to the allocated mpi
> + * @bits: shift to the right if positive, otherwise shift to the left
> + */
> +static _err rsa_mpi_shift(mpi ** n, _i64 bits)
> +{
> +	_i32 i, distance, size, lz;
> +	_u32 * buf;
> +	mpi * handle;
> +	_err retval;
> +
> +	handle = *n;
> +	if(!bits || rsa_mpi_iszero(handle))
> +		return RSA_NO_ERR;
> +
> +	/* Shifting to the right, no resize needed */
> +	if(bits > 0) {
> +		/* Drop off one limb for each 32 bit shift */
> +		distance = bits / 32;
> +		size = handle->size;
> +		buf = handle->data;
> +		for(i = 0; i < size; i++)
> +			buf[i] = (i + distance >= size)? 0x00: buf[i + distance];
> +
> +		/* Shift the remaining 'bits' mod 32 */
> +		bits = bits % 32;
> +		if(bits) {
> +			size -= distance;
> +			distance = 32 - bits;
> +			for(i = 0; i < size; i++) {
> +				buf[i] = buf[i] >> bits;
> +				if(i < size - 1)
> +					buf[i] |=  buf[i + 1] << distance;
> +			}
> +		}
> +
> +		rsa_mpi_canonicalize(handle);
> +		return RSA_NO_ERR;
> +	}
> +
> +	bits = -bits;
> +	lz = rsa_mpi_clz(handle) + (handle->limbs - handle->size) * 32;
> +
> +	/* Shifting to the left
> +	 * Reallocation is needed when the leading zeroes are less than the shift
> +	 * distance
> +	 */
> +	if(lz < bits) {
> +		/* Compute the size of the reallocation */
> +		size = bits - lz;
> +		size = (size / 32) + (size % 32 != 0);
> +		retval = rsa_mpi_resize(n, handle->limbs + size, true);
> +		if(retval < 0)
> +			return retval;
> +		handle = *n;
> +	}
> +	else {
> +		size = bits - rsa_mpi_clz(handle);
> +		handle->size += ((size / 32) + (size % 32 != 0));
> +	}
> +
> +	buf = handle->data;
> +	distance = bits / 32;
> +	/* Shift data 1 byte to the left for each 32 bit shift */
> +	if(distance) {
> +		/* Shift bytes */
> +		for(i = handle->size - distance - 1; i >= 0; i--)
> +			buf[i + distance] = buf[i];
> +		/* Zero the shifted in bytes */
> +		for(i = 0; i < distance; i++)
> +			buf[i] = 0;
> +	}
> +
> +	/* Shift the remaining 'bits' mod 32 */
> +	bits = bits % 32;
> +	distance = 32 - bits;
> +	if(bits)
> +		for(i = handle->size - 1; i >= 0; i--) {
> +			buf[i] = buf[i] << bits;
> +			if(i > 0)
> +				buf[i] |= (buf[i - 1] >> distance);
> +		}
> +
> +	return RSA_NO_ERR;
> +}
> +
> +/*
> + * Multiply two mpis
> + *
> + * Returns 0 on success or a negative value indicating error
> + *
> + * @res: pointer pointer to the result
> + * @a:	 left operand
> + * @b:   right operand
> + */
> +static _err rsa_mpi_multiply(mpi ** res, mpi *	a, mpi * b)

s/<tab>/<space>/  (in several places)

> +{
> +	_i32 i, j, size, asize, bsize;
> +	_u32 * buf, * abuf, * bbuf;
> +	_u64 tmp;
> +	mpi * handle;
> +	_err retval;
> +
> +	asize = a->size;
> +	bsize = b->size;
> +	size = asize + bsize;
> +	retval = rsa_mpi_resize(res, size, false);
> +	if(retval < 0)
> +		return retval;
> +
> +	handle = *res;
> +	handle->sign = a->sign ^ b->sign;
> +
> +	buf = handle->data;
> +	abuf = a->data;
> +	bbuf = b->data;
> +	/* Make the multiplication, using the standard algorithm */
> +	for(i = 0; i < bsize; i++) {
> +		tmp = 0;
> +		for(j = 0; j < asize; j++)
> +			buf[i + j] = tmp = buf[i + j] + (abuf[j] * (_u64)bbuf[i]) + (tmp >> 32);
> +		buf[i + asize] = tmp >> 32;
> +	}
> +
> +	rsa_mpi_canonicalize(handle);
> +	return RSA_NO_ERR;
> +}

> +/*
> + * Compute the remainder of a/b (aka a mod b)
> + *
> + * Returns 0 on success or a negative value indicating error
> + *
> + * @res: pointer pointer to the result
> + * @a:	 left operand
> + * @b:   right operand
> + */
> +static _err rsa_mpi_remainder(mpi ** res, mpi * a, mpi * b)
> +{
> +	_i32 i, k;
> +	_err retval;
> +
> +	/* Because b operand will be shifted we need to have a copy of it in
> +	 * order not to mess with the prototype b
> +	 */
> +	if((retval = rsa_mpi_copy(&aux[0], a)) < 0 ||
> +	   (retval = rsa_mpi_copy(&aux[1], b)) < 0)
> +		return retval;
> +
> +	k = (aux[0]->size - aux[1]->size) * 32;
> +	k += (rsa_mpi_clz(aux[1]) - rsa_mpi_clz(aux[0]));
> +
> +	/* Align the divisor to the divident */
                                    dividend

> +	retval = rsa_mpi_shift(&aux[1], -k);
> +	if(retval < 0)
> +		return retval;
> +
> +	for(i = 0; i <= k; i++) {
> +		retval = rsa_mpi_subtract(res, aux[0], aux[1]);
> +		if(retval < 0)
> +			return retval;
> +
> +		if(!(*res)->sign) {
> +			retval = rsa_mpi_copy(&aux[0], (*res));
> +			if(retval < 0)
> +				return retval;
> +		}
> +
> +		retval = rsa_mpi_shift(&aux[1], 1);
> +		if(retval < 0)
> +			return retval;
> +	}
> +
> +	rsa_mpi_canonicalize(aux[0]);
> +	return rsa_mpi_copy(res, aux[0]);
> +}

> diff -uprN -X linux-2.6.20.1-vanilla/Documentation/dontdiff linux-2.6.20.1/crypto/rsa.h linux-2.6.20.1-vanilla/crypto/rsa.h
> --- linux-2.6.20.1/crypto/rsa.h	1970-01-01 02:00:00.000000000 +0200
> +++ linux-2.6.20.1-vanilla/crypto/rsa.h	2007-03-19 16:29:34.000000000 +0200
> @@ -0,0 +1,86 @@
> +#ifndef _KM_RSA_H_
> +#define _KM_RSA_H_
> +
> +#include <linux/module.h>
> +#include <linux/errno.h>
> +#include <config/rsa/auxcount.h>
> +#include <config/rsa/auxsize.h>

Those 2 config files shouldn't be needed.  include/linux/autoconf.h
is automatically included in all source files/builds.

> +
> +#define RSA_AUX_COUNT 		CONFIG_RSA_AUXCOUNT
> +#define RSA_AUX_SIZE 		CONFIG_RSA_AUXSIZE
> +#define RSA_MAX_U32		0xFFFFFFFF
> +#define RSA_RADIX_BITS		0x20
> +#define RSA_LOGLEVEL		KERN_ALERT
> +#define RSA_NO_ERR		0
> +#define RSA_ERR_INVARG		-1
> +#define RSA_ERR_NOMEM		-2
> +
> +#define true			0x01
> +#define false			0x00

Aren't these already available in C?

> +
> +#ifdef RSA_DEBUG
> +	#define rsa_debug(fmt, args...) 			   \
> +	{ 							   \
> +		if(printk_ratelimit()) 				   \
> +			printk(RSA_LOGLEVEL "rsa: " fmt, ## args); \
> +	}
> +#else
> +	#define rsa_debug(fmt, args...)
> +#endif
> +
> +#define rsa_echo(fmt, args...) printk(RSA_LOGLEVEL "rsa: " fmt, ## args)
> +
> +#if RSA_AUX_COUNT < 8
> +	#error "Rsa module needs at least 8 auxilliary mpis"
> +#endif
> +
> +typedef signed char 		_i8;
> +typedef signed short		_i16;
> +typedef signed int 		_i32;
> +typedef signed long long	_i64;
> +typedef unsigned char 		_u8;
> +typedef unsigned short		_u16;
> +typedef unsigned int 		_u32;
> +typedef unsigned long long	_u64;
> +typedef signed int		_err;
> +
> +/* Multi-precision integer */
> +typedef struct mpi {
> +	_u32	* data;	/* _u32 array holding the number absolute value */
> +	_u8	sign;	/* 1 for negative, 0 for positive */
> +	_i32	size;	/* Significant number limbs */
> +	_i32	limbs;	/* Allocated limbs (sizeof data) */
> +} mpi;
> +
> +/* Module loading/unloading functions */
> +static _err __init	rsa_load(void);
> +static void __exit	rsa_unload(void);
> +
> +/* Mpi utility functions */
> +static _err		rsa_mpi_alloc(mpi **, _i32);
> +static void 		rsa_mpi_free(mpi *);
> +static _err 		rsa_mpi_init(mpi **, _u8 *, _u32, _u32);
> +static _err 		rsa_mpi_resize(mpi **, _i32, _u8);
> +static _err 		rsa_mpi_set(mpi **, _u8 *, _u32);
> +static inline _err 	rsa_mpi_copy(mpi **, mpi *);
> +static void 		rsa_mpi_print(mpi *, _u8);
> +
> +/* Mpi comparing and misc functions */
> +static inline _u8 	rsa_mpi_iszero(mpi *);
> +static _i8 		rsa_mpi_compare(mpi *, mpi *);
> +static _u64	 	rsa_mpi_clz(mpi *);
> +static inline void 	rsa_mpi_complement(mpi *, _u8);
> +static inline void 	rsa_mpi_canonicalize(mpi *);
> +
> +/* Mpi arithmetic functions */
> +static _err		rsa_mpi_shift(mpi **, _i64);
> +static _err 		rsa_mpi_multiply(mpi **, mpi *, mpi *);
> +static _err 		rsa_mpi_subtract(mpi **, mpi *, mpi *);
> +static _err 		rsa_mpi_remainder(mpi **, mpi *, mpi *);
> +
> +/* Rsa functions */
> +static _u32		rsa_modinv(mpi *);
> +static _err 		rsa_monpro(mpi **, mpi *, mpi *, mpi *);
> +static _err 		rsa_modexp(mpi **, mpi *, mpi *, mpi *);
> +
> +#endif /* _KM_RSA_H_ */


---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/