--- /dev/null
+/* -*-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 <mLib/alloc.h>
+#include <mLib/bits.h>
+#include <mLib/dstr.h>
+
+#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 -------------------------------------------------*/
projects / u / mdw / catacomb / commitdiff