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 #include <mLib/macros.h>
  33
  34 #include "mp.h"
  35 #include "mpmont.h"
  36 #include "rsa.h"
  37
  38 /*----- Public key operations ---------------------------------------------*/
  39
  40 /* --- @rsa_pubcreate@ --- *
  41  *
  42  * Arguments:   @rsa_pubctx *rd@ = pointer to an RSA public key context
  43  *              @rsa_pub *rp@ = pointer to RSA public key
  44  *
  45  * Returns:     ---
  46  *
  47  * Use:         Initializes an RSA public-key context.
  48  */
  49
  50 void rsa_pubcreate(rsa_pubctx *rd, rsa_pub *rp)
  51 {
  52   rd->rp = rp; mp_shrink(rp->e);
  53   mpmont_create(&rd->mm, rp->n);
  54 }
  55
  56 /* --- @rsa_pubdestroy@ --- *
  57  *
  58  * Arguments:   @rsa_pubctx *rd@ = pointer to an RSA public key context
  59  *
  60  * Returns:     ---
  61  *
  62  * Use:         Destroys an RSA public-key context.
  63  */
  64
  65 void rsa_pubdestroy(rsa_pubctx *rd)
  66 {
  67   mpmont_destroy(&rd->mm);
  68 }
  69
  70 /* --- @rsa_pubop@ --- *
  71  *
  72  * Arguments:   @rsa_pubctx *rd@ = pointer to an RSA public key context
  73  *              @mp *d@ = destination
  74  *              @mp *p@ = input message
  75  *
  76  * Returns:     The transformed output message.
  77  *
  78  * Use:         Performs an RSA public key operation.
  79  */
  80
  81 mp *rsa_pubop(rsa_pubctx *rd, mp *d, mp *p)
  82 {
  83   mp *e = rd->rp->e;
  84   unsigned i;
  85
  86   if (MP_EQ(e, MP_THREE)) {
  87     MP_COPY(p);
  88     d = mpmont_mul(&rd->mm, d, p, rd->mm.r2);
  89     d = mp_sqr(d, d); d = mpmont_reduce(&rd->mm, d, d);
  90     d = mpmont_mul(&rd->mm, d, d, p);
  91     MP_DROP(p);
  92     return (d);
  93   }
  94 #if MPW_BITS > 16
  95   if (MP_LEN(e) == 1 && e->v[0] == 65537)
  96 #else
  97   if (0 && MP_LEN(e) == 2 && e->v[0] == 1 && e->v[1] == (1 << (16 - MPW_BITS)))
  98 #endif
  99   {
 100     MP_COPY(p);
 101     d = mpmont_mul(&rd->mm, d, p, rd->mm.r2);
 102     for (i = 0; i < 16; i++)
 103       { d = mp_sqr(d, d); d = mpmont_reduce(&rd->mm, d, d); }
 104     d = mpmont_mul(&rd->mm, d, d, p);
 105     MP_DROP(p);
 106     return (d);
 107   }
 108   return (mpmont_exp(&rd->mm, d, p, rd->rp->e));
 109 }
 110
 111 /* --- @rsa_qpubop@ --- *
 112  *
 113  * Arguments:   @rsa_pub *rp@ = pointer to RSA parameters
 114  *              @mp *d@ = destination
 115  *              @mp *p@ = input message
 116  *
 117  * Returns:     Correctly transformed output message.
 118  *
 119  * Use:         Performs an RSA public key operation.
 120  */
 121
 122 mp *rsa_qpubop(rsa_pub *rp, mp *d, mp *c)
 123 {
 124   rsa_pubctx rd;
 125   rsa_pubcreate(&rd, rp);
 126   d = rsa_pubop(&rd, d, c);
 127   rsa_pubdestroy(&rd);
 128   return (d);
 129 }
 130
 131 /*----- Operations with padding -------------------------------------------*/
 132
 133 /* --- @rsa_encrypt@ --- *
 134  *
 135  * Arguments:   @rsa_pubctx *rp@ = pointer to an RSA public key context
 136  *              @mp *d@ = proposed destination integer
 137  *              @const void *m@ = pointer to input message
 138  *              @size_t msz@ = size of input message
 139  *              @rsa_pad *e@ = encoding procedure
 140  *              @void *earg@ = argument pointer for encoding procedure
 141  *
 142  * Returns:     The encrypted message, as a multiprecision integer, or null
 143  *              on failure.
 144  *
 145  * Use:         Does RSA encryption.
 146  */
 147
 148 mp *rsa_encrypt(rsa_pubctx *rp, mp *d, const void *m, size_t msz,
 149                 rsa_pad *e, void *earg)
 150 {
 151   octet *p;
 152   unsigned long nb = mp_bits(rp->rp->n);
 153   size_t n = (nb + 7)/8;
 154   arena *a = d && d->a ? d->a->a : arena_global;
 155
 156   p = x_alloc(a, n);
 157   d = e(d, m, msz, p, n, nb, earg);
 158   x_free(a, p);
 159   return (d ? rsa_pubop(rp, d, d) : 0);
 160 }
 161
 162 /* --- @rsa_verify@ --- *
 163  *
 164  * Arguments:   @rsa_pubctx *rp@ = pointer to an RSA public key contxt
 165  *              @mp *s@ = the signature, as a multiprecision integer
 166  *              @const void *m@ = pointer to message to verify, or null
 167  *              @size_t msz@ = size of input message
 168  *              @dstr *d@ = pointer to output string, or null
 169  *              @rsa_vfrunpad *e@ = decoding procedure
 170  *              @void *earg@ = argument pointer for decoding procedure
 171  *
 172  * Returns:     The length of the output string if successful (0 if no output
 173  *              was wanted); negative on failure.
 174  *
 175  * Use:         Does RSA signature verification.  To use a signature scheme
 176  *              with recovery, pass in @m == 0@ and @d != 0@: the recovered
 177  *              message should appear in @d@.  To use a signature scheme with
 178  *              appendix, provide @m != 0@ and @d == 0@; the result should be
 179  *              zero for success.
 180  */
 181
 182 int rsa_verify(rsa_pubctx *rp, mp *s, const void *m, size_t msz,
 183                dstr *d, rsa_vrfunpad *e, void *earg)
 184 {
 185   mp *p = rsa_pubop(rp, MP_NEW, s);
 186   unsigned long nb = mp_bits(rp->rp->n);
 187   size_t n = (nb + 7)/8;
 188   dstr dd = DSTR_INIT;
 189   int rc;
 190
 191   /* --- Decoder protocol --- *
 192    *
 193    * We deal with two kinds of decoders: ones with message recovery and ones
 194    * with appendix.  A decoder with recovery will leave a message in the
 195    * buffer and exit nonzero: we'll check that against @m@ if provided and
 196    * just leave it otherwise.  A decoder with appendix will inspect @m@ and
 197    * return zero or @-1@ itself.
 198    */
 199
 200   if (!d) d = &dd;
 201   dstr_ensure(d, n);
 202   rc = e(p, m, msz, (octet *)d->buf + d->len, n, nb, earg);
 203   if (rc > 0 && m) {
 204     if (rc != msz || MEMCMP(d->buf + d->len, !=, m, msz))
 205       rc = -1;
 206     else
 207       rc = 0;
 208   }
 209   if (rc > 0)
 210     d->len += rc;
 211   mp_drop(p);
 212   dstr_destroy(&dd);
 213   return (rc);
 214 }
 215
 216 /*----- That's all, folks -------------------------------------------------*/