/*        Frogbit demonstration and challenge program

          Copyright (C) 1996 CONNOTECH Experts-Conseils Inc.

Author:   Thierry Moreau

          CONNOTECH Experts-Conseils Inc.
          9130 Place de Montgolfier
          Montreal, Qc
          Canada
          H2M 2A1

Date:     April 17, 1996, revised April 2005

Revision History:

     Bug fix in LFSR generator(!).

     Idiosyncracies of 16-bit C.

     Fixed a name clash with a BSD definition in string.h

     Removed huffman coding for packing the final state in the verbose mode

     Reverted to binary ciphertext file; default binary cleartext file;
     command-line options starting with - instead of +

     Added the -o[1-7] option to omit from 1 to 7 bits from the end of the file,
     for enhanced flexibility in the standard challenge

     Enhanced source code readability with the last source code change

     Fixed a bug in state input rule enforcement

     Implemented 20 LFSRs from pi hexadecimal notation instead of 10 simpler
     LFSRs for the 10 frogbit PRNGs

     Changed from most significant bit first to least significant bit first

     Minor source code readability enhancements

Purposes: 1) to foster cryptanalysis attempts against the Frogbit
          hash function,
          2) to foster cryptanalysis attempts against the Frogbit
          encryption, granted a 25-years old attack on the
          underlying stream cipher.

Comment:  This program provides a simple file encryption
          capability, but the (claimed) distinctive advantage of
          the Frogbit algorithm is DATA INTEGRITY protection. As
          a consequence, the "challenge" aspect of this program
          relates to finding collision in a hash function.

Prerequisite: This is cryptographic stuff. The intended reader is
          familiar with the subject area.

Practical limitations: No attempt has been made to make the
          encryption capability convenient and/or portable.
          Little validation is applied to the input data (but the
          parameter values are forced to abide by the theoretical
          requirements). Moreover, although the cryptographic
          strength of this program is conjectured to be good, an
          important component (the underlying pseudo-random
          algorithm) has been deliberately chosen to be an
          INSECURE alternative.

User's guide:

     This is ANSI C source code. The compiled program is a
     command-line utility, taking four optional file names:
     cleartext file, ciphertext file, final secret key file, and
     initial secret key file.

     The main challenge is to find two pairs <cleartext file,
     initial secret key file> that produce the same final secret
     key file.

     The auxiliary challenge is to find an algorithm that
     recovers the initial secret key file from a cleartext file
     and the corresponding ciphertext file.

How to read this source code:

     Sequentially. Housekeeping stuff is identified with /**/
/*   at the beginning of each line. In addition, /*RULE*/
/*   identifies places in the source code where a theoretical
     rule is enforced (in the context of processing the initial
     secret key file).

*/

/**********************************************************************/
/***                                                                ***/
/***                The base Frogbit algorithm                      ***/
/***                                                                ***/
/**********************************************************************/

 typedef int ind_t;
 typedef int bit;

/*--------------------------------------------------------------------*/
/*---------------- the state of the Frogbit algorithm ----------------*/

 ind_t T[10];      /* the current permutation table, T(i-1-r'(i-1))   */
 ind_t d_;         /* the current key stream number, d'(i-1)          */

 bit s;            /* the previous bit, s{i-1}                        */

 /* local variables for the run length process                        */
 ind_t r_;         /* the current bounded run count, r'(i-1)          */
 ind_t acc_d;      /* accumulated binary representation K2{i-1}, k2{i}*/

/*--------------------------------------------------------------------*/
/*------------------ keystream "drift" accumulators ------------------*/

    /* These accumulators are for information purposes. Their final
       values may come into play for a hash code. The active state of
       the pseudo-random generators is dealt with later.              */

 struct cntr
 {
   unsigned long c;  /* A count of consumed keystream bits ...        */
   int i;            /*               ... for this key stream source. */
 } drift_cnt[10];

/*--------------------------------------------------------------------*/
/*------------------ the index permutation process -------------------*/

