net.i2p.crypto.eddsa.math
Class GroupElement

java.lang.Object
  extended by net.i2p.crypto.eddsa.math.GroupElement
All Implemented Interfaces:
Serializable

public class GroupElement
extends Object
implements Serializable

A point (x,y) on an EdDSA curve.

Reviewed/commented by Bloody Rookie (nemproject@gmx.de)

Literature:
[1] Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe and Bo-Yin Yang : High-speed high-security signatures
[2] Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson: Twisted Edwards Curves Revisited
[3] Daniel J. Bernsteina, Tanja Lange: A complete set of addition laws for incomplete Edwards curves
[4] Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters: Twisted Edwards Curves
[5] Christiane Pascale Peters: Curves, Codes, and Cryptography (PhD thesis)
[6] Daniel J. Bernstein, Peter Birkner, Tanja Lange and Christiane Peters: Optimizing double-base elliptic-curve single-scalar multiplication

Since:
0.9.15
Author:
str4d
See Also:
Serialized Form

Nested Class Summary
static class GroupElement.Representation
          Available representations for a group element.
 
Field Summary
(package private)  Curve curve
          Variable is package private only so that tests run.
(package private)  GroupElement[] dblPrecmp
          Precomputed table for doubleScalarMultiplyVariableTime(GroupElement, byte[], byte[]), filled if necessary.
(package private)  GroupElement[][] precmp
          Precomputed table for scalarMultiply(byte[]), filled if necessary.
(package private)  GroupElement.Representation repr
          Variable is package private only so that tests run.
(package private)  FieldElement T
          Variable is package private only so that tests run.
(package private)  FieldElement X
          Variable is package private only so that tests run.
(package private)  FieldElement Y
          Variable is package private only so that tests run.
(package private)  FieldElement Z
          Variable is package private only so that tests run.
 
Constructor Summary
GroupElement(Curve curve, byte[] s)
          Creates a group element for a curve from a given encoded point.
GroupElement(Curve curve, GroupElement.Representation repr, FieldElement X, FieldElement Y, FieldElement Z, FieldElement T)
          Creates a group element for a curve.
 
Method Summary
 GroupElement add(GroupElement q)
          GroupElement addition using the twisted Edwards addition law with extended coordinates (Hisil2008).
static GroupElement cached(Curve curve, FieldElement YpX, FieldElement YmX, FieldElement Z, FieldElement T2d)
          Creates a new group element in CACHED representation.
(package private)  GroupElement cmov(GroupElement u, int b)
          Constant-time conditional move.
 GroupElement dbl()
          Doubles a given group element p in P^2 or P^3 representation and returns the result in P x P representation.
 GroupElement doubleScalarMultiplyVariableTime(GroupElement A, byte[] a, byte[] b)
          r = a * A + b * B where a = a[0]+256*a[1]+...+256^31 a[31], b = b[0]+256*b[1]+...+256^31 b[31] and B is this point.
 boolean equals(Object obj)
           
 Curve getCurve()
          Gets the curve of the group element.
 GroupElement.Representation getRepresentation()
          Gets the representation of the group element.
 FieldElement getT()
          Gets the T value of the group element.
 FieldElement getX()
          Gets the X value of the group element.
 FieldElement getY()
          Gets the Y value of the group element.
 FieldElement getZ()
          Gets the Z value of the group element.
 int hashCode()
           
 boolean isOnCurve()
          Verify that a point is on its curve.
 boolean isOnCurve(Curve curve)
          Verify that a point is on the curve.
 GroupElement negate()
          Negates this group element by subtracting it from the neutral group element.
static GroupElement p1p1(Curve curve, FieldElement X, FieldElement Y, FieldElement Z, FieldElement T)
          Creates a new group element in P1P1 representation.
static GroupElement p2(Curve curve, FieldElement X, FieldElement Y, FieldElement Z)
          Creates a new group element in P2 representation.
static GroupElement p3(Curve curve, FieldElement X, FieldElement Y, FieldElement Z, FieldElement T)
          Creates a new group element in P3 representation.
static GroupElement precomp(Curve curve, FieldElement ypx, FieldElement ymx, FieldElement xy2d)
          Creates a new group element in PRECOMP representation.
 void precompute(boolean precomputeSingle)
          Precomputes several tables.
 GroupElement scalarMultiply(byte[] a)
          h = a * B where a = a[0]+256*a[1]+...+256^31 a[31] and B is this point.
(package private)  GroupElement select(int pos, int b)
          Look up 16^i r_i B in the precomputed table.
(package private) static byte[] slide(byte[] a)
          Calculates a sliding-windows base 2 representation for a given value a.
 GroupElement sub(GroupElement q)
          GroupElement subtraction using the twisted Edwards addition law with extended coordinates (Hisil2008).
 byte[] toByteArray()
          Converts the group element to an encoded point on the curve.
 GroupElement toCached()
          Converts the group element to the CACHED representation.
 GroupElement toP2()
          Converts the group element to the P2 representation.
 GroupElement toP3()
          Converts the group element to the P3 representation.
