chiark - git - mdw - catacomb/blob - rsa-priv.c

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