void index_permutation(int j)
{
  int temp;
  int temp_d_= T[j];
  switch((d_<<1)+s)
  {
  case 0:
     temp=T[0];T[0]=T[5];T[5]=T[2];T[2]=T[7];T[7]=temp;
     temp=T[1];T[1]=T[8];T[8]=T[6];T[6]=T[4];T[4]=T[3];T[3]=T[9];
               T[9]=temp;
    break;
  case 1:
     temp=T[0];T[0]=T[2];T[2]=T[7];T[7]=temp;
     temp=T[1];T[1]=T[3];T[3]=T[6];T[6]=T[9];T[9]=T[4];T[4]=T[8];
               T[8]=T[5];T[5]=temp;
    break;
  case 2:
     temp=T[0];T[0]=T[6];T[6]=T[8];T[8]=T[9];T[9]=T[5];T[5]=T[7];
               T[7]=T[1];T[1]=temp;
     temp=T[2];T[2]=T[4];T[4]=T[3];T[3]=temp;
    break;
  case 3:
     temp=T[0];T[0]=T[6];T[6]=temp;
     temp=T[1];T[1]=T[5];T[5]=T[3];T[3]=T[4];T[4]=T[2];T[2]=T[8];
               T[8]=T[7];T[7]=T[9];T[9]=temp;
    break;
  case 4:
     temp=T[0];T[0]=T[3];T[3]=T[6];T[6]=T[5];T[5]=T[1];T[1]=T[2];
               T[2]=temp;
     temp=T[4];T[4]=T[8];T[8]=T[7];T[7]=T[9];T[9]=temp;
    break;
  case 5:
     temp=T[0];T[0]=T[6];T[6]=T[7];T[7]=T[3];T[3]=T[1];T[1]=T[2];
               T[2]=T[9];T[9]=temp;
     temp=T[4];T[4]=T[5];T[5]=T[8];T[8]=temp;
    break;
  case 6:
     temp=T[0];T[0]=T[4];T[4]=T[3];T[3]=T[7];T[7]=T[6];T[6]=T[1];
               T[1]=T[8];T[8]=T[5];T[5]=temp;
     temp=T[2];T[2]=T[9];T[9]=temp;
    break;
  case 7:
     temp=T[0];T[0]=T[5];T[5]=T[4];T[4]=temp;
     temp=T[1];T[1]=T[9];T[9]=T[8];T[8]=T[6];T[6]=T[2];T[2]=T[3];
               T[3]=T[7];T[7]=temp;
    break;
  case 8:
     temp=T[0];T[0]=T[8];T[8]=T[9];T[9]=T[5];T[5]=T[3];T[3]=T[2];
               T[2]=T[1];T[1]=temp;
     temp=T[4];T[4]=T[6];T[6]=T[7];T[7]=temp;
    break;
  case 9:
     temp=T[0];T[0]=T[9];T[9]=T[7];T[7]=T[8];T[8]=T[1];T[1]=T[4];
               T[4]=T[2];T[2]=T[6];T[6]=temp;
     temp=T[3];T[3]=T[5];T[5]=temp;
    break;
  case 10:
     temp=T[0];T[0]=T[7];T[7]=T[2];T[2]=T[4];T[4]=T[1];T[1]=T[6];
               T[6]=T[5];T[5]=T[9];T[9]=temp;
     temp=T[3];T[3]=T[8];T[8]=temp;
    break;
  case 11:
     temp=T[0];T[0]=T[1];T[1]=T[4];T[4]=T[7];T[7]=T[5];T[5]=T[2];
               T[2]=T[8];T[8]=T[3];T[3]=temp;
     temp=T[6];T[6]=T[9];T[9]=temp;
    break;
  case 12:
     temp=T[0];T[0]=T[7];T[7]=T[6];T[6]=T[3];T[3]=temp;
     temp=T[1];T[1]=T[4];T[4]=T[9];T[9]=T[2];T[2]=T[5];T[5]=T[8];
               T[8]=temp;
    break;
  case 13:
     temp=T[0];T[0]=T[3];T[3]=T[5];T[5]=T[2];T[2]=temp;
     temp=T[1];T[1]=T[9];T[9]=T[7];T[7]=T[4];T[4]=T[6];T[6]=T[8];
               T[8]=temp;
    break;
  case 14:
     temp=T[0];T[0]=T[8];T[8]=T[4];T[4]=T[2];T[2]=T[1];T[1]=T[9];
               T[9]=T[3];T[3]=temp;
     temp=T[5];T[5]=T[7];T[7]=T[6];T[6]=temp;
    break;
  case 15:
     temp=T[0];T[0]=T[9];T[9]=T[6];T[6]=T[3];T[3]=T[1];T[1]=T[5];
               T[5]=temp;
     temp=T[2];T[2]=T[4];T[4]=T[7];T[7]=T[8];T[8]=temp;
    break;
  case 16:
     temp=T[0];T[0]=T[7];T[7]=T[2];T[2]=T[6];T[6]=T[1];T[1]=T[3];
               T[3]=T[9];T[9]=T[8];T[8]=temp;
     temp=T[4];T[4]=T[5];T[5]=temp;
    break;
  case 17:
     temp=T[0];T[0]=T[4];T[4]=T[1];T[1]=T[7];T[7]=T[8];T[8]=temp;
     temp=T[2];T[2]=T[9];T[9]=T[3];T[3]=T[5];T[5]=T[6];T[6]=temp;
    break;
  case 18:
     temp=T[0];T[0]=T[2];T[2]=T[3];T[3]=T[8];T[8]=temp;
     temp=T[1];T[1]=T[7];T[7]=T[5];T[5]=T[6];T[6]=T[4];T[4]=T[9];
               T[9]=temp;
    break;
  case 19:
     temp=T[0];T[0]=T[1];T[1]=T[6];T[6]=T[7];T[7]=T[3];T[3]=T[4];
               T[4]=temp;
     temp=T[2];T[2]=T[5];T[5]=T[9];T[9]=T[8];T[8]=temp;
    break;
  }
  d_ = temp_d_;
}

