aboutsummaryrefslogtreecommitdiff
path: root/lib/std
diff options
context:
space:
mode:
Diffstat (limited to 'lib/std')
-rw-r--r--lib/std/crypto/25519/edwards25519.zig163
-rw-r--r--lib/std/crypto/25519/field.zig111
2 files changed, 268 insertions, 6 deletions
diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig
index 3e34576f78..570f79b338 100644
--- a/lib/std/crypto/25519/edwards25519.zig
+++ b/lib/std/crypto/25519/edwards25519.zig
@@ -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..]);
+}
diff --git a/lib/std/crypto/25519/field.zig b/lib/std/crypto/25519/field.zig
index 0bc0ead5f2..d2002ce52d 100644
--- a/lib/std/crypto/25519/field.zig
+++ b/lib/std/crypto/25519/field.zig
@@ -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;
+ }
};
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-28 04:02:00 +0000