examples/elgamal_sig.C

   1 /* Example: local ElGamal signature */
   2
   3 /* The following data are from the paper "Construction of Secure Random Curves
   4  * of Genus 2 over Prime Fields" by Gaudry and Schost.
   5  *
   6  * Use curve C: y^2 =  x^5 + 2682810822839355644900736 * x3
   7  + 226591355295993102902116 * x2 + 2547674715952929717899918 * x
   8  + 4797309959708489673059350.
   9  * with
  10  * p = 5*10^24 + 8503491
  11
  12  * The Jacobian of this curve has a prime order
  13  * N = 24999999999994130438600999402209463966197516075699 (164bit).
  14  * We shall choose a nonunit point g of this order on the Jacobian to be the
  15  * base point.
  16
  17  */
  18
  19 #include <g2hec_nsfieldtype.h>
  20 #include <g2hec_Genus2_ops.h>
  21
  22 #define f3 "2682810822839355644900736"
  23 #define f2 "226591355295993102902116"
  24 #define f1 "2547674715952929717899918"
  25 #define f0 "4797309959708489673059350"
  26 #define ps "5000000000000000008503491"
  27 #define N "24999999999994130438600999402209463966197516075699"
  28
  29 #define str_to_ZZ_p(x) to_ZZ_p(to_ZZ(x))
  30
  31 NS_G2_CLIENT
  32
  33 /* An almost bijection from Jacobian to {1, 2, ..., n-1}
  34  * which maps [u(x), v(x)] to u0^2 + u1^2 mod n.
  35 */
  36 static ZZ from_divisor_to_ZZ(const divisor& div, const ZZ& n)
  37 {
  38   poly_t u = div.get_upoly();
  39   ZZ temp = AddMod(sqr(rep(u.rep[0])), sqr(rep(u.rep[1])), n);
  40   return ( IsZero(temp) ? to_ZZ(1) : temp );
  41 }
  42
  43 int main()
  44 {
  45   /* Set PRNG seed */
  46   SetSeed(to_ZZ(1234567890));
  47
  48   /* Set prime */
  49   ZZ p = to_ZZ(ps);
  50
  51   field_t::init(p); // define GF(p)
  52
  53   ZZ order = to_ZZ(N);
  54
  55   ZZ x, k, b, m; // Private key x, random number k, parameter b, message m
  56
  57   ZZ f_a;
  58
  59   g2hcurve curve;
  60
  61   divisor g, h, a;
  62
  63   poly_t f;
  64
  65   SetCoeff(f, 5, 1);
  66   SetCoeff(f, 4, 0);
  67   SetCoeff(f, 3, str_to_ZZ_p(f3));
  68   SetCoeff(f, 2, str_to_ZZ_p(f2));
  69   SetCoeff(f, 1, str_to_ZZ_p(f1));
  70   SetCoeff(f, 0, str_to_ZZ_p(f0));
  71   curve.set_f(f);
  72   curve.update();
  73
  74   g.set_curve(curve);
  75
  76   /* Base point g */
  77   do {
  78     g.random();
  79   } while (g.is_unit());
  80
  81   /* message m */
  82   RandomBnd(m, order);
  83
  84   /* private key x <> 0 */
  85   do {
  86     RandomBnd(x, order);
  87   } while (IsZero(x));
  88
  89   /* public key h = [x]g */
  90   h = x * g;
  91
  92   /* random number k <> 0*/
  93   do {
  94     RandomBnd(k, order);
  95   } while (IsZero(k));
  96
  97   cout << "Generating ElGmal signature..." << endl;
  98   sleep(3);
  99
 100   a = k * g;
 101
 102   f_a = from_divisor_to_ZZ(a, order);
 103
 104   /* b = (m - x*f(a))/k mod N */
 105   b = MulMod(m - x * f_a, InvMod(k, order), order);
 106
 107   cout << "ElGmal signature generated!" << endl;
 108   sleep(3);
 109
 110   /* Signature verification */
 111   if ( f_a * h + b * a == m * g )
 112     cout << "ElGamal signature verification succeeded!" << endl;
 113   else
 114     cout << "ElGamal signature verification failed!" << endl;
 115
 116    return 0;
 117 }