/*--------------------------------------------------------------------*/
/*-------------------- the core Frogbit algorithm --------------------*/

bit get_PR_bit(ind_t PR_gen_selector,int ik); /* Forward reference:
                                          key stream sources          */

bit encipher_bit(bit m_i_)
{
   int base;

   bit k1_i_   = get_PR_bit(d_,0);
   bit k2_i_   = get_PR_bit(d_,1);

   bit s_i_    = m_i_^k1_i_;

   drift_cnt[d_].c++;

   if (s!=s_i_)
        if (r_==0) base=0;
        else       base=(acc_d+1)<<1;
   else if (r_!=0) base=(acc_d+3)<<1;
        else
        {
          acc_d=k2_i_;
          r_=1;
          return s_i_^k2_i_;
        }

   index_permutation(base+k2_i_);
   r_= 0;
   s=s_i_;

   return s_i_^k2_i_;
}

bit decipher_bit(bit e_i_)
{
   int base;

   bit k1_i_   = get_PR_bit(d_,0);
   bit k2_i_   = get_PR_bit(d_,1);

   bit s_i_    = e_i_^k2_i_;

   drift_cnt[d_].c++;

   if (s!=s_i_)
        if (r_==0) base=0;
        else       base=(acc_d+1)<<1;
   else if (r_!=0) base=(acc_d+3)<<1;
        else
        {
          acc_d=k2_i_;
          r_=1;
          return s_i_^k1_i_;
        }

   index_permutation(base+k2_i_);
   r_= 0;
   s=s_i_;

   return s_i_^k1_i_;
}

/*--------------------------------------------------------------------*/
/*------------ default initialization of the Frogbit state -----------*/

void start_cipher(void) /* This mechanism may be overridden, and indeed
                           it is when a secret key file includes more
                           than just the PRNG state.                  */
{
  ind_t i;
  d_= s= r_= 0;

  for (i=0;i<10;i++)
  {
    T[i]=i;
    drift_cnt[i].c=0;
    drift_cnt[i].i=i;
  }

/* do the processing as if m{i}=0 until one d(i) is drawn,
   and do it once more                                          */
  do
    encipher_bit(0);
  while (r_!=0);
  encipher_bit(0);
}

/*--------------------------------------------------------------------*/

/**/#include <stdio.h>
/**/#include <string.h>
/**/#include <stdlib.h>
/**/#include <ctype.h>
/**/#include <limits.h>
/**/#include <assert.h>

#if (INT_MAX<=32767)
#define L "l"
#else
#define L
#endif

/*--------------------------------------------------------------------*/
/*------------------- file encryption/decryption ---------------------*/

int omit_count=0;

void encipher(FILE *in, FILE *out)
{
  int i, c, e;
  int cnext;
  cnext=getc(in);
  if (EOF==cnext)  return;
  for (;;)
  {
    c=cnext;
    cnext=getc(in);
    if (EOF==cnext)  break;

    e=0;
    for (i=1;i<=(1<<(CHAR_BIT-1));i<<=1)
      if (encipher_bit(0!=(i&c)))  e|=i;

    fputc(e,out);
  }

  e=0;
  for (i=1;i<=(1<<(CHAR_BIT-omit_count-1));i<<=1)
    if (encipher_bit(0!=(i&c)))  e|=i;

  fputc(e,out);
}

void decipher(FILE *in, FILE *out)
{
  int i, c, e;
  int cnext;
  cnext=getc(in);
  if (EOF==cnext)  return;
  for (;;)
  {
    e=cnext;
    cnext=getc(in);
    if (EOF==cnext)  break;

    c=0;
    for (i=1;i<=(1<<(CHAR_BIT-1));i<<=1)
      if (decipher_bit(0!=(i&e)))  c|=i;

    fputc(c,out);
  }

  c=0;
  for (i=1;i<=(1<<(CHAR_BIT-omit_count-1));i<<=1)
    if (decipher_bit(0!=(i&e)))  c|=i;

  fputc(c,out);
}

