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

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