chiark - git - mdw - catacomb/blob - gkcdsa.c

   1 /* -*-c-*-
   2  *
   3  * $Id$
   4  *
   5  * Generalized version of KCDSA
   6  *
   7  * (c) 2004 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 "gkcdsa.h"
  33 #include "group.h"
  34 #include "ghash.h"
  35 #include "mpbarrett.h"
  36 #include "mprand.h"
  37
  38 /*----- Main code ---------------------------------------------------------*/
  39
  40 /* --- @gkcdsa_beginhash@ --- *
  41  *
  42  * Arguments:   @const gkcdsa *c@ = pointer to the context structure
  43  *
  44  * Returns:     A hashing context for you to hash the message.
  45  *
  46  * Use:         Initializes a hash function correctly for you to hash a
  47  *              message.  Requires @h@, @g@ and @p@.
  48  */
  49
  50 ghash *gkcdsa_beginhash(const gkcdsa *c)
  51 {
  52   ghash *h = GH_INIT(c->h);
  53   mp *v = G_TOINT(c->g, MP_NEW, c->p);
  54   size_t sz = c->h->bufsz;
  55   void *p = xmalloc(sz);
  56   if (/*ouch*/ !v) memset(p, 0, sz);
  57   else mp_storeb(v, p, sz);
  58   GH_HASH(h, p, sz);
  59   mp_drop(v); xfree(p);
  60   return (h);
  61 }
  62
  63 /* --- @gkcdsa_endhash@ --- *
  64  *
  65  * Arguments:   @const gkcdsa *c@ = pointer to the context structure
  66  *              @ghash *h@ = the hashing context
  67  *
  68  * Returns:     ---
  69  *
  70  * Use:         Does any final thing that KCDSA wants to do when hashing a
  71  *              message.  (Actually, there's nothing.)  The hashing context
  72  *              isn't finalized.
  73  */
  74
  75 void gkcdsa_endhash(const gkcdsa *c, ghash *h) { ; }
  76
  77 /* --- @hashge@ --- *
  78  *
  79  * Arguments:   @group *g@ = abstract group
  80  *              @const gchash *hc@ = hash class
  81  *              @ge *w@ = a group element
  82  *
  83  * Returns:     A hash context, with the hash of @w@ in it.
  84  */
  85
  86 static ghash *hashge(group *g, const gchash *hc, ge *w)
  87 {
  88   ghash *h;
  89   size_t sz;
  90   void *p;
  91   buf b;
  92   int rc;
  93
  94   sz = hc->hashsz;
  95   if (sz < g->noctets)
  96     sz = g->noctets;
  97   p = xmalloc(sz);
  98   buf_init(&b, p, sz);
  99   rc = G_TORAW(g, &b, w);
 100   assert(rc == 0);
 101   h = GH_INIT(hc);
 102   GH_HASH(h, BBASE(&b), BLEN(&b));
 103   xfree(p);
 104   return (h);
 105 }
 106
 107 /* --- @gkcdsa_sign@ --- *
 108  *
 109  * Arguments:   @const gkcdsa *c@ = my context structure
 110  *              @gkcdsa_sig *s@ = where to put the signature (initialized)
 111  *              @const void *m@ = pointer to message hash
 112  *              @mp *k@ = random exponent for this message or null
 113  *
 114  * Returns:     ---
 115  *
 116  * Use:         Signs a message.  Requires @g@, @u@, @h@, and @r@ if @k@ is
 117  *              null.  This is a better idea than inventing @k@ yourself.
 118  */
 119
 120 void gkcdsa_sign(const gkcdsa *c, gkcdsa_sig *s, const void *m, mp *k)
 121 {
 122   group *g = c->g;
 123   mp *x, *y;
 124   ge *z = G_CREATE(g);
 125   size_t hsz = c->h->hashsz;
 126   ghash *h;
 127
 128   if (k) { MP_COPY(k); goto have_k; }
 129 new_k:
 130   k = mprand_range(k, g->r, c->r, 0);
 131 have_k:
 132   if (MP_ZEROP(k)) goto new_k;
 133   G_EXP(g, z, g->g, k);
 134   if (!s->r) s->r = xmalloc(hsz);
 135   h = hashge(g, c->h, z); GH_DONE(h, s->r);
 136
 137   x = mp_loadb(s->s, m, hsz);
 138   y = mp_loadb(MP_NEW, s->r, hsz);
 139   x = mp_xor(x, x, y);
 140   mp_div(0, &x, x, g->r);
 141   x = mp_sub(x, g->r, x);
 142   x = mp_add(x, x, k);
 143   if (MP_CMP(x, >=, g->r)) x = mp_sub(x, x, g->r);
 144   x = mp_mul(x, x, c->u); mp_div(0, &x, x, g->r);
 145   s->s = x;
 146   mp_drop(k); mp_drop(y); GH_DESTROY(h); G_DESTROY(g, z);
 147 }
 148
 149 /* --- @gkcdsa_verify@ --- *
 150  *
 151  * Arguments:   @const gkcdsa *c@ = my context structure
 152  *              @const gkcdsa_sig *s@ = the signature to verify
 153  *              @const void *m@ = pointer to message hash
 154  *
 155  * Returns:     Zero if OK, negative on failure.
 156  *
 157  * Use:         Checks a signature on a message,  Requires @g@, @p@, @h@.
 158  */
 159
 160 int gkcdsa_verify(const gkcdsa *c, const gkcdsa_sig *s, const void *m)
 161 {
 162   group *g = c->g;
 163   size_t hsz = c->h->hashsz;
 164   group_expfactor e[2];
 165   mp *x, *y;
 166   ghash *h;
 167   ge *z;
 168   octet *p;
 169   int rc = -1;
 170
 171   if (MP_CMP(s->s, <, MP_ONE) || MP_CMP(s->s, >=, g->r))
 172     return (-1);
 173   x = mp_loadb(MP_NEW, m, hsz); y = mp_loadb(MP_NEW, s->r, hsz);
 174   x = mp_xor(x, x, y); mp_div(0, &x, x, g->r);
 175   e[0].base = c->p; e[0].exp = s->s;
 176   e[1].base = g->g; e[1].exp = x;
 177   z = G_CREATE(g); G_MEXP(g, z, e, 2);
 178   h = hashge(g, c->h, z); p = GH_DONE(h, 0);
 179   if (memcmp(p, s->r, hsz) == 0) rc = 0;
 180   mp_drop(x); mp_drop(y); G_DESTROY(g, z); GH_DESTROY(h);
 181   return (rc);
 182 }
 183
 184 /*----- Test rig ----------------------------------------------------------*/
 185
 186 #ifdef TEST_RIG
 187
 188 static group *getgroup(const char *p) {
 189   group *g; qd_parse qd;
 190   qd.p = p; qd.e = 0; g = group_parse(&qd);
 191   if (g && !qd_eofp(&qd)) { G_DESTROYGROUP(g); g = 0; qd.e = "junk at eof"; }
 192   if (!g) { fprintf(stderr, "bad group string `%.*s|%s': %s\n", qd.p - p,
 193                     p, qd.p, qd.e); exit(1); }
 194   return (g);
 195 }
 196
 197 static ge *getge(group *g, const char *p) {
 198   ge *x = G_CREATE(g);
 199   if (group_readstring(g, x, p, 0)) {
 200     fprintf(stderr, "bad group element `%s'\n", p);
 201     exit(1);
 202   }
 203   return (x);
 204 }
 205
 206 static void showge(group *g, const char *p, ge *x) {
 207   fprintf(stderr, "*** %s = ", p); group_writefile(g, x, stderr);
 208   putc('\n', stderr);
 209 }
 210
 211 static void showmp(const char *p, mp *x, int r) {
 212   fprintf(stderr, "*** %s = ", p); mp_writefile(x, stderr, r);
 213   putc('\n', stderr);
 214 }
 215
 216 static int tsign(dstr *v)
 217 {
 218   gdsa c;
 219   gkcdsa_sig s, ss = GKCDSA_SIG_INIT;
 220   ghash *h;
 221   mp *k;
 222   dstr d = DSTR_INIT;
 223   mp *x;
 224   int ok = 1;
 225
 226   c.g = getgroup(v[0].buf); c.h = ghash_byname(v[1].buf);
 227   c.u = *(mp **)v[2].buf; k = *(mp **)v[4].buf;
 228   s.r = (octet *)v[5].buf; s.s = *(mp **)v[6].buf;
 229   DENSURE(&d, c.h->hashsz); d.len = c.h->hashsz; memset(d.buf, 0, d.len);
 230   ss.r = (octet *)d.buf;
 231
 232   x = mp_modinv(MP_NEW, c.u, c.g->r);
 233   c.p = G_CREATE(c.g); G_EXP(c.g, c.p, c.g->g, x);
 234   h = gkcdsa_beginhash(&c);
 235   GH_HASH(h, v[3].buf, v[3].len);
 236   gkcdsa_endhash(&c, h);
 237   gkcdsa_sign(&c, &ss, GH_DONE(h, 0), k);
 238   if (memcmp(s.r, ss.r, c.h->hashsz) || !MP_EQ(s.s, ss.s)) {
 239     ok = 0;
 240     fprintf(stderr, "*** sign failed!\n");
 241     fprintf(stderr, "*** group: %s\n", v[0].buf);
 242     fprintf(stderr, "*** hash: %s\n", c.h->name);
 243     showmp("private key", c.u, 16);
 244     showge(c.g, "public key", c.p);
 245     fprintf(stderr, "*** message: `%s'\n", v[3].buf);
 246     fprintf(stderr, "*** computed r = ");
 247     type_hex.dump(&d, stderr); putc('\n', stderr);
 248     showmp("computed s", ss.s, 16);
 249     fprintf(stderr, "*** computed r = ");
 250     type_hex.dump(&v[5], stderr); putc('\n', stderr);
 251     showmp("expected s", s.s, 16);
 252   }
 253   mp_drop(s.s); dstr_destroy(&d); mp_drop(ss.s); mp_drop(x); mp_drop(k);
 254   mp_drop(c.u); G_DESTROY(c.g, c.p); G_DESTROYGROUP(c.g); GH_DESTROY(h);
 255   assert(mparena_count(MPARENA_GLOBAL) == 0);
 256   return (ok);
 257 }
 258
 259 static int tverify(dstr *v)
 260 {
 261   gkcdsa c;
 262   gkcdsa_sig s;
 263   ghash *h;
 264   int rc, erc;
 265   int ok = 1;
 266
 267   c.g = getgroup(v[0].buf); c.h = ghash_byname(v[1].buf);
 268   c.p = getge(c.g, v[2].buf);
 269   s.r = (octet *)v[4].buf; s.s = *(mp **)v[5].buf;
 270   erc = *(int *)v[6].buf;
 271
 272   h = gkcdsa_beginhash(&c);
 273   GH_HASH(h, v[3].buf, v[3].len);
 274   gkcdsa_endhash(&c, h);
 275   rc = gkcdsa_verify(&c, &s, GH_DONE(h, 0));
 276   if (!rc != !erc) {
 277     ok = 0;
 278     fprintf(stderr, "*** verify failed!\n");
 279     fprintf(stderr, "*** group: %s\n", v[0].buf);
 280     fprintf(stderr, "*** hash: %s\n", c.h->name);
 281     showge(c.g, "public key", c.p);
 282     fprintf(stderr, "*** message: `%s'\n", v[3].buf);
 283     fprintf(stderr, "*** sig r = ");
 284     type_hex.dump(&v[4], stderr); putc('\n', stderr);
 285     showmp("sig s", s.s, 16);
 286     fprintf(stderr, "*** expected %s\n", !erc ? "pass" : "fail");
 287   }
 288   mp_drop(s.s); G_DESTROY(c.g, c.p); G_DESTROYGROUP(c.g);
 289   GH_DESTROY(h);
 290   assert(mparena_count(MPARENA_GLOBAL) == 0);
 291   return (ok);
 292 }
 293
 294 static const test_chunk tests[] = {
 295   { "sign", tsign, { &type_string, &type_string, &type_mp, &type_string,
 296                      &type_mp, &type_hex, &type_mp } },
 297   { "verify", tverify, { &type_string, &type_string, &type_string,
 298                          &type_string, &type_hex, &type_mp, &type_int } },
 299   { 0 }
 300 };
 301
 302 int main(int argc, char *argv[])
 303 {
 304   sub_init();
 305   test_run(argc, argv, tests, SRCDIR "/tests/gkcdsa");
 306   return (0);
 307 }
 308
 309 #endif
 310
 311 /*----- That's all, folks -------------------------------------------------*/