Is this random enough?

Setting up curves with different numbits for ElGamal

This book and the software is very useful for doing experiments of encrypting using elliptic curve cryptography. I’ve been reading some thread with questions on how to change curve parameters, and here’s how:

To change the number of bits, you have to set it in field2n.h

Choose the polynomial irreducible in polymain.c

Set the message to be encrypted in elgamal.c (important note: the length of the message depends on the numbits of the curve)

How secure is ECC with composite field binary?

An interesting discussion about ECC with composite field security with Dr. Michael Rosing here.

Encryption – Decryption finally works

With the help of this debugger and that debugger, changing the data from this:

into this:

make the code works. It’s because the data occupied more space than the capacity of the number of words.


lss-67-39:Rosing Experiments CG chika$ ./test_elgamal_CG
poly_prime =
8 0 0 0 0 c9
setting up curve

the curve after setting up:
form: 1
a2: 0 0 0 0 0 2
a6: 0 0 0 0 0 1

counter = 0
inc = 5
Base point
x: 5 63323eab 10fc68f8 254d4d11 d2d518f2 9979dd24
y: 4 883e6269 de8bf93e f6c224e3 330dbf7f 2dd25ec1

create side 2's private key

Side 2 secret:
5 5d0be8bb a913fcdb 91edee60 4da6d486 295d85ac

Generate side 2's public key

Side 2 public key
x: 0 60838c40 7580aec4 b658d152 729f7f67 51d694bd
y: 0 1be3f90c c4a81de1 848ff01b d63e97a4 6b46c459
data =
0 68616c6c 6f0a0000 0 0 60000000

Hide data on curve and send from side 1 to side 2

curve before send_elgamal:
form: 1
a2: 0 0 0 0 0 2
a6: 0 0 0 0 0 1

Their_public before send_elgamal:
x: 0 60838c40 7580aec4 b658d152 729f7f67 51d694bd
y: 0 1be3f90c c4a81de1 848ff01b d63e97a4 6b46c459
=====IN send_elgamal=====
data (in send_gamal function) :
0 68616c6c 6f0a0000 0 0 60000000
Base point
x: 5 63323eab 10fc68f8 254d4d11 d2d518f2 9979dd24
y: 4 883e6269 de8bf93e f6c224e3 330dbf7f 2dd25ec1
Base curve
form: 1
a2: 0 0 0 0 0 2
a6: 0 0 0 0 0 1

random value:
5 3a0f94f6 e0caf9a7 2d189f04 8591c5e5 3935d4dc
Random point C1
x: 2 d6670f0 ab08aca3 8818adbe cf36881d 83accc06
y: 2 cad560f5 72c889b5 226934a2 733455c8 c53a15a6
counter = 0
inc = 0
raw point M (after poly_embed)
x: 0 68616c6c 6f0a0000 0 0 60000000
y: 0 7a64a103 a296a42d 4130d375 23ef2cf2 3f1a3ec0
Their_public:
x: 0 60838c40 7580aec4 b658d152 729f7f67 51d694bd
y: 0 1be3f90c c4a81de1 848ff01b d63e97a4 6b46c459
hidden point (after poly_elptic_mul)
x: 7 1f5fceb7 8269106c c1708600 cde8821b 38e0c7ee
y: 2 d752fec4 40840001 be4a3e7f 347e7013 7f36ce97
Hidden data (C2):
x: 6 a8a348b9 60a911b7 852a3bb9 8ba949df 5a157ae
y: 0 239b098 7584aea3 af4431db 2f3fa3f4 312c5ea9
Random point (C1):
x: 2 d6670f0 ab08aca3 8818adbe cf36881d 83accc06
y: 2 cad560f5 72c889b5 226934a2 733455c8 c53a15a6
=====OUT send_elgamal

AFTER send_elgamal
curve after send_elgamal:
form: 1
a2: 0 0 0 0 0 2
a6: 0 0 0 0 0 1

Hidden data (C2)
x: 6 a8a348b9 60a911b7 852a3bb9 8ba949df 5a157ae
y: 0 239b098 7584aea3 af4431db 2f3fa3f4 312c5ea9
Random point (C1)
x: 2 d6670f0 ab08aca3 8818adbe cf36881d 83accc06
y: 2 cad560f5 72c889b5 226934a2 733455c8 c53a15a6

