crypto: RSA algorithm patch (kernel version 2.6.21-rc5-git6)
Subsystems (2)
PATCH 1/1 crypto: RSA algorithm patch (kernel version 2.6.21-rc5-git6)
From: Tasos Parisinos <[email protected]>
This patch adds module rsa.ko in the kernel (built-in or as a kernel module) and offers an API to do fast modular exponentiation, using the Montgomery algorithm, thus the exponentiation is not generic but can be used only when the modulus is odd, such as RSA public/private key pairs. This module is the
computational core (using multiple precision integer arithmetics) and does not
provide any means to do key management, implement padding schemas e.t.c. so the
calling code should implement all those as needed.
---
This module exports some symbols, through its header file include/crypto/rsa.h and does not use the glue code of include/crypto.h. This decision was taken because this glue code is not really suitable for asymmetric cryptography in my
opinion. First of all RSA is not a block cipher but a stream cipher. It does not
only have a key but also an exponent that are two different entities. And the most
important is that the key size can be of any length. So it is not practical -yet- to register the algorithm with the crypto api using a struct such as crypto_alg. So another module can include the file include/crypto/rsa.h and call its interface functions to create the operands for the modular exponentiation, execute the exponentiation and use the results. All these functions and structures are well documented kernel-doc style. Also in this way the calling in-kernel code can implement key management, padding schemas, hashing e.t.c as needed. The main purpose
behind the creation of this module was to create the cryptographic infrastructure
to develop an in-kernel system of signed modules.
diff -uprN -X linux.orig/Documentation/dontdiff \
linux.orig/crypto/Kconfig linux/crypto/Kconfig
crypto/Kconfig 2007-03-30 13:27:33.000000000 +0300 renamed from crypto/Kconfig 2007-03-26 01:56:23.000000000 +0300 +0 -0
@@ -440,6 +440,31 @@ config CRYPTO_CAMELLIA
See also:
<https://info.isl.ntt.co.jp/crypt/eng/camellia/index_s.html>
+config CRYPTO_RSA
+ tristate "RSA asymmetric cipher algorithm"
+ help
+ RSA asymmetric cipher algorithm.
+
+ This module uses the montgomery algorithm to compute fast modular + exponentiation. All operands of the modular exponentiation can be + of any bit length, thus you can use any public and/or private key + lengths.
+
+ If it is selected it will add approximately 8K to the kernel size.
+ Select M to build this as a module. The module will be called rsa.
+
+config RSA_AUX_OPERAND_SIZE
+ int "Size of the preallocated auxilliary operands"
+ default "128"
+ depends on CRYPTO_RSA
+ help
+ The rsa module needs some preallocated space to avoid computation-time + allocations. The 'rsa_op' is the struct used by the rsa module to hold + a multi-precision integer operand. This struct maps such an integer on + multiple 32bit limbs. Here you select the size (in 32bit limbs) of the + preallocated auxilliary operands. This size should be close to the key + sizes that are usually used.
+
config CRYPTO_TEST
tristate "Testing module"
depends on m
diff -uprN -X linux.orig/Documentation/dontdiff \
linux.orig/crypto/Makefile linux/crypto/Makefile
crypto/Makefile 2007-03-30 13:27:33.000000000 +0300 renamed from crypto/Makefile 2007-03-26 01:56:23.000000000 +0300 +0 -0
@@ -46,5 +46,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.orig/Documentation/dontdiff \linux.orig/crypto/rsa.c linux/crypto/rsa.c
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 renamed from crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200 +766 -0
766 lines not on this page · raw message
diff -uprN -X linux.orig/Documentation/dontdiff \linux.orig/include/crypto/rsa.h linux/include/crypto/rsa.h
include/crypto/rsa.h 2007-03-30 14:20:45.000000000 +0300 renamed from include/crypto/rsa.h 1970-01-01 02:00:00.000000000 +0200 +25 -0
@@ -0,0 +1,26 @@ +#ifndef _CRYPTO_RSA_H +#define _CRYPTO_RSA_H + +/* + * struct rsa_op: multi-precision integer operand + * @data: array that holds the number absolute value + * @sign: 1 for negative, 0 for positive + * @size: significant number limbs + * @limbs: allocated limbs (sizeof data) + */ +typedef struct rsa_op { + u32 *data; + int sign; + int size; + int limbs; +} rsa_op; + +int rsa_op_alloc(rsa_op **, int); +void rsa_op_free(rsa_op *); +int rsa_op_init(rsa_op **, u8 *, u32, u32); +int rsa_op_set(rsa_op **, u8 *, u32); +int rsa_op_copy(rsa_op **, rsa_op *); +void rsa_op_print(rsa_op *, bool); +int rsa_cipher(rsa_op **, rsa_op *, rsa_op *, rsa_op *); + +#endif
On Fri, 30 Mar 2007 16:26:36 +0300 Tasos Parisinos wrote:
Hi,
Just a few whitespace nits that you can fix with any other comments that you get...
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 line 91
Quoted 8 lines
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 renamed from crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200 +8
-0+static char rsa_op_compare(rsa_op *l, rsa_op *r) +{ + int i; + u32 *lbuf, *rbuf; + + /* Compare the two operands based on sign */ + if (l->sign != r->sign) + return (l->sign)? -1: 1;
-1 : 1;
Quoted 25 lines
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 renamed from crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200 +25
-0+ /* Compare the two operands based on their size */ + if (l->size > r->size && rsa_op_clz(l) < (l->size - r->size) * 32) + return 1; + else if (r->size > l->size && rsa_op_clz(r) < (r->size - l->size) * 32) + return -1; + + /* Compare the two operands based on their hex values */ + lbuf = l->data; + rbuf = r->data; + for (i = min(l->size, r->size) - 1; i >= 0; i--) + if (lbuf[i] > rbuf[i]) + return 1; + else if (lbuf[i] < rbuf[i]) + return -1; + return 0; +} + +static int rsa_op_shift(rsa_op **n, int bits) +{ + int i, distance, size, lz, retval; + u32 *buf; + rsa_op *handle; + + if (!bits) + return 0;
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 line 157
Quoted 10 lines
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 renamed from crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200 +10
-0+ handle = *n; + + /* 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];
0 :
Quoted 105 lines
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 renamed from crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200 +105
-0+ + /* 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_op_canonicalize(handle); + return 0; + } + + bits = -bits; + lz = rsa_op_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 = rsa_op_resize(n, handle->limbs + size); + if (retval < 0) + return retval; + handle = *n; + } + else + handle->size += ((bits - rsa_op_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 */ + memset(handle->data, 0, distance * sizeof(u32)); + } + + /* 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; +} + + + + + + + +/** +/** + * rsa_op_print - print the value of an rsa_op + * @n: pointer to the rsa_op to be printed + * @how: true to print canonicalized + */ +void rsa_op_print(rsa_op *n, bool how) +{ + int i, j; + u32 limb; + u8 byte; + bool started = false; + + printk("Operand @ 0x%x, %d limbs in size, %d limbs allocated, value = ", + (u32)n, n->size, n->limbs); + + /* 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 canonicalization 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 canonicalization + * is selected + */
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300
Quoted 10 lines
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 renamed from crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200 +10
-0+ if (!byte && !started && how) + continue; + + started = true; + byte += (byte <= 0x09)? '0': 'a' - 0x0A; + printk("%c", byte); + } + } + + if(!started)
space after "if"
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 line 628
Quoted 2 lines
crypto/rsa.c 2007-03-30 14:20:07.000000000 +0300 renamed from crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200 +2
-0+ printk("0"); + printk("\n");
and then there's the introduction of a new typedef in a world where we srongly try to limit new typedefs...
+typedef struct rsa_op {
+ u32 *data;
+ int sign;
+ int size;
+ int limbs;
+} rsa_op;
---
~Randy