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

  Represents a point on an EdDSA curve with support for multiple coordinate representations. Provides operations for point addition, doubling, and scalar multiplication.
  See Also:
    Serialized Form

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `static class` | `GroupElement.Representation` Available coordinate representations for a group element.

  - ### Field Summary

    Fields
    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 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

    All Methods Static Methods Instance Methods Concrete Methods
    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 \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.
    `(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.
    `GroupElement` | `toP3PrecomputeDouble()` Converts the group element to the P3 representation, with dblPrecmp populated.
    `(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.

    - #### dblPrecmp

          final GroupElement[] dblPrecmp

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

      Variable is package private only so that tests run.

    - #### precmp

          final GroupElement[][] precmp

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

      Variable is package private only so that tests run.

    - #### repr

          final GroupElement.Representation repr

      Variable is package private only so that tests run.

    - #### T

          final FieldElement T

      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.

  - ### Constructor Detail

    - #### 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.

    - #### 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.

  - ### Method Detail

    - #### 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.

    - #### 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.

    - #### 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\}$.

    - #### 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

    - #### 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

    - #### equals

          public boolean equals(Object obj)

      Overrides:
        `equals` in class `Object`

    - #### 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.

    - #### 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.

    - #### 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.

    - #### hashCode

          public int hashCode()

      Overrides:
        `hashCode` in class `Object`

    - #### 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.

    - #### 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.

    - #### 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.

    - #### 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.

    - #### 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.

    - #### 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

    - #### 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

    - #### 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.

    - #### 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.

    - #### toByteArray

          public byte[] toByteArray()

      Converts the group element to an encoded point on the curve.
      Returns:
        The encoded point as byte array.

    - #### toCached

          public GroupElement toCached()

      Converts the group element to the CACHED representation.
      Returns:
        The group element in the CACHED representation.

    - #### 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.

    - #### 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

    - #### toString

          public String toString()

      Overrides:
        `toString` in class `Object`