Sample Soucre Code in C for the Canadian Patent Application no. 2,156,780

CONNOTECH Experts-conseils Inc.


Table of contents

Utilities
. . . . Pseudo-random number generation from the C standard example
. . . . Linear distribution of random integers
. . . . Greatest common divisor
. . . . Generalized Euclid algorithm
. . . . Modular Multiplication
. . . . Modular Exponentiation
. . . . Number theoretic signed modulo
Definitions of Common Parameters
Code for the Responder (user B) in the Secret Key Exchange
. . . . Bit_Shuffling
. . . . responder_procedures
Code for the Passive Eavesdropper Role in the Key Exchange
. . . . eavesdropper_opportunity
Code for the Adversary role in the Secret Key Exchange
. . . . adversary_procedures
Code for the Initiator (user A) in the Secret Key Exchange
. . . . initiator_pre_computations
. . . . initiator_step_101
. . . . inverse_x_2_t__1_mod_N
. . . . bit_shuffling_test
. . . . initiator_steps_102_onwards
Main program section
. . . . The main program itself
. . . . Preprocessing of parameters
. . . . A small number of trial runs with printout
. . . . A larger sample for accumulating statistics
. . . . Countering the attack of a "sophisticated" adversary
. . . . Reaction to a non-sense responder action

/* ********************************************************

 ---------------------------------------------------------
 |    Method for Cryptographic System Users to Obtain    |
 |  a Jointly Determined, Shared, and Unique Bit String  |
 ---------------------------------------------------------

Author:       Thierry Moreau

Date:         July 28, 1995

Requirements: ANSI X3.159 "C" programming language compiler
              32-bits representation of integers

Caveats:   1) This is a "small-scale model", avoiding
              issues such as multi-precision arithmetic and
              real-life separation of initiator
              cryptographic processor from responder
              cryptographic processor.
           2) The reader should not rely on this source code
              to introduce himself to modulo arithmetic and
              other concepts from the number theory.

   ******************************************************** */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <assert.h>  /* assert(...) intended to raise
                        confidence in the source code
                        correctness.                        */

#if (UINT_MAX<0xFFFFFFFF)
#error This source code requires a 32-bit integer format
#endif

/* ********************************************************
                          Utilities
   ******************************************************** */

#define mod %
#define and &&
#define or ||
#define not !

/* --------------------------------------------------------
  Pseudo-random number generation from the C standard example
   -------------------------------------------------------- */
static unsigned long int next = 1;
#undef RAND_MAX /* overrides the definition from <stdlib.h> */
#define RAND_MAX 32767

int rand(void)
{
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/65536) mod 32768;
}

void srand(unsigned int seed)
{
  next = seed;
}

/* --------------------------------------------------------
            Linear distribution of random integers
   -------------------------------------------------------- */

static unsigned int linear_distribution( unsigned int min
                                       , unsigned int max)
{
  unsigned int return_value;
  assert(max>min);
  do
  {
    /* get at least 32 random bits irrespective of RAND_MAX */
    return_value = (rand()*(RAND_MAX+1)+rand())
                                         *(RAND_MAX+1)+rand();
  } /* but disregard any draw above an exact number of ranges,
       since such a draw would not make the distribution
       uniform                                              */
  while (return_value>=(UINT_MAX-UINT_MAX mod (max-min+1)));

  return return_value mod (max-min+1) + min;
}


/* --------------------------------------------------------
                    Greatest common divisor
   -------------------------------------------------------- */

static unsigned int gcd(unsigned int a, unsigned int b)
{
   int i;
   unsigned int x[4]; /* need x[0], x[1], x[i-1] */

   if (a>b)
   {
     x[0] = a; x[1] = b;
   }
   else
   {
     x[0] = b; x[1] = a;
   }

   i = 1;

   /* mapping 0123456789... into 0123232323... (a trick to
      maintain "elegant" programming style with limited-size
      memory)                                               */
   #define w(x) ((x<4)?x:(2+(x&1)))

   while( x[w(i)] != 0 )
   {

       x[w(i+1)] = x[w(i-1)] mod x[w(i)];

       i++;
   };
   return x[w(i-1)];
   #undef w
}

