net.i2p.crypto.eddsa.math

Class GroupElement

java.lang.Object

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

Author:

str4d

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	GroupElement.Representation Available representations for a group element.

Constructor Summary

Constructors

Constructor and Description
GroupElement(Curve curve, byte[] s) Creates a group element for a curve from a given encoded point.
GroupElement(Curve curve, byte[] s, boolean precomputeSingleAndDouble) 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, without any pre-computation.
GroupElement(Curve curve, GroupElement.Representation repr, FieldElement X, FieldElement Y, FieldElement Z, FieldElement T, boolean precomputeDouble) Creates a group element for a curve, with optional pre-computation.

Method Summary

Modifier and Type	Method and Description
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.
GroupElement	dbl() Doubles a given group element $p$ in $P^2$ or $P^3$ representation and returns the result in $P \times P$ representation.
GroupElement	doubleScalarMultiplyVariableTime(GroupElement A, byte[] a, byte[] b) $r = a * A + b * B$ where $a = a[0]+256*a[1]+\dots+256^{31} a[31]$, $b = b[0]+256*b[1]+\dots+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, without pre-computation.
static GroupElement	p3(Curve curve, FieldElement X, FieldElement Y, FieldElement Z, FieldElement T, boolean precomputeDoubleOnly) Creates a new group element in P3 representation, potentially with pre-computation.
static GroupElement	precomp(Curve curve, FieldElement ypx, FieldElement ymx, FieldElement xy2d) Creates a new group element in PRECOMP representation.
GroupElement	scalarMultiply(byte[] a) $h = a * B$ where $a = a[0]+256*a[1]+\dots+256^{31} a[31]$ and $B$ is this point.
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.
GroupElement	toP3PrecomputeDouble() Converts the group element to the P3 representation, with dblPrecmp populated.
String	toString()

Methods inherited from class java.lang.Object

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

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, without any pre-computation.

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,
                    GroupElement.Representation repr,
                    FieldElement X,
                    FieldElement Y,
                    FieldElement Z,
                    FieldElement T,
                    boolean precomputeDouble)

Creates a group element for a curve, with optional pre-computation.

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.

precomputeDouble - If true, populate dblPrecmp, else set to null.

GroupElement

public GroupElement(Curve curve,
                    byte[] s)

Creates a group element for a curve from a given encoded point. No pre-computation.

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:

• $x = sign(x) * \sqrt{(y^2 - 1) / (d * y^2 + 1)} = sign(x) * \sqrt{u / v}$ with $u = y^2 - 1$ and $v = d * y^2 + 1$.
• Setting $β = (u * v^3) * (u * v^7)^{((q - 5) / 8)}$ one has $β^2 = \pm(u / v)$.
• If $v * β = -u$ multiply $β$ with $i=\sqrt{-1}$.
• Set $x := β$.
• If $sign(x) \ne$ bit 255 of $s$ then negate $x$.

Parameters:

curve - The curve.

s - The encoded point.

GroupElement

public GroupElement(Curve curve,
                    byte[] s,
                    boolean precomputeSingleAndDouble)

Creates a group element for a curve from a given encoded point. With optional pre-computation.

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:

• $x = sign(x) * \sqrt{(y^2 - 1) / (d * y^2 + 1)} = sign(x) * \sqrt{u / v}$ with $u = y^2 - 1$ and $v = d * y^2 + 1$.
• Setting $β = (u * v^3) * (u * v^7)^{((q - 5) / 8)}$ one has $β^2 = \pm(u / v)$.
• If $v * β = -u$ multiply $β$ with $i=\sqrt{-1}$.
• Set $x := β$.
• If $sign(x) \ne$ bit 255 of $s$ then negate $x$.

Parameters:

curve - The curve.

s - The encoded point.

precomputeSingleAndDouble - If true, populate both precmp and dblPrecmp, else set both to null.

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, without pre-computation.

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.

p3

public static GroupElement p3(Curve curve,
                              FieldElement X,
                              FieldElement Y,
                              FieldElement Z,
                              FieldElement T,
                              boolean precomputeDoubleOnly)

Creates a new group element in P3 representation, potentially with pre-computation.

Parameters:

curve - The curve.

X - The $X$ coordinate.

Y - The $Y$ coordinate.

Z - The $Z$ coordinate.

T - The $T$ coordinate.

precomputeDoubleOnly - If true, populate dblPrecmp, else set to null.

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.

toP3PrecomputeDouble

public GroupElement toP3PrecomputeDouble()

Converts the group element to the P3 representation, with dblPrecmp populated.

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.

dbl

public GroupElement dbl()

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

$r$ in $P \times P$ representation:

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

• $X' = (X + Y)^2 - (Y^2 + X^2)$
• $Y' = Y^2 + X^2$
• $Z' = y^2 - X^2$
• $T' = 2 * Z^2 - (y^2 - X^2)$

$r$ converted from $P \times P$ to $P^2$ representation:

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

• $X'' = X' * Z' = ((X + Y)^2 - Y^2 - X^2) * (2 * Z^2 - (y^2 - X^2))$
• $Y'' = Y' * T' = (Y^2 + X^2) * (2 * Z^2 - (y^2 - X^2))$
• $Z'' = Z' * T' = (y^2 - X^2) * (2 * Z^2 - (y^2 - X^2))$

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 \times P$ representation:

• $X' = (Y1 + X1) * (Y2 + X2) - (Y1 - X1) * (Y2 - X2)$
• $Y' = (Y1 + X1) * (Y2 + X2) + (Y1 - X1) * (Y2 - X2)$
• $Z' = 2 * Z1 * Z2 + 2 * d * T1 * T2$
• $T' = 2 * Z1 * T2 - 2 * d * T1 * T2$

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

• $X' = (B - A)$
• $Y' = (B + A)$
• $Z' = (D + C)$
• $T' = (D - C)$

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

scalarMultiply

public GroupElement scalarMultiply(byte[] a)

$h = a * B$ where $a = a[0]+256*a[1]+\dots+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] \le 127$

Parameters:

a - $= a[0]+256*a[1]+\dots+256^{31} a[31]$

Returns:

the GroupElement

doubleScalarMultiplyVariableTime

public GroupElement doubleScalarMultiplyVariableTime(GroupElement A,
                                                     byte[] a,
                                                     byte[] b)

$r = a * A + b * B$ where $a = a[0]+256*a[1]+\dots+256^{31} a[31]$, $b = b[0]+256*b[1]+\dots+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]+\dots+256^{31} a[31]$

b - $= b[0]+256*b[1]+\dots+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