On Wed, 21 Mar 2007 17:13:31 +0200 (EET) Tasos Parisinos wrote: > This patch changes the crypto/Kconfig crypto/Makefile and adds > crypto/rsa.c. These files add module named rsa.o (rsa.ko) built-in or as > a kernel module and offer an API to do fast modular exponentiation > and other multi-precision arithmetics. > Signed-off-by: Tasos Parisinos <[EMAIL PROTECTED]> > > ---
Hi, Lots of good progress here, but still a few comments below. Needs to apply to current mainline. > diff -uprN -X linux-2.6.20.3-vanilla/Documentation/dontdiff \ > linux-2.6.20.3/crypto/rsa.c linux-2.6.20.3-vanilla/crypto/rsa.c > --- linux-2.6.20.3/crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200 > +++ linux-2.6.20.3-vanilla/crypto/rsa.c 2007-03-21 15:15:04.000000000 > +0200 > @@ -0,0 +1,809 @@ > +/* > + * Cryptographic API > + * > + * RSA cipher algorithm implementation > + * > + * Copyright (c) Tasos Parisinos <[EMAIL PROTECTED]> > + * > + * This program is free software; you can redistribute it and/or modify > + * it under the terms of the GNU General Public License as published by > + * the Free Software Foundation; either version 2 of the License, or > + * (at your option) any later version > + * > + */ > + > +#include <linux/module.h> > +#include <linux/errno.h> > +#include <linux/time.h> > + > +#if CONFIG_RSA_AUXCOUNT < 8 > + #error "Rsa module needs at least 8 auxilliary mpis" > +#endif > + > +#define RADIX_BITS 0x20 > +#define UINT32_T_MAX 0xFFFFFFFF > + > +/* Multi-precision integer */ > +typedef struct mpi { > + u32 *data; /* u32 array holding the number absolute value */ > + u8 sign; /* 1 for negative, 0 for positive */ > + int size; /* Significant number limbs */ > + int limbs; /* Allocated limbs (sizeof data) */ > +} mpi; > + > +static mpi *aux[CONFIG_RSA_AUXCOUNT]; > +static u32 modinv; > + > +/* > + * mpi_alloc - allocate an mpi > + * @n: pointer pointer to the allocated mpi > + * @limbs: number of allocated limbs (32 bit digits) > + * > + * The allocated mpi will be zeroed and not canonicalized > + */ Most (probably all) of these functions should also be "static" unless they are meant for use outside of this module. Which leads to the question: which functions are meant for external/exported use? And it would be really Good if those function headers were documented in kernel-doc notation (not much of a change from what you already have here; see Documentation/kernel-doc-nano-HOWTO.txt). > +int mpi_alloc(mpi **n, int limbs) > +{ > + mpi *handle; > + > + *n = NULL; > + if (!limbs) > + return -EINVAL; > + > + /* Allocate space for the mpi */ > + handle = *n = kmalloc(sizeof(mpi), GFP_KERNEL); > + if (!handle) > + return -ENOMEM; > + > + handle->data = kzalloc(limbs * sizeof(u32), GFP_KERNEL); > + if (!handle->data) { > + kfree(handle); > + *n = NULL; > + return -ENOMEM; > + } > + > + handle->sign = 0; > + handle->size = handle->limbs = limbs; > + return 0; > +} > + > +void mpi_free(mpi *n) > +{ > + if (!n) > + return; > + kfree(n->data); > + kfree(n); > +} We usually even designate inlines as static... > +inline int mpi_copy(mpi **dest, mpi *src) > +{ > + int i, s, retval; > + u32 *destbuf, *srcbuf; > + > + retval = 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 0; > +} > +int mpi_multiply(mpi **res, mpi *a, mpi *b) > +{ > + int i, j, size, asize, bsize, retval; > + u32 *buf, *abuf, *bbuf; > + u64 tmp; > + mpi *handle; > + > + asize = a->size; > + bsize = b->size; > + size = asize + bsize; > + retval = 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); Break that line to < 80 columns, please. > + buf[i + asize] = tmp >> 32; > + } > + > + mpi_canonicalize(handle); > + return 0; > +} > + > +/* > + * rsa_monpro - compute the montgomery product (res = a * b mod n) > + * @res: pointer pointer to the result > + * @a: left operand > + * @b: right operand > + * @n: divisor > + */ > +int rsa_monpro(mpi **res, mpi *a, mpi *b, mpi *n) > +{ > + int nsize, i, j, k, retval; > + u32 *buf, *nbuf, *tmp, m; > + u64 product = 0; > + > + nsize = n->size; > + k = nsize << 1; > + retval = mpi_multiply(&aux[2], a, b); > + if (retval < 0) > + return retval; > + > + retval = mpi_resize(&aux[2], max(aux[2]->size, k), true); > + if (retval < 0) > + return retval; > + > + tmp = buf = aux[2]->data; > + nbuf = n->data; > + > + for (i = 0; i < nsize; i++, tmp++) { > + m = buf[i] * modinv; > + product = 0; > + > + for (j = 0; j < nsize; j++) > + tmp[j] = product = tmp[j] + (m * (u64)nbuf[j]) + > (product >> 32); Line too long. > + > + for (j = nsize + i; j < k; j++) > + buf[j] = product = buf[j] + (product >> 32); > + } > + > + retval = mpi_resize(&aux[2], aux[2]->size + 1, true); > + if (retval < 0) > + return retval; > + > + aux[2]->data[aux[2]->size - 1] = product >> 32; > + retval = mpi_shift(&aux[2], nsize * 32); > + if (retval < 0) > + return retval; > + > + if (mpi_compare(aux[2], n) >= 0) { > + if ((retval = mpi_subtract(&aux[3], aux[2], n)) < 0 || > + (retval = mpi_copy(res, aux[3])) < 0) > + return retval; > + } > + else if ((retval = mpi_copy(res, aux[2])) < 0) > + return retval; > + return 0; > +} --- ~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 [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/