3 * RSA parameter generation
5 * (c) 1999 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/dstr.h>
37 #include "strongprime.h"
39 /*----- Main code ---------------------------------------------------------*/
41 /* --- @rsa_gen@, @rsa_gen_e --- *
43 * Arguments: @rsa_priv *rp@ = pointer to block to be filled in
44 * @unsigned nbits@ = required modulus size in bits
45 * @mp *e@ = public exponent
46 * @grand *r@ = random number source
47 * @unsigned n@ = number of attempts to make
48 * @pgen_proc *event@ = event handler function
49 * @void *ectx@ = argument for the event handler
51 * Returns: Zero if all went well, nonzero otherwise.
53 * Use: Constructs a pair of strong RSA primes and other useful RSA
54 * parameters. A small encryption exponent is chosen if
58 static int genprime(mp
**pp
, mp
**dd
, const char *name
,
59 unsigned nbits
, mp
*e
,
60 grand
*r
, unsigned nsteps
, pgen_proc
*event
, void *ectx
)
62 pgen_jumpctx jctx
; pfilt j
;
63 mp
*p
= MP_NEWSEC
, *t
= MP_NEW
, *u
= MP_NEW
;
69 /* Find a start position for the search. */
70 p
= strongprime_setup(name
, p
, &j
, nbits
, r
, nsteps
, event
, ectx
);
73 /* Special handling for e = 3. */
74 if (MP_EQ(e
, MP_THREE
)) {
75 /* We must have p == 2 (mod 3): if p == 0 (mod 3) then p is not prime; if
76 * p == 1 (mod 3) then e|(p - 1). So fiddle the start position and jump
77 * context to allow for this.
80 /* Figure out the residues of the start position and jump. */
81 mp_div(0, &t
, p
, MP_THREE
); p3
= t
->v
[0];
82 mp_div(0, &u
, j
.m
, MP_THREE
); j3
= u
->v
[0];
84 /* If the jump is a multiple of three already, then we're stuffed unless
85 * the start position is 2 (mod 3). This shouldn't happen, since the
86 * jump should be twice a multiple of two large primes, which will be
89 * Set a = (2 - p) j mod 3. Then p' = p + a j == p (mod j), and p' ==
90 * p + (2 - p) j^2 == 2 (mod 3).
94 if (a
== 1) p
= mp_add(p
, p
, j
.m
);
95 else if (a
== 2) { t
= mp_lsl(t
, j
.m
, 1); p
= mp_add(p
, p
, t
); }
97 /* Finally, multiply j by three to make sure it preserves this
100 pfilt_muladd(&j
, &j
, 3, 0);
103 /* Set the search going. */
105 p
= pgen(name
, p
, p
, event
, ectx
,
106 nsteps
, pgen_jump
, &jctx
,
107 PGEN_BAILLIEPSWNTESTS
, pgen_bailliepswtest
, 0);
111 /* Check the GCD constraint. */
112 t
= mp_sub(t
, p
, MP_ONE
);
113 mp_gcd(&t
, &u
, 0, e
, t
);
114 if (!MP_EQ(t
, MP_ONE
)) goto end
;
117 mp_drop(*pp
); *pp
= p
; p
= 0;
118 mp_drop(*dd
); *dd
= u
; u
= 0;
121 mp_drop(p
); mp_drop(t
); mp_drop(u
);
126 int rsa_gen_e(rsa_priv
*rp
, unsigned nbits
, mp
*e
,
127 grand
*r
, unsigned nsteps
, pgen_proc
*event
, void *ectx
)
129 mp
*p
= MP_NEWSEC
, *q
= MP_NEWSEC
, *n
= MP_NEW
;
130 mp
*dp
= MP_NEWSEC
, *dq
= MP_NEWSEC
;
131 mp
*t
= MP_NEW
, *u
= MP_NEW
, *v
= MP_NEW
;
135 #define RETRY(what) \
136 do { if (nsteps) goto fail; else goto retry_##what; } while (0)
138 /* Find the first prime. */
141 if (genprime(&p
, &dp
, "p", nbits
/2, e
, r
, nsteps
, event
, ectx
))
144 /* Find the second prime. */
146 if (genprime(&q
, &dq
, "q", nbits
/2, e
, r
, nsteps
, event
, ectx
))
149 /* Check that gcd(p - 1, q - 1) is sufficiently large. */
150 u
= mp_sub(u
, p
, MP_ONE
);
151 v
= mp_sub(v
, q
, MP_ONE
);
152 mp_gcd(&t
, 0, 0, u
, v
);
153 if (mp_bits(t
) >= 8) RETRY(all
);
155 /* Arrange for p > q. */
156 if (MP_CMP(p
, <, q
)) {
157 tt
= p
; p
= q
; q
= tt
;
158 tt
= dp
; dp
= dq
; dq
= tt
;
161 /* Check that the modulus is the right size. */
163 if (mp_bits(n
) != nbits
) RETRY(all
);
165 /* Now we want to calculate d. The unit-group exponent is λ = lcm(p - 1,
166 * q - 1), so d == e^-1 (mod λ).
170 rp
->d
= mp_modinv(MP_NEW
, e
, t
);
174 rp
->q_inv
= mp_modinv(MP_NEW
, q
, p
);
175 rp
->p
= p
; p
= 0; rp
->dp
= dp
; dp
= 0;
176 rp
->q
= q
; q
= 0; rp
->dq
= dq
; dq
= 0;
181 mp_drop(p
); mp_drop(dp
);
182 mp_drop(q
); mp_drop(dq
);
184 mp_drop(t
); mp_drop(u
); mp_drop(v
);
188 int rsa_gen(rsa_priv
*rp
, unsigned nbits
,
189 grand
*r
, unsigned nsteps
, pgen_proc
*event
, void *ectx
)
191 mp
*f4
= mp_fromulong(MP_NEW
, 65537);
192 int rc
= rsa_gen_e(rp
, nbits
, f4
, r
, nsteps
, event
, ectx
);
193 mp_drop(f4
); return (rc
);
196 /*----- That's all, folks -------------------------------------------------*/