3 * $Id: rsa-gen.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
5 * RSA parameter 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 --------------------------------------------------*
33 * Revision 1.1 1999/12/22 15:50:45 mdw
34 * Initial RSA support.
38 /*----- Header files ------------------------------------------------------*/
40 #include <mLib/dstr.h>
46 #include "strongprime.h"
48 /*----- Main code ---------------------------------------------------------*/
50 /* --- @rsa_gen@ --- *
52 * Arguments: @rsa_param *rp@ = pointer to block to be filled in
53 * @unsigned nbits@ = required modulus size in bits
54 * @grand *r@ = random number source
55 * @unsigned n@ = number of attempts to make
56 * @pgen_proc *event@ = event handler function
57 * @void *ectx@ = argument for the event handler
59 * Returns: Zero if all went well, nonzero otherwise.
61 * Use: Constructs a pair of strong RSA primes and other useful RSA
62 * parameters. A small encryption exponent is chosen if
66 int rsa_gen(rsa_param
*rp
, unsigned nbits
, grand
*r
, unsigned n
,
67 pgen_proc
*event
, void *ectx
)
73 /* --- Generate strong primes %$p$% and %$q$% --- */
75 if ((rp
->p
= strongprime("p", MP_NEW
, nbits
/2, r
, n
, event
, ectx
)) == 0)
77 if ((rp
->q
= strongprime("q", MP_NEW
, nbits
/2, r
, n
, event
, ectx
)) == 0)
80 /* --- Work out the modulus and the CRT coefficient --- */
82 rp
->n
= mp_mul(MP_NEW
, rp
->p
, rp
->q
);
83 rp
->q_inv
= MP_NEW
; mp_gcd(0, 0, &rp
->q_inv
, rp
->p
, rp
->q
);
85 /* --- Work out %$\varphi(n) = (p - 1)(q - 1)$% --- *
87 * Save on further multiplications by noting that %$n = pq$% is known and
88 * that %$(p - 1)(q - 1) = pq - p - q + 1$%.
91 phi
= mp_sub(MP_NEW
, rp
->n
, rp
->p
);
92 phi
= mp_sub(phi
, phi
, rp
->q
);
93 phi
= mp_add(phi
, phi
, MP_ONE
);
95 /* --- Decide on a public exponent --- *
97 * Simultaneously compute the private exponent.
100 rp
->e
= mp_create(1);
103 for (i
= 1; i
< NPRIME
; i
++) {
104 rp
->e
->v
[0] = primetab
[i
];
105 mp_gcd(&g
, 0, &rp
->d
, phi
, rp
->e
);
106 if (MP_CMP(g
, ==, MP_ONE
))
111 /* --- Work out exponent residues --- */
114 rp
->dp
= MP_NEW
; phi
= mp_sub(phi
, rp
->p
, MP_ONE
);
115 mp_div(0, &rp
->dp
, rp
->d
, phi
);
117 rp
->dq
= MP_NEW
; phi
= mp_sub(phi
, rp
->q
, MP_ONE
);
118 mp_div(0, &rp
->dq
, rp
->d
, phi
);
126 /* --- Tidy up when something goes wrong --- */
140 /*----- That's all, folks -------------------------------------------------*/