/* --------------------------------------------------------
                  Generalized Euclid algorithm
   -------------------------------------------------------- */

static void generalized_euclid(unsigned int P, unsigned int Q
                                       ,int*a          ,int*b)
{
   unsigned int x[4]; /* need x[0], x[1], x[i-1] */
   int  u[4],         /* need u[i-1] */
        v[4];         /* need v[i-1] */
   int i;

   if (P>Q)
   {
     x[0] = P; x[1] = Q;
   }
   else
   {
     x[0] = Q; x[1] = P;
   }

   u[0] = 1; u[1] = 0;
   v[0] = 0; v[1] = 1;

   i = 1;

   /* mapping 0123456789... into 0123232323... (a trick to
      maintain "elegant" programming style with limited-size
      memory)                                               */
   #define w(x) ((x<4)?x:(2+(x&1)))

   while( x[w(i)] != 0 )
   {
       int y;

       assert(x[w(i)]==u[w(i)]*x[0]+v[w(i)]*x[1]);

       y = x[w(i-1)]/x[w(i)];

       x[w(i+1)] = x[w(i-1)] mod x[w(i)];

       u[w(i+1)] = u[w(i-1)] - (y*u[w(i)]);
       v[w(i+1)] = v[w(i-1)] - (y*v[w(i)]);

       i++;
   };
   assert(x[w(i)]==u[w(i)]*x[0]+v[w(i)]*x[1]);

   if (P>Q)
   {
     *a = u[w(i-1)];
     *b = v[w(i-1)];
   }
   else
   {
     *a = v[w(i-1)];
     *b = u[w(i-1)];
   }
   #undef w
}

/* --------------------------------------------------------
                      Modular Multiplication
   -------------------------------------------------------- */

/* this version is limited to 16 bits multiplicands a and b */
#define mult_modulo(a,b,m) (((a)*(b))mod(m))

/* --------------------------------------------------------
                     Modular Exponentiation
   -------------------------------------------------------- */

static unsigned int expmod(unsigned int base
                          ,unsigned int exponent
                          ,unsigned int prepmod)
{
   unsigned int mask;
   unsigned int result = 1;

   mask=UINT_MAX-UINT_MAX/2; /* only the highest bit is set */

   while (mask)
   {
       result = mult_modulo(result,result,prepmod);

       if(exponent&mask)
       {
          result=mult_modulo(result,base,prepmod);
       }
       mask >>= 1;
   }
   return result;
}

/* --------------------------------------------------------
                 Number theoretic signed modulo
   -------------------------------------------------------- */

unsigned int number_theoretic_mod(int num, unsigned int denom)
{
  div_t d;  /* a C portable construct for
                                    signed integer division */
  d=div(num,denom);
  if (d.rem>=0)
    return d.rem;
  else
    return d.rem+denom;
}

/* ********************************************************
                Definitions of Common Parameters
   ******************************************************** */

#define L (128)    /* Number of bits
                                in the resulting bit string */
#define k (4)      /* Number of bits to retain in each step */
#define t ((L+k-1)/k) /* Number of steps
                                of the x**2 mod N generator */

static unsigned int N;/* Public key of the Initiator, user A*/

/* ********************************************************
  Code for the Responder (user B) in the Secret Key Exchange
   ******************************************************** */

/* the resulting jointly determined, secret, shared, and
   unique bit string as computed by the responder, user B
   (one bit per byte)                                       */
static char resp_secret_bit_string[L];              /* #204 */

/* --------------------------------------------------------
                            Bit_Shuffling
   -------------------------------------------------------- */

static unsigned int Bit_Shuffling(unsigned int S    /* #202 */
                                 ,unsigned int C
                                 ,unsigned int xA_B
                                 ,unsigned int xB_)
{
  return ((xB_/S)*C*S) + (xA_B*S) + (xB_ mod S);
}

