Implementation of Elliptic Curve Cryptography in ns-2

Caution:

Implementation of real cryptography algorithm in a simulator is not advisable because, the scope of a simulator is to minimize the overall simulation time – but doing real encryption and decryption on a simulator may considerably increase the simulation time. If you see the size of the original ecc code, then you will certainly realize it. We have just ported some freely available ecc code to ns-2 – We just converted a standard C implementation of the algorithm as a C++ level Application Agent of ns2.  Most importantly, the code presenter here is only for understanding this implementation – one can not compile this code without some missing information.

Elliptic Curve Cryptography (ECC)

Just google to learn about ECC. Start your learning from[1].

For installing ns-2 you may refer [2]

For a more efficient way of using cryptography under ns-2 or ns-3, you may use Crypto++ library as explained in the following article:

Secrets of Using Cryptography in ns-3 using Crypto++ Library

Implementation of ECCAgent as Application Agent in ns-2

The Actual Encryption and Decryption Part of the eccDH.cc Code

/********************************************************************************
* *
* NS2 Routines to implement protocols, Diffie-Hellman, Massey-Omura and *
* ElGamal for elliptic curve analogs. *
* *
********************************************************************************/
#include "agent.h"
#include 
#include 
#include "eccDH.h"
#include "packet.h"

INDEX log_2( ELEMENT x);
INDEX Lambda[2][field_prime];
INDEX lg2_m;
char mydata[100];

int opt_quadratic(FIELD2N *a,FIELD2N *b,FIELD2N *y);
void fofx(FIELD2N *x,CURVE *curv,FIELD2N *f);
void esum (POINT *p1,POINT *p2,POINT *p3,CURVE *curv);
void edbl (POINT *p1,POINT *p3,CURVE *curv);
void esub (POINT *p1,POINT *p2,POINT *p3,CURVE *curv);
void copy_point (POINT *p1,POINT *p2);
void elptic_mul(FIELD2N *k, POINT *p, POINT *r, CURVE *curv);
void one (FIELD2N *place);

void InitCurveAndPoint();
void CreateKeys();
void CreateDummyData();
void CreateData(char* data);
void HideDataForAddress(int ToAddress);
void RecoverDataFromAddress(int FromAddress);
void PrintKeysOfAddress(int Address);

void eccdemo();

void ECKGP();
void authen_secret();
CURVE Base_curve;

void rot_right(FIELD2N *a);
void rot_left(FIELD2N *a);
void null(FIELD2N *a);
void copy (FIELD2N *a,FIELD2N *b);
void genlambda();
void genlambda2();
void opt_mul(FIELD2N *a,FIELD2N *b,FIELD2N *c);
void opt_inv(FIELD2N *a,FIELD2N *result);



void one(FIELD2N*);
void random_field( FIELD2N *value);
void Mother(unsigned long *pSeed);
void opt_embed( FIELD2N *data, CURVE *curv, INDEX incrmt,INDEX root,POINT *pnt);
void rand_curve ( CURVE *curv);

void rand_point(POINT *point, CURVE *curve);
void DH_gen_send_key( POINT *Base_point, CURVE *E, FIELD2N *my_private,POINT *My_public);
void DH_gen_send_key( POINT *Base_point, POINT *My_public, CURVE *E, FIELD2N *my_private);
void DH_key_share(POINT *Base_point,POINT *their_public, CURVE *E,FIELD2N *my_private,FIELD2N *shared_secret);
void send_elgamal(POINT *Base_point, CURVE *Base_curve, POINT *Their_public, FIELD2N *raw_data, POINT *Hidden_data, POINT *Random_point);
//void send_elgamal(FIELD2N *raw_data,POINT *Base_point,POINT *Their_public,POINT *Hidden_data,POINT *Random_point, CURVE *Base_curve);
//void receive_elgamal(FIELD2N *my_private, FIELD2N *raw_data, POINT *Base_point, POINT *Hidden_data, POINT *Random_point,CURVE *Base_curve);
void receive_elgamal(POINT *Base_point, CURVE *Base_curve, FIELD2N *my_private, POINT *Hidden_data, POINT *Random_point, FIELD2N *raw_data);
void authen_secret( FIELD2N *d, FIELD2N *k, POINT *Q, POINT *R, POINT *other_Q, POINT *other_R, POINT *W);
void ECKGP(POINT *pnt, POINT *R,CURVE *crv, FIELD2N *k);
void print_field(char *string, FIELD2N *field);
void print_data(char *string, FIELD2N *field,int Format);
void print_point(char *string, POINT *point);
void print_curve(char *string,CURVE *curv);

/* random seed is accessable to everyone, not best way, but functional. */

unsigned long random_seed=0x139b25fe;

/* below is from Mother code, till end of mother. Above is all my fault. */

#include 

static short mother1[10];
static short mother2[10];
static short mStart=1;

#define m16Long 65536L /* 2^16 */
#define m16Mask 0xFFFF /* mask for lower 16 bits */
#define m15Mask 0x7FFF /* mask for lower 15 bits */
#define m31Mask 0x7FFFFFFF /* mask for 31 bits */
#define m32Double 4294967295.0 /* 2^32-1 */

/* Mother **************************************************************
| George Marsaglia's The mother of all random number generators
| producing uniformly distributed pseudo random 32 bit values with
| period about 2^250.
|
| The arrays mother1 and mother2 store carry values in their
| first element, and random 16 bit numbers in elements 1 to 8.
| These random numbers are moved to elements 2 to 9 and a new
| carry and number are generated and placed in elements 0 and 1.
| The arrays mother1 and mother2 are filled with random 16 bit values
| on first call of Mother by another generator. mStart is the switch.
|
| Returns:
| A 32 bit random number is obtained by combining the output of the
| two generators and returned in *pSeed. It is also scaled by
| 2^32-1 and returned as a double between 0 and 1
|
| SEED:
| The inital value of *pSeed may be any long value
*/



