#include <gmp.h>
#include <dsa.h>
#include <sha1.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>

#include "pp.h"
#include "rnd.h"
#include "algs.h"
#include "hostkey.h"
#include "pkt-util.h"
#include "alg-util.h"
#include "algs-list.h"

static void *dsshk_pub_data;
static int dsshk_pub_len;
static void *dsshk_priv_data;
static int dsshk_priv_len;
static int dss_have_hk;

static int hk_ssh_dss_canuse(int forserver)
{
 if (! forserver) return(1);
 dss_have_hk = read_host_key( &hkalg_ssh_dss,
			&dsshk_pub_data, &dsshk_pub_len,
			&dsshk_priv_data, &dsshk_priv_len );
 return(dss_have_hk);
}

static void hk_ssh_dss_host_key(BPP *b, void **privdp, int *privlp)
{
 if (! dss_have_hk) abort();
 b->K_S.data = dsshk_pub_data;
 b->K_S.len = dsshk_pub_len;
 *privdp = dsshk_priv_data;
 *privlp = dsshk_priv_len;
}

static int hk_ssh_dss_match(const void *d1, int l1, const void *d2, int l2)
{
 return((l1==l2)&&!bcmp(d1,d2,l1));
}

static HASHALG *hk_ssh_dss_prehash(void)
{
 extern HASHALG hashalg_sha1;

 return(&hashalg_sha1);
}

static int hk_ssh_dss_checksig(const void *pkdata, int pklen, const void *hash, const void *sig, int siglen)
{
 __label__ parsefail;

 MP_INT p;
 MP_INT q;
 MP_INT g;
 MP_INT y;
 MP_INT r;
 MP_INT s;
 int rv;
 void *ds;

 static void fail(const void *dp __attribute__((__unused__)), const char *fmt __attribute__((__unused__)), ...)
  { goto parsefail;
  }

 static void clears(void)
  { mpz_clear(&p);
    mpz_clear(&q);
    mpz_clear(&g);
    mpz_clear(&y);
    mpz_clear(&r);
    mpz_clear(&s);
  }

 if (pklen < 11+4+4+4+4) return(0);
 if (bcmp(pkdata,"\0\0\0\7ssh-dss",11)) return(0);
 if (siglen != 11+4+40) return(0);
 if (bcmp(sig,"\0\0\0\7ssh-dss\0\0\0\50",15)) return(0);
 mpz_init(&p);
 mpz_init(&q);
 mpz_init(&g);
 mpz_init(&y);
 mpz_init(&r);
 mpz_init(&s);
 parse_data(pkdata,pklen,fail,
	PP_IGNORE(11),
	PP_MPINT(&p),
	PP_MPINT(&q),
	PP_MPINT(&g),
	PP_MPINT(&y),
	PP_ENDSHERE );
 if (0)
  {
parsefail:;
    clears();
    return(0);
  }
 data_to_mpint(&r,((const char *)sig)+15,20);
 data_to_mpint(&s,((const char *)sig)+15+20,20);
 ds = dsa_init(&p,&q,&g,&y);
 rv = dsa_verify(ds,hash,&r,&s);
 dsa_done(ds);
 if (! rv)
  { printf("hk_ssh_dss_checksig failed:\n");
    printf("H(m) =");
     { int i;
       for (i=0;i<20;i++) printf(" %02x",((const unsigned char *)hash)[i]);
     }
    printf("\n");
    printf("p = ");
    mpz_out_str(stdout,16,&p);
    printf("\n");
    printf("q = ");
    mpz_out_str(stdout,16,&q);
    printf("\n");
    printf("g = ");
    mpz_out_str(stdout,16,&g);
    printf("\n");
    printf("y = ");
    mpz_out_str(stdout,16,&y);
    printf("\n");
    printf("r = ");
    mpz_out_str(stdout,16,&r);
    printf("\n");
    printf("s = ");
    mpz_out_str(stdout,16,&s);
    printf("\n");
  }
 clears();
 return(rv);
}

static int hk_ssh_dss_checkpub(const void *blob, int len)
{
 return((len >= 11) && !bcmp(blob,"\0\0\0\7ssh-dss",11));
}

