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

/* -*-c-*-
 *
 * $Id: rsa-decrypt.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
 *
 * RSA decryption
 *
 * (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-decrypt.c,v $
 * Revision 1.1  1999/12/22 15:50:45  mdw
 * Initial RSA support.
 *
 */

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

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

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

/* --- @rsa_decrypt@ --- *
 *
 * Arguments:	@rsa_param *rp@ = pointer to RSA parameters
 *		@mp *d@ = destination
 *		@mp *c@ = ciphertext message
 *		@grand *r@ = pointer to random number source for blinding
 *
 * Returns:	Correctly decrypted message.
 *
 * Use:		Performs RSA decryption, very carefully.
 */

mp *rsa_decrypt(rsa_param *rp, mp *d, mp *c, grand *r)
{
  mp *ki = MP_NEW;

  /* --- 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$%.
   */

  c = MP_COPY(c);
  if (r) {
    mp *k = MP_NEW, *g = MP_NEW;
    mpmont mm;

    do {
      k = mprand_range(k, rp->n, r, 0);
      mp_gcd(&g, 0, &ki, rp->n, k);
    } while (MP_CMP(g, !=, MP_ONE));
    mpmont_create(&mm, rp->n);
    k = mpmont_expr(&mm, k, k, rp->e);
    c = mpmont_mul(&mm, 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$%
   */

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

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

    mp_div(0, &cp, c, rp->p);
    mpmont_create(&mm, rp->p);
    cp = mpmont_exp(&mm, cp, cp, rp->dp);
    mpmont_destroy(&mm);

    mp_div(0, &cq, c, rp->q);
    mpmont_create(&mm, rp->q);
    cq = mpmont_exp(&mm, cq, cq, rp->dq);
    mpmont_destroy(&mm);

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

    d = mp_sub(d, cp, cq);
    if (cp->f & MP_NEG)
      d = mp_add(d, d, rp->p);
    d = mp_mul(d, d, rp->q_inv);
    mp_div(0, &d, d, rp->p);

    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 = mp_mul(d, d, ki);
    mp_div(0, &d, d, rp->n);
    mp_drop(ki);
  }

  /* --- Done --- */

  mp_drop(c);
  return (d);
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
01898d8e	1	/* --c--
	2	*
	3	* $Id: rsa-decrypt.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
	4	*
	5	* RSA decryption
	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-decrypt.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 "mp.h"
	41	#include "mpmont.h"
	42	#include "mprand.h"
	43	#include "rsa.h"
	44
	45	/----- Main code ---------------------------------------------------------/
	46
	47	/* --- @rsa_decrypt@ --- *
	48	*
	49	* Arguments: @rsa_param *rp@ = pointer to RSA parameters
	50	* @mp *d@ = destination
	51	* @mp *c@ = ciphertext message
	52	* @grand *r@ = pointer to random number source for blinding
	53	*
	54	* Returns: Correctly decrypted message.
	55	*
	56	* Use: Performs RSA decryption, very carefully.
	57	*/
	58
	59	mp rsa_decrypt(rsa_param rp, mp d, mp c, grand *r)
	60	{
	61	mp *ki = MP_NEW;
	62
	63	/* --- If so desired, set up a blinding constant --- *
	64	*
65	* Choose a constant %$k$% relatively prime to the modulus %$m$%. Compute
66	* %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%.
67	*/
68
69	c = MP_COPY(c);
70	if (r) {
71	mp k = MP_NEW, g = MP_NEW;
72	mpmont mm;
73
74	do {
75	k = mprand_range(k, rp->n, r, 0);
76	mp_gcd(&g, 0, &ki, rp->n, k);
77	} while (MP_CMP(g, !=, MP_ONE));
78	mpmont_create(&mm, rp->n);
79	k = mpmont_expr(&mm, k, k, rp->e);
80	c = mpmont_mul(&mm, c, c, k);
81	mp_drop(k);
82	mp_drop(g);
83	}
84
85	/* --- Do the actual modular exponentiation --- *
86	*
87	* Use a slightly hacked version of the Chinese Remainder Theorem stuff.
88	*
89	* Let %$q' = q^{-1} \bmod p$%. Then note that
90	* %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$%
91	*/
92
93	{
94	mpmont mm;
95	mp cp = MP_NEW, cq = MP_NEW;
96
97	/* --- Work out the two halves of the result --- */
98
99	mp_div(0, &cp, c, rp->p);
100	mpmont_create(&mm, rp->p);
101	cp = mpmont_exp(&mm, cp, cp, rp->dp);
102	mpmont_destroy(&mm);
103
104	mp_div(0, &cq, c, rp->q);
105	mpmont_create(&mm, rp->q);
106	cq = mpmont_exp(&mm, cq, cq, rp->dq);
107	mpmont_destroy(&mm);
108
109	/* --- Combine the halves using the result above --- */
110
111	d = mp_sub(d, cp, cq);
112	if (cp->f & MP_NEG)
113	d = mp_add(d, d, rp->p);
114	d = mp_mul(d, d, rp->q_inv);
115	mp_div(0, &d, d, rp->p);
116
117	d = mp_mul(d, d, rp->q);
118	d = mp_add(d, d, cq);
119	if (MP_CMP(d, >=, rp->n))
120	d = mp_sub(d, d, rp->n);
121
122	/* --- Tidy away temporary variables --- */
123
124	mp_drop(cp);
125	mp_drop(cq);
126	}
127
128	/* --- Finally, possibly remove the blinding factor --- */
129
130	if (ki) {
131	d = mp_mul(d, d, ki);
132	mp_div(0, &d, d, rp->n);
133	mp_drop(ki);
134	}
135
136	/* --- Done --- */
137
138	mp_drop(c);
139	return (d);
140	}
141
142	/----- That's all, folks -------------------------------------------------/