Pollard's rho algorithm for computing discrete logs.

[u/mdw/catacomb] / dsa.h

/* -*-c-*-
 *
 * $Id: dsa.h,v 1.6 2000/07/01 11:20:51 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.6  2000/07/01 11:20:51  mdw
 * New functions for freeing public and private keys.
 *
 * Revision 1.5  2000/06/17 10:53:42  mdw
 * Minor changes for key fetching.  Typesetting fixes.
 *
 * Revision 1.4  1999/12/22 15:52:44  mdw
 * Reworking for new prime-search system.
 *
 * Revision 1.3  1999/12/10 23:29:48  mdw
 * Change header file guard names.
 *
 * Revision 1.2  1999/11/20 22:23:48  mdw
 * Allow event handler to abort the search process.
 *
 * Revision 1.1  1999/11/19 19:28:00  mdw
 * Implementation of the Digital Signature Algorithm.
 *
 */

#ifndef CATACOMB_DSA_H
#define CATACOMB_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 CATACOMB_KEY_H
#  include "key.h"
#endif

#ifndef CATACOMB_MP_H
#  include "mp.h"
#endif
    
#ifndef CATACOMB_PGEN_H
#  include "pgen.h"
#endif

/*----- 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;

typedef struct dsa_pub {
  dsa_param dp;				/* Shared parameters */
  mp *y;				/* Public key */
} dsa_pub;

typedef struct dsa_priv {
  dsa_param dp;				/* Shared parameters */
  mp *x;				/* Private key */
  mp *y;				/* %$y \equiv g^x \pmod{p}$% */
} dsa_priv;

/* --- 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;

/*----- Key fetching ------------------------------------------------------*/

extern const key_fetchdef dsa_paramfetch[];
#define DSA_PARAMFETCHSZ 5

extern const key_fetchdef dsa_pubfetch[];
#define DSA_PUBFETCHSZ 6

extern const key_fetchdef dsa_privfetch[];
#define DSA_PRIVFETCHSZ 9

/* --- @dsa_paramfree@, @dsa_pubfree@, @dsa_privfree@ --- *
 *
 * Arguments:	@dsa_param *dp@, @dsa_pub *dp@, @dsa_priv *dp@ = pointer
 *			to key block to free
 *
 * Returns:	---
 *
 * Use:		Frees a DSA key block.
 */

extern void dsa_paramfree(dsa_param */*dp*/);
extern void dsa_pubfree(dsa_pub */*dp*/);
extern void dsa_privfree(dsa_priv */*dp*/);

/*----- DSA stepper -------------------------------------------------------*/

typedef struct dsa_stepctx {

  /* --- To be initialized by the client --- */

  grand *r;				/* Random number generator */
  mp *q;				/* Force @p@ to be a multiple */
  size_t bits;				/* Number of bits in the result */
  unsigned or;				/* OR mask for low order bits */
} dsa_stepctx;

/* --- @dsa_step@ --- *
 *
 * The stepper chooses random integers, ensures that they are a multiple of
 * @q@ (if specified), sets the low-order bits, and then tests for
 * divisibility by small primes.
 */

extern int dsa_step(int /*rq*/, pgen_event */*ev*/, void */*p*/);

/*----- Functions provided ------------------------------------------------*/

/* --- @dsa_seed@ --- *
 *
 * Arguments:	@dsa_param *dp@ = where to store parameters
 *		@unsigned ql@ = length of @q@ in bits
 *		@unsigned pl@ = length of @p@ in bits
 *		@unsigned steps@ = number of steps to find @q@
 *		@const void *k@ = pointer to key material
 *		@size_t sz@ = size of key material
 *		@pgen_proc *event@ = event handler function
 *		@void *ectx@ = argument for event handler
 *
 * Returns:	@PGEN_DONE@ if everything worked ok; @PGEN_ABORT@ otherwise.
 *
 * Use:		Generates the DSA shared parameters from a given seed value.
 *		This can take quite a long time.
 *
 *		The algorithm used is a compatible extension of the method
 *		described in the DSA standard, FIPS 186.  The standard
 *		requires that %$q$% be 160 bits in size (i.e., @ql == 160@)
 *		and that the length of %$p$% be %$L = 512 + 64l$% for some
 *		%$l$%.  Neither limitation applies to this implementation.
 */

extern int dsa_seed(dsa_param */*dp*/, unsigned /*ql*/, unsigned /*pl*/,
		    unsigned /*steps*/, const void */*k*/, size_t /*sz*/,
		    pgen_proc */*event*/, void */*ectx*/);

/* --- @dsa_mksig@ --- *
 *
 * Arguments:	@const dsa_param *dp@ = pointer to DSA parameters
 *		@mp *a@ = secret signing key
 *		@mp *m@ = message to be signed
 *		@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*/, mp */*a*/,
		      mp */*m*/, 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
 *		@mp *y@ = public verification key
 *		@mp *m@ = message which was signed
 *		@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*/, mp */*y*/,
		    mp */*m*/, mp */*r*/, mp */*s*/);

/* --- @dsa_verify@ --- *
 *
 * Arguments:	@const dsa_param *dp@ = pointer to DSA parameters
 *		@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*/, 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