From: Tasos Parisinos <[EMAIL PROTECTED]>

This patch changes the crypto/Kconfig and crypto/Makefile and adds crypto/rsa.c and crypto/rsa.h in the source tree. These files add module rsa.o (or rsa.ko) in the kernel (built-in or as a kernel module) and offer an API to do fast modular exponentiation. The modular exponentiation algorithm is in fact implementation of the Montgomery algorithm. The API can also be used to do some multi precision arithmetics as well (multiplication, addition, subtraction, remainder) and can serve as a basis for future multi-precision arithmetics implementations. The module is totally written in C, thus being portable but less efficient than any assembly implementation, but the code architecture is such that one could replace C code with assembly easily in the future. The module does not have a userland interface yet, so it can be only used by other in-kernel code. As mentioned in the subject this patch applies in kernel version 2.6.20.1.
Signed-off-by: Tasos Parisinos <[EMAIL PROTECTED]>

---

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:09:04.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 2K 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.
+
+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 + 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.1-vanilla/Documentation/dontdiff linux-2.6.20.1/crypto/Makefile linux-2.6.20.1-vanilla/crypto/Makefile
--- linux-2.6.20.1/crypto/Makefile    2007-02-20 08:34:32.000000000 +0200
+++ linux-2.6.20.1-vanilla/crypto/Makefile 2007-03-11 14:16:46.000000000 +0200
@@ -2,6 +2,11 @@
# Cryptographic API
#

+ifeq ($(CRYPTO_RSA_DEBUG),y)
+    EXTRA_CFLAGS += -DRSA_DEBUG
+endif
+EXTRA_CFLAGS += -DRSA_HAVE_MPI_PRINT -Wno-unused-function
+
obj-$(CONFIG_CRYPTO) += api.o scatterwalk.o cipher.o digest.o compress.o

