Koblitz-163bit, the point is on curve! On curve! Yay!

Oh, finally. The code proves that the point (x, y) from the sample parameter is on the Koblitz-163.

There are several mistakes:

  1. I took the wrong sample parameters set. It’s not supposed to be the parameters at the previous posting, but these:
  2. I used the wrong equation. It was y^{2}+xy=x^{3}+ax+b ! After spending the whole day debugging every operations and bits and parameters, I checked the equation, and I picked the wrong one all this time. It should have been y^{2}+xy=x^{3}+x^{2}+1 .

The coding is:

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

extern FIELD2N poly_prime;

int main(){
   INDEX i;

   FIELD2N a = {0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001};
   FIELD2N b = {0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001};
   /*FIELD2N b = {0x00000002, 0x0a601907, 0xb8c953ca, 0x1481eb10, 0x512f7874, 0x4a3205fd};   */
   FIELD2N x = {0x00000002, 0xFE13C053, 0x7BBC11AC, 0xAA07D793, 0xDE4E6D5E, 0x5C94EEE8};
   FIELD2N y = {0x00000002, 0x89070FB0, 0x5D38FF58, 0x321F2E80, 0x0536D538, 0xCCDAA3D9};

   FIELD2N yy, xy;
   FIELD2N left, right;
   FIELD2N c;
   FIELD2N x_2, x_3, ax;

   null(&yy);
   null(&xy);
   null(&c);
   null(&left);
   null(&right);
   null(&x_2);
   null(&x_3);
   null(&ax);

   if (!irreducible(&poly_prime)) return(0);
      print_field("poly_prime = ", &poly_prime);

   printf("\nNUMBITS = %d", NUMBITS);
   printf("\nNUMWORD = %d", NUMWORD);
   printf("\nMAXLONG = %d\n", MAXLONG);

   print_field("a = ", &a);
   print_field("b = ", &b);

   print_field("x = ", &x);
   print_field("y = ", &y);
   poly_mul(&y, &y, &yy);
   print_field("yy = ", &yy);
   poly_mul(&x, &y, &xy);
   print_field("xy = ", &xy);
   SUMLOOP(i) left.e[i] = yy.e[i] ^ xy.e[i];
   print_field("left = ", &left);

   poly_mul(&x, &x, &x_2);
   print_field("x_2 = ", &x_2);
   poly_mul(&x, &x_2, &x_3);
   print_field("x_3 = ", &x_3);
   poly_mul(&a, &x, &ax);
   print_field("ax = ", &ax);
   print_field("b = ", &b);
   SUMLOOP(i) right.e[i] = x_3.e[i] ^ x_2.e[i];
   SUMLOOP(i) right.e[i] = right.e[i] ^ b.e[i];
   print_field("right = ", &right);

   return 0;
}

this header file is also have to be updated for the NUMBITS:

/*** field2n.h ***/

#define WORDSIZE        (sizeof(int)*8)
#define NUMBITS         163

#define NUMWORD         (NUMBITS/WORDSIZE)
#define UPRSHIFT        (NUMBITS%WORDSIZE)

#define MAXLONG         (NUMWORD+1)

#define MAXBITS         (MAXLONG*WORDSIZE)
#define MAXSHIFT        (WORDSIZE-1)
#define MSB                     (1L<<MAXSHIFT)

#define UPRBIT          (1L<<(UPRSHIFT-1))
#define UPRMASK         (~(-1L<<UPRSHIFT))
#define SUMLOOP(i)      for(i=0; i<MAXLONG; i++)

typedef short int INDEX;

typedef unsigned long ELEMENT;

typedef struct {
        ELEMENT         e[MAXLONG];
}  FIELD2N;

and also this line from polymain.c:

FIELD2N poly_prime = {0x00000008, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x000000c9}; /*163*/

and the result is:


poly_prime =
8 0 0 0 0 c9

NUMBITS = 163
NUMWORD = 5
MAXLONG = 6
a =
0 0 0 0 0 1
b =
0 0 0 0 0 1

2 fe13c053 7bbc11ac aa07d793 de4e6d5e 5c94eee8
y =
2 89070fb0 5d38ff58 321f2e80 536d538 ccdaa3d9
yy =
7 ca0561ef a7b090b5 ddf25eaf f0567c2c 39c1cad7
xy =
4 d7418721 62b253d5 a381f1f6 80b47e5c ad3aa2a
left =
3 1d44e6ce c502c360 7e73af59 70e20270 331260fd
x_2 =
6 710bd85f 2b559b08 5dc2832e 86f4a4c 7ef8d0be
x_3 =
5 6c4f3e91 ee575868 23b12c77 788d483c 4deab042
right =
3 1d44e6ce c502c360 7e73af59 70e20270 331260fd

Now left and right is equal! YAY!!!

Advertisements