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

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