--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: dsa-gen.c,v 1.1 1999/11/19 19:28:00 mdw Exp $
+ *
+ * Generate DSA shared parameters
+ *
+ * (c) 1999 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: dsa-gen.c,v $
+ * Revision 1.1 1999/11/19 19:28:00 mdw
+ * Implementation of the Digital Signature Algorithm.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "dsa.h"
+#include "mp.h"
+#include "pgen.h"
+#include "rabin.h"
+#include "rc4.h"
+#include "sha.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @dsa_seed@ --- *
+ *
+ * Arguments: @dsa_param *dp@ = where to store parameters
+ * @unsigned l@ = bitlength of @p@ in bits
+ * @const void *k@ = pointer to key material
+ * @void (*proc)(int ev, mp *m, void *p)@ = event procedure
+ * @size_t sz@ = size of key material
+ *
+ * Returns: Zero if all went well, nonzero if key material was
+ * unsuitable (one of the @DSAEV@ codes).
+ *
+ * Use: Generates the DSA shared parameters from a given seed value.
+ * This can take quite a long time. The size of @p@ in bits is
+ * %$l = 512 + 64l'$%. The DSA standard, FIPS 186, only allows
+ * %$0 \le l' \le 8$%. This implementation has no such limit,
+ * although @l@ must be a multiple of 8.
+ *
+ * The event procedure is informed of various happenings during
+ * generation. It is passed an event code describing what
+ * happened, and a multiprecision number which pertains to the
+ * event code.
+ */
+
+int dsa_seed(dsa_param *dp, unsigned l, const void *k, size_t sz,
+ void (*proc)(int /*ev*/, mp */*m*/, void */*p*/), void *arg)
+{
+ mp *q, *p, *g;
+ mp *s = mp_loadb(MP_NEW, k, sz);
+ octet *sbuf = xmalloc(sz);
+ rc4_ctx rc4;
+ int fail;
+
+ l /= 8;
+ rc4_init(&rc4, k, sz);
+
+ /* --- Generate @q@ --- */
+
+ {
+ octet xbuf[SHA_HASHSZ], ybuf[SHA_HASHSZ];
+ sha_ctx c;
+ int i;
+
+ sha_init(&c);
+ sha_hash(&c, k, sz);
+ sha_done(&c, xbuf);
+
+ MPX_UADDN(s->v, s->vl, 1);
+ mp_storeb(s, sbuf, sz);
+ sha_init(&c);
+ sha_hash(&c, sbuf, sz);
+ sha_done(&c, ybuf);
+
+ for (i = 0; i < sizeof(xbuf); i++)
+ xbuf[i] ^= ybuf[i];
+ xbuf[0] |= 0x80;
+ xbuf[SHA_HASHSZ - 1] |= 0x01;
+ q = mp_loadb(MP_NEW, xbuf, sizeof(xbuf));
+ }
+
+ /* --- Quick primality check --- */
+
+ {
+ pgen pg;
+ int rc = pgen_create(&pg, q);
+ pgen_destroy(&pg);
+ if (rc == PGEN_COMPOSITE) {
+ if (proc)
+ proc(DSAEV_FAILQ, q, arg);
+ fail = DSAEV_FAILQ;
+ goto fail_0;
+ }
+ }
+
+ /* --- Ensure that @q@ is prime --- *
+ *
+ * This requires 18 iterations, because the DSA spec is paranoid.
+ * Fortunately, it doesn't actually take very long.
+ */
+
+ {
+ rabin r;
+ int i;
+ mp *g = MP_NEW;
+ octet gbuf[SHA_HASHSZ];
+
+ rabin_create(&r, q);
+ for (i = 0; i < 18; i++) {
+ rc4_encrypt(&rc4, 0, gbuf, sizeof(gbuf));
+ g = mp_loadb(g, gbuf, sizeof(gbuf));
+ if (rabin_test(&r, g) == PGEN_COMPOSITE)
+ break;
+ if (proc)
+ proc(DSAEV_PASSQ, q, arg);
+ }
+ mp_drop(g);
+ rabin_destroy(&r);
+ if (i < 18) {
+ if (proc)
+ proc(DSAEV_FAILQ, q, arg);
+ fail = DSAEV_FAILQ;
+ goto fail_0;
+ }
+ if (proc)
+ proc(DSAEV_GOODQ, q, arg);
+ }
+
+ /* --- Now generate @p@ --- *
+ *
+ * This is, unfortunately, rather more messy and complicated.
+ */
+
+ {
+ mp *q2 = mp_lsl(MP_NEW, q, 1);
+ mp *ll = mp_lsl(MP_NEW, MP_ONE, l * 8 - 1);
+ unsigned n = l / SHA_HASHSZ, b = l % SHA_HASHSZ;
+ size_t psz = SHA_HASHSZ * (n + 1);
+ octet *pbuf = xmalloc(psz);
+ sha_ctx c;
+ unsigned i, j;
+
+ /* --- Fiddle with the leftover bytes count --- */
+
+ b = SHA_HASHSZ - b;
+
+ /* --- Go round 4096 times trying different @p@ values --- */
+
+ p = MP_NEW;
+ for (j = 0; j < 4096; j++) {
+
+ /* --- Build a prospective value of @p@ --- */
+
+ {
+ octet *pp = pbuf + SHA_HASHSZ * n;
+
+ for (i = 0; i <= n; i++) {
+ MPX_UADDN(s->v, s->vl, 1);
+ mp_storeb(s, sbuf, sz);
+ sha_init(&c);
+ sha_hash(&c, sbuf, sz);
+ sha_done(&c, pp);
+ pp -= SHA_HASHSZ;
+ }
+
+ pbuf[b] &= 0x7f;
+ p = mp_loadb(p, pbuf + b, psz - b);
+ p = mp_add(p, p, ll);
+ }
+
+ /* --- Adjust @p@ so that %$p \bmod 2q = 1$% --- */
+
+ {
+ mp *c = MP_NEW;
+ mp_div(0, &c, p, q2);
+ c = mp_sub(c, c, MP_ONE);
+ p = mp_sub(p, p, c);
+ mp_drop(c);
+ }
+
+ /* --- Check that @p@ is large enough --- */
+
+ if (MP_CMP(p, <, ll))
+ continue;
+
+ /* --- Run a simple primality test --- */
+
+ {
+ pgen pg;
+ int rc = pgen_create(&pg, p);
+ pgen_destroy(&pg);
+ if (rc == PGEN_COMPOSITE)
+ continue;
+ }
+
+ /* --- Run the Rabin-Miller test --- */
+
+ {
+ rabin r;
+ mp *g = MP_NEW;
+
+ if (proc)
+ proc(DSAEV_TRYP, p, arg);
+ rabin_create(&r, p);
+ for (i = 0; i < 5; i++) {
+ rc4_encrypt(&rc4, 0, pbuf, psz - b);
+ g = mp_loadb(g, pbuf, psz - b);
+ if (rabin_test(&r, g) == PGEN_COMPOSITE)
+ break;
+ if (proc)
+ proc(DSAEV_PASSP, p, arg);
+ }
+ mp_drop(g);
+ rabin_destroy(&r);
+ if (i < 5) {
+ if (proc)
+ proc(DSAEV_FAILP, p, arg);
+ fail = DSAEV_FAILP;
+ continue;
+ }
+ }
+
+ /* --- It worked! --- */
+
+ if (proc)
+ proc(DSAEV_GOODP, p, arg);
+ break;
+ }
+
+ free(pbuf);
+ mp_drop(q2);
+ mp_drop(ll);
+ if (j >= 4096)
+ goto fail_1;
+ }
+
+ /* --- Choose a generator of an order-%$q$% subgroup of %$Z^*_p$% --- */
+
+ {
+ mp *pp = MP_NEW;
+ mpw hw;
+ mp h;
+ unsigned i;
+ mpmont mm;
+
+ /* --- Calculate %$p' = (p - 1)/q$% --- */
+
+ {
+ mp *p1 = mp_sub(MP_NEW, p, MP_ONE);
+ mp_div(&pp, 0, p1, q);
+ mp_drop(p1);
+ }
+
+ /* --- Now find %$h$% where %$g = h^{p'} \bmod p \ne 1$% --- */
+
+ mp_build(&h, &hw, &hw + 1);
+ mpmont_create(&mm, p);
+ for (i = 0; i < NPRIME; i++) {
+ hw = ptab[i];
+ if (proc)
+ proc(DSAEV_TRYH, &h, arg);
+ g = mpmont_exp(&mm, &h, pp);
+ if (MP_CMP(g, !=, MP_ONE))
+ break;
+ if (proc)
+ proc(DSAEV_FAILH, &h, arg);
+ mp_drop(g);
+ }
+ mp_drop(pp);
+ if (i >= NPRIME) {
+ fail = DSAEV_FAILH;
+ goto fail_1;
+ }
+ }
+ if (proc)
+ proc(DSAEV_GOODG, g, arg);
+
+ /* --- Return the important information that I succeeded --- */
+
+ dp->p = p;
+ dp->q = q;
+ dp->g = g;
+ free(sbuf);
+ return (0);
+
+ /* --- Tidy up after failure --- */
+
+fail_1:
+ mp_drop(p);
+fail_0:
+ mp_drop(q);
+ mp_drop(s);
+ free(sbuf);
+ return (-1);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+static char baton[] = "/-\\|";
+static char *b = baton;
+
+static void event(int ev, mp *m, void *p)
+{
+ if (ev == DSAEV_TRYP || ev == DSAEV_PASSP) {
+ fputc(*b++, stdout);
+ fputc('\b', stdout);
+ fflush(stdout);
+ if (!*b)
+ b = baton;
+ }
+}
+
+static int verify(dstr *v)
+{
+ mp *q = *(mp **)v[2].buf;
+ mp *p = *(mp **)v[3].buf;
+ mp *g = *(mp **)v[4].buf;
+ dsa_param dp;
+ unsigned l = *(unsigned *)v[1].buf;
+ int ok = 1;
+ int rc;
+
+ rc = dsa_seed(&dp, l, v[0].buf, v[0].len, event, 0);
+ if (rc || MP_CMP(q, !=, dp.q) ||
+ MP_CMP(p, !=, dp.p) || MP_CMP(g, !=, dp.g)) {
+ fputs("\n*** gen failed", stderr);
+ fputs("\nseed = ", stderr); type_hex.dump(&v[0], stderr);
+ fprintf(stderr, "\nl = %u", l);
+ fputs("\n q = ", stderr); mp_writefile(q, stderr, 16);
+ fputs("\n p = ", stderr); mp_writefile(q, stderr, 16);
+ fputs("\n g = ", stderr); mp_writefile(g, stderr, 16);
+ if (!rc) {
+ fputs("\ndp.q = ", stderr); mp_writefile(dp.q, stderr, 16);
+ fputs("\ndp.p = ", stderr); mp_writefile(dp.p, stderr, 16);
+ fputs("\ndp.g = ", stderr); mp_writefile(dp.g, stderr, 16);
+ }
+ fputc('\n', stderr);
+ ok = 0;
+ }
+
+ mp_drop(q); mp_drop(p); mp_drop(g);
+ if (!rc) {
+ mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g);
+ }
+ return (ok);
+}
+
+static test_chunk tests[] = {
+ { "gen", verify,
+ { &type_hex, &type_int, &type_mp, &type_mp, &type_mp, 0 } },
+ { 0, 0, { 0 } }
+};
+
+int main(int argc, char *argv[])
+{
+ sub_init();
+ test_run(argc, argv, tests, SRCDIR "/tests/dsa");
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: dsa-sign.c,v 1.1 1999/11/19 19:28:00 mdw Exp $
+ *
+ * DSA signing operation
+ *
+ * (c) 1999 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: dsa-sign.c,v $
+ * Revision 1.1 1999/11/19 19:28:00 mdw
+ * Implementation of the Digital Signature Algorithm.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "dsa.h"
+#include "mp.h"
+#include "mpmont.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @dsa_mksig@ --- *
+ *
+ * Arguments: @const dsa_param *dp@ = pointer to DSA parameters
+ * @const mp *a@ = secret signing key
+ * @const mp *m@ = message to be signed
+ * @const mp *k@ = random data
+ * @mp **rr, **ss@ = where to put output parameters
+ *
+ * Returns: ---
+ *
+ * Use: Computes a DSA signature of a message.
+ */
+
+void dsa_mksig(const dsa_param *dp, const mp *a, const mp *m, const mp *k,
+ mp **rr, mp **ss)
+{
+ mpmont pm, qm;
+ mp *k1, *r;
+ mp *rrr, *ar;
+
+ /* --- Create the Montgomery contexts --- */
+
+ mpmont_create(&pm, dp->p);
+ mpmont_create(&qm, dp->q);
+
+ /* --- Compute %$r = (g^k \bmod p) \bmod q$% --- */
+
+ r = mpmont_exp(&pm, dp->g, k);
+ mp_div(0, &r, r, dp->q);
+ *rr = r;
+
+ /* --- Compute %$k^{-1} \bmod q$% --- */
+
+ mp_gcd(0, 0, &k1, dp->q, (mp *)k);
+
+ /* --- Now for %$k^{-1}(m + ar)$% --- */
+
+ rrr = mpmont_mul(&qm, MP_NEW, r, qm.r2);
+ ar = mpmont_mul(&qm, MP_NEW, a, rrr);
+ ar = mp_add(ar, ar, m);
+ if (MP_CMP(ar, >=, dp->q))
+ ar = mp_sub(ar, ar, dp->q);
+ rrr = mpmont_mul(&qm, rrr, ar, qm.r2);
+ ar = mpmont_mul(&qm, ar, rrr, k1);
+ *ss = ar;
+
+ /* --- Tidy things up a little --- */
+
+ mp_drop(rrr);
+ mp_drop(k1);
+ mpmont_destroy(&pm);
+ mpmont_destroy(&qm);
+}
+
+/* --- @dsa_sign@ --- *
+ *
+ * Arguments: @dsa_param *dp@ = pointer to DSA parameters
+ * @mp *a@ = pointer to secret signing key
+ * @const void *m@ = pointer to message
+ * @size_t msz@ = size of the message
+ * @const void *k@ = secret random data for securing signature
+ * @size_t ksz@ = size of secret data
+ * @void *r@ = pointer to output space for @r@
+ * @size_t rsz@ = size of output space for @r@
+ * @void *s@ = pointer to output space for @s@
+ * @size_t ssz@ = size of output space for @s@
+ *
+ * Returns: ---
+ *
+ * Use: Signs a message, storing the results in a big-endian binary
+ * form.
+ */
+
+void dsa_sign(dsa_param *dp, mp *a,
+ const void *m, size_t msz, const void *k, size_t ksz,
+ void *r, size_t rsz, void *s, size_t ssz)
+{
+ mp *mm = mp_loadb(MP_NEW, m, msz);
+ mp *km = mp_loadb(MP_NEW, k, ksz);
+ mp *rm, *sm;
+ dsa_mksig(dp, a, mm, km, &rm, &sm);
+ mp_storeb(rm, r, rsz);
+ mp_storeb(sm, s, ssz);
+ mp_drop(mm); mp_drop(km);
+ mp_drop(rm); mp_drop(sm);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+#include <mLib/testrig.h>
+
+#include "sha.h"
+
+static int verify(dstr *v)
+{
+ dsa_param dp;
+ mp *x;
+ sha_ctx c;
+ octet hash[SHA_HASHSZ];
+ dsa_sig s;
+ int ok = 1;
+
+ dp.q = *(mp **)v[0].buf;
+ dp.p = *(mp **)v[1].buf;
+ dp.g = *(mp **)v[2].buf;
+ x = *(mp **)v[3].buf;
+
+ sha_init(&c);
+ sha_hash(&c, v[4].buf, v[4].len);
+ sha_done(&c, hash);
+
+ dsa_sign(&dp, x, hash, sizeof(hash), v[5].buf, v[5].len,
+ s.r, sizeof(s.r), s.s, sizeof(s.s));
+
+ if (v[6].len != sizeof(s.r) || v[7].len != sizeof(s.s) ||
+ memcmp(s.r, v[6].buf, sizeof(s.r)) != 0 ||
+ memcmp(s.s, v[7].buf, sizeof(s.s)) != 0) {
+ fputs("\n*** signature failed", stderr);
+ fputs("\nq = ", stderr); mp_writefile(dp.q, stderr, 16);
+ fputs("\np = ", stderr); mp_writefile(dp.p, stderr, 16);
+ fputs("\ng = ", stderr); mp_writefile(dp.g, stderr, 16);
+ fputs("\nx = ", stderr); mp_writefile(x, stderr, 16);
+ fprintf(stderr, "\nmessage = `%s'", v[4].buf);
+ fputs("\nk = ", stderr); type_hex.dump(&v[5], stderr);
+ fputs("\nR = ", stderr); type_hex.dump(&v[6], stderr);
+ fputs("\nS = ", stderr); type_hex.dump(&v[7], stderr);
+
+ {
+ mp *m = MP_NEW;
+ m = mp_loadb(m, hash, sizeof(hash));
+ fputs("\nm = ", stderr); mp_writefile(m, stderr, 16);
+ m = mp_loadb(m, s.r, sizeof(s.r));
+ fputs("\nr = ", stderr); mp_writefile(m, stderr, 16);
+ m = mp_loadb(m, s.s, sizeof(s.s));
+ fputs("\ns = ", stderr); mp_writefile(m, stderr, 16);
+ mp_drop(m);
+ }
+
+ fputc('\n', stderr);
+ ok = 0;
+ }
+
+ mp_drop(dp.p);
+ mp_drop(dp.q);
+ mp_drop(dp.g);
+ mp_drop(x);
+ return (ok);
+}
+
+static test_chunk tests[] = {
+ { "sign", verify,
+ { &type_mp, &type_mp, &type_mp, &type_mp,
+ &type_string, &type_hex, &type_hex, &type_hex, 0 } },
+ { 0, 0, { 0 } }
+};
+
+int main(int argc, char *argv[])
+{
+ sub_init();
+ test_run(argc, argv, tests, SRCDIR "/tests/dsa");
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: dsa-verify.c,v 1.1 1999/11/19 19:28:00 mdw Exp $
+ *
+ * DSA signature verification
+ *
+ * (c) 1999 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: dsa-verify.c,v $
+ * Revision 1.1 1999/11/19 19:28:00 mdw
+ * Implementation of the Digital Signature Algorithm.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "dsa.h"
+#include "mp.h"
+#include "mpmont.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @dsa_vrfy@ --- *
+ *
+ * Arguments: @const dsa_param *dp@ = pointer to DSA parameters
+ * @const mp *y@ = public verification key
+ * @const mp *m@ = message which was signed
+ * @const mp *r, *s@ = the signature
+ *
+ * Returns: Zero if the signature is a forgery, nonzero if it's valid.
+ *
+ * Use: Verifies a DSA digital signature.
+ */
+
+#define SHOW(x) do { fputs(#x " = ", stdout); mp_writefile(x, stdout, 16); fputc('\n', stdout); } while (0)
+
+int dsa_vrfy(const dsa_param *dp, const mp *y,
+ const mp *m, const mp *r, const mp *s)
+{
+ mpmont pm, qm;
+ mp *w;
+ mpmont_factor f[2];
+ int ok;
+
+ /* --- Ensure that all of the signature bits are in range --- */
+
+ if ((r->f | s->f) & MP_NEG)
+ return (0);
+ if (MP_CMP(r, >=, dp->q) || MP_CMP(s, >=, dp->q))
+ return (0);
+
+ /* --- Set up Montgomery contexts --- */
+
+ mpmont_create(&pm, dp->p);
+ mpmont_create(&qm, dp->q);
+
+ /* --- Compute %$w = s^{-1} \bmod q$% --- */
+
+ {
+ mp *z;
+ mp_gcd(0, 0, &z, dp->q, (mp *)s);
+ w = mpmont_mul(&qm, MP_NEW, z, qm.r2);
+ mp_drop(z);
+ }
+
+ /* --- Compute %$wr%$ and %$wm$% --- */
+
+ f[0].exp = mpmont_mul(&qm, MP_NEW, w, m);
+ f[1].exp = mpmont_mul(&qm, MP_NEW, w, r);
+ mp_drop(w);
+ mpmont_destroy(&qm);
+
+ /* --- Do the exponentiation and take residue mod @q@ --- */
+
+ f[0].base = dp->g;
+ f[1].base = (mp *)y;
+ w = mpmont_mexp(&pm, f, 2);
+ mp_div(0, &w, w, dp->q);
+ ok = MP_CMP(w, ==, r);
+
+ /* --- Tidy up --- */
+
+ mp_drop(w);
+ mp_drop(f[0].exp);
+ mp_drop(f[1].exp);
+ mpmont_destroy(&pm);
+ return (ok);
+}
+
+/* --- @dsa_verify@ --- *
+ *
+ * Arguments: @const dsa_param *dp@ = pointer to DSA parameters
+ * @const mp *y@ = public verification key
+ * @const void *m@ = pointer to message block
+ * @size_t msz@ = size of message block
+ * @const void *r@ = pointer to @r@ signature half
+ * @size_t rsz@ = size of @r@
+ * @const void *s@ = pointer to @s@ signature half
+ * @size_t ssz@ = size of @s@
+ *
+ * Returns: Zero if the signature is a forgery, nonzero if it's valid.
+ *
+ * Use: Verifies a DSA digital signature.
+ */
+
+int dsa_verify(const dsa_param *dp, const mp *y,
+ const void *m, size_t msz,
+ const void *r, size_t rsz,
+ const void *s, size_t ssz)
+{
+ mp *mm = mp_loadb(MP_NEW, m, msz);
+ mp *rm = mp_loadb(MP_NEW, r, rsz);
+ mp *sm = mp_loadb(MP_NEW, s, ssz);
+ int ok = dsa_vrfy(dp, y, mm, rm, sm);
+ mp_drop(mm);
+ mp_drop(rm);
+ mp_drop(sm);
+ return (ok);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+#include <mLib/testrig.h>
+
+#include "sha.h"
+
+static int verify(int good, dstr *v)
+{
+ dsa_param dp;
+ mp *y;
+ sha_ctx c;
+ octet hash[SHA_HASHSZ];
+ int ok = 1;
+ int rc;
+
+ dp.q = *(mp **)v[0].buf;
+ dp.p = *(mp **)v[1].buf;
+ dp.g = *(mp **)v[2].buf;
+ y = *(mp **)v[3].buf;
+
+ sha_init(&c);
+ sha_hash(&c, v[4].buf, v[4].len);
+ sha_done(&c, hash);
+
+ rc = dsa_verify(&dp, y, hash, sizeof(hash),
+ v[5].buf, v[5].len, v[6].buf, v[6].len);
+
+ if (!rc != !good) {
+ if (good)
+ fputs("\n*** verification failed", stderr);
+ else
+ fputs("\n*** verification succeeded", stderr);
+ fputs("\nq = ", stderr); mp_writefile(dp.q, stderr, 16);
+ fputs("\np = ", stderr); mp_writefile(dp.p, stderr, 16);
+ fputs("\ng = ", stderr); mp_writefile(dp.g, stderr, 16);
+ fputs("\ny = ", stderr); mp_writefile(y, stderr, 16);
+ fprintf(stderr, "\nmessage = `%s'", v[4].buf);
+ fputs("\nr = ", stderr); type_hex.dump(&v[5], stderr);
+ fputs("\ns = ", stderr); type_hex.dump(&v[6], stderr);
+ fputc('\n', stderr);
+ ok = 0;
+ }
+
+ mp_drop(dp.p);
+ mp_drop(dp.q);
+ mp_drop(dp.g);
+ mp_drop(y);
+ return (ok);
+}
+
+static int vgood(dstr *v) { return verify(1, v); }
+static int vbad(dstr *v) { return verify(0, v); }
+
+static test_chunk tests[] = {
+ { "verify-good", vgood,
+ { &type_mp, &type_mp, &type_mp, &type_mp,
+ &type_string, &type_hex, &type_hex, 0 } },
+ { "verify-bad", vbad,
+ { &type_mp, &type_mp, &type_mp, &type_mp,
+ &type_string, &type_hex, &type_hex, 0 } },
+ { 0, 0, { 0 } }
+};
+
+int main(int argc, char *argv[])
+{
+ sub_init();
+ test_run(argc, argv, tests, SRCDIR "/tests/dsa");
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: dsa.h,v 1.1 1999/11/19 19:28:00 mdw Exp $
+ *
+ * Digital Signature Algorithm
+ *
+ * (c) 1999 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: dsa.h,v $
+ * Revision 1.1 1999/11/19 19:28:00 mdw
+ * Implementation of the Digital Signature Algorithm.
+ *
+ */
+
+#ifndef DSA_H
+#define DSA_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Notes on the Digital Signature Algorithm --------------------------*
+ *
+ * The Digital Signature Algorithm was designed by the NSA for US Government
+ * use. It's defined in FIPS 186-1. Whether it's covered by patents is
+ * under dispute, although it looks relatively clear. It produces compact
+ * signatures, and is relatively easy to compute. It seems strong, if
+ * appropriate parameters are chosen.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef MP_H
+# include "mp.h"
+#endif
+
+/*----- Event codes -------------------------------------------------------*/
+
+enum {
+ DSAEV_OK, /* Everything is fine */
+
+ DSAEV_FAILQ, /* @q@ failed primality test */
+ DSAEV_PASSQ, /* @q@ passeed one iteration */
+ DSAEV_GOODQ, /* Found good prime @q@ */
+
+ DSAEV_TRYP, /* Try prospective @p@ */
+ DSAEV_FAILP, /* @p@ failed primality test */
+ DSAEV_PASSP, /* @p@ passed one iteration */
+ DSAEV_GOODP, /* @p@ accepted as being prime */
+
+ DSAEV_TRYH, /* Try prospective @h@ */
+ DSAEV_FAILH, /* @h@ failed */
+ DSAEV_GOODG /* @g@ accepted as a generator */
+};
+
+/*----- Data structures ---------------------------------------------------*/
+
+/* --- DSA parameter structure --- *
+ *
+ * These parameters can, and probably should, be shared among a group of
+ * users.
+ */
+
+typedef struct dsa_param {
+ mp *p, *q; /* Prime numbers %$p$% and %$q$% */
+ mp *g; /* Generates order-%$q$% subgroup */
+} dsa_param;
+
+/* --- DSA signature structure --- *
+ *
+ * This is the recommended structure for a DSA signature. The actual signing
+ * function can cope with arbitrary-sized objects given appropriate
+ * parameters, however.
+ */
+
+#define DSA_SIGLEN 20
+
+typedef struct dsa_sig {
+ octet r[DSA_SIGLEN]; /* 160-bit @r@ value */
+ octet s[DSA_SIGLEN]; /* 160-bit @s@ value */
+} dsa_sig;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @dsa_seed@ --- *
+ *
+ * Arguments: @dsa_param *dp@ = where to store parameters
+ * @unsigned l@ = bitlength of @p@ in bits
+ * @const void *k@ = pointer to key material
+ * @size_t sz@ = size of key material
+ * @void (*proc)(int ev, mp *m, void *p)@ = event procedure
+ * @void *p@ = argument for event procedure
+ *
+ * Returns: Zero if all went well, nonzero if key material was
+ * unsuitable (one of the @DSAEV@ codes).
+ *
+ * Use: Generates the DSA shared parameters from a given seed value.
+ * This can take quite a long time. The size of @p@ in bits is
+ * %$l = 512 + 64l'$%. The DSA standard, FIPS 186, only allows
+ * %$0 \le l' \le 8$%. This implementation has no such limit,
+ * although @l@ must be a multiple of 8.
+ *
+ * The event procedure is informed of various happenings during
+ * generation. It is passed an event code describing what
+ * happened, and a multiprecision number which pertains to the
+ * event code.
+ */
+
+extern int dsa_seed(dsa_param */*dp*/, unsigned /*l*/,
+ const void */*k*/, size_t /*sz*/,
+ void (*proc)(int /*ev*/, mp */*m*/, void */*p*/),
+ void */*p*/);
+
+/* --- @dsa_mksig@ --- *
+ *
+ * Arguments: @const dsa_param *dp@ = pointer to DSA parameters
+ * @const mp *a@ = secret signing key
+ * @const mp *m@ = message to be signed
+ * @const mp *k@ = random data
+ * @mp **rr, **ss@ = where to put output parameters
+ *
+ * Returns: ---
+ *
+ * Use: Computes a DSA signature of a message.
+ */
+
+extern void dsa_mksig(const dsa_param */*dp*/, const mp */*a*/,
+ const mp */*m*/, const mp */*k*/,
+ mp **/*rr*/, mp **/*ss*/);
+
+/* --- @dsa_sign@ --- *
+ *
+ * Arguments: @dsa_param *dp@ = pointer to DSA parameters
+ * @mp *a@ = pointer to secret signing key
+ * @const void *m@ = pointer to message
+ * @size_t msz@ = size of the message
+ * @const void *k@ = secret random data for securing signature
+ * @size_t ksz@ = size of secret data
+ * @void *r@ = pointer to output space for @r@
+ * @size_t rsz@ = size of output space for @r@
+ * @void *s@ = pointer to output space for @s@
+ * @size_t ssz@ = size of output space for @s@
+ *
+ * Returns: ---
+ *
+ * Use: Signs a message, storing the results in a big-endian binary
+ * form.
+ */
+
+extern void dsa_sign(dsa_param */*dp*/, mp */*a*/,
+ const void */*m*/, size_t /*msz*/,
+ const void */*k*/, size_t /*ksz*/,
+ void */*r*/, size_t /*rsz*/,
+ void */*s*/, size_t /*ssz*/);
+
+/* --- @dsa_vrfy@ --- *
+ *
+ * Arguments: @const dsa_param *dp@ = pointer to DSA parameters
+ * @const mp *y@ = public verification key
+ * @const mp *m@ = message which was signed
+ * @const mp *r, *s@ = the signature
+ *
+ * Returns: Zero if the signature is a forgery, nonzero if it's valid.
+ *
+ * Use: Verifies a DSA digital signature.
+ */
+
+extern int dsa_vrfy(const dsa_param */*dp*/, const mp */*y*/,
+ const mp */*m*/, const mp */*r*/, const mp */*s*/);
+
+/* --- @dsa_verify@ --- *
+ *
+ * Arguments: @const dsa_param *dp@ = pointer to DSA parameters
+ * @const mp *y@ = public verification key
+ * @const void *m@ = pointer to message block
+ * @size_t msz@ = size of message block
+ * @const void *r@ = pointer to @r@ signature half
+ * @size_t rsz@ = size of @r@
+ * @const void *s@ = pointer to @s@ signature half
+ * @size_t ssz@ = size of @s@
+ *
+ * Returns: Zero if the signature is a forgery, nonzero if it's valid.
+ *
+ * Use: Verifies a DSA digital signature.
+ */
+
+extern int dsa_verify(const dsa_param */*dp*/, const mp */*y*/,
+ const void */*m*/, size_t /*msz*/,
+ const void */*r*/, size_t /*rsz*/,
+ const void */*s*/, size_t /*ssz*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+# Test vectors for DSA
+#
+# $Id: dsa,v 1.1 1999/11/19 19:28:13 mdw Exp $
+
+# --- About the tests ---
+#
+# There's only one test vector from FIPS-186. The others I've made up. The
+# tests themselves are split into parameter generation, signature generation,
+# and verification.
+
+gen {
+
+ # --- One that I made up ---
+
+ bbac0ab63411435cb72f1f95b16ab94c92c34221 256
+ 16_84d192cd06ae59691897fa409da6198d5269325d
+ 16_c9c7feaeaedb16505389c5582df1858d0fdb3eecfe61c230d612661bef8c1bc5
+ 16_5cd41fc97d0db5322bab7d659354db2ed9f88e39d2c6fae9f29acab5a522131e;
+
+ # --- FIPS-186 test vector ---
+
+ d5014e4b60ef2ba8b6211b4062ba3224e0427dd3 512
+ 16_c773218c737ec8ee993b4f2ded30f48edace915f
+ 16_8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
+ 16_626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802;
+
+ # --- And a full-sized vector ---
+
+ d1a29e27dfe4d60124cc41a59e012ae690408acfc3266d07f4eaeefdc9f8c70d2d2a338d
+ 1024
+ 16_fd367bd179b5425ef9bb1f51d7d9a916e58288f9
+ 16_dde5808744e1cd37c88667e7033694b2513a7429f035f11c0bafc4dff2b96a672bd0a3ca16aba2ea526df00c8571106ba4a1d83eb62605fc9274ab70bef0a111cd070cca2d8b10edf042d6c44f863c36fabea8bb0d7340eb8c169da27a4b0ba2713c166152a0244235093391c5f71aee8c03dcaf2335a2e4689ccb27ba365ec7
+ 16_65985e4c2d6027a8afdeb9b44cc619e1c4d46bde873e0d4b45325412a2f8365e51245324f888704295fe8233a6666624d9a4701172dbfcab5c9643e1caab79eb2a0c85284d1b858688b8f16804326321f53a723502a6d6ae08dcbffccf2187a799f6281c2478ef0faed5c5c80adeabc5ee435cff8b9ae0b603e47fb08d73b014;
+}
+
+sign {
+
+ # --- Quick simple test ---
+
+ 16_84d192cd06ae59691897fa409da6198d5269325d
+ 16_c9c7feaeaedb16505389c5582df1858d0fdb3eecfe61c230d612661bef8c1bc5
+ 16_5cd41fc97d0db5322bab7d659354db2ed9f88e39d2c6fae9f29acab5a522131e
+ 16_1234 "An example message"
+ c79ef743e2e6849c8d2dcb2bed3212844f4ad31f381
+ 2718bf488b981992b164e664224dd00ca1ed4e1c
+ 5c085679fbfa9ee806781bdbd86a67dbf14df640;
+
+ # --- The FIPS-186 test vector ---
+
+ 16_c773218c737ec8ee993b4f2ded30f48edace915f
+ 16_8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
+ 16_626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
+ 16_2070b3223dba372fde1c0ffc7b2e3b498b260614
+ "abc"
+ 358dad571462710f50e254cf1a376b2bdeaadfbf
+ 8bac1ab66410435cb7181f95b16ab97c92b341c0
+ 41e2345f1f56df2458f426d155b4ba2db6dcd8c8;
+
+ # --- 1024-bit modulus test ---
+
+ 16_fd367bd179b5425ef9bb1f51d7d9a916e58288f9
+ 16_dde5808744e1cd37c88667e7033694b2513a7429f035f11c0bafc4dff2b96a672bd0a3ca16aba2ea526df00c8571106ba4a1d83eb62605fc9274ab70bef0a111cd070cca2d8b10edf042d6c44f863c36fabea8bb0d7340eb8c169da27a4b0ba2713c166152a0244235093391c5f71aee8c03dcaf2335a2e4689ccb27ba365ec7
+ 16_65985e4c2d6027a8afdeb9b44cc619e1c4d46bde873e0d4b45325412a2f8365e51245324f888704295fe8233a6666624d9a4701172dbfcab5c9643e1caab79eb2a0c85284d1b858688b8f16804326321f53a723502a6d6ae08dcbffccf2187a799f6281c2478ef0faed5c5c80adeabc5ee435cff8b9ae0b603e47fb08d73b014
+ 16_23a252f60bae4907a8ed5b6203e2b1da32848cd9
+ "A message signed with a 1024-bit DSA key."
+ 12ccb231683a3d9c13dca6fe882349537eebfd03
+ 2a301061ac185440fbf595f8f7d894158b8d1897
+ 51aedaa73cb8d47e07281d14dda5ea8c0ddf7503;
+}
+
+verify-good {
+
+ # --- Simple test ----
+
+ 16_84d192cd06ae59691897fa409da6198d5269325d
+ 16_c9c7feaeaedb16505389c5582df1858d0fdb3eecfe61c230d612661bef8c1bc5
+ 16_5cd41fc97d0db5322bab7d659354db2ed9f88e39d2c6fae9f29acab5a522131e
+ 16_51812af9600c89ffe0f73902eb09015c03b4e0fbf6ccf073931c12f9aad1fb47
+ "An example message"
+ 2718bf488b981992b164e664224dd00ca1ed4e1c
+ 5c085679fbfa9ee806781bdbd86a67dbf14df640;
+
+ # --- The FIPS-186 test vector ---
+
+ 16_c773218c737ec8ee993b4f2ded30f48edace915f
+ 16_8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
+ 16_626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
+ 16_19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333
+ "abc"
+ 8bac1ab66410435cb7181f95b16ab97c92b341c0
+ 41e2345f1f56df2458f426d155b4ba2db6dcd8c8;
+
+ # --- 1024-bit modulus test ---
+
+ 16_fd367bd179b5425ef9bb1f51d7d9a916e58288f9
+ 16_dde5808744e1cd37c88667e7033694b2513a7429f035f11c0bafc4dff2b96a672bd0a3ca16aba2ea526df00c8571106ba4a1d83eb62605fc9274ab70bef0a111cd070cca2d8b10edf042d6c44f863c36fabea8bb0d7340eb8c169da27a4b0ba2713c166152a0244235093391c5f71aee8c03dcaf2335a2e4689ccb27ba365ec7
+ 16_65985e4c2d6027a8afdeb9b44cc619e1c4d46bde873e0d4b45325412a2f8365e51245324f888704295fe8233a6666624d9a4701172dbfcab5c9643e1caab79eb2a0c85284d1b858688b8f16804326321f53a723502a6d6ae08dcbffccf2187a799f6281c2478ef0faed5c5c80adeabc5ee435cff8b9ae0b603e47fb08d73b014
+ 16_9720498d8ec1208585635faaf952c1204c37119acccc64ed7942867be24770e33db39ffcfa1194549ead8495a7918a20e15144e68125860ef4f8c1a3d771bad690938bdb2c8817e2b89a8fc615d067084a7a2f2f9280e15fb9ccebfe713584260d5ed30545b69745d7b22977bfd44d60d7c5e657aab1c79dc5cb33ff29ee9074
+ "A message signed with a 1024-bit DSA key."
+ 2a301061ac185440fbf595f8f7d894158b8d1897
+ 51aedaa73cb8d47e07281d14dda5ea8c0ddf7503;
+}
+
+verify-bad {
+ 16_c773218c737ec8ee993b4f2ded30f48edace915f
+ 16_8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
+ 16_626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
+ 16_19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333
+ "abd"
+ 8bac1ab66410435cb7181f95b16ab97c92b341c0
+ 41e2345f1f56df2458f426d155b4ba2db6dcd8c8;
+
+ 16_c773218c737ec8ee993b4f2ded30f48edace915f
+ 16_8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
+ 16_626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
+ 16_19131871d75b1612a819f29d78d1b0d7346f7aa77bb62a859bfd6c5675da9d212d3a36ef1672ef660b8c7c255cc0ec74858fba33f44c06699630a76b030ee333
+ "abc"
+ 18bac1ab66410435cb7181f95b16ab97c92b341c0
+ 41e2345f1f56df2458f426d155b4ba2db6dcd8c8;
+}
projects / u / mdw / catacomb / commitdiff