CONNOTECH Experts-conseils Inc.

Source Code for the Core Frogbit Data Integrity Algorithm

by Thierry Moreau

© 1997 CONNOTECH Experts-conseils Inc.

Program listing "A" 

/**********************************************************************/
/***                                                                ***/
/***                The core Frogbit algorithm                      ***/
/***                                                                ***/
/**********************************************************************/

 typedef int index;
 typedef int bit;

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

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

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

 /* local variables for the run length process                        */
 index r_;         /* the current bounded run count, r'(i-1)          */
 index 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(index PR_gen_selector); /* Forward reference: key stream
                                          sources                     */

bit encipher_bit(bit m_i_)
{
   int base;

   bit k1_i_   = get_PR_bit(d_);
   bit k2_i_   = get_PR_bit(d_);

   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_);
   bit k2_i_   = get_PR_bit(d_);

   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_;
}

Program listing "B" 

/**********************************************************************/
/***                                                                ***/
/***                The core Frogbit algorithm                      ***/
/***                                                                ***/
/**********************************************************************/

 typedef int index;
 typedef int bit;

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

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

 /* local variables for the run length process                        */
 int k2_r_s_;      /* accumulated binary representation K2{i-1}, k2{i}*/
                   /* the current bounded run count, r'(i-1)          */
                   /* the previous bit, s{i-1}                        */

/*--------------------------------------------------------------------*/
/*------------------ 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 core Frogbit algorithm --------------------*/

bit get_PR_bit(index PR_gen_selector); /* Forward reference: key stream
                                          sources                     */

 static const int rle_logic_table[128]=
 {  4,  5,  0,  1, 48, 49, 16, 17,  4,  5,  0,  1, 64, 65, 32, 33
 ,130,131,134,135,146,147,178,179,130,131,134,135,162,163,194,195
 ,140,139,136,143,184,155,152,187,140,139,136,143,200,171,168,203
 , 10, 13, 14,  9, 26, 57, 58, 25, 10, 13, 14,  9, 42, 73, 74, 41
 ,130,133,134,129,146,177,178,145,130,133,134,129,162,193,194,161
 ,  4,  3,  0,  7, 48, 19, 16, 51,  4,  3,  0,  7, 64, 35, 32, 67
 , 10, 11, 14, 15, 26, 27, 58, 59, 10, 11, 14, 15, 42, 43, 74, 75
 ,140,141,136,137,184,185,152,153,140,141,136,137,200,201,168,169
 };

/*
We use a table-lookup the control part of Frogbit encryption and
decryption.

+----------------------------------------------------------+
|                   Inputs                                 |
+---------------------+------------------------------------+
|                     |         Internal memory            |
+-----+-----+---------+-------+-------+------+-------------+
|k1{i}|k2{i}|m{i}/e{i}|k2{i-1}|r'(i-1)|s{i-1}|Direction bit|
+-----+-----+---------+-------+-------+------+-------------+

+-------------------------------------------------------------------+
|                         Outputs                                   |
+----------------------------------+--------------------------------+
|                                  |       Internal memory          |
+----------------------------------+-------------+----+-------------+
|                 Externally used                |    |  Constant   |
+----------+-------+-------+-------+-------+-----+----+-------------+
|          |       |       |       |d{0}(i)|     |    |             |
|output bit|d{3}(i)|d{2}(i)|d{1}(i)| k2{i} |r'(i)|s{i}|Direction bit|
+----------+-------+-------+-------+-------+-----+----+-------------+
*/

bit process_bit(bit m_i_)
{
  int t1;

  {
   bit k1_i_   = get_PR_bit(d_);
   bit k2_i_   = get_PR_bit(d_);
   drift_cnt[d_].c++;

   t1=rle_logic_table[(k2_r_s_&15)|(k2_i_<<5)|(m_i_<<4)|(k1_i_<<6)];
  }
  {
   int temp;
   if (0==(t1&4))
   {
     temp=(d_<<1)+(0!=(k2_r_s_&2));
     k2_r_s_=t1;
     d_=T[(k2_r_s_>>3)&15];
     switch(temp)
     {
     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;
     }
     return 0!=(k2_r_s_&128);
   }
   k2_r_s_=t1;
   return 0!=(k2_r_s_&128);
  }
}

