nsz Git - epoint/blob - cmd/genpqg/genpqg.go

   1 // generate P, Q, G parameters of DSA with verifiable, deterministic algorithm
   2 package main
   3
   4 import (
   5         "crypto/dsa"
   6         "crypto/sha1"
   7         "fmt"
   8         "io"
   9         "log"
  10         "math/big"
  11 )
  12
  13 const usage = "usage: ./genpqg"
  14
  15 type prng struct {
  16         state []byte
  17 }
  18
  19 // seed is from
  20 // od -An -tx1 -N20 /dev/urandom |sed 's/^ //;s/[^ ]*/0x&,/g'
  21 var r = &prng{[]byte{
  22         0xef, 0xba, 0x22, 0x1b, 0x07, 0x2c, 0xe8, 0x2f, 0xbe, 0x20, 0x77, 0x5d, 0xd0, 0x5c, 0x33, 0xd5,
  23         0xee, 0x66, 0x27, 0x0f,
  24 }}
  25
  26 // iterated sha1 generator
  27 func (r *prng) Read(p []byte) (n int, err error) {
  28         h := sha1.New()
  29         h.Write(r.state)
  30         r.state = h.Sum(nil)
  31         n = copy(p, r.state)
  32         return
  33 }
  34
  35 // copied from crypto/dsa and slightly modified the generation of q
  36 const numMRTests = 64
  37
  38 func GenerateParameters(params *dsa.Parameters, rand io.Reader) (err error) {
  39         // This function doesn't follow FIPS 186-3 exactly in that it doesn't
  40         // use a verification seed to generate the primes. The verification
  41         // seed doesn't appear to be exported or used by other code and
  42         // omitting it makes the code cleaner.
  43
  44         L := 1024
  45         N := 160
  46         qBytes := make([]byte, N/8)
  47         pBytes := make([]byte, L/8)
  48
  49         q := new(big.Int)
  50         p := new(big.Int)
  51         rem := new(big.Int)
  52         one := new(big.Int)
  53         one.SetInt64(1)
  54
  55 GeneratePrimes:
  56         for {
  57                 // make q > 2^160 - 2^81 so sha1 sum of random bytes
  58                 // are in [1, q-1] with high probability
  59                 for i := 0; i < 10; i++ {
  60                         qBytes[i] = 0xff
  61                 }
  62                 _, err = io.ReadFull(rand, qBytes[10:])
  63                 if err != nil {
  64                         return
  65                 }
  66                 qBytes[len(qBytes)-1] |= 1
  67                 q.SetBytes(qBytes)
  68
  69                 if !big.ProbablyPrime(q, numMRTests) {
  70                         continue
  71                 }
  72
  73                 for i := 0; i < 4*L; i++ {
  74                         _, err = io.ReadFull(rand, pBytes)
  75                         if err != nil {
  76                                 return
  77                         }
  78
  79                         pBytes[len(pBytes)-1] |= 1
  80                         pBytes[0] |= 0x80
  81
  82                         p.SetBytes(pBytes)
  83                         rem.Mod(p, q)
  84                         rem.Sub(rem, one)
  85                         p.Sub(p, rem)
  86                         if p.BitLen() < L {
  87                                 continue
  88                         }
  89
  90                         if !big.ProbablyPrime(p, numMRTests) {
  91                                 continue
  92                         }
  93
  94                         params.P = p
  95                         params.Q = q
  96                         break GeneratePrimes
  97                 }
  98         }
  99
 100         h := new(big.Int)
 101         h.SetInt64(2)
 102         g := new(big.Int)
 103
 104         pm1 := new(big.Int).Sub(p, one)
 105         e := new(big.Int).Div(pm1, q)
 106
 107         for {
 108                 g.Exp(h, e, p)
 109                 if g.Cmp(one) == 0 {
 110                         h.Add(h, one)
 111                         continue
 112                 }
 113
 114                 params.G = g
 115                 return
 116         }
 117
 118         panic("unreachable")
 119 }
 120
 121 func main() {
 122         params := new(dsa.Parameters)
 123         err := GenerateParameters(params, r)
 124         if err != nil {
 125                 log.Fatal(err)
 126         }
 127         fmt.Printf("P: %X\nQ: %X\nG: %X\n", params.P, params.Q, params.G)
 128 }