de.flexiprovider.common.math.ellipticcurves
Class PointGF2n

java.lang.Object
  |
  +--de.flexiprovider.common.math.ellipticcurves.Point
        |
        +--de.flexiprovider.common.math.ellipticcurves.PointGF2n

public class PointGF2n

extends Point

This class implements points and their arithmetic on elliptic curves over finite fields with characteristic 2 (GF(2ⁿ)). A Point P = (x, y) is the tupel x, y that solves the equation y² + xy = x³ + ax² + b, x and y in GF(2ⁿ).

Points on elliptic curves can be added and subtracted. Since each of these operations require a field inversion in GF(2ⁿ), which is expensive, this class calculates with projective coordinates to avoid these inversions. The equation for the elliptic curve is as follows:
Y²Z⁶ + XYZ⁵ = X³Z⁶ + aX²Z⁴ + b,
with x = X/Z² and y = Y/Z³.

For the formulas of the projective addition and doubling add and multiplyBy2, respectively.

Author:

Birgit Henhapl, Vangelis Karatsiolis

See Also:

EllipticCurveGF2n, Point, GF2nField, GF2nElement

Fields inherited from class de.flexiprovider.common.math.ellipticcurves.Point

ENCODING_TYPE_COMPRESSED, ENCODING_TYPE_HYBRID, ENCODING_TYPE_UNCOMPRESSED, mE, mP

Constructor Summary

PointGF2n(byte[] encoded, EllipticCurveGF2n E)
Constructs a new point.

PointGF2n(EllipticCurveGF2n E)
Construct the point at infinity on the specified elliptic curve

PointGF2n(EllipticCurveGF2n E, java.util.Random rand)
Construct a random point on the specified elliptic curve using the given source of randomness.

PointGF2n(GF2nElement x, GF2nElement y, EllipticCurveGF2n E)
Constructs point with specified parameters.

PointGF2n(GF2nElement x, GF2nElement y, GF2nElement z, EllipticCurveGF2n E)
Constructs point with specified parameters.

PointGF2n(PointGF2n other)
Copy constructor.

Method Summary

Point	add(Point other) Adds to this point the point other.
Point	addAffine(Point other) Adds in affine coordinates to this point the point other.
void	addToThis(Point other) Adds to this point the point other.
java.lang.Object	clone()
(package private) byte[]	encodeCompressed() Returns this point in affine, compressed form as a byte array.
(package private) byte[]	encodeHybrid() Returns this point in affine, hybrid form as a byte array.
(package private) byte[]	encodeUncompressed() Returns this point in affine, decompressed form as a byte array.
boolean	equals(java.lang.Object other) Tests whether this point is equal to other.
Point	getAffin() Returns this point with affin coordinates.
GFElement	getX()
GFElement	getXAffin() Return the x-coordinate of this point in affine representation.
GFElement	getY()
GFElement	getYAffin() Return the y-coordinate of this point in affine representation.
GFElement	getZ()
int	hashCode()
boolean	isZero() Tests, whether this point is at infinity.
Point	multiplyBy2() Doubles this point.
Point	multiplyBy2Affine() Doubles this point in affine coordinates.
void	multiplyThisBy2() Doubles this point.
Point	negate() Returns the inverse of this point.
void	negateThis() Negates this PointGF2n.
boolean	onCurve() Tests whether this point is on the curve mE.
Point	subtract(Point other) Subtracts point other from this point.
void	subtractFromThis(Point other) Subtracts point other from this point.
java.lang.String	toString() Returns this point in affine representation as a String: (x, y), where x = mX/mZ2 and y = mZ/mZ3.

Methods inherited from class de.flexiprovider.common.math.ellipticcurves.Point

EC2OSP, getE, isNegativeOf, OS2ECP

Methods inherited from class java.lang.Object

, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

PointGF2n

public PointGF2n(EllipticCurveGF2n E)

Construct the point at infinity on the specified elliptic curve

Parameters:

E - the elliptic curve this point lies on

PointGF2n

public PointGF2n(EllipticCurveGF2n E,
                 java.util.Random rand)

Construct a random point on the specified elliptic curve using the given source of randomness.

Parameters:

E - the elliptic curve this point lies on

rand - the source of randomness

PointGF2n

public PointGF2n(GF2nElement x,
                 GF2nElement y,
                 EllipticCurveGF2n E)
          throws InvalidPointException,
                 DifferentFieldsException

Constructs point with specified parameters. This method throws an InvalidPointException, if (x, y) is not on curve E.

Parameters:

x - x-coordinate

