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

/* -*-c-*-
 *
 * $Id: rsa-priv.c,v 1.4 2004/04/08 01:36:15 mdw Exp $
 *
 * RSA private-key operations
 *
 * (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.
 */

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

#include <mLib/alloc.h>
#include <mLib/bits.h>
#include <mLib/dstr.h>

#include "mp.h"
#include "mpmont.h"
#include "mprand.h"
#include "rsa.h"

/*----- Public key operations ---------------------------------------------*/

/* --- @rsa_privcreate@ --- *
 *
 * Arguments:	@rsa_privctx *rd@ = pointer to an RSA private key context
 *		@rsa_priv *rp@ = pointer to RSA private key
 *		@grand *r@ = pointer to random number source for blinding
 *
 * Returns:	---
 *
 * Use:		Initializes an RSA private-key context.  Keeping a context
 *		for several decryption or signing operations provides a minor
 *		performance benefit.
 *
 *		The random number source may be null if blinding is not
 *		desired.  This improves decryption speed, at the risk of
 *		permitting timing attacks.
 */

void rsa_privcreate(rsa_privctx *rd, rsa_priv *rp, grand *r)
{
  rd->rp = rp;
  rd->r = r;
  if (r)
    mpmont_create(&rd->nm, rp->n);
  mpmont_create(&rd->pm, rp->p);
  mpmont_create(&rd->qm, rp->q);
}

/* --- @rsa_privdestroy@ --- *
 *
 * Arguments:	@rsa_privctx *rd@ = pointer to an RSA decryption context
 *
 * Returns:	---
 *
 * Use:		Destroys an RSA decryption context.
 */

void rsa_privdestroy(rsa_privctx *rd)
{
  if (rd->r)
    mpmont_destroy(&rd->nm);
  mpmont_destroy(&rd->pm);
  mpmont_destroy(&rd->qm);
}

/* --- @rsa_privop@ --- *
 *
 * Arguments:	@rsa_privctx *rd@ = pointer to RSA private key context
 *		@mp *d@ = destination
 *		@mp *c@ = input message
 *
 * Returns:	The transformed output message.
 *
 * Use:		Performs an RSA private key operation.  This function takes
 *		advantage of knowledge of the key factors in order to speed
 *		up decryption.  It also blinds the ciphertext prior to
 *		decryption and unblinds it afterwards to thwart timing
 *		attacks.
 */

mp *rsa_privop(rsa_privctx *rd, mp *d, mp *c)
{
  mp *ki = MP_NEW;
  rsa_priv *rp = rd->rp;

  /* --- If so desired, set up a blinding constant --- *
   *
   * Choose a constant %$k$% relatively prime to the modulus %$m$%.  Compute
   * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%.  Don't bother with the
   * CRT stuff here because %$e$% is chosen to be small.
   */

  c = MP_COPY(c);
  if (rd->r) {
    mp *k = MP_NEWSEC, *g = MP_NEW;

    do {
      k = mprand_range(k, rp->n, rd->r, 0);
      mp_gcd(&g, 0, &ki, rp->n, k);
    } while (!MP_EQ(g, MP_ONE));
    k = mpmont_mul(&rd->nm, k, k, rd->nm.r2);
    k = mpmont_expr(&rd->nm, k, k, rp->e);
    c = mpmont_mul(&rd->nm, c, c, k);
    mp_drop(k);
    mp_drop(g);
  }

  /* --- Do the actual modular exponentiation --- *
   *
   * Use a slightly hacked version of the Chinese Remainder Theorem stuff.
   *
   * Let %$q' = q^{-1} \bmod p$%.  Then note that
   * %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$%
   */

  {
    mp *cp = MP_NEW, *cq = MP_NEW;

    /* --- Work out the two halves of the result --- */

    mp_div(0, &cp, c, rp->p);
    cp = mpmont_exp(&rd->pm, cp, cp, rp->dp);

    mp_div(0, &cq, c, rp->q);
    cq = mpmont_exp(&rd->qm, cq, cq, rp->dq);

    /* --- Combine the halves using the result above --- */

    d = mp_sub(d, cp, cq);
    mp_div(0, &d, d, rp->p);
    d = mpmont_mul(&rd->pm, d, d, rp->q_inv);
    d = mpmont_mul(&rd->pm, d, d, rd->pm.r2);

    d = mp_mul(d, d, rp->q);
    d = mp_add(d, d, cq);
    if (MP_CMP(d, >=, rp->n))
      d = mp_sub(d, d, rp->n);

    /* --- Tidy away temporary variables --- */

    mp_drop(cp);
    mp_drop(cq);
  }

  /* --- Finally, possibly remove the blinding factor --- */

  if (ki) {
    d = mpmont_mul(&rd->nm, d, d, ki);
    d = mpmont_mul(&rd->nm, d, d, rd->nm.r2);
    mp_drop(ki);
  }

  /* --- Done --- */

  mp_drop(c);
  return (d);
}

/* --- @rsa_qprivop@ --- *
 *
 * Arguments:	@rsa_priv *rp@ = pointer to RSA parameters
 *		@mp *d@ = destination
 *		@mp *c@ = input message
 *		@grand *r@ = pointer to random number source for blinding
 *
 * Returns:	Correctly transformed output message
 *
 * Use:		Performs an RSA private key operation, very carefully.
 */

mp *rsa_qprivop(rsa_priv *rp, mp *d, mp *c, grand *r)
{
  rsa_privctx rd;
  rsa_privcreate(&rd, rp, r);
  d = rsa_privop(&rd, d, c);
  rsa_privdestroy(&rd);
  return (d);
}

/*----- Operations with padding -------------------------------------------*/

/* --- @rsa_sign@ --- *
 *
 * Arguments:	@rsa_privctx *rp@ = pointer to an RSA private key context
 *		@mp *d@ = where to put the result
 *		@const void *m@ = pointer to input message
 *		@size_t msz@ = size of input message
 *		@rsa_pad *e@ = encoding procedure
 *		@void *earg@ = argument pointer for encoding procedure
 *
 * Returns:	The signature, as a multiprecision integer, or null on
 *		failure.
 *
 * Use:		Computes an RSA digital signature.
 */

mp *rsa_sign(rsa_privctx *rp, mp *d, const void *m, size_t msz,
	     rsa_pad *e, void *earg)
{
  octet *p;
  unsigned long nb = mp_bits(rp->rp->n);
  size_t n = (nb + 7)/8;
  arena *a = d && d->a ? d->a->a : arena_global;

  p = x_alloc(a, n);
  d = e(d, m, msz, p, n, nb, earg);
  x_free(a, p);
  return (d ? rsa_privop(rp, d, d) : 0);
}

/* --- @rsa_decrypt@ --- *
 *
 * Arguments:	@rsa_privctx *rp@ = pointer to an RSA private key context
 *		@mp *m@ = encrypted message, as a multiprecision integer
 *		@dstr *d@ = pointer to output string
 *		@rsa_decunpad *e@ = decoding procedure
 *		@void *earg@ = argument pointer for decoding procedure
 *
 * Returns:	The length of the output string if successful, negative on
 *		failure.
 *
 * Use:		Does RSA decryption.
 */

