3 * $Id: pgen-safe.c,v 1.3 2000/06/17 11:52:36 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.3 2000/06/17 11:52:36 mdw
34 * Signal a pgen abort if the jump and base share a common factor.
36 * Revision 1.2 2000/02/12 18:21:03 mdw
37 * Overhaul of key management (again).
39 * Revision 1.1 1999/12/22 16:01:34 mdw
40 * Find `safe' primes (i.e., %$p = 2q + 1$%).
44 /*----- Header files ------------------------------------------------------*/
50 /*----- Main code ---------------------------------------------------------*/
52 /* --- @pgen_safestep@ --- *
54 * Steps two numbers, %$q$% and %$p = 2q + 1$%, such that neither has any
55 * small factors. %$p$% is put in the event block.
58 int pgen_safestep(int rq, pgen_event *ev, void *p)
60 pgen_safestepctx *c = p;
61 int rc = PGEN_ABORT, qrc = 0;
65 /* --- Set up the contexts --- */
68 mp *p = mp_split(MP_COPY(ev->m));
71 q = mp_lsr(MP_NEW, p, 1);
72 rc = pfilt_create(&c->p, p);
73 qrc = pfilt_create(&c->q, q);
74 mp_drop(p); mp_drop(q);
77 /* --- Step along --- */
81 rc = pfilt_step(&c->p, 4);
82 qrc = pfilt_step(&c->q, 2);
87 /* --- Tidy the toys away --- */
95 /* --- Continue stepping if necessary --- */
97 while (rc == PGEN_FAIL || qrc == PGEN_FAIL) {
98 rc = pfilt_step(&c->p, 4);
99 qrc = pfilt_step(&c->q, 2);
102 ev->m = MP_COPY(c->p.m);
108 /* --- @pgen_safejump@ --- *
110 * Jumps two numbers, %$q$% and %$p = 2q + 1$% such that neither has any
114 int pgen_safejump(int rq, pgen_event *ev, void *p)
116 pgen_safejumpctx *j = p;
117 int rc = PGEN_ABORT, qrc = 0;
121 /* --- Set up the jump contexts --- *
123 * The jump in @j.q@ is congruent to 2 (mod 4); see @strongprime_setup@.
124 * If @p@ is initially 1 (mod 4) then add @j.q@. Then double @j.q@ to
125 * ensure that the step is 0 (mod 4). Ensure that @jq@ and @q@ don't
126 * have any common factors.
133 if ((p->v[0] & 3) != 3)
134 p = mp_add(p, p, j->jq.m);
135 q = mp_lsr(MP_NEW, p, 1);
136 mp_gcd(&g, 0, 0, q, j->jq.m);
137 if (MP_CMP(g, >, MP_ONE)) {
144 rc = pfilt_create(&j->p, p);
145 pfilt_muladd(&j->jp, &j->jq, 2, 0);
146 qrc = pfilt_create(&j->q, q);
151 /* --- Step on one place --- */
155 rc = pfilt_jump(&j->p, &j->jp);
156 qrc = pfilt_jump(&j->q, &j->jq);
159 /* --- Tidy everything up --- */
162 pfilt_destroy(&j->jp);
163 pfilt_destroy(&j->p);
164 pfilt_destroy(&j->q);
168 /* --- Step on while @p@ or @q@ have small factors --- */
170 while (rc == PGEN_FAIL || qrc == PGEN_FAIL) {
171 rc = pfilt_jump(&j->p, &j->jp);
172 qrc = pfilt_jump(&j->q, &j->jq);
174 ev->m = MP_COPY(j->p.m);
180 /* --- @pgen_safetest@ --- *
182 * Applies Rabin-Miller tests to %$p$% and %$q$%.
185 int pgen_safetest(int rq, pgen_event *ev, void *p)
187 pgen_safetestctx *c = p;
192 rabin_create(&c->q, c->c.q.m);
193 rabin_create(&c->p, c->c.p.m);
197 mp *m = mprand_range(MP_NEW, c->c.q.m, ev->r, 0);
198 rc = rabin_test(&c->p, m);
200 rc = rabin_test(&c->q, m);
204 rabin_destroy(&c->q);
205 rabin_destroy(&c->p);
211 /*----- That's all, folks -------------------------------------------------*/