crypto_algapi-$(CONFIG_PROC_FS) += proc.o
@@ -43,5 +48,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.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-11 13:26:14.000000000 +0200
@@ -0,0 +1,861 @@
+/*--
+
+ 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 "rsa.h"
+
+
+// Variables
+
+static mpi *    aux[RSA_AUX_COUNT];
+static _u32     modinv = 0;
+
+
+// Macros
+
+#define rsaMax(x, y)        ((x > y)? x: y)
+
+
+// Function declarations
+
+
+// Functions
+
+/*--
+    Module loading callback function
+    Returns 0 on success or a negative value indicating error
+*///
+static _err __init rsaLoad(void)
+{
+    _u32 i;
+    _err retval = RSA_NO_ERR;
+ + // Pre-allocate some auxilliary mpis + rsaEcho("Preallocating %d 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++)
+        if((retval = rsaMpiAlloc(&aux[i], RSA_AUX_SIZE)) < 0)
+            goto rollback;
+    rsaEcho("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++)
+        rsaMpiFree(aux[i]);
+    return retval;
+}
+
+
+
+/*--
+    Module unloading callback function
+*///
+static void __exit rsaUnload(void)
+{
+    _u32 i;
+ + // Free all the pre-allocated auxilliary mpis
+    for(i = 0; i < RSA_AUX_COUNT; i++)
+        rsaMpiFree(aux[i]);
+    rsaEcho("RSA cipher algorithm module unloaded\n");
+}
+
+
+
+/*--
+ Preallocate an mpi. The allocated mpi will be all-zeroed and not canonicalized
+    Returns 0 on success or a negative value indicating error
+*///
+static _err rsaMpiAlloc(mpi ** n, // Through this pointer pointer the function will return the allocated mpi + _i32 limbs) // Number of allocated limbs (32 bit digits)
+{
+    mpi * handle;
+ + rsaDebug("rsaMpiAlloc called to allocate an mpi of %d limbs\n", limbs); + + *n = NULL;
+    if(!limbs)
+        return RSA_ERR_INVARG;
+ + // Allocate space for the mpi
+    if(!(handle = *n = kmalloc(sizeof(mpi), GFP_KERNEL)))
+    {
+        rsaDebug("rsaMpiAlloc: kmalloc failed\n");
+        return RSA_ERR_NOMEM;
+    }
+ + if(!(handle->data = kzalloc(limbs * sizeof(_u32), GFP_KERNEL)))
+    {
+        kfree(handle);
+        *n = NULL;
+        rsaDebug("rsaMpiAlloc: kzalloc failed\n");
+ return RSA_ERR_NOMEM; + } + + handle->sign = 0;
+    handle->size = handle->limbs = limbs;
+    return RSA_NO_ERR;
+}
+
+
+
+/*--
+    Free the resources held by an mpi
+*///
+static void rsaMpiFree(mpi * n)
+{
+    if(!n)
+        return;
+    kfree(n->data);
+    kfree(n);
+}
+
+
+
+/*--
+    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
+*///
+static _err rsaMpiInit(mpi ** n, // Through this pointer pointer the function will return the allocated mpi
+                       _u8 *     str,
+                       _u32        size,
+ _u32 xtra) // Preallocate some more limbs to avoid future reallocations
+{
+    _i32 i, j;
+    _u32 * buf;
+    _i32 s;
+    _err retval;
+ + *n = NULL;
+    if(!size && !xtra)
+    {
+        rsaDebug("rsaMpiInit: invalid initialization string\n");
+        return RSA_ERR_INVARG;
+    }
+ + // Allocate space for the mpi and its data
+    s = (size / 4) + ((size % 4)? 1: 0);
+    if((retval = rsaMpiAlloc(n, s + xtra)) < 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;
+}
+
+
+
+/*--
+    Resize an mpi, doing all the needed re-allocations
+    Returns 0 on success or a negative value indicating error
+*///
+static _err rsaMpiResize(mpi **    n,
+                         _i32     size,
+                         _u8    hold)    // Hold the initial data
+{
+    _err retval;
+    mpi * handle = *n;
+ + // If there is an allocated mpi passed in, that has the available limbs
+    if(handle && handle->limbs >= size)
+ { + _i32 i, s;
+         _u32 * buf;
+ + // If the original data are not needed they are zeroed
+        if(!hold)
+ { + for(i = 0, s = handle->size, buf = handle->data; i < s; i++)
+                    buf[i] = 0;
+            handle->sign = 0;
+        }
+        // Zero the xtra limbs
+        else if(size < handle->size)
+            for(i = size, s = handle->size, buf = handle->data; i < s; i++)
+                buf[i] = 0;
+        handle->size = size;
+    }
+ // If there is an allocated mpi passed in, that doesn't have the available
+    // limbs already allocated
+    else if(handle)
+    {
+        mpi * tmp = NULL;
+ + if((retval = rsaMpiAlloc(&tmp, size)) < 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;
+        }
+ + rsaMpiFree(*n);
+        *n = tmp;
+        return retval;
+    }
+    // If there is no allocated mpi passed in, allocate one
+    else if(!(handle) && (retval = rsaMpiAlloc(n, size)) < 0)
+        return retval;
+ + 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
+*///
+static _err rsaMpiSet(mpi **     n,
+                      _u8 *        str,
+                      _u32        size)
+{
+    _i32 s, i, j;
+    _u32 * buf;
+    _err retval;
+ + if(!size)
+    {
+        rsaDebug("rsaMpiSet: invalid initialization string\n");
+        return RSA_ERR_INVARG;
+    }
+ + // Size of the new mpi value (in limbs)
+    s = (size / 4) + ((size % 4)? 1: 0);
+    if((retval = rsaMpiResize(n, s, false)) < 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
+*///
+static _err rsaMpiCopy(mpi **    dest,
+                       mpi *    src)
+{
+    _i32 i, s;
+    _u32 * destbuf, * srcbuf;
+    _err retval;
+ + if((retval = rsaMpiResize(dest, src->size, false)) < 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;
+}
+
+
+
+/*--
+    Print the value of an mpi
+*///
+static void rsaMpiPrint(mpi *    n,
+                        _u8        how)    // True to print canonicalized
+{
+#ifdef RSA_HAVE_MPI_PRINT
+    _i32 i, j;
+    _u32 limb;
+    _u8 byte, started = false;
+
+ rsaEcho("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(rsaMpiIsZero(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");
+#endif
+}
+
+
+
+/*--
+    Check if an mpi is zero
+    Returns true if it is, false otherwise
+*///
+static _u8 rsaMpiIsZero(mpi * n)
+{
+    _i32 i, s;
+    _u32 * buf;
+ + for(i = 0, s = n->size, buf = n->data; i < s; i++)
+        if(buf[i])
+            return false;
+    return true;
+}
+
+
+
+/*--
+    Compare two mpis
+    Returns -1 if a < b, 1 if b < a, 0 otherwise
+*///
+static _i8 rsaMpiCompare(mpi * a,
+                         mpi * b)
+{
+    _i32 i, j, asize, bsize;
+    _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
+    asize = a->size;
+ bsize = b->size; + if(asize > bsize && rsaMpiClz(a) < (asize - bsize) * 32)
+        return 1;
+    else if(asize > bsize)
+        j = bsize;
+    else if(bsize > asize && rsaMpiClz(b) < (bsize - asize) * 32)
+        return -1;
+    else
+        j = asize;
+ + // 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;
+}
+
+
+
+/*--
+    Count leading zeroes
+    Returns the number of leading zero bits
+*///
+static _u64 rsaMpiClz( mpi * n)
+{
+     _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;
+}
+
+
+
+/*--
+    Complement the number (either 1's or 2's complement) ignoring overflow
+*///
+static void rsaMpiComplement(mpi *    n,
+ _u8 which) // Compute 2's complement if true, 1's complement otherwise
+{
+    _i32 i, s;
+    _u32 * buf;
+ + for(i = 0, s = n->size, buf = n->data; i < s; i++)
+        buf[i] ^= RSA_MAX_U32;
+    if(!which)
+ return; + + // Add 1 using the addition carry
+    for(i = 0; i < s; i++)
+    {
+        buf[i] += 1;
+        if(buf[i])
+            break;
+    }
+}
+
+
+
+/*--
+    Ignore any leading zero limbs of an mpi
+*///
+static void rsaMpiCanonicalize(mpi * n)
+{
+    _i32 i;
+    _u32 * buf = n->data;
+ + for(i = n->size - 1; i >= 0; i--)
+        if(!buf[i] && n->size > 1)
+            n->size--;
+        else
+            break;
+}
+
+
+
+/*--
+    Shift a number both directions
+    Returns 0 on success or a negative value indicating error
+*///
+static _err rsaMpiShift(mpi ** n, + _i64 bits) // Shift to the right if positive, otherwise shift to the left
+{
+    _i32 i, distance, size, lz;
+    _u32 * buf;
+    mpi * handle;
+    _err retval;
+ + handle = *n;
+    if(!bits || rsaMpiIsZero(handle))
+        return RSA_NO_ERR;
+ + // Shifting to the right, no resize needed + if(bits > 0)
+    {
+        // Drop off one limb for each 32 bit shift
+ for(i = 0, distance = bits / 32, size = handle->size, buf = handle->data; 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;
+ } + } + + rsaMpiCanonicalize(handle);
+        return RSA_NO_ERR;
+ } + + bits = -bits;
+    lz = rsaMpiClz(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);
+        if((retval = rsaMpiResize(n, handle->limbs + size, true)) < 0)
+            return retval;
+        handle = *n;
+    }
+    else
+    {
+        size = bits - rsaMpiClz(handle);
+        handle->size += ((size / 32) + (size % 32 != 0));
+    }
+ + buf = handle->data; + // Shift data 1 byte to the left for each 32 bit shift
+    if((distance = bits / 32))
+    {
+ // 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
+*///
+static _err rsaMpiMultiply(mpi ** res, // Through this pointer pointer the function will return the product
+                           mpi *    a,
+                           mpi *    b)
+{
+    _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;
+    if((retval = rsaMpiResize(res, size, false)) < 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;
+    }
+ + rsaMpiCanonicalize(handle);
+    return RSA_NO_ERR;
+}
+
+
+
+/*--
+    Subtract two mpis
+    Returns 0 on success or a negative value indicating error
+*///
+static _err rsaMpiSubtract(mpi ** res, // Through this pointer pointer the function will return the difference
+                           mpi *     a,
+                           mpi *    b)
+{
+    _u32 * buf, * abuf, * bbuf;
+    _i32 i, size;
+    mpi * handle;
+    _err retval;
+ + size = rsaMax(a->size, b->size) + (a->sign != b->sign);
+    if((retval = rsaMpiResize(res, size, true)) < 0 ||
+       (retval = rsaMpiResize(&a, size, true)) < 0    ||
+       (retval = rsaMpiResize(&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 we 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)
+            rsaMpiComplement(handle, true);
+    }
+    // If the operands are not signed in the same way we perform addition
+    else
+    {
+         _u8 carry = false;
+         _u64 sum;
+ + for(i = 0; i < size; i++)
+        {
+            buf[i] = sum = abuf[i] + bbuf[i] + carry;
+ carry = (sum > RSA_MAX_U32); + } + + handle->sign = a->sign;
+    }
+ + rsaMpiCanonicalize(handle);
+    rsaMpiCanonicalize(a);
+    rsaMpiCanonicalize(b);
+    return RSA_NO_ERR;
+}
+
+
+
+/*--
+    Compute the remainder of a/b (aka a mod b)
+    Returns 0 on success or a negative value indicating error
+*///
+static _err rsaMpiRemainder(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 = rsaMpiCopy(&aux[0], a)) < 0 || (retval = rsaMpiCopy(&aux[1], b)) < 0)
+        return retval;
+ + k = (aux[0]->size - aux[1]->size) * 32; + k += (rsaMpiClz(aux[1]) - rsaMpiClz(aux[0]));
+    // Align the divisor to the divident
+    if((retval = rsaMpiShift(&aux[1], -k)) < 0)
+        return retval;
+ + for(i = 0; i <= k; i++)
+    {
+        if((retval = rsaMpiSubtract(res, aux[0], aux[1])) < 0)
+            return retval;
+        if(!(*res)->sign && (retval = rsaMpiCopy(&aux[0], (*res))) < 0)
+            return retval;
+        if((retval = rsaMpiShift(&aux[1], 1)) < 0)
+ return retval; + } + + rsaMpiCanonicalize(aux[0]);
+    return rsaMpiCopy(res, aux[0]);
+}
+
+
+
+/*--
+    Compute the first 32 bits of the modular inverse of a number
+    Returns 0 on success or a negative value indicating error
+*///
+static _u32 rsaModinv(mpi * n)
+{
+    _u32 i, x, y, tmp, pow1;
+ + pow1 = y = 1;
+    x = n->data[0];
+ + for(i = 2; i <= RSA_RADIX_BITS; i++)
+    {
+        pow1 = pow1 << 1;
+        tmp = ((_i64)x * y) & (RSA_MAX_U32 >> (32 - i));
+ + if(pow1 < tmp)
+            y += pow1;
+    }
+
+    y = (y ^ RSA_MAX_U32) + 1;
+    return y;
+}
+
+
+
+/*--
+ Compute the montgomery product using single precision modulus modular inverse.
+    Variable modinv must have been pre-computed
+    Returns 0 on success or a negative value indicating error
+*///
+static _err rsaMonpro(mpi **    res,
+                      mpi *        a,
+                      mpi *        b,
+                      mpi *     n)
+{
+    _i32 nsize, i, j, k;
+    _u32 * buf, * nbuf, * tmp, m;
+    _u64 product = 0;
+    _err retval;
+ + nsize = n->size;
+    k = nsize << 1;
+    if((retval = rsaMpiMultiply(&aux[2], a, b)) < 0)
+        return retval;
+    if((retval = rsaMpiResize(&aux[2], rsaMax(aux[2]->size, k), true)) < 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);
+    }
+
+    if((retval = rsaMpiResize(&aux[2], aux[2]->size + 1, true)) < 0)
+        return retval;
+    aux[2]->data[aux[2]->size - 1] = product >> 32;
+    if((retval = rsaMpiShift(&aux[2], nsize * 32)) < 0)
+        return retval;
+ + if(rsaMpiCompare(aux[2], n) >= 0)
+    {
+        if((retval = rsaMpiSubtract(&aux[3], aux[2], n)) < 0 ||
+           (retval = rsaMpiCopy(res, aux[3])) < 0)
+            return retval;
+ } + else if((retval = rsaMpiCopy(res, aux[2])) < 0)
+        return retval;
+    return RSA_NO_ERR;
+}
+
+
+
+/*--
+    Computes the RSA of m, a.k.a m ^ e modn
+    Returns 0 on success or a negative value indicating error
+*///
+static _err rsaModexp(mpi **    res,
+                      mpi *        m,        // base
+                      mpi *        e,        // exponent
+                      mpi *        n)        // modulus
+{
+    _i32 i, j;
+    _u32 limb;
+    _u8 started = false;
+    _err retval;
+ + if(m->size != n->size || rsaMpiCompare(m, n) > 0)
+        return RSA_ERR_INVARG;
+
+    modinv = rsaModinv(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]
+    if((retval = rsaMpiCopy(&aux[5], m)) < 0)
+        return retval;
+    if((retval = rsaMpiShift(&aux[5], -(n->size * 32))) < 0)
+        return retval;
+    if((retval = rsaMpiRemainder(&aux[4], aux[5], n)) < 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]
+    if((retval = rsaMpiSet(&aux[5], "\x01", 1)) < 0)
+        return retval;
+    if((retval = rsaMpiShift(&aux[5], -(n->size * 32))) < 0)
+        return retval;
+    if((retval = rsaMpiRemainder(&aux[7], aux[5], n)) < 0)
+        return retval;
+ + // Canonicalize the exponent and compute the modular exponentiation. + // For each limb of the exponent perform left to right binary exponentiation
+    rsaMpiCanonicalize(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
+            if((retval = rsaMonpro(&aux[5], aux[7], aux[7], n)) < 0)
+                return retval;
+ + if(limb & 0x80000000)
+            {
+                // Compute x' = m' * x' mod n
+                if((retval = rsaMonpro(&aux[7], aux[4], aux[5], n)) < 0)
+                    return retval;
+            }
+            else if((retval = rsaMpiCopy(&aux[7], aux[5])) < 0)
+                return retval;
+ + limb = limb << 1; + }
+    }
+ + // Compute res = x' mod n
+    if((retval = rsaMpiSet(&aux[6], "\x01", 1)) < 0)
+        return retval;
+    return rsaMonpro(res, aux[7], aux[6], n);
+}
+
+
+
+module_init(rsaLoad);
+module_exit(rsaUnload);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Tasos Parisinos @ Sciensis Advanced Technology Systems");
+MODULE_DESCRIPTION("RSA cipher algorithm implementation");
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-14 17:59:00.000000000 +0200
@@ -0,0 +1,112 @@
+#ifndef _KM_RSA_H_
+#define _KM_RSA_H_
+
+
+// Includes
+
+#include <linux/module.h>
+#include <linux/errno.h>
+#include <config/rsa/auxcount.h>
+#include <config/rsa/auxsize.h>
+
+// Defines
+
+#ifdef CONFIG_RSA_AUXCOUNT
+    #define RSA_AUX_COUNT         CONFIG_RSA_AUXCOUNT
+#else
+    #define RSA_AUX_COUNT         0x08
+#endif
+
+#ifdef CONFIG_RSA_AUXSIZE
+    #define RSA_AUX_SIZE         CONFIG_RSA_AUXSIZE
+#else
+    #define RSA_AUX_SIZE         0x80
+#endif
+
+#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
+
+
+// Macros
+
+#ifdef RSA_DEBUG
+ #define rsaDebug(fmt, args...) { if(printk_ratelimit()) printk(RSA_LOGLEVEL "rsa: " fmt, ## args); }
+#else
+    #define rsaDebug(fmt, args...)
+#endif
+
+#define rsaEcho(fmt, args...) printk(RSA_LOGLEVEL "rsa: " fmt, ## args)
+
+#if RSA_AUX_COUNT < 8
+    #error "Rsa needs at least 8 auxilliary mpis"
+#endif
+
+
+// Typedefs
+
+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;
+
+
+// Variables
+
+
+// Function declarations
+
+// Module loading/unloading functions
+static _err    __init    rsaLoad(void);
+static void __exit    rsaUnload(void);
+
+// Mpi utility functions
+static _err             rsaMpiAlloc(mpi **, _i32);
+static void         rsaMpiFree(mpi *);
+static _err             rsaMpiInit(mpi **, _u8 *, _u32, _u32);
+static _err         rsaMpiResize(mpi **, _i32, _u8);
+static _err         rsaMpiSet(mpi **, _u8 *, _u32);
+static _err         rsaMpiCopy(mpi **, mpi *);
+static void         rsaMpiPrint(mpi *, _u8);
+
+// Mpi comparing and misc functions
+static _u8             rsaMpiIsZero(mpi *);
+static _i8             rsaMpiCompare(mpi *, mpi *);
+static _u64             rsaMpiClz(mpi *);
+static void             rsaMpiComplement(mpi *, _u8);
+static void             rsaMpiCanonicalize(mpi *);
+
+// Mpi arithmetic functions
+static _err rsaMpiShift(mpi **, _i64); // 2^k multiplication / division
+static _err         rsaMpiMultiply(mpi **, mpi *, mpi *);
+static _err         rsaMpiSubtract(mpi **, mpi *, mpi *);
+static _err         rsaMpiRemainder(mpi **, mpi *, mpi *);
+
+// Rsa functions
+static _u32             rsaModinv(mpi *);
+static _err         rsaMonpro(mpi **, mpi *, mpi *, mpi *);
+static _err         rsaModexp(mpi **, mpi *, mpi *, mpi *);
+
+ +#endif // _KM_RSA_H_

-
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/

Reply via email to