y - y-coordinate

E - EllipticCurveGF2n is the elliptic curve this point lies on

Throws:

InvalidPointException - if the specified point is not on the curve.

DifferentFieldsException - if x and y are defined over different fields.

PointGF2n

public PointGF2n(GF2nElement x,
                 GF2nElement y,
                 GF2nElement z,
                 EllipticCurveGF2n E)
          throws InvalidPointException,
                 DifferentFieldsException

Constructs point with specified parameters. This method throws an InvalidPointException, if (x, y) is not on curve E.

Parameters:

x - x-coordinate

y - y-coordinate

z - z-coordinate

E - the elliptic curve this point lies on

Throws:

InvalidPointException - if the specified point is not on the curve.

DifferentFieldsException - if x, y, and z are defined over different fields.

PointGF2n

public PointGF2n(byte[] encoded,
                 EllipticCurveGF2n E)
          throws InvalidPointException,
                 InvalidFormatException

Constructs a new point. The information is packed in the given byte array together with the given elliptic curve. (see X9.63-199x)

Parameters:

encoded - the point in normal, compressed or hybrid form.

E - the underlying elliptic curve

Throws:

InvalidPointException - if the point is not on the curve.

InvalidFormatException - if the point representation is invalid.

PointGF2n

public PointGF2n(PointGF2n other)

Copy constructor.

Parameters:

other - point to copy

Method Detail

clone

public java.lang.Object clone()

Overrides:

clone in class Point

Returns:

a clone of this point

equals

public boolean equals(java.lang.Object other)

Tests whether this point is equal to other.

Overrides:

equals in class Point

Parameters:

other - point to compare this point with

Returns:

true if this == other
false if this != other

hashCode

public int hashCode()

Overrides:

hashCode in class Point

Returns:

the hash code of this point

See Also:

Object.hashCode()

toString

public java.lang.String toString()

Returns this point in affine representation as a String: (x, y), where x = mX/mZ² and y = mZ/mZ³. If this point is at infinity (that means, mZ = 0), the output is (0, 0).

Overrides:

toString in class java.lang.Object

Returns:

String (x, y)

getX

public GFElement getX()

Overrides:

getX in class Point

Returns:

the x-coordinate of this point

getY

public GFElement getY()

Overrides:

getY in class Point

Returns:

the y-coordinate of this point

getZ

public GFElement getZ()

Overrides:

getZ in class Point

Returns:

the z-coordinate of this point

getXAffin

public GFElement getXAffin()

Return the x-coordinate of this point in affine representation. In this class, the projective representation x = X/Z² and y = Y/Z³ is chosen to speed up point addition. This method returns the x-coordinate in affine representation.

Overrides:

getXAffin in class Point

Returns:

the x-coordinate of this point in affine representation

getYAffin

public GFElement getYAffin()

Return the y-coordinate of this point in affine representation. In this class, the projective representation x = X/Z² and y = Y/Z³ is chosen to speed up point addition. This method returns the y-coordinate in affine representation.

Overrides:

getYAffin in class Point

Returns:

the y-coordinate of this point in affine representation

getAffin

public Point getAffin()

Description copied from class: Point

Returns this point with affin coordinates.

Overrides:

getAffin in class Point

Returns:

this in affine coordinates

onCurve

public boolean onCurve()

Tests whether this point is on the curve mE. This method returns true, if
mY² - mX³ - mA*mX* mZ⁴ - mB*mZ⁶ = 0,
otherwise false.

Overrides:

onCurve in class Point

Returns:

mY² - mX ³ - mA*mX*mZ ⁴ - mB*mZ⁶ == 0

See Also:

EllipticCurveGF2n

isZero

public boolean isZero()

Description copied from class: Point

Tests, whether this point is at infinity.

Overrides:

isZero in class Point

Returns:

flag indicating whether this is the point at infinity

add

public Point add(Point other)
          throws DifferentCurvesException

Adds to this point the point other.
The algorithm is due to Chudnovsky and Chudnovsky:
input : (X₀, Y₀, Z₀), (X₁, Y₁, Z₁)
output: (X₀, Y₀, Z₀) + (X₁, Y₁, Z₁) = (X₂, Y₂, Z₂)

U₀ = X₀Z₁²
S₀ = Y₀Z₁³
U₁ = X₁Z₀²
W = U₀ + U₁
S₁ = Y₁Z₀³
R = S₀ + S₁
L = Z₀W V = RX¹ + LY₁
Z₂ = LZ₁
T = R + Z₂
X₂ = aZ₂² + TR² + W³
Y₂ = TX₂ + VL²