Recover transmitted message

IN receive_elgamal
Base curve in receive_elgamal
form: 1
a2: 0 0 0 0 0 2
a6: 0 0 0 0 0 1

Hidden_data (in receive_elgamal) :
x: 6 a8a348b9 60a911b7 852a3bb9 8ba949df 5a157ae
y: 0 239b098 7584aea3 af4431db 2f3fa3f4 312c5ea9
Random point
x: 2 d6670f0 ab08aca3 8818adbe cf36881d 83accc06
y: 2 cad560f5 72c889b5 226934a2 733455c8 c53a15a6
hidden_point (d*C1):
x: 7 1f5fceb7 8269106c c1708600 cde8821b 38e0c7ee
y: 2 d752fec4 40840001 be4a3e7f 347e7013 7f36ce97
&raw_point:
x: 0 68616c6c 6f0a0000 0 0 60000000
y: 0 7a64a103 a296a42d 4130d375 23ef2cf2 3f1a3ec0
raw_point.x
0 68616c6c 6f0a0000 0 0 60000000
&raw_data (point):
x: bffff630 bbe72787 d25ef6fb 139332fc 90db35c4 fd129391
y: 0 2 d6670f0 ab08aca3 8818adbe cf36881d
raw_data (point):
x: 0 68616c6c 6f0a0000 0 0 60000000
y: 0 68616c6c 6f0a0000 0 0 60000000
&raw_data (field):
bffff630 bbe72787 d25ef6fb 139332fc 90db35c4 fd129391
raw_data (field):
0 68616c6c 6f0a0000 0 0 60000000
=====OUT receive elgamal

sent data
0 68616c6c 6f0a0000 0 0 60000000
received data (field)
0 68616c6c 6f0a0000 0 0 60000000


Houston, we cannot recover the plaintext


poly_prime =
8 0 0 0 0 c9
data test =
68616c6c 6f0a0000 0 0 0 6000000
setting up curves

the curve after setting up:
form: 1
a2: 2 0 0 0 0 0
a6: 1 0 0 0 0 0

counter = 0
inc = 5
Base point
x: 5 63323eab 10fc68f8 254d4d11 d2d518f2 9979dd24
y: 7 95f678a8 39481c22 2f4c7995 4a571060 6fe263b2

create side 2's private key

Side 2 secret:
5 5d0be8bb a913fcdb 91edee60 4da6d486 295d85ac

Generate side 2's public key

Side 2 public key
x: d107f500 66784cc8 9a0621db 9050de48 31c6e7c5 7d65d83b
y: 2 1763b098 91e23a1e 2f96df5c 50c63a33 a4b16c75

Hide data on curve and send from side 1 to side 2

counter = 0
inc = 0
counter = 0
-- pnt->x =
x: bffff4d8 1 bffff508 90483f7b a0073a58 905e07e8
y: 100131 1000 0 bffff7a0 bffff71c 1ed5
counter = 1
-- pnt->x =
x: bffff4d8 1 bffff508 90483f7b a0073a58 905e07e8
y: 100132 1000 0 bffff7a0 bffff71c 1ed5
Hidden data
x: 100135 70f0eb24 c996c3e4 2d120279 e9f3ec30 3370129a
y: 100132 7a61b198 ccba8673 27995624 c069db6f ab7bdfaa
Random point
x: d107f503 81d255cd 358038a7 148e84da a7b39f16 75d320c4
y: 3 e0053e42 6538a7a0 41dabd3 4cb90701 9a31b3b0

Recover transmitted message

sent data
100130 1000 0 bffff7a0 bffff71c 1ed5
received data
d117f431 a8e83258 f59857d7 646d8b77 90191393 f6674925


point multiplication testing

Point multiplication testing works.

/* CG - March 2010
   program to check point multiplication
*/

#include <stdio.h>
#include <stdlib.h>
#include "field2n.h"
#include "poly.h"
#include "eliptic.h"

extern FIELD2N poly_prime;

void set_field(value, n)
FIELD2N *value;
INDEX n;
{
   value->e[0] = n;
}

