From 5d4a6be97b760e5340a5def64cfd44af6f4150d2 Mon Sep 17 00:00:00 2001 From: mdw Date: Wed, 22 Dec 1999 15:53:12 +0000 Subject: [PATCH] Random number generator for finding DSA parameters. --- dsarand.c | 335 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ dsarand.h | 160 ++++++++++++++++++++++++++++++ 2 files changed, 495 insertions(+) create mode 100644 dsarand.c create mode 100644 dsarand.h diff --git a/dsarand.c b/dsarand.c new file mode 100644 index 0000000..fd54b6d --- /dev/null +++ b/dsarand.c @@ -0,0 +1,335 @@ +/* -*-c-*- + * + * $Id: dsarand.c,v 1.1 1999/12/22 15:53:12 mdw Exp $ + * + * Random number generator for DSA + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: dsarand.c,v $ + * Revision 1.1 1999/12/22 15:53:12 mdw + * Random number generator for finding DSA parameters. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include + +#include +#include + +#include "dsarand.h" +#include "grand.h" +#include "sha.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @STEP@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * + * Use: Increments the buffer by one, interpreting it as a big-endian + * integer. Carries outside the integer are discarded. + */ + +#define STEP(d) do { \ + dsarand *_d = (d); \ + octet *_p = _d->p; \ + octet *_q = _p + _d->sz; \ + unsigned _c = 1; \ + while (_c && _q > _p) { \ + _c += *--_q; \ + *_q = U8(_c); \ + _c >>= 8; \ + } \ +} while (0) + +/* --- @dsarand_init@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * @const void *p@ = pointer to seed buffer + * @size_t sz@ = size of the buffer + * + * Returns: --- + * + * Use: Initializes a DSA random number generator. + */ + +void dsarand_init(dsarand *d, const void *p, size_t sz) +{ + d->p = xmalloc(sz); + d->sz = sz; + if (p) + memcpy(d->p, p, sz); +} + +/* --- @dsarand_reseed@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * @const void *p@ = pointer to seed buffer + * @size_t sz@ = size of the buffer + * + * Returns: --- + * + * Use: Initializes a DSA random number generator. + */ + +void dsarand_reseed(dsarand *d, const void *p, size_t sz) +{ + free(d->p); + d->p = xmalloc(sz); + d->sz = sz; + d->passes = 1; + if (p) + memcpy(d->p, p, sz); +} + +/* --- @dsarand_destroy@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * + * Returns: --- + * + * Use: Disposes of a DSA random number generation context. + */ + +void dsarand_destroy(dsarand *d) +{ + free(d->p); +} + +/* --- @dsarand_fill@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * @void *p@ = pointer to output buffer + * @size_t sz@ = size of output buffer + * + * Returns: --- + * + * Use: Fills an output buffer with pseudorandom data. + * + * Let %$p$% be the numerical value of the input buffer, and let + * %$b$% be the number of bytes required. Let + * %$z = \lceil b / 20 \rceil%$ be the number of SHA outputs + * required. Then the output of pass %$n$% is + * + * %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$% + * %${} \bmod 2^{8b}$% + * + * and the actual result in the output buffer is the XOR of all + * of the output passes. + * + * The DSA procedure for choosing @q@ involves two passes with + * %$z = 1$%; the procedure for choosing @p@ involves one pass + * with larger %$z$%. This generalization of the DSA generation + * procedure is my own invention but it seems relatively sound. + */ + +void dsarand_fill(dsarand *d, void *p, size_t sz) +{ + octet *q = p; + unsigned n = d->passes; + + /* --- Write out the first pass --- * + * + * This can write directly to the output buffer, so it's done differently + * from the latter passes. + */ + + { + size_t o = sz; + + while (o) { + sha_ctx h; + + /* --- Hash the input buffer --- */ + + sha_init(&h); + sha_hash(&h, d->p, d->sz); + + /* --- If enough space, extract the hash output directly --- */ + + if (o >= SHA_HASHSZ) { + o -= SHA_HASHSZ; + sha_done(&h, q + o); + } + + /* --- Otherwise take the hash result out of line and copy it --- */ + + else { + octet hash[SHA_HASHSZ]; + sha_done(&h, hash); + memcpy(q, hash + (SHA_HASHSZ - o), o); + o = 0; + } + + /* --- Step the input buffer --- */ + + STEP(d); + } + + /* --- Another pass has been done --- */ + + n--; + } + + /* --- Write out subsequent passes --- * + * + * The hash output has to be done offline, so this is slightly easier. + */ + + while (n) { + size_t o = sz; + + while (o) { + sha_ctx h; + octet hash[SHA_HASHSZ]; + size_t n; + octet *pp, *qq; + + /* --- Hash the input buffer --- */ + + sha_init(&h); + sha_hash(&h, d->p, d->sz); + sha_done(&h, hash); + + /* --- Work out how much output is wanted --- */ + + n = SHA_HASHSZ; + if (n > o) + n = o; + o -= n; + + /* --- XOR the data out --- */ + + for (pp = hash + (SHA_HASHSZ - n), qq = q + o; + pp < hash + SHA_HASHSZ; pp++, qq++) + *qq ^= *pp; + + /* --- Step the input buffer --- */ + + STEP(d); + } + + /* --- Another pass is done --- */ + + n--; + } +} + +/*----- Generic pseudorandom-number generator interface -------------------*/ + +static const grand_ops gops; + +typedef struct gctx { + grand r; + dsarand d; +} gctx; + +static void gdestroy(grand *r) +{ + gctx *g = (gctx *)r; + dsarand_destroy(&g->d); + DESTROY(g); +} + +static int gmisc(grand *r, unsigned op, ...) +{ + gctx *g = (gctx *)r; + va_list ap; + int rc = 0; + va_start(ap, op); + + switch (op) { + case GRAND_CHECK: + switch (va_arg(ap, unsigned)) { + case GRAND_CHECK: + case GRAND_SEEDBLOCK: + case GRAND_SEEDRAND: + case DSARAND_PASSES: + rc = 1; + break; + default: + rc = 0; + break; + } + break; + case GRAND_SEEDBLOCK: { + const void *p = va_arg(ap, const void *); + size_t sz = va_arg(ap, size_t); + dsarand_reseed(&g->d, p, sz); + } break; + case GRAND_SEEDRAND: { + grand *rr = va_arg(ap, grand *); + rr->ops->fill(rr, g->d.p, g->d.sz); + } break; + case DSARAND_PASSES: + g->d.passes = va_arg(ap, unsigned); + break; + default: + GRAND_BADOP; + break; + } + + va_end(ap); + return (rc); +} + +static void gfill(grand *r, void *p, size_t sz) +{ + gctx *g = (gctx *)r; + dsarand_fill(&g->d, p, sz); +} + +static const grand_ops gops = { + "dsarand", + 0, + gmisc, gdestroy, + grand_word, grand_byte, grand_word, grand_range, gfill +}; + +/* --- @dsarand_create@ --- * + * + * Arguments: @const void *p@ = pointer to seed buffer + * @size_t sz@ = size of seed buffer + * + * Returns: Pointer to a generic generator. + * + * Use: Constructs a generic generator interface over a Catacomb + * entropy pool generator. + */ + +grand *dsarand_create(const void *p, size_t sz) +{ + gctx *g = CREATE(gctx); + g->r.ops = &gops; + dsarand_init(&g->d, p, sz); + return (&g->r); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/dsarand.h b/dsarand.h new file mode 100644 index 0000000..553efb1 --- /dev/null +++ b/dsarand.h @@ -0,0 +1,160 @@ +/* -*-c-*- + * + * $Id: dsarand.h,v 1.1 1999/12/22 15:53:12 mdw Exp $ + * + * Random number generator for DSA + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: dsarand.h,v $ + * Revision 1.1 1999/12/22 15:53:12 mdw + * Random number generator for finding DSA parameters. + * + */ + +#ifndef CATACOMB_DSARAND_H +#define CATACOMB_DSARAND_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +#ifndef CATACOMB_GRAND_H +# include "grand.h" +#endif + +#ifndef CATACOMB_SHA_H +# include "sha.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct dsarand { + octet *p; /* Pointer to seed (modified) */ + size_t sz; /* Size of the seed buffer */ + unsigned passes; /* Number of passes to make */ +} dsarand; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @dsarand_init@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * @const void *p@ = pointer to seed buffer + * @size_t sz@ = size of the buffer + * + * Returns: --- + * + * Use: Initializes a DSA random number generator. + */ + +extern void dsarand_init(dsarand */*d*/, const void */*p*/, size_t /*sz*/); + +/* --- @dsarand_reseed@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * @const void *p@ = pointer to seed buffer + * @size_t sz@ = size of the buffer + * + * Returns: --- + * + * Use: Initializes a DSA random number generator. + */ + +extern void dsarand_reseed(dsarand */*d*/, const void */*p*/, size_t /*sz*/); + +/* --- @dsarand_destroy@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * + * Returns: --- + * + * Use: Disposes of a DSA random number generation context. + */ + +extern void dsarand_destroy(dsarand */*d*/); + +/* --- @dsarand_fill@ --- * + * + * Arguments: @dsarand *d@ = pointer to context + * @void *p@ = pointer to output buffer + * @size_t sz@ = size of output buffer + * + * Returns: --- + * + * Use: Fills an output buffer with pseudorandom data. + * + * Let %$p$% be the numerical value of the input buffer, and let + * %$b$% be the number of bytes required. Let + * %$z = \lceil b / 20 \rceil%$ be the number of SHA outputs + * required. Then the output of pass %$n$% is + * + * %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$% + * %${} \bmod 2^{8b}$% + * + * and the actual result in the output buffer is the XOR of all + * of the output passes. + * + * The DSA procedure for choosing @q@ involves two passes with + * %$z = 1$%; the procedure for choosing @p@ involves one pass + * with larger %$z$%. This generalization of the DSA generation + * procedure is my own invention but it seems relatively sound. + */ + +extern void dsarand_fill(dsarand */*d*/, void */*p*/, size_t /*sz*/); + +/*----- Generic pseudorandom-number generator interface -------------------*/ + +/* --- Miscellaneous operations --- */ + +enum { + DSARAND_PASSES = GRAND_SPECIFIC +}; + +/* --- @dsarand_create@ --- * + * + * Arguments: @const void *p@ = pointer to seed buffer + * @size_t sz@ = size of seed buffer + * + * Returns: Pointer to a generic generator. + * + * Use: Constructs a generic generator interface over a Catacomb + * entropy pool generator. + */ + +extern grand *dsarand_create(const void */*p*/, size_t /*sz*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif -- 2.11.0