void Mother(unsigned long *pSeed)
{
 unsigned long number,
 number1,
 number2;
 short n,
 *p;
 unsigned short sNumber;

 /* Initialize motheri with 9 random values the first time */
 if (mStart) {
 sNumber= *pSeed&m16Mask; /* The low 16 bits */
 number= *pSeed&m31Mask; /* Only want 31 bits */

 p=mother1;
 for (n=18;n--;) {
 number=30903*sNumber+(number>>16); 
 /* One line multiply-with-cary */
 *p++=sNumber=number&m16Mask;
 if (n==9)
 p=mother2;
 }
 /* make cary 15 bits */
 mother1[0]&=m15Mask;
 mother2[0]&=m15Mask;
 mStart=0;
 }

 /* Move elements 1 to 8 to 2 to 9 */
 memmove(mother1+2,mother1+1,8*sizeof(short));
 memmove(mother2+2,mother2+1,8*sizeof(short));

 /* Put the carry values in numberi */
 number1=mother1[0];
 number2=mother2[0];

 /* Form the linear combinations */

number1+=1941*mother1[2]+1860*mother1[3]+1812*mother1[4]+1776*mother1[5]+
 1492*mother1[6]+1215*mother1[7]+1066*mother1[8]+12013*mother1[9];

number2+=1111*mother2[2]+2222*mother2[3]+3333*mother2[4]+4444*mother2[5]+
 5555*mother2[6]+6666*mother2[7]+7777*mother2[8]+9272*mother2[9];

 /* Save the high bits of numberi as the new carry */
 mother1[0]=number1/m16Long;
 mother2[0]=number2/m16Long;
 /* Put the low bits of numberi into motheri[1] */
 mother1[1]=m16Mask&number1;
 mother2[1]=m16Mask&number2;

 /* Combine the two 16 bit random numbers into one 32 bit */
 *pSeed=(((long)mother1[1])<<16)+(long)mother2[1];

 /* Return a double value between 0 and 1 
 return ((double)*pSeed)/m32Double; */
}



/* Generate a random bit pattern which fits in a FIELD2N size variable.
 Calls Mother as many times as needed to create the value.
*/


void random_field( FIELD2N *value)
{
 INDEX i;
 
 SUMLOOP(i)
 {
 Mother( &random_seed);
 value->e[i] = random_seed;
 }
 value->e[0] &= UPRMASK;
}

/* embed data onto a curve.
 Enter with data, curve, ELEMENT offset to be used as increment, and
 which root (0 or 1).
 Returns with point having data as x and correct y value for curve.
 Will use y[0] for last bit of root clear, y[1] for last bit of root set.
 if ELEMENT offset is out of range, default is 0.
*/

void opt_embed( FIELD2N *data, CURVE *curv, INDEX incrmt,INDEX root, POINT *pnt)
{
 FIELD2N f, y[2];
 INDEX inc = incrmt;
 INDEX i;
 
 if ( (inc < 0) || (inc > NUMWORD) ) inc = 0;
 copy( data, &pnt->x);
 fofx( &pnt->x, curv, &f);
 while (opt_quadratic( &pnt->x, &f, y))
 {
 pnt->x.e[inc]++;
 fofx( &pnt->x, curv, &f);
 }
 copy ( &y[root&1], &pnt->y);
}

/* generate a random curve for a given field size.
 Enter with pointer to storage space for returned curve.
 Returns with curve.form = 0, curve.a2 = 0 and curve.a6
 as a random bit pattern. This is for the equation
 
 y^2 + xy = x^3 + a_2x^2 + a_6
*/

void rand_curve ( CURVE *curv)

{
 curv->form = 0;
 random_field( &curv->a6);
 null( &curv->a2);
}

/* generate a random point on a given curve.
 Enter with pointer to curve and one pointer 
 to storage space for returned point. Returns 
 one of solutions to above equation. Negate point
 to get other solution.
*/

void rand_point(POINT *point, CURVE *curve)

{
 FIELD2N rf;

 random_field( &rf);
 opt_embed( &rf, curve, NUMWORD, rf.e[NUMWORD]&1, point);
}

/* Compute a Diffie-Hellman key exchange.

 First routine computes senders public key.
 Enter with public point Base_point which sits on public curve E and
 senders private key my_private.
 Returns public key point My_public = my_private*Base_point to be sent 
 to other side.
*/

void DH_gen_send_key( POINT *Base_point, CURVE *E, FIELD2N *my_private,POINT *My_public)

{
 elptic_mul( my_private, Base_point, My_public, E);
}

/* Second routine computes shared secret that is same for sender and
 receiver.
 Enter with public point Base_point which sits on public curve E along with 
 senders public key their_public and receivers private key k.
 Returns shared_secret as x component of kP
*/

void DH_key_share(POINT *Base_point,POINT *their_public, CURVE *E,FIELD2N *my_private,FIELD2N *shared_secret)

{
 POINT temp;
 
 elptic_mul( my_private, their_public, &temp, E);
 copy (&temp.x, shared_secret);
}

/* Send data to another person using ElGamal protocol. Send Hidden_data and
 Random_point to other side. */

void send_elgamal(POINT *Base_point, CURVE *Base_curve, POINT *Their_public, FIELD2N *raw_data, POINT *Hidden_data, POINT *Random_point)
{
 FIELD2N random_value;
 POINT hidden_point, raw_point;
 
/* create random point to help hide the data */
 
 random_field (&random_value);
 elptic_mul (&random_value, Base_point, Random_point, Base_curve);

/* embed raw data onto the chosen curve, Assume raw data is contained in
 least significant ELEMENTs of the field variable and we won't hurt anything
 using the most significant to operate on. Uses the first root for y value.
*/
 
 opt_embed( raw_data, Base_curve, 0, 0, &raw_point);

/* Create the hiding value using the other person's public key */

 elptic_mul( &random_value, Their_public, &hidden_point, Base_curve);
 esum( &hidden_point, &raw_point, Hidden_data, Base_curve);
}

/* Recieve data from another person using ElGamal protocol. We get
 Hidden_data and Random_point and output raw_data. */

void receive_elgamal(POINT *Base_point, CURVE *Base_curve, FIELD2N *my_private, POINT *Hidden_data, POINT *Random_point, FIELD2N *raw_data)
{
 POINT hidden_point, raw_point;

/* compute hidden point using my private key and the random point */

 elptic_mul( my_private, Random_point, &hidden_point, Base_curve);
 esub( Hidden_data, &hidden_point, &raw_point, Base_curve);
 copy(&raw_point.x, raw_data);
}

/* MQV method to establish shared secret.
 Enter with other servers permenent (other_Q) and 
 ephemeral (other_R) keys,
 this servers permenent key (skey, pkey) and 
 ephemeral (dkey, dpoint) keys.
 Returns shared secret point W. Only W.x is useful as key, 
 and further checks may be necessary to confirm link established.
*/

void authen_secret( FIELD2N *d, FIELD2N *k, POINT *Q, POINT *R, POINT *other_Q, POINT *other_R, POINT *W)

{
 POINT S, T, U;

/* compute U = R' + x'a'Q' from other sides data */

 elptic_mul(&other_Q->x, other_Q, &S, &Base_curve);
 elptic_mul(&other_R->x, &S, &T, &Base_curve);
 esum(other_R, &T, &U, &Base_curve);

/* compute (k + xad)U the hard way. Need modulo math routines to make this
 quicker, but no need to know point order this way.
*/

 elptic_mul(d, &U, &S, &Base_curve);
 elptic_mul(&Q->x, &S, &T, &Base_curve);
 elptic_mul(&R->x, &T, &S, &Base_curve);
 elptic_mul(k, &U, &T, &Base_curve);
 esum(&S, &T, W, &Base_curve);
}

/* Generate a key pair, a random value plus a point.
 This was called ECKGP for Elliptic Curve Key Generation
 Primitive in an early draft of IEEE P1363.

 Input: Base point on curve (pnt, crv)
 
 Output: secret key k and random point R
*/

void ECKGP(POINT *pnt, POINT *R,CURVE *crv, FIELD2N *k)
{
 random_field( k);
 elptic_mul( k, pnt, R, crv);
}

void create_field(char* data, FIELD2N *value)

{
 int len = strlen((const char *) data);
 printf("\n%d : %s ", len, data);
 
 memcpy(&value->e[0], data, len);
 value->e[0] &= UPRMASK; 
}
 
void print_field(char *string, FIELD2N *field)
{
 INDEX i;
 
 printf("%s : ", string);
 SUMLOOP(i) printf("%8x ", field->e[i]);
 printf("\n");
}

void print_data(char *string, FIELD2N *field,int Format)
{
 INDEX i;
 int k;
 if(Format==1) //Hex
 {
 //printf("%s : ", string);
 SUMLOOP(i) printf("%8x", field->e[i]);
 printf("\n");
 }

 if(Format==2) //char
 {
 char *p = (char * ) &field->e[0];
 //printf("%s : ", string);
 //SUMLOOP(i) printf("%4c", field->e[i]);
 
 for(k=0;k< sizeof(FIELD2N);k++) 
 printf("%c",*p++);
 printf("\n");
 } 
}

void print_point(char *string, POINT *point)
{
 printf("%s\n", string);
 print_field( "x", &point->x);
 print_field( "y", &point->y);
 printf("\n");
}

void print_curve(char *string,CURVE *curv)
{
 printf("%s\n", string);
 printf("form = %d\n", curv->form);
 if (curv->form) print_field( "a2", &curv->a2);
 print_field( "a6", &curv->a6);
 printf("\n");
}





/************************************************************************
* *
* Elliptic curves over Galois Fields. These routines find points *
* on a curve, add and double points for type 1 optimal normal bases. *
* *
* For succint explanaition, see Menezes, page 92 *
* *
* This file modified 6/23/97 to work with generalized ONB and *
* tunable field sizes. mgr *
* *
************************************************************************/




/************************************************************************
* Note that the following is obvious to mathematicians. I thought it *
* was pretty cool when I discovered it myself, . *
* *
* Routine to solve quadradic equation. Enter with coeficients *
* a and b and it returns solutions y[2]: y^2 + ay + b = 0. *
* If Tr(b/a^2) != 0, returns y=0 and error code 1. *
* If Tr(b/a^2) == 0, returns y[2] and error code 0. *
* If solution fails, returns y=0 and error code 2. *
* *
* Algorithm used based on normal basis GF math. Since (a+b)^2 = *
* a^2 + b^2 it follows that (a+b)^.5 = a^.5 + b^.5. Note that squaring*
* is a left shift and rooting is a right shift in a normal basis. *
* Transforming the source equation with y = ax and dividing by a^2 *
* gives: *
* x^2 + x + b/a^2 = 0 *
* *
* or x = x^.5 + (b/a^2)^.5 *
* *
* Let k_i = the ith significant bit of (b/a^2)^.5 and *
* x_i = the ith significant bit of x. *
* The above equation is equivelent to a bitwise representation as *
* *
* x_i = x_(i+1) + k_i *
* or *
* x(i+1) = x_i + k_i. *
* *
* Since both x and x+1 are solutions, and 1 is represented by all *
* bits set in a normal basis, we can start with x_0 = 0 or 1 at our *
* pleasure and use the recursion relation to discover every bit of x. *
* The answer is then ax and ax+a returned in y[0] and y[1] respectively*
* If the sum of x_(n-1) + k_(n-1) != x_0, returns error code 2 and *
* y = 0. *
* *
* error code returns *
* 0 y[0] and y[1] values *
* 1 y[0] = y[1] = 0 *
* 2 mathematicly impossible !!!! *
* *
************************************************************************/

int opt_quadratic(FIELD2N *a,FIELD2N *b,FIELD2N *y)

{
 INDEX i, el, bits;
 FIELD2N z, k, a2;
 ELEMENT r, t, mask;

/* test for a=0. Return y = square root of b. */

 r = 0;
 SUMLOOP(i) r |= a->e[i];
 if (!r) 
 {
 copy( b, &y[0]);
 rot_right( &y[0]);
 copy( &y[0], &y[1]);
 return(0);
 }

/* find a^-2 */

 opt_inv( a, &a2);
 rot_left(&a2);

/* find k=(b/a^2)^.5 */

 opt_mul( b, &a2, &k);
 rot_right(&k);
 r = 0;

/* check that Tr(k) is zero. Combine all words first. */

 SUMLOOP(i) r ^= k.e[i];

/* take trace of word, combining half of all the bits each time */

 mask = -1L;
 for (bits = WORDSIZE/2; bits > 0; bits >>= 1)
 {
 mask >>= bits;
 r = ((r & mask) ^ (r >> bits));
 } 

/* if not zero, return error code 1. */

 if (r) 
 {
 null(&y[0]);
 null(&y[1]);
 return(1);
 }

/* point is valid, proceed with solution. mask points to bit i,
which is known, in x bits previously found and k (=b/a^2)^.5. */

 null(&z);
 mask = 1;
 for (bits=0; bits < NUMBITS ; bits++) 
 {

/* source long word could be different than destination */

 i = NUMWORD - bits/WORDSIZE;
 el = NUMWORD - (bits + 1)/WORDSIZE;

/* use present bits to compute next one */

 r = k.e[i] & mask;
 t = z.e[i] & mask;
 r ^= t;

/* same word, so just shift result up */

 if ( el == i ) 
 {
 r <<= 1;
 z.e[el] |= r;
 mask <<= 1;
 } 
 else 
 {

/* different word, reset mask and use a 1 */

 mask = 1;
 if (r) z.e[el] = 1;
 }
 }

/* test that last bit generates a zero */

 r = k.e[0] & UPRBIT;
 t = z.e[0] & UPRBIT;
 if ( r^t ) 
 {
 null(&y[0]);
 null(&y[1]);
 return(2);
 }

/* convert solution back via y = az */

 opt_mul(a, &z, &y[0]);

/* and create complementary (z+1) solution y = az + a */

 null (&y[1]);
 SUMLOOP(i) y[1].e[i] = y[0].e[i] ^ a->e[i];

/* no errors, bye! */

 return(0);
}

/* compute R.H.S. f(x) = x^3 + a2*x^2 + a6 
 curv.form = 0 implies a2 = 0, so no extra multiply. 
 curv.form = 1 is the "twist" curve.
*/

void fofx(FIELD2N *x,CURVE *curv,FIELD2N *f)

{

 FIELD2N x2,x3;
 INDEX i;

 copy(x, &x2);
 rot_left(&x2);
 opt_mul(x, &x2, &x3);
 if (curv->form) opt_mul(&x2, &curv->a2, f);
 else null(f);
 SUMLOOP(i)
 f->e[i] ^= (x3.e[i] ^ curv->a6.e[i]);
}

/****************************************************************************
* *
* Implement elliptic curve point addition for optimal normal basis form. *
* This follows R. Schroeppel, H. Orman, S. O'Mally, "Fast Key Exchange with*
* Elliptic Curve Systems", CRYPTO '95, TR-95-03, Univ. of Arizona, Comp. *
* Science Dept. *
* *
* This version is faster for inversion processes requiring fewer *
* multiplies than projective math version. For NUMBITS = 148 or 226 this *
* is the case because only 10 multiplies are required for inversion but *
* 15 multiplies for projective math. I leave it as a paper to be written *
* [HINT!!] to propagate TR-95-03 to normal basis inversion. In that case *
* inversion will require order 2 multiplies and this method would be far *
* superior to projective coordinates. *
****************************************************************************/

void esum (POINT *p1,POINT *p2,POINT *p3,CURVE *curv)
{
 INDEX i;
 FIELD2N x1, y1, theta, onex, theta2;

/* compute theta = (y_1 + y_2)/(x_1 + x_2) */

 null(&x1);
 null(&y1);
 SUMLOOP(i) 
 {
 x1.e[i] = p1->x.e[i] ^ p2->x.e[i];
 y1.e[i] = p1->y.e[i] ^ p2->y.e[i];
 }
 opt_inv( &x1, &onex);
 opt_mul( &onex, &y1, &theta);
 copy( &theta, &theta2);
 rot_left(&theta2);

/* with theta and theta^2, compute x_3 */

 if (curv->form)
 SUMLOOP (i)
 p3->x.e[i] = theta.e[i] ^ theta2.e[i] ^ p1->x.e[i] ^ p2->x.e[i]
 ^ curv->a2.e[i];
 else
 SUMLOOP (i)
 p3->x.e[i] = theta.e[i] ^ theta2.e[i] ^ p1->x.e[i] ^ p2->x.e[i];

/* next find y_3 */

 SUMLOOP (i) x1.e[i] = p1->x.e[i] ^ p3->x.e[i];
 opt_mul( &x1, &theta, &theta2);
 SUMLOOP (i) p3->y.e[i] = theta2.e[i] ^ p3->x.e[i] ^ p1->y.e[i];
}

/* elliptic curve doubling routine for Schroeppel's algorithm over normal
 basis. Enter with p1, p3 as source and destination as well as curv
 to operate on. Returns p3 = 2*p1.
*/

void edbl (POINT *p1,POINT *p3,CURVE *curv)
{
 FIELD2N x1, y1, theta, theta2, t1;
 INDEX i;

/* first compute theta = x + y/x */

 opt_inv( &p1->x, &x1);
 opt_mul( &x1, &p1->y, &y1);
 SUMLOOP (i) theta.e[i] = p1->x.e[i] ^ y1.e[i];

/* next compute x_3 */

 copy( &theta, &theta2);
 rot_left(&theta2);
 if(curv->form)
 SUMLOOP (i) p3->x.e[i] = theta.e[i] ^ theta2.e[i] ^ curv->a2.e[i];
 else
 SUMLOOP (i) p3->x.e[i] = theta.e[i] ^ theta2.e[i];

/* and lastly y_3 */

 one( &y1);
 SUMLOOP (i) y1.e[i] ^= theta.e[i];
 opt_mul( &y1, &p3->x, &t1);
 copy( &p1->x, &x1);
 rot_left( &x1);
 SUMLOOP (i) p3->y.e[i] = x1.e[i] ^ t1.e[i];
}

/* subtract two points on a curve. just negates p2 and does a sum.
 Returns p3 = p1 - p2 over curv.
*/

void esub (POINT *p1,POINT *p2,POINT *p3,CURVE *curv)

{
 POINT negp;
 INDEX i;

 copy ( &p2->x, &negp.x);
 null (&negp.y);
 SUMLOOP(i) negp.y.e[i] = p2->x.e[i] ^ p2->y.e[i];
 esum (p1, &negp, p3, curv);
}

/* need to move points around, not just values. Optimize later. */

void copy_point (POINT *p1,POINT *p2)

{
 copy (&p1->x, &p2->x);
 copy (&p1->y, &p2->y);
}

/* Routine to compute kP where k is an integer (base 2, not normal basis)
 and P is a point on an elliptic curve. This routine assumes that K
 is representable in the same bit field as x, y or z values of P.
 This is for simplicity, larger or smaller fields can be independently 
 implemented.
 Enter with: integer k, source point P, curve to compute over (curv) and 
 Returns with: result point R.

 Reference: Koblitz, "CM-Curves with good Cryptografic Properties", 
 Springer-Verlag LNCS #576, p279 (pg 284 really), 1992
*/

void elptic_mul(FIELD2N *k,POINT *p,POINT *r, CURVE *curv)

{
 char blncd[NUMBITS+1];
 INDEX bit_count, i;
 ELEMENT notzero;
 FIELD2N number;
 POINT temp;

/* make sure input multiplier k is not zero.
 Return point at infinity if it is.
*/
 copy( k, &number);
 notzero = 0;
 SUMLOOP (i) notzero |= number.e[i];
 if (!notzero)
 {
 null (&r->x);
 null (&r->y);
 return;
 }

/* convert integer k (number) to balanced representation.
 Called non-adjacent form in "An Improved Algorithm for
 Arithmetic on a Family of Elliptic Curves", J. Solinas
 CRYPTO '97. This follows algorithm 2 in that paper.
*/
 bit_count = 0;
 while (notzero)
 {
 /* if number odd, create 1 or -1 from last 2 bits */
 
 if ( number.e[NUMWORD] & 1 )
 {
 blncd[bit_count] = 2 - (number.e[NUMWORD] & 3);
 
 /* if -1, then add 1 and propagate carry if needed */
 
 if ( blncd[bit_count] < 0 )
 {
 for (i=NUMWORD; i>=0; i--)
 {
 number.e[i]++;
 if (number.e[i]) break;
 }
 }
 }
 else
 blncd[bit_count] = 0;
 
 /* divide number by 2, increment bit counter, and see if done */
 
 number.e[NUMWORD] &= ~0 << 1;
 rot_right( &number);
 bit_count++;
 notzero = 0;
 SUMLOOP (i) notzero |= number.e[i];
 }
 
/* now follow balanced representation and compute kP */

 bit_count--;
 copy_point(p,r); /* first bit always set */
 while (bit_count > 0) 
 {
 edbl(r, &temp, curv);
 bit_count--;
 switch (blncd[bit_count]) 
 {
 case 1: esum (p, &temp, r, curv);
 break;
 case -1: esub (&temp, p, r, curv);
 break;
 case 0: copy_point (&temp, r);
 }
 }
}

/* One is not what it appears to be. In any normal basis, "1" is the sum of
all powers of the generator. So this routine puts ones to fill the number size
being used in the address of the FIELD2N supplied. */

void one (FIELD2N *place)

{
 INDEX i;

 SUMLOOP(i) place->e[i] = -1L;
 place->e[0] &= UPRMASK;
}






/************************************************************************************
* *
* Alex project routines for generalized and variable length ONB mathematics. *
* copied from original source and modified with new math. Must be optimized for *
* specific platforms later. Specific implementations should remove C constructs *
* in favor of assembler for more speed. *
 *
************************************************************************************/



void rot_left(FIELD2N *a)

{
 INDEX i;
 ELEMENT bit,temp;

 bit = (a->e[0] & UPRBIT) ? 1L : 0L;
 for (i=NUMWORD; i>=0; i--) {
 temp = (a->e[i] & MSB) ? 1L : 0L;
 a->e[i] = ( a->e[i] << 1) | bit;
 bit = temp;
 }
 a->e[0] &= UPRMASK;
}

void rot_right(FIELD2N *a)

{
 INDEX i;
 ELEMENT bit,temp;

 bit = (a->e[NUMWORD] & 1) ? UPRBIT : 0L;
 SUMLOOP(i) {
 temp = ( a->e[i] >> 1) | bit;
 bit = (a->e[i] & 1) ? MSB : 0L;
 a->e[i] = temp;
 }
 a->e[0] &= UPRMASK;
}

void null(FIELD2N *a)

{
 INDEX i;

 SUMLOOP(i) a->e[i] = 0;
}

void copy (FIELD2N *a,FIELD2N *b)

{
 INDEX i;

 SUMLOOP(i) b->e[i] = a->e[i];
}

/* binary search for most significant bit within word */

INDEX log_2( ELEMENT x)

{
 INDEX k, lg2;
 ELEMENT ebit, bitsave, bitmask;

 lg2 = 0;
 bitsave = x; /* grab bits we're interested in. */
 k = WORDSIZE/2; /* first see if msb is in top half */
 bitmask = -1L<> k);
 }
 return( lg2);
}

/* create Lambda [i,j] table. indexed by j, each entry contains the
value of i which satisfies 2^i + 2^j = 1 || 0 mod field_prime. There are
two 16 bit entries per index j except for zero. See references for
details. Since 2^0 = 1 and 2^2n = 1, 2^n = -1 and the first entry would
be 2^0 + 2^n = 0. Multiplying both sides by 2, it stays congruent to
zero. So Half the table is unnecessary since multiplying exponents by
2 is the same as squaring is the same as rotation once. Lambda[0][0] stores
n = (field_prime - 1)/2. The terms congruent to one must be found via
lookup in the log table. Since every entry for (i,j) also generates an
entry for (j,i), the whole 1D table can be built quickly.
*/

void genlambda()
{
 INDEX i, logof, n, index;
 INDEX log2[field_prime], twoexp;

 for (i=0; ie[i] = copyb.e[i] & amatrix[zero_index].e[i];

/* main loop has two lookups for every position. */

 for (j = 1; je[i] ^= copyb.e[i] &
 (amatrix[zero_index].e[i] ^ amatrix[one_index].e[i]);
 }
}

/* Generic ONB inversion routine.
 Input is pointer to ONB number.
 Output is inverse of input, overwrites input in place.
*/

void opt_inv(FIELD2N *a,FIELD2N *result)

{
 FIELD2N shift, temp;
 INDEX m, s, r, rsft;
 
/* initialize s to lg2_m computed in genlambda. Since msb is always set,
 initialize result to input a and skip first math loop.
*/

 s = lg2_m - 1;
 copy( a, result);
 m = NUMBITS - 1;

/* create window over m and walk up chain of terms */

 while (s >= 0)
 {
 r = m >> s;
 copy( result, &shift);
 for (rsft = 0; rsft < (r>>1); rsft++) rot_left( &shift);
 opt_mul( result, &shift, &temp);
 if ( r&1 ) /* if window value odd */
 {
 rot_left( &temp); /* do extra square */
 opt_mul( &temp, a, result); /* and multiply */
 }
 else copy( &temp, result);
 s--;
 }
 rot_left(result); /* final squaring */
}

The Agent Implementation Part of  the eccDH.cc Code

class eccDHAgent : public Agent {
public:
 eccDHAgent();
protected:
 int command(int argc, const char*const* argv);
private:
 int my_var1;
 double my_var2;
 void MyPrivFunc(void);
};


static class eccDHAgentClass : public TclClass {
public:
 eccDHAgentClass() : TclClass("Agent/eccDHAgent") {}
 TclObject* create(int, const char*const*) {
 return(new eccDHAgent());
 }
} class_eccDH_agent;


eccDHAgent::eccDHAgent() : Agent(PT_UDP) {
 bind("my_var1_otcl", &my_var1);
 bind("my_var2_otcl", &my_var2);
}


int eccDHAgent::command(int argc, const char*const* argv) {
 if(argc == 2) {
 if(strcmp(argv[1], "InitCurveAndPoint") == 0) {
 InitCurveAndPoint();
 return(TCL_OK);
 }
 if(strcmp(argv[1], "CreateKeys") == 0) {
 CreateKeys();
 return(TCL_OK);
 }
 if(strcmp(argv[1], "CreateDummyData") == 0) {
 CreateDummyData();
 return(TCL_OK);
 }
 if(strcmp(argv[1], "Demo") == 0) {
 eccdemo();
 return(TCL_OK);
 }
 }
 if(argc == 3) {
 
 if(strcmp(argv[1], "CreateData") == 0) {
 strcpy((char*)mydata, argv[2]);
 CreateData(mydata);
 return(TCL_OK);
 }
 if(strcmp(argv[1], "HideDataForAddress") == 0) {
 HideDataForAddress( atoi(argv[2]) );
 return(TCL_OK);
 }
 if(strcmp(argv[1], "RecoverDataFromAddress") == 0) {
 RecoverDataFromAddress( atoi(argv[2]) ); 
 return(TCL_OK);
 }
 if(strcmp(argv[1], "PrintKeysOfAddress") == 0) {
 PrintKeysOfAddress( atoi(argv[2]) ); 
 return(TCL_OK);
 }
 
 } 
 return(Agent::command(argc, argv));
}


void eccDHAgent::MyPrivFunc(void) {
 Tcl& tcl = Tcl::instance();
 tcl.eval("puts \"Message From MyPrivFunc\"");
 tcl.evalf("puts \" my_var1 = %d\"", my_var1);
 tcl.evalf("puts \" my_var2 = %f\"", my_var2);
}


FIELD2N PrivateKey[25], PublicKey[25], send_data,get_data;
CURVE koblitz, rnd_crv;
POINT Base, Point[25] ,Hidden_data,Random_point;
INDEX i;
 

void InitCurveAndPoint()
{
 
#ifdef TYPE2
 genlambda2();
#else
 genlambda();
#endif
 // printf("Size of Data : %d\n",MAXLONG);
 printf("create random curve and point\n\n");

 rand_curve(&rnd_crv);
 print_curve("random curve", &rnd_crv);
 rand_point(&Base, &rnd_crv);
 print_point("Base point", &Base);
}

void CreateKeys()
{ int i;
 printf("\nCreating Private and Public keys\n\n");
 for(int i= 0;i<25;i++)
 {
 random_field(&PrivateKey[i]);
 // print_field("PrivateKey ", &PrivateKey[i]);
 DH_gen_send_key( &Base, &rnd_crv, &PrivateKey[i], &Point[i]);
 //print_point("Public Key :", &Point[i]); 
 }
}

void PrintKeysOfAddress(int Address)
{ 
 print_field("PrivateKey ", &PrivateKey[Address]);
 print_point("Public Key :", &Point[Address]); 
}

void CreateDummyData()
{
 printf("\nCreating Dummy Message data\n\n");
 random_field( &send_data);
 print_data("Data to be Sent ", &send_data,1);
}

void CreateData(char* data)
{
 printf("\nCreating Message data\n\n");
 create_field(data, &send_data);
 print_data("Data to be Sent ", &send_data,2);
}

void HideDataForAddress(int ToAddress)
{
 printf("\nHide data on curve and send from SideA to SideB\n\n");
 send_elgamal( &Base, &rnd_crv, &Point[ToAddress],
 &send_data, &Hidden_data, &Random_point);
 print_point("Hidden data", &Hidden_data);
 print_point("Random point", &Random_point);

}

void RecoverDataFromAddress(int FromAddress)
{
 printf("\nRecover Transmitted Message At %d\n\n", FromAddress);
 receive_elgamal( &Base, &rnd_crv, &PrivateKey[FromAddress],
 &Hidden_data, &Random_point, &get_data);
 
 print_data("Received data :", &get_data,2);
}

The eccDH.h

/****** eccDH.h *****/
/****************************************************************
* *
* These are structures used to create elliptic curve *
* points and parameters. "form" is a just a fast way to check *
* if a2 == 0. *
* form equation *
* *
* 0 y^2 + xy = x^3 + a_6 *
* 1 y^2 + xy = x^3 + a_2*x^2 + a_6 *
* *
****************************************************************/
/*** field2n.h ***/

#define WORDSIZE (sizeof(int)*8)
#define NUMBITS 134
#define TYPE2
/*#undef TYPE2 */

#ifdef TYPE2
#define field_prime ((NUMBITS<<1)+1)
#else
#define field_prime (NUMBITS+1)
#endif

#define NUMWORD (NUMBITS/WORDSIZE)
#define UPRSHIFT (NUMBITS%WORDSIZE)
#define MAXLONG (NUMWORD+1)

#define MAXBITS (MAXLONG*WORDSIZE)
#define MAXSHIFT (WORDSIZE-1)
#define MSB (1L<
The TCL Simulation Code to test the Working of EccDH Agent
 
Initializing Some Important Parameters
set val(chan) Channel/WirelessChannel ;# channel type
set val(prop) Propagation/TwoRayGround ;# radio-propagation model
set val(ant) Antenna/OmniAntenna ;# Antenna type
set val(ll) LL ;# Link layer type
set val(ifq) Queue/DropTail/PriQueue ;# Interface queue type
set val(ifqlen) 50 ;# max packet in ifq
set val(netif) Phy/WirelessPhy ;# network interface type
set val(mac) Mac/802_11 ;# MAC type
set val(rp) AODV


# unity gain, omni-directional antennas
# set up the antennas to be centered in the node and 1.5 meters above it
Antenna/OmniAntenna set X_ 0
Antenna/OmniAntenna set Y_ 0
Antenna/OmniAntenna set Z_ 1.5
Antenna/OmniAntenna set Gt_ 1.0
Antenna/OmniAntenna set Gr_ 1.0

# Initialize the SharedMedia interface with parameters to make
# it work like the 914MHz Lucent WaveLAN DSSS radio interface
Phy/WirelessPhy set CPThresh_ 10.0
Phy/WirelessPhy set CSThresh_ 1.559e-11
Phy/WirelessPhy set RXThresh_ 3.652e-10
Phy/WirelessPhy set Rb_ 2*1e6

#inital transmission power of all the nodes
Phy/WirelessPhy set Pt_ 0.2819;# Change it if required
Phy/WirelessPhy set freq_ 914e+6 
Phy/WirelessPhy set L_ 1.0

set ECC_AGENT_PORT 42

set TotalNodes 3

# size of the topography
set val(x) 600
set val(y) 600
 
Setting up the Node Parameters
set chan_1_ [new $val(chan)]

$ns node-config -adhocRouting $val(rp) \
 -llType $val(ll) \
 -macType $val(mac) \
 -ifqType $val(ifq) \
 -ifqLen $val(ifqlen) \
 -antType $val(ant) \
 -propType $val(prop) \
 -phyType $val(netif) \
 -topoInstance $topo \
 -agentTrace ON \
 -routerTrace ON \
 -macTrace ON \
 -movementTrace OFF \
 -channel $chan_1_ 
# subclass Agent/MessagePassing to make it do flooding
 
Defining the Function os the Inherited Agent
Class Agent/EccMessagePassing -superclass Agent/MessagePassing

Agent/EccMessagePassing instproc recv {source sport size data} {
 $self instvar node_ Side
 global ns ECC_AGENT_PORT eccAPP
 
 if {$sport==$ECC_AGENT_PORT && $source == 0 } {
 $ns trace-annotate "[$node_ node-addr] Recieving Encrypted Message From $source"
 $eccAPP RecoverData
 }
}


Agent/EccMessagePassing instproc HideAndSendDataTo {addr} {
 $self instvar node_ Side
 global ns ECC_AGENT_PORT eccAPP
 $eccAPP CreateDummyData
 $eccAPP HideAndSendData
 $self sendto 10 "DummyData" $addr $ECC_AGENT_PORT
 $ns trace-annotate "[$node_ node-addr] Sending Encrypted Message to $addr"
}

set rng [new RNG]
$rng seed 0 

# Create SideA Node
 set SideANode [$ns node]
 $SideANode color "black"
 $ns at 0 "$SideANode label Side-A"
 $SideANode set Y_ 300
 $SideANode set X_ 75
 $SideANode set Z_ 0.0
 $ns initial_node_pos $SideANode 50
 set EccAgent(0) [new Agent/EccMessagePassing]
 $SideANode attach $EccAgent(0) $ECC_AGENT_PORT
 $EccAgent(0) set Side "A"
 
# Create Middle Node
 set MiddleNode [$ns node]
 $MiddleNode color "black"
 $MiddleNode set Y_ 200
 $MiddleNode set X_ 300
 $MiddleNode set Z_ 0.0
 $ns initial_node_pos $MiddleNode 50
 set EccAgent(1) [new Agent/EccMessagePassing]
 $MiddleNode attach $EccAgent(1) $ECC_AGENT_PORT
 $EccAgent(1) set Side "M"
 
# Create SideB Node
 set SideBNode [$ns node]
 $SideBNode color "black"
 $ns at 0 "$SideBNode label Side-B"
 $SideBNode set Y_ 300
 $SideBNode set X_ 525
 $SideBNode set Z_ 0.0
 $ns initial_node_pos $SideBNode 50
 set EccAgent(2) [new Agent/EccMessagePassing]
 $SideBNode attach $EccAgent(2) $ECC_AGENT_PORT
 $EccAgent(1) set Side "B"


set eccAPP [new Agent/eccDHAgent]
#$eccDH Demo

$ns at 0.01 "$ns trace-annotate {Selecting A Random Curve and Point}"
$ns at 0.01 "$eccAPP InitCurveAndPoint"
$ns at 0.02 "$eccAPP CreateSideAKeys"
$ns at 0.03 "$eccAPP CreateSideBKeys"


# now set up some events

$ns at 0.1 "$EccAgent(0) HideAndSendDataTo 2 "
$ns at 0.2 "$EccAgent(0) HideAndSendDataTo 2 "
$ns at 0.3 "$EccAgent(0) HideAndSendDataTo 2 "
 
The following shows the complete tcl simulation script of this simulation :

	

		
Hidden Section! Contact Charles  
		
The key/passphrase will be given once you have been approved for getting paid research support/assistance from Charles. To get paid support, you may start a 'free' research discussion.  
Discuss Through WhatsApp
 

		
		

			
			 
			
			
			
						
		
		
		

		
		

			
		
	



The Simple Covered Communication Scenario
The following Nam output shows the simple, covered communication scenario that we did on MANET

 
Side-A is start sending Encrypted data to Side -B via a middle node

 
Side-A is sending Encrypted data to Side -B via a middle node

 
Side-B is Receiving Encrypted data from Side -B via the middle node


The Encryption and Decryption output
 
We will see the following output in the terminal window while running the above simulation. The output will obviously explain the covered communication.
 
create random curve and point

random curve
form = 0
a6 : 1c 5e629417 3dbdf669 b9fca0fe cd2165b0

Base point
x : c 358df1ea 9ebc2e42 2fbec069 dde73d2c 
y : 9 eb318786 772fce50 72bbc1f8 22ed38bb


Creating SideA private and Public keys

Side A secret: : c d2a3e242 4ce7401a 58e0e961 b20afcdf 
Side A public key
x : 34 69023735 749bc2f7 27123ddd 13c421e8 
y : 2a 82945bef 8826b76a 59602c5 1caaf73a


Creating SideB private and Public keys

Side B secret: : 39 99d659e8 3428a5da 9b130925 aed734d8 
Side B public key
x : 26 8856d11 8ce1eed7 2390aeae 7b3bf293 
y : 1f 1f18ec52 652f16ee 9fa9b2c3 36c8422f


Creating Dummy Message data

Data to be Sent : 16 f93ff6c8 e42f891b d8aeabdf cd419f2f

Hide data on curve and send from SideA to SideB

Hidden data
x : 31 b71d6293 bb851393 2a92dbb5 fc19958c 
y : 3d d2ff2282 87d2accb 970f677a c5c82180

Random point
x : 12 2abaa729 775cb900 bf443998 548c3e9c 
y : 1e 24719fb0 5c4e03db e67be1f0 b46cac9f


Recover Transmitted Message
Received data : : 16 f93ff6c8 e42f891b d8aeabdf cd419f2f
 
Conclusion
We have successfully integrated the ECC code in ns2 and did some preliminary simulations using the eccDH Agent. If you are doing some serious research, then you may need to do few more additional things to use this code.
 
Related work
We have ported the above ECC module to the ns-3 simulator so that we can use that ECC module in ns-3 simulations. we may see that in a future article.
 
References
 

https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
https://www.projectguideline.com/installing-ns3-35-in-debian-10-chroot-jail-under-debian-11-host-os-or-any-version-of-linux-host/