From 8b810a45dec25017a6256e4ef134236444a00921 Mon Sep 17 00:00:00 2001 From: mdw Date: Fri, 19 Nov 1999 19:28:13 +0000 Subject: [PATCH] Implementation of the Digital Signature Algorithm. --- dsa-gen.c | 394 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ dsa-sign.c | 213 ++++++++++++++++++++++++++++++++ dsa-verify.c | 218 +++++++++++++++++++++++++++++++++ dsa.h | 221 +++++++++++++++++++++++++++++++++ tests/dsa | 120 ++++++++++++++++++ 5 files changed, 1166 insertions(+) create mode 100644 dsa-gen.c create mode 100644 dsa-sign.c create mode 100644 dsa-verify.c create mode 100644 dsa.h create mode 100644 tests/dsa diff --git a/dsa-gen.c b/dsa-gen.c new file mode 100644 index 0000000..ac33088 --- /dev/null +++ b/dsa-gen.c @@ -0,0 +1,394 @@ +/* -*-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 +#include + +#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 -------------------------------------------------*/ diff --git a/dsa-sign.c b/dsa-sign.c new file mode 100644 index 0000000..8e5c997 --- /dev/null +++ b/dsa-sign.c @@ -0,0 +1,213 @@ +/* -*-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 + +#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 -------------------------------------------------*/ diff --git a/dsa-verify.c b/dsa-verify.c new file mode 100644 index 0000000..217cede --- /dev/null +++ b/dsa-verify.c @@ -0,0 +1,218 @@ +/* -*-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 + +#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 -------------------------------------------------*/ diff --git a/dsa.h b/dsa.h new file mode 100644 index 0000000..1958d50 --- /dev/null +++ b/dsa.h @@ -0,0 +1,221 @@ +/* -*-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 diff --git a/tests/dsa b/tests/dsa new file mode 100644 index 0000000..c617019 --- /dev/null +++ b/tests/dsa @@ -0,0 +1,120 @@ +# 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; +} -- 2.11.0