/* --------------------------------------------------------
                     responder_procedures
   -------------------------------------------------------- */

static unsigned int responder_procedures(unsigned int S
                                        ,unsigned int C
                                        ,unsigned int xA_B)
{
  unsigned int xi;
  do
  {
   int i_t;
   do
   {
    unsigned int xB_;

    xB_ = linear_distribution(0,N/C);               /* #201 */

    xi = Bit_Shuffling(S,C,xA_B,xB_);               /* #202 */

   } while (not((1<xi)and(xi<(N-1))
                      and(gcd(xi,N)==1)
                      /* this gcd test should be omitted in a
                         full-scale implementation          */
               )
           );
   for (i_t=0; i_t<t; i_t++)
   {
    int i_bit;
    xi = mult_modulo(xi,xi,N);                      /* #203 */
    for (i_bit=0;i_bit<k;i_bit++)                   /* #204 */
    {
      resp_secret_bit_string[i_t*k+i_bit]= (xi&(1<<i_bit))!=0;
    }
   }
  } while (xi == 1); /* unlikely event where the period
                        of the x**2 mod N generator is 1    */
  xi = mult_modulo(xi,xi,N);
  return xi;
}

/* ********************************************************
  Code for the Passive Eavesdropper Role in the Key Exchange
   ******************************************************** */
/* The passive eavesdropper is one who tries to break the
   system by exhaustive search. In this small scale model, the
   eavesdropper is allowed a fixed number of attempts on each
   message exchange. In a full-scale implementation,
   exhaustive search as illustrated here makes no more sense
   than with other cryptosystems.                           */
#define EAVESDROPPER_NB_OF_ATTEMPTS (40)

static int count_samples;
static int count_successes;

/* --------------------------------------------------------
                    eavesdropper_opportunity
   -------------------------------------------------------- */

static void eavesdropper_opportunity(unsigned int S
                                    ,unsigned int C
                                    ,unsigned int xA_B
                                    ,unsigned int xt)
/* nota bene: this function spoils the global variable
              resp_secret_bit_string                        */
{
  int i;
  count_samples++;
  for (i=0;i<EAVESDROPPER_NB_OF_ATTEMPTS;i++)
  {
    if (xt==responder_procedures(S,C,xA_B))
    {
      count_successes++;
      break;
    }
  }
}

/* ********************************************************
    Code for the Adversary role in the Secret Key Exchange
   ******************************************************** */
/* The adversary knows some algorithm to find the prime
   factors of N from information he hopes to gather using the
   following attack. Only the first step of the information
   search is illustrated. The next step of the information
   gathering process is to eavesdrop (either actively or
   passively) the subsequent cryptographic exchanges and
   extract some hints about the shared bit string. A
   successful information gathering attack is an extremely
   remote possibility if the adversary process is considered
   during the cryptographic application design.

   By contrast with the Blum-Goldwasser probabilistic
   encryption cryptosystem, this one has two advantages for
   this type of adversary:
     1) there is a bit shuffling test to detect most
        information gathering attempts,
     2) the resulting bit string is not used to encipher a
        message directly, but as secret cryptosystem keys, MAC
        initial vectors, challenge data to be signed, and so
        on (none of which should disclose any bit of the bit
        string).                                            */

/* --------------------------------------------------------
                     adversary_procedures
   -------------------------------------------------------- */

static unsigned int adversary_procedures(unsigned int S
                                        ,unsigned int C
                                        ,unsigned int xA_B)
{
  unsigned int xt_pred; /* xt predecessor */
  do
  {
    xt_pred = linear_distribution(2,N-2);
  } while (not(   (gcd(xt_pred,N)==1)
               and(mult_modulo(xt_pred,xt_pred,N)!=1)
   /* and other mathematical criteria such as Jacobi symbol */
              )
          );
  return mult_modulo(xt_pred,xt_pred,N);
}

/* ********************************************************
  Code for the Initiator (user A) in the Secret Key Exchange
   ******************************************************** */

