Commit 0d9c474ecf

@@ -4,7 +4,9 @@
 // The MIT license requires this copyright notice to be included in all copies
 // and substantial portions of the software.
 const std = @import("std");
+const debug = std.debug;
 const fmt = std.fmt;
+const mem = std.mem;
 
 /// Group operations over Edwards25519.
 pub const Edwards25519 = struct {
@@ -250,8 +252,150 @@ pub const Edwards25519 = struct {
         scalar.clamp(&t);
         return mul(p, t);
     }
+
+    // montgomery -- recover y = sqrt(x^3 + A*x^2 + x)
+    fn xmontToYmont(x: Fe) !Fe {
+        var x2 = x.sq();
+        const x3 = x.mul(x2);
+        x2 = x2.mul32(Fe.edwards25519a_32);
+        return x.add(x2).add(x3).sqrt();
+    }
+
+    // montgomery affine coordinates to edwards extended coordinates
+    fn montToEd(x: Fe, y: Fe) Edwards25519 {
+        const x_plus_one = x.add(Fe.one);
+        const x_minus_one = x.sub(Fe.one);
+        const x_plus_one_y_inv = x_plus_one.mul(y).invert(); // 1/((x+1)*y)
+
+        // xed = sqrt(-A-2)*x/y
+        const xed = x.mul(Fe.edwards25519sqrtam2).mul(x_plus_one_y_inv).mul(x_plus_one);
+
+        // yed = (x-1)/(x+1) or 1 if the denominator is 0
+        var yed = x_plus_one_y_inv.mul(y).mul(x_minus_one);
+        yed.cMov(Fe.one, @boolToInt(x_plus_one_y_inv.isZero()));
+
+        return Edwards25519{
+            .x = xed,
+            .y = yed,
+            .z = Fe.one,
+            .t = xed.mul(yed),
+        };
+    }
+
+    /// Elligator2 map - Returns Montgomery affine coordinates
+    pub fn elligator2(r: Fe) struct { x: Fe, y: Fe, not_square: bool } {
+        const rr2 = r.sq2().add(Fe.one).invert();
+        var x = rr2.mul32(Fe.edwards25519a_32).neg(); // x=x1
+        var x2 = x.sq();
+        const x3 = x2.mul(x);
+        x2 = x2.mul32(Fe.edwards25519a_32); // x2 = A*x1^2
+        const gx1 = x3.add(x).add(x2); // gx1 = x1^3 + A*x1^2 + x1
+        const not_square = !gx1.isSquare();
+
+        // gx1 not a square => x = -x1-A
+        x.cMov(x.neg(), @boolToInt(not_square));
+        x2 = Fe.zero;
+        x2.cMov(Fe.edwards25519a, @boolToInt(not_square));
+        x = x.sub(x2);
+
+        // We have y = sqrt(gx1) or sqrt(gx2) with gx2 = gx1*(A+x1)/(-x1)
+        // but it is about as fast to just recompute y from the curve equation.
+        const y = xmontToYmont(x) catch unreachable;
+        return .{ .x = x, .y = y, .not_square = not_square };
+    }
+
+    /// Map a 64-bit hash into an Edwards25519 point
+    pub fn fromHash(h: [64]u8) Edwards25519 {
+        const fe_f = Fe.fromBytes64(h);
+        var elr = elligator2(fe_f);
+
+        const y_sign = elr.not_square;
+        const y_neg = elr.y.neg();
+        elr.y.cMov(y_neg, @boolToInt(elr.y.isNegative()) ^ @boolToInt(y_sign));
+        return montToEd(elr.x, elr.y).clearCofactor();
+    }
+
+    fn stringToPoints(comptime n: usize, ctx: []const u8, s: []const u8) [n]Edwards25519 {
+        debug.assert(n <= 2);
+        const H = std.crypto.hash.sha2.Sha512;
+        const h_l: usize = 48;
+        var xctx = ctx;
+        var hctx: [H.digest_length]u8 = undefined;
+        if (ctx.len > 0xff) {
+            var st = H.init(.{});
+            st.update("H2C-OVERSIZE-DST-");
+            st.update(ctx);
+            st.final(&hctx);
+            xctx = hctx[0..];
+        }
+        const empty_block = [_]u8{0} ** H.block_length;
+        var t = [3]u8{ 0, n * h_l, 0 };
+        var xctx_len_u8 = [1]u8{@intCast(u8, xctx.len)};
+        var st = H.init(.{});
+        st.update(empty_block[0..]);
+        st.update(s);
+        st.update(t[0..]);
+        st.update(xctx);
+        st.update(xctx_len_u8[0..]);
+        var u_0: [H.digest_length]u8 = undefined;
+        st.final(&u_0);
+        var u: [n * H.digest_length]u8 = undefined;
+        var i: usize = 0;
+        while (i < n * H.digest_length) : (i += H.digest_length) {
+            mem.copy(u8, u[i..][0..H.digest_length], u_0[0..]);
+            var j: usize = 0;
+            while (i > 0 and j < H.digest_length) : (j += 1) {
+                u[i + j] ^= u[i + j - H.digest_length];
+            }
+            t[2] += 1;
+            st = H.init(.{});
+            st.update(u[i..][0..H.digest_length]);
+            st.update(t[2..3]);
+            st.update(xctx);
+            st.update(xctx_len_u8[0..]);
+            st.final(u[i..][0..H.digest_length]);
+        }
+        var px: [n]Edwards25519 = undefined;
+        i = 0;
+        while (i < n) : (i += 1) {
+            mem.set(u8, u_0[0 .. H.digest_length - h_l], 0);
+            mem.copy(u8, u_0[H.digest_length - h_l ..][0..h_l], u[i * h_l ..][0..h_l]);
+            px[i] = fromHash(u_0);
+        }
+        return px;
+    }
+
+    /// Hash a context `ctx` and a string `s` into an Edwards25519 point
+    ///
+    /// This function implements the edwards25519_XMD:SHA-512_ELL2_RO_ and edwards25519_XMD:SHA-512_ELL2_NU_
+    /// methods from the "Hashing to Elliptic Curves" standard document.
+    ///
+    /// Although not strictly required by the standard, it is recommended to avoid NUL characters in
+    /// the context in order to be compatible with other implementations.
+    pub fn fromString(comptime random_oracle: bool, ctx: []const u8, s: []const u8) Edwards25519 {
+        if (random_oracle) {
+            const px = stringToPoints(2, ctx, s);
+            return px[0].add(px[1]);
+        } else {
+            return stringToPoints(1, ctx, s)[0];
+        }
+    }
+
+    /// Map a 32 bit uniform bit string into an edwards25519 point
+    pub fn fromUniform(r: [32]u8) Edwards25519 {
+        var s = r;
+        const x_sign = s[31] >> 7;
+        s[31] &= 0x7f;
+        const elr = elligator2(Fe.fromBytes(s));
+        var p = montToEd(elr.x, elr.y);
+        const p_neg = p.neg();
+        p.cMov(p_neg, @boolToInt(p.x.isNegative()) ^ x_sign);
+        return p.clearCofactor();
+    }
 };
 
