## 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 ```

• #### Budi Rahardjo 9:15 pm on April 9, 2010 Permalink | Reply

lagi mikir debuggingnya …

• #### CG 4:32 am on April 10, 2010 Permalink | Reply

iya ini lagi di debug, pusing

## 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.]

• #### Budi Rahardjo 12:19 am on March 6, 2010 Permalink | Reply

Next would be point multiplication

• #### CG 12:08 pm on March 7, 2010 Permalink | Reply

working on it π

## 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 ```

• #### zakimath 7:28 am on February 24, 2010 Permalink | Reply

how to find an elliptic curve E with #E (the order of group) is prime…? π

• #### CG 9:21 am on February 24, 2010 Permalink | Reply

hadoh! susah, harus tanya sama dukun math dulu nih π

• #### zakimath 11:10 am on February 24, 2010 Permalink | Reply

hehehe, emang susah bgt! masih belum terbayang… π
Kalo gitu dibalik: Jika diberikan bilangan prima p, apakah terdapat suatu kurva elliptik E sedemikian hingga #E = p ?

• #### CG 11:27 am on February 24, 2010 Permalink | Reply

[berpikir keras] #E itu order kurva ya? berarti jumlah titik dalam kurva? bisa gitu jumlah titiknya ganjil (prima) kan titik2xnya sepasang? y^2?

• #### zakimath 12:59 pm on February 24, 2010 Permalink | Reply

Iya bu, #E itu banyaknya titik dalam suatu kurva E… bener gk sih simbolnya? koq jd lupa, he2… Contohnya kurva elliptik E: y^2 = x^3 + 12x + 20 atas field F_23 itu mempunyai jumlah titik 17, yaitu #E = 17 yg merupakan bilangan prima, akibatnya setiap titiknya merupakan generator dari E. CMIIW…

• #### zakimath 1:03 pm on February 24, 2010 Permalink | Reply

Hmmm, tp rasanya ada yg salah dg komentarku… #E = 17 itu sudah termasuk titik infinity blom ya? aduh, koq jadi lupa… π¦

• #### CG 9:23 pm on February 24, 2010 Permalink | Reply

eh baru aja saya mau bales, iya bner ganjil kan ditambah point of infinity π

• #### HongKong 10:09 pm on February 27, 2010 Permalink | Reply

jawabannya sih.. bisa bilangan ganjil dan bisa juga bilangan genap ((x,0) kan gak punya pasangan)
untuk setiap bilangan prima p selalu dapat dicari kurva eliptik atas Fp dengan orde (banyaknya titik) p

• #### CG 6:26 am on February 28, 2010 Permalink | Reply

thank you, HongKong π

• #### CG 5:33 pm on February 28, 2010 Permalink | Reply

baru inget kalau si HongKong = the geometer π

## 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 $x^{2^{n-1}}+...+x^{2^{1}}+x^{2^{0}}$. If we have n = 4, the identity element or “1” is 1111 ($x^{8}+x^{4}+x^{2}+x$).

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

Hoooraaaay!

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r