void set_curve(curv)
CURVE *curv;
{
   curv->form = 1;
   set_field(&curv->a6, 1L);
   set_field(&curv->a2, 2L);
}

int main()
{
        FIELD2N *data;
        FIELD2N *t;
	FIELD2N y, x, y2, xy;
	ELEMENT index, check;
        INDEX i, error;
	FILE *del;
	CURVE *curve;
        POINT *p, *r;
	char curve_string[80];
	
        data = malloc(sizeof(FIELD2N));
        if (data == NULL) {exit(-1);}

        t = malloc(sizeof(FIELD2N));
        if (t == NULL) {exit(-1);}

        curve = malloc(sizeof(CURVE));
        if (curve == NULL) {exit(-1);}

        p = malloc(sizeof(POINT));
        if (p == NULL) {exit(-1);}

        r = malloc(sizeof(POINT));
        if (r == NULL) {exit(-1);}

	if (!irreducible(&poly_prime)) return(0);
	print_field("poly_prime = ", &poly_prime);
	
	if (error = init_poly_math())
	{
		printf("Can't initialize S matrix, row = %d\n", error);
		return(-1);
	}

        data->e[0] = 1L;	
        data->e[1] = 1L;
        print_field("data test = ", data);

//        printf("NUMWORD = %ld\n", NUMWORD );
        null(t);
        t->e[NUMWORD] = 2L;
        print_field("t = ", t);

        printf("setting up curves\n\n");
        set_curve(curve);
        print_curve("the curve after setting up: ", curve);

        poly_embed(data, curve, 1, 0, p);
        printf("data after embedded to the curve: \n");
        print_point("p = ", p);

        printf("after point multiplication: \n");
        poly_elptic_mul(t, p, r, curve);
        print_point("r = ", r);	
}

This is the result of 2P.

lss-67-23:Rosing Experiments CG chika$ ./test_left_right_eq2
poly_prime =
8 0 0 0 0 c9

NUMBITS = 163
NUMWORD = 5
MAXLONG = 6
a2 =
2 0 0 0 0 0
a6 =
1 0 0 0 0 0

• =

1 1899fea5 56c420f2 9e4b1f87 5cb6b783 899feb0c
y =
1 26a707a1 8daf42c0 dde1d433 6638016d fd2dfcd4
yy =
0 1460a86a b5fd89df 6fc41f77 67325e56 91b4cecb
xy =
6 ed2088de 820e441 93687252 d3242e3a 62be995e
x_2 =
4 3e3b1763 9148e81e efc41b97 24c6e697 82da1543
x_3 =
4 ae6b51e0 468d0597 9c179778 e018bf6e 60eb0e54
ax2 =
3 572b7154 fb506809 60bbfa5d 540ecf02 93e159c1
left =
6 f94020b4 bddd6d9e fcac6d25 b416706c f30a5795
right =
6 f94020b4 bddd6d9e fcac6d25 b416706c f30a5795


And this is for 10P

lss-67-23:Rosing Experiments CG chika$ ./test_left_right_eq2
poly_prime =
8 0 0 0 0 c9

NUMBITS = 163
NUMWORD = 5
MAXLONG = 6
a2 =
2 0 0 0 0 0
a6 =
1 0 0 0 0 0

• =

3 91d7e88a 1bb31eaf bdf2e27d bf0271b6 333c29ce
y =
3 5d3c582c cbc0a643 fe11bd5a f6e54c0 41df835f
yy =
5 69b24b3f 8d3d7709 cd222a06 3d76432f 401b8c42
xy =
6 53764521 604fe896 ed4d10b9 660cd6e3 6c398bdd
x_2 =
7 a53af799 5d9b4e28 8a12d0c9 bb9dae71 9625d3c3
x_3 =
4 6d0ed674 6bfff7dd f5b93ab2 88c98b98 c3079c7f
ax2 =
6 57cad86a 868d6842 d5d6000d d3b31e54 ef259be0
left =
3 3ac40e1e ed729f9f 206f3abf 5b7a95cc 2c22079f
right =
3 3ac40e1e ed729f9f 206f3abf 5b7a95cc 2c22079f


More on testing points on curve

Have successfully tested two points:


