chiark - git - mdw - storin/blob - dsarand.c

   1 /* -*-c-*-
   2  *
   3  * $Id: dsarand.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
   4  *
   5  * Random number generator for DSA
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  * (c) 2000 Mark Wooding
   9  */
  10
  11 /*----- Licensing notice --------------------------------------------------*
  12  *
  13  * Copyright (c) 2000 Mark Wooding
  14  * All rights reserved.
  15  *
  16  * Redistribution and use in source and binary forms, with or without
  17  * modification, are permitted provided that the following conditions are
  18  * met:
  19  *
  20  * 1. Redistributions of source code must retain the above copyright
  21  *    notice, this list of conditions and the following disclaimer.
  22  *
  23  * 2, Redistributions in binary form must reproduce the above copyright
  24  *    notice, this list of conditions and the following disclaimer in the
  25  *    documentation and/or other materials provided with the distribution.
  26  *
  27  * 3. The name of the authors may not be used to endorse or promote
  28  *    products derived from this software without specific prior written
  29  *    permission.
  30  *
  31  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
  32  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  33  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN
  34  * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  35  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  36  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  37  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  38  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  39  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  40  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  41  * POSSIBILITY OF SUCH DAMAGE.
  42  *
  43  * Instead of accepting the above terms, you may redistribute and/or modify
  44  * this software under the terms of either the GNU General Public License,
  45  * or the GNU Library General Public License, published by the Free
  46  * Software Foundation; either version 2 of the License, or (at your
  47  * option) any later version.
  48  */
  49
  50 /*----- Revision history --------------------------------------------------*
  51  *
  52  * $Log: dsarand.c,v $
  53  * Revision 1.1  2000/05/21 11:28:30  mdw
  54  * Initial check-in.
  55  *
  56  * --- Past lives (Catacomb) --- *
  57  *
  58  * Revision 1.1  1999/12/22 15:53:12  mdw
  59  * Random number generator for finding DSA parameters.
  60  *
  61  */
  62
  63 /*----- Header files ------------------------------------------------------*/
  64
  65 #include <stdio.h>
  66 #include <stdlib.h>
  67 #include <string.h>
  68
  69 #include "bits.h"
  70 #include "dsarand.h"
  71 #include "sha.h"
  72
  73 /*----- Main code ---------------------------------------------------------*/
  74
  75 /* --- @STEP@ --- *
  76  *
  77  * Arguments:   @dsarand *d@ = pointer to context
  78  *
  79  * Use:         Increments the buffer by one, interpreting it as a big-endian
  80  *              integer.  Carries outside the integer are discarded.
  81  */
  82
  83 #define STEP(d) do {                                                    \
  84   dsarand *_d = (d);                                                    \
  85   octet *_p = _d->p;                                                    \
  86   octet *_q = _p + _d->sz;                                              \
  87   unsigned _c = 1;                                                      \
  88   while (_c && _q > _p) {                                               \
  89     _c += *--_q;                                                        \
  90     *_q = U8(_c);                                                       \
  91     _c >>= 8;                                                           \
  92   }                                                                     \
  93 } while (0)
  94
  95 /* --- @dsarand_init@ --- *
  96  *
  97  * Arguments:   @dsarand *d@ = pointer to context
  98  *              @const void *p@ = pointer to seed buffer
  99  *              @size_t sz@ = size of the buffer
 100  *
 101  * Returns:     ---
 102  *
 103  * Use:         Initializes a DSA random number generator.
 104  */
 105
 106 void dsarand_init(dsarand *d, const void *p, size_t sz)
 107 {
 108   if ((d->p = malloc(sz)) == 0) {
 109     fputs("Out of memory in dsarand_init!\n", stderr);
 110     exit(EXIT_FAILURE);
 111   }
 112   d->sz = sz;
 113   d->passes = 1;
 114   if (p)
 115     memcpy(d->p, p, sz);
 116 }
 117
 118 /* --- @dsarand_reseed@ --- *
 119  *
 120  * Arguments:   @dsarand *d@ = pointer to context
 121  *              @const void *p@ = pointer to seed buffer
 122  *              @size_t sz@ = size of the buffer
 123  *
 124  * Returns:     ---
 125  *
 126  * Use:         Initializes a DSA random number generator.
 127  */
 128
 129 void dsarand_reseed(dsarand *d, const void *p, size_t sz)
 130 {
 131   free(d->p);
 132   if ((d->p = malloc(sz)) != 0) {
 133     fputs("Out of memory in dsarand_init!\n", stderr);
 134     exit(EXIT_FAILURE);
 135   }
 136   d->sz = sz;
 137   d->passes = 1;
 138   if (p)
 139     memcpy(d->p, p, sz);
 140 }
 141
 142 /* --- @dsarand_destroy@ --- *
 143  *
 144  * Arguments:   @dsarand *d@ = pointer to context
 145  *
 146  * Returns:     ---
 147  *
 148  * Use:         Disposes of a DSA random number generation context.
 149  */
 150
 151 void dsarand_destroy(dsarand *d)
 152 {
 153   free(d->p);
 154 }
 155
 156 /* --- @dsarand_fill@ --- *
 157  *
 158  * Arguments:   @dsarand *d@ = pointer to context
 159  *              @void *p@ = pointer to output buffer
 160  *              @size_t sz@ = size of output buffer
 161  *
 162  * Returns:     ---
 163  *
 164  * Use:         Fills an output buffer with pseudorandom data.
 165  *
 166  *              Let %$p$% be the numerical value of the input buffer, and let
 167  *              %$b$% be the number of bytes required.  Let
 168  *              %$z = \lceil b / 20 \rceil$% be the number of SHA outputs
 169  *              required.  Then the output of pass %$n$% is
 170  *
 171  *                %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$%
 172  *                                                      %${} \bmod 2^{8b}$%
 173  *
 174  *              and the actual result in the output buffer is the XOR of all
 175  *              of the output passes.
 176  *
 177  *              The DSA procedure for choosing @q@ involves two passes with
 178  *              %$z = 1$%; the procedure for choosing @p@ involves one pass
 179  *              with larger %$z$%.  This generalization of the DSA generation
 180  *              procedure is my own invention but it seems relatively sound.
 181  */
 182
 183 void dsarand_fill(dsarand *d, void *p, size_t sz)
 184 {
 185   octet *q = p;
 186   unsigned n = d->passes;
 187
 188   /* --- Write out the first pass --- *
 189    *
 190    * This can write directly to the output buffer, so it's done differently
 191    * from the latter passes.
 192    */
 193
 194   {
 195     size_t o = sz;
 196
 197     while (o) {
 198       sha_ctx h;
 199
 200       /* --- Hash the input buffer --- */
 201
 202       sha_init(&h);
 203       sha_hash(&h, d->p, d->sz);
 204
 205       /* --- If enough space, extract the hash output directly --- */
 206
 207       if (o >= SHA_HASHSZ) {
 208         o -= SHA_HASHSZ;
 209         sha_done(&h, q + o);
 210       }
 211
 212       /* --- Otherwise take the hash result out of line and copy it --- */
 213
 214       else {
 215         octet hash[SHA_HASHSZ];
 216         sha_done(&h, hash);
 217         memcpy(q, hash + (SHA_HASHSZ - o), o);
 218         o = 0;
 219       }
 220
 221       /* --- Step the input buffer --- */
 222
 223       STEP(d);
 224     }
 225
 226     /* --- Another pass has been done --- */
 227
 228     n--;
 229   }
 230
 231   /* --- Write out subsequent passes --- *
 232    *
 233    * The hash output has to be done offline, so this is slightly easier.
 234    */
 235
 236   while (n) {
 237     size_t o = sz;
 238
 239     while (o) {
 240       sha_ctx h;
 241       octet hash[SHA_HASHSZ];
 242       size_t n;
 243       octet *pp, *qq;
 244
 245       /* --- Hash the input buffer --- */
 246
 247       sha_init(&h);
 248       sha_hash(&h, d->p, d->sz);
 249       sha_done(&h, hash);
 250
 251       /* --- Work out how much output is wanted --- */
 252
 253       n = SHA_HASHSZ;
 254       if (n > o)
 255         n = o;
 256       o -= n;
 257
 258       /* --- XOR the data out --- */
 259
 260       for (pp = hash + (SHA_HASHSZ - n), qq = q + o;
 261            pp < hash + SHA_HASHSZ; pp++, qq++)
 262         *qq ^= *pp;
 263
 264       /* --- Step the input buffer --- */
 265
 266       STEP(d);
 267     }
 268
 269     /* --- Another pass is done --- */
 270
 271     n--;
 272   }
 273 }
 274
 275 /*----- That's all, folks -------------------------------------------------*/