>From 0dea4a79c856eb5d0897fa3c83fd7b4aa1b5150f Mon Sep 17 00:00:00 2001
From: Vegard Nossum <[email protected]>
Date: Fri, 23 Jan 2009 20:17:08 +0100
Subject: [PATCH] crypto: implement new prng, Vegard's PRNG
Hi,
I realize that submitting a non-cryptographically secure algorithm to a
crypto mailing list might not make too much sense. On the other hand, it
shouldn't hurt either, and I've written this, so why not? I don't know
if this is actually useful for anything at all, so this patch is more of
an "it exists" rather than a serious patch submission.
The only obvious property of this algorithm is its fixed, known sequence
period.
(Note: I didn't actually test the code either, so it could all be wrong.)
Signed-off-by: Vegard Nossum <[email protected]>
---
crypto/Kconfig | 7 ++
crypto/Makefile | 1 +
crypto/vprng.c | 179 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 187 insertions(+), 0 deletions(-)
create mode 100644 crypto/vprng.c
diff --git a/crypto/Kconfig b/crypto/Kconfig
index 8dde4fc..e31c97d 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -734,6 +734,13 @@ config CRYPTO_ANSI_CPRNG
for cryptographic modules. Uses the Algorithm specified in
ANSI X9.31 A.2.4
+config CRYPTO_VPRNG
+ tristate "Vegard's Pseudo-Random Number Generator"
+ select CRYPTO_RNG
+ help
+ A very simple PRNG. WARNING: This algorithm is not
+ cryptographically secure!
+
source "drivers/crypto/Kconfig"
endif # if CRYPTO
diff --git a/crypto/Makefile b/crypto/Makefile
index 46b08bf..417b197 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -77,6 +77,7 @@ obj-$(CONFIG_CRYPTO_LZO) += lzo.o
obj-$(CONFIG_CRYPTO_RNG2) += rng.o
obj-$(CONFIG_CRYPTO_RNG2) += krng.o
obj-$(CONFIG_CRYPTO_ANSI_CPRNG) += ansi_cprng.o
+obj-$(CONFIG_CRYPTO_VPRNG) += vprng.o
obj-$(CONFIG_CRYPTO_TEST) += tcrypt.o
#
diff --git a/crypto/vprng.c b/crypto/vprng.c
new file mode 100644
index 0000000..eeed88f
--- /dev/null
+++ b/crypto/vprng.c
@@ -0,0 +1,179 @@
+/*
+ * Vegard's Pseudo-Random NG.
+ *
+ * Copyright (c) 2009 Vegard Nossum <[email protected]>
+ *
+ * based on:
+ *
+ * RNG implementation using standard kernel RNG.
+ *
+ * Copyright (c) 2008 Herbert Xu <[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
+ * any later version.
+ *
+ */
+
+#include <crypto/internal/rng.h>
+#include <linux/err.h>
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/random.h>
+
+#define DEFAULT_N 40
+
+/* A table of prime numbers. This could be generated, but what a bother. */
+static int primes[] = {
+ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
+ 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
+ 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
+ 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
+ 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
+};
+
+struct vprng_context {
+ spinlock_t lock;
+
+ /* The number of counters */
+ unsigned int n;
+
+ /* Counters */
+ u8 *c;
+};
+
+static int vprng_init(struct crypto_tfm *tfm)
+{
+ struct vprng_context *ctx = crypto_tfm_ctx(tfm);
+
+ spin_lock_init(&ctx->lock);
+ ctx->n = DEFAULT_N;
+ ctx->c = kcalloc(ctx->n, sizeof(*ctx->c), 0);
+ if (!ctx->c)
+ return -ENOMEM;
+
+ return 0;
+}
+
+static void vprng_exit(struct crypto_tfm *tfm)
+{
+ struct vprng_context *ctx = crypto_tfm_ctx(tfm);
+
+ kfree(ctx->c);
+}
+
+/*
+ * To generate a random bit, we sum the values of all the counters and return
+ * the least significant bit of this number. The counters all wrap around at
+ * a prime number, so the generated sequence of bits has a period of exactly
+ * $ \prod_{i=0}^{n-1} primes_i $ bits.
+ */
+static u8 vprng_get_random_bit(unsigned int n, u8 *c)
+{
+ u8 ret;
+ unsigned int i;
+
+ ret = 0;
+ for (i = 0; i < n; ++i) {
+ ret += c[i];
+
+ if (++c[i] == primes[i])
+ c[i] = 0;
+ }
+
+ return ret & 1;
+}
+
+static u8 vprng_get_random_byte(unsigned int n, u8 *c)
+{
+ u8 ret;
+ unsigned int i;
+
+ ret = 0;
+ for (i = 0; i < 8; ++i)
+ ret = (ret << 1) | vprng_get_random_bit(n, c);
+
+ return ret;
+}
+
+static int vprng_get_random(struct crypto_rng *tfm,
+ u8 *rdata, unsigned int dlen)
+{
+ struct vprng_context *ctx = crypto_rng_ctx(tfm);
+ unsigned int i;
+
+ spin_lock(&ctx->lock);
+ for (i = 0; i < dlen; ++i)
+ rdata[i] = vprng_get_random_byte(ctx->n, ctx->c);
+ spin_unlock(&ctx->lock);
+
+ return 0;
+}
+
+static int _vprng_reset(struct vprng_context *ctx, u8 *seed, unsigned int slen)
+{
+ unsigned int i;
+
+ if (slen != ctx->n)
+ return -EINVAL;
+
+ for (i = 0; i < slen; ++i)
+ ctx->c[i] = seed[i];
+
+ return 0;
+}
+
+static int vprng_reset(struct crypto_rng *tfm, u8 *seed, unsigned int slen)
+{
+ struct vprng_context *ctx = crypto_rng_ctx(tfm);
+ int ret;
+
+ spin_lock(&ctx->lock);
+ ret = _vprng_reset(ctx, seed, slen);
+ spin_unlock(&ctx->lock);
+
+ return ret;
+}
+
+static struct crypto_alg vprng_alg = {
+ .cra_name = "vprng",
+ .cra_driver_name = "vprng",
+ .cra_priority = 100,
+ .cra_flags = CRYPTO_ALG_TYPE_RNG,
+ .cra_ctxsize = sizeof(struct vprng_context),
+ .cra_type = &crypto_rng_type,
+ .cra_module = THIS_MODULE,
+ .cra_list = LIST_HEAD_INIT(vprng_alg.cra_list),
+ .cra_init = &vprng_init,
+ .cra_exit = &vprng_exit,
+ .cra_u = {
+ .rng = {
+ .rng_make_random = vprng_get_random,
+ .rng_reset = vprng_reset,
+ .seedsize = DEFAULT_N,
+ }
+ }
+};
+
+/* Module initalization */
+static int __init vprng_mod_init(void)
+{
+ /* Make sure we have enough prime numbers. */
+ BUILD_BUG_ON(ARRAY_SIZE(primes) < DEFAULT_N);
+
+ return crypto_register_alg(&vprng_alg);
+}
+
+static void __exit vprng_mod_fini(void)
+{
+ crypto_unregister_alg(&vprng_alg);
+}
+
+module_init(vprng_mod_init);
+module_exit(vprng_mod_fini);
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("Vegard's Pseudo-Random Number Generator");
+MODULE_AUTHOR("Vegard Nossum <[email protected]>");
+MODULE_ALIAS("vprng");
--
1.6.0.6
On Wed, Feb 25, 2009 at 04:12:43PM +0100, Vegard Nossum wrote:
>
> I realize that submitting a non-cryptographically secure algorithm to a
> crypto mailing list might not make too much sense. On the other hand, it
> shouldn't hurt either, and I've written this, so why not? I don't know
> if this is actually useful for anything at all, so this patch is more of
> an "it exists" rather than a serious patch submission.
>
> The only obvious property of this algorithm is its fixed, known sequence
> period.
>
> (Note: I didn't actually test the code either, so it could all be wrong.)
>
> Signed-off-by: Vegard Nossum <[email protected]>
If we actually had an in-kernel user for this then I'd be more
than happy to add this :)
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt