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