Class 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
    • 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.
        Since:
        0.9.36
      • 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:

        • 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 = +-(u / v).
        • If v * = -u multiply with i=sqrt(-1).
        • Set x := .
        • If sign(x) != 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 = +-(u / v).
        • If v * β = -u multiply β with i=sqrt(-1).
        • Set x := β.
        • If sign(x) != 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 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.
      • 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

        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.
        Since:
        0.9.36
      • 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 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

        • 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 x 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 x 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
      • 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; Results undefined if b is not in {0, 1}.
      • 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.