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

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