1 #include "os.h"
2 #include <mp.h>
3 #include <libsec.h>
4 
5 DSAsig*
6 dsasign(DSApriv *priv, mpint *m)
7 {
8 	DSApub *pub = &priv->pub;
9 	DSAsig *sig;
10 	mpint *qm1, *k, *kinv, *r, *s;
11 	mpint *q = pub->q, *p = pub->p, *alpha = pub->alpha;
12 	int qlen = mpsignif(q);
13 
14 	qm1 = mpnew(0);
15 	kinv = mpnew(0);
16 	r = mpnew(0);
17 	s = mpnew(0);
18 	k = mpnew(0);
19 	mpsub(pub->q, mpone, qm1);
20 
21 	/* find a k that has an inverse mod q */
22 	while(1){
23 		mprand(qlen, genrandom, k);
24 		if((mpcmp(mpone, k) > 0) || (mpcmp(k, pub->q) >= 0))
25 			continue;
26 		mpextendedgcd(k, q, r, kinv, s);
27 		if(mpcmp(r, mpone) != 0)
28 			sysfatal("dsasign: pub->q not prime");
29 		break;
30 	}
31 
32   	/* make kinv positive */
33 	mpmod(kinv, pub->q, kinv);
34 
35 	/* r = ((alpha**k) mod p) mod q */
36 	mpexp(alpha, k, p, r);
37 	mpmod(r, q, r);
38 
39 	/* s = (kinv*(m + ar)) mod q */
40 	mpmul(r, priv->secret, s);
41 	mpadd(s, m, s);
42 	mpmul(s, kinv, s);
43 	mpmod(s, q, s);
44 
45 	sig = dsasigalloc();
46 	sig->r = r;
47 	sig->s = s;
48 	mpfree(qm1);
49 	mpfree(k);
50 	mpfree(kinv);
51 	return sig;
52 }