4.1 HEC-Diffie-Hellman key exchange

The basic Diffie-Hellman key exchange protocol works as follows:

Alice and Bob wish to agree on a secret random element over an insecure channel without having to exchange any information previously.

They agree on an element P in the Jacobian of the genus 2 curve C with a large (known or unknown) order G.

1. Alice generates a random integer a \in {1, \ldots, \#G - 1}, then sends to Bob the element (divisor)
   Q_1 = [a] P.
2. Bob generates a random integer b \in {1, \ldots, \#G - 1}, then sends to Alice the element (divisor)
   Q_2 = [b] P.
3. Alice then computes
   [ab] P = [a] Q_2.
4. Similarly, Bob computes
   [ab] P = [b] Q_1.

This element [ab] P now serves as the secret that only Alice and Bob know.

We illustrate a local version of this protocol using a genus 2 curve over a prime field GF(p), for an educational purpose.

First we include the header file g2hec_Genus2_ops.h:

#include <g2hec_Genus2_ops.h>

Then we define the maximum length (in decimal digits) of the prime number p to be 300:

#undef MAX_STRING_LEN
#define MAX_STRING_LEN 300

The following statement invokes the namespace used by the G2HEC library, and must be present for every client program.

NS_G2_CLIENT

In the main function, we first set the pseudo-random number generator seed, and allocate a string buffer for receiving a prime number input by the user:

SetSeed(to_ZZ(1234567890));
char p[MAX_STRING_LEN];

cin.getline(p, MAX_STRING_LEN);

We declare and initialize an NTL big integer object pZZ to store this prime number:

ZZ pZZ = to_ZZ(p);

Now we initialize the underline prime field GF(p):

field_t::init(pZZ);

We shall declare and initialize several elements to hold the genus 2 curve, system parameters, keys and so on:

ZZ a, b;
g2hcurve curve;
divisor P, Q1, Q2;

Generate a random valid genus 2 curve:

curve.random();

Set curve for the divisors. A curve needs only to be set once in a program to work for all divisors.

P.set_curve(curve);

To perform Diffie-Hellman key exchange, it is not necessary to know the order of P. A fact is that this order is close to p^2. So we choose a and b to be two random number bounded by p^2.

RandomBnd(a, pZZ*pZZ);
RandomBnd(b, pZZ*pZZ);

We generate a random base point P:

P.random();

Alice computes

Q1 = a * P;

Bob computes

Q2 = b * P;

A successful key exchange should yield the shared secret

if ( b * Q1 == a * Q2)
  cout << "DH key exchange succeeded!" << endl;
else
  cout << "DH key exchange failed!" << endl;

A complete source file for this example can be found in example/dh.C.

4.2 HEC-ElGamal encryption

This example is similar to the Diffie-Hellman key exchange example. Please refer to the source file in examples/elgamal_enc.C for details.

4.3 HEC-ElGamal digital signature

We shall use G2HEC to build a digital signature scheme: the ElGamal digital signature.

Recall how this signature scheme works:

Bob chooses a genus 2 curve C and a prime number p so that the number of GF(p)-rational points of the Jacobian of C has a large prime factor N – preferably the number itself is prime. He then chooses a divisor g of order N, a secret private key x\in\{1, \ldots, N - 1\}, then computes a divisor h = [x] g. Bob publishes g and h as his public key.

To sign a message m \in Z/(N), Bob first generates a random integer i \in {1, \ldots, N - 1}, and computes

Bob then computes a solution, b \in Z/(N) to the congruence

Here f is a map from the Jacobian of C to Z/(N) which is almost injective.

Bob sends the signature (a, b) together with the message m to Alice.

Upon receiving the message and signature from Bob, Alice verifies the signature by checking that

holds.

It needs to be point out that a technical aspect of this algorithm involves the choice of the curve C and the prime number p so that its Jacobian has an order divisible by a large prime number. This is not a trivial task – it involves quite amount of mathematics. Fortunately, there are published data that users can use directly to avoid this difficulty. According to the paper “Construction of Secure Random Curves of Genus 2 over Prime Fields” by Gaudry and Schost, we choose to use in our example the curve with p = 5 \cdot 10^{24} + 850349. The order of the Jacobian of the curve is a prime number

which is to our best interest. In this case, we can pick any random non-unit divisor g as our base point.

At this point, we are able present a local version of this signature scheme.

As usual we include the header file g2hec_Genus2_ops.h:

#include <g2hec_Genus2_ops.h>

Then we define some macros that we are going to use, including the values of coefficients of the polynomial f, the prime number p, the group order of the Jacobian, and a function that maps a suitable value to an NTL ZZ_p object.

#define f3 "2682810822839355644900736"
#define f2 "226591355295993102902116"
#define f1 "2547674715952929717899918"
#define f0 "4797309959708489673059350"
#define ps "5000000000000000008503491"
#define N "24999999999994130438600999402209463966197516075699"

#define str_to_ZZ_p(x) to_ZZ_p(to_ZZ(x))

Also we issue the statement

NS_G2_CLIENT

Recall that we need an almost bijection that maps elements in the Jacobian to an element in {1, \ldots, N - 1}. This map can be chosen as follows:

static ZZ from_divisor_to_ZZ(const divisor& div, const ZZ& n)
{
  poly_t u = div.get_upoly();
  ZZ temp = AddMod(sqr(rep(u.rep[0])), sqr(rep(u.rep[1])), n);
  return ( IsZero(temp) ? to_ZZ(1) : temp );
}

We just mention that we choose this function to take a divisor

to the value defined by the sum of the squares of the degree 0 and degree 1 coefficients modulo the group order N of the Jacobian. Users can define their own such function to use. Security might be affected by bad choice of this almost injective function.

We start working on the main function by initializing the PRNG seed and declaring and define several values:

  SetSeed(to_ZZ(1234567890));

  ZZ p = to_ZZ(ps);

  field_t::init(p); 

  ZZ order = to_ZZ(N);

  ZZ x, k, b, m; 
  // Private key x, random number k, parameter b, message m

  ZZ f_a;

  g2hcurve curve;

  divisor g, h, a;

  poly_t f;

Then we manually assign values of polynomial f and define the corresponding genus 2 curve:

  SetCoeff(f, 5, 1);
  SetCoeff(f, 4, 0);
  SetCoeff(f, 3, str_to_ZZ_p(f3));
  SetCoeff(f, 2, str_to_ZZ_p(f2));
  SetCoeff(f, 1, str_to_ZZ_p(f1));
  SetCoeff(f, 0, str_to_ZZ_p(f0));
  curve.set_f(f);

Then you update the curve information:

curve.update();

This will update some flags related to properties of the curve, and needs to be done immediately after manual assignments to the curve’s defining elements (e.g., the polynomial f).

Now we are ready to set the curve as the underlying curve of the divisors.

g.set_curve(curve);

We randomly choose the base point g, message m to be signed, the private key x, and the public key h:

  do {
    g.random();
  } while (g.is_unit());

  RandomBnd(m, order);

  do {
    RandomBnd(x, order);
  } while (IsZero(x));

  h = x * g;

Note that we want the base point g to be any divisor except the unit divisor, and we do not allow the private key x to be 0. This is what the do...while statements do.

Now we shall generate the ElGamal signature (a, b):

  do {
    RandomBnd(k, order);
  } while (IsZero(k));

  a = k * g;

  f_a = from_divisor_to_ZZ(a, order);

  /* b = (m - x*f(a))/k mod N */
  b = MulMod(m - x * f_a, InvMod(k, order), order);

The element f_a holds the value f(a) given by the almost injection applied to the divisor a.

Alright! Now the most exciting moment has arrived – signature verification:

  if ( f_a * h + b * a == m * g )
    cout << "ElGamal signature verification succeeded!" << endl;
  else
    cout << "ElGamal signature verification failed!" << endl;

The complete source file can be found in examples/elgamal_sig.C.

**************************************************************

In the following chapters, we will give a general overview of the G2HEC’s programming interface. This includes:

• Functions related to genus 2 curve generation and manipulation
• Functions related to divisor generation and manipulation
• Divisor arithmetic functions
• Input and output functions
• Randomness functions

All these interfaces are exported by include/g2hec_Genus2_ops.h unless otherwise specified.

**************************************************************