Pollard's rho algorithm for computing discrete logs.

[u/mdw/catacomb] / dsa-verify.c

/* -*-c-*-
 *
 * $Id: dsa-verify.c,v 1.4 2000/06/17 10:53:35 mdw Exp $
 *
 * DSA signature verification
 *
 * (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: dsa-verify.c,v $
 * Revision 1.4  2000/06/17 10:53:35  mdw
 * Typesetting fixes.
 *
 * Revision 1.3  1999/12/10 23:18:38  mdw
 * Change interface for suggested destinations.
 *
 * Revision 1.2  1999/11/23 00:20:04  mdw
 * Remove stray debugging code.
 *
 * Revision 1.1  1999/11/19 19:28:00  mdw
 * Implementation of the Digital Signature Algorithm.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include "dsa.h"
#include "mp.h"
#include "mpmont.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @dsa_vrfy@ --- *
 *
 * Arguments:   @const dsa_param *dp@ = pointer to DSA parameters
 *              @mp *y@ = public verification key
 *              @mp *m@ = message which was signed
 *              @mp *r, *s@ = the signature
 *
 * Returns:     Zero if the signature is a forgery, nonzero if it's valid.
 *
 * Use:         Verifies a DSA digital signature.
 */

int dsa_vrfy(const dsa_param *dp, mp *y, mp *m, mp *r, mp *s)
{
  mpmont pm, qm;
  mp *w;
  mpmont_factor f[2];
  int ok;

  /* --- Ensure that all of the signature bits are in range --- */

  if ((r->f | s->f) & MP_NEG)
    return (0);
  if (MP_CMP(r, >=, dp->q) || MP_CMP(s, >=, dp->q))
    return (0);

  /* --- Set up Montgomery contexts --- */

  mpmont_create(&pm, dp->p);
  mpmont_create(&qm, dp->q);

  /* --- Compute %$w = s^{-1} \bmod q$% --- */

  {
    mp *z = MP_NEW;
    mp_gcd(0, 0, &z, dp->q, s);
    w = mpmont_mul(&qm, MP_NEW, z, qm.r2);
    mp_drop(z);
  }

  /* --- Compute %$wr$% and %$wm$% --- */

  f[0].exp = mpmont_mul(&qm, MP_NEW, w, m);
  f[1].exp = mpmont_mul(&qm, MP_NEW, w, r);
  mp_drop(w);
  mpmont_destroy(&qm);

  /* --- Do the exponentiation and take residue mod @q@ --- */

  f[0].base = dp->g;
  f[1].base = y;
  w = mpmont_mexp(&pm, MP_NEW, f, 2);
  mp_div(0, &w, w, dp->q);
  ok = MP_CMP(w, ==, r);

  /* --- Tidy up --- */

  mp_drop(w);
  mp_drop(f[0].exp);
  mp_drop(f[1].exp);
  mpmont_destroy(&pm);
  return (ok);
}

/* --- @dsa_verify@ --- *
 *
 * Arguments:   @const dsa_param *dp@ = pointer to DSA parameters
 *              @mp *y@ = public verification key
 *              @const void *m@ = pointer to message block
 *              @size_t msz@ = size of message block
 *              @const void *r@ = pointer to @r@ signature half
 *              @size_t rsz@ = size of @r@
 *              @const void *s@ = pointer to @s@ signature half
 *              @size_t ssz@ = size of @s@
 *
 * Returns:     Zero if the signature is a forgery, nonzero if it's valid.
 *
 * Use:         Verifies a DSA digital signature.
 */

int dsa_verify(const dsa_param *dp, mp *y,
               const void *m, size_t msz,
               const void *r, size_t rsz,
               const void *s, size_t ssz)
{
  mp *mm = mp_loadb(MP_NEW, m, msz);
  mp *rm = mp_loadb(MP_NEW, r, rsz);
  mp *sm = mp_loadb(MP_NEW, s, ssz);
  int ok = dsa_vrfy(dp, y, mm, rm, sm);
  mp_drop(mm);
  mp_drop(rm);
  mp_drop(sm);
  return (ok);
}

/*----- Test rig ----------------------------------------------------------*/

#ifdef TEST_RIG

#include <mLib/testrig.h>

#include "sha.h"

static int verify(int good, dstr *v)
{
  dsa_param dp;
  mp *y;
  sha_ctx c;
  octet hash[SHA_HASHSZ];
  int ok = 1;
  int rc;

  dp.q = *(mp **)v[0].buf;
  dp.p = *(mp **)v[1].buf;
  dp.g = *(mp **)v[2].buf;
  y = *(mp **)v[3].buf;

  sha_init(&c);
  sha_hash(&c, v[4].buf, v[4].len);
  sha_done(&c, hash);

  rc = dsa_verify(&dp, y, hash, sizeof(hash),
                  v[5].buf, v[5].len, v[6].buf, v[6].len);

  if (!rc != !good) {
    if (good)
      fputs("\n*** verification failed", stderr);
    else
      fputs("\n*** verification succeeded", stderr);
    fputs("\nq = ", stderr); mp_writefile(dp.q, stderr, 16);
    fputs("\np = ", stderr); mp_writefile(dp.p, stderr, 16);
    fputs("\ng = ", stderr); mp_writefile(dp.g, stderr, 16);
    fputs("\ny = ", stderr); mp_writefile(y, stderr, 16);
    fprintf(stderr, "\nmessage = `%s'", v[4].buf);
    fputs("\nr = ", stderr); type_hex.dump(&v[5], stderr);
    fputs("\ns = ", stderr); type_hex.dump(&v[6], stderr);
    fputc('\n', stderr);
    ok = 0;
  }

  mp_drop(dp.p);
  mp_drop(dp.q);
  mp_drop(dp.g);
  mp_drop(y);
  assert(mparena_count(MPARENA_GLOBAL) == 0);
  return (ok);
}

static int vgood(dstr *v) { return verify(1, v); }
static int vbad(dstr *v) { return verify(0, v); }

static test_chunk tests[] = {
  { "verify-good", vgood,
    { &type_mp, &type_mp, &type_mp, &type_mp,
      &type_string, &type_hex, &type_hex, 0 } },
  { "verify-bad", vbad,
    { &type_mp, &type_mp, &type_mp, &type_mp,
      &type_string, &type_hex, &type_hex, 0 } },
  { 0, 0, { 0 } }
};

int main(int argc, char *argv[])
{
  sub_init();
  test_run(argc, argv, tests, SRCDIR "/tests/dsa");
  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/