/* contents of the first message */                 /* #301 */
static unsigned int xA_B;/* main item in first message sent */
static unsigned int S
                   ,C;   /* dynamically selected parameters */

/* the resulting jointly determined, secret, shared, and
   unique bit string as computed by the initiator, user A
   (one bit per byte)                                       */
static char init_secret_bit_string[L];              /* #105 */

/* the private prime factors P and Q */
static unsigned int P, Q;

/* pre-computed values to make computations more efficient  */
static unsigned int a_P, b_Q, alpha, beta;

/* internal variables: the four possible values for B's x   */
static unsigned int e,f,g,h;

/* --------------------------------------------------------
                    initiator_pre_computations
   -------------------------------------------------------- */

static void initiator_pre_computations(void)
{
   assert((P*Q)==N);
   {

/* Find a, b such that a*P + b*Q = 1.

   Since further computations are modulo N, "scale" signed a
   and b into positive numbers:

(b*Q*mu + a*P*nu) mod N
 = (            b*Q*mu       +             a*P*nu      ) mod N
 = (          (b*Q)*mu mod N +           (a*P)*nu mod N) mod N
 = (    (b*Q mod N)*mu mod N +     (a*P mod N)*nu mod N) mod N
 = ((b*Q mod (P*Q))*mu mod N + (a*P mod (Q*P))*nu mod N) mod N
 = (  ((b mod P)*Q)*mu mod N +   ((a mod Q)*P)*nu mod N) mod N
      =============              =============
   pre-computed b_Q           pre-computed a_P              */

     int a, b;     generalized_euclid(P,Q,&a,&b);
     assert((a*P+b*Q)==1);

     b_Q = number_theoretic_mod(b,P)*Q;
     a_P = number_theoretic_mod(a,Q)*P;
   }
   alpha=expmod((P+1)/4,t+1,P-1);
   beta =expmod((Q+1)/4,t+1,Q-1);
}

/* --------------------------------------------------------
                      initiator_step_101
   -------------------------------------------------------- */

static void initiator_step_101(void)                /* #101 */
{
  /* This function illustrates implementation decisions about
     S and C parameters. Obviously, these should not be
     taken as recommended practice.                         */

  /* select parameter C among 19,21,23,25 with respective
     probabilities 1/7, 2/7, 2/7, 2/7, 2/7                  */

  C=linear_distribution(19,25);
  C=C|1; /* makes it odd */

  /* select parameter S as a multiple of 17,between 17 and
     N/C                                                    */
  {
    unsigned int min = 17;
    unsigned int max = N/C;
    if (max<min)
        max=min;

    S =17*linear_distribution(min/17,max/17);
  }

  assert((C*S)<N);

  xA_B = linear_distribution(0,C-1);
}

/* --------------------------------------------------------
                    inverse_x_2_t__1_mod_N
   -------------------------------------------------------- */

static unsigned int inverse_x_2_t__1_mod_N(unsigned int xt)
{                                                   /* #102 */
  unsigned int mu=expmod((xt mod P),alpha,P);
  unsigned int nu=expmod((xt mod Q),beta ,Q);

  e=(b_Q*mu    +a_P*nu)     mod N;
  f=(b_Q*(P-mu)+a_P*nu)     mod N;
  g=(b_Q*mu    +a_P*(Q-nu)) mod N;
  h=(b_Q*(P-mu)+a_P*(Q-nu)) mod N;

  assert(   (mult_modulo(e,e,N)==mult_modulo(f,f,N))
         and(mult_modulo(f,f,N)==mult_modulo(g,g,N))
         and(mult_modulo(g,g,N)==mult_modulo(h,h,N))
        );

  return mult_modulo(e,e,N);
}

/* --------------------------------------------------------
                      bit_shuffling_test
   -------------------------------------------------------- */

static int bit_shuffling_test(void)                 /* #103 */
/* returns non-zero when adversary attack detected          */
{
  return (not(  (xA_B==(e/S)mod C)
              or(xA_B==(f/S)mod C)
              or(xA_B==(g/S)mod C)
              or(xA_B==(h/S)mod C)
             )
         );
}

