Class GroupElement
- All Implemented Interfaces:
Serializable
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:
-
Nested Class Summary
Modifier and TypeClassDescriptionstatic enum
Available representations for a group element. -
Field Summary
Modifier and TypeFieldDescription(package private) final Curve
Variable is package private only so that tests run.(package private) final GroupElement[]
Precomputed table fordoubleScalarMultiplyVariableTime(GroupElement, byte[], byte[])
, filled if necessary.(package private) final GroupElement[][]
Precomputed table forscalarMultiply(byte[])
, filled if necessary.(package private) final GroupElement.Representation
Variable is package private only so that tests run.(package private) final FieldElement
Variable is package private only so that tests run.(package private) final FieldElement
Variable is package private only so that tests run.(package private) final FieldElement
Variable is package private only so that tests run.(package private) final FieldElement
Variable is package private only so that tests run. -
Constructor Summary
ConstructorDescriptionGroupElement
(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 TypeMethodDescriptionadd
(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.dbl()
Doubles a given group element $p$ in $P^2$ or $P^3$ representation and returns the result in $P \times P$ representation.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
getCurve()
Gets the curve of the group element.Gets the representation of the group element.getT()
Gets the $T$ value of the group element.getX()
Gets the $X$ value of the group element.getY()
Gets the $Y$ value of the group element.getZ()
Gets the $Z$ value of the group element.int
hashCode()
boolean
Verify that a point is on its curve.boolean
Verify that a point is on the curve.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.scalarMultiply
(byte[] a) $h = a * B$ where $a = a[0]+256*a[1]+\dots+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$.sub
(GroupElement q) GroupElement subtraction using the twisted Edwards addition law with extended coordinates (Hisil2008).byte[]
Converts the group element to an encoded point on the curve.toCached()
Converts the group element to the CACHED representation.toP2()
Converts the group element to the P2 representation.toP3()
Converts the group element to the P3 representation.Converts the group element to the P3 representation, with dblPrecmp populated.(package private) static byte[]
toRadix16
(byte[] a) Convert a to radix 16.toString()
-
Field Details
-
curve
Variable is package private only so that tests run. -
repr
Variable is package private only so that tests run. -
X
Variable is package private only so that tests run. -
Y
Variable is package private only so that tests run. -
Z
Variable is package private only so that tests run. -
T
Variable is package private only so that tests run. -
precmp
Precomputed table forscalarMultiply(byte[])
, filled if necessary.Variable is package private only so that tests run.
-
dblPrecmp
Precomputed table fordoubleScalarMultiplyVariableTime(GroupElement, byte[], byte[])
, filled if necessary.Variable is package private only so that tests run.
-
-
Constructor Details
-
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.- Since:
- 0.9.36
-
GroupElement
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
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.- Since:
- 0.9.36
-
-
Method Details
-
p2
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.
- Since:
- 0.9.36
-
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
Gets the curve of the group element.- Returns:
- The curve.
-
getRepresentation
Gets the representation of the group element.- Returns:
- The representation.
-
getX
Gets the $X$ value of the group element. This is for most representation the projective $X$ coordinate.- Returns:
- The $X$ value.
-
getY
Gets the $Y$ value of the group element. This is for most representation the projective $Y$ coordinate.- Returns:
- The $Y$ value.
-
getZ
Gets the $Z$ value of the group element. This is for most representation the projective $Z$ coordinate.- Returns:
- The $Z$ value.
-
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
Converts the group element to the P2 representation.- Returns:
- The group element in the P2 representation.
-
toP3
Converts the group element to the P3 representation.- Returns:
- The group element in the P3 representation.
-
toP3PrecomputeDouble
Converts the group element to the P3 representation, with dblPrecmp populated.- Returns:
- The group element in the P3 representation.
- Since:
- 0.9.36
-
toCached
Converts the group element to the CACHED representation.- Returns:
- The group element in the CACHED representation.
-
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
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
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
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() -
equals
-
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
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$. Results undefined if $b$ is not in $\{0, 1\}$.
-
select
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
$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
-
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 + \dots + 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]+\dots+256^{31} a[31]$.- Returns:
- The byte array $r$ in the above described form.
-
doubleScalarMultiplyVariableTime
$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
Verify that a point is on the curve.- Parameters:
curve
- The curve to check.- Returns:
- true if the point lies on the curve.
-
toString
-