static int hk_ssh_dss_sign(STR *into, const void *pubdata, int publen, const void *privdata, int privlen, const void *hash)
{
 __label__ parsefail;

 MP_INT p;
 MP_INT q;
 MP_INT g;
 MP_INT y;
 MP_INT r;
 MP_INT s;
 void *dsa;
 unsigned char *res;

 static void fail(const void *dp __attribute__((__unused__)), const char *fmt __attribute__((__unused__)), ...)
  { goto parsefail;
  }

 static void clears(void)
  { mpz_clear(&p);
    mpz_clear(&q);
    mpz_clear(&g);
    mpz_clear(&y);
    mpz_clear(&r);
    mpz_clear(&s);
  }

 if (publen < 11+4+4) return(0);
 if (privlen != 20) return(0);
 if (bcmp(pubdata,"\0\0\0\7ssh-dss",11)) return(0);
 mpz_init(&p);
 mpz_init(&q);
 mpz_init(&g);
 mpz_init(&y);
 mpz_init(&r);
 mpz_init(&s);
 parse_data(pubdata,publen,fail,
	PP_IGNORE(11),
	PP_MPINT(&p),
	PP_MPINT(&q),
	PP_MPINT(&g),
	PP_MPINT(&y),
	PP_ENDSHERE );
 if (0)
  {
parsefail:;
    clears();
    return(0);
  }
 dsa = dsa_init(&p,&q,&g,&y);
 if (! dsa_sign(dsa,hash,privdata,&random_data,&r,&s)) fail(0,0);
 res = malloc(15+20+20);
 bcopy("\0\0\0\7ssh-dss\0\0\0\50",res,15);
 mpint_to_data(&r,res+15,20);
 mpint_to_data(&s,res+15+20,20);
 if (mpz_cmp_ui(&r,0) || mpz_cmp_ui(&s,0)) abort();
 into->data = res;
 into->len = 15 + 20 + 20;
 clears();
 if (! hk_ssh_dss_checksig(pubdata,publen,hash,res,15+20+20)) abort();
 return(1);
}

/*
 * We generate p and q with the NIST-recommended algorithm, from
 *  Applied Cryptography, section 20.1 (pages 489 and 490).  The code
 *  assumes g is a multiple of 8; this is forced on us by our
 *  underlying SHA-1 implementation's being incapable of hashing a
 *  string of bits that's not a multiple of 8 bits long.
 *
 * Actually, this isn't _quite_ the algorithm in the book.  That
 *  algorithm uses SHA; we use SHA-1.  It otherwise is, though, and I
 *  have trouble believing that this makes a significant difference.
 *  We also allow p sizes over 1024 bits.
 *
 * Unfortunately there is another g floating around, that being the g
 *  in the <p,q,g,y> public-key blob.  g is the NIST algorithm g; the
 *  public-key blob g is pkg.
 */