/* --------------------------------------------------------
                 initiator_steps_102_onwards
   -------------------------------------------------------- */

static int initiator_steps_102_onwards(unsigned int xt)
/* returns non-zero when adversary attack detected */
{
  unsigned int xi = inverse_x_2_t__1_mod_N(xt);     /* #102 */
  int i_t;
  if (bit_shuffling_test())                         /* #103 */
    return 1;
  for (i_t=0; i_t<t; i_t++)
  {
    int i_bit;
    for (i_bit=0;i_bit<k;i_bit++)                   /* #105 */
    {
      init_secret_bit_string[i_t*k+i_bit]
                                 = (xi&(1<<i_bit))!=0;
    }
    xi = mult_modulo(xi,xi,N);                      /* #104 */
  }
  if (xt!=xi)
  {
     return 2; /* most probably the xt selected by the
                  adversary was not relatively prime with N */
  }
  return 0;
}

/* ********************************************************
                       Main program section
   ******************************************************** */

#define DUPL_SAMPLE_SIZE (100)
#define ADVERSARY_SAMPLE_SIZE (100)

static int cmp_strings(const void *a, const void *b)
/*         -----------                                      */
/* defined here for a function argument to qsort function   */
{
  return memcmp(a,b,L);
}

static void print_bit_string(char *bit_string)
/*          ----------------                                */
{
  /* packing and printing bits from an array */
  int i;
  int v;
  for (i=0;i<L;i++)
  {
    if (0==(i mod 8))
      v = 0;
    if (bit_string[i])
      v = v | (1<<(7-(i mod 8)));
    if (7==(i mod 8))
      printf("%2.2X",v);
  }
  if (0!=(i mod 8))
    printf("%2.2X",v);
}

/* --------------------------------------------------------
                   The main program itself
   -------------------------------------------------------- */
