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

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