X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/pub/rsa-priv.c diff --git a/pub/rsa-priv.c b/pub/rsa-priv.c new file mode 100644 index 0000000..08a8982 --- /dev/null +++ b/pub/rsa-priv.c @@ -0,0 +1,260 @@ +/* -*-c-*- + * + * 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. + */ + +/*----- 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_EQ(g, MP_ONE)); + k = mpmont_mul(&rd->nm, k, k, rd->nm.r2); + 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 + * @mp *d@ = where to put the result + * @const void *m@ = pointer to input message + * @size_t msz@ = size of input message + * @rsa_pad *e@ = encoding procedure + * @void *earg@ = argument pointer for encoding procedure + * + * Returns: The signature, as a multiprecision integer, or null on + * failure. + * + * Use: Computes an RSA digital signature. + */ + +mp *rsa_sign(rsa_privctx *rp, mp *d, const void *m, size_t msz, + rsa_pad *e, void *earg) +{ + octet *p; + unsigned long nb = mp_bits(rp->rp->n); + size_t n = (nb + 7)/8; + arena *a = d && d->a ? d->a->a : arena_global; + + p = x_alloc(a, n); + d = e(d, m, msz, p, n, nb, earg); + x_free(a, p); + return (d ? rsa_privop(rp, d, d) : 0); +} + +/* --- @rsa_decrypt@ --- * + * + * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context + * @mp *m@ = encrypted message, as a multiprecision integer + * @dstr *d@ = pointer to output string + * @rsa_decunpad *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 decryption. + */ + +int rsa_decrypt(rsa_privctx *rp, mp *m, dstr *d, + rsa_decunpad *e, void *earg) +{ + mp *p = rsa_privop(rp, MP_NEW, m); + unsigned long nb = mp_bits(rp->rp->n); + size_t n = (nb + 7)/8; + int rc; + + dstr_ensure(d, n); + rc = e(p, (octet *)d->buf + d->len, n, nb, earg); + if (rc >= 0) + d->len += rc; + mp_drop(p); + return (rc); +} + +/*----- That's all, folks -------------------------------------------------*/