int main(void)
{
 int i_param;
/* --------------------------------------------------------
                  Preprocessing of parameters
   -------------------------------------------------------- */
 static struct {unsigned int P_sample, Q_sample; }
      spec_numbers[]=
 /* all special numbers of the prescribed forms where N<2**16
         P  *  Q  =   N      Ref. Blum Blum Shub, theorem 8 */
      {{47 , 359}/*16873*/
      ,{23 , 719}/*16537*/
      ,{23 , 359}/* 8257*/
      ,{47 , 167}/* 7849*/
      ,{23 , 167}/* 3841*/
      ,{47 ,  23}/* 1081*/
      };
      /* n.b. 2 is a quadratic residute with respect to
         (47-1)/2 and (719-1)/2, so all these N should give
         optimum periods                                    */

 for (i_param=0
      ;i_param<2 /* first two entries of spec_numbers       */
      ;i_param++)
 {
  int i;

  P = spec_numbers[i_param].P_sample;
  Q = spec_numbers[i_param].Q_sample;
  N = P*Q;

  count_samples=0;/* for eavesdropper success rate statistic*/
  count_successes=0;

  initiator_pre_computations();
  printf("\nTest results using the above program\n"
           "with the x**2 mod %d generator\n\n",N);

/* --------------------------------------------------------
           A small number of trial runs with printout
   -------------------------------------------------------- */
  for (i=0;i<4;i++)
  {
     unsigned int xt;
     initiator_step_101();                          /* #101 */
     /* the first message is S, C, xA_B                #301 */
     xt=responder_procedures(S,C,xA_B);     /* #201 to #204 */
     /* the second message is xt                       #302 */
     if (initiator_steps_102_onwards(xt))   /* #102 to #105 */
        {  assert(1);  }
     assert(!memcmp(init_secret_bit_string
                   ,resp_secret_bit_string,L));

     printf("Sample %d, secret bit string: ",i+1);
     print_bit_string(resp_secret_bit_string);
     printf("\n");

     eavesdropper_opportunity(S,C,xA_B,xt);
  }

/* --------------------------------------------------------
          A larger sample for accumulating statistics
   -------------------------------------------------------- */
  {
    static char sample_bit_strings[DUPL_SAMPLE_SIZE][L];
    int count_duplicates;
    for (i=0;i<DUPL_SAMPLE_SIZE;i++)
    {

     unsigned int xt;
     initiator_step_101();                          /* #101 */
     /* the first message is S, C, xA_B                #301 */
     xt=responder_procedures(S,C,xA_B);     /* #201 to #204 */
     /* the second message is xt                       #302 */
     if (initiator_steps_102_onwards(xt))   /* #102 to #105 */
        {  assert(1);  }
     assert(!memcmp(init_secret_bit_string
                   ,resp_secret_bit_string,L));

     memcpy(sample_bit_strings[i],init_secret_bit_string,L);

     eavesdropper_opportunity(S,C,xA_B,xt);
    }

    qsort(sample_bit_strings,DUPL_SAMPLE_SIZE,L,cmp_strings);

    count_duplicates=0;
    for (i=1;i<DUPL_SAMPLE_SIZE;i++)
    {
     if (0==memcmp(sample_bit_strings[i-1]
                  ,sample_bit_strings[i],L))
     {
        count_duplicates++;
        printf("Duplicate secret bit string: ");
        print_bit_string(sample_bit_strings[i]);
        printf("\n");
     }
    }
    printf("Found %d duplicates in %d samples\n"
                  ,count_duplicates,DUPL_SAMPLE_SIZE);
  }

  printf("Eavesdropping was successful %d times "
                                   "out of %d opportunities\n"
                              ,count_successes,count_samples);

/* --------------------------------------------------------
     Countering the attack of a "sophisticated" adversary
   -------------------------------------------------------- */
  {
    int count_detect_1=0, count_detect_2=0;

    for (i=0;i<ADVERSARY_SAMPLE_SIZE;i++)
    {
      unsigned int xt;
      initiator_step_101();                         /* #101 */
      /* the first message is S, C, xA_B               #301 */
      xt=adversary_procedures(S,C,xA_B);   /* unknown proc? */
      /* the second message is xt                      #302 */
      switch(initiator_steps_102_onwards(xt))   /* #102 ... */
      {
        case 0: /* undetected attack, the adversary could,
                   if it was a general purpose probabilistic
                   encryption application, gather some useful
                   information to factorize N */
          break;
        case 1:
          count_detect_1++; break;
        case 2:
          count_detect_2++; break;
        default:
          assert(1);
      };
    }
    printf(
    "Out of %d attacks, %d were detected (%d special)\n"
            ,ADVERSARY_SAMPLE_SIZE
                        ,count_detect_1+count_detect_2
                                          ,count_detect_2
          );
  }

/* --------------------------------------------------------
            Reaction to a non-sense responder action
   -------------------------------------------------------- */
  {
    /* This test is similar to the previous one, but simply
       intended to check any bug when the responder does not
       give an xt response which is not mathematically
       conforming (either a number not relatively prime with N
       or a number which is not a quadratic residute modulo N)
                                                            */
    int count_detect_1=0, count_detect_2=0;

    for (i=0;i<ADVERSARY_SAMPLE_SIZE;i++)
    {
      unsigned int xt;
      initiator_step_101();                         /* #101 */
      /* the first message is S, C, xA_B               #301 */
      xt=linear_distribution(2,N-2); /* non-sense is random */
      /* the second message is xt                      #302 */
      switch(initiator_steps_102_onwards(xt))   /* #102 ... */
      {
        case 0:
          break;
        case 1:
          count_detect_1++; break;
        case 2:
          count_detect_2++; break;
        default:
          assert(1);
      };
    }
    printf("Out of %d dumb responses, %d were detected "
                                              "(%d special)\n"
            ,ADVERSARY_SAMPLE_SIZE
                               ,count_detect_1+count_detect_2
                                              ,count_detect_2
          );
  }
 }

 return EXIT_SUCCESS;
}


security scheme designalternative to PKIpatent publicationsSAKEMscholarly web contentsconsulting 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