From: mdw Date: Sat, 1 Jul 2000 11:23:20 +0000 (+0000) Subject: Renamed from `rsa-decrypt', since the name was no longer appropriate. X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/c760149fcb65296defd1af967fbfa098bd83143a Renamed from `rsa-decrypt', since the name was no longer appropriate. Add functions for doing padded RSA decryption and signing. --- diff --git a/rsa-priv.c b/rsa-priv.c new file mode 100644 index 0000000..65c4b00 --- /dev/null +++ b/rsa-priv.c @@ -0,0 +1,303 @@ +/* -*-c-*- + * + * $Id: rsa-priv.c,v 1.1 2000/07/01 11:23:20 mdw Exp $ + * + * RSA private-key operations + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: rsa-priv.c,v $ + * Revision 1.1 2000/07/01 11:23:20 mdw + * Renamed from `rsa-decrypt', since the name was no longer appropriate. + * Add functions for doing padded RSA decryption and signing. + * + * --- Previous lives as rsa-decrypt.c --- + * + * Revision 1.2 2000/06/17 11:57:56 mdw + * Improve bulk performance by making better use of Montgomery + * multiplication and separating out initialization and finalization from + * the main code. + * + * Revision 1.1 1999/12/22 15:50:45 mdw + * Initial RSA support. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include "mp.h" +#include "mpmont.h" +#include "mprand.h" +#include "rsa.h" + +/*----- Public key operations ---------------------------------------------*/ + +/* --- @rsa_privcreate@ --- * + * + * Arguments: @rsa_privctx *rd@ = pointer to an RSA private key context + * @rsa_priv *rp@ = pointer to RSA private key + * @grand *r@ = pointer to random number source for blinding + * + * Returns: --- + * + * Use: Initializes an RSA private-key context. Keeping a context + * for several decryption or signing operations provides a minor + * performance benefit. + * + * The random number source may be null if blinding is not + * desired. This improves decryption speed, at the risk of + * permitting timing attacks. + */ + +void rsa_privcreate(rsa_privctx *rd, rsa_priv *rp, grand *r) +{ + rd->rp = rp; + rd->r = r; + if (r) + mpmont_create(&rd->nm, rp->n); + mpmont_create(&rd->pm, rp->p); + mpmont_create(&rd->qm, rp->q); +} + +/* --- @rsa_privdestroy@ --- * + * + * Arguments: @rsa_privctx *rd@ = pointer to an RSA decryption context + * + * Returns: --- + * + * Use: Destroys an RSA decryption context. + */ + +void rsa_privdestroy(rsa_privctx *rd) +{ + if (rd->r) + mpmont_destroy(&rd->nm); + mpmont_destroy(&rd->pm); + mpmont_destroy(&rd->qm); +} + +/* --- @rsa_privop@ --- * + * + * Arguments: @rsa_privctx *rd@ = pointer to RSA private key context + * @mp *d@ = destination + * @mp *c@ = input message + * + * Returns: The transformed output message. + * + * Use: Performs an RSA private key operation. This function takes + * advantage of knowledge of the key factors in order to speed + * up decryption. It also blinds the ciphertext prior to + * decryption and unblinds it afterwards to thwart timing + * attacks. + */ + +mp *rsa_privop(rsa_privctx *rd, mp *d, mp *c) +{ + mp *ki = MP_NEW; + rsa_priv *rp = rd->rp; + + /* --- If so desired, set up a blinding constant --- * + * + * Choose a constant %$k$% relatively prime to the modulus %$m$%. Compute + * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%. Don't bother with the + * CRT stuff here because %$e$% is chosen to be small. + */ + + c = MP_COPY(c); + if (rd->r) { + mp *k = MP_NEWSEC, *g = MP_NEW; + + do { + k = mprand_range(k, rp->n, rd->r, 0); + mp_gcd(&g, 0, &ki, rp->n, k); + } while (MP_CMP(g, !=, MP_ONE)); + k = mpmont_expr(&rd->nm, k, k, rp->e); + c = mpmont_mul(&rd->nm, c, c, k); + mp_drop(k); + mp_drop(g); + } + + /* --- Do the actual modular exponentiation --- * + * + * Use a slightly hacked version of the Chinese Remainder Theorem stuff. + * + * Let %$q' = q^{-1} \bmod p$%. Then note that + * %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$% + */ + + { + mp *cp = MP_NEW, *cq = MP_NEW; + + /* --- Work out the two halves of the result --- */ + + mp_div(0, &cp, c, rp->p); + cp = mpmont_exp(&rd->pm, cp, cp, rp->dp); + + mp_div(0, &cq, c, rp->q); + cq = mpmont_exp(&rd->qm, cq, cq, rp->dq); + + /* --- Combine the halves using the result above --- */ + + d = mp_sub(d, cp, cq); + mp_div(0, &d, d, rp->p); + d = mpmont_mul(&rd->pm, d, d, rp->q_inv); + d = mpmont_mul(&rd->pm, d, d, rd->pm.r2); + + d = mp_mul(d, d, rp->q); + d = mp_add(d, d, cq); + if (MP_CMP(d, >=, rp->n)) + d = mp_sub(d, d, rp->n); + + /* --- Tidy away temporary variables --- */ + + mp_drop(cp); + mp_drop(cq); + } + + /* --- Finally, possibly remove the blinding factor --- */ + + if (ki) { + d = mpmont_mul(&rd->nm, d, d, ki); + d = mpmont_mul(&rd->nm, d, d, rd->nm.r2); + mp_drop(ki); + } + + /* --- Done --- */ + + mp_drop(c); + return (d); +} + +/* --- @rsa_qprivop@ --- * + * + * Arguments: @rsa_priv *rp@ = pointer to RSA parameters + * @mp *d@ = destination + * @mp *c@ = input message + * @grand *r@ = pointer to random number source for blinding + * + * Returns: Correctly transformed output message + * + * Use: Performs an RSA private key operation, very carefully. + */ + +mp *rsa_qprivop(rsa_priv *rp, mp *d, mp *c, grand *r) +{ + rsa_privctx rd; + rsa_privcreate(&rd, rp, r); + d = rsa_privop(&rd, d, c); + rsa_privdestroy(&rd); + return (d); +} + +/*----- Operations with padding -------------------------------------------*/ + +/* --- @rsa_sign@ --- * + * + * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context + * @const void *m@ = pointer to input message + * @size_t sz@ = size of input message + * @dstr *d@ = pointer to output string + * @rsa_encodeproc e@ = encoding procedure + * @void *earg@ = argument pointer for encoding procedure + * + * Returns: The length of the output string if successful, negative on + * failure. + * + * Use: Computes an RSA digital signature. + */ + +int rsa_sign(rsa_privctx *rp, const void *m, size_t sz, + dstr *d, rsa_encodeproc e, void *earg) +{ + mp *x; + size_t n = mp_octets(rp->rp->n); + octet *p; + int rc; + + /* --- Sort out some space --- */ + + dstr_ensure(d, n); + p = d->buf + d->len; + p[0] = 0; + + /* --- Do the packing --- */ + + if ((rc = e(m, sz, p, n, earg)) < 0) + return (rc); + + /* --- Do the encryption --- */ + + x = mp_loadb(MP_NEWSEC, p, n); + x = rsa_privop(rp, x, x); + mp_storeb(x, p, n); + d->len += n; + mp_drop(x); + return (n); +} + +/* --- @rsa_decrypt@ --- * + * + * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context + * @const void *m@ = pointer to input message + * @size_t sz@ = size of input message + * @dstr *d@ = pointer to output string + * @rsa_decodeproc e@ = decoding procedure + * @void *earg@ = argument pointer for decoding procedure + * + * Returns: The length of the output string if successful, negative on + * failure. + * + * Use: Does RSA signature verification. + */ + +int rsa_decrypt(rsa_privctx *rp, const void *m, size_t sz, + dstr *d, rsa_decodeproc e, void *earg) +{ + mp *x; + size_t n = mp_octets(rp->rp->n); + octet *p; + int rc; + + /* --- Do the exponentiation --- */ + + p = x_alloc(d->a, n); + x = mp_loadb(MP_NEW, m, sz); + x = rsa_privop(rp, x, x); + mp_storeb(x, p, n); + mp_drop(x); + + /* --- Do the decoding --- */ + + rc = e(p, n, d, earg); + x_free(d->a, p); + return (rc); +} + +/*----- That's all, folks -------------------------------------------------*/