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

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