git.distorted.org.uk Git - u/mdw/catacomb/blob - dsarand.c

   1 /* -*-c-*-
   2  *
   3  * $Id: dsarand.c,v 1.1 1999/12/22 15:53:12 mdw Exp $
   4  *
   5  * Random number generator for DSA
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: dsarand.c,v $
  33  * Revision 1.1  1999/12/22 15:53:12  mdw
  34  * Random number generator for finding DSA parameters.
  35  *
  36  */
  37
  38 /*----- Header files ------------------------------------------------------*/
  39
  40 #include <stdarg.h>
  41 #include <string.h>
  42
  43 #include <mLib/bits.h>
  44 #include <mLib/sub.h>
  45
  46 #include "dsarand.h"
  47 #include "grand.h"
  48 #include "sha.h"
  49
  50 /*----- Main code ---------------------------------------------------------*/
  51
  52 /* --- @STEP@ --- *
  53  *
  54  * Arguments:   @dsarand *d@ = pointer to context
  55  *
  56  * Use:         Increments the buffer by one, interpreting it as a big-endian
  57  *              integer.  Carries outside the integer are discarded.
  58  */
  59
  60 #define STEP(d) do {                                                    \
  61   dsarand *_d = (d);                                                    \
  62   octet *_p = _d->p;                                                    \
  63   octet *_q = _p + _d->sz;                                              \
  64   unsigned _c = 1;                                                      \
  65   while (_c && _q > _p) {                                               \
  66     _c += *--_q;                                                        \
  67     *_q = U8(_c);                                                       \
  68     _c >>= 8;                                                           \
  69   }                                                                     \
  70 } while (0)
  71
  72 /* --- @dsarand_init@ --- *
  73  *
  74  * Arguments:   @dsarand *d@ = pointer to context
  75  *              @const void *p@ = pointer to seed buffer
  76  *              @size_t sz@ = size of the buffer
  77  *
  78  * Returns:     ---
  79  *
  80  * Use:         Initializes a DSA random number generator.
  81  */
  82
  83 void dsarand_init(dsarand *d, const void *p, size_t sz)
  84 {
  85   d->p = xmalloc(sz);
  86   d->sz = sz;
  87   if (p)
  88     memcpy(d->p, p, sz);
  89 }
  90
  91 /* --- @dsarand_reseed@ --- *
  92  *
  93  * Arguments:   @dsarand *d@ = pointer to context
  94  *              @const void *p@ = pointer to seed buffer
  95  *              @size_t sz@ = size of the buffer
  96  *
  97  * Returns:     ---
  98  *
  99  * Use:         Initializes a DSA random number generator.
 100  */
 101
 102 void dsarand_reseed(dsarand *d, const void *p, size_t sz)
 103 {
 104   free(d->p);
 105   d->p = xmalloc(sz);
 106   d->sz = sz;
 107   d->passes = 1;
 108   if (p)
 109     memcpy(d->p, p, sz);
 110 }
 111
 112 /* --- @dsarand_destroy@ --- *
 113  *
 114  * Arguments:   @dsarand *d@ = pointer to context
 115  *
 116  * Returns:     ---
 117  *
 118  * Use:         Disposes of a DSA random number generation context.
 119  */
 120
 121 void dsarand_destroy(dsarand *d)
 122 {
 123   free(d->p);
 124 }
 125
 126 /* --- @dsarand_fill@ --- *
 127  *
 128  * Arguments:   @dsarand *d@ = pointer to context
 129  *              @void *p@ = pointer to output buffer
 130  *              @size_t sz@ = size of output buffer
 131  *
 132  * Returns:     ---
 133  *
 134  * Use:         Fills an output buffer with pseudorandom data.
 135  *
 136  *              Let %$p$% be the numerical value of the input buffer, and let
 137  *              %$b$% be the number of bytes required.  Let
 138  *              %$z = \lceil b / 20 \rceil%$ be the number of SHA outputs
 139  *              required.  Then the output of pass %$n$% is
 140  *
 141  *                %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$%
 142  *                                                      %${} \bmod 2^{8b}$%
 143  *
 144  *              and the actual result in the output buffer is the XOR of all
 145  *              of the output passes.
 146  *
 147  *              The DSA procedure for choosing @q@ involves two passes with
 148  *              %$z = 1$%; the procedure for choosing @p@ involves one pass
 149  *              with larger %$z$%.  This generalization of the DSA generation
 150  *              procedure is my own invention but it seems relatively sound.
 151  */
 152
 153 void dsarand_fill(dsarand *d, void *p, size_t sz)
 154 {
 155   octet *q = p;
 156   unsigned n = d->passes;
 157
 158   /* --- Write out the first pass --- *
 159    *
 160    * This can write directly to the output buffer, so it's done differently
 161    * from the latter passes.
 162    */
 163
 164   {
 165     size_t o = sz;
 166
 167     while (o) {
 168       sha_ctx h;
 169
 170       /* --- Hash the input buffer --- */
 171
 172       sha_init(&h);
 173       sha_hash(&h, d->p, d->sz);
 174
 175       /* --- If enough space, extract the hash output directly --- */
 176
 177       if (o >= SHA_HASHSZ) {
 178         o -= SHA_HASHSZ;
 179         sha_done(&h, q + o);
 180       }
 181
 182       /* --- Otherwise take the hash result out of line and copy it --- */
 183
 184       else {
 185         octet hash[SHA_HASHSZ];
 186         sha_done(&h, hash);
 187         memcpy(q, hash + (SHA_HASHSZ - o), o);
 188         o = 0;
 189       }
 190
 191       /* --- Step the input buffer --- */
 192
 193       STEP(d);
 194     }
 195
 196     /* --- Another pass has been done --- */
 197
 198     n--;
 199   }
 200
 201   /* --- Write out subsequent passes --- *
 202    *
 203    * The hash output has to be done offline, so this is slightly easier.
 204    */
 205
 206   while (n) {
 207     size_t o = sz;
 208
 209     while (o) {
 210       sha_ctx h;
 211       octet hash[SHA_HASHSZ];
 212       size_t n;
 213       octet *pp, *qq;
 214
 215       /* --- Hash the input buffer --- */
 216
 217       sha_init(&h);
 218       sha_hash(&h, d->p, d->sz);
 219       sha_done(&h, hash);
 220
 221       /* --- Work out how much output is wanted --- */
 222
 223       n = SHA_HASHSZ;
 224       if (n > o)
 225         n = o;
 226       o -= n;
 227
 228       /* --- XOR the data out --- */
 229
 230       for (pp = hash + (SHA_HASHSZ - n), qq = q + o;
 231            pp < hash + SHA_HASHSZ; pp++, qq++)
 232         *qq ^= *pp;
 233
 234       /* --- Step the input buffer --- */
 235
 236       STEP(d);
 237     }
 238
 239     /* --- Another pass is done --- */
 240
 241     n--;
 242   }
 243 }
 244
 245 /*----- Generic pseudorandom-number generator interface -------------------*/
 246
 247 static const grand_ops gops;
 248
 249 typedef struct gctx {
 250   grand r;
 251   dsarand d;
 252 } gctx;
 253
 254 static void gdestroy(grand *r)
 255 {
 256   gctx *g = (gctx *)r;
 257   dsarand_destroy(&g->d);
 258   DESTROY(g);
 259 }
 260
 261 static int gmisc(grand *r, unsigned op, ...)
 262 {
 263   gctx *g = (gctx *)r;
 264   va_list ap;
 265   int rc = 0;
 266   va_start(ap, op);
 267
 268   switch (op) {
 269     case GRAND_CHECK:
 270       switch (va_arg(ap, unsigned)) {
 271         case GRAND_CHECK:
 272         case GRAND_SEEDBLOCK:
 273         case GRAND_SEEDRAND:
 274         case DSARAND_PASSES:
 275           rc = 1;
 276           break;
 277         default:
 278           rc = 0;
 279           break;
 280       }
 281       break;
 282     case GRAND_SEEDBLOCK: {
 283       const void *p = va_arg(ap, const void *);
 284       size_t sz = va_arg(ap, size_t);
 285       dsarand_reseed(&g->d, p, sz);
 286     } break;
 287     case GRAND_SEEDRAND: {
 288       grand *rr = va_arg(ap, grand *);
 289       rr->ops->fill(rr, g->d.p, g->d.sz);
 290     } break;
 291     case DSARAND_PASSES:
 292       g->d.passes = va_arg(ap, unsigned);
 293       break;
 294     default:
 295       GRAND_BADOP;
 296       break;
 297   }
 298
 299   va_end(ap);
 300   return (rc);
 301 }
 302
 303 static void gfill(grand *r, void *p, size_t sz)
 304 {
 305   gctx *g = (gctx *)r;
 306   dsarand_fill(&g->d, p, sz);
 307 }
 308
 309 static const grand_ops gops = {
 310   "dsarand",
 311   0,
 312   gmisc, gdestroy,
 313   grand_word, grand_byte, grand_word, grand_range, gfill
 314 };
 315
 316 /* --- @dsarand_create@ --- *
 317  *
 318  * Arguments:   @const void *p@ = pointer to seed buffer
 319  *              @size_t sz@ = size of seed buffer
 320  *
 321  * Returns:     Pointer to a generic generator.
 322  *
 323  * Use:         Constructs a generic generator interface over a Catacomb
 324  *              entropy pool generator.
 325  */
 326
 327 grand *dsarand_create(const void *p, size_t sz)
 328 {
 329   gctx *g = CREATE(gctx);
 330   g->r.ops = &gops;
 331   dsarand_init(&g->d, p, sz);
 332   return (&g->r);
 333 }
 334
 335 /*----- That's all, folks -------------------------------------------------*/