/**********************************************************************/
/***                                                                ***/
/***              read and write the Frogbit state                  ***/
/***             (minimal and extended secret keys)                 ***/
/***                                                                ***/
/**********************************************************************/

/*--------------------------------------------------------------------*/
/*---------- the state of the 10 PRNGs (minimal secret key) ----------*/

unsigned long next [10][2]={{1,1},{1,1},{1,1},{1,1},{1,1}
                           ,{1,1},{1,1},{1,1},{1,1},{1,1}};

/*--------------------------------------------------------------------*/
/*---- get the state from the file data, enforce theoretical rules ---*/

void adjust_prng_state(void);                   /* forward references */
void get_prng_design(int argc, char *argv[]);

void get_state(int argc, char *argv[])
{
  int i;

  /*{ PRNG state }*/
  for (i=0;i<10;i++) {
    if (argc>(2*i+1))
    {
      next[i][0]=strtoul(argv[2*i+1],NULL,0);
    }
    else
      break;

    if (argc>(2*i+2))
    {
      next[i][1]=strtoul(argv[2*i+2],NULL,0);
    }
    else
      break;
  }

  if (argc>=21)
  {
    /*{ key-stream selection state }*/
    d_= 0;
    if (argc>21)
      d_=strtoul(argv[21],NULL,0)%10;             /*RULE*//* 0<=d_<10 */
    /*{ index permutation state }*/
    for (i=0;i<10;i++)
      T[i]=i;
    for (i=0;i<10;i++)
      if (argc>(i+22))
      {
        int ii;
        int cand=strtoul(argv[i+22],NULL,0)%10; /*RULE*//* 0<=T[i]<10 */
        for (ii=i;ii<10;ii++)
          if (T[ii]==cand)
            break;
        if (ii<10)       /*RULE*//* the vector T[10] is a permutation */
        {
          for (;ii>i;ii--)
            T[ii]=T[ii-1];
          T[i]=cand;
        }
      }
      else
        break;

    /*{ run length encoding (RLE) state }*/
    s= r_= acc_d= 0;
    if (argc>32)
      s=strtoul(argv[32],NULL,0)%2;      /*RULE*//* s is a single bit */
    if (argc>33)
      r_=strtoul(argv[33],NULL,0)%2;               /*RULE*//* 0<=r_<2 */
    if ((argc>34)&&(r_>0))
    {
      acc_d=strtoul(argv[34],NULL,0);
      acc_d%=1<<r_;                       /*RULE*//* 0<=acc_d<(2**r_) */
    }
    if (argc>35)
      /*{ PRNG design parameters }*/
      get_prng_design(argc-34,argv+34); /* rules specific to the PRNG */
    adjust_prng_state();                /* rules specific to the PRNG */
    for (i=0;i<10;i++)
    {
      drift_cnt[i].c=0;
      drift_cnt[i].i=i;
    }
  }
  else
  { /* secret key limited to PRNG state, use
       default Frogbit initialization           */
    adjust_prng_state();                /* rules specific to the PRNG */
    start_cipher();
  }
}

/*--------------------------------------------------------------------*/
/*----------- write the state to the final secret key file -----------*/

/**/void print_prng_design(FILE *fp); /* forward reference */
/**/void print_drift_accum(FILE *fp); /* forward reference */

/**/int verbose_flag=0;

/**/void print_state(FILE *fp)
/**/{
/**/  int i;
/**/  adjust_prng_state();
/**/  fprintf(fp,"{ PRNG state }");
/**/  for (i=0;i<10;i++)
/**/  {
/**/    fprintf(fp," 0x%" L "X 0x%" L "X",next[i][0],next[i][1]);
/**/    if (0==((i+2)%3)) fprintf(fp,"\n");
/**/  }
/**/  fprintf(fp,"\n");
/**/  if (verbose_flag)
/**/    print_drift_accum(fp);
/**/  fprintf(fp,"{ key-stream selection state } %d\n",d_);

/**/  fprintf(fp,"{ index permutation state }");
/**/  for (i=0;i<10;i++)
/**/    fprintf(fp," %d",T[i]);
/**/  fprintf(fp,"\n{ run length encoding (RLE) state } %d %d %d\n"
/**/         ,s,r_,acc_d%(1<<r_));
/**/  print_prng_design(fp);
/**/}

/**/int cmp_cntr(const void *a,const void *b)
/**/{
/**/  return ( (((struct cntr *)a)->c<((struct cntr *)b)->c)
/**/          ?-1
/**/          :(((struct cntr *)a)->c>((struct cntr *)b)->c)
/**/         );
/**/}

