tdsaprimes.c - plan9port - [fork] Plan 9 from user space
  HTML git clone git://src.adamsgaard.dk/plan9port
   DIR Log
   DIR Files
   DIR Refs
   DIR README
   DIR LICENSE
       ---
       tdsaprimes.c (1904B)
       ---
            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         uint32 *u = (uint32*)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 }