int rsa_decrypt(rsa_privctx *rp, mp *m, dstr *d,
		rsa_decunpad *e, void *earg)
{
  mp *p = rsa_privop(rp, MP_NEW, m);
  unsigned long nb = mp_bits(rp->rp->n);
  size_t n = (nb + 7)/8;
  int rc;

  dstr_ensure(d, n);
  rc = e(p, (octet *)d->buf + d->len, n, nb, earg);
  if (rc >= 0)
    d->len += rc;
  mp_drop(p);
  return (rc);
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
c760149f	1	/* --c--
c760149f	2	*
b817bfc6	3	* $Id: rsa-priv.c,v 1.4 2004/04/08 01:36:15 mdw Exp $
c760149f	4	*
	5	* RSA private-key operations
	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
c760149f	30	/----- Header files ------------------------------------------------------/
	31
	32	#include <mLib/alloc.h>
	33	#include <mLib/bits.h>
	34	#include <mLib/dstr.h>
	35
	36	#include "mp.h"
	37	#include "mpmont.h"
	38	#include "mprand.h"
	39	#include "rsa.h"
	40
	41	/----- Public key operations ---------------------------------------------/
	42
	43	/* --- @rsa_privcreate@ --- *
	44	*
	45	* Arguments: @rsa_privctx *rd@ = pointer to an RSA private key context
	46	* @rsa_priv *rp@ = pointer to RSA private key
	47	* @grand *r@ = pointer to random number source for blinding
	48	*
	49	* Returns: ---
	50	*
	51	* Use: Initializes an RSA private-key context. Keeping a context
	52	* for several decryption or signing operations provides a minor
	53	* performance benefit.
	54	*
	55	* The random number source may be null if blinding is not
	56	* desired. This improves decryption speed, at the risk of
	57	* permitting timing attacks.
	58	*/
	59
	60	void rsa_privcreate(rsa_privctx rd, rsa_priv rp, grand *r)
	61	{
	62	rd->rp = rp;
	63	rd->r = r;
	64	if (r)
	65	mpmont_create(&rd->nm, rp->n);
	66	mpmont_create(&rd->pm, rp->p);
	67	mpmont_create(&rd->qm, rp->q);
	68	}
	69
	70	/* --- @rsa_privdestroy@ --- *
	71	*
	72	* Arguments: @rsa_privctx *rd@ = pointer to an RSA decryption context
	73	*
	74	* Returns: ---
	75	*
	76	* Use: Destroys an RSA decryption context.
	77	*/
	78
	79	void rsa_privdestroy(rsa_privctx *rd)
	80	{
	81	if (rd->r)
	82	mpmont_destroy(&rd->nm);
	83	mpmont_destroy(&rd->pm);
	84	mpmont_destroy(&rd->qm);
	85	}
	86
	87	/* --- @rsa_privop@ --- *
	88	*
	89	* Arguments: @rsa_privctx *rd@ = pointer to RSA private key context
	90	* @mp *d@ = destination
	91	* @mp *c@ = input message
	92	*
	93	* Returns: The transformed output message.
94	*
95	* Use: Performs an RSA private key operation. This function takes
96	* advantage of knowledge of the key factors in order to speed
97	* up decryption. It also blinds the ciphertext prior to
98	* decryption and unblinds it afterwards to thwart timing
99	* attacks.
100	*/
101
102	mp rsa_privop(rsa_privctx rd, mp d, mp c)
103	{
104	mp *ki = MP_NEW;
105	rsa_priv *rp = rd->rp;
106
107	/* --- If so desired, set up a blinding constant --- *
108	*
109	* Choose a constant %$k$% relatively prime to the modulus %$m$%. Compute
110	* %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%. Don't bother with the
111	* CRT stuff here because %$e$% is chosen to be small.
112	*/
113
114	c = MP_COPY(c);
115	if (rd->r) {
116	mp k = MP_NEWSEC, g = MP_NEW;
117
118	do {
119	k = mprand_range(k, rp->n, rd->r, 0);
120	mp_gcd(&g, 0, &ki, rp->n, k);
22bab86c	121	} while (!MP_EQ(g, MP_ONE));
b0b682aa	122	k = mpmont_mul(&rd->nm, k, k, rd->nm.r2);
c760149f	123	k = mpmont_expr(&rd->nm, k, k, rp->e);
	124	c = mpmont_mul(&rd->nm, c, c, k);
	125	mp_drop(k);
	126	mp_drop(g);
	127	}
	128
	129	/* --- Do the actual modular exponentiation --- *
	130	*
	131	* Use a slightly hacked version of the Chinese Remainder Theorem stuff.
	132	*
	133	* Let %$q' = q^{-1} \bmod p$%. Then note that
	134	* %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$%
	135	*/
	136
	137	{
	138	mp cp = MP_NEW, cq = MP_NEW;
	139
	140	/* --- Work out the two halves of the result --- */
	141
	142	mp_div(0, &cp, c, rp->p);
	143	cp = mpmont_exp(&rd->pm, cp, cp, rp->dp);
	144
	145	mp_div(0, &cq, c, rp->q);
	146	cq = mpmont_exp(&rd->qm, cq, cq, rp->dq);
	147
	148	/* --- Combine the halves using the result above --- */
	149
	150	d = mp_sub(d, cp, cq);
	151	mp_div(0, &d, d, rp->p);
	152	d = mpmont_mul(&rd->pm, d, d, rp->q_inv);
	153	d = mpmont_mul(&rd->pm, d, d, rd->pm.r2);
	154
	155	d = mp_mul(d, d, rp->q);
	156	d = mp_add(d, d, cq);
	157	if (MP_CMP(d, >=, rp->n))
	158	d = mp_sub(d, d, rp->n);
	159
	160	/* --- Tidy away temporary variables --- */
	161
	162	mp_drop(cp);
	163	mp_drop(cq);
	164	}
	165
	166	/* --- Finally, possibly remove the blinding factor --- */
	167
	168	if (ki) {
	169	d = mpmont_mul(&rd->nm, d, d, ki);
	170	d = mpmont_mul(&rd->nm, d, d, rd->nm.r2);
	171	mp_drop(ki);
	172	}
	173
	174	/* --- Done --- */
	175
	176	mp_drop(c);
	177	return (d);
	178	}
	179
	180	/* --- @rsa_qprivop@ --- *
	181	*
	182	* Arguments: @rsa_priv *rp@ = pointer to RSA parameters
	183	* @mp *d@ = destination
	184	* @mp *c@ = input message
	185	* @grand *r@ = pointer to random number source for blinding
	186	*
187	* Returns: Correctly transformed output message
188	*
189	* Use: Performs an RSA private key operation, very carefully.
190	*/
191
192	mp rsa_qprivop(rsa_priv rp, mp d, mp c, grand *r)
193	{
194	rsa_privctx rd;
195	rsa_privcreate(&rd, rp, r);
196	d = rsa_privop(&rd, d, c);
197	rsa_privdestroy(&rd);
198	return (d);
199	}
200
201	/----- Operations with padding -------------------------------------------/
202
203	/* --- @rsa_sign@ --- *
204	*
205	* Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
b817bfc6	206	* @mp *d@ = where to put the result
c760149f	207	* @const void *m@ = pointer to input message
b817bfc6	208	* @size_t msz@ = size of input message
b817bfc6	209	* @rsa_pad *e@ = encoding procedure
c760149f	210	* @void *earg@ = argument pointer for encoding procedure
c760149f	211	*
b817bfc6	212	* Returns: The signature, as a multiprecision integer, or null on
c760149f	213	* failure.
	214	*
	215	* Use: Computes an RSA digital signature.
	216	*/
	217
b817bfc6	218	mp rsa_sign(rsa_privctx rp, mp d, const void m, size_t msz,
b817bfc6	219	rsa_pad e, void earg)
c760149f	220	{
c760149f	221	octet *p;
b817bfc6	222	unsigned long nb = mp_bits(rp->rp->n);
	223	size_t n = (nb + 7)/8;
	224	arena *a = d && d->a ? d->a->a : arena_global;
	225
	226	p = x_alloc(a, n);
	227	d = e(d, m, msz, p, n, nb, earg);
	228	x_free(a, p);
	229	return (d ? rsa_privop(rp, d, d) : 0);
c760149f	230	}
	231
	232	/* --- @rsa_decrypt@ --- *
	233	*
	234	* Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
b817bfc6	235	* @mp *m@ = encrypted message, as a multiprecision integer
c760149f	236	* @dstr *d@ = pointer to output string
b817bfc6	237	* @rsa_decunpad *e@ = decoding procedure
c760149f	238	* @void *earg@ = argument pointer for decoding procedure
	239	*
	240	* Returns: The length of the output string if successful, negative on
	241	* failure.
	242	*
b817bfc6	243	* Use: Does RSA decryption.
c760149f	244	*/
c760149f	245
b817bfc6	246	int rsa_decrypt(rsa_privctx rp, mp m, dstr *d,
b817bfc6	247	rsa_decunpad e, void earg)
c760149f	248	{
b817bfc6	249	mp *p = rsa_privop(rp, MP_NEW, m);
	250	unsigned long nb = mp_bits(rp->rp->n);
	251	size_t n = (nb + 7)/8;
c760149f	252	int rc;
c760149f	253
b817bfc6	254	dstr_ensure(d, n);
	255	rc = e(p, (octet *)d->buf + d->len, n, nb, earg);
	256	if (rc >= 0)
	257	d->len += rc;
	258	mp_drop(p);
c760149f	259	return (rc);
	260	}
	261
	262	/----- That's all, folks -------------------------------------------------/