3 * $Id: bbs-gen.c,v 1.1 1999/12/10 23:14:59 mdw Exp $
5 * Generate Blum integers
7 * (c) 1999 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 /*----- Revision history --------------------------------------------------*
33 * Revision 1.1 1999/12/10 23:14:59 mdw
34 * Blum-Blum-Shub generator, and Blum-Goldwasser encryption.
38 /*----- Header files ------------------------------------------------------*/
51 /*----- Main code ---------------------------------------------------------*/
53 /* --- @bbs_gen@ --- *
55 * Arguments: @bbs_params *bp@ = pointer to parameter block
56 * @mp *p, *q@ = initial numbers to search from
57 * @size_t n@ = number of attempts to make
58 * @void (*proc)(int ev, mp *m, void *p)@ = event handler
59 * @void *arg@ = argument for event handler
61 * Returns: Zero if all went well, otherwise an event code which explains
64 * Use: Finds two prime numbers %$p'$% and %$q'$% such that both are
65 * congruent to %$3 \bmod 4$%, and $(p - 1)/2$% and
66 * %$(q - 1)/2$% have no common factors. The product %$n = pq$%
67 * is eminently suitable for use as a modulus in a Blum-Blum-
68 * Shub pseudorandom bit generator.
71 int bbs_gen(bbs_params
*bp
, mp
*p
, mp
*q
, size_t n
,
72 int (*proc
)(int /*ev*/, mp */
*m*/
, void */
*p*/
), void *arg
)
77 grand
*gr
= fibrand_create(0);
82 /* --- Initialize @p@ and @q@ --- *
84 * Divide both by two, and make the results odd.
87 p
= mp_lsr(MP_NEW
, p
, 1); p
->v
[0] |= 1;
88 q
= mp_lsr(MP_NEW
, q
, 1); q
->v
[0] |= 1;
90 /* --- Set up the search for @p@ --- *
92 * I want a prime %$p$% such that %$(p - 1)/2$% has no small factors.
95 rcx
= pgen_create(&px
, p
); mp_drop(p
);
96 rcy
= pgen_muladd(&py
, &px
, 2, 1);
98 if (proc
&& (fail
= proc(BBSEV_FINDP
, 0, arg
)) != 0)
103 if (rcx
!= PGEN_COMPOSITE
&& rcy
!= PGEN_COMPOSITE
) {
104 if (rcy
!= PGEN_PRIME
) {
108 if (proc
&& (fail
= proc(BBSEV_TRYP
, py
.m
, arg
)) != 0)
110 rabin_create(&r
, py
.m
);
111 for (i
= 0; i
< 5; i
++) {
112 g
= mprand(g
, sz
, gr
, 1);
113 if ((rcy
= rabin_test(&r
, g
)) == PGEN_COMPOSITE
)
115 if (proc
&& (fail
= proc(BBSEV_PASSP
, py
.m
, arg
)) != 0)
122 if (proc
&& (fail
= proc(BBSEV_FAILP
, py
.m
, arg
)) != 0)
134 if (rcy
!= PGEN_COMPOSITE
)
137 rcx
= pgen_step(&px
, 2);
138 rcy
= pgen_step(&py
, 4);
141 if (proc
&& (fail
= proc(BBSEV_GOODP
, py
.m
, arg
)) != 0)
144 /* --- I now have a @p@ (and a %$(p - 1)/2$%) --- */
146 pp
= MP_COPY(px
.m
); pgen_destroy(&px
);
147 p
= MP_COPY(py
.m
); pgen_destroy(&py
);
149 /* --- Next trick is to generate @q@ --- *
151 * I don't care about small factors of %$(q - 1)/2$%, just that it's
152 * relatively prime to %$(p - 1)/2$%.
156 mp
*m
= mp_lsl(MP_NEW
, q
, 1);
158 rcx
= pgen_create(&px
, m
);
162 if (proc
&& (fail
= proc(BBSEV_FINDQ
, 0, arg
)) != 0)
166 if (rcx
!= PGEN_COMPOSITE
) {
169 /* --- Ensure that %$(p - 1)/2$% and %$(q - 1)/2$% are coprime --- */
171 mp_gcd(&g
, 0, 0, pp
, q
);
172 ok
= MP_CMP(g
, ==, MP_ONE
);
174 if (ok
&& rcx
!= PGEN_PRIME
) {
178 if (proc
&& (fail
= proc(BBSEV_TRYQ
, px
.m
, arg
)) != 0)
180 rabin_create(&r
, px
.m
);
181 for (i
= 0; i
< 5; i
++) {
182 g
= mprand(g
, sz
, gr
, 1);
183 if ((rcx
= rabin_test(&r
, g
)) == PGEN_COMPOSITE
)
185 if (proc
&& (fail
= proc(BBSEV_PASSQ
, px
.m
, arg
)) != 0)
192 if (proc
&& (fail
= proc(BBSEV_FAILQ
, px
.m
, arg
)) != 0)
204 if (ok
&& rcx
!= PGEN_COMPOSITE
)
208 q
= mp_add(q
, q
, MP_TWO
);
209 rcx
= pgen_step(&px
, 4);
212 if (proc
&& (fail
= proc(BBSEV_GOODQ
, px
.m
, arg
)) != 0)
224 bp
->n
= mp_mul(MP_NEW
, p
, q
);
225 gr
->ops
->destroy(gr
);
235 gr
->ops
->destroy(gr
);
244 gr
->ops
->destroy(gr
);
248 /*----- That's all, folks -------------------------------------------------*/