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
;
70 /* Find a start position for the search. */
71 p
= strongprime_setup(name
, p
, &j
, nbits
, r
, nsteps
, event
, ectx
);
74 /* Special handling for e = 3. */
75 if (MP_EQ(e
, MP_THREE
)) {
76 /* We must have p == 2 (mod 3): if p == 0 (mod 3) then p is not prime; if
77 * p == 1 (mod 3) then e|(p - 1). So fiddle the start position and jump
78 * context to allow for this.
81 /* Figure out the residues of the start position and jump. */
82 mp_div(0, &t
, p
, MP_THREE
); p3
= t
->v
[0];
83 mp_div(0, &u
, j
.m
, MP_THREE
); j3
= u
->v
[0];
85 /* If the jump is a multiple of three already, then we're stuffed unless
86 * the start position is 2 (mod 3). This shouldn't happen, since the
87 * jump should be twice a multiple of two large primes, which will be
90 * Set a = (2 - p) j mod 3. Then p' = p + a j == p (mod j), and p' ==
91 * p + (2 - p) j^2 == 2 (mod 3).
95 if (a
== 1) p
= mp_add(p
, p
, j
.m
);
96 else if (a
== 2) { t
= mp_lsl(t
, j
.m
, 1); p
= mp_add(p
, p
, t
); }
98 /* Finally, multiply j by three to make sure it preserves this
101 pfilt_muladd(&j
, &j
, 3, 0);
104 /* Set the search going. */
106 p
= pgen(name
, p
, p
, event
, ectx
,
107 nsteps
, pgen_jump
, &jctx
,
108 rabin_iters(nbits
), pgen_test
, &rb
);
112 /* Check the GCD constraint. */
113 t
= mp_sub(t
, p
, MP_ONE
);
114 mp_gcd(&t
, &u
, 0, e
, t
);
115 if (!MP_EQ(t
, MP_ONE
)) goto end
;
118 mp_drop(*pp
); *pp
= p
; p
= 0;
119 mp_drop(*dd
); *dd
= u
; u
= 0;
122 mp_drop(p
); mp_drop(t
); mp_drop(u
);
127 int rsa_gen_e(rsa_priv
*rp
, unsigned nbits
, mp
*e
,
128 grand
*r
, unsigned nsteps
, pgen_proc
*event
, void *ectx
)
130 mp
*p
= MP_NEWSEC
, *q
= MP_NEWSEC
, *n
= MP_NEW
;
131 mp
*dp
= MP_NEWSEC
, *dq
= MP_NEWSEC
;
132 mp
*t
= MP_NEW
, *u
= MP_NEW
, *v
= MP_NEW
;
136 #define RETRY(what) \
137 do { if (nsteps) goto fail; else goto retry_##what; } while (0)
139 /* Find the first prime. */
142 if (genprime(&p
, &dp
, "p", nbits
/2, e
, r
, nsteps
, event
, ectx
))
145 /* Find the second prime. */
147 if (genprime(&q
, &dq
, "q", nbits
/2, e
, r
, nsteps
, event
, ectx
))
150 /* Check that gcd(p - 1, q - 1) is sufficiently large. */
151 u
= mp_sub(u
, p
, MP_ONE
);
152 v
= mp_sub(v
, q
, MP_ONE
);
153 mp_gcd(&t
, 0, 0, u
, v
);
154 if (mp_bits(t
) >= 8) RETRY(all
);
156 /* Arrange for p > q. */
157 if (MP_CMP(p
, <, q
)) {
158 tt
= p
; p
= q
; q
= tt
;
159 tt
= dp
; dp
= dq
; dq
= tt
;
162 /* Check that the modulus is the right size. */
164 if (mp_bits(n
) != nbits
) RETRY(all
);
166 /* Now we want to calculate d. The unit-group exponent is λ = lcm(p - 1,
167 * q - 1), so d == e^-1 (mod λ).
171 rp
->d
= mp_modinv(MP_NEW
, e
, t
);
175 rp
->q_inv
= mp_modinv(MP_NEW
, q
, p
);
176 rp
->p
= p
; p
= 0; rp
->dp
= dp
; dp
= 0;
177 rp
->q
= q
; q
= 0; rp
->dq
= dq
; dq
= 0;
182 mp_drop(p
); mp_drop(dp
);
183 mp_drop(q
); mp_drop(dq
);
185 mp_drop(t
); mp_drop(u
); mp_drop(v
);
189 int rsa_gen(rsa_priv
*rp
, unsigned nbits
,
190 grand
*r
, unsigned nsteps
, pgen_proc
*event
, void *ectx
)
192 mp
*f4
= mp_fromulong(MP_NEW
, 65537);
193 int rc
= rsa_gen_e(rp
, nbits
, f4
, r
, nsteps
, event
, ectx
);
194 mp_drop(f4
); return (rc
);
197 /*----- That's all, folks -------------------------------------------------*/