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

   1 /* -*-c-*-
   2  *
   3  * [RSA encryption with padding *
   4  * (c) 2000 Straylight/Edgeware
   5  */
   6
   7 /*----- Licensing notice --------------------------------------------------*
   8  *
   9  * This file is part of Catacomb.
  10  *
  11  * Catacomb is free software; you can redistribute it and/or modify
  12  * it under the terms of the GNU Library General Public License as
  13  * published by the Free Software Foundation; either version 2 of the
  14  * License, or (at your option) any later version.
  15  *
  16  * Catacomb is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU Library General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Library General Public
  22  * License along with Catacomb; if not, write to the Free
  23  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  24  * MA 02111-1307, USA.
  25  */
  26
  27 /*----- Header files ------------------------------------------------------*/
  28
  29 #include <mLib/alloc.h>
  30 #include <mLib/bits.h>
  31 #include <mLib/dstr.h>
  32
  33 #include "mp.h"
  34 #include "mpmont.h"
  35 #include "rsa.h"
  36
  37 /*----- Public key operations ---------------------------------------------*/
  38
  39 /* --- @rsa_pubcreate@ --- *
  40  *
  41  * Arguments:   @rsa_pubctx *rd@ = pointer to an RSA public key context
  42  *              @rsa_pub *rp@ = pointer to RSA public key
  43  *
  44  * Returns:     ---
  45  *
  46  * Use:         Initializes an RSA public-key context.
  47  */
  48
  49 void rsa_pubcreate(rsa_pubctx *rd, rsa_pub *rp)
  50 {
  51   rd->rp = rp; mp_shrink(rp->e);
  52   mpmont_create(&rd->mm, rp->n);
  53 }
  54
  55 /* --- @rsa_pubdestroy@ --- *
  56  *
  57  * Arguments:   @rsa_pubctx *rd@ = pointer to an RSA public key context
  58  *
  59  * Returns:     ---
  60  *
  61  * Use:         Destroys an RSA public-key context.
  62  */
  63
  64 void rsa_pubdestroy(rsa_pubctx *rd)
  65 {
  66   mpmont_destroy(&rd->mm);
  67 }
  68
  69 /* --- @rsa_pubop@ --- *
  70  *
  71  * Arguments:   @rsa_pubctx *rd@ = pointer to an RSA public key context
  72  *              @mp *d@ = destination
  73  *              @mp *p@ = input message
  74  *
  75  * Returns:     The transformed output message.
  76  *
  77  * Use:         Performs an RSA public key operation.
  78  */
  79
  80 mp *rsa_pubop(rsa_pubctx *rd, mp *d, mp *p)
  81 {
  82   mp *e = rd->rp->e;
  83   unsigned i;
  84
  85   if (MP_EQ(e, MP_THREE)) {
  86     MP_COPY(p);
  87     d = mpmont_mul(&rd->mm, d, p, rd->mm.r2);
  88     d = mp_sqr(d, d); d = mpmont_reduce(&rd->mm, d, d);
  89     d = mpmont_mul(&rd->mm, d, d, p);
  90     MP_DROP(p);
  91     return (d);
  92   }
  93 #if MPW_BITS > 16
  94   if (MP_LEN(e) == 1 && e->v[0] == 65537)
  95 #else
  96   if (0 && MP_LEN(e) == 2 && e->v[0] == 1 && e->v[1] == (1 << (16 - MPW_BITS)))
  97 #endif
  98   {
  99     MP_COPY(p);
 100     d = mpmont_mul(&rd->mm, d, p, rd->mm.r2);
 101     for (i = 0; i < 16; i++)
 102       { d = mp_sqr(d, d); d = mpmont_reduce(&rd->mm, d, d); }
 103     d = mpmont_mul(&rd->mm, d, d, p);
 104     MP_DROP(p);
 105     return (d);
 106   }
 107   return (mpmont_exp(&rd->mm, d, p, rd->rp->e));
 108 }
 109
 110 /* --- @rsa_qpubop@ --- *
 111  *
 112  * Arguments:   @rsa_pub *rp@ = pointer to RSA parameters
 113  *              @mp *d@ = destination
 114  *              @mp *p@ = input message
 115  *
 116  * Returns:     Correctly transformed output message.
 117  *
 118  * Use:         Performs an RSA public key operation.
 119  */
 120
 121 mp *rsa_qpubop(rsa_pub *rp, mp *d, mp *c)
 122 {
 123   rsa_pubctx rd;
 124   rsa_pubcreate(&rd, rp);
 125   d = rsa_pubop(&rd, d, c);
 126   rsa_pubdestroy(&rd);
 127   return (d);
 128 }
 129
 130 /*----- Operations with padding -------------------------------------------*/
 131
 132 /* --- @rsa_encrypt@ --- *
 133  *
 134  * Arguments:   @rsa_pubctx *rp@ = pointer to an RSA public key context
 135  *              @mp *d@ = proposed destination integer
 136  *              @const void *m@ = pointer to input message
 137  *              @size_t msz@ = size of input message
 138  *              @rsa_pad *e@ = encoding procedure
 139  *              @void *earg@ = argument pointer for encoding procedure
 140  *
 141  * Returns:     The encrypted message, as a multiprecision integer, or null
 142  *              on failure.
 143  *
 144  * Use:         Does RSA encryption.
 145  */
 146
 147 mp *rsa_encrypt(rsa_pubctx *rp, mp *d, const void *m, size_t msz,
 148                 rsa_pad *e, void *earg)
 149 {
 150   octet *p;
 151   unsigned long nb = mp_bits(rp->rp->n);
 152   size_t n = (nb + 7)/8;
 153   arena *a = d && d->a ? d->a->a : arena_global;
 154
 155   p = x_alloc(a, n);
 156   d = e(d, m, msz, p, n, nb, earg);
 157   x_free(a, p);
 158   return (d ? rsa_pubop(rp, d, d) : 0);
 159 }
 160
 161 /* --- @rsa_verify@ --- *
 162  *
 163  * Arguments:   @rsa_pubctx *rp@ = pointer to an RSA public key contxt
 164  *              @mp *s@ = the signature, as a multiprecision integer
 165  *              @const void *m@ = pointer to message to verify, or null
 166  *              @size_t msz@ = size of input message
 167  *              @dstr *d@ = pointer to output string, or null
 168  *              @rsa_vfrunpad *e@ = decoding procedure
 169  *              @void *earg@ = argument pointer for decoding procedure
 170  *
 171  * Returns:     The length of the output string if successful (0 if no output
 172  *              was wanted); negative on failure.
 173  *
 174  * Use:         Does RSA signature verification.  To use a signature scheme
 175  *              with recovery, pass in @m == 0@ and @d != 0@: the recovered
 176  *              message should appear in @d@.  To use a signature scheme with
 177  *              appendix, provide @m != 0@ and @d == 0@; the result should be
 178  *              zero for success.
 179  */
 180
 181 int rsa_verify(rsa_pubctx *rp, mp *s, const void *m, size_t msz,
 182                dstr *d, rsa_vrfunpad *e, void *earg)
 183 {
 184   mp *p = rsa_pubop(rp, MP_NEW, s);
 185   unsigned long nb = mp_bits(rp->rp->n);
 186   size_t n = (nb + 7)/8;
 187   dstr dd = DSTR_INIT;
 188   int rc;
 189
 190   /* --- Decoder protocol --- *
 191    *
 192    * We deal with two kinds of decoders: ones with message recovery and ones
 193    * with appendix.  A decoder with recovery will leave a message in the
 194    * buffer and exit nonzero: we'll check that against @m@ if provided and
 195    * just leave it otherwise.  A decoder with appendix will inspect @m@ and
 196    * return zero or @-1@ itself.
 197    */
 198
 199   if (!d) d = &dd;
 200   dstr_ensure(d, n);
 201   rc = e(p, m, msz, (octet *)d->buf + d->len, n, nb, earg);
 202   if (rc > 0 && m) {
 203     if (rc != msz || memcmp(d->buf + d->len, m, msz) != 0)
 204       rc = -1;
 205     else
 206       rc = 0;
 207   }
 208   if (rc > 0)
 209     d->len += rc;
 210   mp_drop(p);
 211   dstr_destroy(&dd);
 212   return (rc);
 213 }
 214
 215 /*----- That's all, folks -------------------------------------------------*/