FIELD2N x = {0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000};
FIELD2N y = {0x00000003, 0x477aaa32, 0xb86eae40, 0xa053e2a8, 0x0c4b05c3, 0x073f1c94};


and


FIELD2N x = {0x00000001, 0x00000002, 0x00000000, 0x00000000, 0x00000000, 0x00000000};
FIELD2N y = {0x00000004, 0xc2e04f09, 0x7ec85acb, 0x386fc4f1, 0x526affe9, 0xf6e4d3f5};


on curve

poly_prime =
8 0 0 0 0 c9
data :
1 1 0 0 0 0
setting up curves

the curve after setting up:
form: 1
a2: 0 0 0 0 0 0
a6: 1 0 0 0 0 0

point->x :
1 1 0 0 0 0
f :
0 4000141 4000141 4000141 4000000 1f68
point result
x: 1 2 0 0 0 0
y: 4 c2e04f09 7ec85acb 386fc4f1 526affe9 f6e4d3f5


The result:

poly_prime =
8 0 0 0 0 c9

NUMBITS = 163
NUMWORD = 5
MAXLONG = 6
a2 =
0 0 0 0 0 0
a6 =
1 0 0 0 0 0

• =

1 2 0 0 0 0
y =
4 c2e04f09 7ec85acb 386fc4f1 526affe9 f6e4d3f5
yy =
0 8a736b80 84a3b214 9d4c0808 d81f0825 8aecb069
xy =
0 8e736902 8ca3b710 8d4c0200 f81f0825 8aecaf01
x_2 =
1 20000000 64 80000000 0 15b
x_3 =
1 4000282 8000504 10000a08 20000000 1f68
ax2 =
0 0 0 0 0 0
left =
0 4000282 8000504 10000a08 20000000 1f68
right =
0 4000282 8000504 10000a08 20000000 1f68


the left equation is equal to the right equation. It’s on curve. Yay!

[what’s next? thinking.]

modifying curve setting up

/* CG - February 2010
   the program is supposed to find y for any given x
   [in progress]
   the representation is in polynomial
*/

#include <stdio.h>
#include <stdlib.h>
#include "field2n.h"
#include "poly.h"
#include "eliptic.h"

unsigned long random_seed;
extern FIELD2N poly_prime;

void set_field(value, n)
FIELD2N *value;
INDEX n;
{
   value->e[0] = n;
}

void set_curve(curv)
CURVE *curv;
{
   curv->form = 1;
   set_field(&curv->a6, 1L);   
   null(&curv->a2);
//   set_field(&curv->a2, 0L);
}	

int main()
{
   FIELD2N	*data, *data_juga;
   CURVE *curve;
   POINT *point;
   INDEX error;
   FIELD2N f;	
   POINT *pnt;

   curve = malloc(sizeof(CURVE));
   if (curve == NULL) {exit(-1);}

   point = malloc(sizeof(POINT));
   if (point == NULL) {exit(-1);}

   if (!irreducible(&poly_prime)) return(0);
      print_field("poly_prime = ", &poly_prime);
	
   if (error = init_poly_math())
      {
         printf("Can't initialize S matrix, row = %d\n", error);
	 return(-1);
      }

   printf("setting up curves \n\n");
  
   set_curve(curve); 
   print_curve("the curve after setting up: ", curve);
	
   return 0;
}


poly_prime =
8 0 0 0 0 c9
setting up curves

the curve after setting up:
form: 1
a2: 0 0 0 0 0 0
a6: 1 0 0 0 0 0


Is composite field secure?

The discussion about composite field implementation and its security can be read here.

Paper comparing about finite field for using in elliptic curve cryptography is here.

Important paper about how secure is elliptic curve over extension field is here.

Paper about efficient arithmetic in finite field extensions with application in elliptic curve cryptography is here.

ONB1 identity element

Rosing wrote on page 144:

In an optimal normal basis, adding 1 is the same as taking a complement

And finally figuring this out after finding out that the identity element of ONB1 is . If we have n = 4, the identity element or “1” is 1111 ().

That’s why if we have 0011 in normal basis (), adding it with “1” so it becomes 0011 + 1111 = ( = = 1100.

Hoooraaaay!