// 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)
}