Rearrange the file tree.

[u/mdw/catacomb] / pub / rsa-priv.c

/* -*-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 <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 -------------------------------------------------*/