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 +- lib/std/crypto/25519/curve25519.zig | 155 ++++++++ lib/std/crypto/25519/ed25519.zig | 129 +++++++ lib/std/crypto/25519/edwards25519.zig | 224 +++++++++++ lib/std/crypto/25519/field25519.zig | 327 ++++++++++++++++ lib/std/crypto/25519/ristretto255.zig | 153 ++++++++ lib/std/crypto/25519/scalar25519.zig | 185 ++++++++++ lib/std/crypto/25519/x25519.zig | 146 ++++++++ lib/std/crypto/x25519.zig | 675 ---------------------------------- lib/std/mem.zig | 25 ++ 10 files changed, 1357 insertions(+), 677 deletions(-) create mode 100644 lib/std/crypto/25519/curve25519.zig create mode 100644 lib/std/crypto/25519/ed25519.zig create mode 100644 lib/std/crypto/25519/edwards25519.zig create mode 100644 lib/std/crypto/25519/field25519.zig create mode 100644 lib/std/crypto/25519/ristretto255.zig create mode 100644 lib/std/crypto/25519/scalar25519.zig create mode 100644 lib/std/crypto/25519/x25519.zig delete mode 100644 lib/std/crypto/x25519.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" { diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig new file mode 100644 index 0000000000..a17d9baa7b --- /dev/null +++ b/lib/std/crypto/25519/curve25519.zig @@ -0,0 +1,155 @@ +const std = @import("std"); + +/// Group operations over Curve25519. +pub const Curve25519 = struct { + /// The underlying prime field. + pub const Fe = @import("field25519.zig").Fe; + /// Field arithmetic mod the order of the main subgroup. + pub const scalar = @import("scalar25519.zig"); + + x: Fe, + + /// Decode a Curve25519 point from its compressed (X) coordinates. + pub inline fn fromBytes(s: [32]u8) Curve25519 { + return .{ .x = Fe.fromBytes(s) }; + } + + /// Encode a Curve25519 point. + pub inline fn toBytes(p: Curve25519) [32]u8 { + return p.x.toBytes(); + } + + /// Return the Curve25519 base point. + pub inline fn basePoint() Curve25519 { + return .{ .x = Fe.curve25519BasePoint() }; + } + + /// Check that the encoding of a Curve25519 point is canonical. + pub fn rejectNonCanonical(s: [32]u8) !void { + return Fe.rejectNonCanonical(s, false); + } + + /// Reject the neutral element. + pub fn rejectIdentity(p: Curve25519) !void { + if (p.x.isZero()) { + return error.IdentityElement; + } + } + + fn ladder(p: Curve25519, s: [32]u8, comptime bits: usize) !Curve25519 { + var x1 = p.x; + var x2 = Fe.one(); + var z2 = Fe.zero(); + var x3 = x1; + var z3 = Fe.one(); + var swap: u8 = 0; + var pos: usize = bits - 1; + while (true) { + const b = (s[pos / 8] >> @intCast(u3, pos & 7)) & 1; + swap ^= b; + Fe.cSwap2(&x2, &x3, &z2, &z3, swap); + swap = b; + var tmp0 = x3.sub(z3); + var tmp1 = x2.sub(z2); + x2 = x2.add(z2); + z2 = x3.add(z3); + z3 = tmp0.mul(x2); + z2 = z2.mul(tmp1); + tmp0 = tmp1.sq(); + tmp1 = x2.sq(); + x3 = z3.add(z2); + z2 = z3.sub(z2); + x2 = tmp1.mul(tmp0); + tmp1 = tmp1.sub(tmp0); + z2 = z2.sq(); + z3 = tmp1.mul32(121666); + x3 = x3.sq(); + tmp0 = tmp0.add(z3); + z3 = x1.mul(z2); + z2 = tmp1.mul(tmp0); + if (pos == 0) break; + pos -= 1; + } + Fe.cSwap2(&x2, &x3, &z2, &z3, swap); + z2 = z2.invert(); + x2 = x2.mul(z2); + if (x2.isZero()) { + return error.IdentityElement; + } + return @as(Curve25519, .{ .x = x2 }); + } + + /// Multiply a Curve25519 point by a scalar after "clamping" it. + /// Clamping forces the scalar to be a multiple of the cofactor in + /// order to prevent small subgroups attacks. This is the standard + /// way to use Curve25519 for a DH operation. + /// Return error.IdentityElement if the resulting point is + /// the identity element. + pub fn clampedMul(p: Curve25519, s: [32]u8) !Curve25519 { + var t: [32]u8 = s; + scalar.clamp(&t); + return ladder(p, t, 255); + } + + /// Multiply a Curve25519 point by a scalar without clamping it. + /// Return error.IdentityElement if the resulting point is + /// the identity element or error.WeakPublicKey if the public + /// key is a low-order point. + pub fn mul(p: Curve25519, s: [32]u8) !Curve25519 { + const cofactor = [_]u8{8} ++ [_]u8{0} ** 31; + _ = ladder(p, cofactor, 4) catch |_| return error.WeakPublicKey; + return ladder(p, s, 256); + } +}; + +test "curve25519" { + var s = [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, 8 }; + const p = try Curve25519.basePoint().clampedMul(s); + try p.rejectIdentity(); + var buf: [128]u8 = undefined; + const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{p.toBytes()}), "E6F2A4D1C28EE5C7AD0329268255A468AD407D2672824C0C0EB30EA6EF450145"); + const q = try p.clampedMul(s); + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{q.toBytes()}), "3614E119FFE55EC55B87D6B19971A9F4CBC78EFE80BEC55B96392BABCC712537"); + + try Curve25519.rejectNonCanonical(s); + s[31] |= 0x80; + std.testing.expectError(error.NonCanonical, Curve25519.rejectNonCanonical(s)); +} + +test "curve25519 small order check" { + var s: [32]u8 = [_]u8{1} ++ [_]u8{0} ** 31; + const small_order_ss: [7][32]u8 = .{ + .{ + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 0 (order 4) + }, + .{ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1 (order 1) + }, + .{ + 0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae, 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a, 0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd, 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00, // 325606250916557431795983626356110631294008115727848805560023387167927233504 (order 8) */ + }, + .{ + 0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24, 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b, 0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86, 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57, // 39382357235489614581723060781553021112529911719440698176882885853963445705823 (order 8) + }, + .{ + 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p-1 (order 2) + }, + .{ + 0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p (=0, order 4) + }, + .{ + 0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p+1 (=1, order 1) + }, + }; + for (small_order_ss) |small_order_s| { + std.testing.expectError(error.WeakPublicKey, Curve25519.fromBytes(small_order_s).mul(s)); + var extra = small_order_s; + extra[31] ^= 0x80; + std.testing.expectError(error.WeakPublicKey, Curve25519.fromBytes(extra).mul(s)); + var valid = small_order_s; + valid[31] = 0x40; + s[0] = 0; + std.testing.expectError(error.IdentityElement, Curve25519.fromBytes(valid).mul(s)); + } +} diff --git a/lib/std/crypto/25519/ed25519.zig b/lib/std/crypto/25519/ed25519.zig new file mode 100644 index 0000000000..c5baf37683 --- /dev/null +++ b/lib/std/crypto/25519/ed25519.zig @@ -0,0 +1,129 @@ +const std = @import("std"); +const fmt = std.fmt; +const mem = std.mem; +const Sha512 = std.crypto.Sha512; + +/// Ed25519 (EdDSA) signatures. +pub const Ed25519 = struct { + /// The underlying elliptic curve. + pub const Curve = @import("edwards25519.zig").Edwards25519; + /// Length (in bytes) of a seed required to create a key pair. + pub const seed_length = 32; + /// Length (in bytes) of a compressed key pair. + pub const keypair_length = 64; + /// Length (in bytes) of a compressed public key. + pub const public_length = 32; + /// Length (in bytes) of a signature. + pub const signature_length = 64; + /// Length (in bytes) of optional random bytes, for non-deterministic signatures. + pub const noise_length = 32; + + /// Derive a key pair from a secret seed. + pub fn createKeyPair(seed: [seed_length]u8) ![keypair_length]u8 { + var az: [Sha512.digest_length]u8 = undefined; + var h = Sha512.init(); + h.update(&seed); + h.final(&az); + const p = try Curve.basePoint().clampedMul(az[0..32].*); + var keypair: [keypair_length]u8 = undefined; + mem.copy(u8, &keypair, &seed); + mem.copy(u8, keypair[seed_length..], &p.toBytes()); + return keypair; + } + + /// Return the public key for a given key pair. + pub fn publicKey(key_pair: [keypair_length]u8) [public_length]u8 { + var public_key: [public_length]u8 = undefined; + mem.copy(u8, public_key[0..], key_pair[seed_length..]); + return public_key; + } + + /// Sign a message using a key pair, and optional random noise. + /// Having noise creates non-standard, non-deterministic signatures, + /// but has been proven to increase resilience against fault attacks. + pub fn sign(msg: []const u8, key_pair: [keypair_length]u8, noise: ?[noise_length]u8) ![signature_length]u8 { + const public_key = key_pair[32..]; + var az: [Sha512.digest_length]u8 = undefined; + var h = Sha512.init(); + h.update(key_pair[0..seed_length]); + h.final(&az); + + h = Sha512.init(); + if (noise) |*z| { + h.update(z); + } + h.update(az[32..]); + h.update(msg); + var nonce64: [64]u8 = undefined; + h.final(&nonce64); + const nonce = Curve.scalar.reduce64(nonce64); + const r = try Curve.basePoint().mul(nonce); + + var sig: [signature_length]u8 = undefined; + mem.copy(u8, sig[0..32], &r.toBytes()); + mem.copy(u8, sig[32..], public_key); + h = Sha512.init(); + h.update(&sig); + h.update(msg); + var hram64: [Sha512.digest_length]u8 = undefined; + h.final(&hram64); + const hram = Curve.scalar.reduce64(hram64); + + var x = az[0..32]; + Curve.scalar.clamp(x); + const s = Curve.scalar.mulAdd(hram, x.*, nonce); + mem.copy(u8, sig[32..], s[0..]); + return sig; + } + + /// Verify an Ed25519 signature given a message and a public key. + /// Returns error.InvalidSignature is the signature verification failed. + pub fn verify(sig: [signature_length]u8, msg: []const u8, public_key: [public_length]u8) !void { + const r = sig[0..32]; + const s = sig[32..64]; + try Curve.scalar.rejectNonCanonical(s.*); + try Curve.rejectNonCanonical(public_key); + const a = try Curve.fromBytes(public_key); + try a.rejectIdentity(); + + var h = Sha512.init(); + h.update(r); + h.update(&public_key); + h.update(msg); + var hram64: [Sha512.digest_length]u8 = undefined; + h.final(&hram64); + const hram = Curve.scalar.reduce64(hram64); + + const p = try a.neg().mul(hram); + const check = (try Curve.basePoint().mul(s.*)).add(p).toBytes(); + if (mem.timingSafeEqual(u8, &check, r) == false) { + return error.InvalidSignature; + } + } +}; + +test "ed25519 key pair creation" { + var seed: [32]u8 = undefined; + try fmt.hexToBytes(seed[0..], "8052030376d47112be7f73ed7a019293dd12ad910b654455798b4667d73de166"); + const key_pair = try Ed25519.createKeyPair(seed); + var buf: [256]u8 = undefined; + const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{key_pair}), "8052030376D47112BE7F73ED7A019293DD12AD910B654455798B4667D73DE1662D6F7455D97B4A3A10D7293909D1A4F2058CB9A370E43FA8154BB280DB839083"); + + const public_key = Ed25519.publicKey(key_pair); + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{public_key}), "2D6F7455D97B4A3A10D7293909D1A4F2058CB9A370E43FA8154BB280DB839083"); +} + +test "ed25519 signature" { + var seed: [32]u8 = undefined; + try fmt.hexToBytes(seed[0..], "8052030376d47112be7f73ed7a019293dd12ad910b654455798b4667d73de166"); + const key_pair = try Ed25519.createKeyPair(seed); + + const sig = try Ed25519.sign("test", key_pair, null); + var buf: [128]u8 = undefined; + const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{sig}), "10A442B4A80CC4225B154F43BEF28D2472CA80221951262EB8E0DF9091575E2687CC486E77263C3418C757522D54F84B0359236ABBBD4ACD20DC297FDCA66808"); + const public_key = Ed25519.publicKey(key_pair); + try Ed25519.verify(sig, "test", public_key); + std.testing.expectError(error.InvalidSignature, Ed25519.verify(sig, "TEST", public_key)); +} diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig new file mode 100644 index 0000000000..7e748609de --- /dev/null +++ b/lib/std/crypto/25519/edwards25519.zig @@ -0,0 +1,224 @@ +const std = @import("std"); +const fmt = std.fmt; + +/// Group operations over Edwards25519. +pub const Edwards25519 = struct { + /// The underlying prime field. + pub const Fe = @import("field25519.zig").Fe; + /// Field arithmetic mod the order of the main subgroup. + pub const scalar = @import("scalar25519.zig"); + + x: Fe, + y: Fe, + z: Fe, + t: Fe, + + is_base: bool = false, + + /// Decode an Edwards25519 point from its compressed (Y+sign) coordinates. + pub fn fromBytes(s: [32]u8) !Edwards25519 { + const z = Fe.one(); + const y = Fe.fromBytes(s); + var u = y.sq(); + var v = u.mul(Fe.edwards25519d()); + u = u.sub(z); + v = v.add(z); + const v3 = v.sq().mul(v); + var x = v3.sq().mul(v).mul(u).pow2523().mul(v3).mul(u); + const vxx = x.sq().mul(v); + const has_m_root = vxx.sub(u).isZero(); + const has_p_root = vxx.add(u).isZero(); + if ((@boolToInt(has_m_root) | @boolToInt(has_p_root)) == 0) { + return error.InvalidEncoding; + } + x.cMov(x.mul(Fe.sqrtm1()), 1 - @boolToInt(has_m_root)); + x.cMov(x.neg(), @boolToInt(x.isNegative()) ^ (s[31] >> 7)); + const t = x.mul(y); + return @as(Edwards25519, .{ .x = x, .y = y, .z = z, .t = t }); + } + + /// Encode an Edwards25519 point. + pub fn toBytes(p: Edwards25519) [32]u8 { + const zi = p.z.invert(); + var s = p.y.mul(zi).toBytes(); + s[31] ^= @as(u8, @boolToInt(p.x.mul(zi).isNegative())) << 7; + return s; + } + + /// Check that the encoding of a point is canonical. + pub fn rejectNonCanonical(s: [32]u8) !void { + return Fe.rejectNonCanonical(s, true); + } + + /// Return the Edwards25519 base point. + pub inline fn basePoint() Edwards25519 { + return .{ + .x = Fe{ .limbs = .{ 3990542415680775, 3398198340507945, 4322667446711068, 2814063955482877, 2839572215813860 } }, + .y = Fe{ .limbs = .{ 1801439850948184, 1351079888211148, 450359962737049, 900719925474099, 1801439850948198 } }, + .z = Fe.one(), + .t = Fe{ .limbs = .{ 1841354044333475, 16398895984059, 755974180946558, 900171276175154, 1821297809914039 } }, + .is_base = true, + }; + } + + inline fn identityElement() Edwards25519 { + return .{ .x = Fe.zero(), .y = Fe.one(), .z = Fe.one(), .t = Fe.zero() }; + } + + /// Reject the neutral element. + pub fn rejectIdentity(p: Edwards25519) !void { + if (p.x.isZero()) { + return error.IdentityElement; + } + } + + /// Flip the sign of the X coordinate. + pub inline fn neg(p: Edwards25519) Edwards25519 { + return .{ .x = p.x.neg(), .y = p.y, .z = p.z, .t = p.t.neg() }; + } + + /// Double an Edwards25519 point. + pub inline fn dbl(p: Edwards25519) Edwards25519 { + const t0 = p.x.add(p.y).sq(); + var x = p.x.sq(); + var z = p.y.sq(); + const y = z.add(x); + z = z.sub(x); + x = t0.sub(y); + const t = p.z.sq2().sub(z); + return .{ + .x = x.mul(t), + .y = y.mul(z), + .z = z.mul(t), + .t = x.mul(y), + }; + } + + /// Add two Edwards25519 points. + pub inline fn add(p: Edwards25519, q: Edwards25519) Edwards25519 { + const a = p.y.sub(p.x).mul(q.y.sub(q.x)); + const b = p.x.add(p.y).mul(q.x.add(q.y)); + const c = p.t.mul(q.t).mul(Fe.edwards25519d2()); + var d = p.z.mul(q.z); + d = d.add(d); + const x = b.sub(a); + const y = b.add(a); + const z = d.add(c); + const t = d.sub(c); + return .{ + .x = x.mul(t), + .y = y.mul(z), + .z = z.mul(t), + .t = x.mul(y), + }; + } + + inline fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void { + p.x.cMov(a.x, c); + p.y.cMov(a.y, c); + p.z.cMov(a.z, c); + p.t.cMov(a.t, c); + } + + inline fn pcSelect(pc: [16]Edwards25519, b: u8) Edwards25519 { + var t = Edwards25519.identityElement(); + comptime var i: u8 = 0; + inline while (i < 16) : (i += 1) { + t.cMov(pc[i], ((@intCast(usize, (b ^ i)) -% 1) >> 8) & 1); + } + return t; + } + + fn pcMul(pc: [16]Edwards25519, s: [32]u8) !Edwards25519 { + var q = Edwards25519.identityElement(); + var pos: usize = 252; + while (true) { + q = q.dbl().dbl().dbl().dbl(); + const b = (s[pos / 8] >> @intCast(u3, pos & 7)) & 0xf; + q = q.add(pcSelect(pc, b)); + if (pos == 0) break; + pos -= 4; + } + try q.rejectIdentity(); + return q; + } + + fn precompute(p: Edwards25519) [16]Edwards25519 { + var pc: [16]Edwards25519 = undefined; + pc[0] = Edwards25519.identityElement(); + pc[1] = p; + var i: usize = 2; + while (i < 16) : (i += 1) { + pc[i] = pc[i - 1].add(p); + } + return pc; + } + + fn _mul(p: Edwards25519, s: [32]u8) !Edwards25519 { + var pc: [16]Edwards25519 = undefined; + if (p.is_base) { + @setEvalBranchQuota(10000); + pc = comptime precompute(Edwards25519.basePoint()); + } else { + pc = precompute(p); + pc[4].rejectIdentity() catch |_| return error.WeakPublicKey; + } + return pcMul(pc, s); + } + + /// Multiply an Edwards25519 point by a scalar after "clamping" it. + /// Clamping forces the scalar to be a multiple of the cofactor in + /// order to prevent small subgroups attacks. + /// This is strongly recommended for DH operations. + /// Return error.WeakPublicKey if the resulting point is + /// the identity element. + pub fn clampedMul(p: Edwards25519, s: [32]u8) !Edwards25519 { + var t: [32]u8 = s; + scalar.clamp(&t); + return _mul(p, t); + } + + /// Multiply an Edwards25519 point by a scalar without clamping it. + /// Return error.WeakPublicKey if the resulting point is + /// the identity element. + pub fn mul(p: Edwards25519, s: [32]u8) !Edwards25519 { + return _mul(p, s); + } +}; + +test "edwards25519 packing/unpacking" { + const s = [_]u8{170} ++ [_]u8{0} ** 31; + var b = Edwards25519.basePoint(); + const pk = try b.mul(s); + var buf: [128]u8 = undefined; + const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{pk.toBytes()}), "074BC7E0FCBD587FDBC0969444245FADC562809C8F6E97E949AF62484B5B81A6"); + + const small_order_ss: [7][32]u8 = .{ + .{ + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 0 (order 4) + }, + .{ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1 (order 1) + }, + .{ + 0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2, 0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x05, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38, 0x02, 0x88, 0x6d, 0x53, 0xfc, 0x05, // 270738550114484064931822528722565878893680426757531351946374360975030340202(order 8) + }, + .{ + 0xc7, 0x17, 0x6a, 0x70, 0x3d, 0x4d, 0xd8, 0x4f, 0xba, 0x3c, 0x0b, 0x76, 0x0d, 0x10, 0x67, 0x0f, 0x2a, 0x20, 0x53, 0xfa, 0x2c, 0x39, 0xcc, 0xc6, 0x4e, 0xc7, 0xfd, 0x77, 0x92, 0xac, 0x03, 0x7a, // 55188659117513257062467267217118295137698188065244968500265048394206261417927 (order 8) + }, + .{ + 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p-1 (order 2) + }, + .{ + 0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p (=0, order 4) + }, + .{ + 0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p+1 (=1, order 1) + }, + }; + for (small_order_ss) |small_order_s| { + const small_p = try Edwards25519.fromBytes(small_order_s); + std.testing.expectError(error.WeakPublicKey, small_p.mul(s)); + } +} diff --git a/lib/std/crypto/25519/field25519.zig b/lib/std/crypto/25519/field25519.zig new file mode 100644 index 0000000000..9061cbf011 --- /dev/null +++ b/lib/std/crypto/25519/field25519.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 = undefined, + + 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/ristretto255.zig b/lib/std/crypto/25519/ristretto255.zig new file mode 100644 index 0000000000..71fa876c4f --- /dev/null +++ b/lib/std/crypto/25519/ristretto255.zig @@ -0,0 +1,153 @@ +const std = @import("std"); +const fmt = std.fmt; + +/// Group operations over Edwards25519. +pub const Ristretto255 = struct { + /// The underlying elliptic curve. + pub const Curve = @import("edwards25519.zig").Edwards25519; + /// The underlying prime field. + pub const Fe = Curve.Fe; + /// Field arithmetic mod the order of the main subgroup. + pub const scalar = Curve.scalar; + + p: Curve = undefined, + + fn sqrtRatioM1(u: Fe, v: Fe) !Fe { + const v3 = v.sq().mul(v); // v3 = v^3 + var x = v3.sq().mul(u).mul(v). // x = uv^7 + pow2523().mul(v3).mul(u); // x = uv^3(uv^7)^((q-5)/8) + const vxx = x.sq().mul(v); // vx^2 + const m_root_check = vxx.sub(u); // vx^2-u + const p_root_check = vxx.add(u); // vx^2+u + const f_root_check = u.mul(Fe.sqrtm1()).add(vxx); // vx^2+u*sqrt(-1) + const has_m_root = m_root_check.isZero(); + const has_p_root = p_root_check.isZero(); + const has_f_root = f_root_check.isZero(); + const x_sqrtm1 = x.mul(Fe.sqrtm1()); // x*sqrt(-1) + x.cMov(x_sqrtm1, @boolToInt(has_p_root) | @boolToInt(has_f_root)); + x = x.abs(); + if ((@boolToInt(has_m_root) | @boolToInt(has_p_root)) == 0) { + return error.NoRoot; + } + return x; + } + + fn rejectNonCanonical(s: [32]u8) !void { + if ((s[0] & 1) != 0) { + return error.NonCanonical; + } + try Fe.rejectNonCanonical(s, false); + } + + /// Reject the neutral element. + pub inline fn rejectIdentity(p: Ristretto255) !void { + return p.p.rejectIdentity(); + } + + /// Return the base point (Ristretto is a curve in desguise). + pub inline fn basePoint() Ristretto255 { + return .{ .p = Curve.basePoint() }; + } + + /// Decode a Ristretto255 representative. + pub fn fromBytes(s: [32]u8) !Ristretto255 { + try rejectNonCanonical(s); + const s_ = Fe.fromBytes(s); + const ss = s_.sq(); // s^2 + const u1_ = Fe.one().sub(ss); // (1-s^2) + const u1u1 = u1_.sq(); // (1-s^2)^2 + const u2_ = Fe.one().add(ss); // (1+s^2) + const u2u2 = u2_.sq(); // (1+s^2)^2 + const v = Fe.edwards25519d().mul(u1u1).neg().sub(u2u2); // -(d*u1^2)-u2^2 + const v_u2u2 = v.mul(u2u2); // v*u2^2 + const inv_sqrt = sqrtRatioM1(Fe.one(), v_u2u2) catch |e| { + return error.InvalidEncoding; + }; + var x = inv_sqrt.mul(u2_); + const y = inv_sqrt.mul(x).mul(v).mul(u1_); + x = x.mul(s_); + x = x.add(x).abs(); + const t = x.mul(y); + if ((@boolToInt(t.isNegative()) | @boolToInt(y.isZero())) != 0) { + return error.InvalidEncoding; + } + const p: Curve = .{ + .x = x, + .y = y, + .z = Fe.one(), + .t = t, + }; + return @as(Ristretto255, .{ .p = p }); + } + + /// Encode to a Ristretto255 representative. + pub fn toBytes(e: Ristretto255) [32]u8 { + const p = &e.p; + var u1_ = p.z.add(p.y); // Z+Y + const zmy = p.z.sub(p.y); // Z-Y + u1_ = u1_.mul(zmy); // (Z+Y)*(Z-Y) + const u2_ = p.x.mul(p.y); // X*Y + + const u1_u2u2 = u2_.sq().mul(u1_); // u1*u2^2 + + const inv_sqrt = sqrtRatioM1(Fe.one(), u1_u2u2) catch unreachable; + const den1 = inv_sqrt.mul(u1_); + const den2 = inv_sqrt.mul(u2_); + const z_inv = den1.mul(den2).mul(p.t); // den1*den2*T + + const ix = p.x.mul(Fe.sqrtm1()); // X*sqrt(-1) + const iy = p.y.mul(Fe.sqrtm1()); // Y*sqrt(-1) + const eden = den1.mul(Fe.edwards25519sqrtamd()); // den1/sqrt(a-d) + + const t_z_inv = p.t.mul(z_inv); // T*z_inv + const rotate = @boolToInt(t_z_inv.isNegative()); + + var x = p.x; + var y = p.y; + var den_inv = den2; + + x.cMov(iy, rotate); + y.cMov(ix, rotate); + den_inv.cMov(eden, rotate); + + const x_z_inv = x.mul(z_inv); + const yneg = y.neg(); + y.cMov(yneg, @boolToInt(x_z_inv.isNegative())); + + return p.z.sub(y).mul(den_inv).abs().toBytes(); + } + + /// Double a Ristretto255 element. + pub inline fn dbl(p: Ristretto255) Ristretto255 { + return .{ .p = p.p.dbl() }; + } + + /// Add two Ristretto255 elements. + pub inline fn add(p: Ristretto255, q: Ristretto255) Ristretto255 { + return .{ .p = p.p.add(q.p) }; + } + + /// Multiply a Ristretto255 element with a scalar. + /// Return error.WeakPublicKey if the resulting element is + /// the identity element. + pub inline fn mul(p: Ristretto255, s: [32]u8) !Ristretto255 { + return @as(Ristretto255, .{ .p = try p.p.mul(s) }); + } +}; + +test "ristretto255" { + const p = Ristretto255.basePoint(); + var buf: [256]u8 = undefined; + const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{p.toBytes()}), "E2F2AE0A6ABC4E71A884A961C500515F58E30B6AA582DD8DB6A65945E08D2D76"); + + var r: [32]u8 = undefined; + try fmt.hexToBytes(r[0..], "6a493210f7499cd17fecb510ae0cea23a110e8d5b901f8acadd3095c73a3b919"); + var q = try Ristretto255.fromBytes(r); + q = q.dbl().add(p); + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{q.toBytes()}), "E882B131016B52C1D3337080187CF768423EFCCBB517BB495AB812C4160FF44E"); + + const s = [_]u8{15} ++ [_]u8{0} ** 31; + const w = try p.mul(s); + std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{w.toBytes()}), "E0C418F7C8D9C4CDD7395B93EA124F3AD99021BB681DFC3302A9D99A2E53E64E"); +} diff --git a/lib/std/crypto/25519/scalar25519.zig b/lib/std/crypto/25519/scalar25519.zig new file mode 100644 index 0000000000..a94e6531dc --- /dev/null +++ b/lib/std/crypto/25519/scalar25519.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 "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/x25519.zig b/lib/std/crypto/25519/x25519.zig new file mode 100644 index 0000000000..55c860d13e --- /dev/null +++ b/lib/std/crypto/25519/x25519.zig @@ -0,0 +1,146 @@ +const std = @import("std"); +const mem = std.mem; +const fmt = std.fmt; + +/// X25519 DH function. +pub const X25519 = struct { + /// The underlying elliptic curve. + pub const Curve = @import("curve25519.zig").Curve25519; + /// Length (in bytes) of a secret key. + pub const secret_length = 32; + /// Length (in bytes) of the output of the DH function. + pub const minimum_key_length = 32; + + /// Compute the public key for a given private key. + pub fn createPublicKey(public_key: []u8, private_key: []const u8) bool { + std.debug.assert(private_key.len >= minimum_key_length); + std.debug.assert(public_key.len >= minimum_key_length); + var s: [32]u8 = undefined; + mem.copy(u8, &s, private_key[0..32]); + if (Curve.basePoint().clampedMul(s)) |q| { + mem.copy(u8, public_key, q.toBytes()[0..]); + return true; + } else |_| { + return false; + } + } + + /// Compute the scalar product of a public key and a secret scalar. + /// Note that the output should not be used as a shared secret without + /// hashing it first. + pub fn create(out: []u8, private_key: []const u8, public_key: []const u8) bool { + std.debug.assert(out.len >= secret_length); + std.debug.assert(private_key.len >= minimum_key_length); + std.debug.assert(public_key.len >= minimum_key_length); + var s: [32]u8 = undefined; + var b: [32]u8 = undefined; + mem.copy(u8, &s, private_key[0..32]); + mem.copy(u8, &b, public_key[0..32]); + if (Curve.fromBytes(b).clampedMul(s)) |q| { + mem.copy(u8, out, q.toBytes()[0..]); + return true; + } else |_| { + return false; + } + } +}; + +test "x25519 public key calculation from secret key" { + var sk: [32]u8 = undefined; + var pk_expected: [32]u8 = undefined; + var pk_calculated: [32]u8 = undefined; + try fmt.hexToBytes(sk[0..], "8052030376d47112be7f73ed7a019293dd12ad910b654455798b4667d73de166"); + try fmt.hexToBytes(pk_expected[0..], "f1814f0e8ff1043d8a44d25babff3cedcae6c22c3edaa48f857ae70de2baae50"); + std.testing.expect(X25519.createPublicKey(pk_calculated[0..], &sk)); + std.testing.expect(std.mem.eql(u8, &pk_calculated, &pk_expected)); +} + +test "x25519 rfc7748 vector1" { + const secret_key = "\xa5\x46\xe3\x6b\xf0\x52\x7c\x9d\x3b\x16\x15\x4b\x82\x46\x5e\xdd\x62\x14\x4c\x0a\xc1\xfc\x5a\x18\x50\x6a\x22\x44\xba\x44\x9a\xc4"; + const public_key = "\xe6\xdb\x68\x67\x58\x30\x30\xdb\x35\x94\xc1\xa4\x24\xb1\x5f\x7c\x72\x66\x24\xec\x26\xb3\x35\x3b\x10\xa9\x03\xa6\xd0\xab\x1c\x4c"; + + const expected_output = "\xc3\xda\x55\x37\x9d\xe9\xc6\x90\x8e\x94\xea\x4d\xf2\x8d\x08\x4f\x32\xec\xcf\x03\x49\x1c\x71\xf7\x54\xb4\x07\x55\x77\xa2\x85\x52"; + + var output: [32]u8 = undefined; + + std.testing.expect(X25519.create(output[0..], secret_key, public_key)); + std.testing.expect(std.mem.eql(u8, &output, expected_output)); +} + +test "x25519 rfc7748 vector2" { + const secret_key = "\x4b\x66\xe9\xd4\xd1\xb4\x67\x3c\x5a\xd2\x26\x91\x95\x7d\x6a\xf5\xc1\x1b\x64\x21\xe0\xea\x01\xd4\x2c\xa4\x16\x9e\x79\x18\xba\x0d"; + const public_key = "\xe5\x21\x0f\x12\x78\x68\x11\xd3\xf4\xb7\x95\x9d\x05\x38\xae\x2c\x31\xdb\xe7\x10\x6f\xc0\x3c\x3e\xfc\x4c\xd5\x49\xc7\x15\xa4\x93"; + + const expected_output = "\x95\xcb\xde\x94\x76\xe8\x90\x7d\x7a\xad\xe4\x5c\xb4\xb8\x73\xf8\x8b\x59\x5a\x68\x79\x9f\xa1\x52\xe6\xf8\xf7\x64\x7a\xac\x79\x57"; + + var output: [32]u8 = undefined; + + std.testing.expect(X25519.create(output[0..], secret_key, public_key)); + std.testing.expect(std.mem.eql(u8, &output, expected_output)); +} + +test "x25519 rfc7748 one iteration" { + const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00".*; + const expected_output = "\x42\x2c\x8e\x7a\x62\x27\xd7\xbc\xa1\x35\x0b\x3e\x2b\xb7\x27\x9f\x78\x97\xb8\x7b\xb6\x85\x4b\x78\x3c\x60\xe8\x03\x11\xae\x30\x79"; + + var k: [32]u8 = initial_value; + var u: [32]u8 = initial_value; + + var i: usize = 0; + while (i < 1) : (i += 1) { + var output: [32]u8 = undefined; + std.testing.expect(X25519.create(output[0..], &k, &u)); + + std.mem.copy(u8, u[0..], k[0..]); + std.mem.copy(u8, k[0..], output[0..]); + } + + std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); +} + +test "x25519 rfc7748 1,000 iterations" { + // These iteration tests are slow so we always skip them. Results have been verified. + if (true) { + return error.SkipZigTest; + } + + const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"; + const expected_output = "\x68\x4c\xf5\x9b\xa8\x33\x09\x55\x28\x00\xef\x56\x6f\x2f\x4d\x3c\x1c\x38\x87\xc4\x93\x60\xe3\x87\x5f\x2e\xb9\x4d\x99\x53\x2c\x51"; + + var k: [32]u8 = initial_value.*; + var u: [32]u8 = initial_value.*; + + var i: usize = 0; + while (i < 1000) : (i += 1) { + var output: [32]u8 = undefined; + std.testing.expect(X25519.create(output[0..], &k, &u)); + + std.mem.copy(u8, u[0..], k[0..]); + std.mem.copy(u8, k[0..], output[0..]); + } + + std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); +} + +test "x25519 rfc7748 1,000,000 iterations" { + if (true) { + return error.SkipZigTest; + } + + const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"; + const expected_output = "\x7c\x39\x11\xe0\xab\x25\x86\xfd\x86\x44\x97\x29\x7e\x57\x5e\x6f\x3b\xc6\x01\xc0\x88\x3c\x30\xdf\x5f\x4d\xd2\xd2\x4f\x66\x54\x24"; + + var k: [32]u8 = initial_value.*; + var u: [32]u8 = initial_value.*; + + var i: usize = 0; + while (i < 1000000) : (i += 1) { + var output: [32]u8 = undefined; + std.testing.expect(X25519.create(output[0..], &k, &u)); + + std.mem.copy(u8, u[0..], k[0..]); + std.mem.copy(u8, k[0..], output[0..]); + } + + std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); +} diff --git a/lib/std/crypto/x25519.zig b/lib/std/crypto/x25519.zig deleted file mode 100644 index e2e2bf90e5..0000000000 --- a/lib/std/crypto/x25519.zig +++ /dev/null @@ -1,675 +0,0 @@ -// Translated from monocypher which is licensed under CC-0/BSD-3. -// -// https://monocypher.org/ - -const std = @import("../std.zig"); -const builtin = @import("builtin"); -const fmt = std.fmt; - -const Endian = builtin.Endian; -const readIntLittle = std.mem.readIntLittle; -const writeIntLittle = std.mem.writeIntLittle; - -// Based on Supercop's ref10 implementation. -pub const X25519 = struct { - pub const secret_length = 32; - pub const minimum_key_length = 32; - - fn trimScalar(s: []u8) void { - s[0] &= 248; - s[31] &= 127; - s[31] |= 64; - } - - fn scalarBit(s: []const u8, i: usize) i32 { - return (s[i >> 3] >> @intCast(u3, i & 7)) & 1; - } - - pub fn create(out: []u8, private_key: []const u8, public_key: []const u8) bool { - std.debug.assert(out.len >= secret_length); - std.debug.assert(private_key.len >= minimum_key_length); - std.debug.assert(public_key.len >= minimum_key_length); - - var storage: [7]Fe = undefined; - var x1 = &storage[0]; - var x2 = &storage[1]; - var z2 = &storage[2]; - var x3 = &storage[3]; - var z3 = &storage[4]; - var t0 = &storage[5]; - var t1 = &storage[6]; - - // computes the scalar product - Fe.fromBytes(x1, public_key); - - // restrict the possible scalar values - var e: [32]u8 = undefined; - for (e[0..]) |_, i| { - e[i] = private_key[i]; - } - trimScalar(e[0..]); - - // computes the actual scalar product (the result is in x2 and z2) - - // Montgomery ladder - // In projective coordinates, to avoid divisions: x = X / Z - // We don't care about the y coordinate, it's only 1 bit of information - Fe.init1(x2); - Fe.init0(z2); // "zero" point - Fe.copy(x3, x1); - Fe.init1(z3); - - var swap: i32 = 0; - var pos: isize = 254; - while (pos >= 0) : (pos -= 1) { - // constant time conditional swap before ladder step - const b = scalarBit(&e, @intCast(usize, pos)); - swap ^= b; // xor trick avoids swapping at the end of the loop - Fe.cswap(x2, x3, swap); - Fe.cswap(z2, z3, swap); - swap = b; // anticipates one last swap after the loop - - // Montgomery ladder step: replaces (P2, P3) by (P2*2, P2+P3) - // with differential addition - Fe.sub(t0, x3, z3); - Fe.sub(t1, x2, z2); - Fe.add(x2, x2, z2); - Fe.add(z2, x3, z3); - Fe.mul(z3, t0, x2); - Fe.mul(z2, z2, t1); - Fe.sq(t0, t1); - Fe.sq(t1, x2); - Fe.add(x3, z3, z2); - Fe.sub(z2, z3, z2); - Fe.mul(x2, t1, t0); - Fe.sub(t1, t1, t0); - Fe.sq(z2, z2); - Fe.mulSmall(z3, t1, 121666); - Fe.sq(x3, x3); - Fe.add(t0, t0, z3); - Fe.mul(z3, x1, z2); - Fe.mul(z2, t1, t0); - } - - // last swap is necessary to compensate for the xor trick - // Note: after this swap, P3 == P2 + P1. - Fe.cswap(x2, x3, swap); - Fe.cswap(z2, z3, swap); - - // normalises the coordinates: x == X / Z - Fe.invert(z2, z2); - Fe.mul(x2, x2, z2); - Fe.toBytes(out, x2); - - x1.secureZero(); - x2.secureZero(); - x3.secureZero(); - t0.secureZero(); - t1.secureZero(); - z2.secureZero(); - z3.secureZero(); - std.mem.secureZero(u8, e[0..]); - - // Returns false if the output is all zero - // (happens with some malicious public keys) - return !zerocmp(u8, out); - } - - pub fn createPublicKey(public_key: []u8, private_key: []const u8) bool { - var base_point = [_]u8{9} ++ [_]u8{0} ** 31; - return create(public_key, private_key, &base_point); - } -}; - -// Constant time compare to zero. -fn zerocmp(comptime T: type, a: []const T) bool { - var s: T = 0; - for (a) |b| { - s |= b; - } - return s == 0; -} - -//////////////////////////////////// -/// Arithmetic modulo 2^255 - 19 /// -//////////////////////////////////// -// Taken from Supercop's ref10 implementation. -// A bit bigger than TweetNaCl, over 4 times faster. - -// field element -const Fe = struct { - b: [10]i32, - - fn secureZero(self: *Fe) void { - std.mem.secureZero(u8, @ptrCast([*]u8, self)[0..@sizeOf(Fe)]); - } - - fn init0(h: *Fe) void { - for (h.b) |*e| { - e.* = 0; - } - } - - fn init1(h: *Fe) void { - for (h.b[1..]) |*e| { - e.* = 0; - } - h.b[0] = 1; - } - - fn copy(h: *Fe, f: *const Fe) void { - for (h.b) |_, i| { - h.b[i] = f.b[i]; - } - } - - fn neg(h: *Fe, f: *const Fe) void { - for (h.b) |_, i| { - h.b[i] = -f.b[i]; - } - } - - fn add(h: *Fe, f: *const Fe, g: *const Fe) void { - for (h.b) |_, i| { - h.b[i] = f.b[i] + g.b[i]; - } - } - - fn sub(h: *Fe, f: *const Fe, g: *const Fe) void { - for (h.b) |_, i| { - h.b[i] = f.b[i] - g.b[i]; - } - } - - fn cswap(f: *Fe, g: *Fe, b: i32) void { - for (f.b) |_, i| { - const x = (f.b[i] ^ g.b[i]) & -b; - f.b[i] ^= x; - g.b[i] ^= x; - } - } - - fn ccopy(f: *Fe, g: *const Fe, b: i32) void { - for (f.b) |_, i| { - const x = (f.b[i] ^ g.b[i]) & -b; - f.b[i] ^= x; - } - } - - inline fn carryRound(c: []i64, t: []i64, comptime i: comptime_int, comptime shift: comptime_int, comptime mult: comptime_int) void { - const j = (i + 1) % 10; - - c[i] = (t[i] + (@as(i64, 1) << shift)) >> (shift + 1); - t[j] += c[i] * mult; - t[i] -= c[i] * (@as(i64, 1) << (shift + 1)); - } - - fn carry1(h: *Fe, t: []i64) void { - var c: [10]i64 = undefined; - - var sc = c[0..]; - var st = t[0..]; - - carryRound(sc, st, 9, 24, 19); - carryRound(sc, st, 1, 24, 1); - carryRound(sc, st, 3, 24, 1); - carryRound(sc, st, 5, 24, 1); - carryRound(sc, st, 7, 24, 1); - carryRound(sc, st, 0, 25, 1); - carryRound(sc, st, 2, 25, 1); - carryRound(sc, st, 4, 25, 1); - carryRound(sc, st, 6, 25, 1); - carryRound(sc, st, 8, 25, 1); - - for (h.b) |_, i| { - h.b[i] = @intCast(i32, t[i]); - } - } - - fn carry2(h: *Fe, t: []i64) void { - var c: [10]i64 = undefined; - - var sc = c[0..]; - var st = t[0..]; - - carryRound(sc, st, 0, 25, 1); - carryRound(sc, st, 4, 25, 1); - carryRound(sc, st, 1, 24, 1); - carryRound(sc, st, 5, 24, 1); - carryRound(sc, st, 2, 25, 1); - carryRound(sc, st, 6, 25, 1); - carryRound(sc, st, 3, 24, 1); - carryRound(sc, st, 7, 24, 1); - carryRound(sc, st, 4, 25, 1); - carryRound(sc, st, 8, 25, 1); - carryRound(sc, st, 9, 24, 19); - carryRound(sc, st, 0, 25, 1); - - for (h.b) |_, i| { - h.b[i] = @intCast(i32, t[i]); - } - } - - fn fromBytes(h: *Fe, s: []const u8) void { - std.debug.assert(s.len >= 32); - - var t: [10]i64 = undefined; - - t[0] = readIntLittle(u32, s[0..4]); - t[1] = @as(u32, readIntLittle(u24, s[4..7])) << 6; - t[2] = @as(u32, readIntLittle(u24, s[7..10])) << 5; - t[3] = @as(u32, readIntLittle(u24, s[10..13])) << 3; - t[4] = @as(u32, readIntLittle(u24, s[13..16])) << 2; - t[5] = readIntLittle(u32, s[16..20]); - t[6] = @as(u32, readIntLittle(u24, s[20..23])) << 7; - t[7] = @as(u32, readIntLittle(u24, s[23..26])) << 5; - t[8] = @as(u32, readIntLittle(u24, s[26..29])) << 4; - t[9] = (@as(u32, readIntLittle(u24, s[29..32])) & 0x7fffff) << 2; - - carry1(h, t[0..]); - } - - fn mulSmall(h: *Fe, f: *const Fe, comptime g: comptime_int) void { - var t: [10]i64 = undefined; - - for (t[0..]) |_, i| { - t[i] = @as(i64, f.b[i]) * g; - } - - carry1(h, t[0..]); - } - - fn mul(h: *Fe, f1: *const Fe, g1: *const Fe) void { - const f = f1.b; - const g = g1.b; - - var F: [10]i32 = undefined; - var G: [10]i32 = undefined; - - F[1] = f[1] * 2; - F[3] = f[3] * 2; - F[5] = f[5] * 2; - F[7] = f[7] * 2; - F[9] = f[9] * 2; - - G[1] = g[1] * 19; - G[2] = g[2] * 19; - G[3] = g[3] * 19; - G[4] = g[4] * 19; - G[5] = g[5] * 19; - G[6] = g[6] * 19; - G[7] = g[7] * 19; - G[8] = g[8] * 19; - G[9] = g[9] * 19; - - // t's become h - var t: [10]i64 = undefined; - - t[0] = f[0] * @as(i64, g[0]) + F[1] * @as(i64, G[9]) + f[2] * @as(i64, G[8]) + F[3] * @as(i64, G[7]) + f[4] * @as(i64, G[6]) + F[5] * @as(i64, G[5]) + f[6] * @as(i64, G[4]) + F[7] * @as(i64, G[3]) + f[8] * @as(i64, G[2]) + F[9] * @as(i64, G[1]); - t[1] = f[0] * @as(i64, g[1]) + f[1] * @as(i64, g[0]) + f[2] * @as(i64, G[9]) + f[3] * @as(i64, G[8]) + f[4] * @as(i64, G[7]) + f[5] * @as(i64, G[6]) + f[6] * @as(i64, G[5]) + f[7] * @as(i64, G[4]) + f[8] * @as(i64, G[3]) + f[9] * @as(i64, G[2]); - t[2] = f[0] * @as(i64, g[2]) + F[1] * @as(i64, g[1]) + f[2] * @as(i64, g[0]) + F[3] * @as(i64, G[9]) + f[4] * @as(i64, G[8]) + F[5] * @as(i64, G[7]) + f[6] * @as(i64, G[6]) + F[7] * @as(i64, G[5]) + f[8] * @as(i64, G[4]) + F[9] * @as(i64, G[3]); - t[3] = f[0] * @as(i64, g[3]) + f[1] * @as(i64, g[2]) + f[2] * @as(i64, g[1]) + f[3] * @as(i64, g[0]) + f[4] * @as(i64, G[9]) + f[5] * @as(i64, G[8]) + f[6] * @as(i64, G[7]) + f[7] * @as(i64, G[6]) + f[8] * @as(i64, G[5]) + f[9] * @as(i64, G[4]); - t[4] = f[0] * @as(i64, g[4]) + F[1] * @as(i64, g[3]) + f[2] * @as(i64, g[2]) + F[3] * @as(i64, g[1]) + f[4] * @as(i64, g[0]) + F[5] * @as(i64, G[9]) + f[6] * @as(i64, G[8]) + F[7] * @as(i64, G[7]) + f[8] * @as(i64, G[6]) + F[9] * @as(i64, G[5]); - t[5] = f[0] * @as(i64, g[5]) + f[1] * @as(i64, g[4]) + f[2] * @as(i64, g[3]) + f[3] * @as(i64, g[2]) + f[4] * @as(i64, g[1]) + f[5] * @as(i64, g[0]) + f[6] * @as(i64, G[9]) + f[7] * @as(i64, G[8]) + f[8] * @as(i64, G[7]) + f[9] * @as(i64, G[6]); - t[6] = f[0] * @as(i64, g[6]) + F[1] * @as(i64, g[5]) + f[2] * @as(i64, g[4]) + F[3] * @as(i64, g[3]) + f[4] * @as(i64, g[2]) + F[5] * @as(i64, g[1]) + f[6] * @as(i64, g[0]) + F[7] * @as(i64, G[9]) + f[8] * @as(i64, G[8]) + F[9] * @as(i64, G[7]); - t[7] = f[0] * @as(i64, g[7]) + f[1] * @as(i64, g[6]) + f[2] * @as(i64, g[5]) + f[3] * @as(i64, g[4]) + f[4] * @as(i64, g[3]) + f[5] * @as(i64, g[2]) + f[6] * @as(i64, g[1]) + f[7] * @as(i64, g[0]) + f[8] * @as(i64, G[9]) + f[9] * @as(i64, G[8]); - t[8] = f[0] * @as(i64, g[8]) + F[1] * @as(i64, g[7]) + f[2] * @as(i64, g[6]) + F[3] * @as(i64, g[5]) + f[4] * @as(i64, g[4]) + F[5] * @as(i64, g[3]) + f[6] * @as(i64, g[2]) + F[7] * @as(i64, g[1]) + f[8] * @as(i64, g[0]) + F[9] * @as(i64, G[9]); - t[9] = f[0] * @as(i64, g[9]) + f[1] * @as(i64, g[8]) + f[2] * @as(i64, g[7]) + f[3] * @as(i64, g[6]) + f[4] * @as(i64, g[5]) + f[5] * @as(i64, g[4]) + f[6] * @as(i64, g[3]) + f[7] * @as(i64, g[2]) + f[8] * @as(i64, g[1]) + f[9] * @as(i64, g[0]); - - carry2(h, t[0..]); - } - - // we could use Fe.mul() for this, but this is significantly faster - fn sq(h: *Fe, fz: *const Fe) void { - const f0 = fz.b[0]; - const f1 = fz.b[1]; - const f2 = fz.b[2]; - const f3 = fz.b[3]; - const f4 = fz.b[4]; - const f5 = fz.b[5]; - const f6 = fz.b[6]; - const f7 = fz.b[7]; - const f8 = fz.b[8]; - const f9 = fz.b[9]; - - const f0_2 = f0 * 2; - const f1_2 = f1 * 2; - const f2_2 = f2 * 2; - const f3_2 = f3 * 2; - const f4_2 = f4 * 2; - const f5_2 = f5 * 2; - const f6_2 = f6 * 2; - const f7_2 = f7 * 2; - const f5_38 = f5 * 38; - const f6_19 = f6 * 19; - const f7_38 = f7 * 38; - const f8_19 = f8 * 19; - const f9_38 = f9 * 38; - - var t: [10]i64 = undefined; - - t[0] = f0 * @as(i64, f0) + f1_2 * @as(i64, f9_38) + f2_2 * @as(i64, f8_19) + f3_2 * @as(i64, f7_38) + f4_2 * @as(i64, f6_19) + f5 * @as(i64, f5_38); - t[1] = f0_2 * @as(i64, f1) + f2 * @as(i64, f9_38) + f3_2 * @as(i64, f8_19) + f4 * @as(i64, f7_38) + f5_2 * @as(i64, f6_19); - t[2] = f0_2 * @as(i64, f2) + f1_2 * @as(i64, f1) + f3_2 * @as(i64, f9_38) + f4_2 * @as(i64, f8_19) + f5_2 * @as(i64, f7_38) + f6 * @as(i64, f6_19); - t[3] = f0_2 * @as(i64, f3) + f1_2 * @as(i64, f2) + f4 * @as(i64, f9_38) + f5_2 * @as(i64, f8_19) + f6 * @as(i64, f7_38); - t[4] = f0_2 * @as(i64, f4) + f1_2 * @as(i64, f3_2) + f2 * @as(i64, f2) + f5_2 * @as(i64, f9_38) + f6_2 * @as(i64, f8_19) + f7 * @as(i64, f7_38); - t[5] = f0_2 * @as(i64, f5) + f1_2 * @as(i64, f4) + f2_2 * @as(i64, f3) + f6 * @as(i64, f9_38) + f7_2 * @as(i64, f8_19); - t[6] = f0_2 * @as(i64, f6) + f1_2 * @as(i64, f5_2) + f2_2 * @as(i64, f4) + f3_2 * @as(i64, f3) + f7_2 * @as(i64, f9_38) + f8 * @as(i64, f8_19); - t[7] = f0_2 * @as(i64, f7) + f1_2 * @as(i64, f6) + f2_2 * @as(i64, f5) + f3_2 * @as(i64, f4) + f8 * @as(i64, f9_38); - t[8] = f0_2 * @as(i64, f8) + f1_2 * @as(i64, f7_2) + f2_2 * @as(i64, f6) + f3_2 * @as(i64, f5_2) + f4 * @as(i64, f4) + f9 * @as(i64, f9_38); - t[9] = f0_2 * @as(i64, f9) + f1_2 * @as(i64, f8) + f2_2 * @as(i64, f7) + f3_2 * @as(i64, f6) + f4 * @as(i64, f5_2); - - carry2(h, t[0..]); - } - - fn sq2(h: *Fe, f: *const Fe) void { - Fe.sq(h, f); - Fe.mul_small(h, h, 2); - } - - // This could be simplified, but it would be slower - fn invert(out: *Fe, z: *const Fe) void { - var i: usize = undefined; - - var t: [4]Fe = undefined; - var t0 = &t[0]; - var t1 = &t[1]; - var t2 = &t[2]; - var t3 = &t[3]; - - Fe.sq(t0, z); - Fe.sq(t1, t0); - Fe.sq(t1, t1); - Fe.mul(t1, z, t1); - Fe.mul(t0, t0, t1); - - Fe.sq(t2, t0); - Fe.mul(t1, t1, t2); - - Fe.sq(t2, t1); - i = 1; - while (i < 5) : (i += 1) Fe.sq(t2, t2); - Fe.mul(t1, t2, t1); - - Fe.sq(t2, t1); - i = 1; - while (i < 10) : (i += 1) Fe.sq(t2, t2); - Fe.mul(t2, t2, t1); - - Fe.sq(t3, t2); - i = 1; - while (i < 20) : (i += 1) Fe.sq(t3, t3); - Fe.mul(t2, t3, t2); - - Fe.sq(t2, t2); - i = 1; - while (i < 10) : (i += 1) Fe.sq(t2, t2); - Fe.mul(t1, t2, t1); - - Fe.sq(t2, t1); - i = 1; - while (i < 50) : (i += 1) Fe.sq(t2, t2); - Fe.mul(t2, t2, t1); - - Fe.sq(t3, t2); - i = 1; - while (i < 100) : (i += 1) Fe.sq(t3, t3); - Fe.mul(t2, t3, t2); - - Fe.sq(t2, t2); - i = 1; - while (i < 50) : (i += 1) Fe.sq(t2, t2); - Fe.mul(t1, t2, t1); - - Fe.sq(t1, t1); - i = 1; - while (i < 5) : (i += 1) Fe.sq(t1, t1); - Fe.mul(out, t1, t0); - - t0.secureZero(); - t1.secureZero(); - t2.secureZero(); - t3.secureZero(); - } - - // This could be simplified, but it would be slower - fn pow22523(out: *Fe, z: *const Fe) void { - var i: usize = undefined; - - var t: [3]Fe = undefined; - var t0 = &t[0]; - var t1 = &t[1]; - var t2 = &t[2]; - - Fe.sq(t0, z); - Fe.sq(t1, t0); - Fe.sq(t1, t1); - Fe.mul(t1, z, t1); - Fe.mul(t0, t0, t1); - - Fe.sq(t0, t0); - Fe.mul(t0, t1, t0); - - Fe.sq(t1, t0); - i = 1; - while (i < 5) : (i += 1) Fe.sq(t1, t1); - Fe.mul(t0, t1, t0); - - Fe.sq(t1, t0); - i = 1; - while (i < 10) : (i += 1) Fe.sq(t1, t1); - Fe.mul(t1, t1, t0); - - Fe.sq(t2, t1); - i = 1; - while (i < 20) : (i += 1) Fe.sq(t2, t2); - Fe.mul(t1, t2, t1); - - Fe.sq(t1, t1); - i = 1; - while (i < 10) : (i += 1) Fe.sq(t1, t1); - Fe.mul(t0, t1, t0); - - Fe.sq(t1, t0); - i = 1; - while (i < 50) : (i += 1) Fe.sq(t1, t1); - Fe.mul(t1, t1, t0); - - Fe.sq(t2, t1); - i = 1; - while (i < 100) : (i += 1) Fe.sq(t2, t2); - Fe.mul(t1, t2, t1); - - Fe.sq(t1, t1); - i = 1; - while (i < 50) : (i += 1) Fe.sq(t1, t1); - Fe.mul(t0, t1, t0); - - Fe.sq(t0, t0); - i = 1; - while (i < 2) : (i += 1) Fe.sq(t0, t0); - Fe.mul(out, t0, z); - - t0.secureZero(); - t1.secureZero(); - t2.secureZero(); - } - - inline fn toBytesRound(c: []i64, t: []i64, comptime i: comptime_int, comptime shift: comptime_int) void { - c[i] = t[i] >> shift; - if (i + 1 < 10) { - t[i + 1] += c[i]; - } - t[i] -= c[i] * (@as(i32, 1) << shift); - } - - fn toBytes(s: []u8, h: *const Fe) void { - std.debug.assert(s.len >= 32); - - var t: [10]i64 = undefined; - for (h.b[0..]) |_, i| { - t[i] = h.b[i]; - } - - var q = (19 * t[9] + ((@as(i32, 1) << 24))) >> 25; - { - var i: usize = 0; - while (i < 5) : (i += 1) { - q += t[2 * i]; - q >>= 26; - q += t[2 * i + 1]; - q >>= 25; - } - } - t[0] += 19 * q; - - var c: [10]i64 = undefined; - - var st = t[0..]; - var sc = c[0..]; - - toBytesRound(sc, st, 0, 26); - toBytesRound(sc, st, 1, 25); - toBytesRound(sc, st, 2, 26); - toBytesRound(sc, st, 3, 25); - toBytesRound(sc, st, 4, 26); - toBytesRound(sc, st, 5, 25); - toBytesRound(sc, st, 6, 26); - toBytesRound(sc, st, 7, 25); - toBytesRound(sc, st, 8, 26); - toBytesRound(sc, st, 9, 25); - - var ut: [10]u32 = undefined; - for (ut[0..]) |_, i| { - ut[i] = @bitCast(u32, @intCast(i32, t[i])); - } - - writeIntLittle(u32, s[0..4], (ut[0] >> 0) | (ut[1] << 26)); - writeIntLittle(u32, s[4..8], (ut[1] >> 6) | (ut[2] << 19)); - writeIntLittle(u32, s[8..12], (ut[2] >> 13) | (ut[3] << 13)); - writeIntLittle(u32, s[12..16], (ut[3] >> 19) | (ut[4] << 6)); - writeIntLittle(u32, s[16..20], (ut[5] >> 0) | (ut[6] << 25)); - writeIntLittle(u32, s[20..24], (ut[6] >> 7) | (ut[7] << 19)); - writeIntLittle(u32, s[24..28], (ut[7] >> 13) | (ut[8] << 12)); - writeIntLittle(u32, s[28..32], (ut[8] >> 20) | (ut[9] << 6)); - - std.mem.secureZero(i64, t[0..]); - } - - // Parity check. Returns 0 if even, 1 if odd - fn isNegative(f: *const Fe) bool { - var s: [32]u8 = undefined; - Fe.toBytes(s[0..], f); - const isneg = s[0] & 1; - s.secureZero(); - return isneg; - } - - fn isNonZero(f: *const Fe) bool { - var s: [32]u8 = undefined; - Fe.toBytes(s[0..], f); - const isnonzero = zerocmp(u8, s[0..]); - s.secureZero(); - return isneg; - } -}; - -test "x25519 public key calculation from secret key" { - var sk: [32]u8 = undefined; - var pk_expected: [32]u8 = undefined; - var pk_calculated: [32]u8 = undefined; - try fmt.hexToBytes(sk[0..], "8052030376d47112be7f73ed7a019293dd12ad910b654455798b4667d73de166"); - try fmt.hexToBytes(pk_expected[0..], "f1814f0e8ff1043d8a44d25babff3cedcae6c22c3edaa48f857ae70de2baae50"); - std.testing.expect(X25519.createPublicKey(pk_calculated[0..], &sk)); - std.testing.expect(std.mem.eql(u8, &pk_calculated, &pk_expected)); -} - -test "x25519 rfc7748 vector1" { - const secret_key = "\xa5\x46\xe3\x6b\xf0\x52\x7c\x9d\x3b\x16\x15\x4b\x82\x46\x5e\xdd\x62\x14\x4c\x0a\xc1\xfc\x5a\x18\x50\x6a\x22\x44\xba\x44\x9a\xc4"; - const public_key = "\xe6\xdb\x68\x67\x58\x30\x30\xdb\x35\x94\xc1\xa4\x24\xb1\x5f\x7c\x72\x66\x24\xec\x26\xb3\x35\x3b\x10\xa9\x03\xa6\xd0\xab\x1c\x4c"; - - const expected_output = "\xc3\xda\x55\x37\x9d\xe9\xc6\x90\x8e\x94\xea\x4d\xf2\x8d\x08\x4f\x32\xec\xcf\x03\x49\x1c\x71\xf7\x54\xb4\x07\x55\x77\xa2\x85\x52"; - - var output: [32]u8 = undefined; - - std.testing.expect(X25519.create(output[0..], secret_key, public_key)); - std.testing.expect(std.mem.eql(u8, &output, expected_output)); -} - -test "x25519 rfc7748 vector2" { - const secret_key = "\x4b\x66\xe9\xd4\xd1\xb4\x67\x3c\x5a\xd2\x26\x91\x95\x7d\x6a\xf5\xc1\x1b\x64\x21\xe0\xea\x01\xd4\x2c\xa4\x16\x9e\x79\x18\xba\x0d"; - const public_key = "\xe5\x21\x0f\x12\x78\x68\x11\xd3\xf4\xb7\x95\x9d\x05\x38\xae\x2c\x31\xdb\xe7\x10\x6f\xc0\x3c\x3e\xfc\x4c\xd5\x49\xc7\x15\xa4\x93"; - - const expected_output = "\x95\xcb\xde\x94\x76\xe8\x90\x7d\x7a\xad\xe4\x5c\xb4\xb8\x73\xf8\x8b\x59\x5a\x68\x79\x9f\xa1\x52\xe6\xf8\xf7\x64\x7a\xac\x79\x57"; - - var output: [32]u8 = undefined; - - std.testing.expect(X25519.create(output[0..], secret_key, public_key)); - std.testing.expect(std.mem.eql(u8, &output, expected_output)); -} - -test "x25519 rfc7748 one iteration" { - const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00".*; - const expected_output = "\x42\x2c\x8e\x7a\x62\x27\xd7\xbc\xa1\x35\x0b\x3e\x2b\xb7\x27\x9f\x78\x97\xb8\x7b\xb6\x85\x4b\x78\x3c\x60\xe8\x03\x11\xae\x30\x79"; - - var k: [32]u8 = initial_value; - var u: [32]u8 = initial_value; - - var i: usize = 0; - while (i < 1) : (i += 1) { - var output: [32]u8 = undefined; - std.testing.expect(X25519.create(output[0..], &k, &u)); - - std.mem.copy(u8, u[0..], k[0..]); - std.mem.copy(u8, k[0..], output[0..]); - } - - std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); -} - -test "x25519 rfc7748 1,000 iterations" { - // These iteration tests are slow so we always skip them. Results have been verified. - if (true) { - return error.SkipZigTest; - } - - const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"; - const expected_output = "\x68\x4c\xf5\x9b\xa8\x33\x09\x55\x28\x00\xef\x56\x6f\x2f\x4d\x3c\x1c\x38\x87\xc4\x93\x60\xe3\x87\x5f\x2e\xb9\x4d\x99\x53\x2c\x51"; - - var k: [32]u8 = initial_value.*; - var u: [32]u8 = initial_value.*; - - var i: usize = 0; - while (i < 1000) : (i += 1) { - var output: [32]u8 = undefined; - std.testing.expect(X25519.create(output[0..], &k, &u)); - - std.mem.copy(u8, u[0..], k[0..]); - std.mem.copy(u8, k[0..], output[0..]); - } - - std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); -} - -test "x25519 rfc7748 1,000,000 iterations" { - if (true) { - return error.SkipZigTest; - } - - const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"; - const expected_output = "\x7c\x39\x11\xe0\xab\x25\x86\xfd\x86\x44\x97\x29\x7e\x57\x5e\x6f\x3b\xc6\x01\xc0\x88\x3c\x30\xdf\x5f\x4d\xd2\xd2\x4f\x66\x54\x24"; - - var k: [32]u8 = initial_value.*; - var u: [32]u8 = initial_value.*; - - var i: usize = 0; - while (i < 1000000) : (i += 1) { - var output: [32]u8 = undefined; - std.testing.expect(X25519.create(output[0..], &k, &u)); - - std.mem.copy(u8, u[0..], k[0..]); - std.mem.copy(u8, k[0..], output[0..]); - } - - std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); -} diff --git a/lib/std/mem.zig b/lib/std/mem.zig index 1ba64f47fa..dc26ed3d33 100644 --- a/lib/std/mem.zig +++ b/lib/std/mem.zig @@ -334,6 +334,31 @@ test "mem.secureZero" { testing.expectEqualSlices(u8, a[0..], b[0..]); } +/// Constant-time (for a given length) comparison. +pub fn timingSafeEqual(comptime T: type, a: []const T, b: []const T) bool { + const length = a.len; + if (length != b.len) { + return false; + } + const ap = @ptrCast([*]const volatile T, a.ptr); + const bp = @ptrCast([*]const volatile T, b.ptr); + var c: u8 = 0; + var i: usize = 0; + while (i < length) : (i += 1) { + c |= a[i] ^ b[i]; + } + return c == 0; +} + +test "mem.timingSafeEqual" { + var a = [_]u8{0xfe} ** 8; + var b = [_]u8{0xfe} ** 8; + + testing.expect(timingSafeEqual(u8, &a, &b)); + a[0] += 1; + testing.expect(!timingSafeEqual(u8, &a, &b)); +} + /// Initializes all fields of the struct with their default value, or zero values if no default value is present. /// If the field is present in the provided initial values, it will have that value instead. /// Structs are initialized recursively. -- cgit v1.2.3 From 5f9953f41ff7761cdf86c211c91de7470425771c Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Fri, 14 Aug 2020 16:08:26 +0200 Subject: Remove mem.timingSafeEqual() for now This requires assembly implementations, and is not needed for signature verification. Thanks @daurnimator --- lib/std/crypto/25519/ed25519.zig | 2 +- lib/std/mem.zig | 25 ------------------------- 2 files changed, 1 insertion(+), 26 deletions(-) diff --git a/lib/std/crypto/25519/ed25519.zig b/lib/std/crypto/25519/ed25519.zig index c5baf37683..f174fd8581 100644 --- a/lib/std/crypto/25519/ed25519.zig +++ b/lib/std/crypto/25519/ed25519.zig @@ -96,7 +96,7 @@ pub const Ed25519 = struct { const p = try a.neg().mul(hram); const check = (try Curve.basePoint().mul(s.*)).add(p).toBytes(); - if (mem.timingSafeEqual(u8, &check, r) == false) { + if (mem.eql(u8, &check, r) == false) { return error.InvalidSignature; } } diff --git a/lib/std/mem.zig b/lib/std/mem.zig index dc26ed3d33..1ba64f47fa 100644 --- a/lib/std/mem.zig +++ b/lib/std/mem.zig @@ -334,31 +334,6 @@ test "mem.secureZero" { testing.expectEqualSlices(u8, a[0..], b[0..]); } -/// Constant-time (for a given length) comparison. -pub fn timingSafeEqual(comptime T: type, a: []const T, b: []const T) bool { - const length = a.len; - if (length != b.len) { - return false; - } - const ap = @ptrCast([*]const volatile T, a.ptr); - const bp = @ptrCast([*]const volatile T, b.ptr); - var c: u8 = 0; - var i: usize = 0; - while (i < length) : (i += 1) { - c |= a[i] ^ b[i]; - } - return c == 0; -} - -test "mem.timingSafeEqual" { - var a = [_]u8{0xfe} ** 8; - var b = [_]u8{0xfe} ** 8; - - testing.expect(timingSafeEqual(u8, &a, &b)); - a[0] += 1; - testing.expect(!timingSafeEqual(u8, &a, &b)); -} - /// Initializes all fields of the struct with their default value, or zero values if no default value is present. /// If the field is present in the provided initial values, it will have that value instead. /// Structs are initialized recursively. -- cgit v1.2.3 From 6af9bc8c686c5eeaff274fa7ebb96b1ead3212ce Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Fri, 14 Aug 2020 16:33:37 +0200 Subject: Initialize structures directly Suggested by @kubkon, thanks! --- lib/std/crypto/25519/curve25519.zig | 2 +- lib/std/crypto/25519/edwards25519.zig | 2 +- lib/std/crypto/25519/ristretto255.zig | 16 +++++----------- 3 files changed, 7 insertions(+), 13 deletions(-) diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig index a17d9baa7b..011c926f64 100644 --- a/lib/std/crypto/25519/curve25519.zig +++ b/lib/std/crypto/25519/curve25519.zig @@ -76,7 +76,7 @@ pub const Curve25519 = struct { if (x2.isZero()) { return error.IdentityElement; } - return @as(Curve25519, .{ .x = x2 }); + return Curve25519 { .x = x2 }; } /// Multiply a Curve25519 point by a scalar after "clamping" it. diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index 7e748609de..c28ed6865d 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -34,7 +34,7 @@ pub const Edwards25519 = struct { x.cMov(x.mul(Fe.sqrtm1()), 1 - @boolToInt(has_m_root)); x.cMov(x.neg(), @boolToInt(x.isNegative()) ^ (s[31] >> 7)); const t = x.mul(y); - return @as(Edwards25519, .{ .x = x, .y = y, .z = z, .t = t }); + return Edwards25519 { .x = x, .y = y, .z = z, .t = t }; } /// Encode an Edwards25519 point. diff --git a/lib/std/crypto/25519/ristretto255.zig b/lib/std/crypto/25519/ristretto255.zig index 71fa876c4f..f573145385 100644 --- a/lib/std/crypto/25519/ristretto255.zig +++ b/lib/std/crypto/25519/ristretto255.zig @@ -13,9 +13,8 @@ pub const Ristretto255 = struct { p: Curve = undefined, fn sqrtRatioM1(u: Fe, v: Fe) !Fe { - const v3 = v.sq().mul(v); // v3 = v^3 - var x = v3.sq().mul(u).mul(v). // x = uv^7 - pow2523().mul(v3).mul(u); // x = uv^3(uv^7)^((q-5)/8) + const v3 = v.sq().mul(v); // v^3 + var x = v3.sq().mul(u).mul(v).pow2523().mul(v3).mul(u); // uv^3(uv^7)^((q-5)/8) const vxx = x.sq().mul(v); // vx^2 const m_root_check = vxx.sub(u); // vx^2-u const p_root_check = vxx.add(u); // vx^2+u @@ -77,7 +76,7 @@ pub const Ristretto255 = struct { .z = Fe.one(), .t = t, }; - return @as(Ristretto255, .{ .p = p }); + return Ristretto255 { .p = p }; } /// Encode to a Ristretto255 representative. @@ -87,25 +86,20 @@ pub const Ristretto255 = struct { const zmy = p.z.sub(p.y); // Z-Y u1_ = u1_.mul(zmy); // (Z+Y)*(Z-Y) const u2_ = p.x.mul(p.y); // X*Y - const u1_u2u2 = u2_.sq().mul(u1_); // u1*u2^2 - const inv_sqrt = sqrtRatioM1(Fe.one(), u1_u2u2) catch unreachable; const den1 = inv_sqrt.mul(u1_); const den2 = inv_sqrt.mul(u2_); const z_inv = den1.mul(den2).mul(p.t); // den1*den2*T - const ix = p.x.mul(Fe.sqrtm1()); // X*sqrt(-1) const iy = p.y.mul(Fe.sqrtm1()); // Y*sqrt(-1) const eden = den1.mul(Fe.edwards25519sqrtamd()); // den1/sqrt(a-d) - const t_z_inv = p.t.mul(z_inv); // T*z_inv - const rotate = @boolToInt(t_z_inv.isNegative()); + const rotate = @boolToInt(t_z_inv.isNegative()); var x = p.x; var y = p.y; var den_inv = den2; - x.cMov(iy, rotate); y.cMov(ix, rotate); den_inv.cMov(eden, rotate); @@ -131,7 +125,7 @@ pub const Ristretto255 = struct { /// Return error.WeakPublicKey if the resulting element is /// the identity element. pub inline fn mul(p: Ristretto255, s: [32]u8) !Ristretto255 { - return @as(Ristretto255, .{ .p = try p.p.mul(s) }); + return Ristretto255 { .p = try p.p.mul(s) }; } }; -- cgit v1.2.3 From 739b68938cb233d88e47ab73047787aba0ccb918 Mon Sep 17 00:00:00 2001 From: Frank Denis <124872+jedisct1@users.noreply.github.com> Date: Fri, 14 Aug 2020 16:23:55 +0200 Subject: Update lib/std/crypto/25519/field25519.zig Co-authored-by: Jakub Konka --- lib/std/crypto/25519/field25519.zig | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/std/crypto/25519/field25519.zig b/lib/std/crypto/25519/field25519.zig index 9061cbf011..fe5c28056a 100644 --- a/lib/std/crypto/25519/field25519.zig +++ b/lib/std/crypto/25519/field25519.zig @@ -3,7 +3,7 @@ const readIntLittle = std.mem.readIntLittle; const writeIntLittle = std.mem.writeIntLittle; pub const Fe = struct { - limbs: [5]u64 = undefined, + limbs: [5]u64, const MASK51: u64 = 0x7ffffffffffff; -- cgit v1.2.3 From c483bf4f97504f3c9174ec9fd516d8995971023c Mon Sep 17 00:00:00 2001 From: Frank Denis <124872+jedisct1@users.noreply.github.com> Date: Fri, 14 Aug 2020 16:24:18 +0200 Subject: Update lib/std/crypto/25519/ristretto255.zig Co-authored-by: Jakub Konka --- lib/std/crypto/25519/ristretto255.zig | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/std/crypto/25519/ristretto255.zig b/lib/std/crypto/25519/ristretto255.zig index f573145385..997b3085c9 100644 --- a/lib/std/crypto/25519/ristretto255.zig +++ b/lib/std/crypto/25519/ristretto255.zig @@ -10,7 +10,7 @@ pub const Ristretto255 = struct { /// Field arithmetic mod the order of the main subgroup. pub const scalar = Curve.scalar; - p: Curve = undefined, + p: Curve, fn sqrtRatioM1(u: Fe, v: Fe) !Fe { const v3 = v.sq().mul(v); // v^3 -- 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 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 From ed558bfbaa737b187d894eddb8573cde15a3fb33 Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sat, 15 Aug 2020 08:38:44 +0200 Subject: Address @daurnimator feedback --- lib/std/crypto/25519/curve25519.zig | 19 ++++++++--------- lib/std/crypto/25519/ed25519.zig | 8 +++---- lib/std/crypto/25519/edwards25519.zig | 19 ++++++++--------- lib/std/crypto/25519/field.zig | 33 ++++++++--------------------- lib/std/crypto/25519/ristretto255.zig | 33 ++++++++++++++--------------- lib/std/crypto/25519/scalar.zig | 39 ++++++++++++++--------------------- lib/std/crypto/25519/x25519.zig | 34 +++++++++++++++--------------- 7 files changed, 79 insertions(+), 106 deletions(-) diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig index 4fb569ccfb..8b8f8a5586 100644 --- a/lib/std/crypto/25519/curve25519.zig +++ b/lib/std/crypto/25519/curve25519.zig @@ -21,7 +21,7 @@ pub const Curve25519 = struct { /// Return the Curve25519 base point. pub inline fn basePoint() Curve25519 { - return .{ .x = Fe.curve25519BasePoint() }; + return .{ .x = Fe.curve25519BasePoint }; } /// Check that the encoding of a Curve25519 point is canonical. @@ -38,10 +38,10 @@ pub const Curve25519 = struct { fn ladder(p: Curve25519, s: [32]u8, comptime bits: usize) !Curve25519 { var x1 = p.x; - var x2 = Fe.one(); - var z2 = Fe.zero(); + var x2 = Fe.one; + var z2 = Fe.zero; var x3 = x1; - var z3 = Fe.one(); + var z3 = Fe.one; var swap: u8 = 0; var pos: usize = bits - 1; while (true) { @@ -76,7 +76,7 @@ pub const Curve25519 = struct { if (x2.isZero()) { return error.IdentityElement; } - return Curve25519 { .x = x2 }; + return Curve25519{ .x = x2 }; } /// Multiply a Curve25519 point by a scalar after "clamping" it. @@ -88,7 +88,7 @@ pub const Curve25519 = struct { pub fn clampedMul(p: Curve25519, s: [32]u8) !Curve25519 { var t: [32]u8 = s; scalar.clamp(&t); - return ladder(p, t, 255); + return try ladder(p, t, 255); } /// Multiply a Curve25519 point by a scalar without clamping it. @@ -98,7 +98,7 @@ pub const Curve25519 = struct { pub fn mul(p: Curve25519, s: [32]u8) !Curve25519 { const cofactor = [_]u8{8} ++ [_]u8{0} ** 31; _ = ladder(p, cofactor, 4) catch |_| return error.WeakPublicKey; - return ladder(p, s, 256); + return try ladder(p, s, 256); } }; @@ -107,10 +107,9 @@ test "curve25519" { const p = try Curve25519.basePoint().clampedMul(s); try p.rejectIdentity(); var buf: [128]u8 = undefined; - const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{p.toBytes()}), "E6F2A4D1C28EE5C7AD0329268255A468AD407D2672824C0C0EB30EA6EF450145"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{p.toBytes()}), "E6F2A4D1C28EE5C7AD0329268255A468AD407D2672824C0C0EB30EA6EF450145"); const q = try p.clampedMul(s); - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{q.toBytes()}), "3614E119FFE55EC55B87D6B19971A9F4CBC78EFE80BEC55B96392BABCC712537"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{q.toBytes()}), "3614E119FFE55EC55B87D6B19971A9F4CBC78EFE80BEC55B96392BABCC712537"); try Curve25519.rejectNonCanonical(s); s[31] |= 0x80; diff --git a/lib/std/crypto/25519/ed25519.zig b/lib/std/crypto/25519/ed25519.zig index f174fd8581..669bb94480 100644 --- a/lib/std/crypto/25519/ed25519.zig +++ b/lib/std/crypto/25519/ed25519.zig @@ -107,11 +107,10 @@ test "ed25519 key pair creation" { try fmt.hexToBytes(seed[0..], "8052030376d47112be7f73ed7a019293dd12ad910b654455798b4667d73de166"); const key_pair = try Ed25519.createKeyPair(seed); var buf: [256]u8 = undefined; - const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{key_pair}), "8052030376D47112BE7F73ED7A019293DD12AD910B654455798B4667D73DE1662D6F7455D97B4A3A10D7293909D1A4F2058CB9A370E43FA8154BB280DB839083"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{key_pair}), "8052030376D47112BE7F73ED7A019293DD12AD910B654455798B4667D73DE1662D6F7455D97B4A3A10D7293909D1A4F2058CB9A370E43FA8154BB280DB839083"); const public_key = Ed25519.publicKey(key_pair); - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{public_key}), "2D6F7455D97B4A3A10D7293909D1A4F2058CB9A370E43FA8154BB280DB839083"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{public_key}), "2D6F7455D97B4A3A10D7293909D1A4F2058CB9A370E43FA8154BB280DB839083"); } test "ed25519 signature" { @@ -121,8 +120,7 @@ test "ed25519 signature" { const sig = try Ed25519.sign("test", key_pair, null); var buf: [128]u8 = undefined; - const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{sig}), "10A442B4A80CC4225B154F43BEF28D2472CA80221951262EB8E0DF9091575E2687CC486E77263C3418C757522D54F84B0359236ABBBD4ACD20DC297FDCA66808"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{sig}), "10A442B4A80CC4225B154F43BEF28D2472CA80221951262EB8E0DF9091575E2687CC486E77263C3418C757522D54F84B0359236ABBBD4ACD20DC297FDCA66808"); const public_key = Ed25519.publicKey(key_pair); try Ed25519.verify(sig, "test", public_key); std.testing.expectError(error.InvalidSignature, Ed25519.verify(sig, "TEST", public_key)); diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index 3d21af40e5..3f2ede511a 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -17,10 +17,10 @@ pub const Edwards25519 = struct { /// Decode an Edwards25519 point from its compressed (Y+sign) coordinates. pub fn fromBytes(s: [32]u8) !Edwards25519 { - const z = Fe.one(); + const z = Fe.one; const y = Fe.fromBytes(s); var u = y.sq(); - var v = u.mul(Fe.edwards25519d()); + var v = u.mul(Fe.edwards25519d); u = u.sub(z); v = v.add(z); const v3 = v.sq().mul(v); @@ -31,10 +31,10 @@ pub const Edwards25519 = struct { if ((@boolToInt(has_m_root) | @boolToInt(has_p_root)) == 0) { return error.InvalidEncoding; } - x.cMov(x.mul(Fe.sqrtm1()), 1 - @boolToInt(has_m_root)); + x.cMov(x.mul(Fe.sqrtm1), 1 - @boolToInt(has_m_root)); x.cMov(x.neg(), @boolToInt(x.isNegative()) ^ (s[31] >> 7)); const t = x.mul(y); - return Edwards25519 { .x = x, .y = y, .z = z, .t = t }; + return Edwards25519{ .x = x, .y = y, .z = z, .t = t }; } /// Encode an Edwards25519 point. @@ -55,14 +55,14 @@ pub const Edwards25519 = struct { return .{ .x = Fe{ .limbs = .{ 3990542415680775, 3398198340507945, 4322667446711068, 2814063955482877, 2839572215813860 } }, .y = Fe{ .limbs = .{ 1801439850948184, 1351079888211148, 450359962737049, 900719925474099, 1801439850948198 } }, - .z = Fe.one(), + .z = Fe.one, .t = Fe{ .limbs = .{ 1841354044333475, 16398895984059, 755974180946558, 900171276175154, 1821297809914039 } }, .is_base = true, }; } inline fn identityElement() Edwards25519 { - return .{ .x = Fe.zero(), .y = Fe.one(), .z = Fe.one(), .t = Fe.zero() }; + return .{ .x = Fe.zero, .y = Fe.one, .z = Fe.one, .t = Fe.zero }; } /// Reject the neutral element. @@ -98,7 +98,7 @@ pub const Edwards25519 = struct { pub inline fn add(p: Edwards25519, q: Edwards25519) Edwards25519 { const a = p.y.sub(p.x).mul(q.y.sub(q.x)); const b = p.x.add(p.y).mul(q.x.add(q.y)); - const c = p.t.mul(q.t).mul(Fe.edwards25519d2()); + const c = p.t.mul(q.t).mul(Fe.edwards25519d2); var d = p.z.mul(q.z); d = d.add(d); const x = b.sub(a); @@ -124,7 +124,7 @@ pub const Edwards25519 = struct { var t = Edwards25519.identityElement(); comptime var i: u8 = 0; inline while (i < 16) : (i += 1) { - t.cMov(pc[i], ((@intCast(usize, (b ^ i)) -% 1) >> 8) & 1); + t.cMov(pc[i], ((@as(usize, (b ^ i)) -% 1) >> 8) & 1); } return t; } @@ -191,8 +191,7 @@ test "edwards25519 packing/unpacking" { var b = Edwards25519.basePoint(); const pk = try b.mul(s); var buf: [128]u8 = undefined; - const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{pk.toBytes()}), "074BC7E0FCBD587FDBC0969444245FADC562809C8F6E97E949AF62484B5B81A6"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{pk.toBytes()}), "074BC7E0FCBD587FDBC0969444245FADC562809C8F6E97E949AF62484B5B81A6"); const small_order_ss: [7][32]u8 = .{ .{ diff --git a/lib/std/crypto/25519/field.zig b/lib/std/crypto/25519/field.zig index fe5c28056a..59aa1e3ba9 100644 --- a/lib/std/crypto/25519/field.zig +++ b/lib/std/crypto/25519/field.zig @@ -7,34 +7,19 @@ pub const Fe = struct { const MASK51: u64 = 0x7ffffffffffff; - pub inline fn zero() Fe { - return .{ .limbs = .{ 0, 0, 0, 0, 0 } }; - } + pub const zero = Fe{ .limbs = .{ 0, 0, 0, 0, 0 } }; - pub inline fn one() Fe { - return .{ .limbs = .{ 1, 0, 0, 0, 0 } }; - } + pub const one = Fe{ .limbs = .{ 1, 0, 0, 0, 0 } }; - pub inline fn sqrtm1() Fe { - return .{ .limbs = .{ 1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133 } }; // sqrt(-1) - } + pub const sqrtm1 = Fe{ .limbs = .{ 1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133 } }; // sqrt(-1) - pub inline fn curve25519BasePoint() Fe { - return .{ .limbs = .{ 9, 0, 0, 0, 0 } }; - } + pub const curve25519BasePoint = Fe{ .limbs = .{ 9, 0, 0, 0, 0 } }; - pub inline fn edwards25519d() Fe { - return .{ .limbs = .{ 929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575 } }; // 37095705934669439343138083508754565189542113879843219016388785533085940283555 - } + pub const edwards25519d = Fe{ .limbs = .{ 929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575 } }; // 37095705934669439343138083508754565189542113879843219016388785533085940283555 - pub inline fn edwards25519d2() Fe { - return .{ .limbs = .{ 1859910466990425, 932731440258426, 1072319116312658, 1815898335770999, 633789495995903 } }; // 2d - } + pub const edwards25519d2 = Fe{ .limbs = .{ 1859910466990425, 932731440258426, 1072319116312658, 1815898335770999, 633789495995903 } }; // 2d - // 1/sqrt(a-d) - pub inline fn edwards25519sqrtamd() Fe { - return .{ .limbs = .{ 278908739862762, 821645201101625, 8113234426968, 1777959178193151, 2118520810568447 } }; - } + pub const edwards25519sqrtamd = Fe{ .limbs = .{ 278908739862762, 821645201101625, 8113234426968, 1777959178193151, 2118520810568447 } }; // 1/sqrt(a-d) pub inline fn isZero(fe: Fe) bool { var reduced = fe; @@ -77,7 +62,7 @@ pub const Fe = struct { c |= s[i] ^ 0xff; } c = (c -% 1) >> 8; - const d = (@intCast(u16, 0xed - 1) -% @intCast(u16, s[0])) >> 8; + const d = (@as(u16, 0xed - 1) -% @as(u16, s[0])) >> 8; const x = if (ignore_extra_bit) 0 else s[31] >> 7; if ((((c & d) | x) & 1) != 0) { return error.NonCanonical; @@ -148,7 +133,7 @@ pub const Fe = struct { } pub inline fn neg(a: Fe) Fe { - return zero().sub(a); + return zero.sub(a); } pub inline fn isNegative(a: Fe) bool { diff --git a/lib/std/crypto/25519/ristretto255.zig b/lib/std/crypto/25519/ristretto255.zig index 997b3085c9..0bb8e1c92a 100644 --- a/lib/std/crypto/25519/ristretto255.zig +++ b/lib/std/crypto/25519/ristretto255.zig @@ -18,11 +18,11 @@ pub const Ristretto255 = struct { const vxx = x.sq().mul(v); // vx^2 const m_root_check = vxx.sub(u); // vx^2-u const p_root_check = vxx.add(u); // vx^2+u - const f_root_check = u.mul(Fe.sqrtm1()).add(vxx); // vx^2+u*sqrt(-1) + const f_root_check = u.mul(Fe.sqrtm1).add(vxx); // vx^2+u*sqrt(-1) const has_m_root = m_root_check.isZero(); const has_p_root = p_root_check.isZero(); const has_f_root = f_root_check.isZero(); - const x_sqrtm1 = x.mul(Fe.sqrtm1()); // x*sqrt(-1) + const x_sqrtm1 = x.mul(Fe.sqrtm1); // x*sqrt(-1) x.cMov(x_sqrtm1, @boolToInt(has_p_root) | @boolToInt(has_f_root)); x = x.abs(); if ((@boolToInt(has_m_root) | @boolToInt(has_p_root)) == 0) { @@ -53,13 +53,13 @@ pub const Ristretto255 = struct { try rejectNonCanonical(s); const s_ = Fe.fromBytes(s); const ss = s_.sq(); // s^2 - const u1_ = Fe.one().sub(ss); // (1-s^2) + const u1_ = Fe.one.sub(ss); // (1-s^2) const u1u1 = u1_.sq(); // (1-s^2)^2 - const u2_ = Fe.one().add(ss); // (1+s^2) + const u2_ = Fe.one.add(ss); // (1+s^2) const u2u2 = u2_.sq(); // (1+s^2)^2 - const v = Fe.edwards25519d().mul(u1u1).neg().sub(u2u2); // -(d*u1^2)-u2^2 + const v = Fe.edwards25519d.mul(u1u1).neg().sub(u2u2); // -(d*u1^2)-u2^2 const v_u2u2 = v.mul(u2u2); // v*u2^2 - const inv_sqrt = sqrtRatioM1(Fe.one(), v_u2u2) catch |e| { + const inv_sqrt = sqrtRatioM1(Fe.one, v_u2u2) catch |e| { return error.InvalidEncoding; }; var x = inv_sqrt.mul(u2_); @@ -73,10 +73,10 @@ pub const Ristretto255 = struct { const p: Curve = .{ .x = x, .y = y, - .z = Fe.one(), + .z = Fe.one, .t = t, }; - return Ristretto255 { .p = p }; + return Ristretto255{ .p = p }; } /// Encode to a Ristretto255 representative. @@ -87,13 +87,13 @@ pub const Ristretto255 = struct { u1_ = u1_.mul(zmy); // (Z+Y)*(Z-Y) const u2_ = p.x.mul(p.y); // X*Y const u1_u2u2 = u2_.sq().mul(u1_); // u1*u2^2 - const inv_sqrt = sqrtRatioM1(Fe.one(), u1_u2u2) catch unreachable; + const inv_sqrt = sqrtRatioM1(Fe.one, u1_u2u2) catch unreachable; const den1 = inv_sqrt.mul(u1_); const den2 = inv_sqrt.mul(u2_); const z_inv = den1.mul(den2).mul(p.t); // den1*den2*T - const ix = p.x.mul(Fe.sqrtm1()); // X*sqrt(-1) - const iy = p.y.mul(Fe.sqrtm1()); // Y*sqrt(-1) - const eden = den1.mul(Fe.edwards25519sqrtamd()); // den1/sqrt(a-d) + const ix = p.x.mul(Fe.sqrtm1); // X*sqrt(-1) + const iy = p.y.mul(Fe.sqrtm1); // Y*sqrt(-1) + const eden = den1.mul(Fe.edwards25519sqrtamd); // den1/sqrt(a-d) const t_z_inv = p.t.mul(z_inv); // T*z_inv const rotate = @boolToInt(t_z_inv.isNegative()); @@ -125,23 +125,22 @@ pub const Ristretto255 = struct { /// Return error.WeakPublicKey if the resulting element is /// the identity element. pub inline fn mul(p: Ristretto255, s: [32]u8) !Ristretto255 { - return Ristretto255 { .p = try p.p.mul(s) }; + return Ristretto255{ .p = try p.p.mul(s) }; } }; test "ristretto255" { const p = Ristretto255.basePoint(); var buf: [256]u8 = undefined; - const alloc = &std.heap.FixedBufferAllocator.init(&buf).allocator; - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{p.toBytes()}), "E2F2AE0A6ABC4E71A884A961C500515F58E30B6AA582DD8DB6A65945E08D2D76"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{p.toBytes()}), "E2F2AE0A6ABC4E71A884A961C500515F58E30B6AA582DD8DB6A65945E08D2D76"); var r: [32]u8 = undefined; try fmt.hexToBytes(r[0..], "6a493210f7499cd17fecb510ae0cea23a110e8d5b901f8acadd3095c73a3b919"); var q = try Ristretto255.fromBytes(r); q = q.dbl().add(p); - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{q.toBytes()}), "E882B131016B52C1D3337080187CF768423EFCCBB517BB495AB812C4160FF44E"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{q.toBytes()}), "E882B131016B52C1D3337080187CF768423EFCCBB517BB495AB812C4160FF44E"); const s = [_]u8{15} ++ [_]u8{0} ** 31; const w = try p.mul(s); - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{w.toBytes()}), "E0C418F7C8D9C4CDD7395B93EA124F3AD99021BB681DFC3302A9D99A2E53E64E"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{w.toBytes()}), "E0C418F7C8D9C4CDD7395B93EA124F3AD99021BB681DFC3302A9D99A2E53E64E"); } diff --git a/lib/std/crypto/25519/scalar.zig b/lib/std/crypto/25519/scalar.zig index 6971b43489..c3340ab61e 100644 --- a/lib/std/crypto/25519/scalar.zig +++ b/lib/std/crypto/25519/scalar.zig @@ -1,20 +1,17 @@ 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 field_size = [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, // 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); + limbs[idx] = @as(i64, x); } mem.set(i64, limbs[32..], 0); return .{ .limbs = limbs }; @@ -23,7 +20,7 @@ const ScalarExpanded = struct { fn fromBytes64(s: [64]u8) ScalarExpanded { var limbs: [64]i64 = undefined; for (s) |x, idx| { - limbs[idx] = @intCast(i64, x); + limbs[idx] = @as(i64, x); } return .{ .limbs = limbs }; } @@ -38,7 +35,7 @@ const ScalarExpanded = struct { 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)]); + const xj = limbs[j] + carry - 16 * xi * @as(i64, field_size[j - (i - 32)]); carry = (xj + 128) >> 8; limbs[j] = xj - carry * 256; } @@ -48,13 +45,13 @@ const ScalarExpanded = struct { 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]); + const xi = limbs[j] + carry - (limbs[31] >> 4) * @as(i64, field_size[j]); carry = xi >> 8; limbs[j] = xi & 255; } j = 0; inline while (j < 32) : (j += 1) { - limbs[j] -= carry * @intCast(i64, L[j]); + limbs[j] -= carry * @as(i64, field_size[j]); } j = 0; inline while (j < 32) : (j += 1) { @@ -116,15 +113,14 @@ const ScalarExpanded = struct { /// 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); + const xs = @as(u16, s[i]); + const xfield_size = @as(u16, field_size[i]); + c |= @intCast(u8, ((xs -% xfield_size) >> 8) & n); + n &= @intCast(u8, ((xs ^ xfield_size) -% 1) >> 8); if (i == 0) break; i -= 1; } @@ -161,12 +157,10 @@ test "scalar25519" { 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"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{y}), "1E979B917937F3DE71D18077F961F6CEFF01030405060708010203040506070F"); - const field_size = fieldSize(); const reduced = reduce(field_size); - std.testing.expectEqualStrings(try std.fmt.allocPrint(alloc, "{X}", .{reduced}), "0000000000000000000000000000000000000000000000000000000000000000"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{reduced}), "0000000000000000000000000000000000000000000000000000000000000000"); } test "non-canonical scalar25519" { @@ -174,12 +168,11 @@ test "non-canonical scalar25519" { std.testing.expectError(error.NonCanonical, rejectNonCanonical(too_targe)); } -test "scalar25519 mulAdd overflow check" { +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"); + std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{x}), "D14DF91389432C25AD60FF9791B9FD1D67BEF517D273ECCE3D9A307C1B419903"); } diff --git a/lib/std/crypto/25519/x25519.zig b/lib/std/crypto/25519/x25519.zig index 55c860d13e..ac88d40952 100644 --- a/lib/std/crypto/25519/x25519.zig +++ b/lib/std/crypto/25519/x25519.zig @@ -56,32 +56,32 @@ test "x25519 public key calculation from secret key" { } test "x25519 rfc7748 vector1" { - const secret_key = "\xa5\x46\xe3\x6b\xf0\x52\x7c\x9d\x3b\x16\x15\x4b\x82\x46\x5e\xdd\x62\x14\x4c\x0a\xc1\xfc\x5a\x18\x50\x6a\x22\x44\xba\x44\x9a\xc4"; - const public_key = "\xe6\xdb\x68\x67\x58\x30\x30\xdb\x35\x94\xc1\xa4\x24\xb1\x5f\x7c\x72\x66\x24\xec\x26\xb3\x35\x3b\x10\xa9\x03\xa6\xd0\xab\x1c\x4c"; + const secret_key = [32]u8{ 0xa5, 0x46, 0xe3, 0x6b, 0xf0, 0x52, 0x7c, 0x9d, 0x3b, 0x16, 0x15, 0x4b, 0x82, 0x46, 0x5e, 0xdd, 0x62, 0x14, 0x4c, 0x0a, 0xc1, 0xfc, 0x5a, 0x18, 0x50, 0x6a, 0x22, 0x44, 0xba, 0x44, 0x9a, 0xc4 }; + const public_key = [32]u8{ 0xe6, 0xdb, 0x68, 0x67, 0x58, 0x30, 0x30, 0xdb, 0x35, 0x94, 0xc1, 0xa4, 0x24, 0xb1, 0x5f, 0x7c, 0x72, 0x66, 0x24, 0xec, 0x26, 0xb3, 0x35, 0x3b, 0x10, 0xa9, 0x03, 0xa6, 0xd0, 0xab, 0x1c, 0x4c }; - const expected_output = "\xc3\xda\x55\x37\x9d\xe9\xc6\x90\x8e\x94\xea\x4d\xf2\x8d\x08\x4f\x32\xec\xcf\x03\x49\x1c\x71\xf7\x54\xb4\x07\x55\x77\xa2\x85\x52"; + const expected_output = [32]u8{ 0xc3, 0xda, 0x55, 0x37, 0x9d, 0xe9, 0xc6, 0x90, 0x8e, 0x94, 0xea, 0x4d, 0xf2, 0x8d, 0x08, 0x4f, 0x32, 0xec, 0xcf, 0x03, 0x49, 0x1c, 0x71, 0xf7, 0x54, 0xb4, 0x07, 0x55, 0x77, 0xa2, 0x85, 0x52 }; var output: [32]u8 = undefined; - std.testing.expect(X25519.create(output[0..], secret_key, public_key)); - std.testing.expect(std.mem.eql(u8, &output, expected_output)); + std.testing.expect(X25519.create(output[0..], secret_key[0..], public_key[0..])); + std.testing.expect(std.mem.eql(u8, &output, expected_output[0..])); } test "x25519 rfc7748 vector2" { - const secret_key = "\x4b\x66\xe9\xd4\xd1\xb4\x67\x3c\x5a\xd2\x26\x91\x95\x7d\x6a\xf5\xc1\x1b\x64\x21\xe0\xea\x01\xd4\x2c\xa4\x16\x9e\x79\x18\xba\x0d"; - const public_key = "\xe5\x21\x0f\x12\x78\x68\x11\xd3\xf4\xb7\x95\x9d\x05\x38\xae\x2c\x31\xdb\xe7\x10\x6f\xc0\x3c\x3e\xfc\x4c\xd5\x49\xc7\x15\xa4\x93"; + const secret_key = [32]u8{ 0x4b, 0x66, 0xe9, 0xd4, 0xd1, 0xb4, 0x67, 0x3c, 0x5a, 0xd2, 0x26, 0x91, 0x95, 0x7d, 0x6a, 0xf5, 0xc1, 0x1b, 0x64, 0x21, 0xe0, 0xea, 0x01, 0xd4, 0x2c, 0xa4, 0x16, 0x9e, 0x79, 0x18, 0xba, 0x0d }; + const public_key = [32]u8{ 0xe5, 0x21, 0x0f, 0x12, 0x78, 0x68, 0x11, 0xd3, 0xf4, 0xb7, 0x95, 0x9d, 0x05, 0x38, 0xae, 0x2c, 0x31, 0xdb, 0xe7, 0x10, 0x6f, 0xc0, 0x3c, 0x3e, 0xfc, 0x4c, 0xd5, 0x49, 0xc7, 0x15, 0xa4, 0x93 }; - const expected_output = "\x95\xcb\xde\x94\x76\xe8\x90\x7d\x7a\xad\xe4\x5c\xb4\xb8\x73\xf8\x8b\x59\x5a\x68\x79\x9f\xa1\x52\xe6\xf8\xf7\x64\x7a\xac\x79\x57"; + const expected_output = [32]u8{ 0x95, 0xcb, 0xde, 0x94, 0x76, 0xe8, 0x90, 0x7d, 0x7a, 0xad, 0xe4, 0x5c, 0xb4, 0xb8, 0x73, 0xf8, 0x8b, 0x59, 0x5a, 0x68, 0x79, 0x9f, 0xa1, 0x52, 0xe6, 0xf8, 0xf7, 0x64, 0x7a, 0xac, 0x79, 0x57 }; var output: [32]u8 = undefined; - std.testing.expect(X25519.create(output[0..], secret_key, public_key)); - std.testing.expect(std.mem.eql(u8, &output, expected_output)); + std.testing.expect(X25519.create(output[0..], secret_key[0..], public_key[0..])); + std.testing.expect(std.mem.eql(u8, &output, expected_output[0..])); } test "x25519 rfc7748 one iteration" { - const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00".*; - const expected_output = "\x42\x2c\x8e\x7a\x62\x27\xd7\xbc\xa1\x35\x0b\x3e\x2b\xb7\x27\x9f\x78\x97\xb8\x7b\xb6\x85\x4b\x78\x3c\x60\xe8\x03\x11\xae\x30\x79"; + const initial_value = [32]u8{ 0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }; + const expected_output = [32]u8{ 0x42, 0x2c, 0x8e, 0x7a, 0x62, 0x27, 0xd7, 0xbc, 0xa1, 0x35, 0x0b, 0x3e, 0x2b, 0xb7, 0x27, 0x9f, 0x78, 0x97, 0xb8, 0x7b, 0xb6, 0x85, 0x4b, 0x78, 0x3c, 0x60, 0xe8, 0x03, 0x11, 0xae, 0x30, 0x79 }; var k: [32]u8 = initial_value; var u: [32]u8 = initial_value; @@ -95,7 +95,7 @@ test "x25519 rfc7748 one iteration" { std.mem.copy(u8, k[0..], output[0..]); } - std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); + std.testing.expect(std.mem.eql(u8, k[0..], expected_output[0..])); } test "x25519 rfc7748 1,000 iterations" { @@ -104,8 +104,8 @@ test "x25519 rfc7748 1,000 iterations" { return error.SkipZigTest; } - const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"; - const expected_output = "\x68\x4c\xf5\x9b\xa8\x33\x09\x55\x28\x00\xef\x56\x6f\x2f\x4d\x3c\x1c\x38\x87\xc4\x93\x60\xe3\x87\x5f\x2e\xb9\x4d\x99\x53\x2c\x51"; + const initial_value = [32]u8{ 0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }; + const expected_output = [32]u8{ 0x68, 0x4c, 0xf5, 0x9b, 0xa8, 0x33, 0x09, 0x55, 0x28, 0x00, 0xef, 0x56, 0x6f, 0x2f, 0x4d, 0x3c, 0x1c, 0x38, 0x87, 0xc4, 0x93, 0x60, 0xe3, 0x87, 0x5f, 0x2e, 0xb9, 0x4d, 0x99, 0x53, 0x2c, 0x51 }; var k: [32]u8 = initial_value.*; var u: [32]u8 = initial_value.*; @@ -127,8 +127,8 @@ test "x25519 rfc7748 1,000,000 iterations" { return error.SkipZigTest; } - const initial_value = "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"; - const expected_output = "\x7c\x39\x11\xe0\xab\x25\x86\xfd\x86\x44\x97\x29\x7e\x57\x5e\x6f\x3b\xc6\x01\xc0\x88\x3c\x30\xdf\x5f\x4d\xd2\xd2\x4f\x66\x54\x24"; + const initial_value = [32]u8{ 0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }; + const expected_output = [32]u8{ 0x7c, 0x39, 0x11, 0xe0, 0xab, 0x25, 0x86, 0xfd, 0x86, 0x44, 0x97, 0x29, 0x7e, 0x57, 0x5e, 0x6f, 0x3b, 0xc6, 0x01, 0xc0, 0x88, 0x3c, 0x30, 0xdf, 0x5f, 0x4d, 0xd2, 0xd2, 0x4f, 0x66, 0x54, 0x24 }; var k: [32]u8 = initial_value.*; var u: [32]u8 = initial_value.*; -- cgit v1.2.3 From 263c44473896597346bc244d82a2b436d7d2da02 Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sat, 15 Aug 2020 08:55:48 +0200 Subject: Move loop decrements into continuations Suggested by @daurnimator --- lib/std/crypto/25519/curve25519.zig | 3 +-- lib/std/crypto/25519/edwards25519.zig | 3 +-- lib/std/crypto/25519/scalar.zig | 3 +-- 3 files changed, 3 insertions(+), 6 deletions(-) diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig index 8b8f8a5586..b3e014b6d1 100644 --- a/lib/std/crypto/25519/curve25519.zig +++ b/lib/std/crypto/25519/curve25519.zig @@ -44,7 +44,7 @@ pub const Curve25519 = struct { var z3 = Fe.one; var swap: u8 = 0; var pos: usize = bits - 1; - while (true) { + while (true) : (pos -= 1) { const b = (s[pos / 8] >> @intCast(u3, pos & 7)) & 1; swap ^= b; Fe.cSwap2(&x2, &x3, &z2, &z3, swap); @@ -68,7 +68,6 @@ pub const Curve25519 = struct { z3 = x1.mul(z2); z2 = tmp1.mul(tmp0); if (pos == 0) break; - pos -= 1; } Fe.cSwap2(&x2, &x3, &z2, &z3, swap); z2 = z2.invert(); diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index 3f2ede511a..a7044794b2 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -132,12 +132,11 @@ pub const Edwards25519 = struct { fn pcMul(pc: [16]Edwards25519, s: [32]u8) !Edwards25519 { var q = Edwards25519.identityElement(); var pos: usize = 252; - while (true) { + while (true) : (pos -= 4) { q = q.dbl().dbl().dbl().dbl(); const b = (s[pos / 8] >> @intCast(u3, pos & 7)) & 0xf; q = q.add(pcSelect(pc, b)); if (pos == 0) break; - pos -= 4; } try q.rejectIdentity(); return q; diff --git a/lib/std/crypto/25519/scalar.zig b/lib/std/crypto/25519/scalar.zig index c3340ab61e..3a3a29d4bc 100644 --- a/lib/std/crypto/25519/scalar.zig +++ b/lib/std/crypto/25519/scalar.zig @@ -116,13 +116,12 @@ pub fn rejectNonCanonical(s: [32]u8) !void { var c: u8 = 0; var n: u8 = 1; var i: usize = 31; - while (true) { + while (true) : (i -= 1) { const xs = @as(u16, s[i]); const xfield_size = @as(u16, field_size[i]); c |= @intCast(u8, ((xs -% xfield_size) >> 8) & n); n &= @intCast(u8, ((xs ^ xfield_size) -% 1) >> 8); if (i == 0) break; - i -= 1; } if (c == 0) { return error.NonCanonical; -- cgit v1.2.3 From bcef123d902b9d1d8a27b0414932b1b92f6f1a7e Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sat, 15 Aug 2020 10:15:42 +0200 Subject: Address more review issues --- lib/std/crypto/25519/curve25519.zig | 8 +++--- lib/std/crypto/25519/ed25519.zig | 13 +++++++--- lib/std/crypto/25519/edwards25519.zig | 48 +++++++++++++++-------------------- lib/std/crypto/25519/ristretto255.zig | 8 +++--- lib/std/crypto/25519/x25519.zig | 26 +++++++++---------- 5 files changed, 49 insertions(+), 54 deletions(-) diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig index b3e014b6d1..9980c152eb 100644 --- a/lib/std/crypto/25519/curve25519.zig +++ b/lib/std/crypto/25519/curve25519.zig @@ -19,10 +19,8 @@ pub const Curve25519 = struct { return p.x.toBytes(); } - /// Return the Curve25519 base point. - pub inline fn basePoint() Curve25519 { - return .{ .x = Fe.curve25519BasePoint }; - } + /// The Curve25519 base point. + pub const basePoint = Curve25519{ .x = Fe.curve25519BasePoint }; /// Check that the encoding of a Curve25519 point is canonical. pub fn rejectNonCanonical(s: [32]u8) !void { @@ -103,7 +101,7 @@ pub const Curve25519 = struct { test "curve25519" { var s = [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, 8 }; - const p = try Curve25519.basePoint().clampedMul(s); + const p = try Curve25519.basePoint.clampedMul(s); try p.rejectIdentity(); var buf: [128]u8 = undefined; std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{p.toBytes()}), "E6F2A4D1C28EE5C7AD0329268255A468AD407D2672824C0C0EB30EA6EF450145"); diff --git a/lib/std/crypto/25519/ed25519.zig b/lib/std/crypto/25519/ed25519.zig index 669bb94480..eb004d2607 100644 --- a/lib/std/crypto/25519/ed25519.zig +++ b/lib/std/crypto/25519/ed25519.zig @@ -19,12 +19,19 @@ pub const Ed25519 = struct { pub const noise_length = 32; /// Derive a key pair from a secret seed. + /// + /// As in RFC 8032, an Ed25519 public key is generated by hashing + /// the secret key using the SHA-512 function, and interpreting the + /// bit-swapped, clamped lower-half of the output as the secret scalar. + /// + /// For this reason, an EdDSA secret key is commonly called a seed, + /// from which the actual secret is derived. pub fn createKeyPair(seed: [seed_length]u8) ![keypair_length]u8 { var az: [Sha512.digest_length]u8 = undefined; var h = Sha512.init(); h.update(&seed); h.final(&az); - const p = try Curve.basePoint().clampedMul(az[0..32].*); + const p = try Curve.basePoint.clampedMul(az[0..32].*); var keypair: [keypair_length]u8 = undefined; mem.copy(u8, &keypair, &seed); mem.copy(u8, keypair[seed_length..], &p.toBytes()); @@ -57,7 +64,7 @@ pub const Ed25519 = struct { var nonce64: [64]u8 = undefined; h.final(&nonce64); const nonce = Curve.scalar.reduce64(nonce64); - const r = try Curve.basePoint().mul(nonce); + const r = try Curve.basePoint.mul(nonce); var sig: [signature_length]u8 = undefined; mem.copy(u8, sig[0..32], &r.toBytes()); @@ -95,7 +102,7 @@ pub const Ed25519 = struct { const hram = Curve.scalar.reduce64(hram64); const p = try a.neg().mul(hram); - const check = (try Curve.basePoint().mul(s.*)).add(p).toBytes(); + const check = (try Curve.basePoint.mul(s.*)).add(p).toBytes(); if (mem.eql(u8, &check, r) == false) { return error.InvalidSignature; } diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index a7044794b2..a65e1dfc11 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -50,20 +50,16 @@ pub const Edwards25519 = struct { return Fe.rejectNonCanonical(s, true); } - /// Return the Edwards25519 base point. - pub inline fn basePoint() Edwards25519 { - return .{ - .x = Fe{ .limbs = .{ 3990542415680775, 3398198340507945, 4322667446711068, 2814063955482877, 2839572215813860 } }, - .y = Fe{ .limbs = .{ 1801439850948184, 1351079888211148, 450359962737049, 900719925474099, 1801439850948198 } }, - .z = Fe.one, - .t = Fe{ .limbs = .{ 1841354044333475, 16398895984059, 755974180946558, 900171276175154, 1821297809914039 } }, - .is_base = true, - }; - } + /// The edwards25519 base point. + pub const basePoint = Edwards25519{ + .x = Fe{ .limbs = .{ 3990542415680775, 3398198340507945, 4322667446711068, 2814063955482877, 2839572215813860 } }, + .y = Fe{ .limbs = .{ 1801439850948184, 1351079888211148, 450359962737049, 900719925474099, 1801439850948198 } }, + .z = Fe.one, + .t = Fe{ .limbs = .{ 1841354044333475, 16398895984059, 755974180946558, 900171276175154, 1821297809914039 } }, + .is_base = true, + }; - inline fn identityElement() Edwards25519 { - return .{ .x = Fe.zero, .y = Fe.one, .z = Fe.one, .t = Fe.zero }; - } + const identityElement = Edwards25519{ .x = Fe.zero, .y = Fe.one, .z = Fe.one, .t = Fe.zero }; /// Reject the neutral element. pub fn rejectIdentity(p: Edwards25519) !void { @@ -121,16 +117,16 @@ pub const Edwards25519 = struct { } inline fn pcSelect(pc: [16]Edwards25519, b: u8) Edwards25519 { - var t = Edwards25519.identityElement(); + var t = Edwards25519.identityElement; comptime var i: u8 = 0; inline while (i < 16) : (i += 1) { - t.cMov(pc[i], ((@as(usize, (b ^ i)) -% 1) >> 8) & 1); + t.cMov(pc[i], ((@as(usize, b ^ i) -% 1) >> 8) & 1); } return t; } fn pcMul(pc: [16]Edwards25519, s: [32]u8) !Edwards25519 { - var q = Edwards25519.identityElement(); + var q = Edwards25519.identityElement; var pos: usize = 252; while (true) : (pos -= 4) { q = q.dbl().dbl().dbl().dbl(); @@ -144,7 +140,7 @@ pub const Edwards25519 = struct { fn precompute(p: Edwards25519) [16]Edwards25519 { var pc: [16]Edwards25519 = undefined; - pc[0] = Edwards25519.identityElement(); + pc[0] = Edwards25519.identityElement; pc[1] = p; var i: usize = 2; while (i < 16) : (i += 1) { @@ -153,11 +149,14 @@ pub const Edwards25519 = struct { return pc; } - fn _mul(p: Edwards25519, s: [32]u8) !Edwards25519 { + /// Multiply an Edwards25519 point by a scalar without clamping it. + /// Return error.WeakPublicKey if the resulting point is + /// the identity element. + pub fn mul(p: Edwards25519, s: [32]u8) !Edwards25519 { var pc: [16]Edwards25519 = undefined; if (p.is_base) { @setEvalBranchQuota(10000); - pc = comptime precompute(Edwards25519.basePoint()); + pc = comptime precompute(Edwards25519.basePoint); } else { pc = precompute(p); pc[4].rejectIdentity() catch |_| return error.WeakPublicKey; @@ -174,20 +173,13 @@ pub const Edwards25519 = struct { pub fn clampedMul(p: Edwards25519, s: [32]u8) !Edwards25519 { var t: [32]u8 = s; scalar.clamp(&t); - return _mul(p, t); - } - - /// Multiply an Edwards25519 point by a scalar without clamping it. - /// Return error.WeakPublicKey if the resulting point is - /// the identity element. - pub fn mul(p: Edwards25519, s: [32]u8) !Edwards25519 { - return _mul(p, s); + return mul(p, t); } }; test "edwards25519 packing/unpacking" { const s = [_]u8{170} ++ [_]u8{0} ** 31; - var b = Edwards25519.basePoint(); + var b = Edwards25519.basePoint; const pk = try b.mul(s); var buf: [128]u8 = undefined; std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{pk.toBytes()}), "074BC7E0FCBD587FDBC0969444245FADC562809C8F6E97E949AF62484B5B81A6"); diff --git a/lib/std/crypto/25519/ristretto255.zig b/lib/std/crypto/25519/ristretto255.zig index 0bb8e1c92a..21b305f89d 100644 --- a/lib/std/crypto/25519/ristretto255.zig +++ b/lib/std/crypto/25519/ristretto255.zig @@ -43,10 +43,8 @@ pub const Ristretto255 = struct { return p.p.rejectIdentity(); } - /// Return the base point (Ristretto is a curve in desguise). - pub inline fn basePoint() Ristretto255 { - return .{ .p = Curve.basePoint() }; - } + /// The base point (Ristretto is a curve in desguise). + pub const basePoint = Ristretto255{ .p = Curve.basePoint }; /// Decode a Ristretto255 representative. pub fn fromBytes(s: [32]u8) !Ristretto255 { @@ -130,7 +128,7 @@ pub const Ristretto255 = struct { }; test "ristretto255" { - const p = Ristretto255.basePoint(); + const p = Ristretto255.basePoint; var buf: [256]u8 = undefined; std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{p.toBytes()}), "E2F2AE0A6ABC4E71A884A961C500515F58E30B6AA582DD8DB6A65945E08D2D76"); diff --git a/lib/std/crypto/25519/x25519.zig b/lib/std/crypto/25519/x25519.zig index ac88d40952..4b5a8b8482 100644 --- a/lib/std/crypto/25519/x25519.zig +++ b/lib/std/crypto/25519/x25519.zig @@ -17,7 +17,7 @@ pub const X25519 = struct { std.debug.assert(public_key.len >= minimum_key_length); var s: [32]u8 = undefined; mem.copy(u8, &s, private_key[0..32]); - if (Curve.basePoint().clampedMul(s)) |q| { + if (Curve.basePoint.clampedMul(s)) |q| { mem.copy(u8, public_key, q.toBytes()[0..]); return true; } else |_| { @@ -52,7 +52,7 @@ test "x25519 public key calculation from secret key" { try fmt.hexToBytes(sk[0..], "8052030376d47112be7f73ed7a019293dd12ad910b654455798b4667d73de166"); try fmt.hexToBytes(pk_expected[0..], "f1814f0e8ff1043d8a44d25babff3cedcae6c22c3edaa48f857ae70de2baae50"); std.testing.expect(X25519.createPublicKey(pk_calculated[0..], &sk)); - std.testing.expect(std.mem.eql(u8, &pk_calculated, &pk_expected)); + std.testing.expectEqual(pk_calculated, pk_expected); } test "x25519 rfc7748 vector1" { @@ -64,7 +64,7 @@ test "x25519 rfc7748 vector1" { var output: [32]u8 = undefined; std.testing.expect(X25519.create(output[0..], secret_key[0..], public_key[0..])); - std.testing.expect(std.mem.eql(u8, &output, expected_output[0..])); + std.testing.expectEqual(output, expected_output); } test "x25519 rfc7748 vector2" { @@ -76,7 +76,7 @@ test "x25519 rfc7748 vector2" { var output: [32]u8 = undefined; std.testing.expect(X25519.create(output[0..], secret_key[0..], public_key[0..])); - std.testing.expect(std.mem.eql(u8, &output, expected_output[0..])); + std.testing.expectEqual(output, expected_output); } test "x25519 rfc7748 one iteration" { @@ -91,11 +91,11 @@ test "x25519 rfc7748 one iteration" { var output: [32]u8 = undefined; std.testing.expect(X25519.create(output[0..], &k, &u)); - std.mem.copy(u8, u[0..], k[0..]); - std.mem.copy(u8, k[0..], output[0..]); + mem.copy(u8, u[0..], k[0..]); + mem.copy(u8, k[0..], output[0..]); } - std.testing.expect(std.mem.eql(u8, k[0..], expected_output[0..])); + std.testing.expectEqual(k, expected_output); } test "x25519 rfc7748 1,000 iterations" { @@ -115,11 +115,11 @@ test "x25519 rfc7748 1,000 iterations" { var output: [32]u8 = undefined; std.testing.expect(X25519.create(output[0..], &k, &u)); - std.mem.copy(u8, u[0..], k[0..]); - std.mem.copy(u8, k[0..], output[0..]); + mem.copy(u8, u[0..], k[0..]); + mem.copy(u8, k[0..], output[0..]); } - std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); + std.testing.expectEqual(k, expected_output); } test "x25519 rfc7748 1,000,000 iterations" { @@ -138,9 +138,9 @@ test "x25519 rfc7748 1,000,000 iterations" { var output: [32]u8 = undefined; std.testing.expect(X25519.create(output[0..], &k, &u)); - std.mem.copy(u8, u[0..], k[0..]); - std.mem.copy(u8, k[0..], output[0..]); + mem.copy(u8, u[0..], k[0..]); + mem.copy(u8, k[0..], output[0..]); } - std.testing.expect(std.mem.eql(u8, k[0..], expected_output)); + std.testing.expectEqual(k[0..], expected_output); } -- cgit v1.2.3 From d86cde575239d4e38631d562fba8b4001d436ebd Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sat, 15 Aug 2020 11:11:33 +0200 Subject: Add comment, use @truncate --- lib/std/crypto/25519/curve25519.zig | 2 +- lib/std/crypto/25519/edwards25519.zig | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig index 9980c152eb..3a4871a1f3 100644 --- a/lib/std/crypto/25519/curve25519.zig +++ b/lib/std/crypto/25519/curve25519.zig @@ -43,7 +43,7 @@ pub const Curve25519 = struct { var swap: u8 = 0; var pos: usize = bits - 1; while (true) : (pos -= 1) { - const b = (s[pos / 8] >> @intCast(u3, pos & 7)) & 1; + const b = (s[pos >> 3] >> @truncate(u3, pos)) & 1; swap ^= b; Fe.cSwap2(&x2, &x3, &z2, &z3, swap); swap = b; diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index a65e1dfc11..93b1a69d17 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -28,7 +28,7 @@ pub const Edwards25519 = struct { const vxx = x.sq().mul(v); const has_m_root = vxx.sub(u).isZero(); const has_p_root = vxx.add(u).isZero(); - if ((@boolToInt(has_m_root) | @boolToInt(has_p_root)) == 0) { + if ((@boolToInt(has_m_root) | @boolToInt(has_p_root)) == 0) { // best-effort to avoid two conditional branches return error.InvalidEncoding; } x.cMov(x.mul(Fe.sqrtm1), 1 - @boolToInt(has_m_root)); @@ -130,7 +130,7 @@ pub const Edwards25519 = struct { var pos: usize = 252; while (true) : (pos -= 4) { q = q.dbl().dbl().dbl().dbl(); - const b = (s[pos / 8] >> @intCast(u3, pos & 7)) & 0xf; + const b = (s[pos >> 3] >> @truncate(u3, pos)) & 0xf; q = q.add(pcSelect(pc, b)); if (pos == 0) break; } -- cgit v1.2.3 From 5ab69633b712914cccdf2f08d717387864d6c4c7 Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sat, 15 Aug 2020 11:48:34 +0200 Subject: Constify the ladder --- lib/std/crypto/25519/curve25519.zig | 35 ++++++++++++++--------------------- lib/std/crypto/25519/edwards25519.zig | 4 ++-- 2 files changed, 16 insertions(+), 23 deletions(-) diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig index 3a4871a1f3..46d7b9a3a6 100644 --- a/lib/std/crypto/25519/curve25519.zig +++ b/lib/std/crypto/25519/curve25519.zig @@ -43,28 +43,21 @@ pub const Curve25519 = struct { var swap: u8 = 0; var pos: usize = bits - 1; while (true) : (pos -= 1) { - const b = (s[pos >> 3] >> @truncate(u3, pos)) & 1; - swap ^= b; + const bit = (s[pos >> 3] >> @truncate(u3, pos)) & 1; + swap ^= bit; Fe.cSwap2(&x2, &x3, &z2, &z3, swap); - swap = b; - var tmp0 = x3.sub(z3); - var tmp1 = x2.sub(z2); - x2 = x2.add(z2); - z2 = x3.add(z3); - z3 = tmp0.mul(x2); - z2 = z2.mul(tmp1); - tmp0 = tmp1.sq(); - tmp1 = x2.sq(); - x3 = z3.add(z2); - z2 = z3.sub(z2); - x2 = tmp1.mul(tmp0); - tmp1 = tmp1.sub(tmp0); - z2 = z2.sq(); - z3 = tmp1.mul32(121666); - x3 = x3.sq(); - tmp0 = tmp0.add(z3); - z3 = x1.mul(z2); - z2 = tmp1.mul(tmp0); + swap = bit; + const a = x2.add(z2); + const b = x2.sub(z2); + const aa = a.sq(); + const bb = b.sq(); + x2 = aa.mul(bb); + const e = aa.sub(bb); + const da = x3.sub(z3).mul(a); + const cb = x3.add(z3).mul(b); + x3 = da.add(cb).sq(); + z3 = x1.mul(da.sub(cb).sq()); + z2 = e.mul(bb.add(e.mul32(121666))); if (pos == 0) break; } Fe.cSwap2(&x2, &x3, &z2, &z3, swap); diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index 93b1a69d17..5d70122921 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -130,8 +130,8 @@ pub const Edwards25519 = struct { var pos: usize = 252; while (true) : (pos -= 4) { q = q.dbl().dbl().dbl().dbl(); - const b = (s[pos >> 3] >> @truncate(u3, pos)) & 0xf; - q = q.add(pcSelect(pc, b)); + const bit = (s[pos >> 3] >> @truncate(u3, pos)) & 0xf; + q = q.add(pcSelect(pc, bit)); if (pos == 0) break; } try q.rejectIdentity(); -- cgit v1.2.3 From 08dfbee961b7705d6f9d03fc982ec808f370f64a Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sat, 15 Aug 2020 18:03:38 +0200 Subject: Benchmark signatures --- lib/std/crypto/benchmark.zig | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) diff --git a/lib/std/crypto/benchmark.zig b/lib/std/crypto/benchmark.zig index f0f40bd231..267c2881b4 100644 --- a/lib/std/crypto/benchmark.zig +++ b/lib/std/crypto/benchmark.zig @@ -90,7 +90,6 @@ pub fn benchmarkKeyExchange(comptime DhKeyExchange: anytype, comptime exchange_c var out: [DhKeyExchange.minimum_key_length]u8 = undefined; prng.random.bytes(out[0..]); - var offset: usize = 0; var timer = try Timer.start(); const start = timer.lap(); { @@ -107,6 +106,30 @@ pub fn benchmarkKeyExchange(comptime DhKeyExchange: anytype, comptime exchange_c return throughput; } +const signatures = [_]Crypto{Crypto{ .ty = crypto.Ed25519, .name = "ed25519" }}; + +pub fn benchmarkSignatures(comptime Signature: anytype, comptime signatures_count: comptime_int) !u64 { + var seed: [Signature.seed_length]u8 = undefined; + prng.random.bytes(seed[0..]); + const msg = [_]u8{0} ** 64; + const key_pair = try Signature.createKeyPair(seed); + + var timer = try Timer.start(); + const start = timer.lap(); + { + var i: usize = 0; + while (i < signatures_count) : (i += 1) { + _ = try Signature.sign(&msg, key_pair, null); + } + } + const end = timer.read(); + + const elapsed_s = @intToFloat(f64, end - start) / time.ns_per_s; + const throughput = @floatToInt(u64, signatures_count / elapsed_s); + + return throughput; +} + fn usage() void { std.debug.warn( \\throughput_test [options] @@ -183,4 +206,11 @@ pub fn main() !void { try stdout.print("{:>11}: {:5} exchanges/s\n", .{ E.name, throughput }); } } + + inline for (signatures) |E| { + if (filter == null or std.mem.indexOf(u8, E.name, filter.?) != null) { + const throughput = try benchmarkSignatures(E.ty, mode(1000)); + try stdout.print("{:>11}: {:5} signatures/s\n", .{ E.name, throughput }); + } + } } -- cgit v1.2.3 From ab6ffa8a3c1e3fa802cacd970d3ed415ba25a85e Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sat, 15 Aug 2020 21:00:22 +0200 Subject: Work around sqrtRatioM1() issue in release-safe mode --- lib/std/crypto/25519/ristretto255.zig | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/lib/std/crypto/25519/ristretto255.zig b/lib/std/crypto/25519/ristretto255.zig index 21b305f89d..bfdeb41f9d 100644 --- a/lib/std/crypto/25519/ristretto255.zig +++ b/lib/std/crypto/25519/ristretto255.zig @@ -24,11 +24,11 @@ pub const Ristretto255 = struct { const has_f_root = f_root_check.isZero(); const x_sqrtm1 = x.mul(Fe.sqrtm1); // x*sqrt(-1) x.cMov(x_sqrtm1, @boolToInt(has_p_root) | @boolToInt(has_f_root)); - x = x.abs(); + const xa = x.abs(); if ((@boolToInt(has_m_root) | @boolToInt(has_p_root)) == 0) { return error.NoRoot; } - return x; + return xa; } fn rejectNonCanonical(s: [32]u8) !void { -- cgit v1.2.3 From 37ae2464053628d10c7e7e7165ba8a267006b0ad Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sat, 15 Aug 2020 21:14:56 +0200 Subject: Inline Fe.{sub,mul,sq} for a performance boost in release-safe mode --- lib/std/crypto/25519/field.zig | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/lib/std/crypto/25519/field.zig b/lib/std/crypto/25519/field.zig index 59aa1e3ba9..121d187e17 100644 --- a/lib/std/crypto/25519/field.zig +++ b/lib/std/crypto/25519/field.zig @@ -114,7 +114,7 @@ pub const Fe = struct { return fe; } - pub fn sub(a: Fe, b: Fe) Fe { + pub inline fn sub(a: Fe, b: Fe) Fe { var fe = b; comptime var i = 0; inline while (i < 4) : (i += 1) { @@ -200,7 +200,7 @@ pub const Fe = struct { return .{ .limbs = rs }; } - pub fn mul(a: Fe, b: Fe) Fe { + pub inline fn mul(a: Fe, b: Fe) Fe { var ax: [5]u128 = undefined; var bx: [5]u128 = undefined; var a19: [5]u128 = undefined; @@ -223,7 +223,7 @@ pub const Fe = struct { return _carry128(&r); } - fn _sq(a: Fe, double: comptime bool) Fe { + inline fn _sq(a: Fe, double: comptime bool) Fe { var ax: [5]u128 = undefined; var r: [5]u128 = undefined; comptime var i = 0; -- cgit v1.2.3 From 7f9a227abfbce0e67746cc57dd9b6a4bf0a8d94a Mon Sep 17 00:00:00 2001 From: Frank Denis Date: Sun, 16 Aug 2020 00:58:14 +0200 Subject: deinline edwards25519.{add,dbl} --- lib/std/crypto/25519/edwards25519.zig | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig index 5d70122921..11f5963101 100644 --- a/lib/std/crypto/25519/edwards25519.zig +++ b/lib/std/crypto/25519/edwards25519.zig @@ -74,7 +74,7 @@ pub const Edwards25519 = struct { } /// Double an Edwards25519 point. - pub inline fn dbl(p: Edwards25519) Edwards25519 { + pub fn dbl(p: Edwards25519) Edwards25519 { const t0 = p.x.add(p.y).sq(); var x = p.x.sq(); var z = p.y.sq(); @@ -91,7 +91,7 @@ pub const Edwards25519 = struct { } /// Add two Edwards25519 points. - pub inline fn add(p: Edwards25519, q: Edwards25519) Edwards25519 { + pub fn add(p: Edwards25519, q: Edwards25519) Edwards25519 { const a = p.y.sub(p.x).mul(q.y.sub(q.x)); const b = p.x.add(p.y).mul(q.x.add(q.y)); const c = p.t.mul(q.t).mul(Fe.edwards25519d2); -- cgit v1.2.3