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

        crv.form = 0;
//      crv.a2.e[NUMWORD] = 1;
//      crv.a2.e[NUMWORD] = 1;
        crv.a6.e[NUMWORD] = 0x8;
        crv.a6.e[NUMWORD] = 0x9;
        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 =
data =
for point
x: a
y: f
rhs + lhs =
left =
right =


  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).