(package private) static byte[] toRadix16(byte[] a)
          Convert a to radix 16.
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

curve

final Curve curve
Variable is package private only so that tests run.


repr

final GroupElement.Representation repr
Variable is package private only so that tests run.


X

final FieldElement X
Variable is package private only so that tests run.


Y

final FieldElement Y
Variable is package private only so that tests run.


Z

final FieldElement Z
Variable is package private only so that tests run.


T

final FieldElement T
Variable is package private only so that tests run.


precmp

GroupElement[][] precmp
Precomputed table for scalarMultiply(byte[]), filled if necessary.

Variable is package private only so that tests run.


dblPrecmp

GroupElement[] dblPrecmp
Precomputed table for doubleScalarMultiplyVariableTime(GroupElement, byte[], byte[]), filled if necessary.

Variable is package private only so that tests run.

Constructor Detail

GroupElement

public GroupElement(Curve curve,
                    GroupElement.Representation repr,
                    FieldElement X,
                    FieldElement Y,
                    FieldElement Z,
                    FieldElement T)
Creates a group element for a curve.

Parameters:
curve - The curve.
repr - The representation used to represent the group element.
X - The X coordinate.
Y - The Y coordinate.
Z - The Z coordinate.
T - The T coordinate.

GroupElement

public GroupElement(Curve curve,
                    byte[] s)
Creates a group element for a curve from a given encoded point.

A point (x,y) is encoded by storing y in bit 0 to bit 254 and the sign of x in bit 255. x is recovered in the following way:

Method Detail

p2

public static GroupElement p2(Curve curve,
                              FieldElement X,
                              FieldElement Y,
                              FieldElement Z)
Creates a new group element in P2 representation.

Parameters:
curve - The curve.
X - The X coordinate.
Y - The Y coordinate.
Z - The Z coordinate.
Returns:
The group element in P2 representation.

p3

public static GroupElement p3(Curve curve,
                              FieldElement X,
                              FieldElement Y,
                              FieldElement Z,
                              FieldElement T)
Creates a new group element in P3 representation.

Parameters:
curve - The curve.
X - The X coordinate.
Y - The Y coordinate.
Z - The Z coordinate.
T - The T coordinate.
Returns:
The group element in P3 representation.

p1p1

public static GroupElement p1p1(Curve curve,
                                FieldElement X,
                                FieldElement Y,
                                FieldElement Z,
                                FieldElement T)
Creates a new group element in P1P1 representation.

Parameters:
curve - The curve.
X - The X coordinate.
Y - The Y coordinate.
Z - The Z coordinate.
T - The T coordinate.
Returns:
The group element in P1P1 representation.

precomp

public static GroupElement precomp(Curve curve,
                                   FieldElement ypx,
                                   FieldElement ymx,
                                   FieldElement xy2d)
Creates a new group element in PRECOMP representation.

Parameters:
curve - The curve.
ypx - The y + x value.
ymx - The y - x value.
xy2d - The 2 * d * x * y value.
Returns:
The group element in PRECOMP representation.

cached

public static GroupElement cached(Curve curve,
                                  FieldElement YpX,
                                  FieldElement YmX,
                                  FieldElement Z,
                                  FieldElement T2d)
Creates a new group element in CACHED representation.

Parameters:
curve - The curve.
YpX - The Y + X value.
YmX - The Y - X value.
Z - The Z coordinate.
T2d - The 2 * d * T value.
Returns:
The group element in CACHED representation.

getCurve

public Curve getCurve()
Gets the curve of the group element.

Returns:
The curve.

getRepresentation

public GroupElement.Representation getRepresentation()
Gets the representation of the group element.

Returns:
The representation.

getX

public FieldElement getX()
Gets the X value of the group element. This is for most representation the projective X coordinate.

Returns:
The X value.

getY

public FieldElement getY()
Gets the Y value of the group element. This is for most representation the projective Y coordinate.

Returns:
The Y value.

getZ

public FieldElement getZ()
Gets the Z value of the group element. This is for most representation the projective Z coordinate.

Returns:
The Z value.

getT

public FieldElement getT()
Gets the T value of the group element. This is for most representation the projective T coordinate.

Returns:
The T value.

toByteArray

public byte[] toByteArray()
Converts the group element to an encoded point on the curve.

Returns:
The encoded point as byte array.

toP2

public GroupElement toP2()
Converts the group element to the P2 representation.

Returns:
The group element in the P2 representation.

toP3

public GroupElement toP3()
Converts the group element to the P3 representation.

Returns:
The group element in the P3 representation.

toCached

public GroupElement toCached()
Converts the group element to the CACHED representation.

Returns:
The group element in the CACHED representation.

precompute

public void precompute(boolean precomputeSingle)
Precomputes several tables.

The precomputed tables are used for scalarMultiply(byte[]) and doubleScalarMultiplyVariableTime(GroupElement, byte[], byte[]).

Parameters:
precomputeSingle - should the matrix for scalarMultiply() be precomputed?

dbl

public GroupElement dbl()
Doubles a given group element p in P^2 or P^3 representation and returns the result in P x P representation. r = 2 * p where p = (X : Y : Z) or p = (X : Y : Z : T)

