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

   1 /* -*-c-*-
   2  *
   3  * $Id: dsarand.c,v 1.2 2000/07/02 15:21:20 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 AUTHORS 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.2  2000/07/02 15:21:20  mdw
  54  * Fix licence text.
  55  *
  56  * Revision 1.1  2000/05/21 11:28:30  mdw
  57  * Initial check-in.
  58  *
  59  * --- Past lives (Catacomb) --- *
  60  *
  61  * Revision 1.1  1999/12/22 15:53:12  mdw
  62  * Random number generator for finding DSA parameters.
  63  *
  64  */
  65
  66 /*----- Header files ------------------------------------------------------*/
  67
  68 #include <stdio.h>
  69 #include <stdlib.h>
  70 #include <string.h>
  71
  72 #include "bits.h"
  73 #include "dsarand.h"
  74 #include "sha.h"
  75
  76 /*----- Main code ---------------------------------------------------------*/
  77
  78 /* --- @STEP@ --- *
  79  *
  80  * Arguments:   @dsarand *d@ = pointer to context
  81  *
  82  * Use:         Increments the buffer by one, interpreting it as a big-endian
  83  *              integer.  Carries outside the integer are discarded.
  84  */
  85
  86 #define STEP(d) do {                                                    \
  87   dsarand *_d = (d);                                                    \
  88   octet *_p = _d->p;                                                    \
  89   octet *_q = _p + _d->sz;                                              \
  90   unsigned _c = 1;                                                      \
  91   while (_c && _q > _p) {                                               \
  92     _c += *--_q;                                                        \
  93     *_q = U8(_c);                                                       \
  94     _c >>= 8;                                                           \
  95   }                                                                     \
  96 } while (0)
  97
  98 /* --- @dsarand_init@ --- *
  99  *
 100  * Arguments:   @dsarand *d@ = pointer to context
 101  *              @const void *p@ = pointer to seed buffer
 102  *              @size_t sz@ = size of the buffer
 103  *
 104  * Returns:     ---
 105  *
 106  * Use:         Initializes a DSA random number generator.
 107  */
 108
 109 void dsarand_init(dsarand *d, const void *p, size_t sz)
 110 {
 111   if ((d->p = malloc(sz)) == 0) {
 112     fputs("Out of memory in dsarand_init!\n", stderr);
 113     exit(EXIT_FAILURE);
 114   }
 115   d->sz = sz;
 116   d->passes = 1;
 117   if (p)
 118     memcpy(d->p, p, sz);
 119 }
 120
 121 /* --- @dsarand_reseed@ --- *
 122  *
 123  * Arguments:   @dsarand *d@ = pointer to context
 124  *              @const void *p@ = pointer to seed buffer
 125  *              @size_t sz@ = size of the buffer
 126  *
 127  * Returns:     ---
 128  *
 129  * Use:         Initializes a DSA random number generator.
 130  */
 131
 132 void dsarand_reseed(dsarand *d, const void *p, size_t sz)
 133 {
 134   free(d->p);
 135   if ((d->p = malloc(sz)) != 0) {
 136     fputs("Out of memory in dsarand_init!\n", stderr);
 137     exit(EXIT_FAILURE);
 138   }
 139   d->sz = sz;
 140   d->passes = 1;
 141   if (p)
 142     memcpy(d->p, p, sz);
 143 }
 144
 145 /* --- @dsarand_destroy@ --- *
 146  *
 147  * Arguments:   @dsarand *d@ = pointer to context
 148  *
 149  * Returns:     ---
 150  *
 151  * Use:         Disposes of a DSA random number generation context.
 152  */
 153
 154 void dsarand_destroy(dsarand *d)
 155 {
 156   free(d->p);
 157 }
 158
 159 /* --- @dsarand_fill@ --- *
 160  *
 161  * Arguments:   @dsarand *d@ = pointer to context
 162  *              @void *p@ = pointer to output buffer
 163  *              @size_t sz@ = size of output buffer
 164  *
 165  * Returns:     ---
 166  *
 167  * Use:         Fills an output buffer with pseudorandom data.
 168  *
 169  *              Let %$p$% be the numerical value of the input buffer, and let
 170  *              %$b$% be the number of bytes required.  Let
 171  *              %$z = \lceil b / 20 \rceil$% be the number of SHA outputs
 172  *              required.  Then the output of pass %$n$% is
 173  *
 174  *                %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$%
 175  *                                                      %${} \bmod 2^{8b}$%
 176  *
 177  *              and the actual result in the output buffer is the XOR of all
 178  *              of the output passes.
 179  *
 180  *              The DSA procedure for choosing @q@ involves two passes with
 181  *              %$z = 1$%; the procedure for choosing @p@ involves one pass
 182  *              with larger %$z$%.  This generalization of the DSA generation
 183  *              procedure is my own invention but it seems relatively sound.
 184  */
 185
 186 void dsarand_fill(dsarand *d, void *p, size_t sz)
 187 {
 188   octet *q = p;
 189   unsigned n = d->passes;
 190
 191   /* --- Write out the first pass --- *
 192    *
 193    * This can write directly to the output buffer, so it's done differently
 194    * from the latter passes.
 195    */
 196
 197   {
 198     size_t o = sz;
 199
 200     while (o) {
 201       sha_ctx h;
 202
 203       /* --- Hash the input buffer --- */
 204
 205       sha_init(&h);
 206       sha_hash(&h, d->p, d->sz);
 207
 208       /* --- If enough space, extract the hash output directly --- */
 209
 210       if (o >= SHA_HASHSZ) {
 211         o -= SHA_HASHSZ;
 212         sha_done(&h, q + o);
 213       }
 214
 215       /* --- Otherwise take the hash result out of line and copy it --- */
 216
 217       else {
 218         octet hash[SHA_HASHSZ];
 219         sha_done(&h, hash);
 220         memcpy(q, hash + (SHA_HASHSZ - o), o);
 221         o = 0;
 222       }
 223
 224       /* --- Step the input buffer --- */
 225
 226       STEP(d);
 227     }
 228
 229     /* --- Another pass has been done --- */
 230
 231     n--;
 232   }
 233
 234   /* --- Write out subsequent passes --- *
 235    *
 236    * The hash output has to be done offline, so this is slightly easier.
 237    */
 238
 239   while (n) {
 240     size_t o = sz;
 241
 242     while (o) {
 243       sha_ctx h;
 244       octet hash[SHA_HASHSZ];
 245       size_t n;
 246       octet *pp, *qq;
 247
 248       /* --- Hash the input buffer --- */
 249
 250       sha_init(&h);
 251       sha_hash(&h, d->p, d->sz);
 252       sha_done(&h, hash);
 253
 254       /* --- Work out how much output is wanted --- */
 255
 256       n = SHA_HASHSZ;
 257       if (n > o)
 258         n = o;
 259       o -= n;
 260
 261       /* --- XOR the data out --- */
 262
 263       for (pp = hash + (SHA_HASHSZ - n), qq = q + o;
 264            pp < hash + SHA_HASHSZ; pp++, qq++)
 265         *qq ^= *pp;
 266
 267       /* --- Step the input buffer --- */
 268
 269       STEP(d);
 270     }
 271
 272     /* --- Another pass is done --- */
 273
 274     n--;
 275   }
 276 }
 277
 278 /*----- That's all, folks -------------------------------------------------*/