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

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