Messages in this thread Patch in this message | | | Date | Wed, 21 Mar 2007 17:13:31 +0200 (EET) | From | Tasos Parisinos <> | Subject | [PATCH 1/1][NEW] crypto API: rsa algorithm module patch (kernel version 2.6.20.3) |
| |
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 <t.parisinos@sciensis.com>
---
diff -uprN -X linux-2.6.20.3-vanilla/Documentation/dontdiff \ linux-2.6.20.3/crypto/Kconfig linux-2.6.20.3-vanilla/crypto/Kconfig --- linux-2.6.20.3/crypto/Kconfig 2007-03-13 20:27:08.000000000 +0200 +++ linux-2.6.20.3-vanilla/crypto/Kconfig 2007-03-21 15:15:04.000000000 +0200 @@ -458,6 +458,41 @@ config CRYPTO_CRC32C See Castagnoli93. This implementation uses lib/libcrc32c. Module will be crc32c.
+config CRYPTO_RSA + tristate "RSA cipher algorithm" + 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 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 allocated at module load time. + +config RSA_AUXSIZE + int "Initial preallocated mpi limb size" + default "128" + 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. This + struct maps a number on multiple 32 bit limbs (it is actually + a 32 bit array). Here you select the default size (in limbs) + of the preallocated mpis. + config CRYPTO_TEST tristate "Testing module" depends on m diff -uprN -X linux-2.6.20.3-vanilla/Documentation/dontdiff \ linux-2.6.20.3/crypto/Makefile linux-2.6.20.3-vanilla/crypto/Makefile --- linux-2.6.20.3/crypto/Makefile 2007-03-13 20:27:08.000000000 +0200 +++ linux-2.6.20.3-vanilla/crypto/Makefile 2007-03-21 15:15:04.000000000 +0200 @@ -43,5 +43,6 @@ obj-$(CONFIG_CRYPTO_ANUBIS) += anubis.o obj-$(CONFIG_CRYPTO_DEFLATE) += deflate.o obj-$(CONFIG_CRYPTO_MICHAEL_MIC) += michael_mic.o obj-$(CONFIG_CRYPTO_CRC32C) += crc32c.o +obj-$(CONFIG_CRYPTO_RSA) += rsa.o
obj-$(CONFIG_CRYPTO_TEST) += tcrypt.o 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 <t.parisinos@sciensis.com> + * + * 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 + */ +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); +} + +/* + * mpi_init - initialize an mpi given its hex (absolute) value + * @n: pointer pointer to the allocated mpi + * @str: hex data + * @size: sizeof(str) + * @xtra: how many extra limbs to preallocate to avoid reallocations + * + * The optional leading zeroes will be taken into account, so that the + * mpi created will not be canonicalized + */ +int mpi_init(mpi **n, u8 *str, u32 size, u32 xtra) +{ + int i, j, s, retval; + u32 *buf; + + *n = NULL; + if (!size && !xtra) + return -EINVAL; + + /* Allocate space for the mpi and its data */ + s = (size + 3) / 4; + retval = 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 0; +} + +/* + * mpi-resize - resize an mpi, doing all the needed re-allocations + * @n: pointer pointer to the allocated mpi + * @size: the new size + * @hold: true to keep the current data + */ +int mpi_resize(mpi **n, int size, u8 hold) +{ + int retval; + mpi *handle = *n; + + /* If there is an mpi passed in, that has the available limbs */ + if (handle && handle->limbs >= size) { + int i, s; + u32 *buf; + + s = handle->size; + buf = handle->data; + + /* If the original data are not needed they are zeroed */ + if (!hold) { + for (i = 0; i < s; i++) + buf[i] = 0; + handle->sign = 0; + } + /* zero the xtra limbs */ + else if (size < handle->size) + for (i = size; i < s; i++) + buf[i] = 0; + + handle->size = size; + } + /* If there is an mpi passed in, that doesn't have the available + * limbs already allocated + */ + else if (handle) { + mpi *tmp = NULL; + + retval = mpi_alloc(&tmp, size); + if (retval < 0) + return retval; + + /* Copy the original data if they are needed */ + if (hold) { + memcpy(tmp->data, handle->data, + handle->size * sizeof(u32)); + tmp->sign = handle->sign; + } + + mpi_free(*n); + *n = tmp; + return retval; + } + /* If there is no allocated mpi passed in, allocate one */ + else if (!handle) { + retval = mpi_alloc(n, size); + if (retval < 0) + return retval; + } + + return 0; +} + +/* + * mpi_set - set the value of an mpi given its hex (absolute) value + * @n: pointer pointer to the allocated mpi + * @str: hex data + * @size: sizeof(str) + * + * 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 + */ +static int mpi_set(mpi **n, u8 *str, u32 size) +{ + int s, i, j, retval; + u32 *buf; + + if (!size) + return -EINVAL; + + /* Size of the new mpi value (in limbs) */ + s = (size + 3) / 4; + retval = 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 0; +} + +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; +} + +inline u8 mpi_iszero(mpi *n) +{ + int i, s; + u32 *buf; + + s = n->size; + buf = n->data; + for (i = 0; i < s; i++) + if (buf[i]) + return false; + return true; +} + +/* + * mpi_print - print the value of an mpi + * @n: pointer to the mpi + * @how: true to print canonicalized + */ +void mpi_print(mpi *n, u8 how) +{ + int i, j; + u32 limb; + u8 byte, started = false; + + printk("Mpi at 0x%x, %d limbs in size, %d limbs allocated, value = ", + (u32)n, n->size, n->limbs); + + /* If the mpi is merely zero */ + if (mpi_iszero(n) && how) { + printk("0\n"); + return; + } + + /* Print the sign */ + printk("%s", (n->sign)? "-": " "); + + /* Print the hex value */ + for (i = n->size - 1; i >= 0; i--) { + limb = n->data[i]; + + /* Ignore leading zero limbs if canonicalized printing + * is selected + */ + if (!limb && !started && how) + continue; + + /* Print each limb as though each of its nibbles was a + * character from the set '0' to '9' and 'a' to 'f' + */ + for (j = 28; j >= 0; j -= 4) { + byte = (u8)((limb >> j) & 0x0F); + + /* Ignore leading zero bytes if canonicalized printing + * is selected + */ + if (!byte && !started && how) + continue; + + started = true; + byte += (byte <= 0x09)? '0': 'a' - 0x0A; + printk("%c", byte); + } + } + + printk("\n"); +} + +/* + * mpi_clz - count leading zeroes + * @n: the mpi + */ +u32 mpi_clz(mpi *n) +{ + int i; + u32 limb, retval = 0; + + 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; +} + +/* + * mpi_compare - compare two mpis + * @a: the left operand + * @b: the right operand + * + * Returns -1 if a < b, 1 if b < a, 0 otherwise + */ +char mpi_compare(mpi *a, mpi *b) +{ + int i, j; + u32 *abuf, *bbuf; + + /* Compare the two mpis based on sign */ + if (a->sign != b->sign) + return (a->sign)? -1: 1; + + /* Compare the two mpis based on their size */ + if (a->size > b->size && mpi_clz(a) < (a->size - b->size) * 32) + return 1; + else if (a->size > b->size) + j = b->size; + else if (b->size > a->size && mpi_clz(b) < (b->size - a->size) * 32) + return -1; + else + j = a->size; + + /* Compare the two mpis based on their hex values */ + abuf = a->data; + bbuf = b->data; + for (i = j - 1; i >= 0; i--) + if (abuf[i] > bbuf[i]) + return 1; + else if (abuf[i] < bbuf[i]) + return -1; + + return 0; +} + +/* + * mpi_complement - complement an mpi + * @n: the mpi + * @which: true to compute 2's complement + */ +inline void mpi_complement(mpi *n, u8 which) +{ + int i, s; + u32 *buf; + + s = n->size; + buf = n->data; + for (i = 0; i < s; i++) + buf[i] ^= UINT32_T_MAX; + if (!which) + return; + + /* Add 1 using the addition carry */ + for (i = 0; i < s; i++) { + buf[i] += 1; + if (buf[i]) + break; + } +} + +inline void mpi_canonicalize(mpi *n) +{ + int i; + u32 *buf = n->data; + + for (i = n->size - 1; i >= 0; i--) + if (!buf[i] && n->size > 1) + n->size--; + else + break; +} + +/* + * mpi_shift - shift a number either directions + * @n: pointer pointer to the allocated mpi + * @bits: shift to the right if positive, otherwise shift to the left + */ +int mpi_shift(mpi **n, int bits) +{ + int i, distance, size, lz, retval; + u32 *buf; + mpi *handle; + + handle = *n; + if (!bits || mpi_iszero(handle)) + return 0; + + /* 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)? 0: 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; + } + } + + mpi_canonicalize(handle); + return 0; + } + + bits = -bits; + lz = 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 + 31) / 32; + retval = mpi_resize(n, handle->limbs + size, true); + if (retval < 0) + return retval; + handle = *n; + } + else + handle->size += ((bits - mpi_clz(handle) + 31) / 32); + + 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 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); + buf[i + asize] = tmp >> 32; + } + + mpi_canonicalize(handle); + return 0; +} + +int mpi_subtract(mpi **res, mpi *a, mpi *b) +{ + int i, size, retval; + u32 *buf, *abuf, *bbuf; + mpi *handle; + + size = max(a->size, b->size) + (a->sign != b->sign); + if ((retval = mpi_resize(res, size, true)) < 0 || + (retval = mpi_resize(&a, size, true)) < 0 || + (retval = mpi_resize(&b, size, true)) < 0) + return retval; + + handle = *res; + buf = handle->data; + abuf = a->data; + bbuf = b->data; + + /* If the operands are both negative or positive perform subtraction */ + if (a->sign == b->sign) { + u8 borrow = false; + u32 limb; + + for (i = 0; i < size; i++) { + limb = borrow + bbuf[i]; + buf[i] = abuf[i] - limb; + borrow = (abuf[i] < limb); + } + + handle->sign = (borrow)? !b->sign: b->sign; + if (borrow) + mpi_complement(handle, true); + } + /* If the operands are not signed in the same way perform addition */ + else { + u8 carry = false; + u64 sum; + + for (i = 0; i < size; i++) { + buf[i] = sum = abuf[i] + bbuf[i] + carry; + carry = (sum > UINT32_T_MAX); + } + + handle->sign = a->sign; + } + + mpi_canonicalize(handle); + mpi_canonicalize(a); + mpi_canonicalize(b); + return 0; +} + +int mpi_remainder(mpi **res, mpi *a, mpi *b) +{ + int i, k, retval; + + /* Because b operand will be shifted we need to have a copy of it + * in order not to mess with the prototype + */ + if ((retval = mpi_copy(&aux[0], a)) < 0 || + (retval = mpi_copy(&aux[1], b)) < 0) + return retval; + + k = (aux[0]->size - aux[1]->size) * 32; + k += (mpi_clz(aux[1]) - mpi_clz(aux[0])); + + /* Align the divisor to the dividend */ + retval = mpi_shift(&aux[1], -k); + if (retval < 0) + return retval; + + for (i = 0; i <= k; i++) { + retval = mpi_subtract(res, aux[0], aux[1]); + if (retval < 0) + return retval; + + if (!(*res)->sign) { + retval = mpi_copy(&aux[0], (*res)); + if (retval < 0) + return retval; + } + + retval = mpi_shift(&aux[1], 1); + if (retval < 0) + return retval; + } + + mpi_canonicalize(aux[0]); + return mpi_copy(res, aux[0]); +} + +/* + * rsa_modinv - compute the first 32 bits of the modular inverse of a number + * @n: the mpi + */ +u32 rsa_modinv(mpi *n) +{ + u32 i, x, y, tmp, pow1; + + pow1 = y = 1; + x = n->data[0]; + + for (i = 2; i <= RADIX_BITS; i++) { + pow1 = pow1 << 1; + tmp = ((u64)x * y) & (UINT32_T_MAX >> (32 - i)); + if (pow1 < tmp) + y += pow1; + } + + y = (y ^ UINT32_T_MAX) + 1; + return y; +} + +/* + * 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); + + 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; +} + +/* + * rsa_modexp - computes the RSA of m, a.k.a res = m ^ e mod n + * @res: pointer pointer to the result + * @m: base + * @e: exponent + * @n: divisor + */ +int rsa_modexp(mpi **res, mpi *m, mpi *e, mpi *n) +{ + int i, j, retval; + u32 limb; + u8 started = false; + + if (m->size != n->size || mpi_compare(m, n) > 0) + return -EINVAL; + + modinv = rsa_modinv(n); + + /* Compute m * r mod n where r is 2 ^ k and n is the k-bit modulus. + * The resulting m' is stored in aux[4] + */ + retval = mpi_copy(&aux[5], m); + if (retval < 0) + return retval; + + retval = mpi_shift(&aux[5], -(n->size * 32)); + if (retval < 0) + return retval; + + retval = mpi_remainder(&aux[4], aux[5], n); + if (retval < 0) + return retval; + + /* Compute r mod n where r is 2 ^ k and n is the k-bit modulus. + * The resulting x' is stored in aux[7] + */ + retval = mpi_set(&aux[5], "\x01", 1); + if (retval < 0) + return retval; + + retval = mpi_shift(&aux[5], -(n->size * 32)); + if (retval < 0) + return retval; + + retval = mpi_remainder(&aux[7], aux[5], n); + if (retval < 0) + return retval; + + /* Canonicalize the exponent and compute the modular exponentiation. + * For each limb of the exponent perform left to right binary + * exponentiation + */ + mpi_canonicalize(e); + for (i = e->size - 1; i >= 0; i--) { + /* Take a limb of the exponent */ + limb = e->data[i]; + + /* For each of its bits */ + for (j = 0; j < 32; j++) { + /* While the exponent has non significant zeroes shift + * it to the left + */ + if (!(limb & 0x80000000) && !started) { + limb = limb << 1; + continue; + } + + started = true; + /* Compute x' * x' mod n */ + retval = rsa_monpro(&aux[5], aux[7], aux[7], n); + if (retval < 0) + return retval; + + if (limb & 0x80000000) { + /* Compute x' = m' * x' mod n */ + retval = rsa_monpro(&aux[7], aux[4], aux[5], n); + if (retval < 0) + return retval; + } + else if ((retval = mpi_copy(&aux[7], aux[5])) < 0) + return retval; + + limb = limb << 1; + } + } + + /* Compute res = x' mod n */ + retval = mpi_set(&aux[6], "\x01", 1); + if (retval < 0) + return retval; + return rsa_monpro(res, aux[7], aux[6], n); +} + +static int __init rsa_load(void) +{ + int retval = 0; + u32 i; + + /* Pre-allocate some auxilliary mpis */ + printk(KERN_DEBUG "Allocating %d bytes for auxilliary operands\n", + CONFIG_RSA_AUXSIZE * CONFIG_RSA_AUXCOUNT * sizeof(u32)); + + memset(&aux, 0, sizeof(aux)); + for (i = 0; i < CONFIG_RSA_AUXCOUNT; i++) { + retval = mpi_alloc(&aux[i], CONFIG_RSA_AUXSIZE); + if (retval < 0) + goto rollback; + } + + printk(KERN_DEBUG "RSA cipher algorithm module initialized\n"); + return 0; + +/* Free all allocated resources if any errors occur */ +rollback: + for (i = 0; i < CONFIG_RSA_AUXCOUNT; i++) + mpi_free(aux[i]); + return retval; +} + +static void __exit rsa_unload(void) +{ + u32 i; + + /* Free all the pre-allocated auxilliary mpis */ + for (i = 0; i < CONFIG_RSA_AUXCOUNT; i++) + mpi_free(aux[i]); + printk(KERN_DEBUG "RSA cipher algorithm module unloaded\n"); +} + +module_init(rsa_load); +module_exit(rsa_unload); + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Tasos Parisinos @ Sciensis Advanced Technology Systems"); +MODULE_DESCRIPTION("RSA cipher algorithm implementation"); - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |