dsa pqg param generation

diff --git a/cmd/genpqg/Makefile b/cmd/genpqg/Makefile
new file mode 100644 (file)
index 0000000..345a59d
--- /dev/null
+++ b/cmd/genpqg/Makefile
@@ -0,0 +1,7 @@
+include $(GOROOT)/src/Make.inc
+
+TARG=genpqg
+GOFILES=\
+       genpqg.go
+
+include $(GOROOT)/src/Make.cmd

diff --git a/cmd/genpqg/genpqg.go b/cmd/genpqg/genpqg.go
new file mode 100644 (file)
index 0000000..0bd80e3
--- /dev/null
+++ b/cmd/genpqg/genpqg.go
@@ -0,0 +1,128 @@
+// generate P, Q, G parameters of DSA with verifiable, deterministic algorithm
+package main
+
+import (
+       "crypto/dsa"
+       "crypto/sha1"
+       "fmt"
+       "io"
+       "log"
+       "math/big"
+)
+
+const usage = "usage: ./genpqg"
+
+type prng struct {
+       state []byte
+}
+
+// seed is from
+// od -An -tx1 -N20 /dev/urandom |sed 's/^ //;s/[^ ]*/0x&,/g'
+var r = &prng{[]byte{
+       0xef, 0xba, 0x22, 0x1b, 0x07, 0x2c, 0xe8, 0x2f, 0xbe, 0x20, 0x77, 0x5d, 0xd0, 0x5c, 0x33, 0xd5,
+       0xee, 0x66, 0x27, 0x0f,
+}}
+
+// iterated sha1 generator
+func (r *prng) Read(p []byte) (n int, err error) {
+       h := sha1.New()
+       h.Write(r.state)
+       r.state = h.Sum()
+       n = copy(p, r.state)
+       return
+}
+
+// copied from crypto/dsa and slightly modified the generation of q
+const numMRTests = 64
+
+func GenerateParameters(params *dsa.Parameters, rand io.Reader) (err error) {
+       // This function doesn't follow FIPS 186-3 exactly in that it doesn't
+       // use a verification seed to generate the primes. The verification
+       // seed doesn't appear to be exported or used by other code and
+       // omitting it makes the code cleaner.
+
+       L := 1024
+       N := 160
+       qBytes := make([]byte, N/8)
+       pBytes := make([]byte, L/8)
+
+       q := new(big.Int)
+       p := new(big.Int)
+       rem := new(big.Int)
+       one := new(big.Int)
+       one.SetInt64(1)
+
+GeneratePrimes:
+       for {
+               // make q > 2^160 - 2^81 so sha1 sum of random bytes
+               // are in [1, q-1] with high probability
+               for i := 0; i < 10; i++ {
+                       qBytes[i] = 0xff
+               }
+               _, err = io.ReadFull(rand, qBytes[10:])
+               if err != nil {
+                       return
+               }
+               qBytes[len(qBytes)-1] |= 1
+               q.SetBytes(qBytes)
+
+               if !big.ProbablyPrime(q, numMRTests) {
+                       continue
+               }
+
+               for i := 0; i < 4*L; i++ {
+                       _, err = io.ReadFull(rand, pBytes)
+                       if err != nil {
+                               return
+                       }
+
+                       pBytes[len(pBytes)-1] |= 1
+                       pBytes[0] |= 0x80
+
+                       p.SetBytes(pBytes)
+                       rem.Mod(p, q)
+                       rem.Sub(rem, one)
+                       p.Sub(p, rem)
+                       if p.BitLen() < L {
+                               continue
+                       }
+
+                       if !big.ProbablyPrime(p, numMRTests) {
+                               continue
+                       }
+
+                       params.P = p
+                       params.Q = q
+                       break GeneratePrimes
+               }
+       }
+
+       h := new(big.Int)
+       h.SetInt64(2)
+       g := new(big.Int)
+
+       pm1 := new(big.Int).Sub(p, one)
+       e := new(big.Int).Div(pm1, q)
+
+       for {
+               g.Exp(h, e, p)
+               if g.Cmp(one) == 0 {
+                       h.Add(h, one)
+                       continue
+               }
+
+               params.G = g
+               return
+       }
+
+       panic("unreachable")
+}
+
+func main() {
+       params := new(dsa.Parameters)
+       err := GenerateParameters(params, r)
+       if err != nil {
+               log.Fatal(err)
+       }
+       fmt.Printf("P: %X\nQ: %X\nG: %X\n", params.P, params.Q, params.G)
+}

diff --git a/cmd/genpqg/pqg b/cmd/genpqg/pqg
new file mode 100644 (file)
index 0000000..baaccc0
--- /dev/null
+++ b/cmd/genpqg/pqg
@@ -0,0 +1,3 @@
+P: A4D2B9575C25F0E622B8694387128A793E1AD27D12FFF4B5BA11A37CEFD31C935BCBB0A944581A6E6DA12986FCBA9D666607D71D365C286B9BCB57F6D938BE74982B7D770CE438F03B0A20ABA02E5691458C39D96E6E86AE564176ED1A6DFBAFB6EE7674CC5EDCF9FEB6158471FB3FAB53BA1CE1BA64C5626B9E8585FCEF5D31
+Q: FFFFFFFFFFFFFFFFFFFF254EAF9E7916D607AAAF
+G: 7EA5C898777BE4BB29DCDC47289E718F7274C9CD7E570D3D552F3B3EE43C3DEF7BA68E57786926520CCAC71DBA13F37C4064395D5AF3334A04ABD8CED5E7FF476C661953936E8ADDE96A39D8C4AC1080A2BE3FE863A24B08BD43827E54AFADA72433704EA3C12E50E5BD08C130C68A1402FC20DA79CFE0DE931C414348D32B10