void set_direction(bit decrypt_flag)
{
  k2_r_s_=(k2_r_s_&~1)|(decrypt_flag!=0);
}

Program listing "C" 

/**********************************************************************/
/***                                                                ***/
/***          Initialization for the Frogbit lookup table           ***/
/***                                                                ***/
/**********************************************************************/
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv)
{
  int inputs;

  printf(" static const int rle_logic_table[128]=\n {");

  for (inputs=0;inputs<128;inputs++)
  {
    int k1_i, k2_i, v_i, k2_i__1, r_i__1, s_i__1, dir;
    int outputs;

    /*
    +----------------------------------------------------------+
    |                   Inputs                                 |
    +---------------------+------------------------------------+
    |                     |         Internal memory            |
    +-----+-----+---------+-------+-------+------+-------------+
    |k1{i}|k2{i}|m{i}/e{i}|k2{i-1}|r'(i-1)|s{i-1}|Direction bit|
    +-----+-----+---------+-------+-------+------+-------------+
    */
    k1_i   =(inputs&64)!=0;
    k2_i   =(inputs&32)!=0;
    v_i    =(inputs&16)!=0;
    k2_i__1=(inputs&8)!=0;
    r_i__1 =(inputs&4)!=0;
    s_i__1 =(inputs&2)!=0;
    dir    =(inputs&1)!=0;
    /*
   +-------------------------------------------------------------------+
   |                         Outputs                                   |
   +----------------------------------+--------------------------------+
   |                                  |       Internal memory          |
   +----------------------------------+-------------+----+-------------+
   |                 Externally used                |    |  Constant   |
   +----------+-------+-------+-------+-------+-----+----+-------------+
   |          |       |       |       |d{0}(i)|     |    |             |
   |Output bit|d{3}(i)|d{2}(i)|d{1}(i)| k2{i} |r'(i)|s{i}|Direction bit|
   +----------+-------+-------+-------+-------+-----+----+-------------+
    */
    outputs=dir;
    {
      /* do the Frogbit processing with these inputs */
      int s_i;
      if (dir)
        s_i=v_i^k2_i;
      else
        s_i=v_i^k1_i;
      outputs|=((k2_i^v_i^k1_i)<<7)|(s_i<<1);

      if (s_i__1!=s_i)
         if (r_i__1==0) outputs|=                 k2_i <<3;
         else           outputs|= (2+(k2_i__1<<1)+k2_i)<<3;
      else
         if (r_i__1!=0) outputs|= (6+(k2_i__1<<1)+k2_i)<<3;
        else            outputs|=(                k2_i <<3)|(1<<2);
    }

    printf("%3d%s",outputs
                ,((inputs+1)%16)?",":((inputs==127)?"\n };":"\n ,"));
  }
  return EXIT_SUCCESS;
}

/* Sample output from this program:

 static const int rle_logic_table[128]=
 {  4,  5,  0,  1, 48, 49, 16, 17,  4,  5,  0,  1, 64, 65, 32, 33
 ,130,131,134,135,146,147,178,179,130,131,134,135,162,163,194,195
 ,140,139,136,143,184,155,152,187,140,139,136,143,200,171,168,203
 , 10, 13, 14,  9, 26, 57, 58, 25, 10, 13, 14,  9, 42, 73, 74, 41
 ,130,133,134,129,146,177,178,145,130,133,134,129,162,193,194,161
 ,  4,  3,  0,  7, 48, 19, 16, 51,  4,  3,  0,  7, 64, 35, 32, 67
 , 10, 11, 14, 15, 26, 27, 58, 59, 10, 11, 14, 15, 42, 43, 74, 75
 ,140,141,136,137,184,185,152,153,140,141,136,137,200,201,168,169
 };
*/

[ security scheme design | alternative to PKI | patent publications | SAKEM | scholarly web contents | consulting services ]
[ CONNOTECH home page: http://www.connotech.com/ | about us | e-mail to: info@connotech.com ]

CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691 Fax: +1-514-385-5900