/* Constants, under their algorithm names */
#define g 160
/* Derived constants */
#define gbytes (g>>3)
/* Check */
#if g != gbytes<<3
#error "g must be a multiple of 8"
#endif
static void hk_ssh_dss_genkey(FILE *pubf, FILE *privf, int bits)
{
 /* Algorithm values */
 int L;
 int n;
 int b;
 unsigned char S[gbytes] __attribute__((__aligned__));
 unsigned char U[20] __attribute__((__aligned__));
 unsigned char (*V)[20] __attribute__((__aligned__));
 MP_INT q;
 int C;
 int N;
 int k;
 MP_INT W;
 MP_INT X;
 MP_INT p;
 /* Non-algorithm values */
 void *handle;
 int i;
 int j;
 unsigned char t[gbytes];
 unsigned char hash[20];
 MP_INT two_to_L_1;
 MP_INT t2;
 MP_INT q2;
 MP_INT h;
 MP_INT pkg;
 unsigned char xbuf[22];
 MP_INT x;
 MP_INT y;
 int blobsize;
 unsigned char *blobbuf;
 unsigned char *bp;

 L = (bits < 160) ? 1024 : bits;
 n = (L - 1) / 160;
 b = L - 1 - (n * 160);
 if (b == 0)
  { /* We could let it stao zero, but then V[n] would be computed only
       to be totally ignored.  Avoid the waste.  We know n>0 since we
       ensured L>=160 above. */
    n --;
    b = 160;
  }
 V = malloc((n+1)*sizeof(*V));
 mpz_init(&q);
 mpz_init(&W);
 mpz_init(&X);
 mpz_init(&p);
 mpz_init(&t2);
 mpz_init(&q2);
 mpz_init(&h);
 mpz_init(&pkg);
 mpz_init(&x);
 mpz_init(&y);
 mpz_init_set_ui(&two_to_L_1,1);
 mpz_mul_2exp(&two_to_L_1,&two_to_L_1,L-1);
 while <"outer"> (1)
  { while (1)
     { /* Step 1 */
       random_data(&S[0],gbytes);
       /* Step 2 */
       handle = sha1_init();
       sha1_process_bytes(handle,&S[0],gbytes);
       sha1_result(handle,&U[0]);
       bcopy(&S[0],&t[0],gbytes);
       for (i=gbytes-1;(i>=0)&&(t[i]==0xff);i--) t[i] = 0;
       t[i] ++;
       handle = sha1_init();
       sha1_process_bytes(handle,&t[0],gbytes);
       sha1_result(handle,&hash[0]);
       xor_block(&U[0],&hash[0],&U[0],20);
       /* Step 3 */
       U[0] |= 0x80;
       U[19] |= 1;
       data_to_mpint(&q,&U[0],20);
       /* No step */
       write(1,"S",1);
       /* Steps 4 and 5 */
       mpz_set_ui(&t2,2);
       mpz_powm(&t2,&t2,&q,&q);
       if ((mpz_cmp_ui(&t2,2) == 0) && mpz_probab_prime_p(&q,32)) break;
     }
    /* No step - value used in step 9 */
    mpz_mul_2exp(&q2,&q,1);
    /* Step 6 */
    C = 0;
    N = 2;
    while (1)
     { /* Step 7 */
       for (k=0;k<=n;k++)
	{ bcopy(&S[0],&t[0],gbytes);
	  j = N + k;
	  for (i=gbytes-1;(i>=0)&&j;i--)
	   { j += t[i];
	     t[i] = j & 0xff;
	     j >>= 8;
	   }
	  handle = sha1_init();
	  sha1_process_bytes(handle,&t[0],20);
	  sha1_result(handle,&V[k][0]);
	}
       /* Step 8 */
       if (((b+7)>>3) < 20) bzero(&V[n],20-((b+7)>>3));
       if (b & 7) V[n][((b+7)>>3)-1] &= 0xff >> (8 - (b&7));
       data_to_mpint(&W,&V[n][0],20);
       for (i=n-1;i>=0;i--)
	{ mpz_mul_2exp(&W,&W,160);
	  data_to_mpint(&t2,&V[i][0],20);
	  mpz_add(&W,&W,&t2);
	}
       mpz_add(&X,&W,&two_to_L_1);
       /* Step 9 */
       mpz_mod(&t2,&X,&q2);
       mpz_sub(&t2,&X,&t2);
       mpz_add_ui(&p,&t2,1);
       /* Step 10 */
       if (mpz_cmp(&p,&two_to_L_1) >= 0)
	{ /* Steps 11 and 12 */
	  mpz_set_ui(&t2,2);
	  mpz_powm(&t2,&t2,&p,&p);
	  if ((mpz_cmp_ui(&t2,2) == 0) && mpz_probab_prime_p(&p,32)) break <"outer">;
	}
       /* Step 13 */
       C ++;
       N += n + 1;
       /* No step */
       write(1,"C",1);
       /* Step 14 */
       if (C >= 4096) continue <"outer">;
     }
  }
 printf("\nS = ");
 for (i=0;i<gbytes;i++) printf("%02x",S[i]);
 printf("\nC = %d\n",C);
 printf("p = ");
 mpz_out_str(stdout,16,&p);
 printf("\nq = ");
 mpz_out_str(stdout,16,&q);
 printf("\n");
 mpz_set_ui(&h,2);
 mpz_sub_ui(&t2,&p,1);
 mpz_divexact(&t2,&t2,&q);
 while (1)
  { mpz_powm(&pkg,&h,&t2,&p);
    if (mpz_cmp_ui(&pkg,1) > 0) break;
    mpz_add_ui(&h,&h,1);
  }
 do
  { random_data(&xbuf[0],22);
    data_to_mpint(&x,&xbuf[0],22);
    mpz_mod(&x,&x,&q);
  } while (mpz_cmp_ui(&x,0) == 0);
 mpz_powm(&y,&pkg,&x,&p);
 mpint_to_data(&x,&xbuf[0],20);
 printf("h = %u\n",(unsigned int)mpz_get_ui(&h));
 printf("g = ");
 mpz_out_str(stdout,16,&pkg);
 printf("\nx = ");
 for (i=0;i<20;i++) printf("%02x",xbuf[i]);
 printf("\ny = ");
 mpz_out_str(stdout,16,&y);
 printf("\n");
 blobsize = 11 + ((4+(L>>3)+1) * 3) + (4+21);
 blobbuf = malloc(blobsize+32);
 bp = blobbuf;
 bp = put_string(bp,"ssh-dss",-1);
 bp = put_mpint(bp,&p);
 bp = put_mpint(bp,&q);
 bp = put_mpint(bp,&pkg);
 bp = put_mpint(bp,&y);
 if (bp-blobbuf > blobsize) abort();
 fwrite(blobbuf,1,bp-blobbuf,pubf);
 bzero(blobbuf,blobsize);
 free(blobbuf);
 fwrite(&xbuf[0],1,20,privf);
 mpz_clear(&q);
 mpz_clear(&W);
 mpz_clear(&X);
 mpz_clear(&p);
 mpz_clear(&t2);
 mpz_clear(&q2);
 mpz_clear(&h);
 mpz_clear(&pkg);
 mpz_clear(&x);
 mpz_clear(&y);
 mpz_clear(&two_to_L_1);
}
#undef L
#undef n
#undef b
#undef g
#undef gbytes
#undef BLOBSIZE

static const char *hk_ssh_dss_altnames[]
 = { "dss", "dsa", 0 };

HKALG hkalg_ssh_dss
 = { "ssh-dss", 0, 1,
     &hk_ssh_dss_canuse,
     &hk_ssh_dss_host_key,
     &hk_ssh_dss_match,
     &hk_ssh_dss_prehash,
     &hk_ssh_dss_checksig,
     &hk_ssh_dss_sign,
     &hk_ssh_dss_genkey,
     &hk_ssh_dss_checkpub,
     &hk_ssh_dss_altnames[0],
     "identity.dsa",
     "hostkey.dsa" };