/**/void print_drift_accum(FILE *fp)
/**/{
/**/  int i;
/**/  qsort(drift_cnt,10,sizeof(drift_cnt[0]),cmp_cntr);
/**/  fprintf(fp,"{ keystream drift: %d:%" L "d"
/**/                                 ,drift_cnt[0].i,drift_cnt[0].c);
/**/  for(i=1;i<10;i++)
/**/    fprintf(fp," %d+%" L "d",drift_cnt[i].i
/**/                       ,drift_cnt[i].c-drift_cnt[i-1].c);
/**/  fprintf(fp," }\n");
/**/}

/**********************************************************************/
/***                                                                ***/
/***                      housekeeping tasks                        ***/
/***                                                                ***/
/**********************************************************************/

/*--------------------------------------------------------------------*/
/*-------- housekeeping: lexical analysis of secret key file ---------*/

/**/char file_buf[8*1024];

/**/void parse_state(FILE *fp)
/**/{
/**/  int argc;
/**/  char *argv[25+11];
/**/  char *s;

/**/  file_buf[fread(file_buf,1,sizeof(file_buf)-1,fp)]=0;
/**/  fclose(fp);
/**/  s=file_buf;
/**/  argv[0]="?";
/**/  for(argc=1;argc<(25+11);argc++)
/**/  {
/**/    for (;;)
/**/    {
/**/      char *end_comment;
/**/      argv[argc]=strtok(s," \n\r\t\v\f"); s=NULL;
/**/      if ((NULL==argv[argc])||('{'!=argv[argc][0]))
/**/        break;
/**/      for(;;)
/**/      {
/**/        end_comment=strchr(argv[argc],'}');
/**/        if (NULL!=end_comment) break;
/**/        argv[argc]=strtok(NULL," \n\r\t\v\f");
/**/        if (NULL==argv[argc])
/**/          break;
/**/      }
/**/      if (NULL==argv[argc])
/**/        break;
/**/      if (0!=*(end_comment+1))
/**/      {
/**/        argv[argc]=end_comment+1;
/**/        break;
/**/      }
/**/    }
/**/    if (NULL==argv[argc])
/**/      break;
/**/  }
/**/  get_state(argc,argv);
/**/}

/*--------------------------------------------------------------------*/
/*---------- housekeeping: help to the user in case of error ---------*/

/**/void usage(char *s)
/**/{
/**/  fprintf(stderr,
/**/     "usage: %s [flags] [inp [out [final [init]]]]\n"
/**/     "\n"
/**/     "  Frogbit file encryption demo\n"
/**/     "\n"
/**/     "flags:\n"
/**/     "   -e     encryption operation (default)\n"
/**/     "   -d     decryption operation\n"
/**/     "   -t     cleartext file is text format (default is binary file)\n"
/**/     "   -f     force overwriting existing files\n"
/**/     "   -v     a more verbose final state file\n"
/**/     "   -o[1-7] omit so many bits at the end of input file\n"
/**/     "\n"
/**/     "arguments\n"
/**/     "   inp:   input file name (default: standard input)\n"
/**/     "   out:   output file name (default: standard output)\n"
/**/     "   final: final state file name (default: standard error)\n"
/**/     "   init:  initial state file name (secret key)\n"
/**/    ,s);
/**/}

/*--------------------------------------------------------------------*/
/*- housekeeping: the main program, checking command line parameters -*/

/**/int main (int argc, char *argv[])
/**/{
/**/  FILE *in=stdin;
/**/  FILE *out=stdout;
/**/  FILE *init_st=NULL;
/**/  FILE *final_st=stderr;
/**/  int decrypt_flag=0;
/**/  int binary_flag=1;
/**/  int force_flag=0;
/**/  int i;

/**/  for (i=1;i<argc;i++)
/**/  {
/**/    if ('-'==argv[i][0])
/**/      switch (toupper(argv[i][1]))
/**/      {
/**/        case 'D':
/**/          decrypt_flag=1;
/**/        case 'E':
/**/          break;
/**/        case 'F':
/**/          force_flag=1;
/**/          break;
/**/        case 'T':
/**/          binary_flag=0;
/**/          break;
/**/        case 'V':
/**/          verbose_flag=1;
/**/          break;
/**/        case 'O':
/**/          omit_count= ((argv[i][2]>='1')&&(argv[i][2]<='7'))
/**/                     ?(argv[i][2]-'0')
/**/                     :0;
/**/          break;
/**/        default:
/**/        {
/**/          fprintf(stderr,"Error: unknown flag!\n\n");
/**/          usage(argv[0]);
/**/          exit(EXIT_FAILURE);
/**/        }
/**/      }
/**/    else
/**/      break;
/**/  }

/**/  if (argc>(i))
/**/  {
/**/    in=fopen(argv[i],(binary_flag||decrypt_flag)?"rb":"r");
/**/    if (NULL==in)
/**/      fprintf(stderr,"Error: can't open file \"%s\"!\n\n",argv[i]);
/**/  }
/**/  if (argc>(i+1))
/**/  {
/**/    out=fopen(argv[i+1],"r"); if (out) fclose(out);
/**/    if ((NULL==out)||force_flag)
/**/    {
/**/      out=fopen(argv[i+1],(binary_flag||!decrypt_flag)?"wb":"w");
/**/      if (NULL==out)
/**/    fprintf(stderr,"Error: can't open file \"%s\"!\n\n",argv[i+1]);
/**/    }
/**/    else
/**/    {
/**/      fprintf(stderr,"Error: file \"%s\" already exists!\n\n"
                        ,argv[i+1]);
/**/      out=NULL;
/**/    }
/**/  }
/**/  if (argc>(i+2))
/**/  {
/**/    final_st=fopen(argv[i+2],"r"); if (final_st) fclose(final_st);
/**/    if ((NULL==final_st)||force_flag)
/**/    {
/**/      final_st=fopen(argv[i+2],"w");
/**/      if (NULL==final_st)
/**/        fprintf(stderr,"Error: can't open file \"%s\"!\n\n"
                          ,argv[i+2]);
/**/    }
/**/    else
/**/    {
/**/      fprintf(stderr,"Error: file \"%s\" already exists!\n\n"
                        ,argv[i+2]);
/**/      final_st=NULL;
/**/    }
/**/  }
/**/  if (argc>(i+3))
/**/  {
/**/    init_st=fopen(argv[i+3],"r");
/**/    if (NULL==init_st)
/**/     fprintf(stderr,"Error: can't open file \"%s\"!\n\n",argv[i+3]);
/**/  }
/**/  if ((NULL==in)||(NULL==out)||(NULL==final_st))
/**/  {
/**/    usage(argv[0]);
/**/    exit(EXIT_FAILURE);
/**/  }

/**********************************************************************/
/***                                                                ***/
/***              here is what this program really does!            ***/
/***                                                                ***/
/**********************************************************************/

  if (NULL!=init_st) parse_state(init_st);/* use the initial key file */
  else               start_cipher();       /* use defaut (secret) key */

  if (decrypt_flag)
    decipher(in,out);
  else
    encipher(in,out);
  print_state(final_st);

  fclose(in);
  fclose(out);
  fclose(final_st);

  return EXIT_SUCCESS;
}

/**********************************************************************/
/***                                                                ***/
/***              the PRNG, pseudo-random number generator          ***/
/***                                                                ***/
/**********************************************************************/
/*

The following criteria were used to select a Pseudo-Random Number
Generator:
  -  EASILY cryptanalyzed (when used in a SIMPLE stream cipher),
  -  simple to program,
  -  single bit output,
  -  predictable period,
  -  "key space" close to 2**32 per generator.

The rationale for the first criteria is to present a SINGLE
challenge to cryptanalysis: the very FROGBIT algorithm.

We selected the "Linear Feedback Shift Register" (LFSR) generator
(also known as the Tausworthe generator). We use pairs of
independent LFSR generators to generate the bit pairs needed by
the Frogbit algorithm.

For purpose of programming, here are a few simple facts about the
LFSR generator:
i)   the single parameter of a LFSR generator is a binary number
     representing a "polynomial";
ii)  the "degree" of this polynomial is the rank of the highest
     bit of this number;
iii) the polynomial must be "irreductible", a property analogue
     to the primality of numbers, but based on "polynomial
     arithmetic",
iv)  the degree of the polynomial must be a "Marsenne prime
     number" (p such that 2**p-1 is prime), that is 2, 3, 5, 7,
     13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, and
v)   the state of the generator is a number strictly between 0
     and 2**degree.

Briefly, our design allows any irreductible polynomial of degree
up to 31 (the 20 polynomials must be of the same degree).

An extra benefit of the LFSR is the ability to let the user
customize the generator. This feature is included in this program
in order to provide another variable for cryptanalysis purposes.
Essentially, we allow the "initial secret key file" to specify
the degree, and the 20 polynomials (actually, the program uses
the largest polynomial not exceeding the specified value). The
default polynomials are the 20 largest irreductible polynomials
of degree 31.

*/

/*--------------------------------------------------------------------*/
/*--------- the design parameters of the 10 LSFR generators ----------*/

int degree=31;

unsigned long poly[10][2]=
#define DEFAULT_POLYGONS \
{{0xA43F6A87,0x85A308A7},{0x931989F7,0x8370732D}   \
/*3.243F6A88   85A308D3     13198A2E   03707344 */ \
,{0xA4093815,0xA99F31D1},{0x882EFA97,0xEC4E6C63}   \
/*  A4093822   299F31D0     082EFA98   EC4E6C89 */ \
,{0xC52821B5,0xB8D0135D},{0xBE54668B,0xB4E90C4B}   \
/*  452821E6   38D01377     BE5466CF   34E90C6C */ \
,{0xC0AC2993,0xC97C50A9},{0xBF84D5A1,0xB54708F7}   \
/*  C0AC29B7   C97C50DD     3F84D5B5   B5470917 */ \
,{0x9216D5CF,0x8979FAF1},{0xD1310BA1,0x98DFB581}}; \
/*  9216D5D9   8979FB1B     D1310BA6   98DFB5AC */
DEFAULT_POLYGONS

/*--------------------------------------------------------------------*/
/*-------------------- the LSFR generator program --------------------*/

bit get_PR_bit(ind_t ind,int ik)
{
  /* parity of each byte value */
  static const unsigned char parity[1<<CHAR_BIT]=
{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1
,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1
,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1
,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1
,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
};

  union  /* an ANSI C programmer's trick to access individual bytes
            of a 32 bit number                                        */
  {
    unsigned long whole;
    unsigned char part[4];
  } s;
  bit return_value;

  s.whole=next[ind][ik]&poly[ind][ik];
  return_value=( parity[s.part[0]]
                ^parity[s.part[1]]
                ^parity[s.part[2]]
                ^parity[s.part[3]]
               );
  next[ind][ik]= (next[ind][ik]>>1)
                |(((unsigned long)return_value)<<(degree-1));
  return return_value;
}

/*--------------------------------------------------------------------*/
/*-- the theoretic rules specific to the state of the LSFR generator -*/

void adjust_prng_state(void)
{
  int i;
  for (i=0;i<10*2;i++)
  {
    next[i/2][i%2]&=(1UL<<degree)-1;     /*RULE*//* for a degree "n"
                               polynomial,there are "n" bits of state */
    if (0==next[i/2][i%2]) next[i/2][i%2]=1;  /*RULE*//* the state =0
                                                      must be avoided */
  }
}

/**********************************************************************/
/***                                                                ***/
/***      we allow modification of the PRNG "design" parameters     ***/
/***                                                                ***/
/**********************************************************************/

/*--------------------------------------------------------------------*/
/*- get the LSFR design from the file data, enforce theoretical rules */

void prepare_irreductibles(void);
int is_irreductible(unsigned long n);

void get_prng_design(int argc, char *argv[])
{
  unsigned long cur_poly;
  int i;
  /*{ PRNG design parameters }*/
  if (argc>1)
    degree=atoi(argv[1]);
         /*RULE*//* the degree of the polynomials is a Marsenne prime
                    number between 13 and 31 inclusive                */
  if ((degree!=13)&&(degree!=17)&&(degree!=19))
    degree=31;

  prepare_irreductibles();
  cur_poly=(1L<<degree)|((1L<<degree)-1);
  for (i=0;i<10*2;i++)
  {
    if (argc>(i+2))
      cur_poly=strtoul(argv[i+2],NULL,0);
    for(;;)
    {
              /*RULE*//* the same degree applies to every polynomials */
             /*RULE*//* an irreductible polynomial has term x**0 to 1 */
       cur_poly &= (1L<<degree)-1;
       cur_poly |= (1L<<degree)+1;
                      /*RULE*//* the polynomials must be irreductible */
       if (is_irreductible(cur_poly))
       {
         int ii;          /*RULE*//* the polynomials must be distinct */
         for (ii=0;ii<i;ii++)
           if (cur_poly==poly[ii/2][ii%2])
             break;
         if (ii>=i)
           break;
       }
       cur_poly-=2; /* try another one */
    }
    poly[i/2][i%2]=cur_poly;
    cur_poly-=2;
  }
}

/*--------------------------------------------------------------------*/
/* write the LSFR design to the final file (if not the default design)*/

