--- /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 -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff