## Embedding data to a curve

To embed data to a curve, these are things to be the guidelines:

1. The “data” to embedded to the curve is in the form of big integer. In the example by Rosing, the data is processed in hexadecimal representation.
2. Put the data into a variable and add more bits for some “garbage” bits that will help the data to be a point that fits into the curve equation.
3. The more garbage, the more difficult for the attacker to get the data.
4. The garbage keep incremented (with the size of increment we choose) until we find an $x$ that fits the equation, and then there will be two values of  $y$ to make it $P(x,y)$ on curve.

Here’s a simple code for checking that a data can be embedded to a curve (modified Rosing):

```//This program is to experiment with small curves
//CG - Dec 2009

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

extern FIELD2N poly_prime;

int main()
{
FIELD2N t1, t2, test;
FIELD2N q, r, y, x, y2, xy, g[3];
INDEX   i, error, j, order, k, m, n;
ELEMENT index, check;
FILE *del;
CURVE  crv;
POINT   p2, p3, p4, p5, p6, p7;
char curve_string[80];

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

crv.form = 0;
null(&crv.a2);
null(&crv.a6);
//      crv.a2.e[NUMWORD] = 1;
//      crv.a2.e[NUMWORD] = 1;
crv.a6.e[NUMWORD] = 0x8;
crv.a6.e[NUMWORD] = 0x9;
null(&test);
test.e[NUMWORD] = 0xa;
print_field("data = ", &test);
poly_embed( &test, &crv, NUMWORD, 0, &p2);

/*  check that point is in fact on curve  */

copy(&p2.y, &y);
copy(&p2.x, &x);
print_point("for point", &p2);
poly_mul( &p2.y, &y, &y2);
poly_mul( &y, &x, &xy);
SUMLOOP(i) r.e[i] = y2.e[i] ^ xy.e[i];
poly_fofx( &x, &crv, &q);
SUMLOOP(i) test.e[i] = r.e[i] ^ q.e[i];
print_field("rhs + lhs =",&test); //if the rhs+lhs = 0 means that th
e point is on curve
print_field("left = ", &r);
print_field("right = ", &q);
return 0;
}
```

The result is

``` poly_prime = 13 data = a for point x: a y: f rhs + lhs = 0 left = 6 right = 6 ```

Notes:

1. This means that for a 4-bit length curve, 13 (1101 = $x^3 + x^2 + 1$), the data is \$0xa, the point is $P(0xa, 0xf)$. if $rhs + lhs = 0$ means that the data is already on curve.
2. There are several ways to convert a message into a “data” (large integer).

• #### Budi Rahardjo 6:09 am on December 28, 2009 Permalink | Reply

Wow, you have progressed. Let me digest this first. (Still thinking how to find y, given x.)

• #### CG 11:52 am on December 28, 2009 Permalink | Reply

next i have to explore pari for elltor. and finish the decrypting part. oh and also convert the message into a big integer. and praying for finishing it before 11th jan!

• #### Soni 6:17 am on December 28, 2009 Permalink | Reply

i have several questions and comments for this posting:
1. what do you mean by ‘data’? is it a message to be encrypted?
2. what is ‘garbage’? is it some kind of adjustment bit which has purpose to fit the point into the curve, or else?
3. what is a point exactly? is it the message or the key?
4. what do you mean by increment garbage? is it just adding the representation, or add more bits?
5. after you give the example, now i understand how to represent prime number into equation :D.
6. i don’t understand the code. maybe i have to see the header file first before i understand how the functions work. can i?

• #### CG 11:41 am on December 28, 2009 Permalink | Reply

@soni: 1. data is message to be encrypted but have converted from array of characters into a form of integer (usually big integers).
2. garbage is additional bits added to the data in integer representation (so when the data is viewed in binary representation, adding garbage is simply add more bits to it).
3. a point is a pair of (x, y) that solve the curve equation. the message is the data, and the key is how many times the point is moved inside the curve.
5. by converting the prime numbers into binary representation?
6. yes. the code use many header files. and contained a lot of tricks and maths too 😀

## 4-bit curve

Now experimenting on a very small curve, taken from Guide to Elliptic Curve Cryptography #27, $F_2^4$ with reduction polynomial $f(z) = z^4+z+1$, $E: y^2 + xy = x^3 + z^3x^2 + (z^3+1)$ ($a = z^3$, $b = z^3+1$).

Have checked that the points on #81 are on curve.

Next to do is to perform curve operation $Q= k.P$

Notes:

This curve is not a Koblitz curve. Going compare this one with Koblitz (by changing a =1 or a = 0 and b = 1). To generate points on curve look at P1363.

• #### Budi Rahardjo 8:00 am on December 17, 2009 Permalink | Reply

Still thinking how to make a flexible ecc system to calculate all of these.

• #### CG 12:44 pm on December 17, 2009 Permalink | Reply

and what it’s gonna be called? a simulator? platform?

• #### soni 9:22 am on December 18, 2009 Permalink | Reply

what do you mean by ‘small curve’? if we only have 4 bit, it means that we only have a little bit combinations. then we have a rough curve, rather than a smooth curve if we have more bit. is it right?

• #### CG 4:55 pm on December 18, 2009 Permalink | Reply

@soni: i’m afraid it’s not that simple. yes that small curves will have only a small number of points but higher bits doesn’t not determine the smoothness of the curve. the curve is called “smooth” only if it is defined in real numbers, not in finite fields.

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