#include "os.h"
#include <mp.h>
#include <libsec.h>

DSAsig*
dsasign(DSApriv *priv, mpint *m)
{
	DSApub *pub = &priv->pub;
	DSAsig *sig;
	mpint *qm1, *k, *kinv, *r, *s;
	mpint *q = pub->q, *p = pub->p, *alpha = pub->alpha;
	int qlen = mpsignif(q);

	qm1 = mpnew(0);
	kinv = mpnew(0);
	r = mpnew(0);
	s = mpnew(0);
	k = mpnew(0);
	mpsub(pub->q, mpone, qm1);

	/* find a k that has an inverse mod q */
	while(1){
		mprand(qlen, genrandom, k);
		if((mpcmp(mpone, k) > 0) || (mpcmp(k, pub->q) >= 0))
			continue;
		mpextendedgcd(k, q, r, kinv, s);
		if(mpcmp(r, mpone) != 0)
			sysfatal("dsasign: pub->q not prime");
		break;
	}

  	/* make kinv positive */
	mpmod(kinv, pub->q, kinv);

	/* r = ((alpha**k) mod p) mod q */
	mpexp(alpha, k, p, r);
	mpmod(r, q, r);

	/* s = (kinv*(m + ar)) mod q */
	mpmul(r, priv->secret, s);
	mpadd(s, m, s);
	mpmul(s, kinv, s);
	mpmod(s, q, s);

	sig = dsasigalloc();
	sig->r = r;
	sig->s = s;
	mpfree(qm1);
	mpfree(k);
	mpfree(kinv);
	return sig;
}