/**/void print_prng_design(FILE *fp)
/**/{
/**/  static const unsigned long def_poly[10][2]=DEFAULT_POLYGONS
/**/  int i;
/**/  for (i=0;i<10*2;i++)
/**/    if (poly[i/2][i%2]!=def_poly[i/2][i%2])
/**/      break;
/**/  if ((i<10*2)||(degree!=31)||verbose_flag)
/**/  {
/**/    fprintf(fp,"{ PRNG design parameters } %d",degree);
/**/    for (i=0;i<10;i++)
/**/    {
/**/      fprintf(fp," 0x%" L "X 0x%" L "X",poly[i][0],poly[i][1]);
/**/      if (0==((i+2)%3)) fprintf(fp,"\n");
/**/    }
/**/    fprintf(fp,"\n");
/**/  }
/**/}

/**********************************************************************/
/***                                                                ***/
/***                     polynomial arithmetic                      ***/
/***                                                                ***/
/**********************************************************************/

/*--------------------------------------------------------------------*/
/*-------------------- polynomial multiplication ---------------------*/

/**/unsigned long mult_poly(unsigned long a, unsigned long b)
/**/{
/**/  unsigned long r=0;
/**/  unsigned long i;
/**/  for (i=1;i<=b;i<<=1)
/**/  {
/**/    if (b&i)
/**/      r^=a;
/**/    a<<=1;
/**/  }
/**/  return r;
/**/}

/*--------------------------------------------------------------------*/
/*----------------------- polynomial division ------------------------*/

/**/unsigned long div_poly( unsigned long div_end
/**/                      , unsigned long div_or
/**/                      , unsigned long *remainder)
/**/{
/**/  int m_end=-1;
/**/  int m_or=-1;
/**/  unsigned long r=0;
/**/  unsigned long rem=div_end;
/**/  int i;
/**/  for (i=0;i<(CHAR_BIT*sizeof(unsigned long));i++)
/**/  {
/**/    if (div_end&(1L<<i))
/**/      m_end=i;
/**/    if (div_or&(1L<<i))
/**/      m_or=i;
/**/  }
/**/  if (m_or<0) assert("Polynomial division by zero!");
/**/  for (;m_end>=m_or;m_end--)
/**/  {
/**/    if (rem&(1<<m_end))
/**/    {
/**/      rem ^= div_or<<(m_end-m_or);
/**/      r|=1<<(m_end-m_or);
/**/    }
/**/  }
/**/  *remainder=rem;
/**/  return r;
/**/}

/*--------------------------------------------------------------------*/
/*------------- find all 16 bit irreductible polynomials -------------*/

/**/#define NB_USHORT_IRREDUCTIBLES 4720
/**/unsigned int nb_ushort_irreductibles;
/**/unsigned short all_ushort_irreductibles[NB_USHORT_IRREDUCTIBLES];


/**/void prepare_irreductibles(void)
/**/{
/**/#define MAX 0x10000L
/**/#define INDICE(x) ((x-3)/2)

/**/  char *irreductible = (char *)malloc((size_t)INDICE(MAX));
/**/  long i;
/**/  long i_fact;
/**/  for (i=0;i<INDICE(MAX);i++)
/**/    irreductible[i] = 1;
/**/  for (i_fact=3;i_fact<MAX;i_fact+=2)
/**/    if (irreductible[INDICE(i_fact)])
/**/      for (i=2;;i++)
/**/      {
/**/        unsigned long ip=mult_poly(i_fact,i);
/**/        if (ip >= MAX)
/**/          break;
/**/        if (ip&1) irreductible[INDICE(ip)] = 0;
/**/      }

/**/  nb_ushort_irreductibles = 1;
/**/  for (i=0;i<INDICE(MAX);i++)
/**/    if (irreductible[i])  nb_ushort_irreductibles++;
/**/  assert(NB_USHORT_IRREDUCTIBLES==nb_ushort_irreductibles);

/**/  all_ushort_irreductibles[0] = 2;
/**/  i_fact = 1;
/**/  for (i=3;i<MAX;i+=2)
/**/    if (irreductible[INDICE(i)])
/**/       all_ushort_irreductibles[i_fact++] = i;
/**/  free(irreductible);

/**/#undef MAX
/**/#undef INDICE
/**/}

/*--------------------------------------------------------------------*/
/*----------------- 32 bit polynomial irreductibility ----------------*/

/**/int is_irreductible(unsigned long n)
/**/{
/**/  unsigned int i;
/**/  if (n>1)
/**/   for (i=0;i<nb_ushort_irreductibles;i++)
/**/   {
/**/    unsigned long rem;
/**/    if (all_ushort_irreductibles[i] >= n)
/**/       break;
/**/
/**/    div_poly(n,all_ushort_irreductibles[i],&rem);
/**/    if (0 == rem)
/**/      return 0;
/**/   }
/**/  return 1;
/**/}

/*--------------------------------------------------------------------*/
/*----------------------------- the end ------------------------------*/