Method and apparatus for elliptic curve cryptography and recording medium therefore

A method of implementing an elliptic curve cryptographic operation in a cryptographic apparatus implementing an elliptic curve cryptography in a finite field of characteristic 2 (or an extension field of “2”), in which said elliptic curve is given by y2+xy=ax2+b and in which x and y are variables in an x-y coordinate system, a and b are parameters, addition of points P1(x1, y1) and P2(x2, y2) on said elliptic curve composed of points defined by individual coordinate components is presumed to be represented by P3(x3, y3) with subtraction of said points P1(x1, y1) and P2(x2, y2) being presumed to be represented by P4(x4, y4), said method comprising the steps performed by said cryptographic apparatus, of:

• inputting the coordinate component x1;
• transforming the inputted coordinate component x1 into x- and z-coordinates coordinates [X1, Z1] of a projective space where z is a variable of a projective space where z is a variable in the z-coordinate;
• storing said coordinates [X1, Z1] of said projective space;
• transforming the coordinate component x2 into coordinates [X2, Z2] of said projective space;
• storing the projective coordinates [X2, Z2];
• transforming the coordinate component x4 into coordinates [X4, Z4] of said projective space;
• storing the coordinates [X4, Z4];
• determining projective coordinates [X3, Z3] from the stored projective coordinates [X1, Z1], [X2, Z2] and [X4, Z4];
• transforming the projective coordinates [X3, Z3] into said coordinate component x3;
• and
• outputting said coordinate component x3,
• whereby scalar multiplication of said point P1(x1, y1) is determined;
• generating a random number k;
• storing said generated random number k;
• transforming the x-coordinates into projective coordinates to thereby derive projective coordinates [kx, k] through arithmetic operation of individual coordinate components of said projective space and said stored random number k.

An apparatus implementing an elliptic curve cryptographic operation in a finite field of characteristic 2 (or an extension field of “2”), in which x and y are variables in an x-y coordinate system, a and b are parameters, said elliptic curve is given by y2+xy=x3+ax2+b, comprising:

• random number generating means for generating a random number k;
• projective coordinate transformation means receiving as inputs thereto coordinate x0 of said finite field of characteristic 2 and said random number k, to thereby transform said coordinate x0 into projective coordinates [kx0, k]=[X1, Z,1];
• doubling arithmetic means for arithmetically determining a double point from said projective coordinates [X1, Z1];
• addition arithmetic means for determining an addition point from said projective coordinate [X1, Z1] where Z is a variable in the z-coordinate to thereby output said addition point;
• and
• scalar multiplication means receiving, information from said projective coordinate transformation means, said doubling arithmetic means and said addition arithmetic means to thereby perform scalar multiplication of the coordinate component x0.

A recording medium storing a program for implementing an elliptic curve cryptographic operation, said recording medium being in a cryptographic apparatus implementing an elliptic curve cryptography in a finite field of characteristic 2 (or an extension field of “2”), in which said elliptic curve is given by y2+xy=x3+ax2+b, in which x and y are variables in an x-y coordinate system, a and b are parameters, addition of points P1(x1, y1) and P2(x2, y2) on said elliptic curve composed of points defined by individual coordinate components is presumed to be represented by P3(x3, y3) with subtraction of points P1(x1, y1) and P2(x2, y2) being presumed to be represented by P4, (x4, y4), said program when executed causing the cryptographic apparatus to perform:

• inputting an coordinate component x1;
• transforming the inputted coordinate component x1 into x- and z-coordinates [X1, Z1] in a projective space;
• storing said coordinates [X2, Z2] of said projective space;
• transforming the coordinate component x2 into coordinates [X2, Z2] of said projective space;
• storing the projective coordinate [X1, Z1] where z is a variable in the z-coordinate;
• transforming the coordinate component x4 into coordinates [X4, Z4] of said projective space;
• storing the projective coordinates [X4, Z4];
• determining projective coordinates [X3, Z3] from the stored projective coordinates [X1, Z1], [X2, Z2] and [X4, Z4];
• transforming said projective coordinates [X3, Z3] into the coordinate component x3;
• and
• outputting said coordinate component x3,
• whereby scalar multiplication of said point P1(x1, y1) is determined;
• generating a random number k;
• storing said generated random number k;
• transforming the x-coordinates into projective coordinates to thereby derive projective coordinates [k2x, k] through arithmetic operation of individual coordinate components of said projective space and said stored random number k.

A recording medium storing a program for implementing an elliptic curve cryptographic operation, said recording medium being in a cryptographic apparatus implementing an elliptic curve cryptography in a finite field of characteristic 2 (or an extension field of “2”), in which said elliptic curve is given by y2+xy=x3+ax2+b, in which x and y are variables in an x-y coordinate system, a and b are parameters, addition of points P1(x1, y1) and P2(x2, y2) on said elliptic curve composed of points defined by individual coordinate components is presumed to be represented by P3(x3, y3) with subtraction of points P1(x1, y1) and P2(x2, y2) being presumed to be represented by P4, (x4, y4), said program when executed causing the cryptographic apparatus to perform:

• inputting an coordinate component x1;
• transforming the inputted coordinate component x1 into x- and z-coordinates [X1, Z1] in a projective space:
• storing said coordinates [X2, Z2] of said projective space;
• transforming the coordinate component x2 into coordinates [X2, Z2] of said projective space;
• storing the projective coordinate [X1, Z1] where z is a variable in the z-coordinate;
• transforming the coordinate component x4 into coordinates [X4, Z4] of said projective space;
• storing the projective coordinates [X4, Z4];
• determining projective coordinates [X3, Z3] from the stored projective coordinates [X1, Z1], [X2, Z2] and [X4, Z4];
• transforming said projective coordinates [X3, Z3] into the coordinate component x3;
• and
• outputting said coordinate component x3,
• whereby scalar multiplication of said point P1(x1, y1) is determined;
• generating a random number k;
• storing said generated random number k;
• transforming the x-coordinates into projective coordinates to thereby derive projective coordinates [kx, k] through arithmetic operation of individual coordinate components of said projective space and said stored random number k.