git.distorted.org.uk Git - u/mdw/catacomb/blob - dsa-verify.c

   1 /* -*-c-*-
   2  *
   3  * $Id: dsa-verify.c,v 1.6 2001/06/16 12:56:38 mdw Exp $
   4  *
   5  * DSA signature verification
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: dsa-verify.c,v $
  33  * Revision 1.6  2001/06/16 12:56:38  mdw
  34  * Fixes for interface change to @mpmont_expr@ and @mpmont_mexpr@.
  35  *
  36  * Revision 1.5  2000/10/08 12:13:17  mdw
  37  * Use @MP_EQ@ instead of @MP_CMP@.
  38  *
  39  * Revision 1.4  2000/06/17 10:53:35  mdw
  40  * Typesetting fixes.
  41  *
  42  * Revision 1.3  1999/12/10 23:18:38  mdw
  43  * Change interface for suggested destinations.
  44  *
  45  * Revision 1.2  1999/11/23 00:20:04  mdw
  46  * Remove stray debugging code.
  47  *
  48  * Revision 1.1  1999/11/19 19:28:00  mdw
  49  * Implementation of the Digital Signature Algorithm.
  50  *
  51  */
  52
  53 /*----- Header files ------------------------------------------------------*/
  54
  55 #include "dsa.h"
  56 #include "mp.h"
  57 #include "mpmont.h"
  58
  59 /*----- Main code ---------------------------------------------------------*/
  60
  61 /* --- @dsa_vrfy@ --- *
  62  *
  63  * Arguments:   @const dsa_param *dp@ = pointer to DSA parameters
  64  *              @mp *y@ = public verification key
  65  *              @mp *m@ = message which was signed
  66  *              @mp *r, *s@ = the signature
  67  *
  68  * Returns:     Zero if the signature is a forgery, nonzero if it's valid.
  69  *
  70  * Use:         Verifies a DSA digital signature.
  71  */
  72
  73 int dsa_vrfy(const dsa_param *dp, mp *y, mp *m, mp *r, mp *s)
  74 {
  75   mpmont pm, qm;
  76   mp *w;
  77   mp_expfactor f[2];
  78   int ok;
  79
  80   /* --- Ensure that all of the signature bits are in range --- */
  81
  82   if ((r->f | s->f) & MP_NEG)
  83     return (0);
  84   if (MP_CMP(r, >=, dp->q) || MP_CMP(s, >=, dp->q))
  85     return (0);
  86
  87   /* --- Set up Montgomery contexts --- */
  88
  89   mpmont_create(&pm, dp->p);
  90   mpmont_create(&qm, dp->q);
  91
  92   /* --- Compute %$w = s^{-1} \bmod q$% --- */
  93
  94   {
  95     mp *z = MP_NEW;
  96     mp_gcd(0, 0, &z, dp->q, s);
  97     w = mpmont_mul(&qm, MP_NEW, z, qm.r2);
  98     mp_drop(z);
  99   }
 100
 101   /* --- Compute %$wr$% and %$wm$% --- */
 102
 103   f[0].exp = mpmont_mul(&qm, MP_NEW, w, m);
 104   f[1].exp = mpmont_mul(&qm, MP_NEW, w, r);
 105   mp_drop(w);
 106   mpmont_destroy(&qm);
 107
 108   /* --- Do the exponentiation and take residue mod @q@ --- */
 109
 110   f[0].base = dp->g;
 111   f[1].base = y;
 112   w = mpmont_mexp(&pm, MP_NEW, f, 2);
 113   mp_div(0, &w, w, dp->q);
 114   ok = MP_EQ(w, r);
 115
 116   /* --- Tidy up --- */
 117
 118   mp_drop(w);
 119   mp_drop(f[0].exp);
 120   mp_drop(f[1].exp);
 121   mpmont_destroy(&pm);
 122   return (ok);
 123 }
 124
 125 /* --- @dsa_verify@ --- *
 126  *
 127  * Arguments:   @const dsa_param *dp@ = pointer to DSA parameters
 128  *              @mp *y@ = public verification key
 129  *              @const void *m@ = pointer to message block
 130  *              @size_t msz@ = size of message block
 131  *              @const void *r@ = pointer to @r@ signature half
 132  *              @size_t rsz@ = size of @r@
 133  *              @const void *s@ = pointer to @s@ signature half
 134  *              @size_t ssz@ = size of @s@
 135  *
 136  * Returns:     Zero if the signature is a forgery, nonzero if it's valid.
 137  *
 138  * Use:         Verifies a DSA digital signature.
 139  */
 140
 141 int dsa_verify(const dsa_param *dp, mp *y,
 142                const void *m, size_t msz,
 143                const void *r, size_t rsz,
 144                const void *s, size_t ssz)
 145 {
 146   mp *mm = mp_loadb(MP_NEW, m, msz);
 147   mp *rm = mp_loadb(MP_NEW, r, rsz);
 148   mp *sm = mp_loadb(MP_NEW, s, ssz);
 149   int ok = dsa_vrfy(dp, y, mm, rm, sm);
 150   mp_drop(mm);
 151   mp_drop(rm);
 152   mp_drop(sm);
 153   return (ok);
 154 }
 155
 156 /*----- Test rig ----------------------------------------------------------*/
 157
 158 #ifdef TEST_RIG
 159
 160 #include <mLib/testrig.h>
 161
 162 #include "sha.h"
 163
 164 static int verify(int good, dstr *v)
 165 {
 166   dsa_param dp;
 167   mp *y;
 168   sha_ctx c;
 169   octet hash[SHA_HASHSZ];
 170   int ok = 1;
 171   int rc;
 172
 173   dp.q = *(mp **)v[0].buf;
 174   dp.p = *(mp **)v[1].buf;
 175   dp.g = *(mp **)v[2].buf;
 176   y = *(mp **)v[3].buf;
 177
 178   sha_init(&c);
 179   sha_hash(&c, v[4].buf, v[4].len);
 180   sha_done(&c, hash);
 181
 182   rc = dsa_verify(&dp, y, hash, sizeof(hash),
 183                   v[5].buf, v[5].len, v[6].buf, v[6].len);
 184
 185   if (!rc != !good) {
 186     if (good)
 187       fputs("\n*** verification failed", stderr);
 188     else
 189       fputs("\n*** verification succeeded", stderr);
 190     fputs("\nq = ", stderr); mp_writefile(dp.q, stderr, 16);
 191     fputs("\np = ", stderr); mp_writefile(dp.p, stderr, 16);
 192     fputs("\ng = ", stderr); mp_writefile(dp.g, stderr, 16);
 193     fputs("\ny = ", stderr); mp_writefile(y, stderr, 16);
 194     fprintf(stderr, "\nmessage = `%s'", v[4].buf);
 195     fputs("\nr = ", stderr); type_hex.dump(&v[5], stderr);
 196     fputs("\ns = ", stderr); type_hex.dump(&v[6], stderr);
 197     fputc('\n', stderr);
 198     ok = 0;
 199   }
 200
 201   mp_drop(dp.p);
 202   mp_drop(dp.q);
 203   mp_drop(dp.g);
 204   mp_drop(y);
 205   assert(mparena_count(MPARENA_GLOBAL) == 0);
 206   return (ok);
 207 }
 208
 209 static int vgood(dstr *v) { return verify(1, v); }
 210 static int vbad(dstr *v) { return verify(0, v); }
 211
 212 static test_chunk tests[] = {
 213   { "verify-good", vgood,
 214     { &type_mp, &type_mp, &type_mp, &type_mp,
 215       &type_string, &type_hex, &type_hex, 0 } },
 216   { "verify-bad", vbad,
 217     { &type_mp, &type_mp, &type_mp, &type_mp,
 218       &type_string, &type_hex, &type_hex, 0 } },
 219   { 0, 0, { 0 } }
 220 };
 221
 222 int main(int argc, char *argv[])
 223 {
 224   sub_init();
 225   test_run(argc, argv, tests, SRCDIR "/tests/dsa");
 226   return (0);
 227 }
 228
 229 #endif
 230
 231 /*----- That's all, folks -------------------------------------------------*/