From 3f0d80f25eccd12759bad21fb8429e646eff070b Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Fri, 14 Aug 2020 14:06:18 +0200 Subject: Improve curve25519-based crypto This is a rewrite of the x25519 code, that generalizes support for common primitives based on the same finite field. - Low-level operations can now be performed over the curve25519 and edwards25519 curves, as well as the ristretto255 group. - Ed25519 signatures have been implemented. - X25519 is now about twice as fast. - mem.timingSafeEqual() has been added for constant-time comparison. Domains have been clearly separated, making it easier to later add platform-specific implementations. --- lib/std/crypto.zig | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'lib/std/crypto.zig') diff --git a/lib/std/crypto.zig b/lib/std/crypto.zig index d0ec3277e8..d15ec2cff2 100644 --- a/lib/std/crypto.zig +++ b/lib/std/crypto.zig @@ -34,12 +34,17 @@ pub const chaCha20IETF = import_chaCha20.chaCha20IETF; pub const chaCha20With64BitNonce = import_chaCha20.chaCha20With64BitNonce; pub const Poly1305 = @import("crypto/poly1305.zig").Poly1305; -pub const X25519 = @import("crypto/x25519.zig").X25519; const import_aes = @import("crypto/aes.zig"); pub const AES128 = import_aes.AES128; pub const AES256 = import_aes.AES256; +pub const Curve25519 = @import("crypto/25519/curve25519.zig").Curve25519; +pub const Ed25519 = @import("crypto/25519/ed25519.zig").Ed25519; +pub const Edwards25519 = @import("crypto/25519/edwards25519.zig").Edwards25519; +pub const X25519 = @import("crypto/25519/x25519.zig").X25519; +pub const Ristretto255 = @import("crypto/25519/ristretto255.zig").Ristretto255; + const std = @import("std.zig"); pub const randomBytes = std.os.getrandom; @@ -55,7 +60,13 @@ test "crypto" { _ = @import("crypto/sha1.zig"); _ = @import("crypto/sha2.zig"); _ = @import("crypto/sha3.zig"); - _ = @import("crypto/x25519.zig"); + _ = @import("crypto/25519/curve25519.zig"); + _ = @import("crypto/25519/ed25519.zig"); + _ = @import("crypto/25519/edwards25519.zig"); + _ = @import("crypto/25519/field25519.zig"); + _ = @import("crypto/25519/scalar25519.zig"); + _ = @import("crypto/25519/x25519.zig"); + _ = @import("crypto/25519/ristretto255.zig"); } test "issue #4532: no index out of bounds" { -- cgit v1.2.3 From dd8f7b396c24d78168d9582364ab5b3b4606ccc5 Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Fri, 14 Aug 2020 16:45:03 +0200 Subject: Rename the field and scalar modules Suggested by @kubkon --- lib/std/crypto.zig | 4 +- lib/std/crypto/25519/curve25519.zig | 4 +- lib/std/crypto/25519/edwards25519.zig | 4 +- lib/std/crypto/25519/field.zig | 327 ++++++++++++++++++++++++++++++++++ lib/std/crypto/25519/field25519.zig | 327 ---------------------------------- lib/std/crypto/25519/scalar.zig | 185 +++++++++++++++++++ lib/std/crypto/25519/scalar25519.zig | 185 ------------------- 7 files changed, 518 insertions(+), 518 deletions(-) create mode 100644 lib/std/crypto/25519/field.zig delete mode 100644 lib/std/crypto/25519/field25519.zig create mode 100644 lib/std/crypto/25519/scalar.zig delete mode 100644 lib/std/crypto/25519/scalar25519.zig (limited to 'lib/std/crypto.zig') diff --git a/lib/std/crypto.zig b/lib/std/crypto.zig index d15ec2cff2..9fbe70f815 100644 --- a/lib/std/crypto.zig +++ b/lib/std/crypto.zig @@ -63,8 +63,8 @@ test "crypto" { _ = @import("crypto/25519/curve25519.zig"); _ = @import("crypto/25519/ed25519.zig"); _ = @import("crypto/25519/edwards25519.zig"); - _ = @import("crypto/25519/field25519.zig"); - _ = @import("crypto/25519/scalar25519.zig"); + _ = @import("crypto/25519/field.zig"); + _ = @import("crypto/25519/scalar.zig"); _ = @import("crypto/25519/x25519.zig"); _ = @import("crypto/25519/ristretto255.zig"); } diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig index 011c926f64..4fb569ccfb 100644 --- a/lib/std/crypto/25519/curve25519.zig +++ b/lib/std/crypto/25519/curve25519.zig @@ -3,9 +3,9 @@ const std = @import("std"); /// Group operations over Curve25519. pub const Curve25519 = struct { /// The underlying prime field. - pub const Fe = @import("field25519.zig").Fe; + pub const Fe = @import("field.zig").Fe; /// Field arithmetic mod the order of the main subgroup. - pub const scalar = @import("scalar25519.zig"); + pub const scalar = @import("scalar.zig"); x: Fe, diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index c28ed6865d..3d21af40e5 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -4,9 +4,9 @@ const fmt = std.fmt; /// Group operations over Edwards25519. pub const Edwards25519 = struct { /// The underlying prime field. - pub const Fe = @import("field25519.zig").Fe; + pub const Fe = @import("field.zig").Fe; /// Field arithmetic mod the order of the main subgroup. - pub const scalar = @import("scalar25519.zig"); + pub const scalar = @import("scalar.zig"); x: Fe, y: Fe, diff --git a/lib/std/crypto/25519/field.zig b/lib/std/crypto/25519/field.zig new file mode 100644 index 0000000000..fe5c28056a --- /dev/null +++ b/lib/std/crypto/25519/field.zig @@ -0,0 +1,327 @@ +const std = @import("std"); +const readIntLittle = std.mem.readIntLittle; +const writeIntLittle = std.mem.writeIntLittle; + +pub const Fe = struct { + limbs: [5]u64, + + const MASK51: u64 = 0x7ffffffffffff; + + pub inline fn zero() Fe { + return .{ .limbs = .{ 0, 0, 0, 0, 0 } }; + } + + pub inline fn one() Fe { + return .{ .limbs = .{ 1, 0, 0, 0, 0 } }; + } + + pub inline fn sqrtm1() Fe { + return .{ .limbs = .{ 1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133 } }; // sqrt(-1) + } + + pub inline fn curve25519BasePoint() Fe { + return .{ .limbs = .{ 9, 0, 0, 0, 0 } }; + } + + pub inline fn edwards25519d() Fe { + return .{ .limbs = .{ 929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575 } }; // 37095705934669439343138083508754565189542113879843219016388785533085940283555 + } + + pub inline fn edwards25519d2() Fe { + return .{ .limbs = .{ 1859910466990425, 932731440258426, 1072319116312658, 1815898335770999, 633789495995903 } }; // 2d + } + + // 1/sqrt(a-d) + pub inline fn edwards25519sqrtamd() Fe { + return .{ .limbs = .{ 278908739862762, 821645201101625, 8113234426968, 1777959178193151, 2118520810568447 } }; + } + + pub inline fn isZero(fe: Fe) bool { + var reduced = fe; + reduced.reduce(); + const limbs = reduced.limbs; + return (limbs[0] | limbs[1] | limbs[2] | limbs[3] | limbs[4]) == 0; + } + + pub inline fn equivalent(a: Fe, b: Fe) bool { + return a.sub(b).isZero(); + } + + pub fn fromBytes(s: [32]u8) Fe { + var fe: Fe = undefined; + fe.limbs[0] = readIntLittle(u64, s[0..8]) & MASK51; + fe.limbs[1] = (readIntLittle(u64, s[6..14]) >> 3) & MASK51; + fe.limbs[2] = (readIntLittle(u64, s[12..20]) >> 6) & MASK51; + fe.limbs[3] = (readIntLittle(u64, s[19..27]) >> 1) & MASK51; + fe.limbs[4] = (readIntLittle(u64, s[24..32]) >> 12) & MASK51; + + return fe; + } + + pub fn toBytes(fe: Fe) [32]u8 { + var reduced = fe; + reduced.reduce(); + var s: [32]u8 = undefined; + writeIntLittle(u64, s[0..8], reduced.limbs[0] | (reduced.limbs[1] << 51)); + writeIntLittle(u64, s[8..16], (reduced.limbs[1] >> 13) | (reduced.limbs[2] << 38)); + writeIntLittle(u64, s[16..24], (reduced.limbs[2] >> 26) | (reduced.limbs[3] << 25)); + writeIntLittle(u64, s[24..32], (reduced.limbs[3] >> 39) | (reduced.limbs[4] << 12)); + + return s; + } + + pub fn rejectNonCanonical(s: [32]u8, comptime ignore_extra_bit: bool) !void { + var c: u16 = (s[31] & 0x7f) ^ 0x7f; + comptime var i = 30; + inline while (i > 0) : (i -= 1) { + c |= s[i] ^ 0xff; + } + c = (c -% 1) >> 8; + const d = (@intCast(u16, 0xed - 1) -% @intCast(u16, s[0])) >> 8; + const x = if (ignore_extra_bit) 0 else s[31] >> 7; + if ((((c & d) | x) & 1) != 0) { + return error.NonCanonical; + } + } + + fn reduce(fe: *Fe) void { + comptime var i = 0; + comptime var j = 0; + const limbs = &fe.limbs; + inline while (j < 2) : (j += 1) { + i = 0; + inline while (i < 4) : (i += 1) { + limbs[i + 1] += limbs[i] >> 51; + limbs[i] &= MASK51; + } + limbs[0] += 19 * (limbs[4] >> 51); + limbs[4] &= MASK51; + } + limbs[0] += 19; + i = 0; + inline while (i < 4) : (i += 1) { + limbs[i + 1] += limbs[i] >> 51; + limbs[i] &= MASK51; + } + limbs[0] += 19 * (limbs[4] >> 51); + limbs[4] &= MASK51; + + limbs[0] += 0x8000000000000 - 19; + limbs[1] += 0x8000000000000 - 1; + limbs[2] += 0x8000000000000 - 1; + limbs[3] += 0x8000000000000 - 1; + limbs[4] += 0x8000000000000 - 1; + + i = 0; + inline while (i < 4) : (i += 1) { + limbs[i + 1] += limbs[i] >> 51; + limbs[i] &= MASK51; + } + limbs[4] &= MASK51; + } + + pub inline fn add(a: Fe, b: Fe) Fe { + var fe: Fe = undefined; + comptime var i = 0; + inline while (i < 5) : (i += 1) { + fe.limbs[i] = a.limbs[i] + b.limbs[i]; + } + return fe; + } + + pub fn sub(a: Fe, b: Fe) Fe { + var fe = b; + comptime var i = 0; + inline while (i < 4) : (i += 1) { + fe.limbs[i + 1] += fe.limbs[i] >> 51; + fe.limbs[i] &= MASK51; + } + fe.limbs[0] += 19 * (fe.limbs[4] >> 51); + fe.limbs[4] &= MASK51; + fe.limbs[0] = (a.limbs[0] + 0xfffffffffffda) - fe.limbs[0]; + fe.limbs[1] = (a.limbs[1] + 0xffffffffffffe) - fe.limbs[1]; + fe.limbs[2] = (a.limbs[2] + 0xffffffffffffe) - fe.limbs[2]; + fe.limbs[3] = (a.limbs[3] + 0xffffffffffffe) - fe.limbs[3]; + fe.limbs[4] = (a.limbs[4] + 0xffffffffffffe) - fe.limbs[4]; + + return fe; + } + + pub inline fn neg(a: Fe) Fe { + return zero().sub(a); + } + + pub inline fn isNegative(a: Fe) bool { + return (a.toBytes()[0] & 1) != 0; + } + + pub inline fn cMov(fe: *Fe, a: Fe, c: u64) void { + const mask: u64 = 0 -% c; + var x = fe.*; + comptime var i = 0; + inline while (i < 5) : (i += 1) { + x.limbs[i] ^= a.limbs[i]; + } + i = 0; + inline while (i < 5) : (i += 1) { + x.limbs[i] &= mask; + } + i = 0; + inline while (i < 5) : (i += 1) { + fe.limbs[i] ^= x.limbs[i]; + } + } + + pub fn cSwap2(a0: *Fe, b0: *Fe, a1: *Fe, b1: *Fe, c: u64) void { + const mask: u64 = 0 -% c; + var x0 = a0.*; + var x1 = a1.*; + comptime var i = 0; + inline while (i < 5) : (i += 1) { + x0.limbs[i] ^= b0.limbs[i]; + x1.limbs[i] ^= b1.limbs[i]; + } + i = 0; + inline while (i < 5) : (i += 1) { + x0.limbs[i] &= mask; + x1.limbs[i] &= mask; + } + i = 0; + inline while (i < 5) : (i += 1) { + a0.limbs[i] ^= x0.limbs[i]; + b0.limbs[i] ^= x0.limbs[i]; + a1.limbs[i] ^= x1.limbs[i]; + b1.limbs[i] ^= x1.limbs[i]; + } + } + + inline fn _carry128(r: *[5]u128) Fe { + var rs: [5]u64 = undefined; + comptime var i = 0; + inline while (i < 4) : (i += 1) { + rs[i] = @truncate(u64, r[i]) & MASK51; + r[i + 1] += @intCast(u64, r[i] >> 51); + } + rs[4] = @truncate(u64, r[4]) & MASK51; + var carry = @intCast(u64, r[4] >> 51); + rs[0] += 19 * carry; + carry = rs[0] >> 51; + rs[0] &= MASK51; + rs[1] += carry; + carry = rs[1] >> 51; + rs[1] &= MASK51; + rs[2] += carry; + + return .{ .limbs = rs }; + } + + pub fn mul(a: Fe, b: Fe) Fe { + var ax: [5]u128 = undefined; + var bx: [5]u128 = undefined; + var a19: [5]u128 = undefined; + var r: [5]u128 = undefined; + comptime var i = 0; + inline while (i < 5) : (i += 1) { + ax[i] = @intCast(u128, a.limbs[i]); + bx[i] = @intCast(u128, b.limbs[i]); + } + i = 1; + inline while (i < 5) : (i += 1) { + a19[i] = 19 * ax[i]; + } + r[0] = ax[0] * bx[0] + a19[1] * bx[4] + a19[2] * bx[3] + a19[3] * bx[2] + a19[4] * bx[1]; + r[1] = ax[0] * bx[1] + ax[1] * bx[0] + a19[2] * bx[4] + a19[3] * bx[3] + a19[4] * bx[2]; + r[2] = ax[0] * bx[2] + ax[1] * bx[1] + ax[2] * bx[0] + a19[3] * bx[4] + a19[4] * bx[3]; + r[3] = ax[0] * bx[3] + ax[1] * bx[2] + ax[2] * bx[1] + ax[3] * bx[0] + a19[4] * bx[4]; + r[4] = ax[0] * bx[4] + ax[1] * bx[3] + ax[2] * bx[2] + ax[3] * bx[1] + ax[4] * bx[0]; + + return _carry128(&r); + } + + fn _sq(a: Fe, double: comptime bool) Fe { + var ax: [5]u128 = undefined; + var r: [5]u128 = undefined; + comptime var i = 0; + inline while (i < 5) : (i += 1) { + ax[i] = @intCast(u128, a.limbs[i]); + } + const a0_2 = 2 * ax[0]; + const a1_2 = 2 * ax[1]; + const a1_38 = 38 * ax[1]; + const a2_38 = 38 * ax[2]; + const a3_38 = 38 * ax[3]; + const a3_19 = 19 * ax[3]; + const a4_19 = 19 * ax[4]; + r[0] = ax[0] * ax[0] + a1_38 * ax[4] + a2_38 * ax[3]; + r[1] = a0_2 * ax[1] + a2_38 * ax[4] + a3_19 * ax[3]; + r[2] = a0_2 * ax[2] + ax[1] * ax[1] + a3_38 * ax[4]; + r[3] = a0_2 * ax[3] + a1_2 * ax[2] + a4_19 * ax[4]; + r[4] = a0_2 * ax[4] + a1_2 * ax[3] + ax[2] * ax[2]; + if (double) { + i = 0; + inline while (i < 5) : (i += 1) { + r[i] *= 2; + } + } + return _carry128(&r); + } + + pub inline fn sq(a: Fe) Fe { + return _sq(a, false); + } + + pub inline fn sq2(a: Fe) Fe { + return _sq(a, true); + } + + pub inline fn mul32(a: Fe, comptime n: u32) Fe { + const sn = @intCast(u128, n); + var fe: Fe = undefined; + var x: u128 = 0; + comptime var i = 0; + inline while (i < 5) : (i += 1) { + x = a.limbs[i] * sn + (x >> 51); + fe.limbs[i] = @truncate(u64, x) & MASK51; + } + fe.limbs[0] += @intCast(u64, x >> 51) * 19; + + return fe; + } + + inline fn sqn(a: Fe, comptime n: comptime_int) Fe { + var i: usize = 0; + var fe = a; + while (i < n) : (i += 1) { + fe = fe.sq(); + } + return fe; + } + + pub fn invert(a: Fe) Fe { + var t0 = a.sq(); + var t1 = t0.sqn(2).mul(a); + t0 = t0.mul(t1); + t1 = t1.mul(t0.sq()); + t1 = t1.mul(t1.sqn(5)); + var t2 = t1.sqn(10).mul(t1); + t2 = t2.mul(t2.sqn(20)).sqn(10); + t1 = t1.mul(t2); + t2 = t1.sqn(50).mul(t1); + return t1.mul(t2.mul(t2.sqn(100)).sqn(50)).sqn(5).mul(t0); + } + + pub fn pow2523(a: Fe) Fe { + var c = a; + var i: usize = 0; + while (i < 249) : (i += 1) { + c = c.sq().mul(a); + } + return c.sq().sq().mul(a); + } + + pub fn abs(a: Fe) Fe { + var r = a; + r.cMov(a.neg(), @boolToInt(a.isNegative())); + return r; + } +}; diff --git a/lib/std/crypto/25519/field25519.zig b/lib/std/crypto/25519/field25519.zig deleted file mode 100644 index fe5c28056a..0000000000 --- a/lib/std/crypto/25519/field25519.zig +++ /dev/null @@ -1,327 +0,0 @@ -const std = @import("std"); -const readIntLittle = std.mem.readIntLittle; -const writeIntLittle = std.mem.writeIntLittle; - -pub const Fe = struct { - limbs: [5]u64, - - const MASK51: u64 = 0x7ffffffffffff; - - pub inline fn zero() Fe { - return .{ .limbs = .{ 0, 0, 0, 0, 0 } }; - } - - pub inline fn one() Fe { - return .{ .limbs = .{ 1, 0, 0, 0, 0 } }; - } - - pub inline fn sqrtm1() Fe { - return .{ .limbs = .{ 1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133 } }; // sqrt(-1) - } - - pub inline fn curve25519BasePoint() Fe { - return .{ .limbs = .{ 9, 0, 0, 0, 0 } }; - } - - pub inline fn edwards25519d() Fe { - return .{ .limbs = .{ 929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575 } }; // 37095705934669439343138083508754565189542113879843219016388785533085940283555 - } - - pub inline fn edwards25519d2() Fe { - return .{ .limbs = .{ 1859910466990425, 932731440258426, 1072319116312658, 1815898335770999, 633789495995903 } }; // 2d - } - - // 1/sqrt(a-d) - pub inline fn edwards25519sqrtamd() Fe { - return .{ .limbs = .{ 278908739862762, 821645201101625, 8113234426968, 1777959178193151, 2118520810568447 } }; - } - - pub inline fn isZero(fe: Fe) bool { - var reduced = fe; - reduced.reduce(); - const limbs = reduced.limbs; - return (limbs[0] | limbs[1] | limbs[2] | limbs[3] | limbs[4]) == 0; - } - - pub inline fn equivalent(a: Fe, b: Fe) bool { - return a.sub(b).isZero(); - } - - pub fn fromBytes(s: [32]u8) Fe { - var fe: Fe = undefined; - fe.limbs[0] = readIntLittle(u64, s[0..8]) & MASK51; - fe.limbs[1] = (readIntLittle(u64, s[6..14]) >> 3) & MASK51; - fe.limbs[2] = (readIntLittle(u64, s[12..20]) >> 6) & MASK51; - fe.limbs[3] = (readIntLittle(u64, s[19..27]) >> 1) & MASK51; - fe.limbs[4] = (readIntLittle(u64, s[24..32]) >> 12) & MASK51; - - return fe; - } - - pub fn toBytes(fe: Fe) [32]u8 { - var reduced = fe; - reduced.reduce(); - var s: [32]u8 = undefined; - writeIntLittle(u64, s[0..8], reduced.limbs[0] | (reduced.limbs[1] << 51)); - writeIntLittle(u64, s[8..16], (reduced.limbs[1] >> 13) | (reduced.limbs[2] << 38)); - writeIntLittle(u64, s[16..24], (reduced.limbs[2] >> 26) | (reduced.limbs[3] << 25)); - writeIntLittle(u64, s[24..32], (reduced.limbs[3] >> 39) | (reduced.limbs[4] << 12)); - - return s; - } - - pub fn rejectNonCanonical(s: [32]u8, comptime ignore_extra_bit: bool) !void { - var c: u16 = (s[31] & 0x7f) ^ 0x7f; - comptime var i = 30; - inline while (i > 0) : (i -= 1) { - c |= s[i] ^ 0xff; - } - c = (c -% 1) >> 8; - const d = (@intCast(u16, 0xed - 1) -% @intCast(u16, s[0])) >> 8; - const x = if (ignore_extra_bit) 0 else s[31] >> 7; - if ((((c & d) | x) & 1) != 0) { - return error.NonCanonical; - } - } - - fn reduce(fe: *Fe) void { - comptime var i = 0; - comptime var j = 0; - const limbs = &fe.limbs; - inline while (j < 2) : (j += 1) { - i = 0; - inline while (i < 4) : (i += 1) { - limbs[i + 1] += limbs[i] >> 51; - limbs[i] &= MASK51; - } - limbs[0] += 19 * (limbs[4] >> 51); - limbs[4] &= MASK51; - } - limbs[0] += 19; - i = 0; - inline while (i < 4) : (i += 1) { - limbs[i + 1] += limbs[i] >> 51; - limbs[i] &= MASK51; - } - limbs[0] += 19 * (limbs[4] >> 51); - limbs[4] &= MASK51; - - limbs[0] += 0x8000000000000 - 19; - limbs[1] += 0x8000000000000 - 1; - limbs[2] += 0x8000000000000 - 1; - limbs[3] += 0x8000000000000 - 1; - limbs[4] += 0x8000000000000 - 1; - - i = 0; - inline while (i < 4) : (i += 1) { - limbs[i + 1] += limbs[i] >> 51; - limbs[i] &= MASK51; - } - limbs[4] &= MASK51; - } - - pub inline fn add(a: Fe, b: Fe) Fe { - var fe: Fe = undefined; - comptime var i = 0; - inline while (i < 5) : (i += 1) { - fe.limbs[i] = a.limbs[i] + b.limbs[i]; - } - return fe; - } - - pub fn sub(a: Fe, b: Fe) Fe { - var fe = b; - comptime var i = 0; - inline while (i < 4) : (i += 1) { - fe.limbs[i + 1] += fe.limbs[i] >> 51; - fe.limbs[i] &= MASK51; - } - fe.limbs[0] += 19 * (fe.limbs[4] >> 51); - fe.limbs[4] &= MASK51; - fe.limbs[0] = (a.limbs[0] + 0xfffffffffffda) - fe.limbs[0]; - fe.limbs[1] = (a.limbs[1] + 0xffffffffffffe) - fe.limbs[1]; - fe.limbs[2] = (a.limbs[2] + 0xffffffffffffe) - fe.limbs[2]; - fe.limbs[3] = (a.limbs[3] + 0xffffffffffffe) - fe.limbs[3]; - fe.limbs[4] = (a.limbs[4] + 0xffffffffffffe) - fe.limbs[4]; - - return fe; - } - - pub inline fn neg(a: Fe) Fe { - return zero().sub(a); - } - - pub inline fn isNegative(a: Fe) bool { - return (a.toBytes()[0] & 1) != 0; - } - - pub inline fn cMov(fe: *Fe, a: Fe, c: u64) void { - const mask: u64 = 0 -% c; - var x = fe.*; - comptime var i = 0; - inline while (i < 5) : (i += 1) { - x.limbs[i] ^= a.limbs[i]; - } - i = 0; - inline while (i < 5) : (i += 1) { - x.limbs[i] &= mask; - } - i = 0; - inline while (i < 5) : (i += 1) { - fe.limbs[i] ^= x.limbs[i]; - } - } - - pub fn cSwap2(a0: *Fe, b0: *Fe, a1: *Fe, b1: *Fe, c: u64) void { - const mask: u64 = 0 -% c; - var x0 = a0.*; - var x1 = a1.*; - comptime var i = 0; - inline while (i < 5) : (i += 1) { - x0.limbs[i] ^= b0.limbs[i]; - x1.limbs[i] ^= b1.limbs[i]; - } - i = 0; - inline while (i < 5) : (i += 1) { - x0.limbs[i] &= mask; - x1.limbs[i] &= mask; - } - i = 0; - inline while (i < 5) : (i += 1) { - a0.limbs[i] ^= x0.limbs[i]; - b0.limbs[i] ^= x0.limbs[i]; - a1.limbs[i] ^= x1.limbs[i]; - b1.limbs[i] ^= x1.limbs[i]; - } - } - - inline fn _carry128(r: *[5]u128) Fe { - var rs: [5]u64 = undefined; - comptime var i = 0; - inline while (i < 4) : (i += 1) { - rs[i] = @truncate(u64, r[i]) & MASK51; - r[i + 1] += @intCast(u64, r[i] >> 51); - } - rs[4] = @truncate(u64, r[4]) & MASK51; - var carry = @intCast(u64, r[4] >> 51); - rs[0] += 19 * carry; - carry = rs[0] >> 51; - rs[0] &= MASK51; - rs[1] += carry; - carry = rs[1] >> 51; - rs[1] &= MASK51; - rs[2] += carry; - - return .{ .limbs = rs }; - } - - pub fn mul(a: Fe, b: Fe) Fe { - var ax: [5]u128 = undefined; - var bx: [5]u128 = undefined; - var a19: [5]u128 = undefined; - var r: [5]u128 = undefined; - comptime var i = 0; - inline while (i < 5) : (i += 1) { - ax[i] = @intCast(u128, a.limbs[i]); - bx[i] = @intCast(u128, b.limbs[i]); - } - i = 1; - inline while (i < 5) : (i += 1) { - a19[i] = 19 * ax[i]; - } - r[0] = ax[0] * bx[0] + a19[1] * bx[4] + a19[2] * bx[3] + a19[3] * bx[2] + a19[4] * bx[1]; - r[1] = ax[0] * bx[1] + ax[1] * bx[0] + a19[2] * bx[4] + a19[3] * bx[3] + a19[4] * bx[2]; - r[2] = ax[0] * bx[2] + ax[1] * bx[1] + ax[2] * bx[0] + a19[3] * bx[4] + a19[4] * bx[3]; - r[3] = ax[0] * bx[3] + ax[1] * bx[2] + ax[2] * bx[1] + ax[3] * bx[0] + a19[4] * bx[4]; - r[4] = ax[0] * bx[4] + ax[1] * bx[3] + ax[2] * bx[2] + ax[3] * bx[1] + ax[4] * bx[0]; - - return _carry128(&r); - } - - fn _sq(a: Fe, double: comptime bool) Fe { - var ax: [5]u128 = undefined; - var r: [5]u128 = undefined; - comptime var i = 0; - inline while (i < 5) : (i += 1) { - ax[i] = @intCast(u128, a.limbs[i]); - } - const a0_2 = 2 * ax[0]; - const a1_2 = 2 * ax[1]; - const a1_38 = 38 * ax[1]; - const a2_38 = 38 * ax[2]; - const a3_38 = 38 * ax[3]; - const a3_19 = 19 * ax[3]; - const a4_19 = 19 * ax[4]; - r[0] = ax[0] * ax[0] + a1_38 * ax[4] + a2_38 * ax[3]; - r[1] = a0_2 * ax[1] + a2_38 * ax[4] + a3_19 * ax[3]; - r[2] = a0_2 * ax[2] + ax[1] * ax[1] + a3_38 * ax[4]; - r[3] = a0_2 * ax[3] + a1_2 * ax[2] + a4_19 * ax[4]; - r[4] = a0_2 * ax[4] + a1_2 * ax[3] + ax[2] * ax[2]; - if (double) { - i = 0; - inline while (i < 5) : (i += 1) { - r[i] *= 2; - } - } - return _carry128(&r); - } - - pub inline fn sq(a: Fe) Fe { - return _sq(a, false); - } - - pub inline fn sq2(a: Fe) Fe { - return _sq(a, true); - } - - pub inline fn mul32(a: Fe, comptime n: u32) Fe { - const sn = @intCast(u128, n); - var fe: Fe = undefined; - var x: u128 = 0; - comptime var i = 0; - inline while (i < 5) : (i += 1) { - x = a.limbs[i] * sn + (x >> 51); - fe.limbs[i] = @truncate(u64, x) & MASK51; - } - fe.limbs[0] += @intCast(u64, x >> 51) * 19; - - return fe; - } - - inline fn sqn(a: Fe, comptime n: comptime_int) Fe { - var i: usize = 0; - var fe = a; - while (i < n) : (i += 1) { - fe = fe.sq(); - } - return fe; - } - - pub fn invert(a: Fe) Fe { - var t0 = a.sq(); - var t1 = t0.sqn(2).mul(a); - t0 = t0.mul(t1); - t1 = t1.mul(t0.sq()); - t1 = t1.mul(t1.sqn(5)); - var t2 = t1.sqn(10).mul(t1); - t2 = t2.mul(t2.sqn(20)).sqn(10); - t1 = t1.mul(t2); - t2 = t1.sqn(50).mul(t1); - return t1.mul(t2.mul(t2.sqn(100)).sqn(50)).sqn(5).mul(t0); - } - - pub fn pow2523(a: Fe) Fe { - var c = a; - var i: usize = 0; - while (i < 249) : (i += 1) { - c = c.sq().mul(a); - } - return c.sq().sq().mul(a); - } - - pub fn abs(a: Fe) Fe { - var r = a; - r.cMov(a.neg(), @boolToInt(a.isNegative())); - return r; - } -}; diff --git a/lib/std/crypto/25519/scalar.zig b/lib/std/crypto/25519/scalar.zig new file mode 100644 index 0000000000..6971b43489 --- /dev/null +++ b/lib/std/crypto/25519/scalar.zig @@ -0,0 +1,185 @@ +const std = @import("std"); +const mem = std.mem; + +inline fn fieldSize() [32]u8 { + return .{ + 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, // 2^252+27742317777372353535851937790883648493 + }; +} + +const ScalarExpanded = struct { + const L = fieldSize(); + limbs: [64]i64 = [_]i64{0} ** 64, + + fn fromBytes(s: [32]u8) ScalarExpanded { + var limbs: [64]i64 = undefined; + for (s) |x, idx| { + limbs[idx] = @intCast(i64, x); + } + mem.set(i64, limbs[32..], 0); + return .{ .limbs = limbs }; + } + + fn fromBytes64(s: [64]u8) ScalarExpanded { + var limbs: [64]i64 = undefined; + for (s) |x, idx| { + limbs[idx] = @intCast(i64, x); + } + return .{ .limbs = limbs }; + } + + fn reduce(e: *ScalarExpanded) void { + const limbs = &e.limbs; + var carry: i64 = undefined; + var i: usize = 63; + while (i >= 32) : (i -= 1) { + carry = 0; + const k = i - 12; + const xi = limbs[i]; + var j = i - 32; + while (j < k) : (j += 1) { + const xj = limbs[j] + carry - 16 * xi * @intCast(i64, L[j - (i - 32)]); + carry = (xj + 128) >> 8; + limbs[j] = xj - carry * 256; + } + limbs[k] += carry; + limbs[i] = 0; + } + carry = 0; + comptime var j: usize = 0; + inline while (j < 32) : (j += 1) { + const xi = limbs[j] + carry - (limbs[31] >> 4) * @intCast(i64, L[j]); + carry = xi >> 8; + limbs[j] = xi & 255; + } + j = 0; + inline while (j < 32) : (j += 1) { + limbs[j] -= carry * @intCast(i64, L[j]); + } + j = 0; + inline while (j < 32) : (j += 1) { + limbs[j + 1] += limbs[j] >> 8; + } + } + + fn toBytes(e: *ScalarExpanded) [32]u8 { + e.reduce(); + var r: [32]u8 = undefined; + var i: usize = 0; + while (i < 32) : (i += 1) { + r[i] = @intCast(u8, e.limbs[i]); + } + return r; + } + + fn add(a: ScalarExpanded, b: ScalarExpanded) ScalarExpanded { + var r = ScalarExpanded{}; + comptime var i = 0; + inline while (i < 64) : (i += 1) { + r.limbs[i] = a.limbs[i] + b.limbs[i]; + } + return r; + } + + fn mul(a: ScalarExpanded, b: ScalarExpanded) ScalarExpanded { + var r = ScalarExpanded{}; + var i: usize = 0; + while (i < 32) : (i += 1) { + const ai = a.limbs[i]; + comptime var j = 0; + inline while (j < 32) : (j += 1) { + r.limbs[i + j] += ai * b.limbs[j]; + } + } + r.reduce(); + return r; + } + + fn sq(a: ScalarExpanded) ScalarExpanded { + return a.mul(a); + } + + fn mulAdd(a: ScalarExpanded, b: ScalarExpanded, c: ScalarExpanded) ScalarExpanded { + var r: ScalarExpanded = .{ .limbs = c.limbs }; + var i: usize = 0; + while (i < 32) : (i += 1) { + const ai = a.limbs[i]; + comptime var j = 0; + inline while (j < 32) : (j += 1) { + r.limbs[i + j] += ai * b.limbs[j]; + } + } + r.reduce(); + return r; + } +}; + +/// Reject a scalar whose encoding is not canonical. +pub fn rejectNonCanonical(s: [32]u8) !void { + const L = fieldSize(); + var c: u8 = 0; + var n: u8 = 1; + var i: usize = 31; + while (true) { + const xs = @intCast(u16, s[i]); + const xL = @intCast(u16, L[i]); + c |= @intCast(u8, ((xs -% xL) >> 8) & n); + n &= @intCast(u8, ((xs ^ xL) -% 1) >> 8); + if (i == 0) break; + i -= 1; + } + if (c == 0) { + return error.NonCanonical; + } +} + +/// Reduce a scalar to the field size. +pub fn reduce(s: [32]u8) [32]u8 { + return ScalarExpanded.fromBytes(s).toBytes(); +} + +/// Reduce a 64-bytes scalar to the field size. +pub fn reduce64(s: [64]u8) [32]u8 { + return ScalarExpanded.fromBytes64(s).toBytes(); +} + +/// Perform the X25519 "clamping" operation. +/// The scalar is then guaranteed to be a multiple of the cofactor. +pub inline fn clamp(s: *[32]u8) void { + s[0] &= 248; + s[31] = (s[31] & 127) | 64; +} + +/// Return a*b+c (mod L) +pub fn mulAdd(a: [32]u8, b: [32]u8, c: [32]u8) [32]u8 { + return ScalarExpanded.fromBytes(a).mulAdd(ScalarExpanded.fromBytes(b), ScalarExpanded.fromBytes(c)).toBytes(); +} + +test "scalar25519" { + const bytes: [32]u8 = .{ 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 255 }; + var x = ScalarExpanded.fromBytes(bytes); + var y = x.toBytes(); + try rejectNonCanonical(y); + var buf: [128]u8 = undefined; + const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{y}), "1E979B917937F3DE71D18077F961F6CEFF01030405060708010203040506070F"); + + const field_size = fieldSize(); + const reduced = reduce(field_size); + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{reduced}), "0000000000000000000000000000000000000000000000000000000000000000"); +} + +test "non-canonical scalar25519" { + const too_targe: [32]u8 = .{ 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 }; + std.testing.expectError(error.NonCanonical, rejectNonCanonical(too_targe)); +} + +test "scalar25519 mulAdd overflow check" { + const a: [32]u8 = [_]u8{0xff} ** 32; + const b: [32]u8 = [_]u8{0xff} ** 32; + const c: [32]u8 = [_]u8{0xff} ** 32; + const x = mulAdd(a, b, c); + var buf: [128]u8 = undefined; + const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{x}), "D14DF91389432C25AD60FF9791B9FD1D67BEF517D273ECCE3D9A307C1B419903"); +} diff --git a/lib/std/crypto/25519/scalar25519.zig b/lib/std/crypto/25519/scalar25519.zig deleted file mode 100644 index a94e6531dc..0000000000 --- a/lib/std/crypto/25519/scalar25519.zig +++ /dev/null @@ -1,185 +0,0 @@ -const std = @import("std"); -const mem = std.mem; - -inline fn fieldSize() [32]u8 { - return .{ - 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, // 2^252+27742317777372353535851937790883648493 - }; -} - -const ScalarExpanded = struct { - const L = fieldSize(); - limbs: [64]i64 = [_]i64{0} ** 64, - - fn fromBytes(s: [32]u8) ScalarExpanded { - var limbs: [64]i64 = undefined; - for (s) |x, idx| { - limbs[idx] = @intCast(i64, x); - } - mem.set(i64, limbs[32..], 0); - return .{ .limbs = limbs }; - } - - fn fromBytes64(s: [64]u8) ScalarExpanded { - var limbs: [64]i64 = undefined; - for (s) |x, idx| { - limbs[idx] = @intCast(i64, x); - } - return .{ .limbs = limbs }; - } - - fn reduce(e: *ScalarExpanded) void { - const limbs = &e.limbs; - var carry: i64 = undefined; - var i: usize = 63; - while (i >= 32) : (i -= 1) { - carry = 0; - const k = i - 12; - const xi = limbs[i]; - var j = i - 32; - while (j < k) : (j += 1) { - const xj = limbs[j] + carry - 16 * xi * @intCast(i64, L[j - (i - 32)]); - carry = (xj + 128) >> 8; - limbs[j] = xj - carry * 256; - } - limbs[k] += carry; - limbs[i] = 0; - } - carry = 0; - comptime var j: usize = 0; - inline while (j < 32) : (j += 1) { - const xi = limbs[j] + carry - (limbs[31] >> 4) * @intCast(i64, L[j]); - carry = xi >> 8; - limbs[j] = xi & 255; - } - j = 0; - inline while (j < 32) : (j += 1) { - limbs[j] -= carry * @intCast(i64, L[j]); - } - j = 0; - inline while (j < 32) : (j += 1) { - limbs[j + 1] += limbs[j] >> 8; - } - } - - fn toBytes(e: *ScalarExpanded) [32]u8 { - e.reduce(); - var r: [32]u8 = undefined; - var i: usize = 0; - while (i < 32) : (i += 1) { - r[i] = @intCast(u8, e.limbs[i]); - } - return r; - } - - fn add(a: ScalarExpanded, b: ScalarExpanded) ScalarExpanded { - var r = ScalarExpanded{}; - comptime var i = 0; - inline while (i < 64) : (i += 1) { - r.limbs[i] = a.limbs[i] + b.limbs[i]; - } - return r; - } - - fn mul(a: ScalarExpanded, b: ScalarExpanded) ScalarExpanded { - var r = ScalarExpanded{}; - var i: usize = 0; - while (i < 32) : (i += 1) { - const ai = a.limbs[i]; - comptime var j = 0; - inline while (j < 32) : (j += 1) { - r.limbs[i + j] += ai * b.limbs[j]; - } - } - r.reduce(); - return r; - } - - fn sq(a: ScalarExpanded) ScalarExpanded { - return a.mul(a); - } - - fn mulAdd(a: ScalarExpanded, b: ScalarExpanded, c: ScalarExpanded) ScalarExpanded { - var r: ScalarExpanded = .{ .limbs = c.limbs }; - var i: usize = 0; - while (i < 32) : (i += 1) { - const ai = a.limbs[i]; - comptime var j = 0; - inline while (j < 32) : (j += 1) { - r.limbs[i + j] += ai * b.limbs[j]; - } - } - r.reduce(); - return r; - } -}; - -/// Reject a scalar whose encoding is not canonical. -pub fn rejectNonCanonical(s: [32]u8) !void { - const L = fieldSize(); - var c: u8 = 0; - var n: u8 = 1; - var i: usize = 31; - while (true) { - const xs = @intCast(u16, s[i]); - const xL = @intCast(u16, L[i]); - c |= @intCast(u8, ((xs -% xL) >> 8) & n); - n &= @intCast(u8, ((xs ^ xL) -% 1) >> 8); - if (i == 0) break; - i -= 1; - } - if (c == 0) { - return error.NonCanonical; - } -} - -/// Reduce a scalar to the field size. -pub fn reduce(s: [32]u8) [32]u8 { - return ScalarExpanded.fromBytes(s).toBytes(); -} - -/// Reduce a 64-bytes scalar to the field size. -pub fn reduce64(s: [64]u8) [32]u8 { - return ScalarExpanded.fromBytes64(s).toBytes(); -} - -/// Perform the X25519 "clamping" operation. -/// The scalar is then guaranteed to be a multiple of the cofactor. -pub inline fn clamp(s: *[32]u8) void { - s[0] &= 248; - s[31] = (s[31] & 127) | 64; -} - -/// Return a*b+c (mod L) -pub fn mulAdd(a: [32]u8, b: [32]u8, c: [32]u8) [32]u8 { - return ScalarExpanded.fromBytes(a).mulAdd(ScalarExpanded.fromBytes(b), ScalarExpanded.fromBytes(c)).toBytes(); -} - -test "scalar25519" { - const bytes: [32]u8 = .{ 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 255 }; - var x = ScalarExpanded.fromBytes(bytes); - var y = x.toBytes(); - try rejectNonCanonical(y); - var buf: [128]u8 = undefined; - const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{y}), "1E979B917937F3DE71D18077F961F6CEFF01030405060708010203040506070F"); - - const field_size = fieldSize(); - const reduced = reduce(field_size); - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{reduced}), "0000000000000000000000000000000000000000000000000000000000000000"); -} - -test "non-canonical scalar25519" { - const too_targe: [32]u8 = .{ 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 }; - std.testing.expectError(error.NonCanonical, rejectNonCanonical(too_targe)); -} - -test "mulAdd overflow check" { - const a: [32]u8 = [_]u8{0xff} ** 32; - const b: [32]u8 = [_]u8{0xff} ** 32; - const c: [32]u8 = [_]u8{0xff} ** 32; - const x = mulAdd(a, b, c); - var buf: [128]u8 = undefined; - const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{x}), "D14DF91389432C25AD60FF9791B9FD1D67BEF517D273ECCE3D9A307C1B419903"); -} -- cgit v1.2.3