chiark - git - mdw - catacomb/blob - dsa-verify.c

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