- {
- mp *q2 = mp_lsl(MP_NEW, q, 1);
- mp *ll = mp_lsl(MP_NEW, MP_ONE, l * 8 - 1);
- unsigned n = l / SHA_HASHSZ, b = l % SHA_HASHSZ;
- size_t psz = SHA_HASHSZ * (n + 1);
- octet *pbuf = xmalloc(psz);
- sha_ctx c;
- unsigned i, j;
-
- /* --- Fiddle with the leftover bytes count --- */
-
- b = SHA_HASHSZ - b;
-
- /* --- Go round 4096 times trying different @p@ values --- */
-
- p = MP_NEW;
- for (j = 0; j < 4096; j++) {
-
- /* --- Build a prospective value of @p@ --- */
-
- {
- octet *pp = pbuf + SHA_HASHSZ * n;
-
- for (i = 0; i <= n; i++) {
- mpx_uaddn(s->v, s->vl, 1);
- mp_storeb(s, sbuf, sz);
- sha_init(&c);
- sha_hash(&c, sbuf, sz);
- sha_done(&c, pp);
- pp -= SHA_HASHSZ;
- }
-
- pbuf[b] &= 0x7f;
- p = mp_loadb(p, pbuf + b, psz - b);
- p = mp_add(p, p, ll);
- }
-
- /* --- Adjust @p@ so that %$p \bmod 2q = 1$% --- */
-
- {
- mp *c = MP_NEW;
- mp_div(0, &c, p, q2);
- c = mp_sub(c, c, MP_ONE);
- p = mp_sub(p, p, c);
- mp_drop(c);
- }
-
- /* --- Check that @p@ is large enough --- */
-
- if (MP_CMP(p, <, ll))
- continue;
-
- /* --- Run a simple primality test --- */
-
- {
- pgen pg;
- int rc = pgen_create(&pg, p);
- pgen_destroy(&pg);
- if (rc == PGEN_COMPOSITE)
- continue;
- }
-
- /* --- Run the Rabin-Miller test --- */
-
- {
- rabin r;
- mp *g = MP_NEW;
-
- rabin_create(&r, p);
- if (proc && (fail = proc(DSAEV_TRYP, p, arg)) != 0)
- break;
- for (i = 0; i < 5; i++) {
- g = mprand(g, 8 * (psz - b), gr, 1);
- if (rabin_test(&r, g) == PGEN_COMPOSITE)
- break;
- if (proc && (fail = proc(DSAEV_PASSP, p, arg)) != 0)
- break;
- }
- mp_drop(g);
- rabin_destroy(&r);
- if (fail)
- break;
- if (i < 5) {
- if (proc && (fail = proc(DSAEV_FAILP, p, arg)) != 0)
- break;
- continue;
- }
- }
-
- /* --- It worked! --- */
-
- if (proc)
- fail = proc(DSAEV_GOODP, p, arg);
- if (proc && !fail)
- fail = proc(DSAEV_FINDG, 0, arg);
- break;
- }