5 * Generate KCDSA prime groups
7 * (c) 2006 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Header files ------------------------------------------------------*/
32 #include <mLib/macros.h>
39 /*----- Main code ---------------------------------------------------------*/
41 /* --- @dh_kcdsagen@ --- *
43 * Arguments: @dh_param *dp@ = pointer to output parameter block
44 * @unsigned ql@ = size of small factor of %$(p - 1)/2$%
45 * @unsigned pl@ = size of %$p$% in bits
46 * @unsigned flags@ = other generation flags
47 * @unsigned steps@ = number of steps to go
48 * @grand *r@ = random number source
49 * @pgen_proc *ev@ = event handler function
50 * @void *ec@ = context for the event handler
52 * Returns: @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it failed.
54 * Use: Generates a KCDSA prime group. That is, it chooses a prime
55 * %$p$%, such that $%p = 2 q v + 1$%, for primes %$q$% and
56 * %$v$%. The actual group of interest is the subgroup of order
60 int dh_kcdsagen(dh_param *dp, unsigned ql, unsigned pl,
61 unsigned flags, unsigned steps, grand *r,
62 pgen_proc *ev, void *ec)
65 pgen_simulprime sp[2];
73 /* --- First trick: find %$q$% --- */
76 x = mprand(MP_NEW, pl - ql, r, 1);
77 x = pgen("v", x, x, ev, ec,
78 steps, pgen_filter, &pf,
79 rabin_iters(pl - ql), pgen_test, &rb);
83 /* --- Second trick: find %$p$% and %$v$% --- */
86 sp[0].add = MP_ZERO; sp[0].mul = MP_ONE; sp[0].f = 0;
87 sp[1].add = MP_ONE; sp[1].mul = x; sp[1].f = PGENF_KEEP;
88 ss.step = MP_TWO; ss.v = sp; ss.n = N(sp);
89 x = mprand(MP_NEW, ql, r, 1);
90 dp->q = pgen("p", MP_NEW, x, ev, ec,
91 steps, pgen_simulstep, &ss,
92 rabin_iters(ql), pgen_simultest, &ss);
98 /* --- Third trick: find a generator --- */
100 mpmont_create(&pc.mm, dp->p);
101 mp_div(&x, 0, dp->p, dp->q);
105 dp->g = pgen("g", MP_NEW, MP_NEW, ev, ec,
106 0, prim_step, &i, 1, prim_test, &pc);
107 mpmont_destroy(&pc.mm);
114 /* --- Tidying up and going home --- */
125 /*----- That's all, folks -------------------------------------------------*/