chiark / gitweb /
math/t/{mpx,mpmont}: Add some extra tests for flushing out `mul4' bugs.
[catacomb] / pub / dh-gen.c
CommitLineData
052b36d0 1/* -*-c-*-
052b36d0 2 *
3 * Generate Diffie-Hellman parameters
4 *
5 * (c) 1999 Straylight/Edgeware
6 */
7
45c0fd36 8/*----- Licensing notice --------------------------------------------------*
052b36d0 9 *
10 * This file is part of Catacomb.
11 *
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.
45c0fd36 16 *
052b36d0 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.
45c0fd36 21 *
052b36d0 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,
25 * MA 02111-1307, USA.
26 */
27
052b36d0 28/*----- Header files ------------------------------------------------------*/
29
ed229313
MW
30#include <mLib/macros.h>
31
052b36d0 32#include "dh.h"
33#include "grand.h"
34#include "mp.h"
35#include "mpmont.h"
36#include "mprand.h"
37#include "pfilt.h"
38#include "pgen.h"
39#include "prim.h"
40#include "rabin.h"
41
42/*----- Main code ---------------------------------------------------------*/
43
44/* --- @dh_gen@ --- *
45 *
46 * Arguments: @dh_param *dp@ = pointer to output parameter block
47 * @unsigned ql@ = length of %$q$% in bits, or zero
48 * @unsigned pl@ = length of %$p$% in bits
49 * @unsigned steps@ = number of steps to go
50 * @grand *r@ = random number source
51 * @pgen_proc *event@ = event handler function
52 * @void *ectx@ = argument for the event handler
53 *
54 * Returns: @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't.
55 *
56 * Use: Generates Diffie-Hellman parameters.
57 *
58 * The parameters are a prime %$q$%, relatively small, and a
59 * large prime %$p = kq + 1$% for some %$k$%, together with a
60 * generator %$g$% of the cyclic subgroup of order %$q$%. These
61 * are actually the same as the DSA parameter set, but the
62 * generation algorithm is different. Also, if @ql@ is zero,
63 * this algorithm forces %$k = 2$%, and chooses %$g = 4$%. Make
64 * sure you have something interesting to do if you choose this
65 * option.
66 */
67
68int dh_gen(dh_param *dp, unsigned ql, unsigned pl, unsigned steps, grand *r,
69 pgen_proc *event, void *ectx)
70{
71 /* --- If @ql@ is zero, do the time consuming safe-prime thing --- */
72
73 if (!ql) {
ed229313
MW
74 pgen_simulprime sp[2];
75 pgen_simulctx ss;
052b36d0 76
ed229313
MW
77 mp *m = mprand(MP_NEW, pl - 1, r, 1);
78 ss.step = MP_TWO;
79 sp[0].mul = MP_ONE; sp[0].add = MP_ZERO; sp[0].f = 0;
80 sp[1].mul = MP_TWO; sp[1].add = MP_ONE; sp[1].f = PGENF_KEEP;
81 ss.v = sp; ss.n = N(sp);
82 dp->q = pgen("p", MP_NEW, m, event, ectx, steps, pgen_simulstep, &ss,
83 rabin_iters(pl), pgen_simultest, &ss);
052b36d0 84 mp_drop(m);
ed229313
MW
85 if (!dp->q) {
86 mp_drop(sp[1].u.x);
052b36d0 87 return (PGEN_ABORT);
ed229313
MW
88 }
89 dp->p = sp[1].u.x;
052b36d0 90 dp->g = MP_FOUR;
91 return (PGEN_DONE);
92 }
93
94 /* --- Otherwise the job is much simpler --- *
95 *
96 * But doesn't look it...
97 */
98
99 else {
100 pgen_filterctx c;
101 pgen_jumpctx j;
102 rabin rb;
103 prim_ctx p;
104 int i;
105 mp *m = MP_NEW;
106 mp *x, *y;
107
108 /* --- Generate @q@ first --- */
109
110 c.step = 2;
111 m = mprand(MP_NEW, ql, r, 1);
112 dp->q = pgen("q", MP_NEW, m, event, ectx, steps, pgen_filter, &c,
113 rabin_iters(ql), pgen_test, &rb);
114 if (!dp->q)
115 goto fail_q;
116
117 /* --- Now pick a suitable @p@ --- */
118
119 m = mp_lsl(m, dp->q, 1);
120 x = mprand(MP_NEW, pl, r, 0);
121 y = MP_NEW; mp_div(0, &y, x, m);
122 x = mp_sub(x, x, y);
123 x = mp_add(x, x, MP_ONE);
124 mp_drop(y);
125 pfilt_create(&c.f, m);
126 j.j = &c.f;
127 dp->p = pgen("p", MP_NEW, x, event, ectx, steps, pgen_jump, &j,
128 rabin_iters(pl), pgen_test, &rb);
129 pfilt_destroy(&c.f);
130 mp_drop(x);
131 if (!dp->p)
132 goto fail_p;
133
134 /* --- And finally a suitable @g@ --- */
135
136 mpmont_create(&p.mm, dp->p);
137 mp_div(&m, 0, dp->p, dp->q);
138 i = 0;
f621db36 139 p.exp = m;
052b36d0 140 p.n = 0;
141 dp->g = pgen("g", MP_NEW, MP_NEW, event, ectx, 0, prim_step, &i,
142 1, prim_test, &p);
143 mpmont_destroy(&p.mm);
144 if (!dp->g)
145 goto fail_g;
146 mp_drop(m);
147 return (PGEN_DONE);
148
149 /* --- Tidy up --- */
150
151 fail_g:
152 mp_drop(dp->q);
153 fail_q:
154 mp_drop(dp->p);
155 fail_p:
156 mp_drop(m);
157 return (PGEN_ABORT);
158 }
159}
160
161/*----- That's all, folks -------------------------------------------------*/