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