[u/mdw/catacomb] / rsa-gen.c

/* -*-c-*-
 *
 * $Id: rsa-gen.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
 *
 * RSA parameter generation
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: rsa-gen.c,v $
 * Revision 1.1  1999/12/22 15:50:45  mdw
 * Initial RSA support.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <mLib/dstr.h>

#include "grand.h"
#include "mp.h"
#include "pgen.h"
#include "rsa.h"
#include "strongprime.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @rsa_gen@ --- *
 *
 * Arguments:	@rsa_param *rp@ = pointer to block to be filled in
 *		@unsigned nbits@ = required modulus size in bits
 *		@grand *r@ = random number source
 *		@unsigned n@ = number of attempts to make
 *		@pgen_proc *event@ = event handler function
 *		@void *ectx@ = argument for the event handler
 *
 * Returns:	Zero if all went well, nonzero otherwise.
 *
 * Use:		Constructs a pair of strong RSA primes and other useful RSA
 *		parameters.  A small encryption exponent is chosen if
 *		possible.
 */

int rsa_gen(rsa_param *rp, unsigned nbits, grand *r, unsigned n,
	    pgen_proc *event, void *ectx)
{
  mp *phi;
  int i;
  mp *g;

  /* --- Generate strong primes %$p$% and %$q$% --- */

  if ((rp->p = strongprime("p", MP_NEW, nbits/2, r, n, event, ectx)) == 0)
    goto fail_p;
  if ((rp->q = strongprime("q", MP_NEW, nbits/2, r, n, event, ectx)) == 0)
    goto fail_q;

  /* --- Work out the modulus and the CRT coefficient --- */

  rp->n = mp_mul(MP_NEW, rp->p, rp->q);
  rp->q_inv = MP_NEW; mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q);

  /* --- Work out %$\varphi(n) = (p - 1)(q - 1)$% --- *
   *
   * Save on further multiplications by noting that %$n = pq$% is known and
   * that %$(p - 1)(q - 1) = pq - p - q + 1$%.
   */

  phi = mp_sub(MP_NEW, rp->n, rp->p);
  phi = mp_sub(phi, phi, rp->q);
  phi = mp_add(phi, phi, MP_ONE);

  /* --- Decide on a public exponent --- *
   *
   * Simultaneously compute the private exponent.
   */

  rp->e = mp_create(1);
  rp->d = MP_NEW;
  g = MP_NEW;
  for (i = 1; i < NPRIME; i++) {
    rp->e->v[0] = primetab[i];
    mp_gcd(&g, 0, &rp->d, phi, rp->e);
    if (MP_CMP(g, ==, MP_ONE))
      goto good_e;
  }
  goto fail_e;

  /* --- Work out exponent residues --- */

good_e:
  rp->dp = MP_NEW; phi = mp_sub(phi, rp->p, MP_ONE);
  mp_div(0, &rp->dp, rp->d, phi);

  rp->dq = MP_NEW; phi = mp_sub(phi, rp->q, MP_ONE);
  mp_div(0, &rp->dq, rp->d, phi);

  /* --- Done --- */

  mp_drop(phi);
  mp_drop(g);
  return (0);

  /* --- Tidy up when something goes wrong --- */

fail_e:
  mp_drop(g);
  mp_drop(phi);
  mp_drop(rp->n);
  mp_drop(rp->q_inv);
  mp_drop(rp->q);
fail_q:
  mp_drop(rp->p);
fail_p:
  return (-1);
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
01898d8e	1	/* --c--
	2	*
	3	* $Id: rsa-gen.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
	4	*
	5	* RSA parameter generation
	6	*
	7	* (c) 1999 Straylight/Edgeware
	8	*/
	9
	10	/----- Licensing notice --------------------------------------------------
	11	*
	12	* This file is part of Catacomb.
	13	*
	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.
	18	*
	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.
	23	*
	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,
	27	* MA 02111-1307, USA.
	28	*/
	29
	30	/----- Revision history --------------------------------------------------
	31	*
	32	* $Log: rsa-gen.c,v $
	33	* Revision 1.1 1999/12/22 15:50:45 mdw
	34	* Initial RSA support.
	35	*
	36	*/
	37
	38	/----- Header files ------------------------------------------------------/
	39
	40	#include <mLib/dstr.h>
	41
	42	#include "grand.h"
	43	#include "mp.h"
	44	#include "pgen.h"
	45	#include "rsa.h"
	46	#include "strongprime.h"
	47
	48	/----- Main code ---------------------------------------------------------/
	49
	50	/* --- @rsa_gen@ --- *
	51	*
	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
	58	*
	59	* Returns: Zero if all went well, nonzero otherwise.
	60	*
	61	* Use: Constructs a pair of strong RSA primes and other useful RSA
	62	* parameters. A small encryption exponent is chosen if
	63	* possible.
	64	*/
65
66	int rsa_gen(rsa_param rp, unsigned nbits, grand r, unsigned n,
67	pgen_proc event, void ectx)
68	{
69	mp *phi;
70	int i;
71	mp *g;
72
73	/* --- Generate strong primes %$p$% and %$q$% --- */
74
75	if ((rp->p = strongprime("p", MP_NEW, nbits/2, r, n, event, ectx)) == 0)
76	goto fail_p;
77	if ((rp->q = strongprime("q", MP_NEW, nbits/2, r, n, event, ectx)) == 0)
78	goto fail_q;
79
80	/* --- Work out the modulus and the CRT coefficient --- */
81
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);
84
85	/* --- Work out %$\varphi(n) = (p - 1)(q - 1)$% --- *
86	*
87	* Save on further multiplications by noting that %$n = pq$% is known and
88	* that %$(p - 1)(q - 1) = pq - p - q + 1$%.
89	*/
90
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);
94
95	/* --- Decide on a public exponent --- *
96	*
97	* Simultaneously compute the private exponent.
98	*/
99
100	rp->e = mp_create(1);
101	rp->d = MP_NEW;
102	g = MP_NEW;
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))
107	goto good_e;
108	}
109	goto fail_e;
110
111	/* --- Work out exponent residues --- */
112
113	good_e:
114	rp->dp = MP_NEW; phi = mp_sub(phi, rp->p, MP_ONE);
115	mp_div(0, &rp->dp, rp->d, phi);
116
117	rp->dq = MP_NEW; phi = mp_sub(phi, rp->q, MP_ONE);
118	mp_div(0, &rp->dq, rp->d, phi);
119
120	/* --- Done --- */
121
122	mp_drop(phi);
123	mp_drop(g);
124	return (0);
125
126	/* --- Tidy up when something goes wrong --- */
127
128	fail_e:
129	mp_drop(g);
130	mp_drop(phi);
131	mp_drop(rp->n);
132	mp_drop(rp->q_inv);
133	mp_drop(rp->q);
134	fail_q:
135	mp_drop(rp->p);
136	fail_p:
137	return (-1);
138	}
139
140	/----- That's all, folks -------------------------------------------------/