3 * $Id: pgen-safe.c,v 1.4 2000/07/03 18:09:27 mdw Exp $
5 * Safe prime generation
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 --------------------------------------------------*
32 * $Log: pgen-safe.c,v $
33 * Revision 1.4 2000/07/03 18:09:27 mdw
34 * Bug fix to the GCD check. With any luck, this is the last of these to
35 * need nailing to the wall.
37 * Revision 1.3 2000/06/17 11:52:36 mdw
38 * Signal a pgen abort if the jump and base share a common factor.
40 * Revision 1.2 2000/02/12 18:21:03 mdw
41 * Overhaul of key management (again).
43 * Revision 1.1 1999/12/22 16:01:34 mdw
44 * Find `safe' primes (i.e., %$p = 2q + 1$%).
48 /*----- Header files ------------------------------------------------------*/
54 /*----- Main code ---------------------------------------------------------*/
56 /* --- @pgen_safestep@ --- *
58 * Steps two numbers, %$q$% and %$p = 2q + 1$%, such that neither has any
59 * small factors. %$p$% is put in the event block.
62 int pgen_safestep(int rq
, pgen_event
*ev
, void *p
)
64 pgen_safestepctx
*c
= p
;
65 int rc
= PGEN_ABORT
, qrc
= 0;
69 /* --- Set up the contexts --- */
72 mp
*p
= mp_split(MP_COPY(ev
->m
));
75 q
= mp_lsr(MP_NEW
, p
, 1);
76 rc
= pfilt_create(&c
->p
, p
);
77 qrc
= pfilt_create(&c
->q
, q
);
78 mp_drop(p
); mp_drop(q
);
81 /* --- Step along --- */
85 rc
= pfilt_step(&c
->p
, 4);
86 qrc
= pfilt_step(&c
->q
, 2);
91 /* --- Tidy the toys away --- */
99 /* --- Continue stepping if necessary --- */
101 while (rc
== PGEN_FAIL
|| qrc
== PGEN_FAIL
) {
102 rc
= pfilt_step(&c
->p
, 4);
103 qrc
= pfilt_step(&c
->q
, 2);
106 ev
->m
= MP_COPY(c
->p
.m
);
112 /* --- @pgen_safejump@ --- *
114 * Jumps two numbers, %$q$% and %$p = 2q + 1$% such that neither has any
118 int pgen_safejump(int rq
, pgen_event
*ev
, void *p
)
120 pgen_safejumpctx
*j
= p
;
121 int rc
= PGEN_ABORT
, qrc
= 0;
125 /* --- Set up the jump contexts --- *
127 * The jump in @j.q@ is congruent to 2 (mod 4); see @strongprime_setup@.
128 * If @p@ is initially 1 (mod 4) then add @j.q@. Then double @j.q@ to
129 * ensure that the step is 0 (mod 4). Ensure that @jq@ and @q@ don't
130 * have any common factors.
137 if ((p
->v
[0] & 3) != 3)
138 p
= mp_add(p
, p
, j
->jq
.m
);
139 q
= mp_lsr(MP_NEW
, p
, 1);
140 mp_gcd(&g
, 0, 0, p
, j
->jq
.m
);
141 if (MP_CMP(g
, >, MP_ONE
)) {
148 rc
= pfilt_create(&j
->p
, p
);
149 pfilt_muladd(&j
->jp
, &j
->jq
, 2, 0);
150 qrc
= pfilt_create(&j
->q
, q
);
155 /* --- Step on one place --- */
159 rc
= pfilt_jump(&j
->p
, &j
->jp
);
160 qrc
= pfilt_jump(&j
->q
, &j
->jq
);
163 /* --- Tidy everything up --- */
166 pfilt_destroy(&j
->jp
);
167 pfilt_destroy(&j
->p
);
168 pfilt_destroy(&j
->q
);
172 /* --- Step on while @p@ or @q@ have small factors --- */
174 while (rc
== PGEN_FAIL
|| qrc
== PGEN_FAIL
) {
175 rc
= pfilt_jump(&j
->p
, &j
->jp
);
176 qrc
= pfilt_jump(&j
->q
, &j
->jq
);
178 ev
->m
= MP_COPY(j
->p
.m
);
184 /* --- @pgen_safetest@ --- *
186 * Applies Rabin-Miller tests to %$p$% and %$q$%.
189 int pgen_safetest(int rq
, pgen_event
*ev
, void *p
)
191 pgen_safetestctx
*c
= p
;
196 rabin_create(&c
->q
, c
->c
.q
.m
);
197 rabin_create(&c
->p
, c
->c
.p
.m
);
201 mp
*m
= mprand_range(MP_NEW
, c
->c
.q
.m
, ev
->r
, 0);
202 rc
= rabin_test(&c
->p
, m
);
204 rc
= rabin_test(&c
->q
, m
);
208 rabin_destroy(&c
->q
);
209 rabin_destroy(&c
->p
);
215 /*----- That's all, folks -------------------------------------------------*/