+const htest = @import("../test.zig");
+
 test "edwards25519 packing/unpacking" {
     const s = [_]u8{170} ++ [_]u8{0} ** 31;
     var b = Edwards25519.basePoint;
@@ -301,3 +445,22 @@ test "edwards25519 point addition/substraction" {
     std.testing.expectError(error.IdentityElement, p.sub(p).rejectIdentity());
     std.testing.expectError(error.IdentityElement, p.sub(q).add(q).sub(p).rejectIdentity());
 }
+
+test "edwards25519 uniform-to-point" {
+    var r = [32]u8{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 };
+    var p = Edwards25519.fromUniform(r);
+    htest.assertEqual("0691eee3cf70a0056df6bfa03120635636581b5c4ea571dfc680f78c7e0b4137", p.toBytes()[0..]);
+
+    r[31] = 0xff;
+    p = Edwards25519.fromUniform(r);
+    htest.assertEqual("f70718e68ef42d90ca1d936bb2d7e159be6c01d8095d39bd70487c82fe5c973a", p.toBytes()[0..]);
+}
+
+// Test vectors from draft-irtf-cfrg-hash-to-curve-10
+test "edwards25519 hash-to-curve operation" {
+    var p = Edwards25519.fromString(true, "QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_RO_", "abc");
+    htest.assertEqual("31558a26887f23fb8218f143e69d5f0af2e7831130bd5b432ef23883b895831a", p.toBytes()[0..]);
+
+    p = Edwards25519.fromString(false, "QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_NU_", "abc");
+    htest.assertEqual("42fa27c8f5a1ae0aa38bb59d5938e5145622ba5dedd11d11736fa2f9502d73e7", p.toBytes()[0..]);
+}

@@ -12,26 +12,46 @@ pub const Fe = struct {
 
     const MASK51: u64 = 0x7ffffffffffff;
 
+    /// 0
     pub const zero = Fe{ .limbs = .{ 0, 0, 0, 0, 0 } };
 
+    /// 1
     pub const one = Fe{ .limbs = .{ 1, 0, 0, 0, 0 } };
 
-    pub const sqrtm1 = Fe{ .limbs = .{ 1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133 } }; // sqrt(-1)
+    /// sqrt(-1)
+    pub const sqrtm1 = Fe{ .limbs = .{ 1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133 } };
 
+    /// The Curve25519 base point
     pub const curve25519BasePoint = Fe{ .limbs = .{ 9, 0, 0, 0, 0 } };
 
-    pub const edwards25519d = Fe{ .limbs = .{ 929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575 } }; // 37095705934669439343138083508754565189542113879843219016388785533085940283555
+    /// Edwards25519 d = 37095705934669439343138083508754565189542113879843219016388785533085940283555
+    pub const edwards25519d = Fe{ .limbs = .{ 929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575 } };
 
-    pub const edwards25519d2 = Fe{ .limbs = .{ 1859910466990425, 932731440258426, 1072319116312658, 1815898335770999, 633789495995903 } }; // 2d
+    /// Edwards25519 2d
+    pub const edwards25519d2 = Fe{ .limbs = .{ 1859910466990425, 932731440258426, 1072319116312658, 1815898335770999, 633789495995903 } };
 
-    pub const edwards25519sqrtamd = Fe{ .limbs = .{ 278908739862762, 821645201101625, 8113234426968, 1777959178193151, 2118520810568447 } }; // 1/sqrt(a-d)
+    /// Edwards25519 1/sqrt(a-d)
+    pub const edwards25519sqrtamd = Fe{ .limbs = .{ 278908739862762, 821645201101625, 8113234426968, 1777959178193151, 2118520810568447 } };
 
-    pub const edwards25519eonemsqd = Fe{ .limbs = .{ 1136626929484150, 1998550399581263, 496427632559748, 118527312129759, 45110755273534 } }; // 1-d^2
+    /// Edwards25519 1-d^2
+    pub const edwards25519eonemsqd = Fe{ .limbs = .{ 1136626929484150, 1998550399581263, 496427632559748, 118527312129759, 45110755273534 } };
 
-    pub const edwards25519sqdmone = Fe{ .limbs = .{ 1507062230895904, 1572317787530805, 683053064812840, 317374165784489, 1572899562415810 } }; // (d-1)^2
+    /// Edwards25519 (d-1)^2
+    pub const edwards25519sqdmone = Fe{ .limbs = .{ 1507062230895904, 1572317787530805, 683053064812840, 317374165784489, 1572899562415810 } };
 
+    /// Edwards25519 sqrt(ad-1) with a = -1 (mod p)
     pub const edwards25519sqrtadm1 = Fe{ .limbs = .{ 2241493124984347, 425987919032274, 2207028919301688, 1220490630685848, 974799131293748 } };
 
+    /// Edwards25519 A, as a single limb
+    pub const edwards25519a_32: u32 = 486662;
+
+    /// Edwards25519 A
+    pub const edwards25519a = Fe{ .limbs = .{ @as(u64, edwards25519a_32), 0, 0, 0, 0 } };
+
+    /// Edwards25519 sqrt(A-2)
+    pub const edwards25519sqrtam2 = Fe{ .limbs = .{ 1693982333959686, 608509411481997, 2235573344831311, 947681270984193, 266558006233600 } };
+
+    /// Return true if the field element is zero
     pub inline fn isZero(fe: Fe) bool {
         var reduced = fe;
         reduced.reduce();
@@ -39,10 +59,12 @@ pub const Fe = struct {
         return (limbs[0] | limbs[1] | limbs[2] | limbs[3] | limbs[4]) == 0;
     }
 
+    /// Return true if both field elements are equivalent
     pub inline fn equivalent(a: Fe, b: Fe) bool {
         return a.sub(b).isZero();
     }
 
+    /// Unpack a field element
     pub fn fromBytes(s: [32]u8) Fe {
         var fe: Fe = undefined;
         fe.limbs[0] = readIntLittle(u64, s[0..8]) & MASK51;
@@ -54,6 +76,7 @@ pub const Fe = struct {
         return fe;
     }
 
+    /// Pack a field element
     pub fn toBytes(fe: Fe) [32]u8 {
         var reduced = fe;
         reduced.reduce();
@@ -66,6 +89,29 @@ pub const Fe = struct {
         return s;
     }
 
+    /// Map a 64-bit big endian string into a field element
+    pub fn fromBytes64(s: [64]u8) Fe {
+        var fl: [32]u8 = undefined;
+        var gl: [32]u8 = undefined;
+        var i: usize = 0;
+        while (i < 32) : (i += 1) {
+            fl[i] = s[63 - i];
+            gl[i] = s[31 - i];
+        }
+        fl[31] &= 0x7f;
+        gl[31] &= 0x7f;
+        var fe_f = fromBytes(fl);
+        const fe_g = fromBytes(gl);
+        fe_f.limbs[0] += (s[32] >> 7) * 19;
+        i = 0;
+        while (i < 5) : (i += 1) {
+            fe_f.limbs[i] += 38 * fe_g.limbs[i];
+        }
+        fe_f.reduce();
+        return fe_f;
+    }
+
+    /// Reject non-canonical encodings of an element, possibly ignoring the top bit
     pub fn rejectNonCanonical(s: [32]u8, comptime ignore_extra_bit: bool) !void {
         var c: u16 = (s[31] & 0x7f) ^ 0x7f;
         comptime var i = 30;
@@ -80,6 +126,7 @@ pub const Fe = struct {
         }
     }
 
+    /// Reduce a field element mod 2^255-19
     fn reduce(fe: *Fe) void {
         comptime var i = 0;
         comptime var j = 0;
@@ -116,6 +163,7 @@ pub const Fe = struct {
         limbs[4] &= MASK51;
     }
 
+    /// Add a field element
     pub inline fn add(a: Fe, b: Fe) Fe {
         var fe: Fe = undefined;
         comptime var i = 0;
@@ -125,6 +173,7 @@ pub const Fe = struct {
         return fe;
     }
 
+    /// Substract a field elememnt
     pub inline fn sub(a: Fe, b: Fe) Fe {
         var fe = b;
         comptime var i = 0;
@@ -143,14 +192,17 @@ pub const Fe = struct {
         return fe;
     }
 
+    /// Negate a field element
     pub inline fn neg(a: Fe) Fe {
         return zero.sub(a);
     }
 
+    /// Return true if a field element is negative
     pub inline fn isNegative(a: Fe) bool {
         return (a.toBytes()[0] & 1) != 0;
     }
 
+    /// Conditonally replace a field element with `a` if `c` is positive
     pub inline fn cMov(fe: *Fe, a: Fe, c: u64) void {
         const mask: u64 = 0 -% c;
         var x = fe.*;
@@ -168,6 +220,7 @@ pub const Fe = struct {
         }
     }
 
+    /// Conditionally swap two pairs of field elements if `c` is positive
     pub fn cSwap2(a0: *Fe, b0: *Fe, a1: *Fe, b1: *Fe, c: u64) void {
         const mask: u64 = 0 -% c;
         var x0 = a0.*;
@@ -211,6 +264,7 @@ pub const Fe = struct {
         return .{ .limbs = rs };
     }
 
+    /// Multiply two field elements
     pub inline fn mul(a: Fe, b: Fe) Fe {
         var ax: [5]u128 = undefined;
         var bx: [5]u128 = undefined;
@@ -262,14 +316,17 @@ pub const Fe = struct {
         return _carry128(&r);
     }
 
+    /// Square a field element
     pub inline fn sq(a: Fe) Fe {
         return _sq(a, false);
     }
 
+    /// Square and double a field element
     pub inline fn sq2(a: Fe) Fe {
         return _sq(a, true);
     }
 
+    /// Multiply a field element with a small (32-bit) integer
     pub inline fn mul32(a: Fe, comptime n: u32) Fe {
         const sn = @intCast(u128, n);
         var fe: Fe = undefined;
@@ -284,6 +341,7 @@ pub const Fe = struct {
         return fe;
     }
 
+    /// Square a field element `n` times
     inline fn sqn(a: Fe, comptime n: comptime_int) Fe {
         var i: usize = 0;
         var fe = a;
@@ -293,6 +351,7 @@ pub const Fe = struct {
         return fe;
     }
 
+    /// Compute the inverse of a field element
     pub fn invert(a: Fe) Fe {
         var t0 = a.sq();
         var t1 = t0.sqn(2).mul(a);
@@ -306,6 +365,8 @@ pub const Fe = struct {
         return t1.mul(t2.mul(t2.sqn(100)).sqn(50)).sqn(5).mul(t0);
     }
 
+    /// Return a^((p-5)/8) = a^(2^252-3)
+    /// Used to compute square roots since we have p=5 (mod 8); see Cohen and Frey.
     pub fn pow2523(a: Fe) Fe {
         var t0 = a.mul(a.sq());
         var t1 = t0.mul(t0.sqn(2)).sq().mul(a);
@@ -317,9 +378,47 @@ pub const Fe = struct {
         return t1.sqn(120).mul(t1).sqn(10).mul(t0).sqn(2).mul(a);
     }
 
+    /// Return the absolute value of a field element
     pub fn abs(a: Fe) Fe {
         var r = a;
         r.cMov(a.neg(), @boolToInt(a.isNegative()));
         return r;
     }
+
+    /// Return true if the field element is a square
+    pub fn isSquare(a: Fe) bool {
+        // Compute the Jacobi symbol x^((p-1)/2)
+        const _11 = a.mul(a.sq());
+        const _1111 = _11.mul(_11.sq().sq());
+        const _11111111 = _1111.mul(_1111.sq().sq().sq().sq());
+        var t = _11111111.sqn(2).mul(_11);
+        const u = t;
+        t = t.sqn(10).mul(u).sqn(10).mul(u);
+        t = t.sqn(30).mul(t);
+        t = t.sqn(60).mul(t);
+        t = t.sqn(120).mul(t).sqn(10).mul(u).sqn(3).mul(_11).sq();
+        return @bitCast(bool, @truncate(u1, ~(t.toBytes()[1] & 1)));
+    }
+
+    fn uncheckedSqrt(x2: Fe) Fe {
+        var e = x2.pow2523();
+        const p_root = e.mul(x2); // positive root
+        const m_root = p_root.mul(Fe.sqrtm1); // negative root
+        const m_root2 = m_root.sq();
+        e = x2.sub(m_root2);
+        var x = p_root;
+        x.cMov(m_root, @boolToInt(e.isZero()));
+        return x;
+    }
+
+    /// Compute the square root of `x2`, returning `error.NotSquare` if `x2` was not a square
+    pub fn sqrt(x2: Fe) !Fe {
+        var x2_copy = x2;
+        const x = x2.uncheckedSqrt();
+        const check = x.sq().sub(x2_copy);
+        if (check.isZero()) {
+            return x;
+        }
+        return error.NotSquare;
+    }
 };