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

   1 /* -*-c-*-
   2  *
   3  * $Id: dsa-sign.c,v 1.3 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * DSA signing operation
   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 "mpbarrett.h"
  35 #include "mpmont.h"
  36
  37 /*----- Main code ---------------------------------------------------------*/
  38
  39 /* --- @dsa_mksig@ --- *
  40  *
  41  * Arguments:   @const dsa_param *dp@ = pointer to DSA parameters
  42  *              @mp *a@ = secret signing key
  43  *              @mp *m@ = message to be signed
  44  *              @mp *k@ = random data
  45  *              @mp **rr, **ss@ = where to put output parameters
  46  *
  47  * Returns:     ---
  48  *
  49  * Use:         Computes a DSA signature of a message.
  50  */
  51
  52 void dsa_mksig(const dsa_param *dp, mp *a, mp *m, mp *k, mp **rr, mp **ss)
  53 {
  54   mpmont pm;
  55   mpbarrett qb;
  56   mp *k1, *r;
  57   mp *ar;
  58
  59   /* --- Compute %$r = (g^k \bmod p) \bmod q$% --- */
  60
  61   mpmont_create(&pm, dp->p);
  62   r = mpmont_exp(&pm, MP_NEW, dp->g, k);
  63   mpmont_destroy(&pm);
  64   mp_div(0, &r, r, dp->q);
  65
  66   /* --- Compute %$k^{-1} \bmod q$% --- */
  67
  68   k1 = mp_modinv(MP_NEW, k, dp->q);
  69
  70   /* --- Now for %$k^{-1}(m + ar)$% --- */
  71
  72   mpbarrett_create(&qb, dp->q);
  73   ar = mp_mul(MP_NEW, a, r);
  74   ar = mp_add(ar, ar, m);
  75   ar = mpbarrett_reduce(&qb, ar, ar);
  76   ar = mp_mul(ar, ar, k1);
  77   ar = mpbarrett_reduce(&qb, ar, ar);
  78   mpbarrett_destroy(&qb);
  79   MP_DROP(k1);
  80   if (*rr) MP_DROP(*rr);
  81   if (*ss) MP_DROP(*ss);
  82   *rr = r;
  83   *ss = ar;
  84 }
  85
  86 /* --- @dsa_sign@ --- *
  87  *
  88  * Arguments:   @dsa_param *dp@ = pointer to DSA parameters
  89  *              @mp *a@ = pointer to secret signing key
  90  *              @const void *m@ = pointer to message
  91  *              @size_t msz@ = size of the message
  92  *              @const void *k@ = secret random data for securing signature
  93  *              @size_t ksz@ = size of secret data
  94  *              @void *r@ = pointer to output space for @r@
  95  *              @size_t rsz@ = size of output space for @r@
  96  *              @void *s@ = pointer to output space for @s@
  97  *              @size_t ssz@ = size of output space for @s@
  98  *
  99  * Returns:     ---
 100  *
 101  * Use:         Signs a message, storing the results in a big-endian binary
 102  *              form.
 103  */
 104
 105 void dsa_sign(dsa_param *dp, mp *a,
 106               const void *m, size_t msz, const void *k, size_t ksz,
 107               void *r, size_t rsz, void *s, size_t ssz)
 108 {
 109   mp *mm = mp_loadb(MP_NEW, m, msz);
 110   mp *km = mp_loadb(MP_NEW, k, ksz);
 111   mp *rm = MP_NEW, *sm = MP_NEW;
 112   dsa_mksig(dp, a, mm, km, &rm, &sm);
 113   mp_storeb(rm, r, rsz);
 114   mp_storeb(sm, s, ssz);
 115   mp_drop(mm); mp_drop(km);
 116   mp_drop(rm); mp_drop(sm);
 117 }
 118
 119 /*----- Test rig ----------------------------------------------------------*/
 120
 121 #ifdef TEST_RIG
 122
 123 #include <mLib/testrig.h>
 124
 125 #include "sha.h"
 126
 127 static int verify(dstr *v)
 128 {
 129   dsa_param dp;
 130   mp *x;
 131   sha_ctx c;
 132   octet hash[SHA_HASHSZ];
 133   dsa_sig s;
 134   int ok = 1;
 135
 136   dp.q = *(mp **)v[0].buf;
 137   dp.p = *(mp **)v[1].buf;
 138   dp.g = *(mp **)v[2].buf;
 139   x = *(mp **)v[3].buf;
 140
 141   sha_init(&c);
 142   sha_hash(&c, v[4].buf, v[4].len);
 143   sha_done(&c, hash);
 144
 145   dsa_sign(&dp, x, hash, sizeof(hash), v[5].buf, v[5].len,
 146            s.r, sizeof(s.r), s.s, sizeof(s.s));
 147
 148   if (v[6].len != sizeof(s.r) || v[7].len != sizeof(s.s) ||
 149       memcmp(s.r, v[6].buf, sizeof(s.r)) != 0 ||
 150       memcmp(s.s, v[7].buf, sizeof(s.s)) != 0) {
 151     fputs("\n*** signature failed", stderr);
 152     fputs("\nq = ", stderr); mp_writefile(dp.q, stderr, 16);
 153     fputs("\np = ", stderr); mp_writefile(dp.p, stderr, 16);
 154     fputs("\ng = ", stderr); mp_writefile(dp.g, stderr, 16);
 155     fputs("\nx = ", stderr); mp_writefile(x, stderr, 16);
 156     fprintf(stderr, "\nmessage = `%s'", v[4].buf);
 157     fputs("\nk = ", stderr); type_hex.dump(&v[5], stderr);
 158     fputs("\nR = ", stderr); type_hex.dump(&v[6], stderr);
 159     fputs("\nS = ", stderr); type_hex.dump(&v[7], stderr);
 160
 161     {
 162       mp *m = MP_NEW;
 163       m = mp_loadb(m, hash, sizeof(hash));
 164       fputs("\nm = ", stderr); mp_writefile(m, stderr, 16);
 165       m = mp_loadb(m, s.r, sizeof(s.r));
 166       fputs("\nr = ", stderr); mp_writefile(m, stderr, 16);
 167       m = mp_loadb(m, s.s, sizeof(s.s));
 168       fputs("\ns = ", stderr); mp_writefile(m, stderr, 16);
 169       mp_drop(m);
 170     }
 171
 172     fputc('\n', stderr);
 173     ok = 0;
 174   }
 175
 176   mp_drop(dp.p);
 177   mp_drop(dp.q);
 178   mp_drop(dp.g);
 179   mp_drop(x);
 180   assert(mparena_count(MPARENA_GLOBAL) == 0);
 181   return (ok);
 182 }
 183
 184 static test_chunk tests[] = {
 185   { "sign", verify,
 186     { &type_mp, &type_mp, &type_mp, &type_mp,
 187       &type_string, &type_hex, &type_hex, &type_hex, 0 } },
 188   { 0, 0, { 0 } }
 189 };
 190
 191 int main(int argc, char *argv[])
 192 {
 193   sub_init();
 194   test_run(argc, argv, tests, SRCDIR "/tests/dsa");
 195   return (0);
 196 }
 197
 198 #endif
 199
 200 /*----- That's all, folks -------------------------------------------------*/