Overrides:

add in class Point

Parameters:

other - point to add to this point

Returns:

this + other

Throws:

DifferentCurvesException - if this and other are not on the same curve.

addToThis

public void addToThis(Point other)
               throws DifferentCurvesException

Adds to this point the point other.
The algorithm is due to Chudnovsky and Chudnovsky:
input : (X₀, Y₀, Z₀), (X₁, Y₁, Z₁)
output: (X₀, Y₀, Z₀) + (X₁, Y₁, Z₁) = (X₂, Y₂, Z₂)

U₀ = X₀Z₁²
S₀ = Y₀Z₁³
U₁ = X₁Z₀²
W = U₀ + U₁
S₁ = Y₁Z₀³
R = S₀ + S₁
L = Z₀W V = RX¹ + LY₁
Z₂ = LZ₁
T = R + Z₂
X₂ = aZ₂² + TR² + W³
Y₂ = TX₂ + VL²

Overrides:

addToThis in class Point

Parameters:

other - point to add to this point

Throws:

DifferentCurvesException - if this and other are not on the same curve.

addAffine

public Point addAffine(Point other)

Adds in affine coordinates to this point the point other.

Overrides:

addAffine in class Point

Parameters:

other - point to add to this point

Returns:

this + other in affine coordinates

Throws:

DifferentCurvesException - when other is defined over another curve

multiplyBy2

public Point multiplyBy2()

Doubles this point.
input : (X₁, Y₁, Z₁)
output: 2*(X₁, Y₁, Z₁) = (X₂, Y₂, Z₂)

c = b^2m-2,
Z₂ = X₁Z₁²
X₂ = (X₁ + cZ₁²)⁴
U = Z₂ + X₁² + Y₁Z₁
Y₂ = X₁₄Z₂ + UX2

Overrides:

multiplyBy2 in class Point

Returns:

2*this

multiplyThisBy2

public void multiplyThisBy2()

Doubles this point.
input : (X₁, Y₁, Z₁)
output: 2*(X₁, Y₁, Z₁) = (X₂, Y₂, Z₂)

c = b^2m-2,
Z₂ = X₁Z₁²
X₂ = (X₁ + cZ₁²) ⁴
U = Z₂ + X₁² + Y₁Z n ₁
Y₂ = X₁₄Z₂ + UX 2

Overrides:

multiplyThisBy2 in class Point

multiplyBy2Affine

public Point multiplyBy2Affine()

Doubles this point in affine coordinates.

Overrides:

multiplyBy2Affine in class Point

Returns:

2*this in affine coordinates

subtract

public Point subtract(Point other)
               throws DifferentCurvesException

Subtracts point other from this point. When P = (x, y) then -P = (x, x + y). So this method returns
add(other.negate())

Overrides:

subtract in class Point

Parameters:

other - another Point

Returns:

this - other

Throws:

DifferentCurvesException - if this and other are not on the same curve.

subtractFromThis

public void subtractFromThis(Point other)
                      throws DifferentCurvesException

Subtracts point other from this point. When P = (x, y) then -P = (x, x + y).

Overrides:

subtractFromThis in class Point

Parameters:

other - another Point

Throws:

DifferentCurvesException - if this and other are not on the same curve.

negate

public Point negate()

Returns the inverse of this point. When P = (x, y) then -P = (x, x + y).

Overrides:

negate in class Point

Returns:

-this

negateThis

public void negateThis()

Negates this PointGF2n.

Overrides:

negateThis in class Point

encodeUncompressed

byte[] encodeUncompressed()

Returns this point in affine, decompressed form as a byte array. The first byte keeps the value 4, to indicate, that this point is stored in an uncompressed format. The rest of the returned array is split in two halves, the first holds the x-coordinate mX and the second they-coordinate mY.

Overrides:

encodeUncompressed in class Point

Returns:

this as byte array

encodeCompressed

byte[] encodeCompressed()

Returns this point in affine, compressed form as a byte array. The first byte keeps the value 2 or 3, to indicate, that this point is stored in a compressed format. The rest of the returned array is the x-coordinate mX.

Overrides:

encodeCompressed in class Point

Returns:

this as byte array

encodeHybrid

byte[] encodeHybrid()

Returns this point in affine, hybrid form as a byte array. The first byte keeps the value 6 or 7, to indicate, that this point is stored in a hybrid format. The rest of the returned array is split in two halves, the first holds the x-coordinate mX and the second they-coordinate mY.

Overrides:

encodeHybrid in class Point

Returns:

this as byte array