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 -------------------------------------------------*/