| package org.mariadb.jdbc.plugin.authentication.standard.ed25519.math; |
| |
| import java.io.Serializable; |
| import java.util.Arrays; |
| import org.mariadb.jdbc.plugin.authentication.standard.ed25519.Utils; |
| |
| /** |
| * A point $(x,y)$ on an EdDSA curve. |
| * |
| * <p>Reviewed/commented by Bloody Rookie (nemproject@gmx.de) |
| * |
| * <p>Literature:<br> |
| * [1] Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe and Bo-Yin Yang : High-speed |
| * high-security signatures<br> |
| * [2] Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson: Twisted Edwards Curves Revisited |
| * <br> |
| * [3] Daniel J. Bernsteina, Tanja Lange: A complete set of addition laws for incomplete Edwards |
| * curves<br> |
| * [4] Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters: Twisted |
| * Edwards Curves<br> |
| * [5] Christiane Pascale Peters: Curves, Codes, and Cryptography (PhD thesis)<br> |
| * [6] Daniel J. Bernstein, Peter Birkner, Tanja Lange and Christiane Peters: Optimizing double-base |
| * elliptic-curve single-scalar multiplication<br> |
| * |
| * @author str4d |
| */ |
| public class GroupElement implements Serializable { |
| private static final long serialVersionUID = 2395879087349587L; |
| |
| /** |
| * Available representations for a group element. |
| * |
| * <ul> |
| * <li>P2: Projective representation $(X:Y:Z)$ satisfying $x=X/Z, y=Y/Z$. |
| * <li>P3: Extended projective representation $(X:Y:Z:T)$ satisfying $x=X/Z, y=Y/Z, XY=ZT$. |
| * <li>P3PrecomputedDouble: P3 but with dblPrecmp populated. |
| * <li>P1P1: Completed representation $((X:Z), (Y:T))$ satisfying $x=X/Z, y=Y/T$. |
| * <li>PRECOMP: Precomputed representation $(y+x, y-x, 2dxy)$. |
| * <li>CACHED: Cached representation $(Y+X, Y-X, Z, 2dT)$ |
| * </ul> |
| */ |
| public enum Representation { |
| /** Projective ($P^2$): $(X:Y:Z)$ satisfying $x=X/Z, y=Y/Z$ */ |
| P2, |
| /** Extended ($P^3$): $(X:Y:Z:T)$ satisfying $x=X/Z, y=Y/Z, XY=ZT$ */ |
| P3, |
| /** Can only be requested. Results in P3 representation but also populates dblPrecmp. */ |
| P3PrecomputedDouble, |
| /** Completed ($P \times P$): $((X:Z),(Y:T))$ satisfying $x=X/Z, y=Y/T$ */ |
| P1P1, |
| /** Precomputed (Duif): $(y+x,y-x,2dxy)$ */ |
| PRECOMP, |
| /** Cached: $(Y+X,Y-X,Z,2dT)$ */ |
| CACHED |
| } |
| |
| /** |
| * Creates a new group element in P2 representation. |
| * |
| * @param curve The curve. |
| * @param X The $X$ coordinate. |
| * @param Y The $Y$ coordinate. |
| * @param Z The $Z$ coordinate. |
| * @return The group element in P2 representation. |
| */ |
| public static GroupElement p2( |
| final Curve curve, final FieldElement X, final FieldElement Y, final FieldElement Z) { |
| return new GroupElement(curve, Representation.P2, X, Y, Z, null); |
| } |
| |
| /** |
| * Creates a new group element in P3 representation, without pre-computation. |
| * |
| * @param curve The curve. |
| * @param X The $X$ coordinate. |
| * @param Y The $Y$ coordinate. |
| * @param Z The $Z$ coordinate. |
| * @param T The $T$ coordinate. |
| * @return The group element in P3 representation. |
| */ |
| public static GroupElement p3( |
| final Curve curve, |
| final FieldElement X, |
| final FieldElement Y, |
| final FieldElement Z, |
| final FieldElement T) { |
| return p3(curve, X, Y, Z, T, false); |
| } |
| |
| /** |
| * Creates a new group element in P3 representation, potentially with pre-computation. |
| * |
| * @param curve The curve. |
| * @param X The $X$ coordinate. |
| * @param Y The $Y$ coordinate. |
| * @param Z The $Z$ coordinate. |
| * @param T The $T$ coordinate. |
| * @param precomputeDoubleOnly If true, populate dblPrecmp, else set to null. |
| * @return The group element in P3 representation. |
| */ |
| public static GroupElement p3( |
| final Curve curve, |
| final FieldElement X, |
| final FieldElement Y, |
| final FieldElement Z, |
| final FieldElement T, |
| final boolean precomputeDoubleOnly) { |
| return new GroupElement(curve, Representation.P3, X, Y, Z, T, precomputeDoubleOnly); |
| } |
| |
| /** |
| * Creates a new group element in P1P1 representation. |
| * |
| * @param curve The curve. |
| * @param X The $X$ coordinate. |
| * @param Y The $Y$ coordinate. |
| * @param Z The $Z$ coordinate. |
| * @param T The $T$ coordinate. |
| * @return The group element in P1P1 representation. |
| */ |
| public static GroupElement p1p1( |
| final Curve curve, |
| final FieldElement X, |
| final FieldElement Y, |
| final FieldElement Z, |
| final FieldElement T) { |
| return new GroupElement(curve, Representation.P1P1, X, Y, Z, T); |
| } |
| |
| /** |
| * Creates a new group element in PRECOMP representation. |
| * |
| * @param curve The curve. |
| * @param ypx The $y + x$ value. |
| * @param ymx The $y - x$ value. |
| * @param xy2d The $2 * d * x * y$ value. |
| * @return The group element in PRECOMP representation. |
| */ |
| public static GroupElement precomp( |
| final Curve curve, final FieldElement ypx, final FieldElement ymx, final FieldElement xy2d) { |
| return new GroupElement(curve, Representation.PRECOMP, ypx, ymx, xy2d, null); |
| } |
| |
| /** |
| * Creates a new group element in CACHED representation. |
| * |
| * @param curve The curve. |
| * @param YpX The $Y + X$ value. |
| * @param YmX The $Y - X$ value. |
| * @param Z The $Z$ coordinate. |
| * @param T2d The $2 * d * T$ value. |
| * @return The group element in CACHED representation. |
| */ |
| public static GroupElement cached( |
| final Curve curve, |
| final FieldElement YpX, |
| final FieldElement YmX, |
| final FieldElement Z, |
| final FieldElement T2d) { |
| return new GroupElement(curve, Representation.CACHED, YpX, YmX, Z, T2d); |
| } |
| |
| /** Variable is package private only so that tests run. */ |
| final Curve curve; |
| |
| /** Variable is package private only so that tests run. */ |
| final Representation repr; |
| |
| /** Variable is package private only so that tests run. */ |
| final FieldElement X; |
| |
| /** Variable is package private only so that tests run. */ |
| final FieldElement Y; |
| |
| /** Variable is package private only so that tests run. */ |
| final FieldElement Z; |
| |
| /** Variable is package private only so that tests run. */ |
| final FieldElement T; |
| |
| /** |
| * Precomputed table for {@link #scalarMultiply(byte[])}, filled if necessary. |
| * |
| * <p>Variable is package private only so that tests run. |
| */ |
| final GroupElement[][] precmp; |
| |
| /** |
| * Precomputed table for , filled if necessary. |
| * |
| * <p>Variable is package private only so that tests run. |
| */ |
| final GroupElement[] dblPrecmp; |
| |
| /** |
| * Creates a group element for a curve, without any pre-computation. |
| * |
| * @param curve The curve. |
| * @param repr The representation used to represent the group element. |
| * @param X The $X$ coordinate. |
| * @param Y The $Y$ coordinate. |
| * @param Z The $Z$ coordinate. |
| * @param T The $T$ coordinate. |
| */ |
| public GroupElement( |
| final Curve curve, |
| final Representation repr, |
| final FieldElement X, |
| final FieldElement Y, |
| final FieldElement Z, |
| final FieldElement T) { |
| this(curve, repr, X, Y, Z, T, false); |
| } |
| |
| /** |
| * Creates a group element for a curve, with optional pre-computation. |
| * |
| * @param curve The curve. |
| * @param repr The representation used to represent the group element. |
| * @param X The $X$ coordinate. |
| * @param Y The $Y$ coordinate. |
| * @param Z The $Z$ coordinate. |
| * @param T The $T$ coordinate. |
| * @param precomputeDouble If true, populate dblPrecmp, else set to null. |
| */ |
| public GroupElement( |
| final Curve curve, |
| final Representation repr, |
| final FieldElement X, |
| final FieldElement Y, |
| final FieldElement Z, |
| final FieldElement T, |
| final boolean precomputeDouble) { |
| this.curve = curve; |
| this.repr = repr; |
| this.X = X; |
| this.Y = Y; |
| this.Z = Z; |
| this.T = T; |
| this.precmp = null; |
| this.dblPrecmp = precomputeDouble ? precomputeDouble() : null; |
| } |
| |
| /** |
| * Creates a group element for a curve from a given encoded point. No pre-computation. |
| * |
| * <p>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: |
| * |
| * <ul> |
| * <li>$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$. |
| * <li>Setting $β = (u * v^3) * (u * v^7)^{((q - 5) / 8)}$ one has $β^2 = \pm(u / v)$. |
| * <li>If $v * β = -u$ multiply $β$ with $i=\sqrt{-1}$. |
| * <li>Set $x := β$. |
| * <li>If $sign(x) \ne$ bit 255 of $s$ then negate $x$. |
| * </ul> |
| * |
| * @param curve The curve. |
| * @param s The encoded point. |
| */ |
| public GroupElement(final Curve curve, final byte[] s) { |
| this(curve, s, false); |
| } |
| |
| /** |
| * Creates a group element for a curve from a given encoded point. With optional pre-computation. |
| * |
| * <p>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: |
| * |
| * <ul> |
| * <li>$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$. |
| * <li>Setting $β = (u * v^3) * (u * v^7)^{((q - 5) / 8)}$ one has $β^2 = \pm(u / v)$. |
| * <li>If $v * β = -u$ multiply $β$ with $i=\sqrt{-1}$. |
| * <li>Set $x := β$. |
| * <li>If $sign(x) \ne$ bit 255 of $s$ then negate $x$. |
| * </ul> |
| * |
| * @param curve The curve. |
| * @param s The encoded point. |
| * @param precomputeSingleAndDouble If true, populate both precmp and dblPrecmp, else set both to |
| * null. |
| */ |
| public GroupElement(final Curve curve, final byte[] s, boolean precomputeSingleAndDouble) { |
| FieldElement x, y, yy, u, v, v3, vxx, check; |
| y = curve.getField().fromByteArray(s); |
| yy = y.square(); |
| |
| // u = y^2-1 |
| u = yy.subtractOne(); |
| |
| // v = dy^2+1 |
| v = yy.multiply(curve.getD()).addOne(); |
| |
| // v3 = v^3 |
| v3 = v.square().multiply(v); |
| |
| // x = (v3^2)vu, aka x = uv^7 |
| x = v3.square().multiply(v).multiply(u); |
| |
| // x = (uv^7)^((q-5)/8) |
| x = x.pow22523(); |
| |
| // x = uv^3(uv^7)^((q-5)/8) |
| x = v3.multiply(u).multiply(x); |
| |
| vxx = x.square().multiply(v); |
| check = vxx.subtract(u); // vx^2-u |
| if (check.isNonZero()) { |
| check = vxx.add(u); // vx^2+u |
| |
| if (check.isNonZero()) throw new IllegalArgumentException("not a valid GroupElement"); |
| x = x.multiply(curve.getI()); |
| } |
| |
| if ((x.isNegative() ? 1 : 0) != Utils.bit(s, curve.getField().getb() - 1)) { |
| x = x.negate(); |
| } |
| |
| this.curve = curve; |
| this.repr = Representation.P3; |
| this.X = x; |
| this.Y = y; |
| this.Z = curve.getField().ONE; |
| this.T = this.X.multiply(this.Y); |
| if (precomputeSingleAndDouble) { |
| precmp = precomputeSingle(); |
| dblPrecmp = precomputeDouble(); |
| } else { |
| precmp = null; |
| dblPrecmp = null; |
| } |
| } |
| |
| /** |
| * Gets the representation of the group element. |
| * |
| * @return The representation. |
| */ |
| public Representation getRepresentation() { |
| return this.repr; |
| } |
| |
| /** |
| * Converts the group element to an encoded point on the curve. |
| * |
| * @return The encoded point as byte array. |
| */ |
| public byte[] toByteArray() { |
| switch (this.repr) { |
| case P2: |
| case P3: |
| FieldElement recip = Z.invert(); |
| FieldElement x = X.multiply(recip); |
| FieldElement y = Y.multiply(recip); |
| byte[] s = y.toByteArray(); |
| s[s.length - 1] |= (x.isNegative() ? (byte) 0x80 : 0); |
| return s; |
| default: |
| return toP2().toByteArray(); |
| } |
| } |
| |
| /** |
| * Converts the group element to the P2 representation. |
| * |
| * @return The group element in the P2 representation. |
| */ |
| public GroupElement toP2() { |
| return toRep(Representation.P2); |
| } |
| |
| /** |
| * Converts the group element to the P3 representation. |
| * |
| * @return The group element in the P3 representation. |
| */ |
| public GroupElement toP3() { |
| return toRep(Representation.P3); |
| } |
| |
| /** |
| * Converts the group element to the P3 representation, with dblPrecmp populated. |
| * |
| * @return The group element in the P3 representation. |
| */ |
| public GroupElement toP3PrecomputeDouble() { |
| return toRep(Representation.P3PrecomputedDouble); |
| } |
| |
| /** |
| * Converts the group element to the CACHED representation. |
| * |
| * @return The group element in the CACHED representation. |
| */ |
| public GroupElement toCached() { |
| return toRep(Representation.CACHED); |
| } |
| |
| /** |
| * Convert a GroupElement from one Representation to another. TODO-CR: Add additional conversion? |
| * $r = p$ |
| * |
| * <p>Supported conversions: |
| * |
| * <p> |
| * |
| * <ul> |
| * <li>P3 $\rightarrow$ P2 |
| * <li>P3 $\rightarrow$ CACHED (1 multiply, 1 add, 1 subtract) |
| * <li>P1P1 $\rightarrow$ P2 (3 multiply) |
| * <li>P1P1 $\rightarrow$ P3 (4 multiply) |
| * |
| * @param repr The representation to convert to. |
| * @return A new group element in the given representation. |
| */ |
| private GroupElement toRep(final Representation repr) { |
| switch (this.repr) { |
| case P2: |
| if (repr == Representation.P2) { |
| return p2(this.curve, this.X, this.Y, this.Z); |
| } |
| throw new IllegalArgumentException(); |
| case P3: |
| switch (repr) { |
| case P2: |
| return p2(this.curve, this.X, this.Y, this.Z); |
| case P3: |
| return p3(this.curve, this.X, this.Y, this.Z, this.T); |
| case CACHED: |
| return cached( |
| this.curve, |
| this.Y.add(this.X), |
| this.Y.subtract(this.X), |
| this.Z, |
| this.T.multiply(this.curve.get2D())); |
| default: |
| throw new IllegalArgumentException(); |
| } |
| case P1P1: |
| switch (repr) { |
| case P2: |
| return p2( |
| this.curve, this.X.multiply(this.T), Y.multiply(this.Z), this.Z.multiply(this.T)); |
| case P3: |
| return p3( |
| this.curve, |
| this.X.multiply(this.T), |
| Y.multiply(this.Z), |
| this.Z.multiply(this.T), |
| this.X.multiply(this.Y), |
| false); |
| case P3PrecomputedDouble: |
| return p3( |
| this.curve, |
| this.X.multiply(this.T), |
| Y.multiply(this.Z), |
| this.Z.multiply(this.T), |
| this.X.multiply(this.Y), |
| true); |
| case P1P1: |
| return p1p1(this.curve, this.X, this.Y, this.Z, this.T); |
| default: |
| throw new IllegalArgumentException(); |
| } |
| case PRECOMP: |
| if (repr == Representation.PRECOMP) { |
| return precomp(this.curve, this.X, this.Y, this.Z); |
| } |
| throw new IllegalArgumentException(); |
| case CACHED: |
| if (repr == Representation.CACHED) { |
| return cached(this.curve, this.X, this.Y, this.Z, this.T); |
| } |
| throw new IllegalArgumentException(); |
| default: |
| throw new UnsupportedOperationException(); |
| } |
| } |
| |
| /** Precomputes table for {@link #scalarMultiply(byte[])}. */ |
| private GroupElement[][] precomputeSingle() { |
| // Precomputation for single scalar multiplication. |
| GroupElement[][] precmp = new GroupElement[32][8]; |
| // TODO-CR BR: check that this == base point when the method is called. |
| GroupElement Bi = this; |
| for (int i = 0; i < 32; i++) { |
| GroupElement Bij = Bi; |
| for (int j = 0; j < 8; j++) { |
| final FieldElement recip = Bij.Z.invert(); |
| final FieldElement x = Bij.X.multiply(recip); |
| final FieldElement y = Bij.Y.multiply(recip); |
| precmp[i][j] = |
| precomp( |
| this.curve, y.add(x), y.subtract(x), x.multiply(y).multiply(this.curve.get2D())); |
| Bij = Bij.add(Bi.toCached()).toP3(); |
| } |
| // Only every second summand is precomputed (16^2 = 256) |
| for (int k = 0; k < 8; k++) { |
| Bi = Bi.add(Bi.toCached()).toP3(); |
| } |
| } |
| return precmp; |
| } |
| |
| /** Precomputes table for . */ |
| private GroupElement[] precomputeDouble() { |
| // Precomputation for double scalar multiplication. |
| // P,3P,5P,7P,9P,11P,13P,15P |
| GroupElement[] dblPrecmp = new GroupElement[8]; |
| GroupElement Bi = this; |
| for (int i = 0; i < 8; i++) { |
| final FieldElement recip = Bi.Z.invert(); |
| final FieldElement x = Bi.X.multiply(recip); |
| final FieldElement y = Bi.Y.multiply(recip); |
| dblPrecmp[i] = |
| precomp(this.curve, y.add(x), y.subtract(x), x.multiply(y).multiply(this.curve.get2D())); |
| // Bi = edwards(B,edwards(B,Bi)) |
| Bi = this.add(this.add(Bi.toCached()).toP3().toCached()).toP3(); |
| } |
| return dblPrecmp; |
| } |
| |
| /** |
| * 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)$ |
| * |
| * <p>$r$ in $P \times P$ representation: |
| * |
| * <p>$r = ((X' : Z'), (Y' : T'))$ where |
| * |
| * <ul> |
| * <li>$X' = (X + Y)^2 - (Y^2 + X^2)$ |
| * <li>$Y' = Y^2 + X^2$ |
| * <li>$Z' = y^2 - X^2$ |
| * <li>$T' = 2 * Z^2 - (y^2 - X^2)$ |
| * </ul> |
| * |
| * <p>$r$ converted from $P \times P$ to $P^2$ representation: |
| * |
| * <p>$r = (X'' : Y'' : Z'')$ where |
| * |
| * <ul> |
| * <li>$X'' = X' * Z' = ((X + Y)^2 - Y^2 - X^2) * (2 * Z^2 - (y^2 - X^2))$ |
| * <li>$Y'' = Y' * T' = (Y^2 + X^2) * (2 * Z^2 - (y^2 - X^2))$ |
| * <li>$Z'' = Z' * T' = (y^2 - X^2) * (2 * Z^2 - (y^2 - X^2))$ |
| * </ul> |
| * |
| * <p>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: |
| * |
| * <p>$$ 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'). $$ |
| * |
| * @return The P1P1 representation |
| */ |
| public GroupElement dbl() { |
| switch (this.repr) { |
| case P2: |
| case P3: // Ignore T for P3 representation |
| FieldElement XX, YY, B, A, AA, Yn, Zn; |
| XX = this.X.square(); |
| YY = this.Y.square(); |
| B = this.Z.squareAndDouble(); |
| A = this.X.add(this.Y); |
| AA = A.square(); |
| Yn = YY.add(XX); |
| Zn = YY.subtract(XX); |
| return p1p1(this.curve, AA.subtract(Yn), Yn, Zn, B.subtract(Zn)); |
| default: |
| throw new UnsupportedOperationException(); |
| } |
| } |
| |
| /** |
| * GroupElement addition using the twisted Edwards addition law with extended coordinates |
| * (Hisil2008). |
| * |
| * <p>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)$ |
| * |
| * <p>$r$ in $P \times P$ representation: |
| * |
| * <p>$r = ((X' : Z'), (Y' : T'))$ where |
| * |
| * <p> |
| * |
| * <ul> |
| * <li>$X' = (Y1 + X1) * q.X - (Y1 - X1) * q.Y = ((Y1 + X1) * (Y2 + X2) - (Y1 - X1) * (Y2 - X2)) |
| * * 1/Z2$ |
| * <li>$Y' = (Y1 + X1) * q.X + (Y1 - X1) * q.Y = ((Y1 + X1) * (Y2 + X2) + (Y1 - X1) * (Y2 - X2)) |
| * * 1/Z2$ |
| * <li>$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$ |
| * <li>$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$ |
| * </ul> |
| * |
| * <p>Setting $A = (Y1 - X1) * (Y2 - X2), B = (Y1 + X1) * (Y2 + X2), C = 2 * d * T1 * T2, D = 2 * |
| * Z1 * Z2$ we get |
| * |
| * <p> |
| * |
| * <ul> |
| * <li>$X' = (B - A) * 1/Z2$ |
| * <li>$Y' = (B + A) * 1/Z2$ |
| * <li>$Z' = (D + C) * 1/Z2$ |
| * <li>$T' = (D - C) * 1/Z2$ |
| * </ul> |
| * |
| * <p>$r$ converted from $P \times P$ to $P^2$ representation: |
| * |
| * <p>$r = (X'' : Y'' : Z'' : T'')$ where |
| * |
| * <p> |
| * |
| * <ul> |
| * <li>$X'' = X' * Z' = (B - A) * (D + C) * 1/Z2^2$ |
| * <li>$Y'' = Y' * T' = (B + A) * (D - C) * 1/Z2^2$ |
| * <li>$Z'' = Z' * T' = (D + C) * (D - C) * 1/Z2^2$ |
| * <li>$T'' = X' * Y' = (B - A) * (B + A) * 1/Z2^2$ |
| * </ul> |
| * |
| * <p>TODO-CR BR: Formula for the $P^2$ representation is not in agreement with the formula given |
| * in [2] page 6<br> |
| * TODO-CR BR: (the common factor $1/Z2^2$ does not matter):<br> |
| * $$ E = B - A, F = D - C, G = D + C, H = B + A \\ X3 = E * F = (B - A) * (D - C); \\ Y3 = G * H |
| * = (D + C) * (B + A); \\ Z3 = F * G = (D - C) * (D + C); \\ T3 = E * H = (B - A) * (B + A); $$ |
| * |
| * @param q the PRECOMP representation of the GroupElement to add. |
| * @return the P1P1 representation of the result. |
| */ |
| private GroupElement madd(GroupElement q) { |
| if (this.repr != Representation.P3) throw new UnsupportedOperationException(); |
| if (q.repr != Representation.PRECOMP) throw new IllegalArgumentException(); |
| |
| FieldElement YpX, YmX, A, B, C, D; |
| YpX = this.Y.add(this.X); |
| YmX = this.Y.subtract(this.X); |
| A = YpX.multiply(q.X); // q->y+x |
| B = YmX.multiply(q.Y); // q->y-x |
| C = q.Z.multiply(this.T); // q->2dxy |
| D = this.Z.add(this.Z); |
| return p1p1(this.curve, A.subtract(B), A.add(B), D.add(C), D.subtract(C)); |
| } |
| |
| /** |
| * GroupElement subtraction using the twisted Edwards addition law with extended coordinates |
| * (Hisil2008). |
| * |
| * <p>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)$ |
| * |
| * <p>Negating $q$ means negating the value of $X2$ and $T2$ (the latter is irrelevant here). The |
| * formula is in accordance to {@link #madd the above addition}. |
| * |
| * @param q the PRECOMP representation of the GroupElement to subtract. |
| * @return the P1P1 representation of the result. |
| */ |
| private GroupElement msub(GroupElement q) { |
| if (this.repr != Representation.P3) throw new UnsupportedOperationException(); |
| if (q.repr != Representation.PRECOMP) throw new IllegalArgumentException(); |
| |
| FieldElement YpX, YmX, A, B, C, D; |
| YpX = this.Y.add(this.X); |
| YmX = this.Y.subtract(this.X); |
| A = YpX.multiply(q.Y); // q->y-x |
| B = YmX.multiply(q.X); // q->y+x |
| C = q.Z.multiply(this.T); // q->2dxy |
| D = this.Z.add(this.Z); |
| return p1p1(this.curve, A.subtract(B), A.add(B), D.subtract(C), D.add(C)); |
| } |
| |
| /** |
| * GroupElement addition using the twisted Edwards addition law with extended coordinates |
| * (Hisil2008). |
| * |
| * <p>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)$ |
| * |
| * <p>$r$ in $P \times P$ representation: |
| * |
| * <ul> |
| * <li>$X' = (Y1 + X1) * (Y2 + X2) - (Y1 - X1) * (Y2 - X2)$ |
| * <li>$Y' = (Y1 + X1) * (Y2 + X2) + (Y1 - X1) * (Y2 - X2)$ |
| * <li>$Z' = 2 * Z1 * Z2 + 2 * d * T1 * T2$ |
| * <li>$T' = 2 * Z1 * T2 - 2 * d * T1 * T2$ |
| * </ul> |
| * |
| * <p>Setting $A = (Y1 - X1) * (Y2 - X2), B = (Y1 + X1) * (Y2 + X2), C = 2 * d * T1 * T2, D = 2 * |
| * Z1 * Z2$ we get |
| * |
| * <ul> |
| * <li>$X' = (B - A)$ |
| * <li>$Y' = (B + A)$ |
| * <li>$Z' = (D + C)$ |
| * <li>$T' = (D - C)$ |
| * </ul> |
| * |
| * <p>Same result as in {@link #madd} (up to a common factor which does not matter). |
| * |
| * @param q the CACHED representation of the GroupElement to add. |
| * @return the P1P1 representation of the result. |
| */ |
| public GroupElement add(GroupElement q) { |
| if (this.repr != Representation.P3) throw new UnsupportedOperationException(); |
| if (q.repr != Representation.CACHED) throw new IllegalArgumentException(); |
| |
| FieldElement YpX, YmX, A, B, C, ZZ, D; |
| YpX = this.Y.add(this.X); |
| YmX = this.Y.subtract(this.X); |
| A = YpX.multiply(q.X); // q->Y+X |
| B = YmX.multiply(q.Y); // q->Y-X |
| C = q.T.multiply(this.T); // q->2dT |
| ZZ = this.Z.multiply(q.Z); |
| D = ZZ.add(ZZ); |
| return p1p1(this.curve, A.subtract(B), A.add(B), D.add(C), D.subtract(C)); |
| } |
| |
| /** |
| * GroupElement subtraction using the twisted Edwards addition law with extended coordinates |
| * (Hisil2008). |
| * |
| * <p>$r = p - q$ |
| * |
| * <p>Negating $q$ means negating the value of the coordinate $X2$ and $T2$. The formula is in |
| * accordance to {@link #add the above addition}. |
| * |
| * @param q the PRECOMP representation of the GroupElement to subtract. |
| * @return the P1P1 representation of the result. |
| */ |
| public GroupElement sub(GroupElement q) { |
| if (this.repr != Representation.P3) throw new UnsupportedOperationException(); |
| if (q.repr != Representation.CACHED) throw new IllegalArgumentException(); |
| |
| FieldElement YpX, YmX, A, B, C, ZZ, D; |
| YpX = Y.add(X); |
| YmX = Y.subtract(X); |
| A = YpX.multiply(q.Y); // q->Y-X |
| B = YmX.multiply(q.X); // q->Y+X |
| C = q.T.multiply(T); // q->2dT |
| ZZ = Z.multiply(q.Z); |
| D = ZZ.add(ZZ); |
| return p1p1(curve, A.subtract(B), A.add(B), D.subtract(C), D.add(C)); |
| } |
| |
| /** |
| * Negates this group element by subtracting it from the neutral group element. |
| * |
| * <p>TODO-CR BR: why not simply negate the coordinates $X$ and $T$? |
| * |
| * @return The negative of this group element. |
| */ |
| public GroupElement negate() { |
| if (this.repr != Representation.P3) throw new UnsupportedOperationException(); |
| return this.curve.getZero(Representation.P3).sub(toCached()).toP3PrecomputeDouble(); |
| } |
| |
| @Override |
| public int hashCode() { |
| return Arrays.hashCode(this.toByteArray()); |
| } |
| |
| @Override |
| public boolean equals(Object obj) { |
| if (obj == this) return true; |
| if (!(obj instanceof GroupElement)) return false; |
| GroupElement ge = (GroupElement) obj; |
| if (!this.repr.equals(ge.repr)) { |
| try { |
| ge = ge.toRep(this.repr); |
| } catch (RuntimeException e) { |
| return false; |
| } |
| } |
| switch (this.repr) { |
| case P2: |
| case P3: |
| // Try easy way first |
| if (this.Z.equals(ge.Z)) return this.X.equals(ge.X) && this.Y.equals(ge.Y); |
| // X1/Z1 = X2/Z2 --> X1*Z2 = X2*Z1 |
| final FieldElement x1 = this.X.multiply(ge.Z); |
| final FieldElement y1 = this.Y.multiply(ge.Z); |
| final FieldElement x2 = ge.X.multiply(this.Z); |
| final FieldElement y2 = ge.Y.multiply(this.Z); |
| return x1.equals(x2) && y1.equals(y2); |
| case P1P1: |
| return toP2().equals(ge); |
| case PRECOMP: |
| // Compare directly, PRECOMP is derived directly from x and y |
| return this.X.equals(ge.X) && this.Y.equals(ge.Y) && this.Z.equals(ge.Z); |
| case CACHED: |
| // Try easy way first |
| if (this.Z.equals(ge.Z)) |
| return this.X.equals(ge.X) && this.Y.equals(ge.Y) && this.T.equals(ge.T); |
| // (Y+X)/Z = y+x etc. |
| final FieldElement x3 = this.X.multiply(ge.Z); |
| final FieldElement y3 = this.Y.multiply(ge.Z); |
| final FieldElement t3 = this.T.multiply(ge.Z); |
| final FieldElement x4 = ge.X.multiply(this.Z); |
| final FieldElement y4 = ge.Y.multiply(this.Z); |
| final FieldElement t4 = ge.T.multiply(this.Z); |
| return x3.equals(x4) && y3.equals(y4) && t3.equals(t4); |
| default: |
| return false; |
| } |
| } |
| |
| /** |
| * Convert a to radix 16. |
| * |
| * <p>Method is package private only so that tests run. |
| * |
| * @param a $= a[0]+256*a[1]+...+256^{31} a[31]$ |
| * @return 64 bytes, each between -8 and 7 |
| */ |
| static byte[] toRadix16(final byte[] a) { |
| final byte[] e = new byte[64]; |
| int i; |
| // Radix 16 notation |
| for (i = 0; i < 32; i++) { |
| e[2 * i] = (byte) (a[i] & 15); |
| e[2 * i + 1] = (byte) ((a[i] >> 4) & 15); |
| } |
| /* each e[i] is between 0 and 15 */ |
| /* e[63] is between 0 and 7 */ |
| int carry = 0; |
| for (i = 0; i < 63; i++) { |
| e[i] += carry; |
| carry = e[i] + 8; |
| carry >>= 4; |
| e[i] -= carry << 4; |
| } |
| e[63] += carry; |
| /* each e[i] is between -8 and 7 */ |
| return e; |
| } |
| |
| /** |
| * Constant-time conditional move. |
| * |
| * <p>Replaces this with $u$ if $b == 1$.<br> |
| * Replaces this with this if $b == 0$. |
| * |
| * <p>Method is package private only so that tests run. |
| * |
| * @param u The group element to return if $b == 1$. |
| * @param b in $\{0, 1\}$ |
| * @return $u$ if $b == 1$; this if $b == 0$. Results undefined if $b$ is not in $\{0, 1\}$. |
| */ |
| GroupElement cmov(final GroupElement u, final int b) { |
| return precomp(curve, X.cmov(u.X, b), Y.cmov(u.Y, b), Z.cmov(u.Z, b)); |
| } |
| |
| /** |
| * Look up $16^i r_i B$ in the precomputed table. |
| * |
| * <p>No secret array indices, no secret branching. Constant time. |
| * |
| * <p>Must have previously precomputed. |
| * |
| * <p>Method is package private only so that tests run. |
| * |
| * @param pos $= i/2$ for $i$ in $\{0, 2, 4,..., 62\}$ |
| * @param b $= r_i$ |
| * @return the GroupElement |
| */ |
| GroupElement select(final int pos, final int b) { |
| // Is r_i negative? |
| final int bnegative = Utils.negative(b); |
| // |r_i| |
| final int babs = b - (((-bnegative) & b) << 1); |
| |
| // 16^i |r_i| B |
| final GroupElement t = |
| this.curve |
| .getZero(Representation.PRECOMP) |
| .cmov(this.precmp[pos][0], Utils.equal(babs, 1)) |
| .cmov(this.precmp[pos][1], Utils.equal(babs, 2)) |
| .cmov(this.precmp[pos][2], Utils.equal(babs, 3)) |
| .cmov(this.precmp[pos][3], Utils.equal(babs, 4)) |
| .cmov(this.precmp[pos][4], Utils.equal(babs, 5)) |
| .cmov(this.precmp[pos][5], Utils.equal(babs, 6)) |
| .cmov(this.precmp[pos][6], Utils.equal(babs, 7)) |
| .cmov(this.precmp[pos][7], Utils.equal(babs, 8)); |
| // -16^i |r_i| B |
| final GroupElement tminus = precomp(curve, t.Y, t.X, t.Z.negate()); |
| // 16^i r_i B |
| return t.cmov(tminus, bnegative); |
| } |
| |
| /** |
| * $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. |
| * |
| * <p>Preconditions: (TODO: Check this applies here) $a[31] \le 127$ |
| * |
| * @param a $= a[0]+256*a[1]+\dots+256^{31} a[31]$ |
| * @return the GroupElement |
| */ |
| public GroupElement scalarMultiply(final byte[] a) { |
| GroupElement t; |
| int i; |
| |
| final byte[] e = toRadix16(a); |
| |
| GroupElement h = this.curve.getZero(Representation.P3); |
| for (i = 1; i < 64; i += 2) { |
| t = select(i / 2, e[i]); |
| h = h.madd(t).toP3(); |
| } |
| |
| h = h.dbl().toP2().dbl().toP2().dbl().toP2().dbl().toP3(); |
| |
| for (i = 0; i < 64; i += 2) { |
| t = select(i / 2, e[i]); |
| h = h.madd(t).toP3(); |
| } |
| |
| return h; |
| } |
| |
| /** |
| * Calculates a sliding-windows base 2 representation for a given value $a$. To learn more about |
| * it see [6] page 8. |
| * |
| * <p>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\}$ |
| * |
| * <p>Method is package private only so that tests run. |
| * |
| * @param a $= a[0]+256*a[1]+\dots+256^{31} a[31]$. |
| * @return The byte array $r$ in the above described form. |
| */ |
| static byte[] slide(final byte[] a) { |
| byte[] r = new byte[256]; |
| |
| // Put each bit of 'a' into a separate byte, 0 or 1 |
| for (int i = 0; i < 256; ++i) { |
| r[i] = (byte) (1 & (a[i >> 3] >> (i & 7))); |
| } |
| |
| // Note: r[i] will always be odd. |
| for (int i = 0; i < 256; ++i) { |
| if (r[i] != 0) { |
| for (int b = 1; b <= 6 && i + b < 256; ++b) { |
| // Accumulate bits if possible |
| if (r[i + b] != 0) { |
| if (r[i] + (r[i + b] << b) <= 15) { |
| r[i] += r[i + b] << b; |
| r[i + b] = 0; |
| } else if (r[i] - (r[i + b] << b) >= -15) { |
| r[i] -= r[i + b] << b; |
| for (int k = i + b; k < 256; ++k) { |
| if (r[k] == 0) { |
| r[k] = 1; |
| break; |
| } |
| r[k] = 0; |
| } |
| } else break; |
| } |
| } |
| } |
| } |
| |
| return r; |
| } |
| |
| /** |
| * Verify that a point is on the curve. |
| * |
| * @param curve The curve to check. |
| * @return true if the point lies on the curve. |
| */ |
| public boolean isOnCurve(Curve curve) { |
| switch (repr) { |
| case P2: |
| case P3: |
| FieldElement recip = Z.invert(); |
| FieldElement x = X.multiply(recip); |
| FieldElement y = Y.multiply(recip); |
| FieldElement xx = x.square(); |
| FieldElement yy = y.square(); |
| FieldElement dxxyy = curve.getD().multiply(xx).multiply(yy); |
| return curve.getField().ONE.add(dxxyy).add(xx).equals(yy); |
| |
| default: |
| return toP2().isOnCurve(curve); |
| } |
| } |
| |
| @Override |
| public String toString() { |
| return "[GroupElement\nX=" + X + "\nY=" + Y + "\nZ=" + Z + "\nT=" + T + "\n]"; |
| } |
| } |
