math/mpreduce.h: Missing include files.

[u/mdw/catacomb] / rand / dsarand.c

/* -*-c-*-
 *
 * 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.
 */

/*----- Header files ------------------------------------------------------*/

#include <stdarg.h>
#include <string.h>

#include <mLib/alloc.h>
#include <mLib/bits.h>
#include <mLib/sub.h>

#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;
  d->passes = 1;
  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)
{
  xfree(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)
{
  xfree(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:
	case DSARAND_SEEDSZ:
	case DSARAND_GETSEED:
	  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;
    case DSARAND_SEEDSZ:
      rc = g->d.sz;
      break;
    case DSARAND_GETSEED:
      memcpy(va_arg(ap, void *), g->d.p, g->d.sz);
      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, 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 -------------------------------------------------*/