+++ /dev/null
-/* -*-c-*-
- *
- * $Id: rsa-priv.c,v 1.4 2004/04/08 01:36:15 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.
- */
-
-/*----- 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_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 -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff