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];
69 mp
*x
= MP_NEW
, *t
= MP_NEW
;
71 /* --- First trick: find %$v$% --- */
75 x
= mprand(x
, pl
- ql
- 1, r
, 1);
76 x
= pgen("v", x
, x
, ev
, ec
,
77 steps
, pgen_filter
, &pf
,
78 rabin_iters(pl
- ql
), pgen_test
, &rb
);
82 /* --- Second trick: find %$p$% and %$q$% --- */
85 sp
[0].add
= MP_ZERO
; sp
[0].mul
= MP_ONE
; sp
[0].f
= 0;
86 sp
[1].add
= MP_ONE
; sp
[1].mul
= x
; sp
[1].f
= PGENF_KEEP
; x
= MP_NEW
;
87 ss
.step
= MP_TWO
; ss
.v
= sp
; ss
.n
= N(sp
);
89 x
= mprand(x
, ql
, r
, 1);
90 t
= mp_mul(t
, x
, sp
[1].mul
);
91 } while (mp_bits(t
) != pl
);
92 dp
->q
= pgen("p", MP_NEW
, x
, ev
, ec
,
93 steps
, pgen_simulstep
, &ss
,
94 rabin_iters(ql
), pgen_simultest
, &ss
);
99 if (mp_bits(dp
->q
) != ql
|| mp_bits(dp
->p
) != pl
) {
100 if (steps
) goto fail_1
;
106 /* --- Third trick: find a generator --- */
108 mpmont_create(&pc
.mm
, dp
->p
);
109 mp_div(&x
, 0, dp
->p
, dp
->q
);
113 dp
->g
= pgen("g", MP_NEW
, MP_NEW
, ev
, ec
,
114 0, prim_step
, &i
, 1, prim_test
, &pc
);
115 mpmont_destroy(&pc
.mm
);
122 /* --- Tidying up and going home --- */
134 /*----- That's all, folks -------------------------------------------------*/