sys/src/libsec/port/dsaprimes.c

   1 #include "os.h"
   2 #include <mp.h>
   3 #include <libsec.h>
   4
   5 // NIST algorithm for generating DSA primes
   6 // Menezes et al (1997) Handbook of Applied Cryptography, p.151
   7 // q is a 160-bit prime;  p is a 1024-bit prime;  q divides p-1
   8
   9 // arithmetic on unsigned ints mod 2**160, represented
  10 //    as 20-byte, little-endian uchar array
  11
  12 static void
  13 Hrand(uchar *s)
  14 {
  15         ulong *u = (ulong*)s;
  16         *u++ = fastrand();
  17         *u++ = fastrand();
  18         *u++ = fastrand();
  19         *u++ = fastrand();
  20         *u = fastrand();
  21 }
  22
  23 static void
  24 Hincr(uchar *s)
  25 {
  26         int i;
  27         for(i=0; i<20; i++)
  28                 if(++s[i]!=0)
  29                         break;
  30 }
  31
  32 // this can run for quite a while;  be patient
  33 void
  34 DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])
  35 {
  36         int i, j, k, n = 6, b = 63;
  37         uchar s[SHA1dlen], Hs[SHA1dlen], Hs1[SHA1dlen], sj[SHA1dlen], sjk[SHA1dlen];
  38         mpint *two1023, *mb, *Vk, *W, *X, *q2;
  39
  40         two1023 = mpnew(1024);
  41         mpleft(mpone, 1023, two1023);
  42         mb = mpnew(0);
  43         mpleft(mpone, b, mb);
  44         W = mpnew(1024);
  45         Vk = mpnew(1024);
  46         X = mpnew(0);
  47         q2 = mpnew(0);
  48 forever:
  49         do{
  50                 Hrand(s);
  51                 memcpy(sj, s, 20);
  52                 sha1(s, 20, Hs, 0);
  53                 Hincr(sj);
  54                 sha1(sj, 20, Hs1, 0);
  55                 for(i=0; i<20; i++)
  56                         Hs[i] ^= Hs1[i];
  57                 Hs[0] |= 1;
  58                 Hs[19] |= 0x80;
  59                 letomp(Hs, 20, q);
  60         }while(!probably_prime(q, 18));
  61         if(seed != nil) // allow skeptics to confirm computation
  62                 memmove(seed, s, SHA1dlen);
  63         i = 0;
  64         j = 2;
  65         Hincr(sj);
  66         mpleft(q, 1, q2);
  67         while(i<4096){
  68                 memcpy(sjk, sj, 20);
  69                 for(k=0; k <= n; k++){
  70                         sha1(sjk, 20, Hs, 0);
  71                         letomp(Hs, 20, Vk);
  72                         if(k == n)
  73                                 mpmod(Vk, mb, Vk);
  74                         mpleft(Vk, 160*k, Vk);
  75                         mpadd(W, Vk, W);
  76                         Hincr(sjk);
  77                 }
  78                 mpadd(W, two1023, X);
  79                 mpmod(X, q2, W);
  80                 mpsub(W, mpone, W);
  81                 mpsub(X, W, p);
  82                 if(mpcmp(p, two1023)>=0 && probably_prime(p, 5))
  83                         goto done;
  84                 i += 1;
  85                 j += n+1;
  86                 for(k=0; k<n+1; k++)
  87                         Hincr(sj);
  88         }
  89         goto forever;
  90 done:
  91         mpfree(q2);
  92         mpfree(X);
  93         mpfree(Vk);
  94         mpfree(W);
  95         mpfree(mb);
  96         mpfree(two1023);
  97 }