git.distorted.org.uk Git - u/mdw/catacomb/blob - rsa-priv.c

   1 /* -*-c-*-
   2  *
   3  * $Id: rsa-priv.c,v 1.3 2001/06/16 12:56:38 mdw Exp $
   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
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: rsa-priv.c,v $
  33  * Revision 1.3  2001/06/16 12:56:38  mdw
  34  * Fixes for interface change to @mpmont_expr@ and @mpmont_mexpr@.
  35  *
  36  * Revision 1.2  2000/10/08 12:11:22  mdw
  37  * Use @MP_EQ@ instead of @MP_CMP@.
  38  *
  39  * Revision 1.1  2000/07/01 11:23:20  mdw
  40  * Renamed from `rsa-decrypt', since the name was no longer appropriate.
  41  * Add functions for doing padded RSA decryption and signing.
  42  *
  43  * --- Previous lives as rsa-decrypt.c ---
  44  *
  45  * Revision 1.2  2000/06/17 11:57:56  mdw
  46  * Improve bulk performance by making better use of Montgomery
  47  * multiplication and separating out initialization and finalization from
  48  * the main code.
  49  *
  50  * Revision 1.1  1999/12/22 15:50:45  mdw
  51  * Initial RSA support.
  52  *
  53  */
  54
  55 /*----- Header files ------------------------------------------------------*/
  56
  57 #include <mLib/alloc.h>
  58 #include <mLib/bits.h>
  59 #include <mLib/dstr.h>
  60
  61 #include "mp.h"
  62 #include "mpmont.h"
  63 #include "mprand.h"
  64 #include "rsa.h"
  65
  66 /*----- Public key operations ---------------------------------------------*/
  67
  68 /* --- @rsa_privcreate@ --- *
  69  *
  70  * Arguments:   @rsa_privctx *rd@ = pointer to an RSA private key context
  71  *              @rsa_priv *rp@ = pointer to RSA private key
  72  *              @grand *r@ = pointer to random number source for blinding
  73  *
  74  * Returns:     ---
  75  *
  76  * Use:         Initializes an RSA private-key context.  Keeping a context
  77  *              for several decryption or signing operations provides a minor
  78  *              performance benefit.
  79  *
  80  *              The random number source may be null if blinding is not
  81  *              desired.  This improves decryption speed, at the risk of
  82  *              permitting timing attacks.
  83  */
  84
  85 void rsa_privcreate(rsa_privctx *rd, rsa_priv *rp, grand *r)
  86 {
  87   rd->rp = rp;
  88   rd->r = r;
  89   if (r)
  90     mpmont_create(&rd->nm, rp->n);
  91   mpmont_create(&rd->pm, rp->p);
  92   mpmont_create(&rd->qm, rp->q);
  93 }
  94
  95 /* --- @rsa_privdestroy@ --- *
  96  *
  97  * Arguments:   @rsa_privctx *rd@ = pointer to an RSA decryption context
  98  *
  99  * Returns:     ---
 100  *
 101  * Use:         Destroys an RSA decryption context.
 102  */
 103
 104 void rsa_privdestroy(rsa_privctx *rd)
 105 {
 106   if (rd->r)
 107     mpmont_destroy(&rd->nm);
 108   mpmont_destroy(&rd->pm);
 109   mpmont_destroy(&rd->qm);
 110 }
 111
 112 /* --- @rsa_privop@ --- *
 113  *
 114  * Arguments:   @rsa_privctx *rd@ = pointer to RSA private key context
 115  *              @mp *d@ = destination
 116  *              @mp *c@ = input message
 117  *
 118  * Returns:     The transformed output message.
 119  *
 120  * Use:         Performs an RSA private key operation.  This function takes
 121  *              advantage of knowledge of the key factors in order to speed
 122  *              up decryption.  It also blinds the ciphertext prior to
 123  *              decryption and unblinds it afterwards to thwart timing
 124  *              attacks.
 125  */
 126
 127 mp *rsa_privop(rsa_privctx *rd, mp *d, mp *c)
 128 {
 129   mp *ki = MP_NEW;
 130   rsa_priv *rp = rd->rp;
 131
 132   /* --- If so desired, set up a blinding constant --- *
 133    *
 134    * Choose a constant %$k$% relatively prime to the modulus %$m$%.  Compute
 135    * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%.  Don't bother with the
 136    * CRT stuff here because %$e$% is chosen to be small.
 137    */
 138
 139   c = MP_COPY(c);
 140   if (rd->r) {
 141     mp *k = MP_NEWSEC, *g = MP_NEW;
 142
 143     do {
 144       k = mprand_range(k, rp->n, rd->r, 0);
 145       mp_gcd(&g, 0, &ki, rp->n, k);
 146     } while (!MP_EQ(g, MP_ONE));
 147     k = mpmont_mul(&rd->nm, k, k, rd->nm.r2);
 148     k = mpmont_expr(&rd->nm, k, k, rp->e);
 149     c = mpmont_mul(&rd->nm, c, c, k);
 150     mp_drop(k);
 151     mp_drop(g);
 152   }
 153
 154   /* --- Do the actual modular exponentiation --- *
 155    *
 156    * Use a slightly hacked version of the Chinese Remainder Theorem stuff.
 157    *
 158    * Let %$q' = q^{-1} \bmod p$%.  Then note that
 159    * %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$%
 160    */
 161
 162   {
 163     mp *cp = MP_NEW, *cq = MP_NEW;
 164
 165     /* --- Work out the two halves of the result --- */
 166
 167     mp_div(0, &cp, c, rp->p);
 168     cp = mpmont_exp(&rd->pm, cp, cp, rp->dp);
 169
 170     mp_div(0, &cq, c, rp->q);
 171     cq = mpmont_exp(&rd->qm, cq, cq, rp->dq);
 172
 173     /* --- Combine the halves using the result above --- */
 174
 175     d = mp_sub(d, cp, cq);
 176     mp_div(0, &d, d, rp->p);
 177     d = mpmont_mul(&rd->pm, d, d, rp->q_inv);
 178     d = mpmont_mul(&rd->pm, d, d, rd->pm.r2);
 179
 180     d = mp_mul(d, d, rp->q);
 181     d = mp_add(d, d, cq);
 182     if (MP_CMP(d, >=, rp->n))
 183       d = mp_sub(d, d, rp->n);
 184
 185     /* --- Tidy away temporary variables --- */
 186
 187     mp_drop(cp);
 188     mp_drop(cq);
 189   }
 190
 191   /* --- Finally, possibly remove the blinding factor --- */
 192
 193   if (ki) {
 194     d = mpmont_mul(&rd->nm, d, d, ki);
 195     d = mpmont_mul(&rd->nm, d, d, rd->nm.r2);
 196     mp_drop(ki);
 197   }
 198
 199   /* --- Done --- */
 200
 201   mp_drop(c);
 202   return (d);
 203 }
 204
 205 /* --- @rsa_qprivop@ --- *
 206  *
 207  * Arguments:   @rsa_priv *rp@ = pointer to RSA parameters
 208  *              @mp *d@ = destination
 209  *              @mp *c@ = input message
 210  *              @grand *r@ = pointer to random number source for blinding
 211  *
 212  * Returns:     Correctly transformed output message
 213  *
 214  * Use:         Performs an RSA private key operation, very carefully.
 215  */
 216
 217 mp *rsa_qprivop(rsa_priv *rp, mp *d, mp *c, grand *r)
 218 {
 219   rsa_privctx rd;
 220   rsa_privcreate(&rd, rp, r);
 221   d = rsa_privop(&rd, d, c);
 222   rsa_privdestroy(&rd);
 223   return (d);
 224 }
 225
 226 /*----- Operations with padding -------------------------------------------*/
 227
 228 /* --- @rsa_sign@ --- *
 229  *
 230  * Arguments:   @rsa_privctx *rp@ = pointer to an RSA private key context
 231  *              @const void *m@ = pointer to input message
 232  *              @size_t sz@ = size of input message
 233  *              @dstr *d@ = pointer to output string
 234  *              @rsa_encodeproc e@ = encoding procedure
 235  *              @void *earg@ = argument pointer for encoding procedure
 236  *
 237  * Returns:     The length of the output string if successful, negative on
 238  *              failure.
 239  *
 240  * Use:         Computes an RSA digital signature.
 241  */
 242
 243 int rsa_sign(rsa_privctx *rp, const void *m, size_t sz,
 244              dstr *d, rsa_encodeproc e, void *earg)
 245 {
 246   mp *x;
 247   size_t n = mp_octets(rp->rp->n);
 248   octet *p;
 249   int rc;
 250
 251   /* --- Sort out some space --- */
 252
 253   dstr_ensure(d, n);
 254   p = (octet *)d->buf + d->len;
 255   p[0] = 0;
 256
 257   /* --- Do the packing --- */
 258
 259   if ((rc = e(m, sz, p, n, earg)) < 0)
 260     return (rc);
 261
 262   /* --- Do the encryption --- */
 263
 264   x = mp_loadb(MP_NEWSEC, p, n);
 265   x = rsa_privop(rp, x, x);
 266   mp_storeb(x, p, n);
 267   d->len += n;
 268   mp_drop(x);
 269   return (n);
 270 }
 271
 272 /* --- @rsa_decrypt@ --- *
 273  *
 274  * Arguments:   @rsa_privctx *rp@ = pointer to an RSA private key context
 275  *              @const void *m@ = pointer to input message
 276  *              @size_t sz@ = size of input message
 277  *              @dstr *d@ = pointer to output string
 278  *              @rsa_decodeproc e@ = decoding procedure
 279  *              @void *earg@ = argument pointer for decoding procedure
 280  *
 281  * Returns:     The length of the output string if successful, negative on
 282  *              failure.
 283  *
 284  * Use:         Does RSA signature verification.
 285  */
 286
 287 int rsa_decrypt(rsa_privctx *rp, const void *m, size_t sz,
 288                dstr *d, rsa_decodeproc e, void *earg)
 289 {
 290   mp *x;
 291   size_t n = mp_octets(rp->rp->n);
 292   octet *p;
 293   int rc;
 294
 295   /* --- Do the exponentiation --- */
 296
 297   p = x_alloc(d->a, n);
 298   x = mp_loadb(MP_NEW, m, sz);
 299   x = rsa_privop(rp, x, x);
 300   mp_storeb(x, p, n);
 301   mp_drop(x);
 302
 303   /* --- Do the decoding --- */
 304
 305   rc = e(p, n, d, earg);
 306   x_free(d->a, p);
 307   return (rc);
 308 }
 309
 310 /*----- That's all, folks -------------------------------------------------*/