Fixing issue https://github.com/google/tink/issues/224. (#268)
Problem was: isOnCurve did not reduce the limbs before checking for equality.
PiperOrigin-RevId: 272245293
diff --git a/java/src/main/java/com/google/crypto/tink/subtle/Ed25519.java b/java/src/main/java/com/google/crypto/tink/subtle/Ed25519.java
index 0cf1530..a290320 100644
--- a/java/src/main/java/com/google/crypto/tink/subtle/Ed25519.java
+++ b/java/src/main/java/com/google/crypto/tink/subtle/Ed25519.java
@@ -145,6 +145,9 @@
Field25519.mult(rhs, rhs, D);
// rhs = z^4 + D * x^2 * y^2
Field25519.sum(rhs, z4);
+ // Field25519.mult reduces its output, but Field25519.sub does not, so we have to manually
+ // reduce it here.
+ Field25519.reduce(rhs, rhs);
// z^2 (y^2 - x^2) == z^4 + D * x^2 * y^2
return Bytes.equal(Field25519.contract(lhs), Field25519.contract(rhs));
}
diff --git a/java/src/main/java/com/google/crypto/tink/subtle/Field25519.java b/java/src/main/java/com/google/crypto/tink/subtle/Field25519.java
index 1795008..5a24d60 100644
--- a/java/src/main/java/com/google/crypto/tink/subtle/Field25519.java
+++ b/java/src/main/java/com/google/crypto/tink/subtle/Field25519.java
@@ -213,6 +213,27 @@
}
/**
+ * Reduce a field element by calling reduceSizeByModularReduction and reduceCoefficients.
+ *
+ * @param input An input array of any length. If the array has 19 elements, it will be used as
+ * temporary buffer and its contents changed.
+ * @param output An output array of size LIMB_CNT. After the call |output[i]| < 2^26 will hold.
+ *
+ */
+ static void reduce(long[] input, long[] output) {
+ long[] tmp;
+ if (input.length == 19) {
+ tmp = input;
+ } else {
+ tmp = new long[19];
+ System.arraycopy(input, 0, tmp, 0, input.length);
+ }
+ reduceSizeByModularReduction(tmp);
+ reduceCoefficients(tmp);
+ System.arraycopy(tmp, 0, output, 0, LIMB_CNT);
+ }
+
+ /**
* Reduce a long form to a reduced-size form by taking the input mod 2^255 - 19.
*
* On entry: |output[i]| < 14*2^54
@@ -306,11 +327,8 @@
static void mult(long[] output, long[] in, long[] in2) {
long[] t = new long[19];
product(t, in, in2);
- // |t[i]| < 14*2^54
- reduceSizeByModularReduction(t);
- reduceCoefficients(t);
// |t[i]| < 2^26
- System.arraycopy(t, 0, output, 0, LIMB_CNT);
+ reduce(t, output);
}
/**
@@ -363,10 +381,7 @@
squareInner(t, in);
// |t[i]| < 14*2^54 because the largest product of two limbs will be < 2^(27+27) and SquareInner
// adds together, at most, 14 of those products.
- reduceSizeByModularReduction(t);
- reduceCoefficients(t);
- // |t[i]| < 2^26
- System.arraycopy(t, 0, output, 0, LIMB_CNT);
+ reduce(t, output);
}
/**
diff --git a/java/src/test/java/com/google/crypto/tink/subtle/Ed25519Test.java b/java/src/test/java/com/google/crypto/tink/subtle/Ed25519Test.java
index b8d83b6..e8f7393 100644
--- a/java/src/test/java/com/google/crypto/tink/subtle/Ed25519Test.java
+++ b/java/src/test/java/com/google/crypto/tink/subtle/Ed25519Test.java
@@ -55,4 +55,11 @@
assertArrayEquals(originalPublicKey, publicKey);
}
}
+
+ /** Test for https://github.com/google/tink/issues/224. */
+ @Test
+ public void testScalarMultWithBase() throws Exception {
+ byte[] scalar = Hex.decode("521784c403e6fb32d48e0da85969a82f5952856bde4471a42b3fa56fd8b96c0d");
+ Ed25519.scalarMultWithBaseToBytes(scalar);
+ }
}
