public class GroupElement extends Object implements 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
Modifier and Type | Class and Description |
---|---|
static class |
GroupElement.Representation
Available representations for a group element.
|
Modifier and Type | Field and Description |
---|---|
(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 and Description |
---|
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.
|
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.
|
(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() |
final Curve curve
final GroupElement.Representation repr
final FieldElement X
final FieldElement Y
final FieldElement Z
final FieldElement T
GroupElement[][] precmp
scalarMultiply(byte[])
,
filled if necessary.
Variable is package private only so that tests run.
GroupElement[] dblPrecmp
doubleScalarMultiplyVariableTime(GroupElement, byte[], byte[])
,
filled if necessary.
Variable is package private only so that tests run.
public GroupElement(Curve curve, GroupElement.Representation repr, FieldElement X, FieldElement Y, FieldElement Z, FieldElement T)
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.public GroupElement(Curve curve, byte[] s)
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:
curve
- The curve.s
- The encoded point.public static GroupElement p2(Curve curve, FieldElement X, FieldElement Y, FieldElement Z)
curve
- The curve.X
- The X coordinate.Y
- The Y coordinate.Z
- The Z coordinate.public static GroupElement p3(Curve curve, FieldElement X, FieldElement Y, FieldElement Z, FieldElement T)
curve
- The curve.X
- The X coordinate.Y
- The Y coordinate.Z
- The Z coordinate.T
- The T coordinate.public static GroupElement p1p1(Curve curve, FieldElement X, FieldElement Y, FieldElement Z, FieldElement T)
curve
- The curve.X
- The X coordinate.Y
- The Y coordinate.Z
- The Z coordinate.T
- The T coordinate.public static GroupElement precomp(Curve curve, FieldElement ypx, FieldElement ymx, FieldElement xy2d)
curve
- The curve.ypx
- The y + x value.ymx
- The y - x value.xy2d
- The 2 * d * x * y value.public static GroupElement cached(Curve curve, FieldElement YpX, FieldElement YmX, FieldElement Z, FieldElement T2d)
curve
- The curve.YpX
- The Y + X value.YmX
- The Y - X value.Z
- The Z coordinate.T2d
- The 2 * d * T value.public Curve getCurve()
public GroupElement.Representation getRepresentation()
public FieldElement getX()
public FieldElement getY()
public FieldElement getZ()
public FieldElement getT()
public byte[] toByteArray()
public GroupElement toP2()
public GroupElement toP3()
public GroupElement toCached()
public void precompute(boolean precomputeSingle)
The precomputed tables are used for scalarMultiply(byte[])
and doubleScalarMultiplyVariableTime(GroupElement, byte[], byte[])
.
precomputeSingle
- should the matrix for scalarMultiply() be precomputed?public GroupElement dbl()
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').
public GroupElement add(GroupElement q)
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).
q
- the CACHED representation of the GroupElement to add.public GroupElement sub(GroupElement q)
r = p - q
Negating q means negating the value of the coordinate X2 and T2.
The formula is in accordance to the above addition
.
q
- the PRECOMP representation of the GroupElement to subtract.public GroupElement negate()
TODO-CR BR: why not simply negate the coordinates X and T?
static byte[] toRadix16(byte[] a)
Method is package private only so that tests run.
a
- = a[0]+256*a[1]+...+256^31 a[31]GroupElement cmov(GroupElement u, int b)
Replaces this with u if b == 1.
Replaces this with this if b == 0.
Method is package private only so that tests run.
u
- The group element to return if b == 1.b
- in {0, 1}GroupElement select(int pos, int b)
No secret array indices, no secret branching. Constant time.
Must have previously precomputed.
Method is package private only so that tests run.
pos
- = i/2 for i in {0, 2, 4,..., 62}b
- = r_ipublic GroupElement scalarMultiply(byte[] a)
Preconditions: (TODO: Check this applies here) a[31] <= 127
a
- = a[0]+256*a[1]+...+256^31 a[31]static byte[] slide(byte[] a)
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.
a
- = a[0]+256*a[1]+...+256^31 a[31].public GroupElement doubleScalarMultiplyVariableTime(GroupElement A, byte[] a, byte[] b)
A must have been previously precomputed.
A
- in P3 representation.a
- = a[0]+256*a[1]+...+256^31 a[31]b
- = b[0]+256*b[1]+...+256^31 b[31]public boolean isOnCurve()
public boolean isOnCurve(Curve curve)
curve
- The curve to check.