Commit 332fbb4b02

@@ -102,6 +102,14 @@ pub const Curve25519 = struct {
     }
 
     /// Compute the Curve25519 equivalent to an Edwards25519 point.
+    ///
+    /// Note that the function doesn't check that the input point is
+    /// on the prime order group, e.g. that it is an Ed25519 public key
+    /// for which an Ed25519 secret key exists.
+    ///
+    /// If this is required, for example for compatibility with libsodium's strict
+    /// validation policy, the caller can call the `rejectUnexpectedSubgroup` function
+    /// on the input point before calling this function.
     pub fn fromEdwards25519(p: crypto.ecc.Edwards25519) IdentityElementError!Curve25519 {
         try p.clearCofactor().rejectIdentity();
         const one = crypto.ecc.Edwards25519.Fe.one;

@@ -9,6 +9,7 @@ const IdentityElementError = crypto.errors.IdentityElementError;
 const NonCanonicalError = crypto.errors.NonCanonicalError;
 const NotSquareError = crypto.errors.NotSquareError;
 const WeakPublicKeyError = crypto.errors.WeakPublicKeyError;
+const UnexpectedSubgroupError = crypto.errors.UnexpectedSubgroupError;
 
 /// Group operations over Edwards25519.
 pub const Edwards25519 = struct {
@@ -78,6 +79,46 @@ pub const Edwards25519 = struct {
         }
     }
 
+    /// Reject a point if it is not in the prime order subgroup generated by the standard base point.
+    ///
+    /// If the point is not in the main subgroup:
+    ///
+    /// - `WeakPublicKeyError` is returned if the point belongs to a low-order subgroup.
+    /// - `UnexpectedSubgroupError` is returned otherwise.
+    pub fn rejectUnexpectedSubgroup(p: Edwards25519) (WeakPublicKeyError || UnexpectedSubgroupError)!void {
+        try p.rejectLowOrder();
+
+        // Multiply p by the order of subgroup - This is a prime order group, so the result should be the neutral element.
+        const _10 = p.dbl();
+        const _11 = p.add(_10);
+        const _100 = p.add(_11);
+        const _110 = _10.add(_100);
+        const _1000 = _10.add(_110);
+        const _1011 = _11.add(_1000);
+        const _10000 = _1000.dbl();
+        const _100000 = _10000.dbl();
+        const _100110 = _110.add(_100000);
+        const _1000000 = _100000.dbl();
+        const _1010000 = _10000.add(_1000000);
+        const _1010011 = _11.add(_1010000);
+        const _1100011 = _10000.add(_1010011);
+        const _1100111 = _100.add(_1100011);
+        const _1101011 = _100.add(_1100111);
+        const _10010011 = _1000000.add(_1010011);
+        const _10010111 = _100.add(_10010011);
+        const _10111101 = _100110.add(_10010111);
+        const _11010011 = _1000000.add(_10010011);
+        const _11100111 = _1010000.add(_10010111);
+        const _11101101 = _110.add(_11100111);
+        const _11110101 = _1000.add(_11101101);
+        const q = ((_11110101.add(((((_1101011.add(((((_10.add(((_1011.add(_11110101)).shift(126)
+            .add(_1010011)).shift(9).add(_11110101))).shift(7).add(_1100111)).shift(9).add(_11110101).shift(11)
+            .add(_10111101)).shift(8).add(_11100111)).shift(9))).shift(6).add(_1011)).shift(14).add(_10010011).shift(10)
+            .add(_1100011)).shift(9).add(_10010111)).shift(10))).shift(8).add(_11010011)).shift(8).add(_11101101);
+        q.rejectIdentity() catch return;
+        return error.UnexpectedSubgroup;
+    }
+
     /// Multiply a point by the cofactor
     pub fn clearCofactor(p: Edwards25519) Edwards25519 {
         return p.dbl().dbl().dbl();
@@ -142,6 +183,13 @@ pub const Edwards25519 = struct {
         return p.add(q.neg());
     }
 
+    /// Double a point `n` times.
+    fn shift(p: Edwards25519, n: comptime_int) Edwards25519 {
+        var q = p;
+        for (0..n) |_| q = q.dbl();
+        return q;
+    }
+
     inline fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void {
         p.x.cMov(a.x, c);
         p.y.cMov(a.y, c);
@@ -575,3 +623,16 @@ test "implicit reduction of invalid scalars" {
     try htest.assertEqual("339f189ecc5fbebe9895345c72dc07bda6e615f8a40e768441b6f529cd6c671a", p1.toBytes()[0..]);
     try htest.assertEqual("a501e4c595a3686d8bee7058c7e6af7fd237f945c47546910e37e0e79b1bafb0", p3.toBytes()[0..]);
 }
+
+test "subgroup check" {
+    for (0..100) |_| {
+        var p = Edwards25519.basePoint;
+        const s = Edwards25519.scalar.random();
+        p = try p.mulPublic(s);
+        try p.rejectUnexpectedSubgroup();
+    }
+    var bogus: [Edwards25519.encoded_length]u8 = undefined;
+    _ = try std.fmt.hexToBytes(&bogus, "4dc95e3c28d78c48a60531525e6327e259b7ba0d2f5c81b694052c766a14b625");
+    const p = try Edwards25519.fromBytes(bogus);
+    try std.testing.expectError(error.UnexpectedSubgroup, p.rejectUnexpectedSubgroup());
+}

@@ -31,5 +31,8 @@ pub const WeakParametersError = error{WeakParameters};
 /// Public key would be insecure to use
 pub const WeakPublicKeyError = error{WeakPublicKey};
 
+/// Point is not in the prime order group
+pub const UnexpectedSubgroupError = error{UnexpectedSubgroup};
+
 /// Any error related to cryptography operations
-pub const Error = AuthenticationError || OutputTooLongError || IdentityElementError || EncodingError || SignatureVerificationError || KeyMismatchError || NonCanonicalError || NotSquareError || PasswordVerificationError || WeakParametersError || WeakPublicKeyError;
+pub const Error = AuthenticationError || OutputTooLongError || IdentityElementError || EncodingError || SignatureVerificationError || KeyMismatchError || NonCanonicalError || NotSquareError || PasswordVerificationError || WeakParametersError || WeakPublicKeyError || UnexpectedSubgroupError;