java.lang.Object
net.i2p.crypto.eddsa.math.GroupElement
All Implemented Interfaces:
Serializable
public class GroupElementextends 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:

  • Field Details

  • 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 twisted Edwards curve the point lies on.
      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 twisted Edwards curve the point lies on.
      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 twisted Edwards curve the point lies on.
      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 twisted Edwards curve the point lies on.
      s - The encoded point.
      precomputeSingleAndDouble - If true, populate both precmp and dblPrecmp, else set both to null.

  • Method Details

    • p2

      public static GroupElement p2(Curve curve, FieldElement x, FieldElement y, FieldElement z)
      Creates a new group element in P2 representation.
      Parameters:
      curve - The twisted Edwards curve the point lies on
      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 twisted Edwards curve the point lies on.
      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 twisted Edwards curve the point lies on.
      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 twisted Edwards curve the point lies on.
      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 twisted Edwards curve the point lies on.
      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 twisted Edwards curve the point lies on.
      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()
      The curve of the group element.
      Returns:
      the twisted Edwards curve this point is an element of

    • getRepresentation

      public GroupElement.Representation getRepresentation()
      The representation of the group element.
      Returns:
      the projective representation this point is currently held in

    • getX

      public FieldElement getX()
      The $X$ value of the group element. This is for most representation the projective $X$ coordinate.
      Returns:
      The $X$ value.

    • getY

      public FieldElement getY()
      The $Y$ value of the group element. This is for most representation the projective $Y$ coordinate.
      Returns:
      The $Y$ value.

    • getZ

      public FieldElement getZ()
      The $Z$ value of the group element. This is for most representation the projective $Z$ coordinate.
      Returns:
      The $Z$ value.

    • getT

      public FieldElement getT()
      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.

    • toRep

      private GroupElement toRep(GroupElement.Representation repr)
      Convert a GroupElement from one Representation to another. $r = p$

      Supported conversions:

      • P3 $\rightarrow$ P2
      • P3 $\rightarrow$ CACHED (1 multiply, 1 add, 1 subtract)
      • P1P1 $\rightarrow$ P2 (3 multiply)
      • P1P1 $\rightarrow$ P3 (4 multiply).
      Parameters:
      repr - The representation to convert to.
      Returns:
      A new group element in the given representation.

    • precomputeSingle

      private GroupElement[][] precomputeSingle()
      Precomputes table for scalarMultiply(byte[]).
      Returns:
      the 32 by 8 table of precomputed multiples of this element

    • precomputeDouble

      private GroupElement[] precomputeDouble()
      Precomputes table for doubleScalarMultiplyVariableTime(GroupElement, byte[], byte[]).
      Returns:
      the 16-entry table of odd multiples (P through 31P) of this element

    • 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

    • madd

      GroupElement madd(GroupElement q)
      GroupElement addition using the twisted Edwards addition law with extended coordinates (Hisil2008).

      this must be in $P^3$ representation and $q$ in PRECOMP representation. $r = p + q$ where $p = this = (X1 : Y1 : Z1 : T1), q = (q.X, q.Y, q.Z) = (Y2/Z2 + X2/Z2, Y2/Z2 - X2/Z2, 2 * d * X2/Z2 * Y2/Z2)$

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

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

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

      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) * 1/Z2$
      • $Y' = (B + A) * 1/Z2$
      • $Z' = (D + C) * 1/Z2$
      • $T' = (D - C) * 1/Z2$

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

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

      • $X'' = X' * Z' = (B - A) * (D + C) * 1/Z2^2$
      • $Y'' = Y' * T' = (B + A) * (D - C) * 1/Z2^2$
      • $Z'' = Z' * T' = (D + C) * (D - C) * 1/Z2^2$
      • $T'' = X' * Y' = (B - A) * (B + A) * 1/Z2^2$.
      Parameters:
      q - the PRECOMP representation of the GroupElement to add.
      Returns:
      the P1P1 representation of the result.

    • msub

      private GroupElement msub(GroupElement q)
      GroupElement subtraction using the twisted Edwards addition law with extended coordinates (Hisil2008).

      this must be in $P^3$ representation and $q$ in PRECOMP representation. $r = p - q$ where $p = this = (X1 : Y1 : Z1 : T1), q = (q.X, q.Y, q.Z) = (Y2/Z2 + X2/Z2, Y2/Z2 - X2/Z2, 2 * d * X2/Z2 * Y2/Z2)$

      Negating $q$ means negating the value of $X2$ and $T2$ (the latter is irrelevant here). 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.

    • add

      public final 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(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.
      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

    • 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$, the signed lookup-table window, negative when the corresponding bit of the scalar is set
      Returns:
      $16^i r_i B$ in precomputed 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: $a[31] \le 127$.

      Parameters:
      a - $= a[0]+256*a[1]+\dots+256^{31} a[31]$
      Returns:
      $a * B$ as a group element

    • 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 $\{-31, -29, \dots, -1, 0, 1, \dots, 29, 31\}$

      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

      public GroupElement doubleScalarMultiplyVariableTime(GroupElement aPoint, 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:
      aPoint - 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:
      $a * A + b * B$, with $A$ aPoint and $B$ this point

    • 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