r in P x P representation:

r = ((X' : Z'), (Y' : T')) where

r converted from P x P to P^2 representation:

r = (X'' : Y'' : Z'') where

Formula for the P^2 representation is in agreement with the formula given in [4] page 12 (with a = -1) up to a common factor -1 which does not matter:

B = (X + Y)^2; C = X^2; D = Y^2; E = -C = -X^2; F := E + D = Y^2 - X^2; H = Z^2; J = F − 2 * H; X3 = (B − C − D) · J = X' * (-T'); Y3 = F · (E − D) = Z' * (-Y'); Z3 = F · J = Z' * (-T').

Returns:
The P1P1 representation

add

public GroupElement add(GroupElement q)
GroupElement addition using the twisted Edwards addition law with extended coordinates (Hisil2008).

this must be in P^3 representation and q in CACHED representation. r = p + q where p = this = (X1 : Y1 : Z1 : T1), q = (q.X, q.Y, q.Z, q.T) = (Y2 + X2, Y2 - X2, Z2, 2 * d * T2)

r in P x P representation:

Setting A = (Y1 - X1) * (Y2 - X2), B = (Y1 + X1) * (Y2 + X2), C = 2 * d * T1 * T2, D = 2 * Z1 * Z2 we get

Same result as in madd(net.i2p.crypto.eddsa.math.GroupElement) (up to a common factor which does not matter).

Parameters:
q - the CACHED representation of the GroupElement to add.
Returns:
the P1P1 representation of the result.

sub

public GroupElement sub(GroupElement q)
GroupElement subtraction using the twisted Edwards addition law with extended coordinates (Hisil2008).

r = p - q

Negating q means negating the value of the coordinate X2 and T2. The formula is in accordance to the above addition.

Parameters:
q - the PRECOMP representation of the GroupElement to subtract.
Returns:
the P1P1 representation of the result.

negate

public GroupElement negate()
Negates this group element by subtracting it from the neutral group element.

TODO-CR BR: why not simply negate the coordinates X and T?

Returns:
The negative of this group element.

hashCode

public int hashCode()
Overrides:
hashCode in class Object

equals

public boolean equals(Object obj)
Overrides:
equals in class Object

toRadix16

static byte[] toRadix16(byte[] a)
Convert a to radix 16.

Method is package private only so that tests run.

Parameters:
a - = a[0]+256*a[1]+...+256^31 a[31]
Returns:
64 bytes, each between -8 and 7

cmov

GroupElement cmov(GroupElement u,
                  int b)
Constant-time conditional move.

Replaces this with u if b == 1.
Replaces this with this if b == 0.

Method is package private only so that tests run.

Parameters:
u - The group element to return if b == 1.
b - in {0, 1}
Returns:
u if b == 1; this if b == 0; null otherwise.

select

GroupElement select(int pos,
                    int b)
Look up 16^i r_i B in the precomputed table.

No secret array indices, no secret branching. Constant time.

Must have previously precomputed.

Method is package private only so that tests run.

Parameters:
pos - = i/2 for i in {0, 2, 4,..., 62}
b - = r_i
Returns:
the GroupElement

scalarMultiply

public GroupElement scalarMultiply(byte[] a)
h = a * B where a = a[0]+256*a[1]+...+256^31 a[31] and B is this point. If its lookup table has not been precomputed, it will be at the start of the method (and cached for later calls). Constant time.

Preconditions: (TODO: Check this applies here) a[31] <= 127

Parameters:
a - = a[0]+256*a[1]+...+256^31 a[31]
Returns:
the GroupElement

slide

static byte[] slide(byte[] a)
Calculates a sliding-windows base 2 representation for a given value a. To learn more about it see [6] page 8.

Output: r which satisfies a = r0 * 2^0 + r1 * 2^1 + ... + r255 * 2^255 with ri in {-15, -13, -11, -9, -7, -5, -3, -1, 0, 1, 3, 5, 7, 9, 11, 13, 15}

Method is package private only so that tests run.

Parameters:
a - = a[0]+256*a[1]+...+256^31 a[31].
Returns:
The byte array r in the above described form.

doubleScalarMultiplyVariableTime

public GroupElement doubleScalarMultiplyVariableTime(GroupElement A,
                                                     byte[] a,
                                                     byte[] b)
r = a * A + b * B where a = a[0]+256*a[1]+...+256^31 a[31], b = b[0]+256*b[1]+...+256^31 b[31] and B is this point.

A must have been previously precomputed.

Parameters:
A - in P3 representation.
a - = a[0]+256*a[1]+...+256^31 a[31]
b - = b[0]+256*b[1]+...+256^31 b[31]
Returns:
the GroupElement

isOnCurve

public boolean isOnCurve()
Verify that a point is on its curve.

Returns:
true if the point lies on its curve.

isOnCurve

public boolean isOnCurve(Curve curve)
Verify that a point is on the curve.

Parameters:
curve - The curve to check.
Returns:
true if the point lies on the curve.

toString

public String toString()
Overrides:
toString in class Object